text:
# Construction 1

Counting sets with small sumset, and the clique number of random Cayley graphs
Ben Green111Supported by a grant from the Engineering and Physical Sciences Research Council of the UK and a Fellowship of Trinity College Cambridge.

## Abstract

Given a set $`A/N`$ we may form a Cayley sum graph $`G_A`$ on vertex set $`/N`$ by joining $`i`$ to $`j`$ if and only if $`i+jA`$. We investigate the extent to which performing this construction with a random set $`A`$ simulates the generation of a random graph, proving that the clique number of $`G_A`$ is almost surely $`O(\mathrm{log}N)`$. This shows that Cayley sum graphs can furnish good examples of Ramsey graphs. To prove this result we must study the specific structure of set addition on $`/N`$. Indeed, we also show that the clique number of a random Cayley sum graph on $`\mathrm{\Gamma }=(/2)^n`$ is almost surely not $`O(\mathrm{log}|\mathrm{\Gamma }|)`$.

1. Introduction. There are many papers in which a graph is constructed from a set in something like the following manner.

###### Construction 1

Let $`\mathrm{\Gamma }`$ be a finite abelian group with cardinality $`N`$ and let $`A\mathrm{\Gamma }`$. Define $`G_A`$ to be the graph on vertex set $`\mathrm{\Gamma }`$ in which $`ijE(G_A)`$ precisely when $`i+jA`$.

For any positive integer $`m`$ write $`_m=/m`$. In this paper we will be interested in the two particular groups $`\mathrm{\Gamma }=_N`$ and $`\mathrm{\Gamma }=_2^n`$.
Example. Suppose that $`N`$ is prime and let $`A`$ be the set of quadratic residues modulo $`N`$. The graph $`G_A`$ is then called the Paley sum graph of order $`N`$, and is denoted by $`P_N`$. It is generally thought that the Paley graphs behave much like random graphs from the binomial model $`G(N,1/2)`$, though in many respects this statement is far from being proven. We remind the reader that in this model all (labelled) graphs on $`N`$ vertices occur with equal probability. Equivalently, a graph from $`G(N,1/2)`$ may be generated by picking each possible edge $`ij`$ independently at random with probability $`1/2`$. See  for the basic definitions of random graph theory (and much more).
In the light of the above example it seems natural to address the following question.

###### Question 2

To what extent does choosing a random subset $`A\mathrm{\Gamma }`$ and forming $`G_A`$ simulate the selection of a random graph on $`N`$ vertices?

We call a graph generated using this model a random Cayley sum graph. The reader may have already noticed that there is one sense in which a random Cayley sum graph is definitely not like a random graph – it is always regular. However in a recent paper of Krivelevich, Sudakov, Vu and Wormald  a good quantity of evidence was collected to support the claim that a random regular graph of degree $`N/2`$ (say) behaves in many ways almost exactly like a random graph from the binomial model $`G(N,1/2)`$.
In this paper we will investigate just one aspect of Question 2, the clique number of a random Cayley sum graph. There are clearly other ways in which we might compare a random Cayley sum graph to a random graph. An investigation of the second largest eigenvalue, for example, leads naturally to some classical questions on random trigonometric polynomials. We discuss this matter in a separate paper .
This is really a paper in combinatorial number theory. To see why, let $`A\mathrm{\Gamma }`$ and consider what it means for $`X\mathrm{\Gamma }`$ to span a clique in $`G_A`$. We must have $`i+jA`$ whenever $`i,j`$ are distinct elements of $`X`$. Now the set $`\{i+j:i,jX,ij\}`$ is called the restricted sumset of $`X`$ with itself and is normally written $`X\widehat{+}X`$. Thus we see that $`X`$ spans a clique in $`G_A`$ if and only if $`X\widehat{+}XA`$.
Now if $`X`$ is highly structured, for example if it is an arithmetic progression, then $`|X\widehat{+}X|`$ is rather small compared to $`|X|`$ and the probability that $`G_A`$ contains the clique spanned by $`X`$ will be quite large. This does not mean, however, that the clique number of a random Cayley graph is very large since there are rather few arithmetic progressions.
Let $`k,m`$, and make the following definition.

###### Definition 3

$`S_k^m(\mathrm{\Gamma })`$ is the collection of sets $`X\mathrm{\Gamma }`$ with $`|X|=k`$ and $`|X\widehat{+}X|=m`$.

Observe that $`S_k^m(\mathrm{\Gamma })`$ is empty if $`m<k1`$. Now one can easily write down a formula for $`E(\mathrm{\Gamma },k)`$, the expected number of $`k`$-cliques in a random Cayley graph on $`\mathrm{\Gamma }`$. Indeed one has

$`E(\mathrm{\Gamma };k)`$ $`=`$ $`{\displaystyle \underset{X\mathrm{\Gamma }:|X|=k}{}}(X\text{ is a clique in }G_A)`$
$`=`$ $`{\displaystyle \underset{mk1}{}}{\displaystyle \underset{XS_k^m(\mathrm{\Gamma })}{}}(X\widehat{+}XA)`$
$`=`$ $`{\displaystyle \underset{mk1}{}}{\displaystyle \underset{XS_k^m(\mathrm{\Gamma })}{}}2^m`$
$`=`$ $`{\displaystyle \underset{mk1}{}}|S_k^m(\mathrm{\Gamma })|2^m.`$
Now suppose we could show, for some function $`F=F_\mathrm{\Gamma }:`$, that $`E(\mathrm{\Gamma },F(N))=o(1)`$. Writing $`\omega `$ for the clique number and $`\mathrm{\Omega }_k`$ for the number of cliques of size $`k`$ we would then have

$$(\omega F(N))=(\mathrm{\Omega }_{F(N)}1)E(\mathrm{\Gamma },F(N))=o(1)$$

by Markov’s inequality. That is, the clique number of a random Cayley graph on $`\mathrm{\Gamma }`$ is almost surely at most $`F(N)`$. As a result of these observations our attention is drawn to the problem of finding effective upper bounds for $`|S_k^m(\mathrm{\Gamma })|`$.
Further notation and background. Let $`|\mathrm{\Gamma }|=N`$ and consider the sample space $`\mathrm{\Omega }_N`$ consisting of all graphs on $`N`$ vertices. If $`E=E_N`$ is an event in this sample space then we write

* $`_{\text{ran}}^{(N)}(E)`$ for the probability that a random graph from $`G(N,1/2)`$ satisfies $`E`$;
* $`_{\text{reg}}^{(N)}(E)`$ for the probability that a graph selected from $`𝒢_{N,N/2}`$ satisfies $`E`$, where $`𝒢_{N,N/2}`$ puts the uniform distribution on all the $`N/2`$-regular graphs on $`N`$ labelled vertices;
* $`_\mathrm{\Gamma }(E)`$ for the probability that if $`A\mathrm{\Gamma }`$ is chosen randomly, then the Cayley sum graph $`G_A`$ satisfies $`E`$.

The following well-known result concerning the clique number of a random graph (see, for example, ) sets our later results in context. In this paper, all logs are to the base 2 unless otherwise specified.

###### Theorem 4

For any fixed $`ϵ>0`$ we have

$$\underset{N\mathrm{}}{lim}_{\text{ran}}^{(N)}\left((2ϵ)\mathrm{log}N\omega (2+ϵ)\mathrm{log}N\right)=\mathrm{\hspace{0.33em}1}.$$

In  the same result is proved for random regular graphs:

###### Theorem 5

For any fixed $`ϵ>0`$ we have

$$\underset{N\mathrm{}}{lim}_{\text{reg}}^{(N)}\left((2ϵ)\mathrm{log}N\omega (2+ϵ)\mathrm{log}N\right)=\mathrm{\hspace{0.33em}1}.$$

Questions equivalent to estimating the clique number of a random Cayley sum graph appear in various places in the literature222The author would like to thank Benny Sudakov for drawing his attention to the two papers ., such as . To the best of my knowledge the following result, which is essentially given in , is the best known.

###### Theorem 6

There is an absolute constant $`C`$ such that

$$\underset{N\mathrm{}}{lim}__N\left(\omega C(\mathrm{log}N)^2\right)=\mathrm{\hspace{0.33em}1}.$$

A similar result is mentioned in , where it is remarked that it would be interesting to try and improve on it, and also, without proof, in .
Let us conclude this section by making a remark concerning our terminology. We use the term Cayley sum graph to make it clear that the objects we are considering are very slightly different from what are normally called Cayley graphs. In an abelian group $`\mathrm{\Gamma }`$ a (true) Cayley graph is formed as follows. Take a symmetric set $`A`$, that is to say a set in which $`aA`$ implies that $`aA`$. Form a graph on vertex set $`\mathrm{\Gamma }`$ by joining $`i`$ to $`j`$ if and only if $`ijA`$. The group $`\mathrm{\Gamma }`$ acts on the resulting graph in an obvious way, and for this reason true Cayley graphs are perhaps more natural than Cayley sum graphs. From the rather number-theoretical point of view of this paper, however, the treatment of Cayley sum graphs seems to be a little tidier. The methods of this paper apply to true Cayley graphs with minimal modifications. When $`\mathrm{\Gamma }=_2^n`$, of course, the two types of graph actually coincide.
2. Statement of results. The main result of this paper is the following improvement of Theorem 6.

###### Theorem 7

We have

$$\underset{N\mathrm{}}{lim}__N\left(\omega \mathrm{\hspace{0.33em}160}\mathrm{log}N\right)=1.$$

An immediate consequence of Theorem 7 is the following result in Ramsey theory, for which we do not know an independent proof:

###### Theorem 8

For all sufficiently large integers $`N`$ there exists a set $`A_N`$ for which the Cayley sum graph $`G_A`$ has no cliques or independent sets of size $`160\mathrm{log}N`$.

The behaviour of random Cayley sum graphs on $`_2^n`$ is different, reflecting the fact that this group has much richer subgroup structure. We will prove the following.

###### Theorem 9

There are absolute constants $`C_1,C_2>0`$ such that

$$\underset{N\mathrm{}}{lim}_{_2^n}\left(C_1\mathrm{log}N\mathrm{log}\mathrm{log}N\omega C_2\mathrm{log}N\mathrm{log}\mathrm{log}N\right)=\mathrm{\hspace{0.33em}1},$$

where $`N=2^n=|_2^n|`$.

We make no effort to optimise the values of $`C_1`$ and $`C_2`$ in this result.
3. Freiman isomorphism classes. A vital notion in this paper is that of a Freiman isomorphism. Let $`s`$ be a positive integer, let $`A`$ and $`B`$ be subsets of (possibly different) abelian groups and let $`\varphi :AB`$ be a map. Then we say that $`\varphi `$ is a Freiman $`s`$-homomorphism if whenever $`a_1,\mathrm{},a_s,a_1^{},\mathrm{},a_s^{}A`$ satisfy

$$a_1+a_2+\mathrm{}+a_s=a_1^{}+a_2^{}+\mathrm{}+a_s^{}$$
(1)
we have

