15
$\begingroup$

Green and Tao's version of Freiman's theorem over finite fields (doi:10.1017/S0963548309009821) is as follows:

If $A$ is a set in $\mathbb{F}_2^n$ for which $|A+A| \leqslant K|A|$, then $A$ is contained in a subspace of size $2^{2K+O(\sqrt{K}\log(K))}|A|$.

Does anybody know of a version of this bound with an explicit constant for the error term, or just an explicit exponent with more or less the same order of magnitude? For example, replacing the $O(\cdot)$ term by another multiple of $K$ might be sufficient for my purposes. (I would like to apply the bound to some specific sets $A$ and values of $n$. Roughly speaking, my $n$ range from about $50$ to $100$, and my $K$ range from about $50$ to $1000$, in case that helps.)

There is an earlier result of Ruzsa and Green, in which the upper bound is given explicitly as $K^22^{2K^2-2}$, but this is far too large for what I need it for.

I suppose one might be able to infer an explicit bound by reading Green and Tao's proof with enough care, but of course it would be easier not to have to do this.

$\endgroup$
16
$\begingroup$

Even-Zohar (On sums of generating sets in $\mathbb{Z}_2^n$, Combin. Probab. Comput. 21 (2012), no. 6, 916–941, available at https://arxiv.org/abs/1108.4902) has proved a completely explicit and sharp version of Frieman's theorem in $\mathbb{F}_2^n$ - see Theorem 2 of that paper.

As a corollary, one gets that if $\lvert A+A\rvert\leq K\lvert A\rvert$ then $A$ is contained a subspace of size at most

$$ (1+o(1))\frac{4^K}{2K}\lvert A\rvert.$$

(Precise bounds with no hidden constants are in the Theorem 2, but are quite cumbersome to write out here - but they are trivial to calculate for any specific values of $K$.)

$\endgroup$
1
  • $\begingroup$ Excellent. Many thanks! $\endgroup$ Jul 31 at 4:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.