betaFeedback

WorksMathematics

Additive energy, Freiman's lemma, and an edge-isoperimetric problem on the boolean cube

Abstract

Let d∈Nd \in \mathbb{N} and let A⊆RdA \subseteq \mathbb{R}^d be a finite, non-empty set not contained in any translate of a hyperplane. We show that there exists a subset S⊆AS \subseteq A such that d≪∣S∣≪dd \ll |S| \ll d and E(A,S):=∣{(a1,a2,s1,s2)∈A×A×S×S:a1+s1=a2+s2}∣≪∣A∣∣S∣.E(A,S) := |\{(a_1,a_2,s_1,s_2)\in A\times A\times S\times S:a_1+s_1=a_2+s_2\}|\ll\lvert A\rvert\lvert S\rvert. This can be interpreted as a robust, analytic generalisation of the classical Freiman's lemma, and recovers Freiman's lemma up to a constant multiplicative factor. In the process of proving this result, we also show that for any integer 1≤m≤d1 \leq m \leq d and any set A⊂RdA \subset \mathbb{R}^d with ∣A∣≤(dm)|A| \leq \binom{d}{m}, one has E(A,B)≤4(m+1/m)∣A∣∣B∣, E(A, B) \leq 4(m + 1/m) |A||B|, where BB is the canonical basis of Zd\mathbb{Z}^d. This gives new estimates for multiplicative energies between finite sets of primes and arbitrary subsets of positive integers, improving a previous result of Shkredov. Using related ideas, we also prove new bounds for an edge-isoperimetric problem for certain graphs on the boolean cube, improving an earlier result of Kirshner and Samorodnitsky. We give two different proofs of the first result described in this abstract and three different proofs of the second one.

Introduction

An important theme in additive combinatorics is the interplay between notions of dimension of a set and its additive structure. For example, Freiman’s theorem states that any finite set A⊆ZA \subseteq\mathbb{Z} such that ∣A+A∣≤K∣A∣|A+A| \le K|A|, where

A+A={a1+a2:a1,a2∈A}A+A=\{a_1+a_2:a_1,a_2\in A\}

must be contained in a small-dimensional generalised arithmetic progression PP of the form

P={u0+u1ℓ1+⋯+urℓr:1≤ℓi≤Li (1≤i≤r)}P=\{u_0+u_1\ell_1+\cdots+u_r\ell_r:1\le\ell_i\le L_i\ (1\le i\le r)\}

for some suitably chosen u0,u1,…,ur∈Zu_0,u_1,\ldots,u_r\in\mathbb{Z} and L1,…,Lr∈NL_1,\ldots,L_r\in\mathbb{N} satisfying

L1⋯Lr≪K∣A∣andr≪K1.(1)L_1\cdots L_r\ll_K |A| \quad\text{and}\quad r\ll_K 1. \tag*{(1)}

Obtaining variations of this type of result with a strong quantitative dependence on KK forms the content of the infamous polynomial Freiman–Ruzsa conjecture over Z\mathbb{Z}, see [22, 24].

From the perspective of applications, one is often just interested in obtaining good bounds for the second inequality in (1); see, for instance, the weak polynomial Freiman–Ruzsa conjecture over Z\mathbb{Z} and its applications to sum-product-type estimates over R\mathbb{R} [10, 18]. This is roughly equivalent to studying the following type of question: given a set A⊆RdA \subseteq\mathbb{R}^{d}, what notions of high-dimensionality can we apply on AA to deduce strong lower bounds for ∣A+A∣/∣A∣|A+A|/|A|? The starting result here is the well-known Freiman’s lemma, which states that if A⊆RdA \subseteq\mathbb{R}^{d} satisfies dim⁡(A)=d\dim(A)=d, then

∣A+A∣≥(d+1)∣A∣−d(d+1)/2≥(d+1)∣A∣/2,(2)|A+A| \ge(d+1)|A|-d(d+1)/2 \ge(d+1)|A|/2, \tag*{(2)}

where dim⁡(A)\dim(A) denotes the dimension of the affine subspace generated by AA. The first inequality here is sharp, as can be seen by setting

A={e1,2e1,…,Ne1}+{0,e2,e3,…,ed},A=\{e_{1},2e_{1},\ldots,Ne_{1}\}+\{0,e_{2},e_{3},\ldots,e_{d}\},