$$\varphi (a_1)+\varphi (a_2)+\mathrm{}+\varphi (a_s)=\varphi (a_1^{})+\varphi (a_2^{})+\mathrm{}+\varphi (a_s^{}).$$
(2)
If $`\varphi `$ has an inverse which is also a $`s`$-homomorphism then we say that it is a Freiman $`s`$-isomorphism, and write $`A_sB`$. This is the case precisely if (1) holds for any $`a_i,a_i^{}`$ satisfying (2).
This is a standard and very convenient terminology in additive number theory. One must, however, be slightly careful: we invite the reader to consider the obvious map $`\varphi :\{0,1\}_2`$, which is a one to one Freiman 2-homomorphism but not a Freiman isomorphism.
In this paper we will mostly, but not exclusively, be concerned with Freiman $`2`$-homomorphisms. From now on we will refer to these simply as homomorphisms.
In order to discuss the theory of Freiman homomorphisms as cleanly as possible we introduce some further definitions. These are very much in the spirit of , and indeed Lemma 11 below is a crude (though slightly more general) version of one of the results of that paper.
Let $`F`$ be a field, let $`k`$ be a positive integer and let $`W`$ be a vector space over $`F`$. Let $`V_k`$ be a $`k`$-dimensional vector space over $`F`$ with basis $`\{e_1,\mathrm{},e_k\}`$. For any sequence $`\sigma =(a_1,\mathrm{},a_k)`$ of $`k`$ elements of $`W`$ we can define a linear map $`\varphi _\sigma :V_kW`$ by

$$\varphi _\sigma \left(\lambda _ie_i\right)=\lambda _ia_i.$$

If $`v\mathrm{ker}\varphi _\sigma `$ then we say that $`v`$ is satisfied by $`\sigma `$. Let $`s2`$ be an integer. Call any vector of the form

$$e_{i_1}+\mathrm{}+e_{i_s}e_{j_1}\mathrm{}e_{j_s},$$

where the $`i`$s and $`j`$s need not be distinct, an $`s`$-relation. Write $`_s`$ for the set of all $`s`$-relations in $`V_k`$. If $`SV_k`$ write $`\text{Span}(S)`$ for the $`F`$-linear span of the elements of $`S`$.
Now for any subset $`S`$ and any subspace $`U`$ of a vector space one has $`S\text{Span}(SU)=SU`$. Thus in particular

$$_s\text{Span}\left(_s\mathrm{ker}\varphi _\sigma \right)=_s\mathrm{ker}\varphi _\sigma .$$
(3)
That is to say, the set $`_s\mathrm{ker}\varphi _\sigma `$ of $`s`$-relations satisfied by $`\sigma `$ can be completely recovered from the subspace spanned by it.

###### Lemma 10

Suppose that $`\sigma =(a_i)_{i=1}^k`$ and $`\sigma ^{}=(a_i^{})_{i=1}^k`$ are two sequences of distinct elements of $`W`$, and suppose that $`\text{Span}\left(_s\mathrm{ker}\varphi _\sigma \right)=\text{Span}\left(_s\mathrm{ker}\varphi _\sigma ^{}\right)`$. Then the sets $`A=\{a_1,\mathrm{},a_k\}`$ and $`A^{}=\{a_1,\mathrm{},a_k\}`$ are $`s`$-isomorphic.

Proof. By (3) we have $`_s\mathrm{ker}\varphi _\sigma =_s\mathrm{ker}\varphi _\sigma ^{}`$. That is, the set of $`s`$-relations satisfied by $`\sigma `$ and $`\sigma ^{}`$ are the same. An $`s`$-isomorphism between $`A`$ and $`A^{}`$ is therefore given by the map $`a_ia_i^{}`$.

###### Lemma 11

The number of $`s`$-isomorphism classes of subsets of $`W`$ of size $`k`$ is at most $`k^{2sk}`$.

Proof. Given any set $`A=\{a_1,\mathrm{},a_k\}W`$ we may form a sequence $`\sigma =(a_1,\mathrm{},a_k)`$. By Lemma 10 the number of $`s`$-isomorphism classes of sets $`A`$ is at most the number of subspaces of $`V_k`$ spanned by $`s`$-relations. There are at most $`k^{2s}`$ of these $`s`$-relations, and any such subspace is spanned by some subset of at most $`k`$ of them. The required bound follows.
Now if $`W,W^{}`$ are two vector spaces over $`F`$ and if $`AW`$ then the space $`\text{Hom}_s(A,W^{})`$ of Freiman $`s`$-homomorphisms $`\varphi :AW^{}`$ is a vector space over $`F`$. We call $`r_F(A)=dim\text{Hom}_2(A,F)1`$ the Freiman dimension of $`A`$. It is easy to see that $`dim\text{Hom}_2(A,W^{})=(r_F(A)+1)^{dimW^{}}`$. In a short while we will prove the main result of this section, Lemma 13. Let us first prepare the ground with the following lemma from linear algebra.

###### Lemma 12

Let $`F`$ be a field, let $`A`$ be a finite non-empty set, and let $`\mathrm{\Phi }`$ be a subspace of $`\mathrm{\Psi }`$, the vector space of all maps from $`A`$ to $`F`$. Write $`d=dim\mathrm{\Phi }`$. Then there exists a subset $`\{a_1,\mathrm{},a_d\}A`$ with the following properties.
*(i)* For any $`f_1,\mathrm{},f_dF`$ there is a unique $`\varphi \mathrm{\Phi }`$ with $`\varphi (a_i)=f_i`$ *(*$`i=1,\mathrm{},d`$*)*.
*(ii)* If $`aA`$ then there are $`\lambda _1,\mathrm{},\lambda _dF`$ *(*depending only on $`a`$*)* such that $`\varphi (a)=\lambda _1\varphi (a_1)+\mathrm{}+\lambda _d\varphi (a_d)`$ for any $`\varphi \mathrm{\Phi }`$. If the constant map, which sends everything in $`A`$ to $`1_F`$, lies in $`\mathrm{\Phi }`$ then we may assume that $`\lambda _1+\mathrm{}+\lambda _d=1`$.

Proof. Let $`A=\{a_1,\mathrm{},a_k\}`$. Choose as a basis for $`\mathrm{\Psi }`$ the set $`\{\alpha _1,\mathrm{},\alpha _k\}`$ of maps defined by the conditions $`\alpha _i(a_j)=\delta _{ij}`$. Now we may find some $`kd`$ of the $`\alpha _i`$ which, when taken together with $`\mathrm{\Phi }`$, span the whole of $`\mathrm{\Psi }`$. Relabeling if necessary we may assume that these elements are $`\alpha _{d+1},\mathrm{},\alpha _k`$, so that

$$\mathrm{\Psi }=\mathrm{\Phi }\text{Span}(\alpha _{d+1},\mathrm{},\alpha _k).$$
(4)
It follows that for any $`f_1,\mathrm{},f_dF`$ we may find $`\varphi \mathrm{\Phi }`$ and $`\mu _{d+1},\mathrm{},\mu _kF`$ so that

$$f_1\alpha _1+\mathrm{}+f_d\alpha _d=\varphi +\mu _{d+1}\alpha _{d+1}+\mathrm{}+\mu _k\alpha _k,$$

implying that $`\varphi (a_i)=f_i`$ ($`i=1,\mathrm{},d`$). To see that $`\varphi `$ is unique, suppose that $`\varphi ^{}(a_i)=\varphi ^{\prime \prime }(a_i)`$ for some $`\varphi ^{},\varphi ^{\prime \prime }\mathrm{\Phi }`$ and all $`i=1,\mathrm{},d`$. Then $`\varphi ^{}\varphi ^{\prime \prime }\text{Span}(\alpha _{d+1},\mathrm{},\alpha _k)`$ and thus $`\varphi ^{}\varphi ^{\prime \prime }=0`$ since the sum in (4) is direct.

As for assertion (ii), observe that any $`xA`$ induces a linear functional $`t_x:\mathrm{\Phi }F`$ via the rule $`t_x(\varphi )=\varphi (x)`$. For a fixed $`aA`$ the $`d+1`$ linear functionals $`t_a,t_{a_1},\mathrm{},t_{a_d}`$ are linearly dependent and therefore we can find $`\mu ,\mu _1,\mathrm{},\mu _dF`$, not all zero, so that

$$\mu \varphi (a)+\mu _1\varphi (a_1)+\mathrm{}+\mu _d\varphi (a_d)=\mathrm{\hspace{0.33em}0}$$
(5)
for any $`\varphi \mathrm{\Phi }`$. If $`\mu `$ were equal to zero then we could easily contradict (i) by setting $`f_i=1`$ and $`f_j=0`$ for $`ji`$. Therefore this is not the case and we may divide (5) through by $`\mu `$ to get (ii) (with $`\lambda _i=\mu ^1\mu _i`$ for $`i=1,\mathrm{},d`$). If the constant map lies in $`\mathrm{\Phi }`$ then (5) must hold for it, which implies that $`\lambda _1+\mathrm{}+\lambda _d=1`$.

###### Lemma 13

Let $`W`$ and $`W^{}`$ be finite-dimensional vector spaces over a field $`F`$ and let $`AW`$ be a finite non-empty set of Freiman dimension $`r=r_F(A)`$. Then there is a subset $`\{a_1,\mathrm{},a_{r+1}\}A`$ with the following properties.
*(i)* For any $`w_1^{},\mathrm{},w_{r+1}^{}W^{}`$ there is a unique $`\varphi \text{Hom}_2(A,W^{})`$ with $`\varphi (a_i)=w_i^{}`$ *(*$`i=1,\mathrm{},r+1`$*)*. Moreover, if $`w_1^{},\mathrm{},w_{r+1}^{}`$ are linearly independent then $`\varphi `$ is an isomorphism.
*(ii)* If $`aA`$ then there are $`\lambda _1,\mathrm{},\lambda _{r+1}F`$ *(*depending only on $`a`$*)* with $`\lambda _1+\mathrm{}+\lambda _{r+1}=1_F`$ and such that $`\varphi (a)=\lambda _1\varphi (a_1)+\mathrm{}+\lambda _{r+1}\varphi (a_{r+1})`$ for any $`\varphi \text{Hom}_2(A,W^{})`$.

Proof. Part (ii) and the first part of (i) are swift consequences of Lemma 12, (i). Although that lemma deals only with homomorphisms from $`A`$ to $`F`$, the required extension follows easily using the isomorphism $`\text{Hom}_2(A,F^n)(\text{Hom}_2(A,F))^n`$.

To prove the second assertion of (i), suppose that suppose that $`\varphi \text{Hom}_2(A,W^{})`$ is not a Freiman isomorphism. Then there are elements $`a,a^{},a^{\prime \prime },a^{\prime \prime \prime }A`$ such that $`\varphi (a)+\varphi (a^{})=\varphi (a^{\prime \prime })+\varphi (a^{\prime \prime \prime })`$ but $`a+a^{}a^{\prime \prime }+a^{\prime \prime \prime }`$. By part (ii) there are $`u_i,u_i^{},u_i^{\prime \prime },u_i^{\prime \prime \prime }F`$ such that $`\psi (a)=_{i=1}^{r+1}u_i\psi (a_i)`$ for all $`\psi \text{Hom}_2(A,V)`$, for any vector space $`V`$ over $`F`$ (and similarly for $`a^{},a^{\prime \prime },a^{\prime \prime \prime }`$). One has

