Monthly Archive

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

Maximal dimension of a subspace included in a dense set of a large vector space

08/02/2019 in Uncategorized | Laisser un commentaire

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.