where {e1,…,ed}\{e_{1},\ldots,e_{d}\} is the canonical basis of Zd\mathbb{Z}^{d}. One can obtain stronger lower bounds of the shape ∣A+A∣≥Cd∣A∣|A+A|\ge C^{d}|A| for some absolute constant C>1C>1 by assuming stricter “higher-dimensional” conditions on AA; see, for example, the Freiman–Bilu theorem [4] or lower bounds for sumsets of sets containing hypercubes [12, 16]. Despite its simplicity, (2) has had various applications to Freiman-type inverse theorems and sum-product estimates.

More recently, various works [14, 8] have explored robust versions of (2), wherein, given a finite set A⊆RdA\subseteq\mathbb{R}^{d} with dim⁡(A)=d\dim(A)=d, one is interested in finding a set S⊆AS\subseteq A such that

∣S∣≪d1and∣A+S∣≫d∣A∣.(3)|S|\ll_{d}1\quad\text{and}\quad|A+S|\gg d|A|. \tag*{(3)}

Such results have found applications towards a conjecture of Alon [1] on independence numbers of Cayley graphs over Z/NZ\mathbb{Z}/N\mathbb{Z} as well as a question of Green–Morris [11] on counting the number of subsets of [N]={1,2,…,N}[N]=\{1,2,\ldots,N\} with a given size and doubling, see [8, 9]. Jing–Mudgal [14] proved that for any finite set A⊆RdA\subseteq\mathbb{R}^{d} with dim⁡(A)=d\dim(A)=d, one can find S⊆AS\subseteq A with

∣S∣≪d1and∣A+S∣≥(d+1)∣A∣−5(d+1)3.(4)|S|\ll_{d}1\quad\text{and}\quad|A+S|\ge(d+1)|A|-5(d+1)^{3}. \tag*{(4)}

The dependence of ∣S∣|S| on dd here is quite poor. By employing quite different methods, Campos–Dahia–Marciano [8] proved that for any γ>0\gamma>0, whenever d>γ−3d>\gamma^{-3}, one can find S⊆AS\subseteq A such that

∣S∣≪γ−1dand∣A+S∣≥(1−5γ)(d+1)∣A∣/2.(5)|S|\ll\gamma^{-1}d\quad\text{and}\quad|A+S|\ge(1-5\gamma)(d+1)|A|/2. \tag*{(5)}

Thus, while the above lower bound is weaker than its analogue described in (4), the upper bound on ∣S∣|S| is quite nice. In a very recent sequel paper, Campos–Dahia–Marciano [9] removed the factor of 1/21/2 from the lower bound in the right hand side of (5) at the cost of worsening the dependence of ∣S∣|S| on dd as well as requiring ∣A∣≫d/γ|A|\gg d/\gamma.

In this paper, using very different techniques as compared to [8, 9, 14] we provide a significant qualitative generalisation of such results which is more analytic in nature. In particular, let us define, for any non-empty finite sets A,B⊆RdA,B\subseteq\mathbb{R}^{d}, the additive energy

E(A,B)=∑a1,a2∈Ab1,b2∈B1a1+b1=a2+b2.E(A,B)=\sum_{\substack{a_{1},a_{2}\in A\\b_{1},b_{2}\in B}}1_{a_{1}+b_{1}=a_{2}+b_{2}}.

Moreover, we call a non-empty set S={s1,…,sr}⊂RdS=\{s_{1},\ldots,s_{r}\}\subset\mathbb{R}^{d} affine-independent if, for any c1,…,cr∈Rc_{1},\ldots,c_{r}\in\mathbb{R} with c1+⋯+cr=0c_{1}+\cdots+c_{r}=0, we have c1s1+⋯+crsr=0c_{1}s_{1}+\cdots+c_{r}s_{r}=0 if and only if c1=⋯=cr=0c_{1}=\cdots=c_{r}=0. With this in hand, our main result is as follows.

Theorem 1.1. Let d∈Nd\in\mathbb{N} and let A⊂RdA\subset\mathbb{R}^{d} be a finite, non-empty set with dim⁡(A)=d\dim(A)=d. Then there exists some affine-independent S⊂AS\subset A such that d≪∣S∣≪dd\ll|S|\ll d and

E(A,S)≪∣A∣∣S∣.E(A,S)\ll|A||S|.

Theorem 1.1 immediately delivers estimates of the shape (3). Indeed, a simple application of Cauchy’s inequality implies that

∣A+S∣≥∣A∣2∣S∣2E(A,S)≫∣A∣∣S∣≫d∣A∣.|A+S| \ge\frac{|A|^{2}|S|^{2}}{E(A,S)} \gg|A||S| \gg d|A|.

Hence, Theorem 1.1 suggests a new heuristic as to why finite sets A⊂RdA \subset\mathbb{R}^{d} with dim⁡(A)=d\dim(A)=d satisfy ∣A+A∣/∣A∣≫d|A+A|/|A| \gg d: one can always find an affine-independent set S⊆AS \subseteq A satisfying ∣S∣≫d|S| \gg d with which AA has very little additive interaction. More generally, Theorem 1.1 dispenses the following corollary.

Corollary 1.2. Let η∈(0,1]\eta\in(0,1], let d∈Nd \in\mathbb{N} and let A⊂RdA \subset\mathbb{R}^{d} be a finite, non-empty set with dim⁡(A)=d\dim(A)=d. Then there exists some S⊂AS \subset A with d≪∣S∣≪dd \ll|S| \ll d such that, for any set B⊆AB \subseteq A with ∣B∣≥η∣A∣|B| \ge\eta|A|, one has

∣B+S∣≫η2d∣A∣.|B+S| \gg\eta^{2}d|A|.

This highlights the strength of upper bounds on energies as compared to lower bounds of sumsets; the former very easily extend to dense subsets while the latter do not offer this flexibility. Consequently, our proof of Theorem 1.1 requires some new ideas and in fact, the techniques involved therein differ significantly from the ideas used in [14, 8, 9]. Indeed, while the latter works rely crucially on combinatorial-geometric arguments to obtain translates of the set AA which are sufficiently disjoint, one of the ideas we use to obtain upper bounds on the additive energy E(A,S)E(A,S) is to employ analytic methods to pass to studying higher-order energies.

Thus, given finite, non-empty subsets X,SX,S of some abelian group and f:X→[0,∞)f:X \to[0,\infty), we define the weighted additive energy

Ef(X,S):=∑x1,x2∈Xf(x1)f(x2)∑s1,s2∈S1x1+s1=x2+s2.(6)E_f(X,S):=\sum_{x_1,x_2\in X}f(x_1)f(x_2)\sum_{s_1,s_2\in S}\mathbf{1}_{x_1+s_1=x_2+s_2}. \tag*{(6)}

We are interested in upper bounds for Ef(X,S)E_f(X,S) and E(X,S)E(X,S) when S={e1,…,ed}S=\{e_1,\ldots,e_d\} and X⊆RdX \subseteq\mathbb{R}^{d} is some finite, non-empty set. When ∣X∣≥2d|X| \ge2^d, one can not do significantly better than the trivial bound E(X,S)≤∣X∣∣S∣2E(X,S) \le|X||S|^2. Indeed setting X={0,1}dX=\{0,1\}^{d}, observe that for any $1 \le i < j \le d,thereareatleast$2d−2, there are at least \$2^{d-2} elements x∈Xx \in X such that x+ei−ej∈Xx+e_i-e_j \in X, and so,

E(X,S)≥∣S∣∣X∣+∣S∣(∣S∣−1)∣X∣/4≫∣X∣∣S∣2.E(X,S) \ge|S||X|+|S|(|S|-1)|X|/4 \gg|X||S|^2.

On the other hand, when ∣X∣≪dO(1)|X| \ll d^{O(1)}, one can not find such good lower bounds. For instance, given d,m∈Nd,m \in\mathbb{N} with m≤d/2m \le d/2, one can set