$$\psi (a)+\psi (a^{})\psi (a^{\prime \prime })\psi (a^{\prime \prime \prime })=\underset{i=1}{\overset{r+1}{}}(u_i+u_i^{}u_i^{\prime \prime }u_i^{\prime \prime \prime })\psi (a_i)$$
(6)
for all $`\psi `$. Taking $`V=W`$ and $`\psi =\text{id}`$ we see that not all of the $`u_i+u_i^{}u_i^{\prime \prime }u_i^{\prime \prime \prime }`$ are zero. Therefore, setting $`V=W^{}`$ and $`\psi =\varphi `$, one sees that $`\varphi (a_1),\mathrm{},\varphi (a_{r+1})`$ must be linearly dependent.

###### Corollary 14

Let $`AW`$. Then $`r=r_F(A)`$ is the largest integer $`d`$ such that $`A`$ is isomorphic to a subset of $`F^d`$ which is not contained in an affine subspace. In particular if $`A`$ is a set of integers then $`r_{}(A)=d`$ really is equal to dimension in the original sense of Freiman **.

Proof. Apply Lemma 13 (ii) with $`W^{}=W`$ and $`\varphi =\text{id}`$. It follows that there are $`\{a_1,a_2,\mathrm{},a_{r+1}\}`$ such that $`A`$ is a subset of $`\{\lambda _1a_1+\mathrm{}+\lambda _{r+1}a_{r+1}:\lambda _1+\mathrm{}+\lambda _{r+1}=1_F\}`$, an affine space over $`F`$ of dimension $`r`$. As $`r_F(A)`$ is clearly an isomorphism invariant, the same must be true of any set isomorphic to $`A`$ and it therefore follows that $`dr`$. To see that $`rd`$, pick linearly independent vectors $`w_1^{},\mathrm{},w_{r+1}^{}`$ in some space $`W^{}`$, and observe that $`A`$ is isomorphic to some set containing all of the $`w_i^{}`$ by Lemma 13 (i).
4. Isomorphism classes with small doubling. As in the last section, let $`W`$ be a vector space over a field $`F`$. The main result of this section is a bound for the number of mutually non-isomorphic sets $`AW`$ of cardinality $`k`$ with small (restricted) doubling property. The cardinality of $`A\widehat{+}A`$ is an isomorphism invariant and we say that an isomorphism class of sets has small doubling property if $`m=|A\widehat{+}A|`$ is relatively small in comparison to $`|A|`$ for each set in that class.
If $`BW`$ and if $`t`$ is a non-negative integer than a $`t`$-extension of $`B`$ is simply any set $`BE`$ where $`E=\{x_1,\mathrm{},x_t\}`$ and the $`x_i`$ are distinct elements of $`WB`$.

###### Proposition 15

Suppose that $`AW`$ has sufficiently large cardinality $`k=|A|`$ and let $`m=|A\widehat{+}A|`$. Then there exist $`a^{}A`$ and $`A_0,A_1A`$ such that $`|A_0|4k^{1/15}m`$, $`|AA_1|4k^{4/5}m`$ and $`a^{}+A_1A_0\widehat{+}A_0`$.

Proof. Let $`Q=k^{1/5}`$ and $`q=k^{1/15}`$. Draw a graph on vertex set $`A`$ by joining $`x`$ to $`y`$ if $`x+y`$ is $`Q`$-unpopular, that is if the number of pairs $`(w,z)A^2`$, $`wz`$, with $`w+z=x+y`$ is less than $`Q`$. The total number of edges in the graph is no more than $`Qm`$, and so some vertex $`a^{}`$ has degree at most $`2Qm/k`$. This means that with at most $`2Qm/k`$ exceptions the sums $`a^{}+a`$, $`aA`$ are $`Q`$-popular. Pick a set $`XA`$ by choosing each $`aA`$ to lie in $`X`$ independently and at random with probability $`q`$. Let $`Z=\{aA|a^{}+aX\widehat{+}X\}`$. If $`s=a^{}+a`$ is $`Q`$-popular then there are at least $`Q/3`$ disjoint pairs $`(b,c)A^2`$ with $`b+c=s`$ and $`bc`$. For each the probability that both $`b`$ and $`c`$ lie in $`X`$ is $`q^2`$, and so

$$(aZ)(1q^2)^{Q/3}e^{q^2Q/3}.$$

It follows that

$$𝔼|Z|\frac{2Qm}{k}+e^{q^2Q/3}k\mathrm{\hspace{0.33em}3}k^{4/5}m.$$

Clearly we have $`𝔼|X|=qk=k^{14/15}`$ and so

$$𝔼\left(|X|+k^{11/15}|Z|\right)\mathrm{\hspace{0.33em}4}k^{1/15}m.$$
(7)
Pick a specific $`XA`$ for which $`|X|+k^{11/15}|Z|4k^{1/15}m`$, and set $`A_0=X`$, $`A_1=AZ`$. Then $`|A_0|4k^{1/15}m`$, $`|AA_1|4k^{4/5}m`$ and, by construction, $`a^{}+A_1A_0\widehat{+}A_0`$.

###### Lemma 16

Fix a non-negative integer $`t`$ and a set $`BW`$ of cardinality $`|B|=l`$. Then the number of mutually non-isomorphic sets $`A`$ of cardinality $`|A|=l+t`$, such that there exists a subset $`A_0A`$ satisfying $`A_0_3B`$, is at most $`l^{3t^4}`$.

Proof. Write $`B=\{b_1,\mathrm{},b_l\}`$. Given $`A_0A`$ with the required properties write $`A_0=\{a_1,\mathrm{},a_l\}`$ and $`A=A_0\{a_{l+1},\mathrm{},a_{l+t}\}`$ in a manner that respects the 3-isomorphism between $`A_0`$ and $`B`$; that is, for $`i_1,i_2,i_3,i_4,i_5,i_6\{1,\mathrm{},l\}`$

$$b_{i_1}+b_{i_2}+b_{i_3}b_{i_4}b_{i_5}b_{i_6}=\mathrm{\hspace{0.33em}0}$$

if and only if

$$a_{i_1}+a_{i_2}+a_{i_3}a_{i_4}a_{i_5}a_{i_6}=\mathrm{\hspace{0.33em}0}.$$

The isomorphism class of $`A`$ is determined by the 2-relations in $`V_{l+t}`$ satisfied by $`A`$. With each possible relation we can associate its projection $`wV_t`$ onto the last $`t`$ coordinates of $`V_{l+t}`$. There are at most $`t^4`$ non-zero projections $`w`$; fix one of them, say $`w=(1,0,\mathrm{},0)`$, and consider relations corresponding to this specific projection. If $`A`$ satisfies such a relation, say

$$a_{i_1}+a_{l+1}=a_{i_2}+a_{i_3}$$
(8)
with $`i_1,i_2,i_3\{1,\mathrm{},l\}`$, then all other such relations are uniquely determined: they correspond to the equalities $`a_{i_2}+a_{i_3}a_{i_1}=a_{j_2}+a_{j_3}a_{j_1}`$ with $`j_1,j_2,j_3\{1,\mathrm{},l\}`$, hence to the equalities $`b_{i_2}+b_{i_3}b_{i_1}=b_{j_2}+b_{j_3}b_{j_1}`$ with $`j_1,j_2,j_3\{1,\mathrm{},l\}`$. Since there are at most $`l^3`$ choices for the relation (8), there are at most $`l^3`$ choices for the whole system of relations corresponding to $`w`$ which $`A`$ satisfies. Moreover, it is not difficult to see that this conclusion is actually true for any possible $`w0`$. The result follows on observing that to determine the system of relations in $`V_{l+t}`$, satisfied by $`A`$, we must for each non-zero $`wV_t`$ determine the system of relations corresponding to $`w`$.
The next lemma is an easy exercise.

###### Lemma 17

Suppose that $`X_6X^{}`$. Then $`X\widehat{+}X_3X^{}\widehat{+}X^{}`$ and any $`BX\widehat{+}X`$ is $`3`$-isomorphic to a subset of $`X^{}\widehat{+}X^{}`$.

###### Proposition 18

Let $`k`$ be a sufficiently large positive integer and let $`mk^{31/30}`$. Then the number of isomorphism classes of $`AF^k`$ with $`|A|=k`$ and $`|A\widehat{+}A|m`$ is at most $`(em/k)^k\mathrm{exp}\left(k^{31/32}\right)`$.

Proof. By Proposition 15, to any $`AF^k`$ with $`|A|=k`$ and $`|A\widehat{+}A|m`$ there correspond $`a^{}A`$ and $`A_0,A_1A`$ such that $`|A_0|4k^{1/15}m`$, $`|A_1||A|4k^{4/5}m`$ and $`a^{}+A_1A_0\widehat{+}A_0`$. By Lemma 11, the number of possible 6-isomorphism classes to which $`A_0`$ can belong is $`M<\mathrm{exp}\left(k^{30/31}\right)`$; let $`X_1,\mathrm{},X_M`$ be representatives of these classes. By Lemma 17, the set $`a^{}+A_1`$ is 3-isomorphic to a non-empty subset of some $`X_i\widehat{+}X_i`$ of cardinality at most $`k`$; consequently, the number of 3-isomorphism classes to which $`A_1`$ can belong is at most $`Mk(em/k)^k`$. By Lemma 16, each of these 3-isomorphism classes gives rise, by $`t`$-extensions for any fixed $`t4k^{4/5}m`$, to at most $`\mathrm{exp}(k^{29/30})`$ isomorphism classes. Altogether, we get at most

$$\mathrm{exp}(k^{30/31})k(em/k)^k4k^{4/5}m\mathrm{exp}(k^{29/30})<(em/k)^k\mathrm{exp}(k^{31/32})$$

possible isomorphism classes for $`A`$.
5. Avoiding very small doubling. The bound of Proposition 18 becomes rather ineffective when $`m7k`$, say. This section contains a trick which allows us to avoid ever considering sets with extremely small doubling (see, however, the section entitled Concluding Remarks). The result we will actually use, Corollary 20, is a consequence of the following more general proposition.

###### Proposition 19

Let $`k`$ be a sufficiently large positive integer and let $`A`$ be a subset of an abelian group with $`|A|=k`$. Let $`ϵ>0`$ be sufficiently small. Then there is a set $`BA`$ with

$$|B|\frac{3\mathrm{log}(1/ϵ)}{ϵ}\sqrt{k}$$

and $`|B\widehat{+}B|(1ϵ)k`$.

Proof. Let $`p=3ϵ^1\sqrt{\mathrm{log}(6/ϵ)/2k}`$. Choose a set $`BA`$ by picking each element of $`k`$ independently and at random with probability $`p`$. By some rather standard tail estimates (see, for example, \[4, Theorem A.1.4\]) we have

