Academic literature on the topic 'Freiman-Ruzsa theorem'

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.

Let A and B be two affinely generating sets of ℤ2n. As usual, we denote their Minkowski sum by A+B. How small can A+B be, given the cardinalities of A and B? We give a tight answer to this question. Our bound is attained when both A and B are unions of cosets of a certain subgroup of ℤ2n. These cosets are arranged as Hamming balls, the smaller of which has radius 1.By similar methods, we re-prove the Freiman–Ruzsa theorem in ℤ2n, with an optimal upper bound. Denote by F(K) the maximal spanning constant |〈 A 〉|/|A| over all subsets A ⊆ ℤ2n with doubling constant |A+A|/|A| ≤ K. We explicitly calculate F(K), and in particular show that 4K/4K ≤ F(K)⋅(1+o(1)) ≤ 4K/2K. This improves the estimate F(K) = poly(K)4K, found recently by Green and Tao [17] and by Konyagin [23].

Let G = (G, +) be an additive group. The sumset theory of Plünnecke and Ruzsa gives several relations between the size of sumsets A + B of finite sets A, B, and related objects such as iterated sumsets kA and difference sets A − B, while the inverse sumset theory of Freiman, Ruzsa, and others characterizes those finite sets A for which A + A is small. In this paper we establish analogous results in which the finite set A ⊂ G is replaced by a discrete random variable X taking values in G, and the cardinality |A| is replaced by the Shannon entropy H(X). In particular, we classify those random variables X which have small doubling in the sense that H(X1 + X2) = H(X) + O(1) when X1, X2 are independent copies of X, by showing that they factorize as X = U + Z, where U is uniformly distributed on a coset progression of bounded rank, and H(Z) = O(1).When G is torsion-free, we also establish the sharp lower bound $\Ent(X+X) \geq \Ent(X) + \frac{1}{2} \log 2 - o(1)$, where o(1) goes to zero as H(X) → ∞.

Réalisé en cotutelle avec l'Université Paris-Diderot.
Nous présentons trois résultats en combinatoire additive, un domaine récent à la croisée de la combinatoire, l'analyse harmonique et la théorie analytique des nombres. Le thème unificateur de notre thèse est la détection de structures additives dans les ensembles arithmétiques à faible densité, avec un intérêt particulier pour les aspects quantitatifs. Notre première contribution est une estimation de densité améliorée pour le problème, initié entre autres par Bourgain, de trouver une longue progression arithmétique dans un ensemble somme triple. Notre deuxième résultat consiste en une généralisation des bornes de Sanders pour le théorème de Roth, du cas d'un ensemble dense dans les entiers à celui d'un ensemble à faible croissance additive dans un groupe abélien arbitraire. Finalement, nous étendons les meilleures bornes quantitatives connues pour le théorème de Roth dans les premiers, à tous les systèmes d'équations linéaires invariants par translation et de complexité un.
We present three results in additive combinatorics, a recent field at the interface of combinatorics, harmonic analysis and analytic number theory. The unifying theme in our thesis is the detection of additive structure in arithmetic sets of low density, with an emphasis on quantitative aspects. Our first contribution is an improved density estimate for the problem, initiated by Bourgain and others, of finding a long arithmetic progression in a triple sumset. Our second result is a generalization of Sanders' bounds for Roth's theorem from the dense setting, to the setting of small doubling in an arbitrary abelian group. Finally, we extend the best known quantitative results for Roth's theorem in the primes, to all translation-invariant systems of equations of complexity one.