Freiman's theorem explained

In additive combinatorics, a discipline within mathematics, Freiman's theorem is a central result which indicates the approximate structure of sets whose sumset is small. It roughly states that if

|A + A|/|A| is small, then A can be contained in a small generalized arithmetic progression.

Statement

If

A is a finite subset of Z with |A + A|\le K|A| , then A is contained in a generalized arithmetic progression of dimension at most d(K) and size at most f(K)|A| , where d(K) and f(K) are constants depending only on K .

Examples

For a finite set

A of integers, it is always true that|A + A| \ge 2 |A| -1 ,

with equality precisely when

A is an arithmetic progression.

More generally, suppose

A is a subset of a finite proper generalized arithmetic progression P of dimension d such that |P| \le C|A| for some real C \ge 1 . Then |P + P| \le 2 ^{d} |P| , so that|A + A| \le |P + P| \le 2 ^{d} |P| \le C 2 ^{d|A|.}

History of Freiman's theorem

This result is due to Gregory Freiman (1964, 1966).^{[1] [2] [3]} Much interest in it, and applications, stemmed from a new proof by Imre Z. Ruzsa (1992,1994).^{[4] [5]} Mei-Chu Chang proved new polynomial estimates for the size of arithmetic progressions arising in the theorem in 2002.^[6] The current best bounds were provided by Tom Sanders.^[7]

Tools used in the proof

The proof presented here follows the proof in Yufei Zhao's lecture notes.^[8]

Plünnecke–Ruzsa inequality

See main article: Plünnecke–Ruzsa inequality.

Ruzsa covering lemma

The Ruzsa covering lemma states the following:

Let

A and S be finite subsets of an abelian group with S nonempty, and let K be a positive real number. Then if |A + S| \le K|S| , there is a subset T of A with at most K elements such that A \subseteq T + S - S .

This lemma provides a bound on how many copies of

S - S one needs to cover A , hence the name. The proof is essentially a greedy algorithm:

Proof: Let

T be a maximal subset of A such that the sets t + S for A are all disjoint. Then |T + S| = |T| ⋅ |S| , and also |T + S| \le |A + S| \le K|S| , so |T| \le K . Furthermore, for any a \in A , there is some t \in T such that t + S intersects a + S , as otherwise adding a to T contradicts the maximality of T . Thus a \in T + S - S , so A \subseteq T + S - S .

Freiman homomorphisms and the Ruzsa modeling lemma

Let

s \ge 2 be a positive integer, and \Gamma and \Gamma' be abelian groups. Let A \subseteq \Gamma and B \subseteq \Gamma' . A map \varphi \colon A \to B is a Freiman s -homomorphism if\varphi(a _{1)} + … + \varphi(a _{s)} = \varphi(a _{1')} + … + \varphi(a _{s')} whenever a _{1} + … + a _{s} = a _{1'} + … + a _{s'} for any a _{1,} \ldots, a _{s,} a _{1',} \ldots, a _{s'} \in A .

If in addition

\varphi is a bijection and \varphi ^{-1} \colon B \to A is a Freiman s -homomorphism, then \varphi is a Freiman s -isomorphism.

If

\varphi is a Freiman s -homomorphism, then \varphi is a Freiman t -homomorphism for any positive integer t such that 2 \le t \le s .

Then the Ruzsa modeling lemma states the following:

Let

A be a finite set of integers, and let s \ge 2 be a positive integer. Let N be a positive integer such that N \ge |sA - sA| . Then there exists a subset A' of A with cardinality at least |A|/s such that A' is Freiman s -isomorphic to a subset of Z /N Z .

The last statement means there exists some Freiman

s -homomorphism between the two subsets.

Proof sketch: Choose a prime