$$\left(\left||B|pk\right|ϵpk/3\right)<\mathrm{\hspace{0.33em}2}e^{2ϵ^2p^2k/9}=ϵ/3.$$
(9)
Now for any $`xB\widehat{+}B`$ write $`s(x)`$ for the number of ordered pairs $`(b_1,b_2)B^2`$ with $`b_1b_2`$ and $`b_1+b_2=x`$. The sum $`M(B)=_xs(x)^2`$ equals the number of quadruples $`(b_1,b_2,b_3,b_4)B^4`$ with $`b_1+b_2=b_3+b_4`$ and $`b_1b_2`$, $`b_3b_4`$. We call these summing quadruples.

Let us divide the summing quadruples $`(a_1,a_2,a_3,a_4)A^4`$ into two classes: those in which $`a_1,a_2,a_3,a_4`$ are all distinct and those in which either $`a_1=a_3,a_2=a_4`$ or $`a_1=a_4,a_2=a_3`$. Call this latter type degenerate; there are less than $`2k^2`$ degenerate quadruples in $`A^4`$, and at most $`k^3`$ non-degenerate ones. Now for a given quadruple, one can calculate the probability that it is also contained in $`B^4`$. This probability is $`p^4`$ if the quadruple is non-degenerate, and $`p^2`$ otherwise. Thus

$$𝔼M(B)=𝔼\left(s(x)^2\right)\mathrm{\hspace{0.33em}2}k^2p^2+k^3p^4.$$

It follows immediately that

$$\left(M(B)\frac{2k^2p^2+k^3p^4}{1ϵ/3}\right)ϵ/3.$$
(10)
Comparing (9) and (10), we see that there is a specific choice of $`B`$ for which

$$\left||B|pk\right|ϵpk/3\text{and}M(B)\frac{2k^2p^2+k^3p^4}{1ϵ/3}.$$
(11)
Now the Cauchy-Schwarz inequality gives

$$M(B)=\underset{xB\widehat{+}B}{}s(x)^2\frac{\left(s(x)\right)^2}{|B\widehat{+}B|}=\frac{|B|^2(|B|1)^2}{|B\widehat{+}B|}.$$

This, together with (11) and a small amount of computation, shows that $`|B\widehat{+}B|(1ϵ)k`$. Moreover we have, from (11), that

$$|B|pk(1+ϵ/3)\frac{3\mathrm{log}(1/ϵ)}{ϵ}\sqrt{k}.$$

This completes the proof.

###### Corollary 20

Let $`k`$ be a sufficiently large positive integer and let $`A`$ be a subset of an abelian group with $`|A|=k`$. Then $`A`$ contains a subset $`C`$, $`|C|k/8`$, with $`|C\widehat{+}C|7|C|`$.

Proof. Apply Proposition 19 with $`ϵ=1/9`$. This supplies us with a set $`B`$, $`|B|100\sqrt{k}`$, such that $`|B\widehat{+}B|8k/9`$. Now simply take $`C`$ to be the union of $`B`$ and some arbitrary elements of $`A`$ so as to ensure that $`|C|`$ lies between $`k/8`$ and $`8k/63`$.
6. The rank of sets with small doubling. In this section we obtain results concerning the Freiman dimension of sets $`A\mathrm{\Gamma }`$ with $`|A|=k`$ and $`|A\widehat{+}A|=m`$. It is in this section that the difference between different groups $`\mathrm{\Gamma }`$ comes to the fore. When $`\mathrm{\Gamma }=_N`$ we can relate $`A`$ to a subset of the integers, but this is not possible for $`\mathrm{\Gamma }=_2^n`$ and, by necessity, we must find a different approach.
Let $`A_N`$ have $`|A|=k`$ and $`|A\widehat{+}A|=m`$ and consider the image $`\overline{A}`$ of $`A`$ under the least positive residue or “unfolding” map $`_N\{1,\mathrm{},N\}`$. This clearly has $`|\overline{A}|=k`$ and $`|\overline{A}\widehat{+}\overline{A}|2m`$. Thus we may apply the following result of Freiman \[8, page 24\].

###### Lemma 21 (Freiman)

Let $`S`$ have cardinality $`k`$ and Freiman dimension $`r=r_{}(S)`$. Then we have the inequality

$$|S\widehat{+}S|r\left(k\frac{r+1}{2}\right).$$

###### Lemma 22

Suppose that $`A_N`$ has $`|A|=k`$ and $`|A\widehat{+}A|=m`$, and let $`\overline{A}`$ be the image of $`A`$ under the unfolding map $`_N`$. Then we have the bound $`r_{}(\overline{A})4m/k`$.

Proof. Observe that $`r=r(\overline{A})k1`$, this being a general property shared by all sets of $`k`$ integers. Applying Lemma 21, we have

$$2m|\overline{A}\widehat{+}\overline{A}|r\left(k\frac{r+1}{2}\right)\frac{1}{2}kr.$$

###### Proposition 23

We have the bounds

$$|S_k^m(_N)|N^{1+\frac{4m}{k}}\left(\frac{2em}{k}\right)^k\mathrm{exp}\left(k^{31/32}\right)$$
(12)
if $`mk^{31/30}/2`$ and

$$|S_k^m(_N)|N^{1+\frac{4m}{k}}k^{4k}$$
(13)
whatever the value of $`m`$.

Proof. It suffices to count the number of lifts $`\overline{A}`$ of sets $`AS_k^m(_N)`$. Let $`X_1,\mathrm{},X_M`$ be a complete set of representatives of the isomorphism classes of subsets $`X`$ of the integers with $`|X|=k`$ and $`|X\widehat{+}X|2m`$. We always have $`Mk^{4k}`$ by Lemma 11 but, when $`mk^{31/30}/2`$, Proposition 18 allows us to do better and we have the bound $`M(2em/k)^k\mathrm{exp}(k^{31/32})`$. Now each $`\overline{A}`$ is the image of some $`X_i`$ under some isomorphism $`\psi :X_i\{1,\mathrm{},N\}`$, and by Lemma 13 (i) there are at most $`N^{r_{}(X_i)+1}`$ such isomorphisms. The proposition follows immediately from these observations and Lemma 22.
We now turn our attention to subsets of $`_2^n`$. An important tool will be the following consequence of an inequality of Plünnecke which was reproved by Ruzsa . If $`G`$ is any abelian group and if $`XG`$ then we write $`kX`$ for the $`k`$-fold sum $`X+X+\mathrm{}+X`$ and $`kXlX`$ for the set $`X+\mathrm{}+XX\mathrm{}X`$, where there are $`k1`$ plus signs and $`l`$ difference signs.

###### Theorem 24 (Plünnecke – Ruzsa)

Let $`AG`$ be such that $`|A+A|C|A|`$. Then for any positive integers $`k`$ and $`l`$ one has

$$|kAlA|C^{k+l}|A|.$$

This allows us to get a bound on the Freiman dimension over $`_2`$ of subsets of $`_2^n`$ with small doubling.

###### Lemma 25

Suppose that $`A_2^n`$ has cardinality $`k`$ and $`|A\widehat{+}A|=m`$. Then $`r__2(A)+14m\mathrm{log}k/k`$.

Proof. By Corollary 14 we may assume (by subjecting $`A`$ to a Freiman isomorphism if necessary) that $`A`$ is not contained in any affine subspace of $`_2^n`$ of dimension less than $`r__2(A)`$.
Let $``$ be an arbitrary ordering on $`_2^n`$ and let $`h=\mathrm{log}_ek`$. Suppose that $`|A|=k`$ and that $`|A\widehat{+}A|=m`$, so that $`|A+A|m+1`$ (we are in characteristic 2!), and let $`XA`$ be a subset of $`A`$ which is such that the sums $`x_1+x_2+\mathrm{}+x_h`$ ($`x_1\mathrm{}x_h`$) are all distinct, and which is maximal with respect to this property. If $`|X|h`$ then we have, using Theorem 24,

$`\left({\displaystyle \frac{|X|}{h}}\right)^h`$ $``$ $`\left({\displaystyle \genfrac{}{}{0pt}{}{|X|}{h}}\right)`$
$``$ $`|hX|`$
$``$ $`|hA|`$
$``$ $`\left({\displaystyle \frac{m+1}{k}}\right)^hk.`$
It follows immediately from this that

$$|X|\mathrm{\hspace{0.33em}2}mhk^{1+1/h}\mathrm{\hspace{0.33em}4}m\mathrm{log}k/k.$$
(14)
Now the maximality of $`X`$ implies that if we set $`Y=X\{a\}`$ for any $`aAX`$ then some two of the sums $`y_1+\mathrm{}+y_h`$, $`y_1^{}+\mathrm{}+y_h^{}`$ must be equal, where $`y_1\mathrm{}y_h`$ and $`y_1^{}\mathrm{}y_h^{}`$. It is clear that precisely one of the $`y_i`$’s or $`y_i^{}`$’s must equal $`a`$, and so $`ahX(h1)X`$. In particular, $`A`$ is contained in the affine subspace of $`_2^n`$ spanned by $`X`$. The required inequality follows.
It is interesting to compare this with the estimate

$$r__2(A)+1\mathrm{log}k+(m/k)^4+2\mathrm{log}(m/k).$$

This bound, which follows from the work of Ruzsa  on Freiman’s theorem in torsion groups, is stronger than Lemma 25 when $`m/k(\mathrm{log}k)^{1/3}`$. Ruzsa and I, in work in progress, can improve this bound to something more like $`\mathrm{log}k+2(m/k)^2`$. It would be interesting to know the true behaviour: perhaps $`r\mathrm{log}k+Cm/k`$.

###### Proposition 26

We have the bounds

$$|S_k^m(_2^n)|N^{\frac{4m\mathrm{log}k}{k}}\left(\frac{em}{k}\right)^k\mathrm{exp}\left(k^{31/32}\right)$$
(15)
if $`mk^{31/30}`$ and

$$|S_k^m(_2^n)|N^{\frac{4m\mathrm{log}k}{k}}k^{4k}$$
(16)
whetever the value of $`m`$.

Proof. This is slightly more straightforward than Proposition 23. Let $`X_1,\mathrm{},X_M`$ be a complete set of representatives of the isomorphism classes of sets $`X_2^n`$ with $`|X|=k`$ and $`|X\widehat{+}X|m`$. Proposition 18 gives bounds for $`M`$, and we know that any set $`AS_k^m(_2^n)`$ is the image of some $`X_i`$ under an isomorphism $`\psi :X_i_2^n`$. Lemma 13, (i) and Lemma 25 allow us to bound the number of such isomorphisms.
7. Putting everything together. In this section we use Propositions 23 and 26 to give upper bounds for the sums

$$\underset{m7k}{}|S_k^m(\mathrm{\Gamma })|2^m$$

when $`\mathrm{\Gamma }=_N`$ and $`_2^n`$. An application of Proposition 19 will then allow us to prove Theorems 7 and 9. We begin with Theorem 7. Let $`k=20\mathrm{log}N`$. Using (12) and (13) we have