References

  1. [1]N. Alon, Large sets in finite fields are sumsets, J. Number Theory 126 (2007), no. 1, 110–118.DOI
  2. [2]A. E. Ashikhmin, G. D. Cohen, M. Krivelevich, S. N. Litsyn, Bounds on distance distributions in codes of known size, IEEE Trans. Inform. Theory 51 (2005), no. 1, 250–258.
  3. [3]W. Beckner, Inequalities in Fourier analysis, Ann. of Math. (2) 102 (1975), no. 1, 159–182.DOI
  4. [4]Y. Bilu, Structure of sets with small sumset, Structure theory of set addition, Astérisque No. 258 (1999), xi, 77–108.
  5. [5]A. Bonami, Étude des coefficients de Fourier des fonctions de Lᵖ(G), Ann. Inst. Fourier (Grenoble) 20 (1970), fasc. 2, 335–402.DOI
  6. [6]S. Brazitikos, A. Giannopoulos, P. Valettas, B.-H. Vritsiou, Geometry of isotropic convex bodies, Mathematical Surveys and Monographs, 196, Amer. Math. Soc., Providence, RI, 2014; MR3185453
  7. [7]D. A. Burgess, The distribution of quadratic residues and non-residues, Mathematika 4 (1957), 106–112.DOI
  8. [8]M. Campos, G. Dahia, J. P. Marciano, On the independence number of sparser random Cayley graphs, J. Lond. Math. Soc. (2) 110 (2024), no. 6, Paper No. e70041, 54 pp.DOI
  9. [9]M. Campos, G. Dahia, J. P. Marciano, Counting sets with given doubling via dimension, arXiv:2609.05384.
  10. [10]W. T. Gowers, B. Green, F. Manners, T. Tao, On a conjecture of Marton, Ann. of Math. (2) 201 (2025), no. 2, 515–549.arxiv.org/abs/2311.05762
  11. [11]B. Green, R. Morris, Counting sets with small sumset and applications, Combinatorica 36 (2016), 129–159arxiv.org/abs/1305.3079
  12. [12]B. Green, T. Tao, Compressions, convex geometry and the Freiman–Bilu theorem, Q. J. Math. 57 (2006), no. 4, 495–504.DOI
  13. [13]L. Gross, Logarithmic Sobolev inequalities, Amer. J. Math. 97 (1975), no. 4, 1061–1083.
  14. [14]Y. Jing, A. Mudgal, Kemperman’s inequality and Freiman’s lemma via few translates, arXiv:2307.03066.arxiv.org/abs/2307.03066
  15. [15]N. Kirshner, A. Samorodnitsky, A moment ratio bound for polynomials and some extremal properties of Krawchouk polynomials and Hamming spheres, IEEE Trans. Inform. Theory 67 (2021), no. 6, 3509–3541.arxiv.org/abs/1909.11929
  16. [16]J. Lim, A. Mudgal, C. Pohoata, X. Shao, On exponential Freiman dimension, arXiv:2512.14403.arxiv.org/abs/2512.14403
  17. [17]R. Lyons, Determinantal probability measures, Publ. Math. 98 (2003), 167–212.
  18. [18]A. Mudgal, An Elekes–Rónyai theorem for sets with few products, Int. Math. Res. Not. IMRN 2024, no. 13, 10410–10424.arxiv.org/abs/2308.04191
  19. [19]A. Mudgal, On an asymmetric additive energy inequality, arXiv:2607.25442
  20. [20]T. Nishiyama, Lower bounds for the total variation distance given means and variances of distributions, arXiv:2212.05820.arxiv.org/abs/2212.05820
  21. [21]R. O’Donnell, Analysis of Boolean functions, Cambridge University Press, New York, 2014. xx+423 pp.arxiv.org/abs/2105.10386
  22. [22]R. Raghavan, Improved Bounds for the Freiman-Ruzsa Theorem, arXiv:2512.11217.
  23. [23]C. Reiher, T. Schoen, Note on the theorem of Balog, Szemerédi, and Gowers, Combinatorica 44 (2024), no. 3, 691–698.DOI
  24. [24]T. Sanders, The structure theory of set addition revisited, Bull. Amer. Math. Soc. (N.S.) 50 (2013), no. 1, 93–127.DOI
  25. [25]C. Schildkraut, Lower bounds for sphere packing in arbitrary norms, arXiv:2406.07479.
  26. [26]I. D. Shkredov, On some applications of GCD sums to arithmetic combinatorics, J. Number Theory 231 (2022), 433–450.arxiv.org/abs/2010.03020
  27. [27]I.D. Shkredov, Additive dimension and the growth of sets, Discrete Math. 347 (2024), no. 9, Paper No. 114077, 25 pp.arxiv.org/abs/2205.07296

Paper details

vlnc:W_r7fvkx7y
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 23

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents