Hostname: page-component-6898cfcb55-cbk24 Total loading time: 0 Render date: 2026-11-11T10:00:18.620Z Has data issue: false hasContentIssue false
  • English
  • Français

Freiman's Theorem in Finite Fields via Extremal Set Theory

Published online by Cambridge University Press:  01 May 2009

BEN GREEN and
TERENCE TAO
BEN GREEN
Affiliation:
Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WA, UK (e-mail: b.j.green@dpmms.cam.ac.uk)
TERENCE TAO
Affiliation:
Department of Mathematics, UCLA, Los Angeles, CA 90095-1555, USA (e-mail: tao@math.ucla.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Using various results from extremal set theory (interpreted in the language of additive combinatorics), we prove an asymptotically sharp version of Freiman's theorem in $\F_2^n$: if $A \subseteq \F_2^n$ is a set for which |A + A| ≤ K|A| then A is contained in a subspace of size $2^{2K + O(\sqrt{K}\log K)}|A|$; except for the $O(\sqrt{K} \log K)$ error, this is best possible. If in addition we assume that A is a downset, then we can also cover A by O(K46) translates of a coordinate subspace of size at most |A|, thereby verifying the so-called polynomial Freiman–Ruzsa conjecture in this case. A common theme in the arguments is the use of compression techniques. These have long been familiar in extremal set theory, but have been used only rarely in the additive combinatorics literature.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 3 , May 2009, pp. 335 - 355
Copyright
Copyright © Cambridge University Press 2009

References

[1]Bogolyubov, N. N. (1939) Sur quelques propriétés arithmétiques des presque-périodes. Ann. Chaire Math. Phys. Kiev 4 185–194.Google Scholar
[2]Bollobás, B. and Leader, I. (1996) Sums in the grid. Discrete Math. 162 31–48.CrossRefGoogle Scholar
[3]Deshouillers, J. M., Hennecart, F. and Plagne, A. (2004) On small sumsets in $(\Z/2\Z)^n$. Combinatorica 24 53–68.CrossRefGoogle Scholar
[4]Frankl, P. (1987) The shifting technique in extremal set theory. In Surveys in Combinatorics 1987 (New Cross, 1987), Vol. 123 of London Mathematical Society Lecture Notes, Cambridge University Press, pp. 81–110.Google Scholar
[5]Freiman, G. (1973) Foundations of a Structural Theory of Set Addition, Translated from the Russian. Vol. 37 of Translations of Mathematical Monographs, AMS, Providence, RI.Google Scholar
[6]Freiman, G. (1999) Structure theory of set addition. Astérisque 258 1–33.Google Scholar
[7]Green, B. J. (2005) Finite field models in additive combinatorics. In Surveys in Combinatorics, Vol. 327 of London Mathematical Society Lecture Notes, Cambridge University Press, pp. 1–27.Google Scholar
[8]Green, B. J. and Ruzsa, I. Z. (2006) Sets with small sumset and rectification. Bull. London Math. Soc. 38 43–52.CrossRefGoogle Scholar
[9]Green, B. J. and Ruzsa, I. Z. (2007) Freiman's theorem in an arbitrary abelian group. J. London Math. Soc. 75 (1) 163–175.Google Scholar
[10]Green, B. J. and Tao, T. C. A note on the Freiman and Balog–Szemerédi–Gowers theorems in finite fields. Submitted; available at: http://www.arxiv.org/abs/math.CO/0701585. To appear in J. Austral. Math. Soc.Google Scholar
[11]Plagne, A. (2003) Additive number theory sheds extra light on the Hopf–Stiefel ^ function (English summary). Enseign. Math. (2) 49 109–116.Google Scholar
[12]Ruzsa, I. (1994) Generalized arithmetical progressions and sumsets. Acta Math. Hungar. 65 379–388.Google Scholar
[13]Ruzsa, I. Z. (1999) An analog of Freiman's theorem in groups. In Structure Theory of Set Addition, Astérisque 258 323–326.Google Scholar
[14]Sanders, T. (2008) A note on Freiman's theorem in vector spaces. Combin. Probab. Comput. 17 (2)297–305.CrossRefGoogle Scholar
[15]Tao, T. C. and Vu, V. H. (2006) Additive Combinatorics, Cambridge University Press.Google Scholar
[16]Yuzvinsky, S. (1981) Orthogonal pairings of Euclidean spaces. Michigan Math. J. 28 131–145.Google Scholar