$`{\displaystyle \underset{m7k}{}}|S_k^m(_N)|2^m`$ $`=`$ $`{\displaystyle \underset{m=7k}{\overset{k^{31/30}/2}{}}}|S_k^m(_N)|2^m+{\displaystyle \underset{m=k^{31/30}/2}{\overset{k(k1)/2}{}}}|S_k^m(_N)|2^m`$
$``$ $`{\displaystyle \underset{m=7k}{\overset{k^{31/30}/2}{}}}2^{m\left(\left(\frac{4}{k}+\frac{1}{m}\right)\mathrm{log}N+\frac{k}{m}\mathrm{log}\left(\frac{2em}{k}\right)1+o(1)\right)}+{\displaystyle \underset{mk^{31/30}/2}{}}2^{m\left(\frac{4\mathrm{log}N}{k}1+o(1)\right)}`$
Now $`\mathrm{log}(2eC)/C10.2499`$ when $`C7`$, and so both of the sums appearing here are bounded above by $`N^2`$ for $`N`$ sufficiently large.
Now suppose that some randomly selected set $`A_N`$ contains $`X\widehat{+}X`$ with $`|X|=k`$. Then, by Proposition 19, $`A`$ contains some set $`Y\widehat{+}Y`$ where $`|Y|k/8`$ and $`|Y\widehat{+}Y|7|Y|`$. However if $`k=160\mathrm{log}N`$ then the expected number of such sets $`Y`$ that $`A`$ contains is at most $`N^2`$, and in particular the probability that it contains even one is $`o(1)`$. It follows immediately that almost surely $`A`$ does not contain any $`X\widehat{+}X`$ with $`|X|=160\mathrm{log}N`$, and this is the claim of Theorem 7.
Similar computations apply for the group $`_2^n`$, but now of course we use formulae (15) and (16) of Proposition 26 instead. Let $`k=11\mathrm{log}N\mathrm{log}\mathrm{log}N`$. One has

$`{\displaystyle \underset{m7k}{}}|S_k^m(_2^n)|2^m`$ $`=`$ $`{\displaystyle \underset{m=7k}{\overset{k^{31/30}/2}{}}}|S_k^m(_2^n)|2^m+{\displaystyle \underset{m=k^{31/30}/2}{\overset{k(k1)/2}{}}}|S_k^m(_2^n)|2^m`$
$``$ $`{\displaystyle \underset{m=7k}{\overset{k^{31/30}/2}{}}}2^{m\left(\frac{4\mathrm{log}k\mathrm{log}N}{k}+\frac{k}{m}\mathrm{log}\left(\frac{em}{k}\right)1+o(1)\right)}+{\displaystyle \underset{mk^{31/30}/2}{}}2^{m\left(\frac{4\mathrm{log}k\mathrm{log}N}{k}1+o(1)\right)}`$
Now $`\mathrm{log}(eC)/C10.39`$ when $`C7`$, and so both sums appearing here are bounded above by $`N^2`$ for $`N`$ sufficiently large. The rest of the argument proceeds exactly as before, and one gets Theorem 9 (with $`C_2=308`$).
8. A lower bound for $`_2^n`$. In this section we prove the lower bound in Theorem 9. Throughout this section we write $`\mathrm{\Gamma }=_2^n`$ and $`N=|\mathrm{\Gamma }|`$.

###### Proposition 27

$$\underset{n\mathrm{}}{lim}_\mathrm{\Gamma }(\omega \frac{1}{4}\mathrm{log}N\mathrm{log}\mathrm{log}N)=\mathrm{\hspace{0.33em}1}.$$

Proof. Let $`k=\mathrm{log}n+\mathrm{log}\mathrm{log}n1`$ and consider all $`k`$-dimensional subspaces $`H_1,\mathrm{},H_M`$ of $`\mathrm{\Gamma }`$, where

$$M=\frac{(2^n1)(2^n2)\mathrm{}(2^n2^{k1})}{(2^k1)(2^k2)\mathrm{}(2^k2^{k1})}\mathrm{\hspace{0.33em}2}^{nkk^2}.$$

For a random set $`A\mathrm{\Gamma }`$ let $`X_i`$ denote the indicator function of the event $`H_i\{0\}A`$, and let $`X=X_1+\mathrm{}+X_M`$. We have

$$𝔼X\mathrm{\hspace{0.33em}2}^{nkk^22^k}.$$
(17)
We will also estimate $`\text{Var}(X)`$, and to do this it is necessary to prove a lemma.

###### Lemma 28

The number of pairs $`(i,j)`$ for which $`dim(H_iH_j)=l`$, $`0lk`$, is at most $`2^{n(2kl)}`$.

Proof of Lemma. We will show that the quantity in question is exactly

$$\frac{(2^n1)(2^n2)\mathrm{}(2^n2^{2kl1})}{(2^k2^l)^2\mathrm{}(2^k2^{k1})^2(2^l1)(2^l2)\mathrm{}(2^l2^{l1})},$$

which is easily seen to be at most $`2^{n(2kl)}`$. To make this count, first pick the intersection $`L=H_iH_j`$ in any of

$$\frac{(2^n1)(2^n2)\mathrm{}(2^n2^{l1})}{(2^l1)(2^l2)\mathrm{}(2^l2^{l1})}$$

ways. Then pick vectors $`u_1,\mathrm{},u_{kl},v_1,\mathrm{},v_{kl}`$ so that $`H_i=\text{Span}(L,u_1,\mathrm{},u_{kl})`$ and $`H_j=\text{Span}(L,v_1,\mathrm{},v_{kl})`$. The subspace $`L`$ together with all the points $`u_i,v_i`$ spans a subspace of dimension $`2kl`$, so the number of choices for the $`u_i,v_i`$ is

$$(2^n2^l)(2^n2^{l+1})\mathrm{}(2^n2^{2kl1}).$$

However, many of these choices will give the same subspaces $`H_i,H_j`$. If $`H_i,H_j`$ are fixed and have $`H_iH_j=L`$ then there are $`(2^k2^l)\mathrm{}(2^k2^{k1})`$ ways of choosing $`u_1,\mathrm{},u_{kl}`$ so that $`H_i=\text{Span}(L,u_1,\mathrm{},u_{kl})`$, and the same number of ways of choosing $`v_1,\mathrm{},v_{kl}`$. This completes the proof of the lemma.
Now the covariance $`\text{Cov}(X_i,X_j)`$ is positive if and only if $`H_i\{0\}`$ intersects $`H_j\{0\}`$, which requires $`dim(H_iH_j)1`$. Thus we have, using the lemma,

$`\text{Var}(X)`$ $`=`$ $`{\displaystyle \underset{i,j}{}}\text{Cov}(X_i,X_j)`$
$``$ $`2{\displaystyle \underset{l=1}{\overset{k}{}}}2^{n(2kl)}2^{2^{k+1}}\left(2^{2^l}1\right)`$
$``$ $`2{\displaystyle \underset{l=1}{\overset{k}{}}}2^{2kn2^{k+1}+2^lnl}.`$
Now one can check that $`2^lnl2n`$ for $`1lk`$, and so

$$\text{Var}(X)\mathrm{\hspace{0.33em}8}k2^{(2k1)n2^{k+1}}.$$

Now Chebyshev’s inequality tells us that

$$(X=0)\frac{\text{Var}(X)}{(𝔼X)^2}\mathrm{\hspace{0.33em}8}k2^{2k^2n},$$

which is $`o(1)`$. This means that with probability $`1o(1)`$ the set $`A`$ contains some $`H_i\{0\}`$. Note, however, that $`H_i\{0\}`$ is precisely $`H_i\widehat{+}H_i`$.
9. Concluding remarks. It would certainly be of interest to determine the clique number of a random Cayley sum graph on $`_N`$ asymptotically (almost surely). There are several points at which are argument leading to Theorem 7 was suboptimal. One was that we rather shied away from the issue of counting sets with extremely small doubling property, resorting instead to the trick of Proposition 19. It is possible to say rather more about these using Freiman’s deep theorem , which says that such sets are economically contained in a multidimensional arithmetic progression. It was also rather wasteful to treat subsets of $`_N`$ by using the unfolding map $`_N\{1,\mathrm{},N\}`$ in such a naïve way. When $`N`$ is prime, it is possible to prove the following result:

###### Proposition 29

Suppose that $`N`$ is prime and that $`A`$ is a subset of $`_N`$ with $`|A\widehat{+}A|(\mathrm{log}N)^2/32`$. Then there are $`\lambda _N^{},\mu _N`$ for which $`\lambda A+\mu \{0,\mathrm{},N/2\}`$.

By subjecting our set $`A`$ to such a homothety one can ensure that the unfolding map induces a Freiman isomorphism, so that the lifting $`\overline{A}`$ has $`|\overline{A}\widehat{+}\overline{A}|=m`$. Proposition 29 may be called a rectification principle in the spirit of .
Using these results, and tidying up the approximations used in, for example, Lemma 22, one can certainly reduce the number 160 drastically, and perhaps even to $`(3+ϵ)`$. To do this would be difficult, and there seem to be some even more substantial obstacles to pushing the constant down to $`(2+ϵ)`$, which seems likely to be the correct value. We may return to these issues in a future paper.
Another issue deserving of remark arises from the result of Graham and Ringrose , which implies that there is an absolute constant $`c`$ such that, for infinitely many primes $`N`$, the clique number $`\omega (P_N)`$ is at least $`c\mathrm{log}N\mathrm{log}\mathrm{log}\mathrm{log}N`$. However, using the Borel-Cantelli lemma together with the bounds obtained in §7 one can show that almost surely any sequence $`(G_N)_N`$ of random Cayley sum graphs on $`_N`$, $`|G_N|=N`$, will have $`lim\; sup_N\mathrm{}\omega (G_N)/\mathrm{log}N160`$. Thus Paley graphs are (in a sense) not as good Ramsey graphs as random Cayley sum graphs.
Let us close by mentioning a conjecture from .

###### Conjecture 30 (Alon)

There exists an absolute constant $`b`$ such that for every group $`\mathrm{\Gamma }`$ on $`n`$ elements there is a Cayley graph on this group containing neither a complete subgraph nor an independent set on more than $`b\mathrm{log}n`$ vertices.

The results of this paper confirm this conjecture for cyclic groups but one should not expect the full conjecture, if it is true, to be easy to prove. Quite apart from the fact that our methods seem to break down hopelessly for all but a few very special groups, the result of Proposition 27 shows that random methods alone will not suffice to attack Alon’s conjecture.
10. Acknowledgements. I would like to thank Imre Ruzsa and Seva Lev for their generous help in improving the exposition in this paper.

Ben Green
Trinity College, Cambridge, England.
email: bjg23@hermes.cam.ac.uk


format: text

text:
# References

A Comment on the Invariance of the Speed of Light

Harihar Behera

Patapur, P.O.: Endal, Jajpur-755023, Orissa, India

E-mail : harihar@iopb.res.in

## Abstract

The invariance of the speed of light in all inertial frames is shown to be an inevitable consequence of the relativity principle of special relativity contrary to the view held by Hsu and Hsu in taiji relativity where the speed of light is no longer a universal constant.The present approach is not only new but also much simpler than the existing approaches.

The two postulates of special relativity, viz.,$`(i)`$ the relativity principle and $`(ii)`$ the postulate on the speed of light, are the basics of a theory that has been tremendously successful in describing a wide range of phenomena, although there exist derivations of Lorentz transformations (LT) without the postulate on the speed of light \[1-8\]. However, using the relativity principle only, Hsu and Hsu  have developed a general theory, named taiji relativity, which has four dimensional symmetry and is consistent with experiments although the speed of light is no longer a universal constant within its framework. In the development of taiji relativity the authors have considered the usual case of two inertial frames $`F`$ and $`F^{}`$ and to simplify the discussion defined the speed of light to be constant and isotropic in the frame $`F`$ by synchronizing the clocks in that frame according to the usual method of special relativity. The authors have made this definition in one frame only and could just as easily have used the $`F`$ frame, as all frames are equivalent, so this procedure does not select a preferred frame. As the principle of relativity itself does not specify how the $`F`$ and $`F^{}`$ clocks should be related, the theory does not tell us anything about the speed of light in any other frame, they say \[9-12\]. But here in this communication, the invariance of the speed of light in all inertial frames is shown to be a natural consequence of the relativity principle contrary to the view held by the authors \[9-12\].

Consider two inertial frames $`F`$ and $`F^{}`$ which are in uniform relative motion. An event may be characterized by specifying the co-ordinates $`(x,y,z,t)`$ of the event in $`F`$ and the event is characterized by the co-ordinates $`(x^{},y^{},z^{},t^{})`$ in $`F^{}`$. Let us proceed to find a transformation between $`(x,y,z,t)`$ and $`(x^{},y^{},z^{},t^{})`$ without the light-speed postulate of special relativity. To simplify the algebra let the relative velocity$`v`$ of $`F`$ and $`F^{}`$ be along a common $`x/x^{}`$ axis with corresponding planes parallel. Also at the instant the origins $`0`$ and $`0^{}`$ coincide, we let the clocks there to read $`t=0`$ and $`t^{}=0`$ respectively. The homogeneity of space and time in inertial frames requires that the transformations must be linear so that the simplest form they can take is

$$x^{}=k(xvt);y^{}=y;z^{}=z;t^{}=lx+mt$$
(1)
In order to determine the values of the three co-efficients $`k,l,`$ and $`m`$ we shall use the idea of the homogeneity and isotropy of space. Let us assume that at the time $`t=0`$ a spherical electromagnetic wave left the origin of $`F`$ which coincides with the origin of $`F^{}`$ at that moment. Let the speed of light be assumed as $`c`$ and $`c^{}`$ in $`F`$ and $`F^{}`$ respectively with $`cc^{}`$. We know that the two frames $`F`$ and $`F^{}`$ are equivalent. Therefore the electromagnetic wave propagates in all directions in each inertial frame as the space is homogeneous and isotropic. By the equivalence of inertial frames (i.e. relativity principle), the wave forms (fronts) of the electromagnetic wave in the two frames $`F`$ and $`F^{}`$ must be equivalent or similar, otherwise it would be possible to determine from the shape of the wave front which one i.e.$`F`$ or $`F^{}`$ is at rest or in uniform motion from which the absolute nature of motion or rest may be inferred contrary to the relativity principle. Again the wave front of a spherical electromagnetic wave in an isotropic and homogeneous medium describes a sphere whose radius expands with time at a rate equal to its speed in that medium. Thus the equation of the spherical wave fronts in the two inertial frames must take the forms:

$$x^2+y^2+z^2=c^2t^2$$
(2)
$$x_{}^{}{}_{}{}^{2}+y_{}^{}{}_{}{}^{2}+z_{}^{}{}_{}{}^{2}=c_{}^{}{}_{}{}^{2}t_{}^{}{}_{}{}^{2}$$
(3)
when the transformations (1) are substituted in (3), we get

$$(k^2l^2c^2)x^2+y^2+z^22(lmc^2k^2v)=(m^2c^2k^2v^2)t^2$$
(4)
In order for the expression (4) to agree with (2), which represents the same thing, we must have

$`(i)`$ $`k^2l^2c^2=1,`$
$`(ii)`$ $`m^2c^2k^2v^2=c^2,`$
$`(iii)`$ $`lmc^2k^2v=0`$ (5)
This set of three equations (5) when solved for $`k,l`$ and $`m`$ yield

$`(i)`$ $`k=(1v^2/c^2)^{1/2},`$
$`(ii)`$ $`l=(c/c^{})(v/c^2)(1v^2/c^2)^{1/2},`$
$`(iii)`$ $`m=(c/c^{})(1v^2/c^2)^{1/2}`$ (6)
Now in view of these values of $`k,l`$ and $`m`$, the transformations (1) can be represented in the following matrix form, viz.,

$$\left(\begin{array}{c}x^{}\\ y^{}\\ z^{}\\ t^{}\end{array}\right)=A\left(\begin{array}{c}x\\ y\\ z\\ t\end{array}\right),\mathrm{where}A=\left(\begin{array}{cccc}k& 0& 0& kv\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ kv/cc^{}& 0& 0& kc/c^{}\end{array}\right)$$
(7)
The inverse transformations for $`x,y,z,t`$, then given by

$$\left(\begin{array}{c}x\\ y\\ z\\ t\end{array}\right)=A^1\left(\begin{array}{c}x^{}\\ y^{}\\ z^{}\\ t^{}\end{array}\right),\mathrm{where}A^1=\left(\begin{array}{cccc}k& 0& 0& kvc^{}/c\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ kv/c^2& 0& 0& kc^{}/c\end{array}\right)$$
(8)
Hence the transformation for $`x`$ becomes

$$x=k(x^{}+vc^{}t^{}/c)$$
(9)
But relativity principle demands that the transformation for $`x`$ must be given by :

$$x=k(x^{}+vt^{})$$
(10)
Thus Eq. (9) contradicts Eq. (10). Such a contradiction arises because of our assumption that $`cc^{}`$. Hence in the order for Eq. (9) to be in accord with the relativity principle (so with Eq. (10)),we must have $`c=c^{}`$.

From the above discussion, we may conclude that the postulation on the speed of light in special relativity is an inevitable consequence of the relativity principle taken in conjunction with the idea of the homogeneity and isotropy of space and the homogeneity of time in all inertial frames. The present approach is physically distinct from and logically simpler than the standard special relativity, as we make use of only one postulate. The idea of constructing a relativity theory by using only the relativity principle has also been discussed by Ritz, Tolman and Pauli , but the present approach is not only new but also much simpler than the existing approaches and has been given as a preliminary report in .

The author thanks Prof. N.Barik, Dept. of Phys. Utkal University, Bhubaneswar, P.C.Naik, Dept. of Physics, D.D.College, Keonjhar and N.K. Behera, Dept. of Chem. U.N. College, Soro for fruitful discussions and suggestions.The author also acknoledges the help received from the Institute of Physics,Bhubaneswar for using its Library and Computer Centre for this work.


text:
# New Low-Mass Members of the Taurus Star-Forming Region Based on observations obtained at the Kitt Peak National Observatory, Keck Observatory, Fred Lawrence Whipple Observatory, and the MMT Observatory. This publication makes use of data products from the Two Micron All Sky Survey, which is a joint project of the University of Massachusetts and the Infrared Processing and Analysis Center/California Institute of Technology, funded by the National Aeronautics and Space Administration and the National Science Foundation.

## 1 Introduction

Magnitude-limited searches for members of nearby star-forming regions are an important basis for a variety of studies of young stars and brown dwarfs. For instance, such surveys provide well-defined membership samples from which unbiased initial mass functions (IMFs) can be derived. In addition, newly discovered young brown dwarfs are valuable targets for detailed studies of the formation of objects at the bottom of the mass function.

The Taurus dark cloud complex has proven to be amenable to a census of its low-mass stars and brown dwarfs. The members of this region are nearby (140 pc) and young (1 Myr), and thus can be detected down to very low masses. In addition, because a majority of the members of Taurus (excluding protostars) exhibit relatively low extinction ($`A_V5`$), they are accessible to measurements at both optical and infrared (IR) wavelengths. Over time, surveys for new members in this low-density, dispersed population ($`n1`$-10 pc-3) have steadily expanded in areal coverage (Strom & Strom, 1994; Briceño et al., 1998; Luhman & Rieke, 1998; Luhman, 2000; Martín et al., 2001). Most recently, Briceño et al. (2002) used wide-field optical imaging, 2MASS data, and followup spectroscopy to search for low-mass stars and brown dwarfs in 8 deg2 that encompassed half of the known pre-main sequence population in Taurus. They discovered nine new members with spectral types of M5.75-M9.5, corresponding to masses of 0.1-0.015 $`M_{}`$ by the theoretical evolutionary models of Baraffe et al. (1998).

At the conclusion of the study by Briceño et al. (2002), there remained candidate members of Taurus that had not been observed spectroscopically. In this paper, we identify the most promising of those candidates (§ 2), describe spectroscopic observations of them (§ 3), measure spectral types and determine whether they are Taurus members (§ 4), and discuss the physical properties of the six new members and update the IMF from Briceño et al. (2002) (§ 5).

## 2 Selection of Candidate Members of Taurus

Briceño et al. (2002) used optical and near-IR photometry to select potential young stars and brown dwarfs in 8 deg2 of Taurus. In this section, we examine the photometry from that survey to identify the remaining candidates that lack the spectroscopy needed to confirm membership in Taurus and to measure spectral types. To do this, we could simply use the observed color-magnitude and color-color diagrams (e.g., $`I`$ vs. $`IZ`$, $`JH`$ vs. $`IK_s`$) in the manner described by Briceño et al. (2002). Instead, we revise those methods in a way that more clearly separates Taurus members from field stars.

