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 ⊆ Z A \subseteq\mathbb{Z} A ⊆ Z such that ∣ A + A ∣ ≤ K ∣ A ∣ |A+A| \le K|A| ∣ A + A ∣ ≤ K ∣ A ∣ , where
A + A = { a 1 + a 2 : a 1 , a 2 ∈ A } A+A=\{a_1+a_2:a_1,a_2\in A\} A + A = { a 1 + a 2 : a 1 , a 2 ∈ A }
must be contained in a small-dimensional generalised arithmetic progression P P P of the form
P = { u 0 + u 1 ℓ 1 + ⋯ + u r ℓ r : 1 ≤ ℓ i ≤ L i ( 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)\} P = { u 0 + u 1 ℓ 1 + ⋯ + u r ℓ r : 1 ≤ ℓ i ≤ L i ( 1 ≤ i ≤ r )}
for some suitably chosen u 0 , u 1 , … , u r ∈ Z u_0,u_1,\ldots,u_r\in\mathbb{Z} u 0 , u 1 , … , u r ∈ Z and L 1 , … , L r ∈ N L_1,\ldots,L_r\in\mathbb{N} L 1 , … , L r ∈ N satisfying
L 1 ⋯ L r ≪ K ∣ A ∣ and r ≪ K 1. (1) L_1\cdots L_r\ll_K |A| \quad\text{and}\quad r\ll_K 1. \tag*{(1)} L 1 ⋯ L r ≪ K ∣ A ∣ and r ≪ K 1. (1)
Obtaining variations of this type of result with a strong quantitative dependence on K K K forms the content of the infamous polynomial Freiman–Ruzsa conjecture over Z \mathbb{Z} 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} Z and its applications to sum-product-type estimates over R \mathbb{R} R [10 , 18 ] . This is roughly equivalent to studying the following type of question: given a set A ⊆ R d A \subseteq\mathbb{R}^{d} A ⊆ R d , what notions of high-dimensionality can we apply on A A A to deduce strong lower bounds for ∣ A + A ∣ / ∣ A ∣ |A+A|/|A| ∣ A + A ∣/∣ A ∣ ? The starting result here is the well-known Freiman’s lemma, which states that if A ⊆ R d A \subseteq\mathbb{R}^{d} A ⊆ R d satisfies dim ( A ) = d \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)} ∣ A + A ∣ ≥ ( d + 1 ) ∣ A ∣ − d ( d + 1 ) /2 ≥ ( d + 1 ) ∣ A ∣/2 , (2)
where dim ( A ) \dim(A) dim ( A ) denotes the dimension of the affine subspace generated by A A A . The first inequality here is sharp, as can be seen by setting
A = { e 1 , 2 e 1 , … , N e 1 } + { 0 , e 2 , e 3 , … , e d } , A=\{e_{1},2e_{1},\ldots,Ne_{1}\}+\{0,e_{2},e_{3},\ldots,e_{d}\}, A = { e 1 , 2 e 1 , … , N e 1 } + { 0 , e 2 , e 3 , … , e d } ,
where { e 1 , … , e d } \{e_{1},\ldots,e_{d}\} { e 1 , … , e d } is the canonical basis of Z d \mathbb{Z}^{d} Z d . One can obtain stronger lower bounds of the shape ∣ A + A ∣ ≥ C d ∣ A ∣ |A+A|\ge C^{d}|A| ∣ A + A ∣ ≥ C d ∣ A ∣ for some absolute constant C > 1 C>1 C > 1 by assuming stricter “higher-dimensional” conditions on A A A ; 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 ⊆ R d A\subseteq\mathbb{R}^{d} A ⊆ R d with dim ( A ) = d \dim(A)=d dim ( A ) = d , one is interested in finding a set S ⊆ A S\subseteq A S ⊆ A such that
∣ S ∣ ≪ d 1 and ∣ A + S ∣ ≫ d ∣ A ∣ . (3) |S|\ll_{d}1\quad\text{and}\quad|A+S|\gg d|A|. \tag*{(3)} ∣ S ∣ ≪ d 1 and ∣ A + S ∣ ≫ d ∣ A ∣. (3)
Such results have found applications towards a conjecture of Alon [1 ] on independence numbers of Cayley graphs over Z / N Z \mathbb{Z}/N\mathbb{Z} Z / N 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\} [ N ] = { 1 , 2 , … , N } with a given size and doubling, see [8 , 9 ] . Jing–Mudgal [14 ] proved that for any finite set A ⊆ R d A\subseteq\mathbb{R}^{d} A ⊆ R d with dim ( A ) = d \dim(A)=d dim ( A ) = d , one can find S ⊆ A S\subseteq A S ⊆ A with
∣ S ∣ ≪ d 1 and ∣ 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)} ∣ S ∣ ≪ d 1 and ∣ A + S ∣ ≥ ( d + 1 ) ∣ A ∣ − 5 ( d + 1 ) 3 . (4)
The dependence of ∣ S ∣ |S| ∣ S ∣ on d d d here is quite poor. By employing quite different methods, Campos–Dahia–Marciano [8 ] proved that for any γ > 0 \gamma>0 γ > 0 , whenever d > γ − 3 d>\gamma^{-3} d > γ − 3 , one can find S ⊆ A S\subseteq A S ⊆ A such that
∣ S ∣ ≪ γ − 1 d and ∣ 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)} ∣ S ∣ ≪ γ − 1 d and ∣ A + S ∣ ≥ ( 1 − 5 γ ) ( d + 1 ) ∣ A ∣/2. (5)
Thus, while the above lower bound is weaker than its analogue described in (4) , the upper bound on ∣ S ∣ |S| ∣ S ∣ is quite nice. In a very recent sequel paper, Campos–Dahia–Marciano [9 ] removed the factor of 1 / 2 1/2 1/2 from the lower bound in the right hand side of (5) at the cost of worsening the dependence of ∣ S ∣ |S| ∣ S ∣ on d d d as well as requiring ∣ A ∣ ≫ d / γ |A|\gg d/\gamma ∣ A ∣ ≫ d / γ .
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 ⊆ R d A,B\subseteq\mathbb{R}^{d} A , B ⊆ R d , the additive energy
E ( A , B ) = ∑ a 1 , a 2 ∈ A b 1 , b 2 ∈ B 1 a 1 + b 1 = a 2 + b 2 . 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}}. E ( A , B ) = a 1 , a 2 ∈ A b 1 , b 2 ∈ B ∑ 1 a 1 + b 1 = a 2 + b 2 .
Moreover, we call a non-empty set S = { s 1 , … , s r } ⊂ R d S=\{s_{1},\ldots,s_{r}\}\subset\mathbb{R}^{d} S = { s 1 , … , s r } ⊂ R d affine-independent if, for any c 1 , … , c r ∈ R c_{1},\ldots,c_{r}\in\mathbb{R} c 1 , … , c r ∈ R with c 1 + ⋯ + c r = 0 c_{1}+\cdots+c_{r}=0 c 1 + ⋯ + c r = 0 , we have c 1 s 1 + ⋯ + c r s r = 0 c_{1}s_{1}+\cdots+c_{r}s_{r}=0 c 1 s 1 + ⋯ + c r s r = 0 if and only if c 1 = ⋯ = c r = 0 c_{1}=\cdots=c_{r}=0 c 1 = ⋯ = c r = 0 . With this in hand, our main result is as follows.
Theorem 1.1. Let d ∈ N d\in\mathbb{N} d ∈ N and let A ⊂ R d A\subset\mathbb{R}^{d} A ⊂ R d be a finite, non-empty set with dim ( A ) = d \dim(A)=d dim ( A ) = d . Then there exists some affine-independent S ⊂ A S\subset A S ⊂ A such that d ≪ ∣ S ∣ ≪ d d\ll|S|\ll d d ≪ ∣ S ∣ ≪ d and
E ( A , S ) ≪ ∣ A ∣ ∣ S ∣ . E(A,S)\ll|A||S|. E ( A , S ) ≪ ∣ 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 ∣ 2 E ( A , S ) ≫ ∣ A ∣ ∣ S ∣ ≫ d ∣ A ∣ . |A+S| \ge\frac{|A|^{2}|S|^{2}}{E(A,S)} \gg|A||S| \gg d|A|. ∣ A + S ∣ ≥ E ( A , S ) ∣ A ∣ 2 ∣ S ∣ 2 ≫ ∣ A ∣∣ S ∣ ≫ d ∣ A ∣.
Hence, Theorem 1.1 suggests a new heuristic as to why finite sets A ⊂ R d A \subset\mathbb{R}^{d} A ⊂ R d with dim ( A ) = d \dim(A)=d dim ( A ) = d satisfy ∣ A + A ∣ / ∣ A ∣ ≫ d |A+A|/|A| \gg d ∣ A + A ∣/∣ A ∣ ≫ d : one can always find an affine-independent set S ⊆ A S \subseteq A S ⊆ A satisfying ∣ S ∣ ≫ d |S| \gg d ∣ S ∣ ≫ d with which A A A has very little additive interaction. More generally, Theorem 1.1 dispenses the following corollary.
Corollary 1.2. Let η ∈ ( 0 , 1 ] \eta\in(0,1] η ∈ ( 0 , 1 ] , let d ∈ N d \in\mathbb{N} d ∈ N and let A ⊂ R d A \subset\mathbb{R}^{d} A ⊂ R d be a finite, non-empty set with dim ( A ) = d \dim(A)=d dim ( A ) = d . Then there exists some S ⊂ A S \subset A S ⊂ A with d ≪ ∣ S ∣ ≪ d d \ll|S| \ll d d ≪ ∣ S ∣ ≪ d such that, for any set B ⊆ A B \subseteq A B ⊆ A with ∣ B ∣ ≥ η ∣ A ∣ |B| \ge\eta|A| ∣ B ∣ ≥ η ∣ A ∣ , one has
∣ B + S ∣ ≫ η 2 d ∣ A ∣ . |B+S| \gg\eta^{2}d|A|. ∣ B + S ∣ ≫ η 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 A A A which are sufficiently disjoint, one of the ideas we use to obtain upper bounds on the additive energy E ( A , S ) 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 , S X,S X , S of some abelian group and f : X → [ 0 , ∞ ) f:X \to[0,\infty) f : X → [ 0 , ∞ ) , we define the weighted additive energy
E f ( X , S ) : = ∑ x 1 , x 2 ∈ X f ( x 1 ) f ( x 2 ) ∑ s 1 , s 2 ∈ S 1 x 1 + s 1 = x 2 + s 2 . (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)} E f ( X , S ) := x 1 , x 2 ∈ X ∑ f ( x 1 ) f ( x 2 ) s 1 , s 2 ∈ S ∑ 1 x 1 + s 1 = x 2 + s 2 . (6)
We are interested in upper bounds for E f ( X , S ) E_f(X,S) E f ( X , S ) and E ( X , S ) E(X,S) E ( X , S ) when S = { e 1 , … , e d } S=\{e_1,\ldots,e_d\} S = { e 1 , … , e d } and X ⊆ R d X \subseteq\mathbb{R}^{d} X ⊆ R d is some finite, non-empty set. When ∣ X ∣ ≥ 2 d |X| \ge2^d ∣ X ∣ ≥ 2 d , one can not do significantly better than the trivial bound E ( X , S ) ≤ ∣ X ∣ ∣ S ∣ 2 E(X,S) \le|X||S|^2 E ( X , S ) ≤ ∣ X ∣∣ S ∣ 2 . Indeed setting X = { 0 , 1 } d X=\{0,1\}^{d} X = { 0 , 1 } d , observe that for any $1 \le i < j \le d, t h e r e a r e a t l e a s t $ 2 d − 2 , there are at least \$2^{d-2} , t h er e a r e a tl e a s t $ 2 d − 2 elements x ∈ X x \in X x ∈ X such that x + e i − e j ∈ X x+e_i-e_j \in X x + e i − e j ∈ 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. E ( X , S ) ≥ ∣ S ∣∣ X ∣ + ∣ S ∣ ( ∣ S ∣ − 1 ) ∣ X ∣/4 ≫ ∣ X ∣∣ S ∣ 2 .
On the other hand, when ∣ X ∣ ≪ d O ( 1 ) |X| \ll d^{O(1)} ∣ X ∣ ≪ d O ( 1 ) , one can not find such good lower bounds. For instance, given d , m ∈ N d,m \in\mathbb{N} d , m ∈ N with m ≤ d / 2 m \le d/2 m ≤ d /2 , one can set
X = { ( x 1 , … , x d ) ∈ { 0 , 1 } d : x 1 + ⋯ + x d = m } . X=\{(x_1,\ldots,x_d)\in\{0,1\}^{d}:x_1+\cdots+x_d=m\}. X = {( x 1 , … , x d ) ∈ { 0 , 1 } d : x 1 + ⋯ + x d = m } .
For any x ∈ X x \in X x ∈ X , there are at least m ( d − m ) m(d-m) m ( d − m ) choices of 1 ≤ i , j ≤ d 1 \le i,j \le d 1 ≤ i , j ≤ d such that x − e i + e j ∈ X x-e_i+e_j \in X x − e i + e j ∈ X , whence,
E ( X , S ) ≥ m ( d − m ) ∣ X ∣ . (7) E(X,S)\ge m(d-m)|X|. \tag*{(7)} E ( X , S ) ≥ m ( d − m ) ∣ X ∣. (7)
We are able to prove a corresponding upper bound in this setting.
Theorem 1.3. Let d , m ∈ N d,m \in\mathbb{N} d , m ∈ N with m ≤ d m \le d m ≤ d , let S = { e 1 , … , e d } S=\{e_1,\ldots,e_d\} S = { e 1 , … , e d } and let f : R d → [ 0 , ∞ ) f:\mathbb{R}^{d}\to[0,\infty) f : R d → [ 0 , ∞ ) be supported on a finite, non-empty set X ⊆ R d X \subseteq\mathbb{R}^{d} X ⊆ R d and satisfy
( ∑ x ∈ X f ( x ) ) 2 ∑ x ∈ X f ( x ) 2 ≤ ( d m ) . (8) \frac{\left(\sum_{x\in X}f(x)\right)^2}{\sum_{x\in X}f(x)^2}\le\binom{d}{m}. \tag*{(8)} ∑ x ∈ X f ( x ) 2 ( ∑ x ∈ X f ( x ) ) 2 ≤ ( m d ) . (8)
Then we have
E f ( X , S ) ≤ 4 d ( m + 1 / m ) ∑ x ∈ X f ( x ) 2 . (9) E_f(X,S) \leq4d(m+1/m)\sum_{x\in X} f(x)^2. \tag*{(9)} E f ( X , S ) ≤ 4 d ( m + 1/ m ) x ∈ X ∑ f ( x ) 2 . (9)
Setting f ( x ) = 1 X f(x)=\mathbf{1}_X f ( x ) = 1 X for some X ⊂ R d X\subset\mathbb{R}^d X ⊂ R d with ∣ X ∣ ≤ ( d m ) |X|\leq\binom{d}{m} ∣ X ∣ ≤ ( m d ) , Theorem 1.3 implies
E ( X , S ) ≪ m d ∣ X ∣ , (10) E(X,S)\ll md|X|, \tag*{(10)} E ( X , S ) ≪ m d ∣ X ∣ , (10)
matching the lower bound in (7) up to a factor of O ( 1 ) O(1) O ( 1 ) .
It turns out that such estimates are very closely related to an edge-isoperimetric problem for graphs on the boolean cube. For any set X ⊆ { 0 , 1 } d X\subseteq\{0,1\}^d X ⊆ { 0 , 1 } d , write T ( X ) T(X) T ( X ) for the number of ordered pairs ( x 1 , x 2 ) ∈ X × X (x_1,x_2)\in X\times X ( x 1 , x 2 ) ∈ X × X for which the difference x 1 − x 2 x_1-x_2 x 1 − x 2 contains exactly two non-zero entries. Thus, T ( X ) T(X) T ( X ) counts the number of pairs of elements of X X X at Hamming distance 2. The quantity T ( X ) T(X) T ( X ) has been previously studied in [2 , 15 ] , and the best known bound here is due to Kirshner–Samorodnitsky [15, Corollary 7], who proved strong hypercontractivity-type inequalities and combined them with Fourier-analytic arguments to get
T ( X ) ≤ e 2 m ( d − m ) ∣ X ∣ whenever X ⊆ { 0 , 1 } d satisfies ∣ X ∣ ≤ ( d m ) (11) T(X)\leq e^2m(d-m)|X|\quad\text{whenever }X\subseteq\{0,1\}^d\text{ satisfies }|X|\leq\binom{d}{m} \tag*{(11)} T ( X ) ≤ e 2 m ( d − m ) ∣ X ∣ whenever X ⊆ { 0 , 1 } d satisfies ∣ X ∣ ≤ ( m d ) (11)
for some integer 1 ≤ m ≤ d / 2 1\leq m\leq d/2 1 ≤ m ≤ d /2 . The trivial upper bound on T ( X ) T(X) T ( X ) is ( d 2 ) ∣ X ∣ \binom{d}{2}|X| ( 2 d ) ∣ X ∣ (see (21) ), and so (1.11) is only nontrivial when m ≤ 0.073 d m\leq0.073d m ≤ 0.073 d .
Using a more direct graph-theoretic approach, we can prove the following upper bound on T ( X ) T(X) T ( X ) , which improves upon (11) whenever either bound is nontrivial.
Theorem 1.4. Let m , d m,d m , d be integers such that 1 ≤ m ≤ d / 2 1\leq m\leq d/2 1 ≤ m ≤ d /2 and let X ⊂ { 0 , 1 } d X\subset\{0,1\}^d X ⊂ { 0 , 1 } d satisfy ∣ X ∣ ≤ ( d m ) |X|\leq\binom{d}{m} ∣ X ∣ ≤ ( m d ) . Then
T ( X ) ≤ 4 m d ∣ X ∣ . (12) T(X)\leq4md|X|. \tag*{(12)} T ( X ) ≤ 4 m d ∣ X ∣. (12)
We highlight the connection between Theorems 1.3 and 1.4 in Remark 2.3. For now, we simply note that a bound of the form (10) for X ⊂ { 0 , 1 } d X\subset\{0,1\}^d X ⊂ { 0 , 1 } d follows directly by applying Theorem 1.4, since points x 1 , x 2 ∈ X x_1,x_2\in X x 1 , x 2 ∈ X satisfying x 1 + e i = x 2 + e j x_1+e_i=x_2+e_j x 1 + e i = x 2 + e j for distinct 1 ≤ i , j ≤ d 1\leq i,j\leq d 1 ≤ i , j ≤ d are at Hamming distance 2. Our combinatorial proof of Theorem 1.4 can also be used to prove (1.10) in general with the same leading constant 4; see Remark 4.2.
Another interesting aspect of the proofs of Theorems 1.3 and 1.4 is that they do not invoke any hypercontractivity-type result or Fourier analysis. That said, we will provide an alternative approach to proving a weaker version of Theorem 1.3 using results of Kirshner–Samorodnitsky [15 ] on hypercontractivity for the boolean cube. In particular, we will use the latter to prove a variant of Theorem 1.3 in the group ( Z / 2 Z ) d (\mathbb{Z}/2\mathbb{Z})^d ( Z /2 Z ) d , see Lemma 6.3. This variant allows us to deduce Proposition 6.1, an analogue of Theorem 1.3 which gives a weaker version of conclusion (1.9) on the stricter assumption that ∣ X ∣ ≤ ( d m ) |X|\leq\binom{d}{m} ∣ X ∣ ≤ ( m d ) . We remark that either Theorem 1.3 or Proposition 6.1 is enough to prove Theorem 1.1.
Returning to (1.10), we can use this along with a standard fibring argument and the theory of Freiman isomorphisms to deduce the following.
Corollary 1.5. Let d , m ∈ N d,m\in\mathbb{N} d , m ∈ N such that m ≤ d m\leq d m ≤ d , let P ⊆ N P\subseteq\mathbb{N} P ⊆ N be a set of d d d prime numbers and let Q ⊆ N Q\subseteq\mathbb{N} Q ⊆ N be a finite set such that ∣ Q ∣ ≤ ( d m ) |Q|\leq\binom{d}{m} ∣ Q ∣ ≤ ( m d ) . Then
M ( P , Q ) : = ∑ q 1 , q 2 ∈ Q ∑ p 1 , p 2 ∈ P 1 p 1 q 1 = p 2 q 2 ≪ m d ∣ Q ∣ . M(P,Q):=\sum_{q_1,q_2\in Q}\sum_{p_1,p_2\in P}\mathbf{1}_{p_1q_1=p_2q_2}\ll md|Q|. M ( P , Q ) := q 1 , q 2 ∈ Q ∑ p 1 , p 2 ∈ P ∑ 1 p 1 q 1 = p 2 q 2 ≪ m d ∣ Q ∣.
Corollary 1.5 improves upon an earlier result of Shkredov [26 ] which states that for any set P P P of d d d prime numbers and any finite, non-empty set Q ⊂ N Q \subset\mathbb{N} Q ⊂ N , one has
M ( P , Q ) ≪ d ∣ Q ∣ log ∣ Q ∣ . (13) M(P,Q) \ll d|Q|\log|Q|. \tag*{(13)} M ( P , Q ) ≪ d ∣ Q ∣ log ∣ Q ∣. (13)
The above bound is only non-trivial when ∣ Q ∣ = 2 o ( d ) |Q| = 2^{o(d)} ∣ Q ∣ = 2 o ( d ) . For such choices of d d d , let 1 ≤ m ≤ d / 2 1 \le m \le d/2 1 ≤ m ≤ d /2 be an integer such that
( d m − 1 ) ≤ ∣ Q ∣ ≤ ( d m ) . \binom{d}{m-1} \le|Q| \le\binom{d}{m}. ( m − 1 d ) ≤ ∣ Q ∣ ≤ ( m d ) .
Then log ∣ Q ∣ ≫ ( m − 1 ) log ( d / m ) \log|Q| \gg(m-1)\log(d/m) log ∣ Q ∣ ≫ ( m − 1 ) log ( d / m ) , and so, Corollary 1.5 improves (13) by a factor of log ( d / m ) \log(d/m) log ( d / m ) .
Remark 1.6. We note that Shkredov [26 ] studied the setting of Corollary 1.5 in order to prove the following result. Let A ⊂ N A \subset\mathbb{N} A ⊂ N be a finite, non-empty set such that ∣ A ⋅ A ∣ ≪ ∣ A ∣ |A \cdot A| \ll|A| ∣ A ⋅ A ∣ ≪ ∣ A ∣ , where A ⋅ A = { a ⋅ a ′ : a , a ′ ∈ A } A \cdot A = \{a \cdot a' : a,a' \in A\} A ⋅ A = { a ⋅ a ′ : a , a ′ ∈ A } denotes the product set of A A A . Then the smallest positive integer k ∉ A k \notin A k ∈ / A satisfies
k ≪ log ∣ A ∣ log log ∣ A ∣ . (14) k \ll\log|A|\log\log|A|. \tag*{(14)} k ≪ log ∣ A ∣ log log ∣ A ∣. (14)
This can be seen as an integer analogue of Vinogradov’s least quadratic nonresidue problem which, given prime p p p , concerns the size n p n_p n p of the least k ∈ N k \in\mathbb{N} k ∈ N such that k ( m o d p ) ∉ R k \pmod p \notin R k ( mod p ) ∈ / R , where R R R is the set of quadratic residues in Z / p Z \mathbb{Z}/p\mathbb{Z} Z / p Z . Note that ∣ R ⋅ R ∣ = ∣ R ∣ |R \cdot R| = |R| ∣ R ⋅ R ∣ = ∣ R ∣ . It is expected that n p ≪ ε p ε n_p \ll_\varepsilon p^\varepsilon n p ≪ ε p ε for every ε > 0 \varepsilon> 0 ε > 0 , but the best unconditional result towards this is of the form n p ≪ ε p 1 / ( 4 e 1 / 2 ) + ε n_p \ll_\varepsilon p^{1/(4e^{1/2})+\varepsilon} n p ≪ ε p 1/ ( 4 e 1/2 ) + ε for every ε > 0 \varepsilon> 0 ε > 0 .1 The latter is a classical result of Burgess [7 ] .
We observe that one can use Freiman’s lemma directly to prove that
Indeed, let { 1 , 2 , … , k − 1 } ⊆ A \{1,2,\ldots,k-1\} \subseteq A { 1 , 2 , … , k − 1 } ⊆ A and let P P P be the set of primes in { 1 , 2 , … , k − 1 } \{1,2,\ldots,k-1\} { 1 , 2 , … , k − 1 } . One may now use a standard fibring argument along with (2) to deduce that
∣ P ∣ ∣ A ∣ / 2 ≤ ∣ A ⋅ A ∣ ≪ ∣ A ∣ |P||A|/2 \le|A \cdot A| \ll|A| ∣ P ∣∣ A ∣/2 ≤ ∣ A ⋅ A ∣ ≪ ∣ A ∣
whence ∣ P ∣ ≪ 1 |P| \ll1 ∣ P ∣ ≪ 1 . Since ∣ P ∣ ≫ k / log k |P| \gg k/\log k ∣ P ∣ ≫ k / log k , we must have k ≪ 1 k \ll1 k ≪ 1 .
Proof Ideas
We briefly discuss some of the ideas employed in our paper. Our starting point for proving Theorem 1.1 is by proving a decomposition lemma for arbitrary d d d -dimensional sets A ⊂ R d A \subset\mathbb{R}^d A ⊂ R d , see Lemma 3.1. In particular, using iterative applications of the weak Polynomial Freiman–Ruzsa theorem due to Gowers–Green–Manners–Tao and a strong quantitative version of the Balog–Szemerédi–Gowers theorem due to Reiher–Schoen, we are able to show that any set d d d -dimensional set A ⊂ R d A \subset\mathbb{R}^d A ⊂ R d can be partitioned into a “structured piece” A s t r A_{\mathrm{str}} A str and an “unstructured piece” A u n s t r A_{\mathrm{unstr}} A unstr , where A s t r A_{\mathrm{str}} A str is contained in few translates of a sufficiently low-dimensional subspace V ⊂ R d V \subset\mathbb{R}^d V ⊂ R d while A u n s t r A_{\mathrm{unstr}} A unstr either is quite small, or has a small additive energy and is not concentrated on any translate of subspaces approximating V V V . Using variants of Theorem 1.3, we are able to control E ( A s t r , S ) E(A_{\mathrm{str}},S) E ( A str , S ) for any set S ⊂ R d S \subset\mathbb{R}^d S ⊂ R d such that the set π ( S ) \pi(S) π ( S ) is affine-independent and ∣ π ( S ) ∣ = ∣ S ∣ |\pi(S)| = |S| ∣ π ( S ) ∣ = ∣ S ∣ , where π : R d → R d / V \pi:\mathbb{R}^d \to\mathbb{R}^d/V π : R d → R d / V is the natural projection map. Our goal now is to find a suitable affine-independent set S ⊂ A S \subset A S ⊂ A such that E ( A u n s t r , S ) E(A_{\mathrm{unstr}},S) E ( A unstr , S ) is also well-controlled. We do this via employing the probabilistic method. More specifically, we use a novel, iterative sampling procedure that takes into account that our random set S S S must have π ( S ) \pi(S) π ( S ) be affine-independent. The aforementioned properties of A u n s t r A_{\mathrm{unstr}} A unstr then imply that E ( A u n s t r , S ) E(A_{\mathrm{unstr}},S) E ( A unstr , S ) is suitably bounded above. As for Theorem 1.3 , we provide three different approaches to proving such estimates, the first being a graph-theoretic approach, the second relying on a technical analysis of higher-order additive energies and the final relying on sharp hypercontractivity-type results. Here, we briefly outline our second approach. We begin by bounding E f ( X , S ) E_f(X,S) E f ( X , S ) in terms the quantity
∑ x , x ′ ∈ X f ( x ) f ( x ′ ) ∑ s 1 , … , s 2 t ∈ S 1 x − x ′ = s 1 + ⋯ + s t − s t + 1 − ⋯ − s 2 t \sum_{x,x'\in X} f(x)f(x') \sum_{s_1,\ldots,s_{2t}\in S} \mathbf{1}_{x-x'=s_1+\cdots+s_t-s_{t+1}-\cdots-s_{2t}} x , x ′ ∈ X ∑ f ( x ) f ( x ′ ) s 1 , … , s 2 t ∈ S ∑ 1 x − x ′ = s 1 + ⋯ + s t − s t + 1 − ⋯ − s 2 t
via an application of Lemma 2.4 , where t = 2 m t=2m t = 2 m . We call the latter quantity E t E_t E t . We divide such solutions into two types; the first of these having few cancelling pairs , that is, pairs ( i , j ) ∈ { 1 , … , t } × { 1 , … , t } (i,j)\in\{1,\ldots,t\}\times\{1,\ldots,t\} ( i , j ) ∈ { 1 , … , t } × { 1 , … , t } such that s i = s j s_i=s_j s i = s j . We upper bound the number of these solutions by crucially using the linear independence of the set S S S along with the hypothesis that ( ∑ x f ( x ) ) 2 \left(\sum_x f(x)\right)^2 ( ∑ x f ( x ) ) 2 is controlled nicely by ∑ x f ( x ) 2 \sum_x f(x)^2 ∑ x f ( x ) 2 . The remaining type of solutions have many cancelling pairs. These we deal with an inductive, combinatorial argument; in particular, we show that the count of such solutions are controlled nicely by E t − 1 E_{t-1} E t − 1 . A second application of Lemma 2.4 allows us to bound this in terms of E t E_t E t and ∑ x f ( x ) 2 \sum_x f(x)^2 ∑ x f ( x ) 2 . This combines with the preceding discussion to give us the desired bound on E f ( X , S ) E_f(X,S) E f ( X , S ) .
Returning to Theorem 1.1 , our proof ideas are very analytic in nature. In particular, they crucially depend on Theorem 1.3 . There is an alternative approach to proving Theorem 1.1 (found by a query to GPT-6 Astra; see Remark 1.7 and Section A) which replaces the decomposition lemma and analytic estimates with a more geometric approach. The latter uses notions that are standard in convex geometry and relies crucially on the idea that, once a finite set A A A is normalized appropriately, the intersection A ∩ ( A + v ) A\cap(A+v) A ∩ ( A + v ) must be small if ∥ v ∥ 2 \lVert v\rVert_2 ∥ v ∥ 2 is large. (This is the content of Lemma A.4 .)
Organization
In §2 we give some definitions and set some notation which we will use throughout the paper. We also state many of the ingredients we use to prove Theorem 1.1 . In §3 we prove Theorem 1.1 assuming Theorem 1.3 . §§4–6 contain three distinct proofs of statements related to Theorem 1.3 . First, in §4, we prove Theorem 1.4 using graph-theoretic techniques. In §5, we prove Theorem 1.3 by analysing higher-order weighted additive energies. In §6, we provide an alternative proof of a weaker version of Theorem 1.3 via hypercontractivity-type results. Finally, in Appendix A, we give an alternative, more geometric proof of Theorem 1.1 which was found by GPT-6 Astra.
Notation
In this paper we use Vinogradov notation; that is, we write X ≪ z Y X\ll_z Y X ≪ z Y , or equivalently X = O z ( Y ) X=O_z(Y) X = O z ( Y ) , to mean that ∣ X ∣ ≤ C z Y |X|\le C_zY ∣ X ∣ ≤ C z Y for some constant C z > 0 C_z>0 C z > 0 which depends only on the parameter z > 0 z>0 z > 0 . Given sets A , B , C A,B,C A , B , C , we write A = B ∪ ˙ C A=B\mathbin{\dot\cup}C A = B ∪ ˙ C if A = B ∪ C A=B\cup C A = B ∪ C and B ∩ C = ∅ B\cap C=\varnothing B ∩ C = ∅ . For any n ∈ N n\in\mathbb{N} n ∈ N , we denote [ n ] = { 1 , 2 , … , n } [n]=\{1,2,\ldots,n\} [ n ] = { 1 , 2 , … , n } . For any finite, non-empty set A ⊆ R d A\subseteq\mathbb{R}^d A ⊆ R d , we write 1 A \mathbf{1}_A 1 A for its characteristic function.
Acknowledgements
We would like to thank Dan Altman for helpful conversations. The first author is supported by a Leverhulme Early Career Fellowship ECF-2025-148. The second author is supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-2146755. The first and third authors would like to thank the American Institute of Mathematics for providing excellent working conditions.
AI Declaration
The main body of this paper, that is, the content in §§1–6, was entirely generated and written by the authors without any AI assistance. AI tools, in particular GPT-6 Astra, were then used for literature search and proof-reading of this content. During this process, GPT-6 Astra suggested an alternative, more geometric approach to proving Theorem 1.1. A significantly digested and rewritten version of this is recorded in Appendix A, with the authors having found various citations and sources for all the ideas used by GPT-6 Astra.
Remark 1.7. In this remark, we present a brief mathematical and philosophical comparison of the two proofs of Theorem 1.1. The human-generated proof of Theorem 1.1, that is, the proof recorded in §3, relies on heavy machinery from additive combinatorics (see Theorems 2.7 and 2.8) along with various combinatorial and probabilistic manoeuvres and our human-generated proof of Theorem 1.3. The AI approach does not rely on the aforementioned heavy-machinery and does not consider the connection between Theorems 1.1 and 1.3. Instead, it builds a very direct geometric approach to studying Theorem 1.1, relying on ideas from convex geometry to obtain a very explicit and optimal version of Theorem 1.1, see Theorem A.1.
Theorem A.1 is a stronger version of Theorem 1.1 and the AI approach is more direct and shorter than the human-generated approach. On the other hand, an advantage of the indirect human-generated approach is finding this connection between Theorem 1.1 and Theorem 1.3, which a priori appear to be somewhat unrelated. In fact, having to prove Theorem 1.3 led us to find two new proofs of results of the shape (1.11), subsequently resulting in the improvements described in Theorem 1.4.
Preliminaries
For two finitely-supported functions f , g : R d → C f,g:\mathbb{R}^{d}\to\mathbb{C} f , g : R d → C , we define their convolution f ∗ g : R d → C f*g:\mathbb{R}^{d}\to\mathbb{C} f ∗ g : R d → C by setting
( f ∗ g ) ( x ) = ∑ y ∈ supp f f ( y ) g ( x − y ) (f*g)(x)=\sum_{y\in\operatorname{supp} f}f(y)g(x-y) ( f ∗ g ) ( x ) = y ∈ supp f ∑ f ( y ) g ( x − y )
for all x ∈ R d x\in\mathbb{R}^{d} x ∈ R d . For any p > 0 p>0 p > 0 and any finitely-supported function f : R d → C f:\mathbb{R}^{d}\to\mathbb{C} f : R d → C , we define
∥ f ∥ p = ( ∑ x ∈ supp f ∣ f ( x ) ∣ p ) 1 / p and ∥ f ∥ ∞ = sup x ∣ f ( x ) ∣ , \lVert f\rVert_{p}=\left(\sum_{x\in\operatorname{supp} f}|f(x)|^{p}\right)^{1/p}
\quad\text{and}\quad
\lVert f\rVert_{\infty}=\sup_{x}|f(x)|, ∥ f ∥ p = x ∈ supp f ∑ ∣ f ( x ) ∣ p 1/ p and ∥ f ∥ ∞ = x sup ∣ f ( x ) ∣ ,
where supp f = { x ∈ R d : f ( x ) ≠ 0 } \operatorname{supp} f=\{x\in\mathbb{R}^{d}:f(x)\ne0\} supp f = { x ∈ R d : f ( x ) = 0 } . We will also write E ( X ) = E ( X , X ) E(X)=E(X,X) E ( X ) = E ( X , X ) for any finite, non-empty set X ⊆ R d X\subseteq\mathbb{R}^{d} X ⊆ R d .
Let X , Y ⊆ Z d X,Y\subseteq\mathbb{Z}^{d} X , Y ⊆ Z d be finite, non-empty sets. Then we have the trivial bound
E ( X , Y ) ≤ ∣ X ∣ ∣ Y ∣ 2 . (15) E(X,Y)\le|X||Y|^{2}. \tag*{(15)} E ( X , Y ) ≤ ∣ X ∣∣ Y ∣ 2 . (15)
We have the following straightforward upper bounds on mixed additive energies.
Lemma 2.1. Let A , B , C , D A,B,C,D A , B , C , D be finite, non-empty sets in R d \mathbb{R}^{d} R d . Then
∑ a ∈ A ∑ b ∈ B ∑ c ∈ C ∑ d ∈ D 1 a + b = c + d ≤ E ( A , B ) 1 / 2 E ( C , D ) 1 / 2 . \sum_{a\in A}\sum_{b\in B}\sum_{c\in C}\sum_{d\in D}\mathbf{1}_{a+b=c+d}\le E(A,B)^{1/2}E(C,D)^{1/2}. a ∈ A ∑ b ∈ B ∑ c ∈ C ∑ d ∈ D ∑ 1 a + b = c + d ≤ E ( A , B ) 1/2 E ( C , D ) 1/2 .
Proof. For any x ∈ R d x \in\mathbb{R}^{d} x ∈ R d , let
r ( x ) = ∑ a ∈ A ∑ b ∈ B 1 x = a + b and r ′ ( x ) = ∑ c ∈ C ∑ d ∈ D 1 x = c + d . r(x)=\sum_{a\in A}\sum_{b\in B}\mathbf{1}_{x=a+b}\quad\text{and}\quad r'(x)=\sum_{c\in C}\sum_{d\in D}\mathbf{1}_{x=c+d}. r ( x ) = a ∈ A ∑ b ∈ B ∑ 1 x = a + b and r ′ ( x ) = c ∈ C ∑ d ∈ D ∑ 1 x = c + d .
Applying double-counting and Cauchy’s inequality gives us
∑ a ∈ A ∑ b ∈ B ∑ c ∈ C ∑ d ∈ D 1 a + b = c + d = ∑ x ∈ A + B r ( x ) r ′ ( x ) ≤ ( ∑ x ∈ A + B r ( x ) 2 ) 1 / 2 ( ∑ x ∈ A + B r ′ ( x ) 2 ) 1 / 2 . \sum_{a\in A}\sum_{b\in B}\sum_{c\in C}\sum_{d\in D}\mathbf{1}_{a+b=c+d}=\sum_{x\in A+B}r(x)r'(x)\leq\left(\sum_{x\in A+B}r(x)^2\right)^{1/2}\left(\sum_{x\in A+B}r'(x)^2\right)^{1/2}. a ∈ A ∑ b ∈ B ∑ c ∈ C ∑ d ∈ D ∑ 1 a + b = c + d = x ∈ A + B ∑ r ( x ) r ′ ( x ) ≤ ( x ∈ A + B ∑ r ( x ) 2 ) 1/2 ( x ∈ A + B ∑ r ′ ( x ) 2 ) 1/2 .
Using double-counting again, we see that
∑ x ∈ A + B r ( x ) 2 = E ( A , B ) and ∑ x ∈ A + B r ′ ( x ) 2 ≤ E ( C , D ) , \sum_{x\in A+B}r(x)^2=E(A,B)\quad\text{and}\quad\sum_{x\in A+B}r'(x)^2\leq E(C,D), x ∈ A + B ∑ r ( x ) 2 = E ( A , B ) and x ∈ A + B ∑ r ′ ( x ) 2 ≤ E ( C , D ) ,
and so we are done. □
We will use the above lemma multiple times in our paper. For example, this immediately delivers the following result.
Lemma 2.2. Let X 1 , X 2 ⊆ R d X_1,X_2\subseteq\mathbb{R}^{d} X 1 , X 2 ⊆ R d be finite, disjoint sets, let X = X 1 ⊔ X 2 X=X_1\sqcup X_2 X = X 1 ⊔ X 2 and let Y ⊆ R d Y\subseteq\mathbb{R}^{d} Y ⊆ R d be a finite, non-empty set. Then
E ( X , Y ) ≤ 2 E ( X 1 , Y ) + 2 E ( X 2 , Y ) . (16) E(X,Y)\leq2E(X_1,Y)+2E(X_2,Y). \tag*{(16)} E ( X , Y ) ≤ 2 E ( X 1 , Y ) + 2 E ( X 2 , Y ) . (16) Proof. Note that
E ( X , Y ) = E ( X 1 , Y ) + E ( X 2 , Y ) + 2 ∑ x ∈ X 1 ∑ x ′ ∈ X 2 ∑ y 1 , y 2 ∈ Y 1 x + y 1 = x ′ + y 2 . E(X,Y)=E(X_1,Y)+E(X_2,Y)+2\sum_{x\in X_1}\sum_{x'\in X_2}\sum_{y_1,y_2\in Y}\mathbf{1}_{x+y_1=x'+y_2}. E ( X , Y ) = E ( X 1 , Y ) + E ( X 2 , Y ) + 2 x ∈ X 1 ∑ x ′ ∈ X 2 ∑ y 1 , y 2 ∈ Y ∑ 1 x + y 1 = x ′ + y 2 . Lemma 2.1 and the AM–GM inequality imply that the last term on the right-hand side above can be bounded above by
2 E ( X 1 , Y ) 1 / 2 E ( X 2 , Y ) 1 / 2 ≤ E ( X 1 , Y ) + E ( X 2 , Y ) . 2E(X_1,Y)^{1/2}E(X_2,Y)^{1/2}\leq E(X_1,Y)+E(X_2,Y). 2 E ( X 1 , Y ) 1/2 E ( X 2 , Y ) 1/2 ≤ E ( X 1 , Y ) + E ( X 2 , Y ) . This concludes the proof of Lemma 2.2. □
Let us now consider a slightly more general setting which arises in the proof of Theorem 1.3. Suppose X , S X,S X , S are some finite, non-empty sets in R d \mathbb{R}^{d} R d and f : X → [ 0 , ∞ ) f:X\to[0,\infty) f : X → [ 0 , ∞ ) is a function and k ≥ 1 k\geq1 k ≥ 1 is an integer. Define
E k = ∑ x 1 , x 2 ∈ X ∑ s 1 , … , s 2 k ∈ S f ( x 1 ) f ( x 2 ) 1 x 1 − x 2 = s 1 − s 2 + ⋯ + s 2 k − 1 − s 2 k and E 0 = ∑ x ∈ X f ( x ) 2 . (17) E_k=\sum_{x_1,x_2\in X}\sum_{s_1,\ldots,s_{2k}\in S}f(x_1)f(x_2)\mathbf{1}_{x_1-x_2=s_1-s_2+\cdots+s_{2k-1}-s_{2k}}\quad\text{and}\quad E_0=\sum_{x\in X}f(x)^2. \tag*{(17)} E k = x 1 , x 2 ∈ X ∑ s 1 , … , s 2 k ∈ S ∑ f ( x 1 ) f ( x 2 ) 1 x 1 − x 2 = s 1 − s 2 + ⋯ + s 2 k − 1 − s 2 k and E 0 = x ∈ X ∑ f ( x ) 2 . (17)
We will often be interested in bounding E r E_r E r in terms of E k E_k E k for some k ≥ r ≥ 0 k \ge r \ge0 k ≥ r ≥ 0 . When the set X X X is contained in Z d \mathbb{Z}^d Z d , this can be done in a straightforward manner by using orthogonality to pass to Fourier space and applying Hölder’s inequality there. This can then be extended to sets X ⊂ R d X \subset\mathbb{R}^d X ⊂ R d by using the theory of Freiman isomorphisms. This leads to the following result.
Lemma 2.4. For any r ≥ 1 r \ge1 r ≥ 1 and any 0 ≤ k ≤ r 0 \le k \le r 0 ≤ k ≤ r , we have
E k ≤ E 0 1 − k / r E r k / r . E_k \le E_0^{1-k/r} E_r^{k/r}. E k ≤ E 0 1 − k / r E r k / r .
Instead of using Fourier analysis, we will describe an alternative proof of Lemma 2.4 which proceeds purely combinatorially.
Proof of Lemma 2.4. We may assume f f f does not vanish everywhere on X X X since otherwise the result is trivial. This means that E 0 = ∑ x ∈ X ∣ f ( x ) ∣ 2 > 0 E_0 = \sum_{x \in X} \lvert f(x)\rvert^2 > 0 E 0 = ∑ x ∈ X ∣ f ( x ) ∣ 2 > 0 . Moreover, one can check that E k ≥ ∑ x ∈ X ∣ f ( x ) ∣ 2 ∣ S ∣ k > 0 E_k \ge\sum_{x \in X} \lvert f(x)\rvert^2 \lvert S\rvert^k > 0 E k ≥ ∑ x ∈ X ∣ f ( x ) ∣ 2 ∣ S ∣ k > 0 for every k ≥ 1 k \ge1 k ≥ 1 by simply considering solutions satisfying x 1 = x 2 x_1=x_2 x 1 = x 2 and s 2 i − 1 = s 2 i s_{2i-1}=s_{2i} s 2 i − 1 = s 2 i for all 1 ≤ i ≤ k 1 \le i \le k 1 ≤ i ≤ k . For any j ∈ Z ≥ 0 j \in\mathbb{Z}_{\ge0} j ∈ Z ≥ 0 and y ∈ R d y \in\mathbb{R}^d y ∈ R d , define
r j ( y ) = ∑ x ∈ X ∑ s 1 , … , s j ∈ S f ( x ) 1 y = x + s 1 + ⋯ + s j and r j ′ ( y ) = ∑ x ∈ X ∑ s 1 , … , s j ∈ S f ( x ) 1 y = x + s 1 + ⋯ + s j − 1 − s j . r_j(y)=\sum_{x\in X}\sum_{s_1,\ldots,s_j\in S} f(x)\mathbf{1}_{y=x+s_1+\cdots+s_j}
\quad\text{and}\quad
r'_j(y)=\sum_{x\in X}\sum_{s_1,\ldots,s_j\in S} f(x)\mathbf{1}_{y=x+s_1+\cdots+s_{j-1}-s_j}. r j ( y ) = x ∈ X ∑ s 1 , … , s j ∈ S ∑ f ( x ) 1 y = x + s 1 + ⋯ + s j and r j ′ ( y ) = x ∈ X ∑ s 1 , … , s j ∈ S ∑ f ( x ) 1 y = x + s 1 + ⋯ + s j − 1 − s j .
For any positive integer j j j , double-counting gives us
E j = ∑ y ∈ R d r j ( y ) 2 = ∑ y ∈ R d r j ′ ( y ) 2 = ∑ z ∈ R d r j + 1 ′ ( z ) r j − 1 ′ ( z ) . E_j=\sum_{y\in\mathbb{R}^d}r_j(y)^2=\sum_{y\in\mathbb{R}^d}r'_j(y)^2=\sum_{z\in\mathbb{R}^d}r'_{j+1}(z)r'_{j-1}(z). E j = y ∈ R d ∑ r j ( y ) 2 = y ∈ R d ∑ r j ′ ( y ) 2 = z ∈ R d ∑ r j + 1 ′ ( z ) r j − 1 ′ ( z ) .
Applying Cauchy’s inequality and double-counting, we get that
E j ≤ E j + 1 1 / 2 E j − 1 1 / 2 . (18) E_j\le E_{j+1}^{1/2}E_{j-1}^{1/2}. \tag*{(18)} E j ≤ E j + 1 1/2 E j − 1 1/2 . (18)
Now, for any 0 ≤ j ≤ r 0 \le j \le r 0 ≤ j ≤ r , let a j = log E j a_j=\log E_j a j = log E j and for any 1 ≤ j ≤ r 1 \le j \le r 1 ≤ j ≤ r , let Δ j = a j − a j + 1 \Delta_j=a_j-a_{j+1} Δ j = a j − a j + 1 . The bound (18) is equivalent to writing Δ j ≤ Δ j + 1 \Delta_j\le\Delta_{j+1} Δ j ≤ Δ j + 1 for any 1 ≤ j ≤ r 1\le j\le r 1 ≤ j ≤ r . This means that for any 1 ≤ k ≤ r 1\le k\le r 1 ≤ k ≤ r , one has
k − 1 ∑ i = 1 k Δ i ≤ r − 1 ∑ i = 1 r Δ i . k^{-1}\sum_{i=1}^{k}\Delta_i\le r^{-1}\sum_{i=1}^{r}\Delta_i. k − 1 i = 1 ∑ k Δ i ≤ r − 1 i = 1 ∑ r Δ i .
Simplifying, we get that ( a k − a 0 ) / k ≤ ( a r − a 0 ) / r (a_k-a_0)/k\le(a_r-a_0)/r ( a k − a 0 ) / k ≤ ( a r − a 0 ) / r , that is,
a k ≤ a r ( k / r ) + a 0 ( 1 − k / r ) . a_k\le a_r(k/r)+a_0(1-k/r). a k ≤ a r ( k / r ) + a 0 ( 1 − k / r ) .
This is precisely the desired bound. □
Remark 2.5. This proof is reminiscent of the ideas described in [19 ] , and in fact, Lemma 2.4 follows from [19 Theorem 1.1] . Variations of this type of idea, when k = 1 k=1 k = 1 and r = 2 l r=2^l r = 2 l for some l ∈ N l\in\mathbb{N} l ∈ N , have also been used in the proof of the asymmetric Balog–Szemerédi–Gowers theorem, see [27 Lemma 42] .
In our proof of Theorem 1.1 , we will find it useful to pass from an upper bound on the additive energy between two sets X X X and Y Y Y to an upper bound on E ( X , Y ′ ) E(X,Y') E ( X , Y ′ ) where Y ′ Y' Y ′ is a small set sampled from Y Y Y . If Y ′ Y' Y ′ is obtained by taking s s s elements of Y Y Y uniformly at random, it is not too hard to upper-bound the expected value of E ( X , Y ′ ) E(X,Y') E ( X , Y ′ ) in terms of E ( X , Y ) E(X,Y) E ( X , Y ) . We require a slight generalization of such a statement where the elements of Y ′ Y' Y ′ are not too correlated.
Lemma 2.6 (Subsampling). Let D \mathcal{D} D be a probability distribution on tuples ( y 1 , … , y s ) (y_1,\ldots,y_s) ( y 1 , … , y s ) of distinct elements of Y Y Y . Suppose that, for each $1 \leq i < j \leq s$, the marginal distribution of the pair ( y i , y j ) (y_i,y_j) ( y i , y j ) has maximum point probability at most C / ∣ Y ∣ 2 C/|Y|^2 C /∣ Y ∣ 2 for some parameter C > 0 C > 0 C > 0 . Then
E ( y 1 , … , y s ) ∼ D E ( X , { y 1 , … , y s } ) ≤ s ∣ X ∣ + C s 2 ∣ Y ∣ 2 E ( X , Y ) . \underset{(y_1,\ldots,y_s)\sim\mathcal{D}}{\mathbb{E}} E(X,\{y_1,\ldots,y_s\}) \leq s|X|+\frac{Cs^2}{|Y|^2}E(X,Y). ( y 1 , … , y s ) ∼ D E E ( X , { y 1 , … , y s }) ≤ s ∣ X ∣ + ∣ Y ∣ 2 C s 2 E ( X , Y ) .
Proof. We have
E ( X , { y 1 , … , y s } ) = s ∣ X ∣ + 2 ∑ 1 ≤ i < j ≤ s ( 1 X ∗ 1 − X ) ( y i − y j ) . E(X,\{y_1,\ldots,y_s\})=s|X|+2\sum_{1\leq i<j\leq s}(\mathbf{1}_X * \mathbf{1}_{-X})(y_i-y_j). E ( X , { y 1 , … , y s }) = s ∣ X ∣ + 2 1 ≤ i < j ≤ s ∑ ( 1 X ∗ 1 − X ) ( y i − y j ) .
Our assumption on the point probabilities of pairs ( y i , y j ) (y_i,y_j) ( y i , y j ) implies that, for i ≠ j i\ne j i = j ,
E ( y 1 , … , y s ) ∼ D ( 1 X ∗ 1 − X ) ( y i − y j ) = ∑ z 1 , z 2 ∈ Y Pr [ ( y i , y j ) = ( z 1 , z 2 ) ] ( 1 X ∗ 1 − X ) ( z 1 − z 2 ) ≤ C ∣ Y ∣ 2 ∑ z 1 , z 2 ∈ Y ( 1 X ∗ 1 − X ) ( z 1 − z 2 ) = C ∣ Y ∣ 2 E ( X , Y ) . \begin{aligned}
\underset{(y_1,\ldots,y_s)\sim\mathcal{D}}{\mathbb{E}}(\mathbf{1}_X * \mathbf{1}_{-X})(y_i-y_j)
=\sum_{z_1,z_2\in Y}\Pr[(y_i,y_j)=(z_1,z_2)](\mathbf{1}_X * \mathbf{1}_{-X})(z_1-z_2) \\
&\leq\frac{C}{|Y|^2}\sum_{z_1,z_2\in Y}(\mathbf{1}_X * \mathbf{1}_{-X})(z_1-z_2)
=\frac{C}{|Y|^2}E(X,Y).
\end{aligned} ( y 1 , … , y s ) ∼ D E ( 1 X ∗ 1 − X ) ( y i − y j ) = z 1 , z 2 ∈ Y ∑ Pr [( y i , y j ) = ( z 1 , z 2 )] ( 1 X ∗ 1 − X ) ( z 1 − z 2 ) ≤ ∣ Y ∣ 2 C z 1 , z 2 ∈ Y ∑ ( 1 X ∗ 1 − X ) ( z 1 − z 2 ) = ∣ Y ∣ 2 C E ( X , Y ) .
The claimed bound follows. □ \square □
We will need the following quantitative version of the Balog–Szemerédi–Gowers theorem due to Reiher–Schoen [23 Theorem 1.2] . For our application, the quality of the upper bound on ∣ A ′ − A ′ ∣ |A' - A'| ∣ A ′ − A ′ ∣ is not so important, but it is crucial to have a bound of the form ∣ A ′ ∣ ≫ δ c ∣ A ∣ |A'| \gg\delta^c|A| ∣ A ′ ∣ ≫ δ c ∣ A ∣ for some c < 1 c < 1 c < 1 .
Theorem 2.7. Let A A A be a finite nonempty subset of an abelian group and let δ > 0 \delta> 0 δ > 0 . Suppose that E ( A , A ) ≥ δ ∣ A ∣ 3 E(A,A) \geq\delta|A|^3 E ( A , A ) ≥ δ ∣ A ∣ 3 . Then there exists some subset A ′ ⊆ A A' \subseteq A A ′ ⊆ A for which
∣ A ′ ∣ ≫ δ 1 / 2 ∣ A ∣ and ∣ A ′ − A ′ ∣ ≪ δ − 4 ∣ A ′ ∣ . |A'| \gg\delta^{1/2}|A| \quad\text{and}\quad|A'-A'| \ll\delta^{-4}|A'|. ∣ A ′ ∣ ≫ δ 1/2 ∣ A ∣ and ∣ A ′ − A ′ ∣ ≪ δ − 4 ∣ A ′ ∣.
We will also need a structure theorem for sets with small doubling in R d \mathbb{R}^d R d . In particular, the following can be deduced by combining the resolution of the weak polynomial Freiman–Ruzsa conjecture due to Gowers–Green–Manners–Tao [10 Theorem 1.3] along with a standard application of the Plünnecke–Ruzsa inequality and Ruzsa’s covering lemma.
Theorem 2.8. There exists an absolute constant C > 0 C > 0 C > 0 such that for every d ∈ N d \in\mathbb{N} d ∈ N , any finite, non-empty A ⊂ R d A \subset\mathbb{R}^d A ⊂ R d satisfying ∣ A − A ∣ ≤ K ∣ A ∣ |A-A| \leq K|A| ∣ A − A ∣ ≤ K ∣ A ∣ , for some K ≥ 1 K \geq1 K ≥ 1 , is contained within K C K^C K C translates of some vector space of dimension at most C log K C\log K C log K .
Proof. By the Plünnecke–Ruzsa inequality, we have ∣ A + A ∣ ≤ K 2 ∣ A ∣ |A+A| \leq K^2|A| ∣ A + A ∣ ≤ K 2 ∣ A ∣ . The abelian group ⟨ A ⟩ \langle A\rangle ⟨ A ⟩ generated by A A A is finitely generated and torsion-free, and so it is isomorphic to Z n \mathbb{Z}^n Z n for some positive integer n n n . [10 Theorem 1.3] implies that there is some A ′ ⊂ A A' \subset A A ′ ⊂ A with ∣ A ′ ∣ ≥ K − C 1 ∣ A ∣ |A'| \geq K^{-C_1}|A| ∣ A ′ ∣ ≥ K − C 1 ∣ A ∣ and with affine span in Z n \mathbb{Z}^n Z n of dimension at most 2 C 2 log K 2C_2\log K 2 C 2 log K , where C 1 C_1 C 1 and C 2 C_2 C 2 are absolute constants (the same as those in [10 Theorem 1.3] ).
We claim that the dimension of the affine span of A ′ A' A ′ in R d \mathbb{R}^d R d is at most that in Z n \mathbb{Z}^n Z n . Indeed, the statement that A ′ A' A ′ has affine span in Z n \mathbb{Z}^n Z n of dimension D ≤ 2 C 2 log K D \leq2C_2\log K D ≤ 2 C 2 log K implies that, if a 1 , … , a D + 2 ∈ A ′ a_1,\ldots,a_{D+2}\in A' a 1 , … , a D + 2 ∈ A ′ , then there exist c 1 , … , c D + 2 ∈ Q c_1,\ldots,c_{D+2}\in\mathbb{Q} c 1 , … , c D + 2 ∈ Q , not all zero but summing to zero, for which
c 1 a 1 + ⋯ + c D + 2 a D + 2 = 0 (19) c_1a_1+\cdots+c_{D+2}a_{D+2}=0 \tag*{(19)} c 1 a 1 + ⋯ + c D + 2 a D + 2 = 0 (19)
Scaling up, we can take c 1 , … , c D + 2 ∈ Z c_1,\ldots,c_{D+2} \in\mathbb{Z} c 1 , … , c D + 2 ∈ Z and interpret (2.5) in R d \mathbb{R}^d R d . From here, we obtain that the affine span of A ′ A' A ′ in R d \mathbb{R}^d R d has dimension at most D D D .
Finally, let V V V be the subspace of R d \mathbb{R}^d R d spanned by A ′ − A ′ A'-A' A ′ − A ′ . The desired result now follows from Ruzsa’s covering lemma: since ∣ A + A ′ ∣ ≤ ∣ A + A ∣ ≤ K 2 ∣ A ∣ ≤ K C 1 + 2 ∣ A ′ ∣ |A+A'| \leq|A+A| \leq K^2|A| \leq K^{C_1+2}|A'| ∣ A + A ′ ∣ ≤ ∣ A + A ∣ ≤ K 2 ∣ A ∣ ≤ K C 1 + 2 ∣ A ′ ∣ , the set A A A can be covered by at most K C 1 + 2 K^{C_1+2} K C 1 + 2 translates of A ′ − A ′ ⊂ V A'-A' \subset V A ′ − A ′ ⊂ V . □
Proof of Theorem 1.1
In this section, we prove Theorem 1.1 assuming Theorem 1.3. The first step is to find a decomposition of our set A A A into two pieces, one of which is structured and the other of which is either small or not too structured. For this purpose, we will find the following notation useful: given a non-empty set S ⊆ R d S \subseteq\mathbb{R}^d S ⊆ R d and some subspace V V V of R d \mathbb{R}^d R d , we denote by S / V S/V S / V the image π ( S ) \pi(S) π ( S ) of S S S under the canonical projection map π : R d → R d / V \pi:\mathbb{R}^d \to\mathbb{R}^d/V π : R d → R d / V .
Lemma 3.1. Suppose d d d is sufficiently large. Set ε : = d − 1 / 10 \varepsilon:= d^{-1/10} ε := d − 1/10 and δ : = d − 3 / 2 \delta:= d^{-3/2} δ := d − 3/2 . Then any finite set A ⊂ R d A \subset\mathbb{R}^d A ⊂ R d with dim ( A ) = d \dim(A)=d dim ( A ) = d can be decomposed into two sets A s t r ⊔ A u n s t r A_{\mathrm{str}} \sqcup A_{\mathrm{unstr}} A str ⊔ A unstr such that the following two properties hold:
The set A s t r A_{\mathrm{str}} A str is contained within the union of d O ( 1 ) d^{O(1)} d O ( 1 ) -many translates of some subspace V ⊂ R d V \subset\mathbb{R}^d V ⊂ R d of dimension at most d / 2 d/2 d /2 .
The set A u n s t r A_{\mathrm{unstr}} A unstr either satisfies ∣ A u n s t r ∣ ≤ 1 4 ∣ A ∣ |A_{\mathrm{unstr}}| \leq\frac{1}{4}|A| ∣ A unstr ∣ ≤ 4 1 ∣ A ∣ , or else satisfies both (i) that E ( A u n s t r ) < δ ∣ A u n s t r ∣ 3 E(A_{\mathrm{unstr}}) < \delta|A_{\mathrm{unstr}}|^3 E ( A unstr ) < δ ∣ A unstr ∣ 3 and (ii) that, for any subspace V ⊂ V ′ ⊂ R d V \subset V' \subset\mathbb{R}^d V ⊂ V ′ ⊂ R d with dim ( V ′ / V ) ≤ d / 100 \dim(V'/V) \leq d/100 dim ( V ′ / V ) ≤ d /100 and any x ∈ R d x \in\mathbb{R}^d x ∈ R d , we have
∣ A u n s t r ∩ ( x + V ′ ) ∣ < ( 1 − ε ) ∣ A u n s t r ∣ . (20) |A_{\mathrm{unstr}} \cap(x+V')| < (1-\varepsilon)|A_{\mathrm{unstr}}|. \tag*{(20)} ∣ A unstr ∩ ( x + V ′ ) ∣ < ( 1 − ε ) ∣ A unstr ∣. (20)
Proof. We will construct our decomposition iteratively. Initially, set A 1 = ∅ A_1=\varnothing A 1 = ∅ and B 1 = A B_1=A B 1 = A and V 1 = { 0 } V_1=\{0\} V 1 = { 0 } and ρ 1 = ∣ B 1 ∣ / ∣ A ∣ = 1 \rho_1=|B_1|/|A|=1 ρ 1 = ∣ B 1 ∣/∣ A ∣ = 1 . At the beginning of the i t h i^{\mathrm{th}} i th step of the procedure, for any integer i ≥ 1 i \geq1 i ≥ 1 , we will have disjoint sets A i A_i A i and B i B_i B i such that A = A i ⊔ B i A=A_i \sqcup B_i A = A i ⊔ B i , the parameter ρ i = ∣ B i ∣ / ∣ A ∣ \rho_i=|B_i|/|A| ρ i = ∣ B i ∣/∣ A ∣ and the vector space V i ⊂ R d V_i \subset\mathbb{R}^d V i ⊂ R d . With this in hand, the i t h i^{\mathrm{th}} i th step involves proceeding through the following conditions in order.
If ρ i ≤ 1 / d \rho_i \leq1/d ρ i ≤ 1/ d , terminate the procedure.
If there exists a subset B ′ ⊆ B i B' \subseteq B_i B ′ ⊆ B i such that ∣ B ′ ∣ ≥ ( 1 − ε ) ∣ B i ∣ |B'| \geq(1-\varepsilon)|B_i| ∣ B ′ ∣ ≥ ( 1 − ε ) ∣ B i ∣ and B ′ / V i ⊆ ( x + V ′ ) / V i B'/V_i \subseteq(x+V')/V_i B ′ / V i ⊆ ( x + V ′ ) / V i for some x ∈ R d x \in\mathbb{R}^d x ∈ R d and some subspace V i ⊂ V ′ ⊂ R d V_i \subset V' \subset\mathbb{R}^d V i ⊂ V ′ ⊂ R d satisfying dim V ′ − dim V i ≤ d / 100 \dim V'-\dim V_i \leq d/100 dim V ′ − dim V i ≤ d /100 , update
V i + 1 : = V ′ and A i + 1 : = A i ⊔ ( B i ∩ ( x + V ′ ) ) and B i + 1 : = B i ∖ ( B i ∩ ( x + V ′ ) ) . V_{i+1}:=V' \quad\text{and}\quad A_{i+1}:=A_i \sqcup(B_i \cap(x+V')) \quad\text{and}\quad B_{i+1}:=B_i\setminus(B_i\cap(x+V')). V i + 1 := V ′ and A i + 1 := A i ⊔ ( B i ∩ ( x + V ′ )) and B i + 1 := B i ∖ ( B i ∩ ( x + V ′ )) .
In this way, we have ρ i + 1 ≤ ε ρ i \rho_{i+1}\leq\varepsilon\rho_i ρ i + 1 ≤ ε ρ i . Proceed to the ( i + 1 ) t h (i+1)^{\mathrm{th}} ( i + 1 ) th step.
If instead E ( B i , B i ) ≥ δ ∣ B i ∣ 3 E(B_i,B_i)\geq\delta|B_i|^3 E ( B i , B i ) ≥ δ ∣ B i ∣ 3 , apply Theorem 2.7 and then Theorem 2.8 to find some subset T ⊂ B i T\subset B_i T ⊂ B i for which ∣ T ∣ ≥ c δ 1 / 2 ∣ B i ∣ |T|\geq c\delta^{1/2}|B_i| ∣ T ∣ ≥ c δ 1/2 ∣ B i ∣ and which may be covered by δ − C ′ \delta^{-C'} δ − C ′ translates of some vector space W W W of dimension at most C ′ log ( 1 / δ ) C'\log(1/\delta) C ′ log ( 1/ δ ) , where c , C ′ > 0 c,C'>0 c , C ′ > 0 are constants. Update
V i + 1 = V i + W and A i + 1 = A i ⊔ T and B i + 1 = B i ∖ T . V_{i+1}=V_i+W \quad\text{and}\quad A_{i+1}=A_i\sqcup T \quad\text{and}\quad B_{i+1}=B_i\setminus T. V i + 1 = V i + W and A i + 1 = A i ⊔ T and B i + 1 = B i ∖ T .
In this way, we have ρ i + 1 ≤ ( 1 − c δ 1 / 2 ) ρ i \rho_{i+1}\leq(1-c\delta^{1/2})\rho_i ρ i + 1 ≤ ( 1 − c δ 1/2 ) ρ i . Proceed to the ( i + 1 ) t h (i+1)^{\mathrm{th}} ( i + 1 ) th step.
If neither of the previous steps have been successful, terminate the procedure.
It is simple to check that this procedure can only run for finitely many steps, and so, suppose the above procedure stops after t t t steps, for some t ∈ N t\in\mathbb{N} t ∈ N . The termination condition in event 1 and our choices of ε \varepsilon ε and δ \delta δ imply that event 2 can occur at most 10 times and event 3 can occur at most c − 1 d 3 / 4 / log d c^{-1}d^{3/4}/\log d c − 1 d 3/4 / log d times. We conclude that, at the end of the procedure,
dim V t ≤ d 10 + O ( d 3 / 4 ( log d ) 2 ) ≤ d 2 . \dim V_t \le\frac{d}{10} + O\left(d^{3/4}(\log d)^2\right) \le\frac{d}{2}. dim V t ≤ 10 d + O ( d 3/4 ( log d ) 2 ) ≤ 2 d .
Moreover, at the i i i th step of the procedure, we observe that A i A_i A i is covered by at most i ⋅ d C ′ ′ i \cdot d^{C''} i ⋅ d C ′′ translates of V i V_i V i for some absolute constant C ′ ′ C'' C ′′ . We thus conclude that A t A_t A t is covered by at most d O ( 1 ) d^{O(1)} d O ( 1 ) translates of V t V_t V t . We now set A s t r : = A t A_{\mathrm{str}} := A_t A str := A t and A u n s t r : = B t A_{\mathrm{unstr}} := B_t A unstr := B t and V : = V t V := V_t V := V t to obtain the desired conclusion. □
Next, using Theorem 1.3, we bound the additive energy between A s t r A_{\mathrm{str}} A str and any set which remains affine-independent when quotiented by V V V . We will in fact need the following slight generalization of Theorem 1.3.
Lemma 3.2. Let d , m ∈ N d,m \in\mathbb{N} d , m ∈ N with m ≤ d m \le d m ≤ d . Let S S S be an affine-independent subset of R d \mathbb{R}^d R d , and let f : R d → [ 0 , ∞ ) f:\mathbb{R}^d \to[0,\infty) f : R d → [ 0 , ∞ ) be supported on a finite, non-empty set X ⊆ R d X \subseteq\mathbb{R}^d X ⊆ R d and satisfy ( ∥ f ∥ 1 / ∥ f ∥ 2 ) 2 ≤ ( d m ) (\lVert f\rVert_1/\lVert f\rVert_2)^2 \le\binom{d}{m} (∥ f ∥ 1 / ∥ f ∥ 2 ) 2 ≤ ( m d ) . Then we have
E f ( X , S ) ≪ m d ∥ f ∥ 2 2 . E_f(X,S) \ll md\lVert f\rVert_2^2. E f ( X , S ) ≪ m d ∥ f ∥ 2 2 .
Proof. Since translating S S S does not change E f ( X , S ) E_f(X,S) E f ( X , S ) , we may translate S S S suitably so as to ensure that 0 ∈ S 0 \in S 0 ∈ S . By changing the coordinate frame, we may assume that the other ∣ S ∣ − 1 |S|-1 ∣ S ∣ − 1 elements of S S S are e 1 , … , e j e_1,\ldots,e_j e 1 , … , e j for j = ∣ S ∣ − 1 j=|S|-1 j = ∣ S ∣ − 1 . We conclude from Theorem 1.3 that
E f ( X , S ) ≤ E f ( X , { 0 , e 1 , … , e d } ) ≤ ∑ x ∈ X f ( x ) 2 + 2 ∑ i = 1 d ∑ x ∈ X f ( x ) f ( x + e i ) + E f ( X , { e 1 , … , e d } ) ≪ ( d + 1 + m d ) ∥ f ∥ 2 2 . \begin{aligned}
E_f(X,S) \le E_f(X,\{0,e_1,\ldots,e_d\}) \\
&\le\sum_{x\in X} f(x)^2 + 2\sum_{i=1}^{d}\sum_{x\in X}f(x)f(x+e_i) + E_f(X,\{e_1,\ldots,e_d\}) \\
&\ll(d+1+md)\lVert f\rVert_2^2.
\end{aligned} E f ( X , S ) ≤ E f ( X , { 0 , e 1 , … , e d }) ≤ x ∈ X ∑ f ( x ) 2 + 2 i = 1 ∑ d x ∈ X ∑ f ( x ) f ( x + e i ) + E f ( X , { e 1 , … , e d }) ≪ ( d + 1 + m d ) ∥ f ∥ 2 2 .
We will use this lemma to show that any set S ⊂ R d S \subset\mathbb{R}^d S ⊂ R d with ∣ S ∣ = ∣ S / V ∣ ≫ d |S|=|S/V| \gg d ∣ S ∣ = ∣ S / V ∣ ≫ d and with S / V S/V S / V being affine-independent has little additive interaction with A s t r A_{\mathrm{str}} A str .
Lemma 3.3. Let V V V and A s t r A_{\mathrm{str}} A str be as in the conclusion of Lemma 3.1. Let S S S be any set of size at least d / 100 d/100 d /100 such that S / V S/V S / V is affine-independent and ∣ S ∣ = ∣ S / V ∣ |S|=|S/V| ∣ S ∣ = ∣ S / V ∣ . Then E ( A s t r , S ) ≪ ∣ A ∣ ∣ S ∣ E(A_{\mathrm{str}},S)\ll|A||S| E ( A str , S ) ≪ ∣ A ∣∣ S ∣ .
Proof. Let π : R d → R d / V \pi:\mathbb{R}^d \to\mathbb{R}^d/V π : R d → R d / V be the canonical projection map, let X = π ( A s t r ) X=\pi(A_{\mathrm{str}}) X = π ( A str ) and let S ′ = π ( S ) S'=\pi(S) S ′ = π ( S ) . Condition (1) of Lemma 3.1 implies that ∣ X ∣ ≤ d O ( 1 ) |X|\le d^{O(1)} ∣ X ∣ ≤ d O ( 1 ) . For any x ∈ X x\in X x ∈ X , let A x = A s t r ∩ ( x + V ) A_x=A_{\mathrm{str}}\cap(x+V) A x = A str ∩ ( x + V ) . Note that
E ( A s t r , S ) = ∑ x 1 , x 2 ∈ X ∑ s 1 , s 2 ∈ S ∣ A x 1 ∩ ( A x 2 + s 1 − s 2 ) ∣ ≤ ∑ x 1 , x 2 ∈ X ∑ s 1 , s 2 ∈ S 1 x 1 − x 2 = π ( s 1 ) − π ( s 2 ) ∣ A x 1 ∣ 1 / 2 ∣ A x 2 ∣ 1 / 2 . \begin{aligned}
E(A_{\mathrm{str}},S)=\sum_{x_1,x_2\in X}\sum_{s_1,s_2\in S}|A_{x_1}\cap(A_{x_2}+s_1-s_2)| \\
&\le\sum_{x_1,x_2\in X}\sum_{s_1,s_2\in S}\mathbf{1}_{x_1-x_2=\pi(s_1)-\pi(s_2)}|A_{x_1}|^{1/2}|A_{x_2}|^{1/2}.
\end{aligned} E ( A str , S ) = x 1 , x 2 ∈ X ∑ s 1 , s 2 ∈ S ∑ ∣ A x 1 ∩ ( A x 2 + s 1 − s 2 ) ∣ ≤ x 1 , x 2 ∈ X ∑ s 1 , s 2 ∈ S ∑ 1 x 1 − x 2 = π ( s 1 ) − π ( s 2 ) ∣ A x 1 ∣ 1/2 ∣ A x 2 ∣ 1/2 .
In the second step above, we have used the fact that whenever the set A x 1 ∩ ( A x 2 + s 1 − s 2 ) A_{x_1}\cap(A_{x_2}+s_1-s_2) A x 1 ∩ ( A x 2 + s 1 − s 2 ) is non-empty, we must have x 1 = x 2 + π ( s 1 ) − π ( s 2 ) x_1=x_2+\pi(s_1)-\pi(s_2) x 1 = x 2 + π ( s 1 ) − π ( s 2 ) . Define f : X → [ 0 , ∞ ) f:X\to[0,\infty) f : X → [ 0 , ∞ ) by setting f ( x ) = ∣ A x ∣ 1 / 2 f(x)=|A_x|^{1/2} f ( x ) = ∣ A x ∣ 1/2 for every x ∈ X x\in X x ∈ X . We have the bound
∥ f ∥ 1 2 ∥ f ∥ 2 2 ≤ ∣ X ∣ ≤ d O ( 1 ) ≤ ( dim ( R d / V ) ) O ( 1 ) . \frac{\lVert f\rVert_1^2}{\lVert f\rVert_2^2}\le|X|\le d^{O(1)}\le\left(\dim(\mathbb{R}^d/V)\right)^{O(1)}. ∥ f ∥ 2 2 ∥ f ∥ 1 2 ≤ ∣ X ∣ ≤ d O ( 1 ) ≤ ( dim ( R d / V ) ) O ( 1 ) .
So, we may apply Lemma 3.2 to X , S ′ ⊂ R d / V X, S' \subset\mathbb{R}^d/V X , S ′ ⊂ R d / V with m = O ( 1 ) m=O(1) m = O ( 1 ) to obtain
E ( A s t r , S ) ≤ E f ( X , S ′ ) ≪ ∣ A s t r ∣ ∣ S ′ ∣ = ∣ A s t r ∣ ∣ S ∣ ≤ ∣ A ∣ ∣ S ∣ . E(A_{\mathrm{str}},S) \le E_f(X,S') \ll|A_{\mathrm{str}}||S'| = |A_{\mathrm{str}}||S| \le|A||S|. E ( A str , S ) ≤ E f ( X , S ′ ) ≪ ∣ A str ∣∣ S ′ ∣ = ∣ A str ∣∣ S ∣ ≤ ∣ A ∣∣ S ∣.
Now, we provide a procedure for selecting such a set S S S for which E ( A u n s t r , S ) E(A_{\mathrm{unstr}},S) E ( A unstr , S ) is well-controlled.
Lemma 3.4. Let V V V and A u n s t r A_{\mathrm{unstr}} A unstr be as in Lemma 3.1 . Then there exists a subset S S S of A A A of size at least d / 100 d/100 d /100 such that S / V S/V S / V is affine-independent and ∣ S ∣ = ∣ S / V ∣ |S|=|S/V| ∣ S ∣ = ∣ S / V ∣ and
E ( A u n s t r , S ) ≪ ∣ A ∣ ∣ S ∣ . E(A_{\mathrm{unstr}},S) \ll|A||S|. E ( A unstr , S ) ≪ ∣ A ∣∣ S ∣.
Proof. We first remark that A / V A/V A / V is full-dimensional in R d / V \mathbb{R}^d/V R d / V , and so there exists a subset S ⊆ A S\subseteq A S ⊆ A such that ∣ S ∣ ≥ d / 100 |S|\ge d/100 ∣ S ∣ ≥ d /100 and S / V S/V S / V is affine-independent and ∣ S ∣ = ∣ S / V ∣ |S|=|S/V| ∣ S ∣ = ∣ S / V ∣ . If ∣ A u n s t r ∣ ≤ 1 d ∣ A ∣ |A_{\mathrm{unstr}}|\le\frac{1}{d}|A| ∣ A unstr ∣ ≤ d 1 ∣ A ∣ , then the trivial bound (2.1) implies
E ( A u n s t r , S ) ≤ ∣ A u n s t r ∣ ∣ S ∣ 2 ≪ ∣ A ∣ ∣ S ∣ . E(A_{\mathrm{unstr}},S)\le|A_{\mathrm{unstr}}||S|^2\ll|A||S|. E ( A unstr , S ) ≤ ∣ A unstr ∣∣ S ∣ 2 ≪ ∣ A ∣∣ S ∣.
So, we may henceforth assume that we are in case (2) of Lemma 3.1 .
In this case, we use a randomized procedure to construct such a set S S S , with an aim of applying Lemma 2.6 . For 1 ≤ j ≤ d / 100 1\le j\le d/100 1 ≤ j ≤ d /100 , choose an element y j ∈ A u n s t r y_j\in A_{\mathrm{unstr}} y j ∈ A unstr uniformly at random subject to the condition that the set { y 1 , … , y j } / V \{y_1,\ldots,y_j\}/V { y 1 , … , y j } / V is affine-independent. There are at least ε ∣ A u n s t r ∣ \varepsilon|A_{\mathrm{unstr}}| ε ∣ A unstr ∣ choices for each y j y_j y j : otherwise, the affine-span V ′ V' V ′ of { y 1 , … , y j − 1 } + V \{y_1,\ldots,y_{j-1}\}+V { y 1 , … , y j − 1 } + V would satisfy ∣ V ′ ∩ A u n s t r ∣ ≥ ( 1 − ε ) ∣ A u n s t r ∣ |V'\cap A_{\mathrm{unstr}}|\ge(1-\varepsilon)|A_{\mathrm{unstr}}| ∣ V ′ ∩ A unstr ∣ ≥ ( 1 − ε ) ∣ A unstr ∣ , contradicting (3.1). In particular, given the values of y 1 , … , y j − 1 y_1,\ldots,y_{j-1} y 1 , … , y j − 1 , the maximum point probability of y j y_j y j is at most ε − 1 / ∣ A u n s t r ∣ \varepsilon^{-1}/|A_{\mathrm{unstr}}| ε − 1 /∣ A unstr ∣ . We claim moreover that, for each 1 ≤ i < j ≤ d / 100 1\le i<j\le d/100 1 ≤ i < j ≤ d /100 , the maximum point probability of the pair ( y i , y j ) (y_i,y_j) ( y i , y j ) is at most ε − 2 / ∣ A u n s t r ∣ 2 \varepsilon^{-2}/|A_{\mathrm{unstr}}|^2 ε − 2 /∣ A unstr ∣ 2 . Indeed, for each a 1 , a 2 ∈ A a_1,a_2\in A a 1 , a 2 ∈ A ,
Pr [ y i = a 1 , y j = a 2 ] ≤ max z 1 , … , z i − 1 Pr [ y i = a 1 , y j = a 2 ∣ y 1 = z 1 , … , y i − 1 = z i − 1 ] = max z 1 , … , z i − 1 Pr [ y i = a 1 ∣ y [ 1 , i ) = z [ 1 , i ) ] ⋅ Pr [ y j = a 2 ∣ y [ 1 , i ) = z [ 1 , i ) , y i = a 1 ] ≤ ε − 1 ∣ A u n s t r ∣ ⋅ max z 1 , … , z i − 1 Pr [ y j = a 2 ∣ y [ 1 , i ) = z [ 1 , i ) , y i = a 1 ] ≤ ε − 1 ∣ A u n s t r ∣ ⋅ max z 1 , … , z j − 1 Pr [ y j = a 2 ∣ y [ 1 , i ) = z [ 1 , i ) , y i = a 1 , y ( i , j ) = z ( i , j ) ] ≤ ε − 2 ∣ A u n s t r ∣ 2 , \begin{aligned}
\Pr[y_i=a_1,y_j=a_2]
&\le\max_{z_1,\ldots,z_{i-1}}\Pr[y_i=a_1,y_j=a_2\mid y_1=z_1,\ldots,y_{i-1}=z_{i-1}]\\
&=\max_{z_1,\ldots,z_{i-1}}\Pr[y_i=a_1\mid y_{[1,i)}=z_{[1,i) }]\cdot\Pr[y_j=a_2\mid y_{[1,i)}=z_{[1,i)},y_i=a_1]\\
&\le\frac{\varepsilon^{-1}}{|A_{\mathrm{unstr}}|}\cdot\max_{z_1,\ldots,z_{i-1}}\Pr[y_j=a_2\mid y_{[1,i)}=z_{[1,i)},y_i=a_1]\\
&\le\frac{\varepsilon^{-1}}{|A_{\mathrm{unstr}}|}\cdot\max_{z_1,\ldots,z_{j-1}}\Pr[y_j=a_2\mid y_{[1,i)}=z_{[1,i)},y_i=a_1,y_{(i,j)}=z_{(i,j)}]\\
&\le\frac{\varepsilon^{-2}}{|A_{\mathrm{unstr}}|^2},
\end{aligned} Pr [ y i = a 1 , y j = a 2 ] ≤ z 1 , … , z i − 1 max Pr [ y i = a 1 , y j = a 2 ∣ y 1 = z 1 , … , y i − 1 = z i − 1 ] = z 1 , … , z i − 1 max Pr [ y i = a 1 ∣ y [ 1 , i ) = z [ 1 , i ) ] ⋅ Pr [ y j = a 2 ∣ y [ 1 , i ) = z [ 1 , i ) , y i = a 1 ] ≤ ∣ A unstr ∣ ε − 1 ⋅ z 1 , … , z i − 1 max Pr [ y j = a 2 ∣ y [ 1 , i ) = z [ 1 , i ) , y i = a 1 ] ≤ ∣ A unstr ∣ ε − 1 ⋅ z 1 , … , z j − 1 max Pr [ y j = a 2 ∣ y [ 1 , i ) = z [ 1 , i ) , y i = a 1 , y ( i , j ) = z ( i , j ) ] ≤ ∣ A unstr ∣ 2 ε − 2 ,
where we have used notation like y [ 1 , i ) y_{[1,i)} y [ 1 , i ) as shorthand for the tuple ( y 1 , … , y i − 1 ) (y_1,\ldots,y_{i-1}) ( y 1 , … , y i − 1 ) . Therefore, letting S = { y 1 , … , y ⌊ d / 100 ⌋ } S=\{y_1,\ldots,y_{\lfloor d/100\rfloor}\} S = { y 1 , … , y ⌊ d /100 ⌋ } , we may apply Lemma 2.6 to deduce that
E E ( A u n s t r , S ) ≤ ∣ A u n s t r ∣ ∣ S ∣ + ε − 2 ( d / 100 ) 2 ∣ A u n s t r ∣ 2 E ( A u n s t r ) ≪ ∣ A ∣ ∣ S ∣ + ε − 2 d 2 δ ∣ A u n s t r ∣ ≪ ∣ A ∣ ∣ S ∣ . \mathbb{E}E(A_{\mathrm{unstr}},S)\le|A_{\mathrm{unstr}}||S|+\frac{\varepsilon^{-2}(d/100)^2}{|A_{\mathrm{unstr}}|^2}E(A_{\mathrm{unstr}})\ll|A||S|+\varepsilon^{-2}d^2\delta|A_{\mathrm{unstr}}|\ll|A||S|. E E ( A unstr , S ) ≤ ∣ A unstr ∣∣ S ∣ + ∣ A unstr ∣ 2 ε − 2 ( d /100 ) 2 E ( A unstr ) ≪ ∣ A ∣∣ S ∣ + ε − 2 d 2 δ ∣ A unstr ∣ ≪ ∣ A ∣∣ S ∣.
This means that there must exist some set S ⊆ A u n s t r S\subseteq A_{\mathrm{unstr}} S ⊆ A unstr satisfying the conclusion of Lemma 3.4 , and so, we are done. □ \square □
Theorem 1.1 follows from combining Lemmas 3.1 , 3.3 and 3.4 with (2.2).
The edge-isoperimetric problem over the Boolean cube
In this section, we present our proof of Theorem 1.4. So that we can use additive notation, we identify the vertices of the hypercube with ( Z / 2 Z ) d (\mathbb{Z}/2\mathbb{Z})^d ( Z /2 Z ) d . To avoid ambiguity with Z d \mathbb{Z}^d Z d or R d \mathbb{R}^d R d , we write e i ′ ∈ ( Z / 2 Z ) d e_i' \in(\mathbb{Z}/2\mathbb{Z})^d e i ′ ∈ ( Z /2 Z ) d for the vector with a 1 in coordinate i i i and zeros in other coordinates. In particular, { e 1 ′ , … , e d ′ } \{e_1',\ldots,e_d'\} { e 1 ′ , … , e d ′ } forms a basis for ( Z / 2 Z ) d (\mathbb{Z}/2\mathbb{Z})^d ( Z /2 Z ) d . Moreover, two vertices x 1 , x 2 ∈ ( Z / 2 Z ) d x_1,x_2 \in(\mathbb{Z}/2\mathbb{Z})^d x 1 , x 2 ∈ ( Z /2 Z ) d have Hamming distance 2 if and only if their difference x 1 − x 2 x_1-x_2 x 1 − x 2 can be written as e i ′ + e j ′ e_i'+e_j' e i ′ + e j ′ for some distinct 1 ≤ i , j ≤ d 1\le i,j\le d 1 ≤ i , j ≤ d . This observation immediately delivers the bound
T ( X ) ≤ ∣ X ∣ ( d 2 ) . (21) T(X) \le|X| \binom{d}{2}. \tag*{(21)} T ( X ) ≤ ∣ X ∣ ( 2 d ) . (21)
We are now ready to present our proof of Theorem 1.4.
Proof of Theorem 1.4. Let G G G be the graph with vertex set X X X where vertices x 1 x_1 x 1 and x 2 x_2 x 2 are joined by an edge if x 1 − x 2 = e i ′ + e j ′ x_1-x_2=e_i'+e_j' x 1 − x 2 = e i ′ + e j ′ for some distinct i , j ∈ { 1 , … , d } i,j\in\{1,\ldots,d\} i , j ∈ { 1 , … , d } . Two edges with increments e i ′ + e j ′ e_i'+e_j' e i ′ + e j ′ and e k ′ + e ℓ ′ e_k'+e_\ell' e k ′ + e ℓ ′ are said to conflict if { i , j } ∩ { k , ℓ } \{i,j\}\cap\{k,\ell\} { i , j } ∩ { k , ℓ } is nonempty. We call a subset of the edge set of G G G non-conflicting if no two edges in the subset conflict. The number of edges of G G G is T ( X ) / 2 T(X)/2 T ( X ) /2 , so the average degree L L L of G G G satisfies L = T ( X ) / ∣ X ∣ L=T(X)/|X| L = T ( X ) /∣ X ∣ . We may assume for the sake of contradiction that L ≥ 4 m d L\ge4md L ≥ 4 m d .
Let X ′ ⊂ X X'\subset X X ′ ⊂ X be a subset such that the induced subgraph G ′ : = G [ X ′ ] G':=G[X'] G ′ := G [ X ′ ] has minimum degree exceeding L / 2 L/2 L /2 . Such a subset can be found by repeatedly removing vertices of degree at most L / 2 L/2 L /2 until none remain; each removal does not decrease the average degree, so this process terminates in a nonempty graph. Let P P P be the number of paths of length m m m consisting of non-conflicting edges in G ′ G' G ′ . Our desired bound will follow from obtaining suitable upper and lower bounds for P P P .
For the upper bound, note that between any two distinct vertices x x x and y y y in G ′ G' G ′ , there are at most ( 2 m ) ! / 2 m (2m)!/2^m ( 2 m )! / 2 m non-conflicting paths. Indeed, if there is any such path, then we can write
x − y = e i 1 ′ + e j 1 ′ + ⋯ + e i m ′ + e j m ′ x-y=e_{i_1}'+e_{j_1}'+\cdots+e_{i_m}'+e_{j_m}' x − y = e i 1 ′ + e j 1 ′ + ⋯ + e i m ′ + e j m ′
for some distinct i 1 , j 1 , … , i m , j m ∈ { 1 , … , d } i_1,j_1,\ldots,i_m,j_m\in\{1,\ldots,d\} i 1 , j 1 , … , i m , j m ∈ { 1 , … , d } . Since the set { e 1 ′ , … , e d ′ } \{e_1',\ldots,e_d'\} { e 1 ′ , … , e d ′ } is linearly independent, such a representation is unique up to permutation of { i 1 , j 1 , … , i m , j m } \{i_1,j_1,\ldots,i_m,j_m\} { i 1 , j 1 , … , i m , j m } . The factor of 2 − m 2^{-m} 2 − m comes from the fact that swapping i k i_k i k and j k j_k j k does not change the path. We thus conclude that
P ≤ ( 2 m ) ! 2 m ∣ X ′ ∣ 2 . (22) P\le\frac{(2m)!}{2^m}|X'|^2. \tag*{(22)} P ≤ 2 m ( 2 m )! ∣ X ′ ∣ 2 . (22)
On the other hand, given a non-conflicting path consisting of edges
{ ( x 0 , x 1 ) , ( x 1 , x 2 ) , … , ( x t − 1 , x t ) } , \{(x_0,x_1),(x_1,x_2),\ldots,(x_{t-1},x_t)\}, {( x 0 , x 1 ) , ( x 1 , x 2 ) , … , ( x t − 1 , x t )} ,
there are at most 2 d t 2dt 2 d t edges out of x t x_t x t which conflict with some edge previously in the path. Indeed, at most 2 d 2d 2 d putative new edges e k ′ + e ℓ ′ e_k'+e_\ell' e k ′ + e ℓ ′ conflict with each previous e i r ′ + e j r ′ e_{i_r}'+e_{j_r}' e i r ′ + e j r ′ , as at most 2 d 2d 2 d subsets { k , ℓ } ⊂ { 1 , … , d } \{k,\ell\}\subset\{1,\ldots,d\} { k , ℓ } ⊂ { 1 , … , d } of size 2 intersect { i r , j r } \{i_r,j_r\} { i r , j r } . Thus, given any x ∈ X ′ x\in X' x ∈ X ′ , there are at least
∏ r = 0 m − 1 ( L 2 − 2 d r ) ≥ ∏ r = 0 m − 1 ( 2 d ( m − r ) ) = ( 2 d ) m m ! \prod_{r=0}^{m-1}\left(\frac{L}{2}-2dr\right)\ge\prod_{r=0}^{m-1}(2d(m-r))=(2d)^m m! r = 0 ∏ m − 1 ( 2 L − 2 d r ) ≥ r = 0 ∏ m − 1 ( 2 d ( m − r )) = ( 2 d ) m m !
non-conflicting paths starting from the vertex x x x . We conclude
P ≥ ( 2 d ) m m ! ∣ X ′ ∣ . (23) P\ge(2d)^m m!|X'|. \tag*{(23)} P ≥ ( 2 d ) m m ! ∣ X ′ ∣. (23)
Combining (22) and (23) gives
∣ X ′ ∣ ≥ 2 m ( 2 d ) m m ! ( 2 m ) ! = 4 m ( 2 m m ) ⋅ d m m ! > ( d m ) . |X'| \ge\frac{2^m(2d)^m m!}{(2m)!} = \frac{4^m}{\binom{2m}{m}} \cdot\frac{d^m}{m!} > \binom{d}{m}. ∣ X ′ ∣ ≥ ( 2 m )! 2 m ( 2 d ) m m ! = ( m 2 m ) 4 m ⋅ m ! d m > ( m d ) .
This contradicts the fact that ∣ X ′ ∣ ≤ ∣ X ∣ ≤ ( d m ) |X'| \le|X| \le\binom{d}{m} ∣ X ′ ∣ ≤ ∣ X ∣ ≤ ( m d ) , and so we are done. □
Remark 4.1. For m ≫ d m \gg d m ≫ d , our proof of Theorem 1.4 can be pushed slightly further. Namely, the upper bound 2 d t 2dt 2 d t on the number of potential conflicting edges can be strengthened to
( d 2 ) − ( d − 2 t 2 ) = t ( 2 d − 2 t − 1 ) , \binom{d}{2} - \binom{d-2t}{2} = t(2d-2t-1), ( 2 d ) − ( 2 d − 2 t ) = t ( 2 d − 2 t − 1 ) ,
which is a substantial improvement when t ≫ d t \gg d t ≫ d . Following this, one can prove that ∣ X ∣ ≤ ( d − m − 1 m ) |X| \le\binom{d-m-1}{m} ∣ X ∣ ≤ ( m d − m − 1 ) implies T ( X ) ≤ 4 m ( d − m ) ∣ X ∣ T(X) \le4m(d-m)|X| T ( X ) ≤ 4 m ( d − m ) ∣ X ∣ , which improves the leading constant in Theorem 1.4 for some ranges of m m m .
Remark 4.2. The proof of Theorem 1.4 we just presented can be modified to prove a bound
E ( X , S ) ≤ ( 4 m + 1 ) d ∣ X ∣ E(X,S) \le(4m+1)d|X| E ( X , S ) ≤ ( 4 m + 1 ) d ∣ X ∣
for X ⊂ R d X \subset\mathbb{R}^d X ⊂ R d of size at most ( d m ) \binom{d}{m} ( m d ) , where S = { e 1 , … , e d } S=\{e_1,\ldots,e_d\} S = { e 1 , … , e d } . Construct the graph G G G with vertex set X X X and where x 1 , x 2 ∈ X x_1,x_2\in X x 1 , x 2 ∈ X are joined by an edge if x 1 − x 2 = e i − e j x_1-x_2=e_i-e_j x 1 − x 2 = e i − e j for some distinct i , j ∈ { 1 , … , d } i,j\in\{1,\ldots,d\} i , j ∈ { 1 , … , d } . The average degree of G G G is L : = E ( X , S ) / ∣ X ∣ − d L:=E(X,S)/|X|-d L := E ( X , S ) /∣ X ∣ − d . Call two edges e i − e j e_i-e_j e i − e j and e i ′ − e j ′ e_{i'}-e_{j'} e i ′ − e j ′ of G G G conflicting if i = j ′ i=j' i = j ′ or i ′ = j i'=j i ′ = j . Assuming L ≥ 4 m d L\ge4md L ≥ 4 m d and following the same strategy, the bounds (22) and (23) read
( 2 d ) m m ! ∣ X ′ ∣ ≤ P ≤ m ! 2 ∣ X ′ ∣ 2 . (2d)^m m!|X'| \le P \le m!^2|X'|^2. ( 2 d ) m m ! ∣ X ′ ∣ ≤ P ≤ m ! 2 ∣ X ′ ∣ 2 .
and the bound ∣ X ′ ∣ > ( d m ) |X'|>\binom{d}{m} ∣ X ′ ∣ > ( m d ) can be extracted similarly.
Weighted Asymmetric Additive Energy Estimates
In this section, we present our proof of Theorem 1.3. This requires an analysis of higher-order energies. So, for each integer s ≥ 1 s\ge1 s ≥ 1 and each y ∈ R d y\in\mathbb{R}^d y ∈ R d , we define the quantities
E s ( y ) : = { ( i 1 , … , i s , j 1 , … , j s ) ∈ [ d ] 2 s : y = e i 1 − e j 1 + ⋯ + e i s − e j s } . \mathcal{E}_s(y):=\{(i_1,\ldots,i_s,j_1,\ldots,j_s)\in[d]^{2s}:y=e_{i_1}-e_{j_1}+\cdots+e_{i_s}-e_{j_s}\}. E s ( y ) := {( i 1 , … , i s , j 1 , … , j s ) ∈ [ d ] 2 s : y = e i 1 − e j 1 + ⋯ + e i s − e j s } .
and
R s ( y ) : = { ( i 1 , … , i s , j 1 , … , j s ) ∈ E s ( y ) : i k ≠ j ℓ for all 1 ≤ k , ℓ ≤ s } . \mathcal{R}_s(y):=\{(i_1,\ldots,i_s,j_1,\ldots,j_s)\in\mathcal{E}_s(y):i_k\ne j_\ell\text{ for all }1\le k,\ell\le s\}. R s ( y ) := {( i 1 , … , i s , j 1 , … , j s ) ∈ E s ( y ) : i k = j ℓ for all 1 ≤ k , ℓ ≤ s } .
Moreover, let R 0 ( 0 ) = E 0 ( 0 ) = { 1 } \mathcal{R}_0(0)=\mathcal{E}_0(0)=\{1\} R 0 ( 0 ) = E 0 ( 0 ) = { 1 } and R 0 ( y ) = E 0 ( y ) = ∅ \mathcal{R}_0(y)=\mathcal{E}_0(y)=\varnothing R 0 ( y ) = E 0 ( y ) = ∅ for all y ≠ 0 y\ne0 y = 0 . Now, for any integer s ≥ 0 s\ge0 s ≥ 0 , write
R s = ∑ x 1 , x 2 ∈ X f ( x 1 ) f ( x 2 ) ∣ R s ( x 1 − x 2 ) ∣ R_s=\sum_{x_1,x_2\in X}f(x_1)f(x_2)|\mathcal{R}_s(x_1-x_2)| R s = x 1 , x 2 ∈ X ∑ f ( x 1 ) f ( x 2 ) ∣ R s ( x 1 − x 2 ) ∣
and
E s = ∑ x 1 , x 2 ∈ X f ( x 1 ) f ( x 2 ) ∣ E s ( x 1 − x 2 ) ∣ = ∑ x 1 , x 2 ∈ X f ( x 1 ) f ( x 2 ) ∑ 1 ≤ i 1 , … , i s ≤ d 1 ≤ j 1 , … , j s ≤ d 1 x 1 − x 2 = e i 1 − e j 1 + ⋯ + e i s − e j s . (24) \begin{aligned}
E_s&=\sum_{x_1,x_2\in X}f(x_1)f(x_2)|\mathcal{E}_s(x_1-x_2)|\\
&=\sum_{x_1,x_2\in X}f(x_1)f(x_2)
\sum_{\substack{1\le i_1,\ldots,i_s\le d\\1\le j_1,\ldots,j_s\le d}}
\mathbf{1}_{x_1-x_2=e_{i_1}-e_{j_1}+\cdots+e_{i_s}-e_{j_s}}. \tag*{(24)}
\end{aligned} E s = x 1 , x 2 ∈ X ∑ f ( x 1 ) f ( x 2 ) ∣ E s ( x 1 − x 2 ) ∣ = x 1 , x 2 ∈ X ∑ f ( x 1 ) f ( x 2 ) 1 ≤ i 1 , … , i s ≤ d 1 ≤ j 1 , … , j s ≤ d ∑ 1 x 1 − x 2 = e i 1 − e j 1 + ⋯ + e i s − e j s . (24)
Note that the last of these definitions is exactly the one recorded in (17) . In particular,
E 0 = ∥ f ∥ 2 2 and E 1 = E f ( X , S ) . (25) E_0=\|f\|_2^2\quad\text{and}\quad E_1=E_f(X,S). \tag*{(25)} E 0 = ∥ f ∥ 2 2 and E 1 = E f ( X , S ) . (25)
We must show that E 1 ≤ 4 d ( m + 1 / m ) E 0 E_1\le4d(m+1/m)E_0 E 1 ≤ 4 d ( m + 1/ m ) E 0 subject to the condition that ∥ f ∥ 1 2 / ∥ f ∥ 2 2 ≤ ( d m ) \|f\|_1^2/\|f\|_2^2\le\binom{d}{m} ∥ f ∥ 1 2 /∥ f ∥ 2 2 ≤ ( m d ) . We may assume m ≤ d / 2 m\le d/2 m ≤ d /2 .
The main estimate behind the proof of Theorem 1.3 is as follows.
Lemma 5.1. Let t = 2 m t=2m t = 2 m . Then
E t ≤ 2 d t E t − 1 + ( 2 d ) t t ! E 0 . E_t \leq2dtE_{t-1}+(2d)^t t!E_0. E t ≤ 2 d t E t − 1 + ( 2 d ) t t ! E 0 .
This combines naturally with Lemma 2.4 to imply the conclusion of Theorem 1.3 .
Proof of Theorem 1.3. First, suppose that
( 2 d ) t t ! E 0 ≤ ( 2 d t ) E t − 1 / m 2 . (26) (2d)^t t!E_0 \leq(2dt)E_{t-1}/m^2. \tag*{(26)} ( 2 d ) t t ! E 0 ≤ ( 2 d t ) E t − 1 / m 2 . (26)
In this case, Lemma 5.1 implies that
E t ≤ ( 2 d t ) E t − 1 ( 1 + 1 / m 2 ) , E_t \leq(2dt)E_{t-1}(1+1/m^2), E t ≤ ( 2 d t ) E t − 1 ( 1 + 1/ m 2 ) ,
whence Lemma 2.4 implies that
E t 1 / t ≤ ( 2 d t ) ( 1 + 1 / m 2 ) E 0 1 / t . E_t^{1/t} \leq(2dt)(1+1/m^2)E_0^{1/t}. E t 1/ t ≤ ( 2 d t ) ( 1 + 1/ m 2 ) E 0 1/ t .
A second application of Lemma 2.4 then gives us
E 1 ≤ E 0 1 − 1 / t E t 1 / t ≤ ( 2 d t ) ( 1 + 1 / m 2 ) E 0 . E_1 \leq E_0^{1-1/t}E_t^{1/t} \leq(2dt)(1+1/m^2)E_0. E 1 ≤ E 0 1 − 1/ t E t 1/ t ≤ ( 2 d t ) ( 1 + 1/ m 2 ) E 0 .
Combining this with (25) yields the required bound. Now, if (26) does not hold, then we get that
E t − 1 < m 2 ( 2 d ) t − 1 ( t − 1 ) ! E 0 , E_{t-1}<m^2(2d)^{t-1}(t-1)!E_0, E t − 1 < m 2 ( 2 d ) t − 1 ( t − 1 )! E 0 ,
whence Lemma 2.4 gives us
E 1 ≤ E t − 1 1 / ( t − 1 ) E 0 1 − 1 / ( t − 1 ) < m 2 / ( t − 1 ) ( 2 d ) ( ( t − 1 ) ! ) 1 / ( t − 1 ) E 0 . E_1 \leq E_{t-1}^{1/(t-1)}E_0^{1-1/(t-1)} < m^{2/(t-1)}(2d)((t-1)!)^{1/(t-1)}E_0. E 1 ≤ E t − 1 1/ ( t − 1 ) E 0 1 − 1/ ( t − 1 ) < m 2/ ( t − 1 ) ( 2 d ) (( t − 1 )! ) 1/ ( t − 1 ) E 0 .
Since t = 2 m t=2m t = 2 m , we can use the AM-GM inequality to get ( ( t − 1 ) ! ) 1 / ( t − 1 ) ≤ m ((t-1)!)^{1/(t-1)}\leq m (( t − 1 )! ) 1/ ( t − 1 ) ≤ m . Moreover, one can see that m 1 / ( m − 1 / 2 ) ≤ 2 m^{1/(m-1/2)}\leq2 m 1/ ( m − 1/2 ) ≤ 2 for all integers m ≥ 1 m\geq1 m ≥ 1 , which dispenses the required estimate in this case. □
Thus we will now prepare to prove Lemma 5.1 . We will start by analysing E s ( y ) \mathcal{E}_s(y) E s ( y ) for fixed choices of y y y and integer s ≥ 2 s\geq2 s ≥ 2 . In particular, for any tuple τ = ( i 1 , … , i s , j 1 , … , j s ) ∈ E s ( y ) \tau=(i_1,\ldots,i_s,j_1,\ldots,j_s)\in\mathcal{E}_s(y) τ = ( i 1 , … , i s , j 1 , … , j s ) ∈ E s ( y ) , we call the pair ( i k , j ℓ ) (i_k,j_\ell) ( i k , j ℓ ) for some k , ℓ ∈ [ s ] k,\ell\in[s] k , ℓ ∈ [ s ] a cancelling pair if e i k − e j ℓ = 0 e_{i_k}-e_{j_\ell}=0 e i k − e j ℓ = 0 . Furthermore, write h ( τ ) h(\tau) h ( τ ) for the maximum number of disjoint cancelling pairs in τ \tau τ . For any 0 ≤ u ≤ s 0\leq u\leq s 0 ≤ u ≤ s , let
E s u ( y ) = { τ ∈ E s ( y ) : h ( τ ) = u } . \mathcal{E}_s^u(y)=\{\tau\in\mathcal{E}_s(y):h(\tau)=u\}. E s u ( y ) = { τ ∈ E s ( y ) : h ( τ ) = u } .
Note that for any τ ∈ E s u ( y ) \tau\in\mathcal{E}_s^u(y) τ ∈ E s u ( y ) and any 0 ≤ u < s 0\leq u<s 0 ≤ u < s , once we remove the u u u disjoint cancelling pairs, we obtain an element of R s − u ( y ) \mathcal{R}_{s-u}(y) R s − u ( y ) . This gives us the bound
∣ E s u ( y ) ∣ ≤ ( s u ) 2 d u u ! ∣ R s − u ( y ) ∣ , (27) |\mathcal{E}_s^u(y)|\leq\binom{s}{u}^2 d^u u!|\mathcal{R}_{s-u}(y)|, \tag*{(27)} ∣ E s u ( y ) ∣ ≤ ( u s ) 2 d u u ! ∣ R s − u ( y ) ∣ , (27)
since we can choose the indices corresponding to the u u u cancelling pairs in ( s u ) 2 \binom{s}{u}^2 ( u s ) 2 many ways and fix the values of these indices in d u u ! d^u u! d u u ! many ways.
With this in hand, we record a useful intermediate bound.
Lemma 5.2. For any 1 ≤ u ≤ s 1\leq u\leq s 1 ≤ u ≤ s , we have
∣ E s u ( y ) ∣ ≤ d s 2 ∣ E s − 1 u − 1 ( y ) ∣ / u . |\mathcal{E}_s^u(y)|\leq ds^2|\mathcal{E}_{s-1}^{u-1}(y)|/u. ∣ E s u ( y ) ∣ ≤ d s 2 ∣ E s − 1 u − 1 ( y ) ∣/ u .
Proof. Construct a bipartite multigraph with the vertex set E s u ( y ) ⊔ E s − 1 u − 1 ( y ) \mathcal{E}^{u}_{s}(y) \sqcup\mathcal{E}^{u-1}_{s-1}(y) E s u ( y ) ⊔ E s − 1 u − 1 ( y ) by connecting any τ ∈ E s u ( y ) \tau\in\mathcal{E}^{u}_{s}(y) τ ∈ E s u ( y ) to τ ′ ∈ E s − 1 u − 1 ( y ) \tau' \in\mathcal{E}^{u-1}_{s-1}(y) τ ′ ∈ E s − 1 u − 1 ( y ) if one obtains τ ′ \tau' τ ′ from τ \tau τ by removing one cancelling pair. This graph is a multigraph since we are allowing for multiple edges between two vertices; indeed, some τ \tau τ may have multiple choices of cancelling pairs which, when cancelled, give us the same τ ′ ∈ E s − 1 u − 1 ( y ) \tau' \in\mathcal{E}^{u-1}_{s-1}(y) τ ′ ∈ E s − 1 u − 1 ( y ) . Let E ′ E' E ′ be the number of edges in this graph. Note that
E ′ ≥ u ∣ E s u ( y ) ∣ E' \geq u|\mathcal{E}^{u}_{s}(y)| E ′ ≥ u ∣ E s u ( y ) ∣
since every τ ∈ E s u ( y ) \tau\in\mathcal{E}^{u}_{s}(y) τ ∈ E s u ( y ) has at least u u u cancelling pairs, each of which, when removed, give us some element in E s − 1 u − 1 ( y ) \mathcal{E}^{u-1}_{s-1}(y) E s − 1 u − 1 ( y ) . On the other hand, we have
E ′ ≤ d s 2 ∣ E s − 1 u − 1 ( y ) ∣ E' \leq ds^{2}|\mathcal{E}^{u-1}_{s-1}(y)| E ′ ≤ d s 2 ∣ E s − 1 u − 1 ( y ) ∣
since for any fixed τ ∈ E s − 1 u − 1 ( y ) \tau\in\mathcal{E}^{u-1}_{s-1}(y) τ ∈ E s − 1 u − 1 ( y ) , we have at most s 2 s^{2} s 2 choices for the positions where we may insert the two extra indices associated to a cancelling pair and at most d d d choices for the value that this cancelling pair is to take. Combining the above two bounds delivers the desired bound, thus finishing our proof of Lemma 5.2. □
We are now ready to prove Lemma 5.1.
Proof of Lemma 5.1. Using (5.1) and the preceding discussion, we see that
E t = ∑ x 1 , x 2 ∈ X f ( x 1 ) f ( x 2 ) ∣ E t ( x 1 − x 2 ) ∣ = ∑ x 1 , x 2 ∈ X f ( x 1 ) f ( x 2 ) ∑ u = 0 t ∣ E t u ( x 1 − x 2 ) ∣ . E_t=\sum_{x_1,x_2\in X}f(x_1)f(x_2)|\mathcal{E}_t(x_1-x_2)|=\sum_{x_1,x_2\in X}f(x_1)f(x_2)\sum_{u=0}^{t}|\mathcal{E}^{u}_{t}(x_1-x_2)|. E t = x 1 , x 2 ∈ X ∑ f ( x 1 ) f ( x 2 ) ∣ E t ( x 1 − x 2 ) ∣ = x 1 , x 2 ∈ X ∑ f ( x 1 ) f ( x 2 ) u = 0 ∑ t ∣ E t u ( x 1 − x 2 ) ∣.
Using (5.4) and Lemma 5.2 to estimate the cases when 0 ≤ u < t / 2 0\leq u<t/2 0 ≤ u < t /2 and t / 2 ≤ u ≤ t t/2\leq u\leq t t /2 ≤ u ≤ t respectively, we get that
E t ≤ ∑ 0 ≤ u < t / 2 ( t u ) 2 d u u ! R t − u + ∑ x 1 , x 2 ∈ X f ( x 1 ) f ( x 2 ) ∑ t / 2 ≤ u ≤ t d t 2 u ∣ E t − 1 u − 1 ( x 1 − x 2 ) ∣ . (28) E_t\leq\sum_{0\leq u<t/2}\binom{t}{u}^{2}d^{u}u!R_{t-u}+\sum_{x_1,x_2\in X}f(x_1)f(x_2)\sum_{t/2\leq u\leq t}\frac{dt^{2}}{u}|\mathcal{E}^{u-1}_{t-1}(x_1-x_2)|. \tag*{(28)} E t ≤ 0 ≤ u < t /2 ∑ ( u t ) 2 d u u ! R t − u + x 1 , x 2 ∈ X ∑ f ( x 1 ) f ( x 2 ) t /2 ≤ u ≤ t ∑ u d t 2 ∣ E t − 1 u − 1 ( x 1 − x 2 ) ∣. (28)
The second sum on the right hand side of (5.5) can be bounded above by
2 d t ∑ x 1 , x 2 ∈ X f ( x 1 ) f ( x 2 ) ∑ t / 2 ≤ u ≤ t ∣ E t − 1 u − 1 ( x 1 − x 2 ) ∣ ≤ 2 d t E t − 1 . (29) 2dt\sum_{x_1,x_2\in X}f(x_1)f(x_2)\sum_{t/2\leq u\leq t}|\mathcal{E}^{u-1}_{t-1}(x_1-x_2)|\leq2dtE_{t-1}. \tag*{(29)} 2 d t x 1 , x 2 ∈ X ∑ f ( x 1 ) f ( x 2 ) t /2 ≤ u ≤ t ∑ ∣ E t − 1 u − 1 ( x 1 − x 2 ) ∣ ≤ 2 d t E t − 1 . (29)
We now consider the first sum, and so let 0 ≤ u < t / 2 0\leq u<t/2 0 ≤ u < t /2 . For any x 1 , x 2 ∈ X x_1,x_2\in X x 1 , x 2 ∈ X , a representation of x 1 − x 2 x_1-x_2 x 1 − x 2 as e i 1 − e j 1 + ⋯ + e i t − u − e j t − u e_{i_1}-e_{j_1}+\cdots+e_{i_{t-u}}-e_{j_{t-u}} e i 1 − e j 1 + ⋯ + e i t − u − e j t − u with the i k i_k i k distinct from the j ℓ j_\ell j ℓ , if such a representation exists, is unique up to permutation of the i k i_k i k and the j ℓ j_\ell j ℓ . This follows from the linear independence of the set { e 1 , … , e d } \{e_1,\ldots,e_d\} { e 1 , … , e d } . We conclude that
R t − u ≤ ( ( t − u ) ! ) 2 ∑ x 1 , x 2 ∈ X f ( x 1 ) f ( x 2 ) = ( ( t − u ) ! ) 2 ∥ f ∥ 1 2 . R_{t-u}\leq((t-u)!)^{2}\sum_{x_1,x_2\in X}f(x_1)f(x_2)=((t-u)!)^{2}\lVert f\rVert_{1}^{2}. R t − u ≤ (( t − u )! ) 2 x 1 , x 2 ∈ X ∑ f ( x 1 ) f ( x 2 ) = (( t − u )! ) 2 ∥ f ∥ 1 2 .
Our hypothesis implies that ∥ f ∥ 1 2 ≤ ∥ f ∥ 2 2 ( d m ) \lVert f\rVert_{1}^{2}\leq\lVert f\rVert_{2}^{2}\binom{d}{m} ∥ f ∥ 1 2 ≤ ∥ f ∥ 2 2 ( m d ) , whence, the first sum on the right hand side of (5.5) is bounded above by
∑ 0 ≤ u < t / 2 ( t u ) 2 d u u ! ( ( t − u ) ! ) 2 ∥ f ∥ 2 2 ( d m ) = E 0 ( t ! ) 2 ( d m ) ∑ 0 ≤ u < t / 2 d u u ! . \sum_{0\leq u<t/2}\binom{t}{u}^{2}d^{u}u!((t-u)!)^{2}\lVert f\rVert_{2}^{2}\binom{d}{m}=E_{0}(t!)^{2}\binom{d}{m}\sum_{0\leq u<t/2}\frac{d^{u}}{u!}. 0 ≤ u < t /2 ∑ ( u t ) 2 d u u ! (( t − u )! ) 2 ∥ f ∥ 2 2 ( m d ) = E 0 ( t ! ) 2 ( m d ) 0 ≤ u < t /2 ∑ u ! d u .
For any 0 ≤ u < t / 2 = m ≤ d / 2 0\leq u<t/2=m\leq d/2 0 ≤ u < t /2 = m ≤ d /2 , observe that
d u u ! ≤ 1 2 t / 2 − u d t / 2 ( t / 2 ) ! . \frac{d^{u}}{u!}\leq\frac{1}{2^{t/2-u}}\frac{d^{t/2}}{(t/2)!}. u ! d u ≤ 2 t /2 − u 1 ( t /2 )! d t /2 .
Thus the right hand side of the preceding inequality is bounded above by
E 0 ( t ! ) 2 d m m ! d t / 2 ( t / 2 ) ! ∑ 0 ≤ u < t / 2 1 2 t / 2 − u < E 0 t ! ( t t / 2 ) d t ≤ E 0 t ! ( 2 d ) t . E_0(t!)^2\frac{d^{m}}{m!}\frac{d^{t/2}}{(t/2)!}\sum_{0\le u<t/2}\frac{1}{2^{t/2-u}}<E_0t!\binom{t}{t/2}d^t\le E_0t!(2d)^t. E 0 ( t ! ) 2 m ! d m ( t /2 )! d t /2 0 ≤ u < t /2 ∑ 2 t /2 − u 1 < E 0 t ! ( t /2 t ) d t ≤ E 0 t ! ( 2 d ) t .
Putting this together with (5.5) and (5.6) gives us
E t ≤ E 0 t ! ( 2 d ) t + 2 d t E t − 1 . E_t\le E_0t!(2d)^t+2dtE_{t-1}. E t ≤ E 0 t ! ( 2 d ) t + 2 d t E t − 1 .
Remark 5.3. This proof of Theorem 1.3 we have presented can be modified to prove Theorem 1.4.2 Given y ∈ ( Z / 2 Z ) d y\in(\mathbb{Z}/2\mathbb{Z})^d y ∈ ( Z /2 Z ) d , write
E s ( y ) : = { ( i 1 , … , i 2 s ) ∈ [ d ] 2 s : y = e i 1 ′ + ⋯ + e i 2 s ′ } , \mathcal{E}_s(y):=\{(i_1,\ldots,i_{2s})\in[d]^{2s}:y=e'_{i_1}+\cdots+e'_{i_{2s}}\}, E s ( y ) := {( i 1 , … , i 2 s ) ∈ [ d ] 2 s : y = e i 1 ′ + ⋯ + e i 2 s ′ } ,
and define R s ( y ) \mathcal{R}_s(y) R s ( y ) to be the set of elements τ : = ( i 1 , … , i 2 s ) ∈ E s ( y ) \tau:=(i_1,\ldots,i_{2s})\in\mathcal{E}_s(y) τ := ( i 1 , … , i 2 s ) ∈ E s ( y ) with i 1 , … , i 2 s i_1,\ldots,i_{2s} i 1 , … , i 2 s distinct. A cancelling pair in τ \tau τ becomes any pair of equal entries. Defining E s \mathcal{E}_s E s analogously to (5.1), the inequality Lemma 2.4 can be proven in precisely the same fashion, and we have
E 1 = ∑ x 1 , x 2 ∈ X ∣ E 1 ( x 1 − x 2 ) ∣ = 2 T ( X ) + d ∣ X ∣ . (30) E_1=\sum_{x_1,x_2\in X}|\mathcal{E}_1(x_1-x_2)|=2T(X)+d|X|. \tag*{(30)} E 1 = x 1 , x 2 ∈ X ∑ ∣ E 1 ( x 1 − x 2 ) ∣ = 2 T ( X ) + d ∣ X ∣. (30)
Defining E s u ( y ) \mathcal{E}_s^u(y) E s u ( y ) similarly, the analogue of Lemma 5.2 in this setting reads
∣ E s u ( y ) ∣ ≤ d s ( 2 s − 1 ) ∣ E s − 1 u ( y ) ∣ / u . (31) |\mathcal{E}_s^u(y)|\le ds(2s-1)|\mathcal{E}_{s-1}^u(y)|/u. \tag*{(31)} ∣ E s u ( y ) ∣ ≤ d s ( 2 s − 1 ) ∣ E s − 1 u ( y ) ∣/ u . (31)
The extra factor of 2 − 1 / s 2-1/s 2 − 1/ s in (5.8) as compared to Lemma 5.2 is due to the fact that there are ( 2 s 2 ) = s ( 2 s − 1 ) \binom{2s}{2}=s(2s-1) ( 2 2 s ) = s ( 2 s − 1 ) places in which to insert a cancelling pair into an element of E s − 1 u ( y ) \mathcal{E}_{s-1}^u(y) E s − 1 u ( y ) , rather than s 2 s^2 s 2 . Similarly to Lemma 5.1, one can use (5.8) to prove
E t ≤ 2 ( 2 t − 1 ) d E t − 1 + 2 ( d m ) d t / 2 ( 2 t ) ! 2 t / 2 ( t / 2 ) ! E 0 E_t\le2(2t-1)dE_{t-1}+2\binom{d}{m}\frac{d^{t/2}(2t)!}{2^{t/2}(t/2)!}E_0 E t ≤ 2 ( 2 t − 1 ) d E t − 1 + 2 ( m d ) 2 t /2 ( t /2 )! d t /2 ( 2 t )! E 0
for t = 2 m t=2m t = 2 m , whenever m ≤ d / 4 m\le d/4 m ≤ d /4 . When m > 1 m>1 m > 1 , the above inequality is enough to obtain the bound E 1 ≤ 8 m d E 0 E_1\le8mdE_0 E 1 ≤ 8 m d E 0 . When m = 1 m=1 m = 1 , one can prove such a bound by hand using (5.7) and T ( X ) ≤ ∣ X ∣ 2 T(X)\le|X|^2 T ( X ) ≤ ∣ X ∣ 2 , while for m > d / 4 m>d/4 m > d /4 such a bound follows trivially from (2.1).
Theorem 1.3 and Hypercontractivity
In this section, we will consider the following corollary of Theorem 1.3.
Proposition 6.1. Let d ∈ N d\in\mathbb{N} d ∈ N , let S = { e 1 , … , e d } S=\{e_1,\ldots,e_d\} S = { e 1 , … , e d } be the canonical basis of Z d \mathbb{Z}^d Z d , and let X ⊂ Z d X\subset\mathbb{Z}^d X ⊂ Z d be a non-empty set such that ∣ X ∣ ≤ ( d m ) |X|\le\binom{d}{m} ∣ X ∣ ≤ ( m d ) for some m ∈ N m\in\mathbb{N} m ∈ N . Then, for any f : X → [ 0 , ∞ ) f:X\to[0,\infty) f : X → [ 0 , ∞ ) , we have
E f ( X , S ) ≤ 16 m d ⋅ ∥ f ∥ 2 2 . E_f(X,S)\le16md\cdot\|f\|_2^2. E f ( X , S ) ≤ 16 m d ⋅ ∥ f ∥ 2 2 .
This follows from Theorem 1.3 in a straightforward manner.
Proof of Proposition 6.1. Cauchy’s inequality implies that any function f : R d → [ 0 , ∞ ) f:\mathbb{R}^{d}\to[0,\infty) f : R d → [ 0 , ∞ ) which is supported on some finite, non-empty set X ⊆ R d X\subseteq\mathbb{R}^{d} X ⊆ R d also satisfies
∥ f ∥ 1 2 ≤ ∣ X ∣ ∥ f ∥ 2 2 . \lVert f\rVert_{1}^{2}\leq|X|\lVert f\rVert_{2}^{2}. ∥ f ∥ 1 2 ≤ ∣ X ∣ ∥ f ∥ 2 2 .
Thus if ∣ X ∣ ≤ ( d d / 2 ) |X|\leq\binom{d}{d/2} ∣ X ∣ ≤ ( d /2 d ) , the hypothesis (1.8) of Theorem 1.3 is automatically satisfied. Applying Theorem 1.3 immediately gives us the desired conclusion. □ \square □
Our main aim of this section is to give an alternative proof of Proposition 6.1 which utilises ideas from the vast collection of results associated with the Hypercontractivity phenomenon. We begin by introducing some relevant notation. Let G = ( Z / 2 Z ) d G=(\mathbb{Z}/2\mathbb{Z})^{d} G = ( Z /2 Z ) d . Given any function f : G → R f:G\to\mathbb{R} f : G → R and any 1 ≤ p < ∞ 1\leq p<\infty 1 ≤ p < ∞ , define3
∥ f ∥ L p = ( 2 − d ∑ x ∈ G ∣ f ( x ) ∣ p ) 1 / p and ∥ f ∥ L ∞ = max x ∈ G ∣ f ( x ) ∣ . \lVert f\rVert_{L^{p}}=\left(2^{-d}\sum_{x\in G}|f(x)|^{p}\right)^{1/p}
\qquad\text{and}\qquad
\lVert f\rVert_{L^{\infty}}=\max_{x\in G}|f(x)|. ∥ f ∥ L p = ( 2 − d x ∈ G ∑ ∣ f ( x ) ∣ p ) 1/ p and ∥ f ∥ L ∞ = x ∈ G max ∣ f ( x ) ∣.
For any two functions f , g : G → R f,g:G\to\mathbb{R} f , g : G → R , we define their convolution f ∗ g : G → R f*g:G\to\mathbb{R} f ∗ g : G → R by setting
( f ∗ g ) ( x ) = 2 − d ∑ y ∈ G f ( y ) g ( x − y ) = 2 − d ∑ y ∈ G f ( y ) g ( x + y ) . (f*g)(x)=2^{-d}\sum_{y\in G}f(y)g(x-y)=2^{-d}\sum_{y\in G}f(y)g(x+y). ( f ∗ g ) ( x ) = 2 − d y ∈ G ∑ f ( y ) g ( x − y ) = 2 − d y ∈ G ∑ f ( y ) g ( x + y ) .
for all x ∈ G x\in G x ∈ G . We set ⟨ f , g ⟩ = ( f ∗ g ) ( 0 ) \langle f,g\rangle=(f*g)(0) ⟨ f , g ⟩ = ( f ∗ g ) ( 0 ) .
Next, for any 0 ≤ ρ ≤ 1 0\leq\rho\leq1 0 ≤ ρ ≤ 1 , define the function μ ρ : G → [ 0 , ∞ ) \mu_{\rho}:G\to[0,\infty) μ ρ : G → [ 0 , ∞ ) as
μ ρ ( x 1 , … , x d ) = ∏ 1 ≤ i ≤ d ( ( 1 + ρ ) 1 x i = 0 + ( 1 − ρ ) 1 x i = 1 ) \mu_{\rho}(x_{1},\ldots,x_{d})=\prod_{1\leq i\leq d}\left((1+\rho)\mathbf{1}_{x_i=0}+(1-\rho)\mathbf{1}_{x_i=1}\right) μ ρ ( x 1 , … , x d ) = 1 ≤ i ≤ d ∏ ( ( 1 + ρ ) 1 x i = 0 + ( 1 − ρ ) 1 x i = 1 )
for all ( x 1 , … , x d ) ∈ G (x_{1},\ldots,x_{d})\in G ( x 1 , … , x d ) ∈ G . Finally, define the noise operator T ρ T_{\rho} T ρ by setting T ρ f = f ∗ μ ρ T_{\rho}f=f*\mu_{\rho} T ρ f = f ∗ μ ρ for all f : G → R f:G\to\mathbb{R} f : G → R . Thus for any x ∈ G x\in G x ∈ G , one has
( T ρ f ) ( x ) = 2 − d ∑ y ∈ G μ ρ ( y ) f ( x + y ) . (T_{\rho}f)(x)=2^{-d}\sum_{y\in G}\mu_{\rho}(y)f(x+y). ( T ρ f ) ( x ) = 2 − d y ∈ G ∑ μ ρ ( y ) f ( x + y ) .
Example 6.2. Let ρ = 0 \rho=0 ρ = 0 . Then μ 0 ( x ) = 1 \mu_{0}(x)=1 μ 0 ( x ) = 1 for all x ∈ G x\in G x ∈ G . Thus, for any f : G → R f:G\to\mathbb{R} f : G → R , we see that T 0 f T_{0}f T 0 f is the constant function satisfying ( T 0 f ) ( x ) = 2 − d ∑ y ∈ G f ( y ) (T_{0}f)(x)=2^{-d}\sum_{y\in G}f(y) ( T 0 f ) ( x ) = 2 − d ∑ y ∈ G f ( y ) for all x ∈ G x\in G x ∈ G . Moreover, when ρ = 1 \rho=1 ρ = 1 , then μ 1 ( x ) = 2 d \mu_{1}(x)=2^{d} μ 1 ( x ) = 2 d for x = 0 ∈ G x=0\in G x = 0 ∈ G and μ 1 ( x ) = 0 \mu_{1}(x)=0 μ 1 ( x ) = 0 otherwise. This means that T 1 f = f T_{1}f=f T 1 f = f for all f : G → R f:G\to\mathbb{R} f : G → R .
Noting the above example, it is natural to ask, as ρ \rho ρ varies in [ 0 , 1 ] [0,1] [ 0 , 1 ] , how much “smoother” T ρ ( f ) T_{\rho}(f) T ρ ( f ) is compared to f f f . A straightforward application of Hölder’s inequality gives us contractivity , that is, for any 0 ≤ ρ ≤ 1 0\leq\rho\leq1 0 ≤ ρ ≤ 1 and any 1 ≤ p ≤ ∞ 1\leq p\leq\infty 1 ≤ p ≤ ∞ and any f : G → R f:G\to\mathbb{R} f : G → R , we have
∥ T ρ f ∥ L p ≤ ∥ f ∥ L p . (32) \lVert T_{\rho}f\rVert_{L^{p}}\leq\lVert f\rVert_{L^{p}}. \tag*{(32)} ∥ T ρ f ∥ L p ≤ ∥ f ∥ L p . (32)
The hypercontractivity phenomenon suggests that T ρ f T_{\rho}f T ρ f exhibits much more smoothness. In particular, for any 1 ≤ p ≤ q ≤ ∞ 1\leq p\leq q\leq\infty 1 ≤ p ≤ q ≤ ∞ and any 0 ≤ ρ ≤ ( p − 1 q − 1 ) 1 / 2 0\leq\rho\leq\left(\frac{p-1}{q-1}\right)^{1/2} 0 ≤ ρ ≤ ( q − 1 p − 1 ) 1/2 and any f : G → R f:G\to\mathbb{R} f : G → R , one has
∥ T ρ f ∥ L q ≤ ∥ f ∥ L p . (33) \lVert T_{\rho}f\rVert_{L^{q}}\leq\lVert f\rVert_{L^{p}}. \tag*{(33)} ∥ T ρ f ∥ L q ≤ ∥ f ∥ L p . (33)
This immediately implies (6.1) by a simple application of Hölder’s inequality. Inequality (6.2) seems to have been first proven by Bonami [5 ] , with later developments given by Beckner [3 ] and Gross [13 ] ; see [21 Chapter 9] for further references.
We will now highlight the connection between such results and upper bounds on additive energies. Recall the following notation from § 4 ; for every 1 ≤ i ≤ d 1 \le i \le d 1 ≤ i ≤ d , the element e i ′ ∈ G e_i' \in G e i ′ ∈ G denotes the vector which has 1 1 1 in its i i i th coordinate and 0 0 0 in all other coordinates. In particular, { e 1 ′ , … , e d ′ } \{e_1',\ldots,e_d'\} { e 1 ′ , … , e d ′ } is a basis of G G G . Observe that for any 0 ≤ ρ ≤ 1 0 \le\rho\le1 0 ≤ ρ ≤ 1 and any X ⊆ G X \subseteq G X ⊆ G and any f : X → [ 0 , ∞ ) f:X \to[0,\infty) f : X → [ 0 , ∞ ) , one has
⟨ T ρ f , f ⟩ = 2 − d ∑ x ∈ G ( T ρ f ) ( x ) f ( x ) = 2 − 2 d ∑ x , y ∈ G μ ρ ( y ) f ( x + y ) f ( x ) ≥ 2 − d − 1 ( 1 + ρ 2 ) d − 2 ( 1 − ρ 2 ) 2 ∑ x ∈ X ∑ 1 ≤ i ≠ j ≤ d f ( x ) f ( x + e i ′ − e j ′ ) = 2 − d − 1 ( 1 + ρ 2 ) d − 2 ( 1 − ρ 2 ) 2 ( E f ( X , { e 1 ′ , … , e d ′ } ) − d ∑ x ∈ X f ( x ) 2 ) . (34) \begin{aligned}
\langle T_\rho f,f\rangle&= 2^{-d}\sum_{x\in G}(T_\rho f)(x)f(x)=2^{-2d}\sum_{x,y\in G}\mu_\rho(y)f(x+y)f(x)\\
&\ge2^{-d-1}\left(\frac{1+\rho}{2}\right)^{d-2}\left(\frac{1-\rho}{2}\right)^2\sum_{x\in X}\sum_{1\le i\ne j\le d}f(x)f(x+e_i'-e_j')\\
&=2^{-d-1}\left(\frac{1+\rho}{2}\right)^{d-2}\left(\frac{1-\rho}{2}\right)^2\left(E_f(X,\{e_1',\ldots,e_d'\})-d\sum_{x\in X}f(x)^2\right). \tag*{(34)}
\end{aligned} ⟨ T ρ f , f ⟩ = 2 − d x ∈ G ∑ ( T ρ f ) ( x ) f ( x ) = 2 − 2 d x , y ∈ G ∑ μ ρ ( y ) f ( x + y ) f ( x ) ≥ 2 − d − 1 ( 2 1 + ρ ) d − 2 ( 2 1 − ρ ) 2 x ∈ X ∑ 1 ≤ i = j ≤ d ∑ f ( x ) f ( x + e i ′ − e j ′ ) = 2 − d − 1 ( 2 1 + ρ ) d − 2 ( 2 1 − ρ ) 2 ( E f ( X , { e 1 ′ , … , e d ′ }) − d x ∈ X ∑ f ( x ) 2 ) . (34)
On the other hand, hypercontractivity-type results naturally deliver upper bounds for ⟨ T ρ f , f ⟩ \langle T_\rho f,f\rangle ⟨ T ρ f , f ⟩ . For our purposes, the classical hypercontractivity inequality (33) does not seem strong enough to prove Proposition 6.1. We will instead use sharper hypercontractivity-type results given by Kirshner–Samorodnitsky [15 ] to prove the following.
Lemma 6.3. Let f : G → [ 0 , ∞ ) f:G\to[0,\infty) f : G → [ 0 , ∞ ) be supported on a set X X X satisfying ∣ X ∣ ≤ ( d m ) |X|\le\binom{d}{m} ∣ X ∣ ≤ ( m d ) for some integer 1 ≤ m ≤ d / 2 1\le m\le d/2 1 ≤ m ≤ d /2 . Then
E f ( X , { e 1 ′ , … , e d ′ } ) ≤ 16 m d ∑ x ∈ X f ( x ) 2 . E_f(X,\{e_1',\ldots,e_d'\})\le16md\sum_{x\in X}f(x)^2. E f ( X , { e 1 ′ , … , e d ′ }) ≤ 16 m d x ∈ X ∑ f ( x ) 2 .
We remark that, for f = 1 X f=1_X f = 1 X , we have E f ( X , { e 1 ′ , … , e d ′ } ) = d ∣ X ∣ + 2 T ( X ) E_f(X,\{e_1',\ldots,e_d'\})=d|X|+2T(X) E f ( X , { e 1 ′ , … , e d ′ }) = d ∣ X ∣ + 2 T ( X ) , where T T T is as in Theorem 1.4 .
Lemma 6.3 allows us to prove Proposition 6.1 in a straightforward manner.
Proof of Proposition 6.1. For m > d / 2 m>d/2 m > d /2 the result is trivial, so we assume m ≤ d / 2 m\le d/2 m ≤ d /2 . Let π \pi π be the canonical projection map from Z d \mathbb{Z}^d Z d to G = ( Z / 2 Z ) d G=(\mathbb{Z}/2\mathbb{Z})^d G = ( Z /2 Z ) d and let g : G → [ 0 , ∞ ) g:G\to[0,\infty) g : G → [ 0 , ∞ ) be given by setting
g ( y ) = ( ∑ x ∈ π − 1 ( y ) f ( x ) 2 ) 1 / 2 g(y)=\left(\sum_{x\in\pi^{-1}(y)}f(x)^2\right)^{1/2} g ( y ) = x ∈ π − 1 ( y ) ∑ f ( x ) 2 1/2
for all y ∈ G y\in G y ∈ G . Thus, we have
∑ x ∈ X f ( x ) 2 = ∑ y ∈ π ( X ) g ( y ) 2 . \sum_{x\in X}f(x)^2=\sum_{y\in\pi(X)}g(y)^2. x ∈ X ∑ f ( x ) 2 = y ∈ π ( X ) ∑ g ( y ) 2 .
The function g g g is supported on π ( X ) \pi(X) π ( X ) which satisfies ∣ π ( X ) ∣ ≤ ∣ X ∣ ≤ ( d m ) |\pi(X)|\le|X|\le\binom{d}{m} ∣ π ( X ) ∣ ≤ ∣ X ∣ ≤ ( m d ) , so Lemma 6.3 gives us
E g ( π ( X ) , { e 1 ′ , … , e d ′ } ) ≤ 16 m d ∑ y ∈ π ( X ) g ( y ) 2 = 16 m d ∑ x ∈ X f ( x ) 2 . (35) E_g(\pi(X),\{e_1',\ldots,e_d'\})\le16md\sum_{y\in\pi(X)}g(y)^2=16md\sum_{x\in X}f(x)^2. \tag*{(35)} E g ( π ( X ) , { e 1 ′ , … , e d ′ }) ≤ 16 m d y ∈ π ( X ) ∑ g ( y ) 2 = 16 m d x ∈ X ∑ f ( x ) 2 . (35)
Observe that
E f ( X , S ) − d ∑ x ∈ X f ( x ) 2 = ∑ i ≠ j ∑ x ∈ X f ( x ) f ( x + e i − e j ) = ∑ i ≠ j ∑ y ∈ π ( X ) ∑ x ∈ X ∩ π − 1 ( y ) f ( x ) f ( x + e i − e j ) . (36) \begin{aligned}
E_f(X,S)-d\sum_{x\in X}f(x)^2&=\sum_{i\ne j}\sum_{x\in X}f(x)f(x+e_i-e_j)\\
&=\sum_{i\ne j}\sum_{y\in\pi(X)}\sum_{x\in X\cap\pi^{-1}(y)}f(x)f(x+e_i-e_j). \tag*{(36)}
\end{aligned} E f ( X , S ) − d x ∈ X ∑ f ( x ) 2 = i = j ∑ x ∈ X ∑ f ( x ) f ( x + e i − e j ) = i = j ∑ y ∈ π ( X ) ∑ x ∈ X ∩ π − 1 ( y ) ∑ f ( x ) f ( x + e i − e j ) . (36)
Applying Cauchy’s inequality, we see that
E f ( X , S ) ≤ d ∑ x ∈ X f ( x ) 2 + ∑ i ≠ j ∑ y ∈ π ( X ) ( ∑ x ∈ π − 1 ( y ) f ( x ) 2 ) 1 / 2 ( ∑ x ∈ π − 1 ( y ) f ( x + e i − e j ) 2 ) 1 / 2 = d ∑ y ∈ π ( X ) g ( y ) 2 + ∑ i ≠ j ∑ y ∈ π ( X ) g ( y ) g ( y + e i ′ − e j ′ ) = E g ( π ( X ) , { e 1 ′ , … , e d ′ } ) . \begin{aligned}
E_f(X,S) \le d\sum_{x\in X} f(x)^2+\sum_{i\ne j}\sum_{y\in\pi(X)}\left(\sum_{x\in\pi^{-1}(y)}f(x)^2\right)^{1/2}\left(\sum_{x\in\pi^{-1}(y)}f(x+e_i-e_j)^2\right)^{1/2} \\
&= d\sum_{y\in\pi(X)}g(y)^2+\sum_{i\ne j}\sum_{y\in\pi(X)}g(y)g(y+e'_i-e'_j)=E_g(\pi(X),\{e'_1,\ldots,e'_d\}).
\end{aligned} E f ( X , S ) ≤ d x ∈ X ∑ f ( x ) 2 + i = j ∑ y ∈ π ( X ) ∑ x ∈ π − 1 ( y ) ∑ f ( x ) 2 1/2 x ∈ π − 1 ( y ) ∑ f ( x + e i − e j ) 2 1/2 = d y ∈ π ( X ) ∑ g ( y ) 2 + i = j ∑ y ∈ π ( X ) ∑ g ( y ) g ( y + e i ′ − e j ′ ) = E g ( π ( X ) , { e 1 ′ , … , e d ′ }) .
Combining this with (35) gives us the desired estimate.
Hence, we will now focus on proving Lemma 6.3. In this endeavour, we will require some further definitions from [15 ] . Thus, let H : ( 0 , 1 ) → [ 0 , ∞ ) H:(0,1)\to[0,\infty) H : ( 0 , 1 ) → [ 0 , ∞ ) be the binary entropy function
H ( σ ) = − σ log 2 σ − ( 1 − σ ) log 2 ( 1 − σ ) . H(\sigma)=-\sigma\log_2\sigma-(1-\sigma)\log_2(1-\sigma). H ( σ ) = − σ log 2 σ − ( 1 − σ ) log 2 ( 1 − σ ) .
Let ϕ : [ 0 , 1 / 2 ] 2 → R \phi:[0,1/2]^2\to\mathbb{R} ϕ : [ 0 , 1/2 ] 2 → R be the function as defined at the beginning of [15 Section 2.A.6] . [15 Lemma 21] implies that
min 0 < ε ≤ 1 / 2 ( ϕ ( σ , ε ) + 1 − H ( σ ) − y log 2 ε − ( 1 − y ) log 2 ( 1 − ε ) ) = σ H ( y 2 σ ) + ( 1 − σ ) H ( y 2 ( 1 − σ ) ) (37) \min_{0<\varepsilon\le1/2}\left(\phi(\sigma,\varepsilon)+1-H(\sigma)-y\log_2\varepsilon-(1-y)\log_2(1-\varepsilon)\right)
=\sigma H\left(\frac{y}{2\sigma}\right)+(1-\sigma)H\left(\frac{y}{2(1-\sigma)}\right) \tag*{(37)} 0 < ε ≤ 1/2 min ( ϕ ( σ , ε ) + 1 − H ( σ ) − y log 2 ε − ( 1 − y ) log 2 ( 1 − ε ) ) = σ H ( 2 σ y ) + ( 1 − σ ) H ( 2 ( 1 − σ ) y ) (37)
for 0 ≤ σ ≤ 1 / 2 0\le\sigma\le1/2 0 ≤ σ ≤ 1/2 and 0 ≤ y ≤ 2 σ ( 1 − σ ) 0\le y\le2\sigma(1-\sigma) 0 ≤ y ≤ 2 σ ( 1 − σ ) . (The identity (6.5) is the only property of the function ϕ \phi ϕ we will use.) With this in hand, we now record the following result of Kirshner–Samorodnitsky [15 Corollary 28] .
Lemma 6.4. Let 0 < ρ < 1 0<\rho<1 0 < ρ < 1 and 0 ≤ σ ≤ 1 / 2 0\le\sigma\le1/2 0 ≤ σ ≤ 1/2 , and let ε = ( 1 − ρ ) / 2 \varepsilon=(1-\rho)/2 ε = ( 1 − ρ ) /2 . For any f : { 0 , 1 } d → R f:\{0,1\}^d\to\mathbb{R} f : { 0 , 1 } d → R supported on a set of size at most 2 d H ( σ ) 2^{dH(\sigma)} 2 d H ( σ ) , we have4
⟨ T ρ f , f ⟩ ≤ 2 d ( ϕ ( σ , ε ) + 1 − H ( σ ) ) ∥ f ∥ L 2 2 . \langle T_\rho f,f\rangle\le2^{d(\phi(\sigma,\varepsilon)+1-H(\sigma))}\|f\|_{L^2}^2. ⟨ T ρ f , f ⟩ ≤ 2 d ( ϕ ( σ , ε ) + 1 − H ( σ )) ∥ f ∥ L 2 2 .
Remark 6.5. It is perhaps worth mentioning that despite the fact that the above inequality pertains to two objects defined in the physical space, Kirshner–Samorodnitsky prove Lemma 6.4 by applying a Parseval-type identity to pass from ⟨ T ρ f , f ⟩ \langle T_\rho f,f\rangle ⟨ T ρ f , f ⟩ to an inner product defined over the Fourier space and applying sharper level-k -type inequalities there, which themselves are a consequence of a sharper hypercontractivity-type theorem.
We are now ready to prove Lemma 6.3.
Proof of Lemma 6.3. For m = 1 m=1 m = 1 , we may simply compute
E f ( X , { e 1 ′ , … , e d ′ } ) ≤ d ∑ x ∈ X f ( x ) 2 + 2 ∑ x , y ∈ X f ( x ) f ( y ) ≤ 3 d ∑ x ∈ X f ( x ) 2 . E_f(X,\{e'_1,\ldots,e'_d\})\le d\sum_{x\in X}f(x)^2+2\sum_{x,y\in X}f(x)f(y)\le3d\sum_{x\in X}f(x)^2. E f ( X , { e 1 ′ , … , e d ′ }) ≤ d x ∈ X ∑ f ( x ) 2 + 2 x , y ∈ X ∑ f ( x ) f ( y ) ≤ 3 d x ∈ X ∑ f ( x ) 2 .
which is a strong enough bound. Henceforth, assume m > 1 m>1 m > 1 . Let σ = m / d \sigma=m/d σ = m / d and note that ∣ X ∣ ≤ ( d m ) ≤ 2 d H ( σ ) |X|\le\binom{d}{m}\le2^{dH(\sigma)} ∣ X ∣ ≤ ( m d ) ≤ 2 d H ( σ ) . We thus conclude from Lemma 6.4, for any 0 < ρ < 1 0<\rho<1 0 < ρ < 1 , that
⟨ T ρ f , f ⟩ ≤ 2 d ( ϕ ( σ , ε ) + 1 − H ( σ ) ) ∥ f ∥ L 2 2 , \langle T_\rho f,f\rangle\le2^{d(\phi(\sigma,\varepsilon)+1-H(\sigma))}\|f\|_{L^2}^2, ⟨ T ρ f , f ⟩ ≤ 2 d ( ϕ ( σ , ε ) + 1 − H ( σ )) ∥ f ∥ L 2 2 ,
where ε = ( 1 − ρ ) / 2 \varepsilon=(1-\rho)/2 ε = ( 1 − ρ ) /2 . Combining this with (34) gives us
E f ( X , { e 1 ′ , … , e d ′ } ) ≤ ( d + 2 ⋅ 2 d ( ϕ ( σ , ε ) + 1 − H ( σ ) − t log 2 ε − ( 1 − t ) log 2 ( 1 − ε ) ) ) ∑ x ∈ X f ( x ) 2 (38) E_f(X,\{e'_1,\ldots,e'_d\})\le\left(d+2\cdot2^{d(\phi(\sigma,\varepsilon)+1-H(\sigma)-t\log_2\varepsilon-(1-t)\log_2(1-\varepsilon))}\right)\sum_{x\in X}f(x)^2 \tag*{(38)} E f ( X , { e 1 ′ , … , e d ′ }) ≤ ( d + 2 ⋅ 2 d ( ϕ ( σ , ε ) + 1 − H ( σ ) − t l o g 2 ε − ( 1 − t ) l o g 2 ( 1 − ε )) ) x ∈ X ∑ f ( x ) 2 (38)
where t = 2 / d t = 2/d t = 2/ d . Using (6.5) to choose ε \varepsilon ε appropriately (which we may do since σ = m / d ≤ 1 / 2 \sigma= m/d \le1/2 σ = m / d ≤ 1/2 and t = 2 / d ≤ σ ≤ 2 σ ( 1 − σ ) t = 2/d \le\sigma\le2\sigma(1-\sigma) t = 2/ d ≤ σ ≤ 2 σ ( 1 − σ ) ), we thus have
E f ( X , { e 1 ′ , … , e d ′ } ) ≤ ( d + 2 d r + 1 ) ∑ x ∈ X f ( x ) 2 E_f(X,\{e'_1,\ldots,e'_d\}) \le(d+2^{dr+1})\sum_{x\in X} f(x)^2 E f ( X , { e 1 ′ , … , e d ′ }) ≤ ( d + 2 d r + 1 ) x ∈ X ∑ f ( x ) 2
where
r = σ H ( 1 d σ ) + ( 1 − σ ) H ( 1 d ( 1 − σ ) ) = m d H ( 1 m ) + d − m d H ( 1 d − m ) . r=\sigma H\left(\frac{1}{d\sigma}\right)+(1-\sigma)H\left(\frac{1}{d(1-\sigma)}\right)=\frac{m}{d}H\left(\frac{1}{m}\right)+\frac{d-m}{d}H\left(\frac{1}{d-m}\right). r = σ H ( d σ 1 ) + ( 1 − σ ) H ( d ( 1 − σ ) 1 ) = d m H ( m 1 ) + d d − m H ( d − m 1 ) .
The result follows, as in [15 Proof of Corollary 7] , from observing that
t H ( 1 / t ) ≤ log 2 t + 1 / ( log 2 ) tH(1/t)\le\log_2 t+1/(\log2) t H ( 1/ t ) ≤ log 2 t + 1/ ( log 2 )
for t ≥ 1 t\ge1 t ≥ 1 . Indeed, the latter implies that 2 d r ≤ e 2 m ( d − m ) 2^{dr}\le e^{2}m(d-m) 2 d r ≤ e 2 m ( d − m ) , and so
E f ( X , { e 1 ′ , … , e d ′ } ) ≤ ( d + 2 e 2 m ( d − m ) ) ∑ x ∈ X f ( x ) 2 ≤ 16 m d ∑ x ∈ X f ( x ) 2 . E_f(X,\{e'_1,\ldots,e'_d\})\le(d+2e^{2}m(d-m))\sum_{x\in X}f(x)^2\le16md\sum_{x\in X}f(x)^2. E f ( X , { e 1 ′ , … , e d ′ }) ≤ ( d + 2 e 2 m ( d − m )) x ∈ X ∑ f ( x ) 2 ≤ 16 m d x ∈ X ∑ f ( x ) 2 .
References
Appendix A. A geometric approach to Theorem 1.1
In this section, we present a significantly digested proof of the following explicit version of Theorem 1.1 which was found by GPT-6 Astra when the main body of the document was in the proofreading phase. In what follows, we call an affine-independent set of d + 1 d+1 d + 1 vectors in R d \mathbb{R}^{d} R d an affine basis .
Theorem A.1. Given a finite set A ⊂ R d A \subset\mathbb{R}^{d} A ⊂ R d with full affine span, there exists some affine basis S ⊂ A S \subset A S ⊂ A of R d \mathbb{R}^{d} R d for which
E ( A , S ) ≤ ( 2 d + 3 ) ∣ A ∣ − ( 2 d + 2 ) . E(A,S) \le(2d+3)|A|-(2d+2). E ( A , S ) ≤ ( 2 d + 3 ) ∣ A ∣ − ( 2 d + 2 ) .
Theorem A.1 is tight when A A A is the simplex. In this case, the only affine basis contained in A A A is A A A itself, and we have E ( A , A ) = ( 2 d + 1 ) ( d + 1 ) E(A,A)=(2d+1)(d+1) E ( A , A ) = ( 2 d + 1 ) ( d + 1 ) . We do not know if the multiplicative constant 2 (for large d d d and ∣ A ∣ |A| ∣ A ∣ ) is the best possible.
Unlike the proof we presented in the main body of the document, the proof of Theorem A.1 is geometric in nature. It follows the following three steps:
Find a norm ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ on R d \mathbb{R}^{d} R d which is scaled appropriately to capture the “orientation” of the set A A A .5
Show that, if a vector v v v is large with respect to the norm ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ , then A ∩ ( A + v ) A \cap(A+v) A ∩ ( A + v ) cannot be large.
Choose a probability distribution on affine bases contained within A A A which biases against choosing vectors which are nearby with respect to ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ .
Once these steps are accomplished, one may simply choose S ⊂ A S \subset A S ⊂ A an affine basis from the distribution constructed in (3) and upper-bound the expected value of E ( A , S ) E(A,S) E ( A , S ) using (2).
We begin the proof by defining the notion which captures (1).
Definition A.2. A finite, nonempty set A ⊂ R d A \subset\mathbb{R}^{d} A ⊂ R d is in isotropic position if
1 ∣ A ∣ ∑ a ∈ A a = 0 and 1 ∣ A ∣ ∑ a ∈ A a a T = I d . \frac{1}{|A|}\sum_{a\in A} a=0 \qquad\text{and}\qquad\frac{1}{|A|}\sum_{a\in A} aa^{\mathsf{T}}=I_d. ∣ A ∣ 1 a ∈ A ∑ a = 0 and ∣ A ∣ 1 a ∈ A ∑ a a T = I d . This notion is standard in the convex geometry literature; for a reference on the use of isotropic position, see the book [6 ] .
Lemma A.3. Let A ⊂ R d A \subset\mathbb{R}^{d} A ⊂ R d be finite and nonempty. Suppose that the affine span of A A A is all of R d \mathbb{R}^{d} R d . Then there is an affine transformation ρ \rho ρ such that the image ρ ( A ) \rho(A) ρ ( A ) of A A A is in isotropic position.
In other words, given a full-dimensional subset A A A of an abstract d d d -dimensional Euclidean space, one can assign a zero vector and a coordinate frame which makes A A A isotropic.
Lemma A.4. Let A A A be in isotropic position and let v ∈ R d v \in\mathbb{R}^{d} v ∈ R d be non-zero. We have
∣ A ∩ ( A + v ) ∣ ≤ 2 ∣ A ∣ ∥ v ∥ 2 . |A \cap(A+v)| \le\frac{2|A|}{\lVert v\rVert^{2}}. ∣ A ∩ ( A + v ) ∣ ≤ ∥ v ∥ 2 2∣ A ∣ .
Lemma A.5. Let A A A be a finite subset of R d \mathbb{R}^{d} R d in isotropic position. There exists a probability distribution P \mathcal{P} P supported on affine-independent subsets of A A A of size d + 1 d+1 d + 1 such that, for any distinct x , y ∈ A x,y \in A x , y ∈ A ,
Pr S ∼ P [ x , y ∈ S ] = ( 1 + ∥ x ∥ 2 ) ( 1 + ∥ y ∥ 2 ) − ( 1 + ( x ⋅ y ) ) 2 ∣ A ∣ 2 . \Pr_{S\sim\mathcal{P}}[x,y \in S] = \frac{(1+\lVert x\rVert^{2})(1+\lVert y\rVert^{2})-(1+(x\cdot y))^{2}}{|A|^{2}}. S ∼ P Pr [ x , y ∈ S ] = ∣ A ∣ 2 ( 1 + ∥ x ∥ 2 ) ( 1 + ∥ y ∥ 2 ) − ( 1 + ( x ⋅ y ) ) 2 .
We will prove and discuss these lemmas in the following subsections. First, we deduce Theorem A.1.
Proof of Theorem A.1. By Lemma A.3, and the fact that additive energy is invariant under affine transformation, we may assume A A A is in isotropic position. Let P \mathcal{P} P be the probability distribution on affine bases S ⊂ A S \subset A S ⊂ A given by Lemma A.5. We compute
E S ∼ P E ( A , S ) = ∑ x , y ∈ A Pr [ x , y ∈ S ] ⋅ ∣ ( A + x ) ∩ ( A + y ) ∣ = ( d + 1 ) ∣ A ∣ + ∑ x , y ∈ A x ≠ y Pr [ x , y ∈ S ] ⋅ ∣ A ∩ ( A + x − y ) ∣ ≤ ( d + 1 ) ∣ A ∣ + ∑ x , y ∈ A x ≠ y ( 1 + ∥ x ∥ 2 ) ( 1 + ∥ y ∥ 2 ) − ( 1 + ( x ⋅ y ) ) 2 ∣ A ∣ 2 ⋅ 2 ∣ A ∣ ∥ x − y ∥ 2 . \begin{aligned}
\mathbb{E}_{S\sim\mathcal{P}} E(A,S)=\sum_{x,y\in A}\Pr[x,y\in S]\cdot|(A+x)\cap(A+y)| \\
&=(d+1)|A|+\sum_{\substack{x,y\in A\\x\ne y}}\Pr[x,y\in S]\cdot|A\cap(A+x-y)| \\
&\le(d+1)|A|+\sum_{\substack{x,y\in A\\x\ne y}}\frac{(1+\lVert x\rVert^{2})(1+\lVert y\rVert^{2})-(1+(x\cdot y))^{2}}{|A|^{2}}\cdot\frac{2|A|}{\lVert x-y\rVert^{2}}.
\end{aligned} E S ∼ P E ( A , S ) = x , y ∈ A ∑ Pr [ x , y ∈ S ] ⋅ ∣ ( A + x ) ∩ ( A + y ) ∣ = ( d + 1 ) ∣ A ∣ + x , y ∈ A x = y ∑ Pr [ x , y ∈ S ] ⋅ ∣ A ∩ ( A + x − y ) ∣ ≤ ( d + 1 ) ∣ A ∣ + x , y ∈ A x = y ∑ ∣ A ∣ 2 ( 1 + ∥ x ∥ 2 ) ( 1 + ∥ y ∥ 2 ) − ( 1 + ( x ⋅ y ) ) 2 ⋅ ∥ x − y ∥ 2 2∣ A ∣ .
where in the last line we have used both Lemma A.4 and the conclusion of Lemma A.5. Observe that we have the bound
( 1 + ∥ x ∥ 2 ) ( 1 + ∥ y ∥ 2 ) − ( 1 + ( x ⋅ y ) ) 2 = 1 + ∥ x ∥ 2 + ∥ y ∥ 2 + ∥ x ∥ 2 ∥ y ∥ 2 − 1 − 2 ( x ⋅ y ) − ( x ⋅ y ) 2 = ∥ x − y ∥ 2 + ∥ x ∥ 2 ∥ y ∥ 2 − ( x ⋅ y ) 2 ≤ ∥ x − y ∥ 2 + ( ∥ x ∥ 2 + ∥ y ∥ 2 2 ) 2 − ( x ⋅ y ) 2 = ∥ x − y ∥ 2 ( 1 + ∥ x + y 2 ∥ 2 ) . \begin{aligned}
(1+\lVert x\rVert^{2})(1+\lVert y\rVert^{2})-(1+(x\cdot y))^{2}
&=1+\lVert x\rVert^{2}+\lVert y\rVert^{2}+\lVert x\rVert^{2}\lVert y\rVert^{2}-1-2(x\cdot y)-(x\cdot y)^{2}\\
&=\lVert x-y\rVert^{2}+\lVert x\rVert^{2}\lVert y\rVert^{2}-(x\cdot y)^{2}\\
&\le\lVert x-y\rVert^{2}+\left(\frac{\lVert x\rVert^{2}+\lVert y\rVert^{2}}{2}\right)^{2}-(x\cdot y)^{2}\\
&=\lVert x-y\rVert^{2}\left(1+\left\lVert\frac{x+y}{2}\right\rVert^{2}\right).
\end{aligned} ( 1 + ∥ x ∥ 2 ) ( 1 + ∥ y ∥ 2 ) − ( 1 + ( x ⋅ y ) ) 2 = 1 + ∥ x ∥ 2 + ∥ y ∥ 2 + ∥ x ∥ 2 ∥ y ∥ 2 − 1 − 2 ( x ⋅ y ) − ( x ⋅ y ) 2 = ∥ x − y ∥ 2 + ∥ x ∥ 2 ∥ y ∥ 2 − ( x ⋅ y ) 2 ≤ ∥ x − y ∥ 2 + ( 2 ∥ x ∥ 2 + ∥ y ∥ 2 ) 2 − ( x ⋅ y ) 2 = ∥ x − y ∥ 2 ( 1 + 2 x + y 2 ) .
Thus, we see that
E S ∼ P E ( A , S ) ≤ ( d + 1 ) ∣ A ∣ + 2 ∣ A ∣ ∑ x , y ∈ A x ≠ y ( 1 + ∥ x + y 2 ∥ 2 ) = ( d + 1 ) ∣ A ∣ + 2 ( ∣ A ∣ − 1 ) + 1 2 ∣ A ∣ ∑ x , y ∈ A ( ∥ x ∥ 2 + 2 ( x ⋅ y ) + ∥ y ∥ 2 ) − 2 ∣ A ∣ ∑ x ∈ A ∥ x ∥ 2 . \begin{aligned}
\mathbb{E}_{S\sim\mathcal{P}} E(A,S)\le(d+1)|A|+\frac{2}{|A|}\sum_{\substack{x,y\in A\\x\ne y}}\left(1+\left\lVert\frac{x+y}{2}\right\rVert^{2}\right) \\
&=(d+1)|A|+2(|A|-1)+\frac{1}{2|A|}\sum_{x,y\in A}\left(\lVert x\rVert^{2}+2(x\cdot y)+\lVert y\rVert^{2}\right)-\frac{2}{|A|}\sum_{x\in A}\lVert x\rVert^{2}.
\end{aligned} E S ∼ P E ( A , S ) ≤ ( d + 1 ) ∣ A ∣ + ∣ A ∣ 2 x , y ∈ A x = y ∑ ( 1 + 2 x + y 2 ) = ( d + 1 ) ∣ A ∣ + 2 ( ∣ A ∣ − 1 ) + 2∣ A ∣ 1 x , y ∈ A ∑ ( ∥ x ∥ 2 + 2 ( x ⋅ y ) + ∥ y ∥ 2 ) − ∣ A ∣ 2 x ∈ A ∑ ∥ x ∥ 2 .
Since A A A is in isotropic position, we have that
∑ x ∈ A ∥ x ∥ 2 = tr ∑ x ∈ A x x T = ∣ A ∣ d and ∑ x , y ∈ A x ⋅ y = 0. \sum_{x\in A}\lVert x\rVert^2=\operatorname{tr}\sum_{x\in A}xx^{\mathsf T}=|A|d\quad\text{and}\quad\sum_{x,y\in A}x\cdot y=0. x ∈ A ∑ ∥ x ∥ 2 = tr x ∈ A ∑ x x T = ∣ A ∣ d and x , y ∈ A ∑ x ⋅ y = 0.
This combines with the preceding inequality to give us
E S ∼ P E ( A , S ) ≤ ( d + 3 ) ∣ A ∣ − 2 + d ∣ A ∣ − 2 d = ( 2 d + 3 ) ∣ A ∣ − ( 2 d + 2 ) . \mathop{\mathbb{E}}_{S\sim\mathcal{P}} E(A,S)\leq(d+3)|A|-2+d|A|-2d=(2d+3)|A|-(2d+2). E S ∼ P E ( A , S ) ≤ ( d + 3 ) ∣ A ∣ − 2 + d ∣ A ∣ − 2 d = ( 2 d + 3 ) ∣ A ∣ − ( 2 d + 2 ) .
Taking any S S S with E ( A , S ) ≤ E S ∼ P E ( A , S ) E(A,S)\leq\mathop{\mathbb{E}}_{S\sim\mathcal{P}}E(A,S) E ( A , S ) ≤ E S ∼ P E ( A , S ) gives the result. □ \square □
Remark A.6. The saving in this proof Theorem 1.1 over the trivial bound by a factor of d d d comes primarily from Lemma A.4. Indeed, if A A A is isotropic, one may compute
E x , y ∈ A ∥ x − y ∥ 2 = 2 d , \mathop{\mathbb{E}}_{x,y\in A}\lVert x-y\rVert^2=2d, E x , y ∈ A ∥ x − y ∥ 2 = 2 d ,
where the expectation is over uniformly random points in A A A . So, one might hope that, for a “typical” pair of points x , y ∈ A x,y\in A x , y ∈ A , we have ∥ x − y ∥ 2 ≫ d \lVert x-y\rVert^2\gg d ∥ x − y ∥ 2 ≫ d and thus (by Lemma A.4) ∣ A ∩ ( A + y − x ) ∣ ≪ ∣ A ∣ / d |A\cap(A+y-x)|\ll|A|/d ∣ A ∩ ( A + y − x ) ∣ ≪ ∣ A ∣/ d . If this bound were to hold for all pairs of elements of some S ⊂ A S\subset A S ⊂ A of size on the order of d d d , we would have E ( A , S ) ≪ ∣ A ∣ d E(A,S)\ll|A|d E ( A , S ) ≪ ∣ A ∣ d .
Lemma A.5 provides a particularly clean way of finding (enough) such pairs simultaneously, but there are other approaches as well. One alternative proof (which was also found by GPT-6 Astra) applies the additional computation that, for any set A ⊂ R d A\subset\mathbb{R}^{d} A ⊂ R d in isotropic position and any affine subspace L ⊆ R d L\subseteq\mathbb{R}^{d} L ⊆ R d of dimension r < d r<d r < d , one has
1 ∣ A ∣ ∑ a ∈ A ( inf x ∈ L ∥ a − x ∥ 2 ) ≥ d − r . (39) \frac{1}{|A|}\sum_{a\in A}\left(\inf_{x\in L}\lVert a-x\rVert^2\right)\geq d-r. \tag*{(39)} ∣ A ∣ 1 a ∈ A ∑ ( x ∈ L inf ∥ a − x ∥ 2 ) ≥ d − r . (39)
(That is, isotropic sets do not cluster too strongly around affine subspaces.) The bound (A.1) can be used to greedily construct an affine-independent set S ⊆ A S\subseteq A S ⊆ A of size ⌈ d / 3 ⌉ \lceil d/3\rceil ⌈ d /3 ⌉ such that for any distinct s 1 , s 2 ∈ S s_1,s_2\in S s 1 , s 2 ∈ S , one has ∥ s 1 − s 2 ∥ 2 > 2 d / 3 \lVert s_1-s_2\rVert^2>2d/3 ∥ s 1 − s 2 ∥ 2 > 2 d /3 : at each step, simply add the point in A A A which is furthest away from the affine span of the previously chosen points. Applying Lemma A.4 leads to the bound E ( A , S ) < 3 ∣ A ∣ ∣ S ∣ E(A,S)<3|A||S| E ( A , S ) < 3∣ A ∣∣ S ∣ .
Attaining isotropic position
In this subsection, we prove Lemma A.3. This lemma is certainly not new; see for example [6 Proposition 2.3.3] in the convex setting.
Proof of Lemma A.3. Let m = 1 ∣ A ∣ ∑ a ∈ A a m=\frac{1}{|A|}\sum_{a\in A}a m = ∣ A ∣ 1 ∑ a ∈ A a be the center of mass of a a a , and consider the matrix
M = 1 ∣ A ∣ ∑ a ∈ A ( a − m ) ( a − m ) T . M=\frac{1}{|A|}\sum_{a\in A}(a-m)(a-m)^{\mathsf T}. M = ∣ A ∣ 1 a ∈ A ∑ ( a − m ) ( a − m ) T .
The matrix M M M is symmetric and positive definite: if v ∈ R d ∖ { 0 } v\in\mathbb{R}^{d}\setminus\{0\} v ∈ R d ∖ { 0 } , then
v T M v = 1 ∣ A ∣ ∑ a ∈ A ( ( a − m ) ⋅ v ) 2 . v^{\mathsf T}Mv=\frac{1}{|A|}\sum_{a\in A}((a-m)\cdot v)^2. v T M v = ∣ A ∣ 1 a ∈ A ∑ (( a − m ) ⋅ v ) 2 .
This quantity is positive, since if it were zero then every point a ∈ A a\in A a ∈ A would lie in the hyperplane { x ∈ R d : ( x − m ) ⋅ v = 0 } \{x\in\mathbb{R}^{d}:(x-m)\cdot v=0\} { x ∈ R d : ( x − m ) ⋅ v = 0 } , contradicting the fact that A A A is d d d -dimensional. Since M M M is positive definite, we can write M = N 2 M=N^2 M = N 2 for some positive definite matrix N N N . Then B : = { N − 1 ( a − m ) : a ∈ A } B:=\{N^{-1}(a-m):a\in A\} B := { N − 1 ( a − m ) : a ∈ A } satisfies
1 ∣ B ∣ ∑ b ∈ B b = N − 1 1 ∣ A ∣ ∑ a ∈ A ( a − m ) = 0 \frac{1}{|B|}\sum_{b\in B}b=N^{-1}\frac{1}{|A|}\sum_{a\in A}(a-m)=0 ∣ B ∣ 1 b ∈ B ∑ b = N − 1 ∣ A ∣ 1 a ∈ A ∑ ( a − m ) = 0
and
1 ∣ B ∣ ∑ b ∈ B b b T = 1 ∣ A ∣ ∑ a ∈ A N − 1 ( a − m ) ( a − m ) T N − T = N − 1 ( 1 ∣ A ∣ ∑ a ∈ A ( a − m ) ( a − m ) T ) N − 1 = N − 1 M N − 1 = I d . \begin{aligned}
\frac{1}{|B|}\sum_{b\in B}bb^{\mathsf{T}}=\frac{1}{|A|}\sum_{a\in A}N^{-1}(a-m)(a-m)^{\mathsf{T}}N^{-\mathsf{T}} \\
&=N^{-1}\left(\frac{1}{|A|}\sum_{a\in A}(a-m)(a-m)^{\mathsf{T}}\right)N^{-1}=N^{-1}MN^{-1}=I_d.
\end{aligned} ∣ B ∣ 1 b ∈ B ∑ b b T = ∣ A ∣ 1 a ∈ A ∑ N − 1 ( a − m ) ( a − m ) T N − T = N − 1 ( ∣ A ∣ 1 a ∈ A ∑ ( a − m ) ( a − m ) T ) N − 1 = N − 1 M N − 1 = I d .
So, the affine transformation ρ ( x ) = N − 1 ( x − m ) \rho(x)=N^{-1}(x-m) ρ ( x ) = N − 1 ( x − m ) puts A A A into isotropic position. □ \square □
Intersecting with translates
In this subsection, we prove Lemma A.4. It will be useful to first isolate the following computation: if A A A is in isotropic position, then
∑ a ∈ A ( a ⋅ v ) 2 = v T ( ∑ a ∈ A a a T ) v = v T ( ∣ A ∣ I d ) v = ∣ A ∣ ⋅ ∥ v ∥ 2 . (40) \sum_{a\in A}(a\cdot v)^2=v^{\mathsf{T}}\left(\sum_{a\in A}aa^{\mathsf{T}}\right)v=v^{\mathsf{T}}(|A|I_d)v=|A|\cdot\lVert v\rVert^2. \tag*{(40)} a ∈ A ∑ ( a ⋅ v ) 2 = v T ( a ∈ A ∑ a a T ) v = v T ( ∣ A ∣ I d ) v = ∣ A ∣ ⋅ ∥ v ∥ 2 . (40)
Now, the idea behind the proof of Lemma A.4 is as follows: for a pair of points ( x , x + v ) (x,x+v) ( x , x + v ) which both lie in A A A , the values of x ⋅ v x\cdot v x ⋅ v and ( x + v ) ⋅ v (x+v)\cdot v ( x + v ) ⋅ v differ by at least ∥ v ∥ 2 \lVert v\rVert^2 ∥ v ∥ 2 , and thus contribute at least ( − ∥ v ∥ 2 / 2 ) 2 + ( ∥ v ∥ 2 / 2 ) 2 = ∥ v ∥ 4 / 2 (-\lVert v\rVert^2/2)^2+(\lVert v\rVert^2/2)^2=\lVert v\rVert^4/2 ( − ∥ v ∥ 2 /2 ) 2 + (∥ v ∥ 2 /2 ) 2 = ∥ v ∥ 4 /2 to the sum (A.2). Thus, there cannot be too many such contributions. Carrying this argument through naively loses a factor of two as compared to the statement of Lemma A.4; by being slightly more careful about counting patterns of the form { x , x + v , x + 2 v , … } \{x,x+v,x+2v,\ldots\} { x , x + v , x + 2 v , … } in A A A , we may prove Lemma A.4.
Proof of Lemma A.4. Consider the graph G G G whose vertex set is A A A and where elements x x x and x − v x-v x − v , for any x ∈ A ∩ ( A + v ) x\in A\cap(A+v) x ∈ A ∩ ( A + v ) , are connected by an edge. The graph G G G has ∣ A ∩ ( A + v ) ∣ |A\cap(A+v)| ∣ A ∩ ( A + v ) ∣ edges. The connected components of G G G are paths of the form x , x + v , … , x + ( m − 1 ) v x,x+v,\ldots,x+(m-1)v x , x + v , … , x + ( m − 1 ) v for various x x x and m m m ; let X X X be the set of such pairs ( x , m ) (x,m) ( x , m ) . For ( x , m ) ∈ X (x,m)\in X ( x , m ) ∈ X , we have x + m v ∉ A x+mv\notin A x + m v ∈ / A . We conclude that
A = ⨆ ( x , m ) ∈ X { x , x + v , … , x + ( m − 1 ) v } ; ∣ A ∩ ( A + v ) ∣ = e ( G ) = ∑ ( x , m ) ∈ X ( m − 1 ) . (41) A=\bigsqcup_{(x,m)\in X}\{x,x+v,\ldots,x+(m-1)v\};\qquad|A\cap(A+v)|=e(G)=\sum_{(x,m)\in X}(m-1). \tag*{(41)} A = ( x , m ) ∈ X ⨆ { x , x + v , … , x + ( m − 1 ) v } ; ∣ A ∩ ( A + v ) ∣ = e ( G ) = ( x , m ) ∈ X ∑ ( m − 1 ) . (41)
Now, the subset of A A A corresponding to ( x , m ) ∈ X (x,m)\in X ( x , m ) ∈ X contributes to (A.2) depending on m m m :
∑ k = 0 m − 1 ( ( x + k v ) ⋅ v ) 2 = ∑ k = 0 m − 1 ( x ⋅ v + k ∥ v ∥ 2 ) 2 ≥ ∥ v ∥ 4 min t ∈ R ∑ k = 0 m − 1 ( t + k ) 2 = ∥ v ∥ 4 ∑ k = 0 m − 1 ( − m − 1 2 + k ) 2 = ∥ v ∥ 4 ⋅ 1 12 m ( m 2 − 1 ) . \begin{aligned}
\sum_{k=0}^{m-1}((x+kv)\cdot v)^2
&=\sum_{k=0}^{m-1}(x\cdot v+k\lVert v\rVert^2)^2\\
&\ge\lVert v\rVert^4\min_{t\in\mathbb{R}}\sum_{k=0}^{m-1}(t+k)^2\\
&=\lVert v\rVert^4\sum_{k=0}^{m-1}\left(-\frac{m-1}{2}+k\right)^2
=\lVert v\rVert^4\cdot\frac{1}{12}m(m^2-1).
\end{aligned} k = 0 ∑ m − 1 (( x + k v ) ⋅ v ) 2 = k = 0 ∑ m − 1 ( x ⋅ v + k ∥ v ∥ 2 ) 2 ≥ ∥ v ∥ 4 t ∈ R min k = 0 ∑ m − 1 ( t + k ) 2 = ∥ v ∥ 4 k = 0 ∑ m − 1 ( − 2 m − 1 + k ) 2 = ∥ v ∥ 4 ⋅ 12 1 m ( m 2 − 1 ) .
We conclude from (A.2) and (A.3) that
∣ A ∣ ⋅ ∥ v ∥ 2 = ∑ a ∈ A ( a ⋅ v ) 2 = ∑ ( x , m ) ∈ X ∑ k = 0 m − 1 ( ( x + k v ) ⋅ v ) 2 ≥ ∥ v ∥ 4 ∑ ( x , m ) ∈ X 1 12 m ( m 2 − 1 ) . |A| \cdot\lVert v\rVert^{2} = \sum_{a \in A} (a \cdot v)^{2} = \sum_{(x,m)\in X} \sum_{k=0}^{m-1} ((x+kv)\cdot v)^{2} \ge\lVert v\rVert^{4} \sum_{(x,m)\in X} \frac{1}{12}m(m^{2}-1). ∣ A ∣ ⋅ ∥ v ∥ 2 = a ∈ A ∑ ( a ⋅ v ) 2 = ( x , m ) ∈ X ∑ k = 0 ∑ m − 1 (( x + k v ) ⋅ v ) 2 ≥ ∥ v ∥ 4 ( x , m ) ∈ X ∑ 12 1 m ( m 2 − 1 ) .
Using the inequality 1 6 m ( m 2 − 1 ) ≥ m − 1 \frac{1}{6}m(m^{2}-1) \ge m-1 6 1 m ( m 2 − 1 ) ≥ m − 1 for all m ∈ N m \in\mathbb{N} m ∈ N and (A.3), we obtain the bound
∣ A ∣ ⋅ ∥ v ∥ 2 ≥ ∥ v ∥ 4 ∑ ( x , m ) ∈ X 1 2 ( m − 1 ) = 1 2 ∣ A ∩ ( A + v ) ∣ ⋅ ∥ v ∥ 4 . |A| \cdot\lVert v\rVert^{2} \ge\lVert v\rVert^{4} \sum_{(x,m)\in X} \frac{1}{2}(m-1) = \frac{1}{2}|A \cap(A+v)| \cdot\lVert v\rVert^{4}. ∣ A ∣ ⋅ ∥ v ∥ 2 ≥ ∥ v ∥ 4 ( x , m ) ∈ X ∑ 2 1 ( m − 1 ) = 2 1 ∣ A ∩ ( A + v ) ∣ ⋅ ∥ v ∥ 4 .
Remark A.7. The multiplicative constant 2 in Lemma A.4 is tight. For d = 1 d=1 d = 1 one can take v = 2 e 1 v=2e_{1} v = 2 e 1 and A A A to consist of ∣ A ∣ / 2 |A|/2 ∣ A ∣/2 copies each of e 1 e_{1} e 1 and − e 1 -e_{1} − e 1 (perhaps translated very slightly so that A A A is a set rather than a multiset); for larger d d d , simply add to A A A a regular d d d -simplex in the hyperplane e 1 ⊥ e_{1}^{\perp} e 1 ⊥ at the appropriate scale to make A A A isotropic.
Remark A.8. The idea behind Lemma A.4 — if S S S is a set in isotropic position then the size of the intersection S ∩ ( S + v ) S \cap(S+v) S ∩ ( S + v ) decays as ∥ v ∥ 2 \lVert v\rVert_{2} ∥ v ∥ 2 grows — is not new, although this specific statement seems to be. A similar statement in one dimension was proven by Nishiyama [20 Theorem 1(a)] in the context of total variation between probability distributions on R \mathbb{R} R : from this statement, one can extract the bound
∣ A ∩ ( A + v ) ∣ ≤ 4 ∣ A ∣ ∥ v ∥ 2 2 + 4 |A \cap(A+v)| \le\frac{4|A|}{\lVert v\rVert_{2}^{2}+4} ∣ A ∩ ( A + v ) ∣ ≤ ∥ v ∥ 2 2 + 4 4∣ A ∣
for A A A in isotropic position, which is comparable to Lemma A.4 (and has the advantage of remaining nontrivial even for v v v near zero). In higher dimensions, a version of such a statement also appeared in an early version of a preprint of the second author [25 ] : here, a bound on K ∩ ( K + v ) K \cap(K+v) K ∩ ( K + v ) decaying exponentially in ∥ v ∥ 2 \lVert v\rVert_{2} ∥ v ∥ 2 was proven for a convex body K K K in isotropic position. (Such a bound relies substantially on the convexity of K K K , but a bound decaying quadratically in ∥ v ∥ 2 \lVert v\rVert_{2} ∥ v ∥ 2 is sufficient for our purposes.)
A distribution on affine bases
Finally, we prove Lemma A.5. The probability distribution P \mathcal{P} P constructed in the proof is a fairly classical example of a determinantal probability measure, and all of the facts we need are contained, for example, in the survey article of Lyons [17 ] on the topic. In particular, the distribution we use is discussed in [17 Sections 2 and 5] .
Let X X X be a finite set in R n \mathbb{R}^{n} R n . Given any subset Y ⊂ X Y \subset X Y ⊂ X , write M Y M_{Y} M Y for the n × ∣ Y ∣ n \times|Y| n × ∣ Y ∣ matrix whose columns are the elements of Y Y Y . Note that the matrix M Y M_{Y} M Y is only defined up to permutation of the columns. The associated matrix
M Y M Y T = ∑ x ∈ Y x x T ∈ R n × n M_{Y}M_{Y}^{\mathsf{T}} = \sum_{x\in Y} xx^{\mathsf{T}} \in\mathbb{R}^{n\times n} M Y M Y T = x ∈ Y ∑ x x T ∈ R n × n
is independent of the ordering of the columns of M Y M_{Y} M Y , and is nonsingular whenever Y Y Y spans R n \mathbb{R}^{n} R n . Moreover, the Cauchy–Binet formula gives us
∑ Y ⊂ X ∣ Y ∣ = n det ( M Y ) 2 = ∑ Y ⊂ X ∣ Y ∣ = n det ( M Y M Y T ) = det ( M X M X T ) . (42) \sum_{\substack{Y\subset X\\ |Y|=n}} \det(M_{Y})^{2} = \sum_{\substack{Y\subset X\\ |Y|=n}} \det(M_{Y}M_{Y}^{\mathsf{T}}) = \det(M_{X}M_{X}^{\mathsf{T}}). \tag*{(42)} Y ⊂ X ∣ Y ∣ = n ∑ det ( M Y ) 2 = Y ⊂ X ∣ Y ∣ = n ∑ det ( M Y M Y T ) = det ( M X M X T ) . (42)
If X X X spans R n \mathbb{R}^{n} R n (so that M X M X T M_{X}M_{X}^{\mathsf{T}} M X M X T is nonsingular), then the identity (A.4) inspires the following probability distribution on subsets Y ⊂ X Y \subset X Y ⊂ X of X X X of size n n n : choose Y ⊂ X Y \subset X Y ⊂ X with probability det ( M Y M Y T ) / det ( M X M X T ) \det(M_YM_Y^{\mathsf T})/\det(M_XM_X^{\mathsf T}) det ( M Y M Y T ) / det ( M X M X T ) . Call this distribution P X P_X P X . The support of P X P_X P X is exactly the set of bases of R n \mathbb{R}^n R n contained in X X X . Moreover, in a suitable sense, P X P_X P X places higher weight on bases which are “well spread-out”: if Y Y Y consists of vectors which are close together, then det ( M Y ) \det(M_Y) det ( M Y ) , and consequently det ( M Y M Y T ) \det(M_YM_Y^{\mathsf T}) det ( M Y M Y T ) , will be small.
If P \mathcal{P} P is a determinantal probability measure on subsets Y Y Y of a ground set X X X , it turns out that one can explicitly compute the probability that a particular subset T ⊂ X T\subset X T ⊂ X is contained within Y ∼ P Y\sim\mathcal{P} Y ∼ P . In our setting of interest, this is essentially the content of [17 Theorem 5.1] .
Lemma A.9. Let X ⊂ R n X\subset\mathbb{R}^n X ⊂ R n . Let T ⊂ X T\subset X T ⊂ X be fixed, and sample Y ∼ P X Y\sim P_X Y ∼ P X . Then
Pr [ T ⊂ Y ] = det ( M T T ( M X M X T ) − 1 M T ) . \Pr[T\subset Y]=\det\left(M_T^{\mathsf T}(M_XM_X^{\mathsf T})^{-1}M_T\right). Pr [ T ⊂ Y ] = det ( M T T ( M X M X T ) − 1 M T ) .
Note that, if ∣ T ∣ = n |T|=n ∣ T ∣ = n , this probability reduces to det ( M T M T T ) / det ( M X M X T ) \det(M_TM_T^{\mathsf T})/\det(M_XM_X^{\mathsf T}) det ( M T M T T ) / det ( M X M X T ) , and Lemma A.9 collapses to the definition of P X P_X P X .
For completeness of exposition, we present a proof of Lemma A.9 using the Cauchy–Binet formula and Schur complements, which is essentially equivalent to the proof given in [17 ] .
Proof of Lemma A.9. Let k = ∣ T ∣ k=|T| k = ∣ T ∣ . Note that the definition of P X P_X P X commutes with linear transformations, that is, if L : R n → R n L:\mathbb{R}^n\to\mathbb{R}^n L : R n → R n is an invertible linear map, the distribution found by sampling Y ∼ P X Y\sim P_X Y ∼ P X and applying L L L to each element of Y Y Y is the same as the distribution P L X P_{LX} P L X . If T T T is linearly dependent, then Pr [ T ⊂ Y ] = 0 \Pr[T\subset Y]=0 Pr [ T ⊂ Y ] = 0 while the matrix M T T ( M X M X T ) − 1 M T M_T^{\mathsf T}(M_XM_X^{\mathsf T})^{-1}M_T M T T ( M X M X T ) − 1 M T has rank strictly less than ∣ T ∣ |T| ∣ T ∣ , and so there is nothing to prove. As such, we may assume T T T is linearly independent (in particular, k ≤ n k\le n k ≤ n ), and thus a change of basis allows us to assume that T = { e 1 , … , e k } T=\{e_1,\ldots,e_k\} T = { e 1 , … , e k } .
For each element x ∈ X x\in X x ∈ X , write u x ∈ R k u_x\in\mathbb{R}^k u x ∈ R k (resp. v x ∈ R n − k v_x\in\mathbb{R}^{n-k} v x ∈ R n − k ) for the first k k k (resp. last n − k n-k n − k ) entries of x x x . Write Z : = { v x : x ∈ X ∖ T } Z:=\{v_x:x\in X\setminus T\} Z := { v x : x ∈ X ∖ T } . Consider some set T ⊂ Y ⊂ X T\subset Y\subset X T ⊂ Y ⊂ X with ∣ Y ∣ = n |Y|=n ∣ Y ∣ = n , and write Y = T ⊔ T ′ Y=T\sqcup T' Y = T ⊔ T ′ . The matrix M Y M_Y M Y has k k k columns e 1 , … , e k e_1,\ldots,e_k e 1 , … , e k and n − k n-k n − k columns of the form u x ⊕ v x u_x\oplus v_x u x ⊕ v x for each x ∈ T ′ x\in T' x ∈ T ′ . As a result,
det ( M Y ) 2 = det ( I k ∗ 0 M { v x : x ∈ T ′ } ) 2 = det ( M { v x : x ∈ T ′ } ) 2 . \det(M_Y)^2=\det\begin{pmatrix} I_k & * \\ 0 & M_{\{v_x:x\in T'\}} \end{pmatrix}^2=\det\left(M_{\{v_x:x\in T'\}}\right)^2. det ( M Y ) 2 = det ( I k 0 ∗ M { v x : x ∈ T ′ } ) 2 = det ( M { v x : x ∈ T ′ } ) 2 .
This enables us to compute
det ( M X M X T ) ⋅ Pr [ T ⊂ Y ] = ∑ T ⊂ Y ⊂ X ∣ Y ∣ = n det ( M Y ) 2 = ∑ T ′ ⊂ X ∖ T ∣ T ′ ∣ = n − k det ( M T ⊔ T ′ ) 2 = ∑ T ′ ′ ⊂ Z ∣ T ′ ′ ∣ = n − k det ( M T ′ ′ ) 2 = det ( ∑ v ∈ Z v v T ) , \begin{aligned}
\det(M_XM_X^{\mathsf T})\cdot\Pr[T\subset Y]
=
\sum_{\substack{T\subset Y\subset X\\ |Y|=n}}\det(M_Y)^2 \\
&=
\sum_{\substack{T'\subset X\setminus T\\ |T'|=n-k}}\det(M_{T\sqcup T'})^2
=
\sum_{\substack{T''\subset Z\\ |T''|=n-k}}\det(M_{T''})^2
=
\det\left(\sum_{v\in Z}vv^{\mathsf T}\right),
\end{aligned} det ( M X M X T ) ⋅ Pr [ T ⊂ Y ] = T ⊂ Y ⊂ X ∣ Y ∣ = n ∑ det ( M Y ) 2 = T ′ ⊂ X ∖ T ∣ T ′ ∣ = n − k ∑ det ( M T ⊔ T ′ ) 2 = T ′′ ⊂ Z ∣ T ′′ ∣ = n − k ∑ det ( M T ′′ ) 2 = det ( v ∈ Z ∑ v v T ) ,
where we have used the Cauchy–Binet formula in the last equality.
Now, consider the block decompositions
M X M X T = ( N 00 N 01 N 10 N 11 ) and ( M X M X T ) − 1 = ( N ~ 00 N ~ 01 N ~ 10 N ~ 11 ) , M_XM_X^{\mathsf T}=
\begin{pmatrix}
N_{00} & N_{01}\\
N_{10} & N_{11}
\end{pmatrix}
\qquad\text{and}\qquad
(M_XM_X^{\mathsf T})^{-1}=
\begin{pmatrix}
\widetilde N_{00} & \widetilde N_{01}\\
\widetilde N_{10} & \widetilde N_{11}
\end{pmatrix}, M X M X T = ( N 00 N 10 N 01 N 11 ) and ( M X M X T ) − 1 = ( N 00 N 10 N 01 N 11 ) ,
where N 00 , N ~ 00 ∈ R k × k N_{00},\widetilde N_{00}\in\mathbb{R}^{k\times k} N 00 , N 00 ∈ R k × k and N 11 , N ~ 11 ∈ R ( n − k ) × ( n − k ) N_{11},\widetilde N_{11}\in\mathbb{R}^{(n-k)\times(n-k)} N 11 , N 11 ∈ R ( n − k ) × ( n − k ) . Our previous computation shows that
Pr [ T ⊂ Y ] = det ( M X M X T ) − 1 det ( ∑ v ∈ Z v v T ) = det N 11 det ( M X M X T ) . (43) \Pr[T\subset Y]=\det(M_XM_X^{\mathsf T})^{-1}\det\left(\sum_{v\in Z}vv^{\mathsf T}\right)
=\frac{\det N_{11}}{\det(M_XM_X^{\mathsf T})}. \tag*{(43)} Pr [ T ⊂ Y ] = det ( M X M X T ) − 1 det ( v ∈ Z ∑ v v T ) = det ( M X M X T ) det N 11 . (43)
On the other hand, we have
M T T ( M X M X T ) − 1 M T = ( I k 0 ) ( N ~ 00 N ~ 01 N ~ 10 N ~ 11 ) ( I k 0 ) = N ~ 00 . (44) M_T^{\mathsf T}(M_XM_X^{\mathsf T})^{-1}M_T=(I_k\ \ 0)\begin{pmatrix}\widetilde{N}_{00} & \widetilde{N}_{01}\\ \widetilde{N}_{10} & \widetilde{N}_{11}\end{pmatrix}\begin{pmatrix}I_k\\ 0\end{pmatrix}=\widetilde{N}_{00}. \tag*{(44)} M T T ( M X M X T ) − 1 M T = ( I k 0 ) ( N 00 N 10 N 01 N 11 ) ( I k 0 ) = N 00 . (44)
Now, we compute
\begin{pmatrix}N_{00} & N_{01}\\ N_{10} & N_{11}\end{pmatrix}
\begin{pmatrix}I_k & 0\\ -N_{11}^{-1}N_{10} & I_{n-k}\end{pmatrix}
=
\begin{pmatrix}N_{00}-N_{01}N_{11}^{-1}N_{10} & N_{01}\\ 0 & N_{11}\end{pmatrix}. \tag*{(45)}\end{pmatrix}
Taking determinants in (A.7) gives det ( M X M X T ) = det N 11 det ( N 00 − N 01 N 11 − 1 N 10 ) \det(M_XM_X^{\mathsf T})=\det N_{11}\det(N_{00}-N_{01}N_{11}^{-1}N_{10}) det ( M X M X T ) = det N 11 det ( N 00 − N 01 N 11 − 1 N 10 ) , while inverting (A.7) we find N ~ 00 = ( N 00 − N 01 N 11 − 1 N 10 ) − 1 \widetilde{N}_{00}=(N_{00}-N_{01}N_{11}^{-1}N_{10})^{-1} N 00 = ( N 00 − N 01 N 11 − 1 N 10 ) − 1 . That is,
det ( M X M X T ) = det N 11 det ( N 00 − N 01 N 11 − 1 N 10 ) = det N 11 det N ~ 00 . \det(M_XM_X^{\mathsf T})=\det N_{11}\det(N_{00}-N_{01}N_{11}^{-1}N_{10})=\frac{\det N_{11}}{\det\widetilde{N}_{00}}. det ( M X M X T ) = det N 11 det ( N 00 − N 01 N 11 − 1 N 10 ) = det N 00 det N 11 .
The result now follows from (A.5) and (A.6). □
We now begin to apply Lemma A.9 to our setting. If M X M X T = λ I n M_XM_X^{\mathsf T}=\lambda I_n M X M X T = λ I n for some scalar λ \lambda λ and T = { x , y } T=\{x,y\} T = { x , y } is a two-element set, we have
det ( M T T M X − T M X − 1 M T ) = ∣ λ − 1 x T x λ − 1 x T y λ − 1 y T x λ − 1 y T y ∣ = λ − 2 ( ∥ x ∥ 2 ∥ y ∥ 2 − ( x ⋅ y ) 2 ) . (46) \det(M_T^{\mathsf T}M_X^{-{\mathsf T}}M_X^{-1}M_T)=\left|\begin{matrix}\lambda^{-1}x^{\mathsf T}x & \lambda^{-1}x^{\mathsf T}y\\ \lambda^{-1}y^{\mathsf T}x & \lambda^{-1}y^{\mathsf T}y\end{matrix}\right|=\lambda^{-2}\left(\lVert x\rVert^2\lVert y\rVert^2-(x\cdot y)^2\right). \tag*{(46)} det ( M T T M X − T M X − 1 M T ) = λ − 1 x T x λ − 1 y T x λ − 1 x T y λ − 1 y T y = λ − 2 ( ∥ x ∥ 2 ∥ y ∥ 2 − ( x ⋅ y ) 2 ) . (46)
With this computation and Lemma A.9 in hand, we can now prove Lemma A.5.
Proof of Lemma A.5. Writing X = { ( a ⊕ 1 ) : a ∈ A } ⊂ R d + 1 X=\{(a\oplus1):a\in A\}\subset\mathbb{R}^{d+1} X = {( a ⊕ 1 ) : a ∈ A } ⊂ R d + 1 , we have
∑ x ∈ X x x T = ( ∑ a ∈ A a a T ∑ a ∈ A a ∑ a ∈ A a T ∑ a ∈ A 1 ) = ∣ A ∣ ⋅ I d + 1 . \sum_{x\in X}xx^{\mathsf T}=
\begin{pmatrix}\sum_{a\in A}aa^{\mathsf T} & \sum_{a\in A}a\\ \sum_{a\in A}a^{\mathsf T} & \sum_{a\in A}1\end{pmatrix}
=|A|\cdot I_{d+1}. x ∈ X ∑ x x T = ( ∑ a ∈ A a a T ∑ a ∈ A a T ∑ a ∈ A a ∑ a ∈ A 1 ) = ∣ A ∣ ⋅ I d + 1 .
Consider the distribution P X \mathcal{P}_X P X supported on bases of R d + 1 \mathbb{R}^{d+1} R d + 1 contained in X X X of size d + 1 d+1 d + 1 . By the map a ⊕ 1 ↦ a a\oplus1\mapsto a a ⊕ 1 ↦ a , we can form a corresponding distribution P \mathcal{P} P on subsets of A A A of size d + 1 d+1 d + 1 ; since a 1 , … , a d + 1 a_1,\ldots,a_{d+1} a 1 , … , a d + 1 are affine-independent if and only if a 1 ⊕ 1 , … , a d + 1 ⊕ 1 a_1\oplus1,\ldots,a_{d+1}\oplus1 a 1 ⊕ 1 , … , a d + 1 ⊕ 1 are linearly independent, the support of P \mathcal{P} P is exactly the set of affine bases of R d \mathbb{R}^d R d contained in A A A . So, applying Lemma A.9 with (A.8), we have for x , y ∈ A x,y\in A x , y ∈ A that
Pr S ∼ P [ x , y ∈ S ] = Pr Y ∼ P X [ x ⊕ 1 , y ⊕ 1 ∈ Y ] = ∥ x ⊕ 1 ∥ 2 ∥ y ⊕ 1 ∥ 2 − ( ( x ⊕ 1 ) ⋅ ( y ⊕ 1 ) ) 2 ∣ A ∣ 2 = ( 1 + ∥ x ∥ 2 ) ( 1 + ∥ y ∥ 2 ) − ( 1 + ( x ⋅ y ) ) 2 ∣ A ∣ 2 . \begin{aligned}
\Pr_{S\sim\mathcal{P}}[x,y\in S]=\Pr_{Y\sim\mathcal{P}_X}[x\oplus1,y\oplus1\in Y] \\
&=\frac{\lVert x\oplus1\rVert^2\lVert y\oplus1\rVert^2-((x\oplus1)\cdot(y\oplus1))^2}{|A|^2} \\
&=\frac{(1+\lVert x\rVert^2)(1+\lVert y\rVert^2)-(1+(x\cdot y))^2}{|A|^2}.
\end{aligned} S ∼ P Pr [ x , y ∈ S ] = Y ∼ P X Pr [ x ⊕ 1 , y ⊕ 1 ∈ Y ] = ∣ A ∣ 2 ∥ x ⊕ 1 ∥ 2 ∥ y ⊕ 1 ∥ 2 − (( x ⊕ 1 ) ⋅ ( y ⊕ 1 ) ) 2 = ∣ A ∣ 2 ( 1 + ∥ x ∥ 2 ) ( 1 + ∥ y ∥ 2 ) − ( 1 + ( x ⋅ y ) ) 2 .
Email address: Akshat.Mudgal@warwick.ac.uk
Mathematics Institute, Zeeman Building, University of Warwick, Coventry CV4 7AL, UK
Email address: carlsch@stanford.edu
Department of Mathematics, Stanford University, Stanford, CA 94305, USA
Email address: zakhdm@mit.edu
Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA