You are currently browsing the monthly archive for février 2019.

Let $A\subset\mathbb{F}_3^n$ have at least $\alpha 3^n$ elements, for some $\alpha >0$ (we say that $A$ has density at least $\alpha$), and very large $n$.
We know, by Meshulam’s theorem (Roth’s theorem in vector spaces), and even more strongly by Ellenberg-Gijswijt, who used the Croot-Lev-Pach method, that $A$ must contain a 3-term arithmetic progression, in other words an affine line.

But does it have to contain planes or even affine subspaces of larger dimensions?

First we examine the case of a random set $A$, thus each $x\in\mathbb{F}_3^n$ is taken in $A$ with probability $\alpha$ independently of each other.
This implies that any given subspace has probability
$\alpha^{3^k}$ to be included in $A$.
Now how many affine subspaces of dimension $k$ are there in a space of dimension $n$? This is $3^{n-k}\binom{n}{k}_3$ where $\binom{n}{k}_3$ is the number of linear subspaces of dimension $k$, and is easily seen to equal

$\displaystyle{ \binom{n}{k}_3=\frac{(3^n-1)\times\cdots \times(3^{n-k+1}-1)}{(3^k-1)\times\cdots\times (3-1)}.}$

One gets the obvious bound

$\displaystyle{ \binom{n}{k}_3\leq 3^{kn}.}$

Thus the expected number of subspaces of dimension $k$ in $A$ is at most $\alpha^{3^k}3^{kn}$.
This is of the order of magnitude of a constant
when $k$ is of the order of $\log (n/\alpha^{-1})$.
So when $k\asymp\log (n/\alpha^{-1})$, there may be no single subspace of dimension $k$.
However, using
the lower bound

$\displaystyle{ \binom{n}{k}_3\geq \frac{(3^{n-k+1}-1)^k}{3^{k^2}}}$

may be used to show similarly that when

$\displaystyle{ k\ll \log (n/\alpha^{-1}),}$

the set $A$ is likely (in fact, almost sure) to contain subspaces of dimension $k$.

Now we prove that if a set has positive density and $n$ is large enough, then $A$ must contain a subspace of dimension $\Omega(\log n/\log\log n)$.

The key is basically to use Varnavides averaging argument along with the Ellenberg-Gijswijt bound.
Let $n(\alpha, k)$ be the minimum $n$ (if it exists) such that any set $A\in\mathbb{F}_p^n$ of density $\alpha$ must contain a subspace of dimension $k$. The Ellenberg-Gijswijt bound amounts to $n(\alpha,1)\leq c\log \alpha^{-1}$; indeed, $\alpha$ just has to be at least $C(2.756/3)^n$ to ensure a line. Then Varnavides argument is an averaging trick that says that a dense set must contain many lines. So many that it must contain many parallel lines. So many that the set of starting points of these lines must in turn contain a line. In which case we obtain a plane. And so on. This was used by Brown and Buhler to derive the recursive relationship

$\displaystyle{ n(\frac{1}{r},k+1)\leq n_0+n(\frac{1}{er^2},1),}$

where $n_0=n(\frac{1}{r+1},k)$ and $e$ is the number of linear spaces of dimension $k$ in a space of dimension $n_0$. We can bound $e$ by $3^{n_0k}$, which yields $n(\frac{1}{er^2},1)\ll n_0 k+\log r$.
And so

$\displaystyle{ n(\frac{1}{r},k+1)\ll kn(\frac{1}{r+1},k)+\log r.}$

Inducting, one obtains

$\displaystyle{ n=n(\frac{1}{r},k)\leq (c')^k k k!\log (r+k).}$

Thus $\log n\ll k\log k$. In other words $k\gg \frac{\log n}{\log\log n}$, which is exactly the claimed result.