We wish to identify the stars in the fields surveyed by Briceño et al. (2002) that have both the colors and the absolute photometry expected of members of the Taurus population. Optical color-magnitude diagrams (CMDs) are widely used for selecting candidate members of clusters on this basis. However, in star-forming clouds, the presence of highly variable extinction ($`A_V=0`$-20 in Taurus) increases the contamination of background stars in the region of the CMD inhabited by members and prevents reliable mass estimates for candidate members (i.e., reddened high-mass members and unreddened low-mass members can have the same optical color and magnitude). The photometry in such diagrams cannot be corrected for extinction when only two bands are available. In the case of the Taurus fields, in addition to $`I`$ and $`Z`$ photometry, we have near-IR data from 2MASS. As a result, we have been able to estimate the extinction toward each star by dereddening its position in $`JH`$ versus $`IK_s`$ until it intersects the sequence of colors for dwarfs later than K6 (Leggett, 1992), which is the range of spectral types occupied by most known members of Taurus. If a star has a spectral type earlier than K6, the extinction will be underestimated in this method, but that is acceptable. The dereddening process tends to remove background stars from the area of the CMD where members reside, and if a star’s extinction is underestimated, then at worst it remains in that area and is selected as a candidate. In other words, an underestimate of extinction will not result in the rejection of a bonafide member. After correcting the photometry for extinction in this way, we plot the results on CMDs of $`IK_s`$ versus $`H`$ and $`IZ`$ versus $`H`$ in Figure 1. We choose $`H`$ as the magnitude because it correlates closely with bolometric luminosity, requires only a small correction for extinction, and is not susceptible to significant contamination from excess emission from circumstellar material. Meanwhile, the $`IK_s`$ and $`IZ`$ colors are used because they increase rapidly with decreasing mass, producing a member sequence that is distinct from the location of most field stars in the CMDs. In Figure 1, we omit the stars appearing below the reddening vector in the diagram of $`I`$ versus $`IZ`$ in Briceño et al. (2002) because they are well below the member sequence and thus are likely to be field stars. From the $`250`$ stars that remain, we plot only those that exhibit extinctions of $`A_V8`$. We are primarily interested in identifying candidate members at lower extinctions that might fall within the limit of $`A_V4`$ that defined the IMF from Briceño et al. (2002) so that we can approach 100% completeness for that sample. The extinctions derived for the construction of Figure 1 are only rough estimates since they are based on photometry alone without any information on the spectral types. Therefore, to be certain that members at $`A_V4`$ were not missed, we considered a threshold of $`A_V8`$ in selecting candidates. In Figure 1, we include all objects that have been spectroscopically confirmed as members in this work and in previous studies for the Taurus fields in question. We also indicate the field stars identified through our new spectroscopy, while omitting the field stars found in previous work.

We now describe the regions in Figure 1 that are inhabited by Taurus members and examine the photometry to identify any potential members that lack previous spectra. When the known members of Taurus are placed on a Hertzsprung-Russell (H-R) diagram, they exhibit median and maximum ages of $`1`$ and 10 Myr, respectively, on the model isochrones of Baraffe et al. (1998), except at the latest spectral types, where some of the members appear between the isochrones for 10 and 30 Myr (Briceño et al. (2002), § 5.2). We plot the 10 Myr isochrone from 0.015 to 1 $`M_{}`$ in the diagram of $`IK_s`$ versus $`H`$ in Figure 1 by combining the predicted effective temperatures and bolometric luminosities (Baraffe et al., 1998), a temperature scale this is compatible with the adopted models (Luhman, 1999; Luhman et al., 2003), dwarf colors and bolometric corrections (Leggett, 1992; Luhman, 1999), and a distance modulus of 5.76 (Wichmann et al., 1998). The plateau near $`H=13.5`$ in the resulting isochrone in Figure 1, which does not appear in a plot of the isochrone in $`T_{\mathrm{eff}}`$ versus $`L_{\mathrm{bol}}`$, reflects the rapid increase in $`IK_s`$ between M5 and M9. Because standard values of intrinsic $`IZ`$ as a function of spectral type are not available, we cannot plot the isochrone in $`IZ`$ versus $`H`$. However, the lower envelope of the sequence of known members in $`IZ`$ versus $`H`$ effectively delineates the location of the 10 Myr isochrone (except at late types, or $`IZ>1.7`$) and the line above which we should search for new members. Approximately 23 stars lack spectra and fall near the member sequences in both of the CMDs in Figure 1. In the next section, we describe spectroscopy of 22 of these stars, which are listed in Tables 1 and 2. The remaining source is 2MASSs 0435283+241000, which has dereddened photometry of $`H=15.75`$, $`IZ=2.33`$, and $`IK_s=4.89`$. We did not observe this star because it is at the detection limits of both the optical and 2MASSs data and therefore its positions in the CMDs are highly uncertain.

## 3 Spectroscopic Observations of Candidates

Table 3 summarizes our observations of the 22 candidate members of Taurus identified in the previous section. One of these objects, 2MASSs J0419012+280248, was observed on two occasions. The FAST spectrometer (Fabricant et al., 1998) on the 1.5 m Tillinghast reflector at the Fred Lawrence Whipple Observatory was operated with the 300 l mm-1 grating ($`\lambda _{\mathrm{blaze}}=4800`$ Å) and $`2\stackrel{}{\mathrm{.}}0`$ slit, providing a resolution of FWHM$`=5`$ Å. The Keck I low-resolution imaging spectrometer (LRIS; Oke et al. 1995) was configured with the 400 l mm-1 grating ($`\lambda _{\mathrm{blaze}}=8500`$ Å), GG495 blocking filter, and $`1\stackrel{}{\mathrm{.}}0`$ slit (FWHM$`=6`$ Å). With the Blue Channel spectrometer at the MMT Observatory, we used the 600 l mm-1 grating ($`\lambda _{\mathrm{blaze}}=9630`$ Å), LP495 blocking filter, and $`1\stackrel{}{\mathrm{.}}0`$ slit (FWHM$`=2.7`$ Å). Each spectrum was collected with the slit rotated to the parallactic angle. The exposure times ranged from 300 to 2700 s. After bias subtraction and flat-fielding, the spectra were extracted and calibrated in wavelength with arc lamp data. The spectra were then corrected for the sensitivity functions of the detectors, which were measured from observations of spectrophotometric standard stars.

## 4 Spectral Classification of Candidates

We measure spectral types and assess membership for the 22 candidate Taurus members that were observed spectroscopically by applying the methods of classification described in our previous studies of Taurus and other young populations (Luhman, 1999; Briceño et al., 2002).

We classify 13 candidates as background giants and one candidate as a background early-type star. Strong absorption in the Ca II triplet is the most distinguishing feature of the giants, as illustrated for two of these stars in Figure 2. The data for the other eight candidates are displayed in Figure 2. Two of these stars, 2MASSs J0418021+281748 and J0436008+225517, are below the main sequence when placed on the H-R diagram with the distance of Taurus, which indicates that they are probably field dwarfs behind the star-forming region. Although young stars that are observed in scattered light can appear at comparable positions on the H-R diagram (Briceño et al. (2002), § 5.2), such stars usually exhibit emission in H$`\alpha `$ or some other evidence of youth. However, no such signatures are found in the data for these two stars. In addition, the strength of the K I and Na I absorption in the spectrum of 2MASSs J0436008+225517 provides conclusive evidence that it is a field dwarf.

The spectra for the six remaining sources in Figure 2 exhibit evidence of youth, and thus membership in Taurus, in the form of the weak K I and Na I absorption features that are characteristic of pre-main-sequence objects (Martín et al., 1996; Luhman et al., 1998a, b; Luhman, 1999). The membership of five of these sources is independently established by the presence of reddening in their spectra and their positions above the main sequence for the distance of Taurus, which indicate that they cannot be field dwarfs in the foreground or the background of the cloud, respectively. The equivalent widths of H$`\alpha `$ emission in KPNO-Tau 11, 13, and 15 are consistent with those of both active field dwarfs and young objects. Meanwhile, the much stronger emission in KPNO-Tau 10, 12, and 14 is common among the latter but rare in the former (Gizis et al., 2000). For the coolest new member, KPNO-Tau 12, we find that the best match to the optical spectrum is provided with an average of dwarf and giant spectra (normalized at 7500 Å), as shown in Figure 3, which is consistent with the results of our previous classifications of young objects later than M6 (Luhman, 1999; Briceño et al., 2002). The spectrum for KPNO-Tau 12 in Figure 3 is from the November observations with Keck. We did not use the January data from the MMT in measuring the spectral type of this object because the signal-to-noise was too low.

The classifications and other measurements for the 16 background field stars and the six new Taurus members are listed in Tables 1 and 2, respectively. The photometric errors are $`0.1`$ mag for KPNO-Tau 12 and $`0.03`$ mag for the remaining sources.

## 5 Properties of New Members

In this section, we use the photometry, spectroscopy, and theoretical evolutionary models to examine the physical properties of the six new Taurus members.

### 5.1 Disk and Accretion Signatures

Excess continuum emission and optical emission lines are signatures of circumstellar disks and accretion that could appear in the available data for the new Taurus members. The near-IR colors of the six new members match those of reddened dwarfs and have no significant excess emission in the $`K`$-band. This is consistent with the observation that only half of the known members of Taurus exhibit $`K`$-band excess emission, while a much larger fraction show evidence for disks in photometry at longer bandpasses such as $`L`$ (Kenyon & Hartmann, 1995; Haisch et al., 2000). Five of the new members show moderate to strong emission in H$`\alpha `$ ($`W_\lambda =6`$-36 Å) that is typical of young stars in Taurus, while the M9 object KPNO-Tau 12 exhibits a far larger equivalent width. A given value of $`L_{H\alpha }/L_{\mathrm{bol}}`$ corresponds to larger equivalent widths at later spectral types as the stellar continuum surrounding H$`\alpha `$ becomes weaker. In addition, when this faint continuum is detected at low signal-to-noise, it is possible to erroneously measure arbitrarily large values of the equivalent width. However, in the case of KPNO-Tau 12, the continuum near H$`\alpha `$ is well-detected, as demonstrated in Figure 4. In measuring the equivalent width of H$`\alpha `$, the continuum level across the line was taken to be the level from the best fit M9 standard (§ 4) after normalizing the two spectra at the surrounding continuum (6400-6500 and 6600-6700 Å). In this way, the equivalent width of H$`\alpha `$ is confidently measured to be between 850 and 1050 Å in the November spectrum. Because of insufficient signal-to-noise in the continuum surrounding H$`\alpha `$, an equivalent width was not measured from the January spectrum.

To compare the H$`\alpha `$ emission in KPNO-Tau 12 to that in other M-type sources, we consider the ratio $`L_{H\alpha }/L_{\mathrm{bol}}`$. We arrived at two separate flux calibrations for the November spectrum of KPNO-Tau 12 by using the $`I`$-band photometry of this source from Briceño et al. (2002) and the data for the spectrophotometric standard. We adopted the average of these calibrations, which differed by 20%. From the resulting spectrum, we measured an H$`\alpha `$ flux of $`2.45\pm 0.25\times 10^{15}`$ erg s-1 cm-2 in the November data. Meanwhile, the flux of H$`\alpha `$ in the January spectrum was 30% higher. After correcting the November measurement for an extinction of $`A_V=0.5`$ and combining the result with the bolometric luminosity derived in the next section, we find log $`(L_{H\alpha }/L_{\mathrm{bol}})=2.6\pm 0.12`$, which is slightly higher than the strongest emission observed in late-M dwarfs (Schneider et al., 1991; Martín et al., 1999; Liebert et al., 1999) and two orders of magnitude greater than the typical values for these objects (Gizis et al., 2000). The only known young late-M sources with comparable H$`\alpha `$ emission are LS-RCrA 1 in R Coronae Australis (Fernández & Comerón, 2001) and S Ori 71 in $`\sigma `$ Orionis (Barrado y Navascués et al., 2002). Several other young low-mass objects have been found with H$`\alpha `$ intensities that are only a few times lower than those in KPNO-Tau 12, LS-RCrA 1, and S Ori 71 (Zapatero Osorio et al., 2002; Briceño et al., 2002; Luhman et al., 2003).

