Remarks on the inverse Littlewood conjecture Thomas F. Bloom, Ben Green Abstract . The Littlewood conjecture, proven by Konyagin and McGehee-Pigno-Smith in the 1980s, states that if A ⊂ ℤ A\subset\mathbb{Z} is a finite set of integers with | A | = N \lvert A\rvert=N then ‖ 1 A ^ ‖ 1 ⩾ c ​ log ⁡ N \|\widehat{1_{A}}\|_{1}\geqslant c\log N for some absolute constant c > 0 c>0 . We explore what structure A A must have if ‖ 1 A ^ ‖ 1 ⩽ K ​ log ⁡ N \|\widehat{1_{A}}\|_{1}\leqslant K\log N for some constant K K . Under such an assumption we prove, for instance, that A A contains a subset A ′ ⊆ A A^{\prime}\subseteq A with | A | ⩾ N 0.99 \lvert A\rvert\geqslant N^{0.99} such that | A ′ + A ′ | ≪ K O ⁡ ( 1 ) ​ | A ′ | \lvert A^{\prime}+A^{\prime}\rvert\ll K^{O(1)}\lvert A^{\prime}\rvert . As a consequence, for any k ⩾ 3 k\geqslant 3 , if N N is sufficiently large depending on k k and K K , then A A must contain an arithmetic progression of length k k . A byproduct of our analysis is a (slightly) improved bound for the constant c c . 1. Introduction For a finite set A\subset\mathbf{Z} the Fourier transform \widehat{1_{A}}:\mathbf{R}/\mathbf{Z}\to\mathbf{C} is defined by \widehat{1_{A}}(\theta)=\sum_{n\in A}e(-n\theta) , where e(x):=e^{2\pi ix} . Define \|\widehat{1_{A}}\|_{1}=\int_{0}^{1}\lvert\widehat{1_{A}}(\theta)\rvert\,\mathrm{d}\theta. A famous conjecture of Littlewood stated that 1 1 1 We use the Vinogradov notation f\gg g , equivalent to g=O(f) , to denote the existence of some absolute constant c>0 such that \left\lvert f(x)\right\rvert\geqslant c\left\lvert g(x)\right\rvert for all sufficiently large x . \|\widehat{1_{A}}\|_{1}\gg\log N for any set A of N integers, which is achieved for example by an arithmetic progression of length N . This was proved in 1981 independently by Konyagin [ 11 ] and McGehee, Pigno, and Smith [ 12 ] . A discussion of the problem and its history may be found in [ 3 , Chapter 10] . This lower bound is universal, yet rarely achieved – in fact generically we expect \|\widehat{1_{A}}\|_{1} to be closer to the trivial upper bound N^{1/2} , which is an immediate consequence of the Cauchy-Schwarz inequality and Parseval’s identity. This is achieved when A is lacunary, for example, or a random positive density subset of an interval (with high probability). In fact, the only examples we know that achieve O(\log N) are arithmetic progressions and simple variations, for example the union of O(1) arithmetic progressions and some small unstructured set. It is therefore natural, especially from the viewpoint of modern additive combinatorics, to ask the following inverse question. Question 1.1 . Let K>0 be some large constant. What can we say about the structure of sets A\subset\mathbf{Z} with \left\lvert A\right\rvert=N and \|\widehat{1_{A}}\|_{1}\leqslant K\log N ? This question was asked by the second author [ 7 ] and one possible precise conjecture in this direction was formulated by Petridis [ 13 , Question 5.1] (see Section 6 for further details). While we are some way from a full resolution of this question, in this paper we offer the following weak partial progress. Recall that the additive energy E(B) of a finite set B\subset\mathbf{Z} is defined by E(B)=\#\{(b_{1},b_{2},b_{3},b_{4})\in B^{4}:b_{1}+b_{2}=b_{3}+b_{4}\}. (1.1) We have E(B)=\int^{1}_{0}|\widehat{1_{B}}(\theta)|^{4}d\theta, (1.2) as can be checked using the orthogonality relation for characters. We also write \omega[B]:=E(B)/|B|^{3} for the normalised additive energy of B , which satisfies 0<\omega[B]\leqslant 1 . Theorem 1.2 . Let N be a sufficiently large positive integer. Let \delta\in(0,\frac{1}{2}] and K>0 . If A is a set of N integers such that \|\widehat{1_{A}}\|_{1}\leqslant K\log N then there is a subset A^{\prime}\subseteq A of size \left\lvert A^{\prime}\right\rvert\gg N^{1-\delta} such that \omega[A^{\prime}]\gg(\delta/K)^{2} . The set A^{\prime} produced in Theorem 1.2 is in fact an initial segment of A . The following two corollaries are almost immediate consequences of this and standard results in additive combinatorics. Corollary 1.3 . Let N be a sufficiently large positive integer. Let K>0 and suppose that A\subset\mathbf{Z} is a finite set of size N such that \|\widehat{1_{A}}\|_{1}\leqslant K\log N . Then there exists an arithmetic progression P of length \geqslant N^{c_{K}} such that \left\lvert A\cap P\right\rvert\geqslant c_{K}\left\lvert P\right\rvert , where c_{K}>0 depends only on K . Proof. Apply Theorem 1.2 with \delta=\frac{1}{2} . Applying the Balog-Szemerédi-Gowers theorem (see, for example, [ 16 , Theorem 2.31] ) to the resulting set A^{\prime} , we obtain a set A^{\prime\prime}\subseteq A , |A^{\prime\prime}|\gg K^{-O(1)}N^{1/2} , with \left\lvert A^{\prime\prime}+A^{\prime\prime}\right\rvert\leqslant K^{O(1)}\lvert A^{\prime\prime}\rvert . By the Freiman-Ruzsa theorem (see, for example [ 16 , Theorem 5.33] ), there are arithmetic progressions P_{1},\ldots,P_{r} with r=O_{K}(1) such that A^{\prime\prime}\subseteq P_{1}+\cdots+P_{r} and \left\lvert P_{1}+\cdots+P_{r}\right\rvert=\left\lvert P_{1}\right\rvert\cdots\left\lvert P_{r}\right\rvert\ll_{K}\left\lvert A^{\prime\prime}\right\rvert. By averaging there exists some i , 1\leqslant i\leqslant r , and x such that \left\lvert(P_{i}+x)\cap A^{\prime\prime}\right\rvert\gg_{K}\left\lvert P_{i}\right\rvert\gg_{K}\left\lvert A^{\prime\prime}\right\rvert^{1/r}. Since N is large, the length of P_{i} is bounded below by N^{c_{K}} for some c_{K}>0 . ∎ Corollary 1.4 . Let K>0 and let k\geqslant 3 be an integer. Let N be sufficiently large in terms of k,K and let A\subset\mathbf{Z} be a finite set of size N such that \|\widehat{1_{A}}\|_{1}\leqslant K\log N . Then A contains an arithmetic progression of length k . Proof. This follows immediately from Corollary 1.3 and Szemerédi’s theorem. ∎ Remark . The key feature of Theorem 1.2 is that the lower bound on E(A^{\prime}) is a constant times |A^{\prime}|^{3} . If one is prepared to tolerate logarithmic losses then a one line application of Hölder’s inequality on the Fourier side shows that we in fact have E(A)\geqslant N^{3}/(K\log N)^{2} . However, this would certainly be too weak to deduce Corollary 1.4 given our current knowledge of bounds in Szemerédi’s theorem when k\geqslant 4 . 1.1. Previous structural results We now summarise what was previously known concerning this inverse question for sets with small \|\widehat{1_{A}}\|_{1} . • As noted above, it is a trivial consequence of Hölder’s inequality that A itself must have reasonably large additive energy: E(A)\geqslant N^{3}/(K\log N)^{2} . • Pichorides [ 14 , Lemma 3] noted that an argument of Zygmund [ 18 , Chapter XII, 7.6] implies that the largest dissociated 2 2 2 A set X\subset\mathbf{Z} is dissociated if all 2^{\left\lvert X\right\rvert} subset sums are distinct. subset of A has size O_{K}((\log N)^{3}) . This was independently rediscovered by Bedert [ 1 ] . • Petridis [ 13 ] showed that A cannot have genuine 3-dimensional structure, in a certain precise sense. • Picking up on the theme of Petridis, Hanson [ 8 ] showed that A cannot have genuine 2-dimensional structure, again in a sense he was able to make precise. • If we replace the upper bound \leqslant K\log N with \leqslant K , and replace \mathbf{Z} with a finite abelian group G , then a much more satisfactory answer is known: the second author and Sanders [ 6 ] have shown that if A\subseteq G has \|\widehat{1_{A}}\|_{1}\leqslant K then 1_{A} can be written as a simple linear combination of O_{K}(1) indicator functions of cosets of subgroups of G . This condition is (qualitatively) necessary and sufficient. Part of the motivation for inverse results of this nature originated in work of Bourgain [ 2 ] , which highlighted a connection between Littlewood’s conjecture and the task of improving the lower bounds for the sum-free subset problem in additive combinatorics. Bedert [ 1 ] has made significant progress on this problem recently, making use of that connection. 1.2. Bounds for the Littlewood conjecture The lower bound \|\widehat{1_{A}}\|_{1}\gg\log N is the best possible up to an absolute constant, since this is achieved when A is an arithmetic progression of length N . In this case, one may compute (see, for example, [ 18 , II.12.1] ) that \|\widehat{1_{A}}\|_{1}=\frac{4}{\pi^{2}}\log N+O(1). One may ask (and Hardy and Littlewood did ask [ 10 , p 167] ) whether this leading constant is the best possible or even whether \|\widehat{1_{A}}\|_{1}\geqslant\|\widehat{1_{P}}\|_{1} where P is an arithmetic progression of length N . This statement, or the slightly weaker statement that \|\widehat{1_{A}}\|_{1}\geqslant(\frac{4}{\pi^{2}}-o(1))\log N , is usually called the Strong Littlewood Conjecture . Less ambitiously, one can seek to prove the best possible value of c in an inequality \|\widehat{1_{A}}\|_{1}\geqslant(c-o(1))\log N. The argument of McGehee, Pigno, and Smith [ 12 ] achieved c=1/30 . The numerics were optimised by Stegeman [ 15 ] and Yabuta [ 17 ] , the latter proving a value of c\approx 0.1295 . We give a slight improvement on this constant. Theorem 1.5 . If A\subset\mathbf{Z} is a finite set of size N then \|\widehat{1_{A}}\|_{1}\geqslant(c-o(1))\log N where c=0.1422917\cdots . For comparison note that 4/\pi^{2}\approx 0.405 so we are still about a factor of 3 away from the optimal value. The value of c is found as the maximum of a complicated two-variable expression and presumably has no nicer form. The proofs of Theorems 1.2 and 1.5 both hinge on a detailed analysis of the test functions used by McGehee, Pigno, and Smith. This is the main business of the paper. In the final section of the paper we make some additional comments and record some further questions and conjectures. Notation For any function f\in\ell^{1}(\mathbf{Z}) we define the Fourier transform \widehat{f}:[0,1]\to\mathbf{C} by \widehat{f}(\theta)=\sum_{n}f(n)e(-n\theta), where e(x)=e^{2\pi ix} . The convolution is defined in the usual way, so that if f,g\in\ell^{1}(\mathbf{Z}) then f\ast g(x)=\sum_{y}f(y)g(x-y). Note that if A=\mathrm{supp}(f) and B=\mathrm{supp}(g) then \mathrm{supp}(f\ast g)\subseteq A+B . All of the functions we consider will have finite support, so there are no issues of convergence. We note here the useful property that \widehat{f\ast g}=\widehat{f}\cdot\widehat{g} . It is convenient to use inner product notation, so that if f,g:\mathbf{Z}\to\mathbf{C} we write \langle f,g\rangle=\sum_{n\in\mathbf{Z}}f(n)\overline{g(n)}, and \langle\widehat{f},\widehat{g}\rangle=\int_{0}^{1}\widehat{f}(\theta)\overline{\widehat{g}(\theta)}\,\mathrm{d}\theta . By Parseval’s identity \langle f,g\rangle=\langle\widehat{f},\widehat{g}\rangle. 2. McGehee-Pigno-Smith test functions The overall strategy to prove Theorem 1.2 is to mimic proofs of the Littlewood conjecture, aiming to prove a lower bound of the shape \|\widehat{1_{A}}\|_{1}>K\log N . Since this lower bound is false by assumption, some stage in our purported proof must fail, which will reveal structural information about A . All proofs of the Littlewood conjecture follow a similar strategy, obtaining a lower bound for \|\widehat{1}_{A}\|_{1} via construction of a suitable test function. In particular, our goal will be to try to construct a test function \mathcal{R}:\mathbf{Z}\to\mathbf{C} such that (1) \|\widehat{\mathcal{R}}\|_{\infty}\leqslant 1 and (2) \langle 1_{A},\mathcal{R}\rangle>K\log N . By Parseval’s identity and the triangle inequality these facts combined imply \|\widehat{1_{A}}\|_{1}>K\log N . This contradicts our hypothesis, so the construction of such a test function must fail. The new observation is that, examining the details of the construction of the test function, this yields some additive information about A . We will use the test functions of McGehee, Pigno, and Smith [ 12 ] . These are not the only ones capable of proving the Littlewood conjecture but, of the ones we are aware of, they perform the best from the quantitative point of view. For a discussion of other possible test functions we refer to the survey paper of Fournier [ 4 ] . The following lemma details the construction of these test functions. Lemma 2.1 . Let b>0 and set c=1-e^{-b} . If f:\mathbf{Z}\to\mathbf{R} is a finitely supported function then there exists a function \mathcal{R}_{f}:\mathbf{Z}\to\mathbf{C} ( which depends on b ) with the following properties: (1) \mathcal{R}_{f} is supported on \mathbf{Z}_{\leqslant 0} ; (2) \left\lVert\mathcal{R}_{f}\right\rVert_{2}\leqslant 2^{1/2}b\left\lVert f\right\rVert_{2} ; (3) \|\widehat{\mathcal{R}_{f}}+1\|_{\infty}\leqslant 1 ; and (4) if \|\widehat{f}\|_{\infty}\leqslant 1 then, for any g:\mathbf{Z}\to\mathbf{C} with \|\widehat{g}\|_{\infty}\leqslant 1 , the function h:=g+cf+g\ast\mathcal{R}_{f} satisfies \|\widehat{h}\|_{\infty}\leqslant 1 . Proof. Since \lvert\widehat{f}\rvert is a 1 -periodic symmetric function we can write \lvert\widehat{f}(\theta)\rvert=\sum_{n\in\mathbf{Z}}c_{n}e(n\theta) for some c_{n}\in\mathbf{R} with c_{n}=c_{-n} , and define h_{f}:\mathbf{Z}\to\mathbf{C} by h_{f}(n)=\begin{cases}c_{0}&\textrm{if }n=0\\ 2c_{n}&\textrm{ if }n<0\textrm{, and}\\ 0&\textrm{otherwise,}\end{cases} so that h_{f} is supported on \mathbf{Z}_{\leqslant 0} . Furthermore, since \widehat{h_{f}}(\theta)=c_{0}+2\sum_{n<0}c_{n}e(n\theta), for any \theta\in\mathbf{R}/\mathbf{Z} we have \Re\widehat{h_{f}}(\theta)=c_{0}+\sum_{n<0}c_{n}(e(n\theta)+e(-n\theta))=\lvert\widehat{f}(\theta)\rvert\geqslant 0. By Parseval’s theorem, \left\lVert h_{f}\right\rVert_{2}^{2}=c_{0}^{2}+2\sum_{n\neq 0}c_{n}^{2}\leqslant 2\sum_{n}c_{n}^{2}=2\|f\|_{2}^{2}. We may now define \mathcal{R}_{f}(n)=\sum_{j\geqslant 1}\frac{(-b)^{j}}{j!}h_{f}^{(j)}(n), where h_{f}^{(j)}=h_{f}\ast\cdots\ast h_{f} denotes the j -fold convolution. Equivalently, we may define \mathcal{R}_{f} via its Fourier transform by \widehat{\mathcal{R}_{f}}(\theta)=\sum_{j\geqslant 1}\frac{(-b)^{j}}{j!}\widehat{h_{f}}(\theta)^{j}=e^{-b\widehat{h_{f}}(\theta)}-1. Since \mathrm{supp}(g_{1}\ast g_{2})\subseteq\mathrm{supp}(g_{1})+\mathrm{supp}(g_{2}) for any pair of functions g_{1},g_{2}:\mathbf{Z}\rightarrow\mathbf{C} , it is clear that \mathcal{R}_{f} is supported on \mathbf{Z}_{\leqslant 0} , which is item (1). The inequality \left\lvert e^{-z}-1\right\rvert\leqslant\left\lvert z\right\rvert , valid whenever \Re z\geqslant 0 , implies \lvert\widehat{\mathcal{R}_{f}}(\theta)\rvert\leqslant b\lvert\widehat{h_{f}}(\theta)\rvert pointwise, and hence in particular \left\lVert\mathcal{R}_{f}\right\rVert_{2}\leqslant b\left\lVert h_{f}\right\rVert_{2}\leqslant 2^{1/2}b\left\lVert f\right\rVert_{2}, which is item (2). We also have \lvert\widehat{\mathcal{R}_{f}}(\theta)+1\rvert=e^{-b\Re\widehat{h_{f}}(\theta)}=e^{-b\lvert\widehat{f}(\theta)\rvert}\leqslant 1 pointwise, which is (3). Finally, suppose \|\widehat{f}\|_{\infty},\|\widehat{g}\|_{\infty}\leqslant 1 and consider h=cf+g+g\ast\mathcal{R}_{f}, where c=1-e^{-b} . Taking the Fourier transform, we have the pointwise inequality \lvert\widehat{h}\rvert\leqslant\lvert\widehat{g}\rvert\lvert 1+\widehat{\mathcal{R}_{f}}\rvert+c\lvert\widehat{f}\rvert\leqslant e^{-b\lvert\widehat{f}\rvert}+(1-e^{-b})\lvert\widehat{f}\rvert\leqslant 1, which is (4). In the final step here we used the inequality e^{-bx}+(1-e^{-b})x\leqslant 1 , which is valid for all x with 0\leqslant x\leqslant 1 . ∎ The form of item (4) lends itself to an iterative argument, the details of which are as follows. Lemma 2.2 . Let b>0 and c=1-e^{-b} . Let J\in\mathbf{N} and suppose that g_{1},\ldots,g_{J}:\mathbf{Z}\to\mathbf{R} are finitely supported functions such that \|\widehat{g_{i}}\|_{\infty}\leqslant 1 for all i=1,\dots,J . Then there exists a test function \mathcal{R}:\mathbf{Z}\to\mathbf{C} such that \|\widehat{\mathcal{R}}\|_{\infty}\leqslant 1 and \mathcal{R}=c\sum_{j=1}^{J}g_{j}+\sum_{j=1}^{J}D_{j}, (2.1) where the function D_{j} has the shape D_{j}=c\sum_{1\leqslant i0 be a real parameter, and let J\in\mathbf{N} . Let A\subset\mathbf{Z} be a finite set and suppose that A_{1},\dots,A_{J} are initial segments of A with A_{1}\subseteq\cdots\subseteq A_{J} . Let \lambda>1 be a parameter, and suppose that \left\lvert A_{j+1}\right\rvert\geqslant\lambda\left\lvert A_{j}\right\rvert for j=1,\dots,J . Then \|\widehat{1_{A}}\|_{1}\geqslant(1-e^{-b})\left(J-\frac{b\sqrt{2}}{\sqrt{\lambda}-1}\sum_{i=1}^{J}\omega[A_{i}]^{1/2}\right), where \omega[\cdot] denotes normalised additive energy. Proof. For j=1,\dots,J , let \mu_{j}=\frac{1}{\left\lvert A_{j}\right\rvert}1_{A_{j}} . Then \left\lVert\mu_{j}\right\rVert_{1}=1 and \|\widehat{\mu_{j}}\|_{\infty}\leqslant 1 . Let \mathcal{R} be the associated McGehee-Pigno-Smith test function given by Lemma 2.2 , with parameter b , so that \|\widehat{\mathcal{R}}\|_{\infty}\leqslant 1 and \mathcal{R}=c\sum_{j=1}^{J}\mu_{j}+\sum_{j=1}^{J}D_{j}, where c=1-e^{-b} . Since \langle\mu_{j},1_{A}\rangle=1 for all j , we deduce that \|\widehat{1_{A}}\|_{1}\geqslant\left\lvert\langle\mathcal{R},1_{A}\rangle\right\rvert\geqslant cJ-\Big|\sum_{j}\langle D_{j},1_{A}\rangle\Big|. (3.1) It therefore suffices to prove an upper bound on \big|\sum_{j}\langle D_{j},1_{A}\rangle\big| of sufficient quality. By ( 2.2 ) we have D_{j}=c\sum_{ii}|A_{j}|^{-1/2}\leqslant\frac{\left\lvert A_{i}\right\rvert^{-1/2}}{\sqrt{\lambda}-1}, and the stated conclusion follows using the definition \omega[A_{i}]=E(A_{i})/|A_{i}|^{3} . ∎ 4. Improved constants for Littlewood’s conjecture In the next two sections we deduce our two main theorems from Proposition 3.1 , starting here with Theorem 1.5 , the improved constant for Littlewood’s conjecture. One may deduce Littlewood’s conjecture (with some constant) from Proposition 3.1 by taking A_{i} to be roughly the \approx\lambda^{i} smallest elements of A for all i and using the trivial bound \omega[A_{i}]\leqslant 1 , choosing b>0 and 1/\lambda suitably small absolute constants yields \|\widehat{1_{A}}\|_{1}\gg J , where \lambda^{J}\asymp N and hence J\gg_{\lambda}\log N as required. To extract a decent constant from this is a delicate optimisation in both b and \lambda , and this was the task considered by [ 15 , 17 ] . To get the slightly better constant in Theorem 1.5 , we will use a slightly less trivial bound for the \omega[A_{i}] , obtained using a rearrangement inequality. Lemma 4.1 . Suppose that A,B are finite sets of integers with cardinalities n,m respectively, where m\leqslant n . Then E(A,B)=\#\{(a_{1},b_{1},a_{2},b_{2})\in A\times B\times A\times B\}\leqslant nm^{2}\big(1-\frac{m}{3n}\big)+\frac{m}{3}. In particular, \omega[A]\leqslant\frac{2}{3}+o_{n\rightarrow\infty}(1) . Proof. This follows from a well-known rearrangement inequality (see Gabriel [ 5 , Theorem 3] or [ 9 , Theorem 376] 3 3 3 It is important to note, when reading this reference, the convention established on the previous page: ‘We may agree that, when there is no indication to the contrary, sums involving several suffixes are extended over values of the suffixes whose sum vanishes’. ). A quick proof is as follows. Let the elements of A be a_{1}0 and \lambda\geqslant 2 be some constants to be chosen later, and fix some A\subset\mathbf{Z} of size N , for some large N (where the notion of ‘large’ may depend on \lambda and b ). We now construct nested initial segments A_{1}\subseteq\cdots\subseteq A_{J} of A , for a certain parameter J . Let A_{1} be the set consisting of the smallest \lfloor\log N\rfloor elements of A . In general, if A_{1},\ldots,A_{j} have been constructed, let A_{j+1} be the set of the smallest \lceil\lambda\left\lvert A_{j}\right\rvert\rceil elements of A and continue. Otherwise, we set J=j and halt. Furthermore we have \left\lvert A_{j+1}\right\rvert\geqslant\lambda\left\lvert A_{j}\right\rvert for j=1,\dots,J . Additionally, \left\lvert A_{j+1}\right\rvert\leqslant\lambda\left\lvert A_{j}\right\rvert+1 for j=1,\dots,J , and hence by induction |A_{j}|\leqslant\lambda^{r}\big(|A_{j-r}|+\lambda^{-1}+\lambda^{-2}+\cdots+\lambda^{-r}\big) for any r\geqslant 1 . Taking r=j-1 (and since \lambda\geqslant 2 ) we have \left\lvert A_{j}\right\rvert\leqslant\lambda^{j-1}(1+\log N). By definition, the parameter J was minimal such that N<\lambda\left\lvert A_{J}\right\rvert. It follows that N<\lambda^{J}(1+\log N) and so J\geqslant(1-o(1))\frac{\log N}{\log\lambda}. (4.2) Here, and below, o(1) means a quantity tending to 0 as N\rightarrow\infty . Applying Lemma 4.1 to A_{1},\dots,A_{J} and substituting in to Proposition 3.1 , and recalling our bound ( 4.2 ) on J , we deduce that \|\widehat{1_{A}}\|_{1}\geqslant(1-o(1))f(b,\lambda)\log N where f(b,\lambda)=\frac{1-e^{-b}}{\log\lambda}\left(1-\frac{2b}{\sqrt{3}(\sqrt{\lambda}-1)}\right). It remains to choose b>0 and \lambda\in[2,\infty) to maximise f(b,\lambda) . Computational investigations tell us that the maximum value is f(b,\lambda)=0.1422917\cdots achieved at b=1.3766505\cdots\quad\textrm{and}\quad\lambda=36.1127893\cdots.\qed 5. A structural inverse result Now we turn to the deduction of Theorem 1.2 . In deducing Theorem 1.2 we are not concerned with constants, and so we record the following simpler consequence of Proposition 3.1 . Corollary 5.1 . Let \eta\in(0,1/4] . Let A\subset\mathbf{Z} be a finite set. Suppose we have a nested sequence A_{1}\subseteq A_{2}\subseteq\cdots\subseteq A_{J} of initial segments of A such that \left\lvert A_{i-1}\right\rvert\leqslant(1-\eta)\left\lvert A_{i}\right\rvert. There exists a constant c>0 such that \|\widehat{1_{A}}\|_{1}\gg J-c\eta^{-1}\sum_{i=1}^{J}\omega[A_{i}]^{1/2}. Proof. This follows immediately from Proposition 3.1 with b=1 and 1/\lambda=1-\eta , so that \frac{1}{\sqrt{\lambda}-1}\ll\eta^{-1} . ∎ We may now prove Theorem 1.2 . Proof of Theorem 1.2 . We may assume that K\geqslant\frac{1}{100} (say) since the Littlewood conjecture is true. If \delta/K\leqslant N^{-1/2} then the result is trivial by taking A^{\prime}=A , since any set of size N has at least N^{2} additive quadruples. If \delta\leqslant C(\log N)^{-1} for some absolute constant C>0 then the result is again true with A^{\prime}=A by applying Hölder’s inequality on the Fourier side, noting that E(A)^{1/4} is the L^{4} -norm of \widehat{1}_{A} . In what follows we suppose that \delta/K>N^{-1/2} and that \delta\geqslant C(\log N)^{-1} (where C>0 is some absolute constant to be chosen later). Set \eta:=c\delta/K , where c\in(0,\frac{1}{4}] is an absolute constant to be specified later. In particular, \eta^{-1}\ll N^{1/2} . We construct nested initial segments A_{1}\subseteq A_{2}\subseteq\cdots\subseteq A_{J} of A in the following fashion. Let A_{1} be the smallest \lfloor N^{1-\delta}\rfloor elements of A . In general, if A_{1},\ldots,A_{j} have been constructed, then let A_{j+1} be the set of the smallest \lceil(1-\eta)^{-1}\left\lvert A_{j}\right\rvert\rceil elements of A if A has this many elements, or else halt with j=J . By construction it is clear that \left\lvert A_{j}\right\rvert\leqslant(1-\eta)\left\lvert A_{j+1}\right\rvert for all j\in\{1,\dots,J\} . Furthermore, \left\lvert A_{j+1}\right\rvert\leqslant(1-\eta)^{-1}\left\lvert A_{j}\right\rvert+1 for j\in\{1,\dots,J\} , and hence by the same induction leading to ( 4.2 ) we have \left\lvert A_{j}\right\rvert\leqslant(1-\eta)^{1-j}(N^{1-\delta}+\eta^{-1})\ll(1-\eta)^{1-j}N^{1-\delta}. (5.1) The parameter J was the minimal j\geqslant 1 such that N<(1-\eta)^{-1}\left\lvert A_{J}\right\rvert, and hence by ( 5.1 ) we have N^{\delta}\ll(1-\eta)^{-J}\leqslant e^{2\eta J} . Since \delta\geqslant C(\log N)^{-1} (and N is sufficiently large), provided C>0 is chosen sufficiently large, it follows that J\gg\eta^{-1}\delta\log N . By Corollary 5.1 we see that either \sum_{i=1}^{J}\omega[A_{i}]^{1/2}\gg\eta J (5.2) or \|\widehat{1_{A}}\|_{1}\gg\eta^{-1}\delta\log N . If the constant c is chosen appropriately then, since \eta=c\delta/K , the latter option is contrary to our assumption. Thus ( 5.2 ) holds and so there exists some i such that \omega[A_{i}]\gg\eta^{2}\gg(\delta/K)^{2}. The conclusion now follows taking A^{\prime}=A_{i} (noting that since A_{1}\subseteq A^{\prime} we always have \left\lvert A^{\prime}\right\rvert\geqslant\lfloor N^{1-\delta}\rfloor ). ∎ 6. Speculations about stronger structure The structure found by Theorem 1.2 is, although non-trivial, still quite weak compared to the kind of structure one expects to find. For instance, we do not know of a counterexample to the following conjecture. Conjecture 6.1 . Let A\subset\mathbf{Z} be a finite set of size N . If \|\widehat{1_{A}}\|_{1}\leqslant K\log N then for some m,r\ll_{K}1 the following holds. There are finite arithmetic progressions P_{1},\ldots,P_{m}\subset\mathbb{Z} , each of length at most N , and finite sets X_{1},\ldots,X_{r}\subset\mathbf{Z} such that \big|\bigcup_{j}X_{j}\big|=o_{K}(N) , together with \epsilon_{1},\ldots,\epsilon_{m},\eta_{1},\ldots,\eta_{r}\in\{-1,1\} such that 1_{A}=\sum_{1\leqslant i\leqslant m}\epsilon_{i}1_{P_{i}}+\sum_{1\leqslant j\leqslant r}\eta_{j}1_{X_{j}}. A very similar (but slightly stronger) conjecture was put forward in print by Petridis [ 13 , Question 5.1] . Analogous results are known to be true in finite field settings due to work of Sanders and the second author [ 6 ] . A consequence of Conjecture 6.1 , still much stronger than anything we can prove, would be that there exists an arithmetic progression P of length at most N such that |A\cap P|\gg_{K}N . A third possible inverse statement concerns the ‘dimension’ of A , defined as the size of the largest dissociated subset of A . As noted in the introduction, Pichorides [ 14 ] has proved that if \|\widehat{1_{A}}\|_{1}\leqslant K\log N then \dim A\ll_{K}(\log N)^{3}. In the other direction, there are examples where \|\widehat{1_{A}}\|_{1}\ll\log N and yet \dim(A)\gg(\log N)^{2} – simply take the union of an arithmetic progression P of size \approx N and a dissociated set of size \approx X=\lfloor(\log N)^{2}\rfloor , and use the triangle inequality together with the observation that \|\widehat{1_{X}}\|_{1}\leqslant\left\lvert X\right\rvert^{1/2}\ll\log N. We conjecture that this is the best possible. Conjecture 6.2 . Let K>0 and N be sufficiently large depending only on K . Let A\subset\mathbf{Z} be a finite set of size N . If \|\widehat{1_{A}}\|_{1}\leqslant K\log N then \dim A\ll_{K}(\log N)^{2} . Furthermore, A contains a subset of size \gg_{K}N and dimension \ll_{K}\log N .