q sufficiently large such that the modulo-q reduction map \pi _{q} \colon Z \to Z /q Z is a Freiman s -isomorphism from A to its image in Z /q Z . Let \psi _{q} \colon Z /q Z \to Z be the lifting map that takes each member of Z /q Z to its unique representative in \{ 1 ,\ldots,q\} \subseteq Z . For nonzero λ \in Z /q Z , let ⋅ λ \colon Z /q Z \to Z /q Z be the multiplication by λ map, which is a Freiman s -isomorphism. Let B be the image ( ⋅ λ \circ\pi _{q)(A)} . Choose a suitable subset B' of B with cardinality at least |B|/s such that the restriction of \psi _{q} to B' is a Freiman s -isomorphism onto its image, and let A' \subseteq A be the preimage of B' under ⋅ λ \circ\pi _{q} . Then the restriction of \psi _{q} \circ ⋅ λ \circ \pi _{q} to A' is a Freiman s -isomorphism onto its image \psi _{q(B')} . Lastly, there exists some choice of nonzero λ such that the restriction of the modulo-N reduction Z \to Z /N Z to \psi _{q(B')} is a Freiman s -isomorphism onto its image. The result follows after composing this map with the earlier Freiman s -isomorphism.

Bohr sets and Bogolyubov's lemma

Though Freiman's theorem applies to sets of integers, the Ruzsa modeling lemma allows one to model sets of integers as subsets of finite cyclic groups. So it is useful to first work in the setting of a finite field, and then generalize results to the integers. The following lemma was proved by Bogolyubov:

Let

A \in F ^{n} _{2} and let \alpha = |A|/ 2 ^{n} . Then 4 A contains a subspace of F ^{n} _{2} of dimension at least n - \alpha ^{-2} .

Generalizing this lemma to arbitrary cyclic groups requires an analogous notion to “subspace”: that of the Bohr set. Let

R be a subset of Z /N Z where N is a prime. The Bohr set of dimension |R| and width \varepsilon is \operatorname{Bohr}(R, \varepsilon) = \{ x \in Z /N Z : \forall r \in R, |rx/N| \le \varepsilon \},

where

|rx/N| is the distance from rx/N to the nearest integer. The following lemma generalizes Bogolyubov's lemma:

Let

A \in Z /N Z and \alpha = |A|/N . Then 2 A -2 A contains a Bohr set of dimension at most \alpha ^{-2} and width 1 / 4 .

Here the dimension of a Bohr set is analogous to the codimension of a set in

F ^{n} _{2} . The proof of the lemma involves Fourier-analytic methods. The following proposition relates Bohr sets back to generalized arithmetic progressions, eventually leading to the proof of Freiman's theorem.

Let

X be a Bohr set in Z /N Z of dimension d and width \varepsilon . Then X contains a proper generalized arithmetic progression of dimension at most d and size at least (\varepsilon/d) ^{dN} .

The proof of this proposition uses Minkowski's theorem, a fundamental result in geometry of numbers.

Proof

By the Plünnecke–Ruzsa inequality,

| 8 A -8 A|\le K ^{16} |A| . By Bertrand's postulate, there exists a prime N such that | 8 A -8 A|\le N\le 2 K ^{16} |A| . By the Ruzsa modeling lemma, there exists a subset A' of A of cardinality at least |A|/ 8 such that A' is Freiman 8-isomorphic to a subset B\subseteq Z /N Z .

By the generalization of Bogolyubov's lemma,

2 B -2 B contains a proper generalized arithmetic progression of dimension d at most ( 1 /( 8 ⋅ 2 K ^{16} )) ^{-2} =256 K ^{32} and size at least ( 1 /( 4 d)) ^{dN} . Because A' and B are Freiman 8-isomorphic, 2 A' -2 A' and 2 B -2 B are Freiman 2-isomorphic. Then the image under the 2-isomorphism of the proper generalized arithmetic progression in 2 B -2 B is a proper generalized arithmetic progression in 2 A' -2 A'\subseteq 2 A -2 A called P .

But

P + A\subseteq 3 A -2 A , since P\subseteq 2 A -2 A . Thus |P + A|\le | 3 A -2 A|\le | 8 A -8 A|\le N\le ( 4 d) ^{d|P|} so by the Ruzsa covering lemma A\subseteq X + P - P for some X\subseteq A of cardinality at most ( 4 d) ^{d} . Then X + P - P is contained in a generalized arithmetic progression of dimension |X| + d and size at most 2 ^{|X|} 2 ^{d} |P|\le 2 ^{|X|+d} | 2 A -2 A|\le 2 ^{|X|+d} K ^{4|A|} , completing the proof.

Generalizations

A result due to Ben Green and Imre Ruzsa generalized Freiman's theorem to arbitrary abelian groups. They used an analogous notion to generalized arithmetic progressions, which they called coset progressions. A coset progression of an abelian group

G is a set P + H for a proper generalized arithmetic progression P and a subgroup H of G . The dimension of this coset progression is defined to be the dimension of P , and its size is defined to be the cardinality of the whole set. Green and Ruzsa showed the following:

Let

A be a finite set in an abelian group G such that |A + A| \le K|A| . Then A is contained in a coset progression of dimension at most d(K) and size at most f(K)|A| , where f(K) and d(K) are functions of K that are independent of G .

Green and Ruzsa provided upper bounds of

d(K) = CK ^{4log} (K +2 ) and f(K) = e ^{CK ^{4log} ^{2(K+2)}} for some absolute constant C .^[9]

Terence Tao (2010) also generalized Freiman's theorem to solvable groups of bounded derived length.^[10]

Extending Freiman’s theorem to an arbitrary nonabelian group is still open. Results for

K< 2 , when a set has very small doubling, are referred to as Kneser theorems.^[11]

The polynomial Freiman–Ruzsa conjecture,^[12] is a generalization published in a paper^[13] by Imre Ruzsa but credited by him to Katalin Marton. It states that if a subset of a group (a power of a cyclic group)

A\subset G has doubling constant such that |A + A|\le K|A| then it is covered by a bounded number K ^{C} of cosets of some subgroup H\subset G with|H|\le |A| . In 2012 Toms Sanders gave an almost polynomial bound of the conjecture for abelian groups.^{[14] [15]} In 2023 a solution over G = F ^{n} _{2} a field of characteristic 2 has been posted as a preprint by Tim Gowers, Ben Green, Freddie Manners and Terry Tao.^{[16] [17] [18]}

See also

• Markov spectrum
• Plünnecke–Ruzsa inequality
• Kneser's theorem (combinatorics)

Further reading

• G. A. . Freiman . Gregory Freiman . Structure theory of set addition . Astérisque . 258 . 1999 . 1–33 . 0958.11008 .

Notes and References

1. 0163.29501 . Freiman . G.A. . Gregory Freiman . Addition of finite sets . en . Soviet Mathematics. Doklady . 5 . 1366–1370 . 1964 .
2. Book: Freiman, G. A. . Gregory Freiman . Foundations of a Structural Theory of Set Addition . ru . Kazan Gos. Ped. Inst. . Kazan . 1966 . 140 . 0203.35305 .
3. Book: Nathanson, Melvyn B. . 1996 . Additive Number Theory: Inverse Problems and Geometry of Sumsets . 165 . . Springer . 978-0-387-94655-9 . 0859.11003. p. 252.
4. Ruzsa . I. Z. . August 1992 . Arithmetical progressions and the number of sums . Periodica Mathematica Hungarica . en . 25 . 1 . 105–111 . 10.1007/BF02454387 . 0031-5303.
5. Imre Z. . Ruzsa . Imre Z. Ruzsa . Generalized arithmetical progressions and sumsets . . 65 . 4 . 1994 . 379–388 . 0816.11008 . 10.1007/bf01876039 . free.
6. 2002. A polynomial bound in Freiman's theorem. Duke Mathematical Journal. 113. 399–419. 1909605. Chang. Mei-Chu. 3. 10.1215/s0012-7094-02-11331-3. 10.1.1.207.3090.
7. Tom. Sanders. Tom Sanders (mathematician). 2013. The structure theory of set addition revisited. Bulletin of the American Mathematical Society. 50. 93–127. 10.1090/S0273-0979-2012-01392-7 . 1212.0458. 42609470 .
8. Web site: Zhao . Yufei . Graph Theory and Additive Combinatorics . 2019-12-02 . 2019-11-23 . https://web.archive.org/web/20191123230241/http://yufeizhao.com/gtac/fa17/gtac.pdf . dead .
9. Imre Z. . Ruzsa . Imre Z. Ruzsa . Green . Ben . Ben Green (mathematician) . Freiman's theorem in an arbitrary abelian group . Journal of the London Mathematical Society. 75 . 1 . 2007 . 163–175 . 10.1112/jlms/jdl021. math/0505198 . 15115236 .
10. Terence . Tao. Terence Tao . Freiman's theorem for solvable groups . Contributions to Discrete Mathematics . 5 . 2 . 2010 . 137–184 . 10.11575/cdm.v5i2.62020 . free.
11. Web site: Tao . Terence . Terence Tao. An elementary non-commutative Freiman theorem . Terence Tao's blog. 10 November 2009 .
12. Web site: 2007-03-11 . (Ben Green) The Polynomial Freiman–Ruzsa conjecture . 2023-11-14 . What's new . en.
13. Ruzsa . I. . 1999 . An analog of Freiman's theorem in groups . Astérisque . 258 . 323–326.
14. Sanders . Tom . 2012-10-15 . On the Bogolyubov–Ruzsa lemma . Analysis & PDE . en . 5 . 3 . 627–655 . 10.2140/apde.2012.5.627 . 1948-206X. free . 1011.0107 .
15. Web site: Brubaker . Ben . 2023-12-04 . An Easy-Sounding Problem Yields Numbers Too Big for Our Universe . 2023-12-11 . Quanta Magazine . en.
16. Gowers . W. T. . Green . Ben . Manners . Freddie . Tao . Terence . 2023 . On a conjecture of Marton . math.NT . 2311.05762.
17. Web site: 2023-11-13 . On a conjecture of Marton . 2023-11-14 . What's new . en.
18. Web site: Sloman . Leila . December 6, 2023 . 'A-Team’ of Math Proves a Critical Link Between Addition and Sets . December 16, 2023 . Quanta Magazine.