There are additional indications that active accretion is probably occurring in KPNO-Tau 12. The TiO bands at 6600-7300 Å are weaker than those of the best fit standard spectrum in Figure 3, which is suggestive of veiling from blue excess continuum emission. On the other hand, this behavior could imply a spectral type later than our classification of M9 since the TiO bands become weaker and eventually disappear from M to L types. But given the good quality of the fit of M9 to the data beyond 7300 Å and the presence of intense H$`\alpha `$ emission, the weak appearance of the TiO bands is probably a result of continuum veiling. We also detect emission in He I at 6678 Å and in the Ca II IR triplet, as shown in Figure 4. We measure equivalent widths of $`8\pm 2`$ Å for He I and $`4\pm 1`$, $`2.5\pm 1`$, and $`1.5\pm 0.5`$ Å for Ca II at 8498, 8542, and 8662 Å. KPNO-Tau 12 is the coolest young object known to exhibit these emission lines, which are usually indicators of intense accretion when observed in young stars (Muzerolle et al., 1998; Beristain et al., 2001). Alternatively, emission in He I and Ca II, as well as strong H$`\alpha `$ and continuum veiling, can be attributed to a magnetic flare event, as in the case of the field M9.5 dwarf 2MASSW J0149090+295613 (Liebert et al., 1999). However, since the duty cycle of such flares is low in field objects (Gizis et al., 2000; Liebert et al., 2003) and the emission in KPNO-Tau 12 was strong at both epochs of our observations, the emission in KPNO-Tau 12 is probably not from a flare event. Given that KPNO-Tau 12 is member of a star-forming region, it is much more likely that the emission in H$`\alpha `$, He I, Ca II, and the blue continuum are the result of active accretion.

### 5.2 Extinctions, Temperatures, and Luminosities

Following the procedures described by Briceño et al. (2002), we estimate extinctions, effective temperatures, and bolometric luminosities from the spectral types and photometry for the six new Taurus members. The values for these parameters are listed in Table 2. The combined uncertainties in $`A_J`$, $`J`$, and BCJ ($`\sigma 0.14`$, 0.03, 0.1) correspond to errors of $`\pm 0.07`$ in the relative values of log $`L_{\mathrm{bol}}`$. When an uncertainty in the distance modulus is included ($`\sigma 0.2`$), the total uncertainties are $`\pm 0.11`$. We use the temperatures and luminosities in Table 2 to place the six sources on the H-R diagram in Figure 5. For reference, we also show the previously known Taurus members that have $`A_V4`$ and are within the 8.4 deg2 surveyed by Briceño et al. (1998), Luhman (2000), and Briceño et al. (2002), which comprise the IMF sample from Briceño et al. (2002). The five new members at M3-M6 fall within this sequence of members, which is spread between $`<1`$ and 10 Myr for most masses. Meanwhile, the new M9 source KPNO-Tau 12 appears near the 30 Myr model isochrone of Baraffe et al. (1998), as does one of the previously known M8.5 members. An age of 30 Myr is much larger than expected given the median age of 1 Myr for the Taurus population and the apparent presence of active accretion in KPNO-Tau 12. Interestingly, the one other young late-M source known to exhibit accretion signatures in the form of He I and Ca II emission, LS-RCrA 1, also falls much lower on the H-R diagram than expected (Fernández & Comerón, 2001).

We consider three possible explanations for the anomalously old ages implied by the H-R diagrams of some late-M sources, particularly KPNO-Tau 12 and LS-RCrA 1. First, there could be deficiencies in either the models or the conversion of spectral types to temperatures. In this work, we use a temperature scale that has been adjusted at late spectral types so that the low-mass members of Taurus and IC 348 have median ages comparable to the ones of the higher mass sources (Luhman et al., 2003). As a result, the adopted combination of models and temperature scale should produce the most reliable age and mass estimates that are currently possible. However, as suggested by Fernández & Comerón (2001) in the case of LS-RCrA 1, intense accretion could produce an evolutionary path on the H-R diagram that differs from that predicted by models of non-accreting objects. Indeed, both of the known late-M objects with evidence for accretion in the form of He I and Ca II emission are subluminous on the H-R diagram. Fernández & Comerón (2001) proposed a second explanation for the low luminosity of LS-RCrA 1 in which this object is seen in scattered light. For a young star that is occulted by an optically thick structure such as an edge-on disk, the observed photometry measures only the scattered light. As a result, the luminosity implied by the photometry is an underestimate, and the star appears subluminous for its temperature on the H-R diagram. For a low-mass source undergoing intense accretion, it is possible that a significant fraction of the object is blocked by accreting circumstellar material, which could account for the correlation between accretion activity and low luminosity for KPNO-Tau 12 and LS-RCrA 1. However, this occulting mechanism would need to be more efficient for brown dwarfs than for stars since young stars in Taurus with He I emission do not have systematically lower luminosities than other stellar members. As a third possibility, the old ages inferred from the model isochrones could result from errors in the luminosity estimates of young sources. The finite width of the Taurus sequence on the H-R diagram could arise not from a spread in ages but from various sources such as extinction uncertainties, unresolved binaries, variability from accretion and from rotation of spotted surfaces, and differences in distances to individual members (Kenyon & Hartmann, 1990; Hartmann, 2001). If so, then the width of the sequence in log L should remain roughly constant at all masses, and thus correspond to an increasing apparent spread of ages as the separation between model isochrones in log L decreases from stellar to substellar masses. This phenomenon probably produces erroneously old ages on the model isochrones for at least some low-mass members of young clusters, but would not explain the fact that both late-type objects showing He I emission are subluminous.

### 5.3 Masses

We now consider the masses of the new Taurus members. By combining the positions on the H-R diagram with the evolutionary models of Baraffe et al. (1998), we infer masses of 0.10, 0.13, 0.15, 0.16, and 0.4 $`M_{}`$ for KPNO-Tau 14, 11, 13, 10, and 15. These mass estimates are not sensitive to uncertainties in the luminosities since the predicted evolution of a star is mostly vertical on the H-R diagram for ages of $`<10`$ Myr. However, this is not true at substellar masses, where the mass tracks have significant components in both temperature and luminosity. The models imply a mass of 0.03 $`M_{}`$ for the M9 object KPNO-Tau 12 based on its position on the H-R diagram. Under two of the three explanations for the low luminosity of this source (§ 5.2), the luminosity estimate is uncertain. In these cases, a more reliable mass is derived by placing the object on the 1 Myr isochrone for the adopted temperature, which would imply a mass of 0.015 $`M_{}`$ from the models of Baraffe et al. (1998). For the third explanation in which the temperature and luminosity are significantly affected by accretion, KPNO-Tau 12 could have an even lower mass (Fernández & Comerón, 2001). If this object does have a mass below 0.015 $`M_{}`$, one might be tempted to refer to it as an accreting free-floating planetary mass object. However, the various properties of low-mass brown dwarfs – such as the evidence of intense accretion in objects like KPNO-Tau 12 – indicate that they probably form in a star-like fashion rather than in circumstellar disks (Briceño et al., 2002). Therefore, the term “planetary” has little or no applicability. For the purposes of this work, we adopt a mass of 0.02 $`M_{}`$ for this object.

As mentioned previously, the IMF presented by Briceño et al. (2002) included the 86 known Taurus members that fell within the 8.4 deg2 surveyed by Briceño et al. (1998), Luhman (2000), and Briceño et al. (2002) and that had extinctions of $`A_V4`$. There remained a few potential members that lacked spectroscopy within these defining parameters, so the IMF sample was not 100% complete. However, because the candidates were not concentrated at a particular magnitude range, Briceño et al. (2002) concluded that the sample of confirmed members was unbiased in mass down to the completeness limit of the photometry, which corresponded to 0.02 $`M_{}`$ for $`A_V=4`$. Through spectroscopy of those candidates, we have found six new members, all of which have $`A4`$. After adding these sources to the extinction-limited sample from Briceño et al. (2002), we arrive at the IMF in Figure 6, which should be virtually 100% complete for $`A_V4`$ and masses above 0.02 $`M_{}`$ in the 8.4 deg2 survey fields. Because of the small number of new members that are added to the IMF from Briceño et al. (2002) and the wide range of masses of these new sources, the shapes of the IMFs here and in Briceño et al. (2002) do not differ significantly. Thus, the conclusions from Briceño et al. (2002) regarding the observed variations in the IMFs of Taurus and the Trapezium remain unchanged.

## 6 Conclusions

We have obtained spectroscopy for candidate young stars and brown dwarfs that appeared in an optical and IR photometric survey of 8 deg2 of the Taurus star-forming region by Briceño et al. (2002). We have estimated individual extinctions for the stars detected in the survey and have plotted the dereddened photometry on color-magnitude diagrams. Within an extinction limit of $`A_V8`$, we identified 22 sources that were potential members of Taurus and that lacked previous spectroscopy. Through optical spectroscopy of these candidates, we have discovered six new members with spectral types ranging from M2.75 to M9. From the spectral types and photometry of these objects, we have estimated extinctions, effective temperatures, and bolometric luminosities, and have combined these results with the evolutionary models of Baraffe et al. (1998) to infer individual masses that range from 0.4 to 0.02 $`M_{}`$. These new members fall within the extinction limit of $`A_V4`$ that defined the sample from which Briceño et al. (2002) derived an IMF. Therefore, we have added them to that extinction-limited sample and have presented the updated IMF, which applies to the 8.4 deg2 in Taurus surveyed by Briceño et al. (1998), Luhman (2000), and Briceño et al. (2002). The new M9 source is a particularly interesting discovery from this work. It has the second latest spectral type of the known members of Taurus. In addition, it exhibits the strongest H$`\alpha `$ emission observed to date for a late-M source ($`W_\lambda 950`$ Å, log $`(L_{H\alpha }/L_{\mathrm{bol}})=2.6`$) and is the least massive object found with emission in He I 6678 Å and the Ca II IR triplet, which are suggestive of active accretion. High-resolution spectroscopy of the emission lines in this object would provide valuable insight into the formation of low-mass brown dwarfs.

We thank Perry Berlind and Mike Calkins for performing the FAST observations. K. L. was supported by grant NAG5-11627 from the NASA Longterm Space Astrophysics program. C. B. received partial support from grant S1-2001001144 of the Fondo Nacional de Ciencia y Tecnología (FONACYT) of Venezuela. We are grateful to France Allard and Isabelle Baraffe for access to their most recent calculations. This research has made use of the NASA/IPAC Infrared Science Archive, which is operated by the Jet Propulsion Laboratory, California Institute of Technology, under contract with the National Aeronautics and Space Administration. Some of the data presented herein were obtained at the W. M. Keck Observatory, which is operated as a scientific partnership among the California Institute of Technology, the University of California, and the National Aeronautics and Space Administration. The Observatory was made possible by the generous financial support of the W. M. Keck Foundation. We wish to extend special thanks to those of Hawaiian ancestry on whose sacred mountain we are privileged to be guests. Without their generous hospitality, some of the observations presented herein would not have been possible. Some of the data in this work were obtained at the MMT Observatory, a joint facility of the Smithsonian Institution and the University of Arizona.