July 09, 2024
For a positive integer \(n \geq 2\), define \(t_n\) to be the smallest number such that the additive energy \(E(A)\) of any subset \(A \subset \{0,1,\cdots,n-1\}^d\) and any \(d\) is at most \(|A|^{t_n}\). Trivially we have \(t_n \leq 3\) and \[t_n \geq 3 - \log_n\frac{3n^3}{2n^3+n}\] by considering \(A = \{0,1,\cdots,n-1\}^d\). In this note, we investigate the behavior of \(t_n\) for large \(n\) and obtain the following non-trivial bounds: \[3 - (1+o_{n\rightarrow\infty}(1)) \log_n \frac{3\sqrt{3}}{4} \leq t_n \leq 3 - \log_n(1+c),\] where \(c>0\) is an absolute constant.
Let \(A \subset G\) be a finite subset of an abelian group \(G\). The additive energy \(E(A)\) of \(A\) is defined to be the number of additive quadruples in \(A\): \[E(A) = \#\{(a_1,a_2,a_3,a_4) \in A^4: a_1+a_2=a_3+a_4\}.\] Trivially we have \(|A|^2 \leq E(A) \leq |A|^3\). A central theme in additive combinatorics is to understand the structure of those sets \(A\) whose additive energy \(E(A)\) is close to its trivial upper bound \(|A|^3\). The famous Balog-Szemeredi-Gowers theorem and Freiman’s theorem are both results in this direction. See [2] for precise statements of these results and their proofs.
In this paper we study upper bounds for \(E(A)\) when \(A\) lies in certain subsets of \(\mathbb{Z}^d\) for potentially large \(d\). For a positive integer \(n \geq 2\), define \(t_n\) to be the smallest number such that \(E(A) \leq |A|^{t_n}\) for all subsets \(A \subset \{0,1,\cdots,n-1\}^d\) and all positive integers \(d\). One can calculate that \[\begin{align} E(\{0,1,\cdots,n-1\}) &= \sum_{s \in \mathbb{Z}} |\{(a,b): s=a+b, 0 \leq a,b\leq n-1\}|^2 \\ &= 1^2 + 2^2 + \cdots + n^2 + (n-1)^2 + \cdots + 1^2 = \frac{2n^3+n}{3} \end{align}\] and that \[E(\{0,1,\cdots,n-1\}^d) = E(\{0,1,\cdots,n-1\})^d = \left(\frac{2n^3+n}{3}\right)^d.\] Thus we have the trivial bounds \[\label{trivial-bounds} 3 \geq t_n \geq \log_n \frac{2n^3+n}{3} = 3 - \log_n \frac{3n^3}{2n^3+n}.\tag{1}\] It is known [3] that \(t_2 = \log_26\) so that the lower bound in 1 for \(t_2\) is sharp. For \(n = 3\), it was proved in [4] that \[t_3 \geq 2\log_2 2.5664 \geq 2.71949.\] See [4] and its proof in [4]. In particular, this implies that the trivial lower bound \(t_3 \geq \log_319 \approx 2.68\) in 1 is not sharp. Our main goal is to explore the behavior of \(t_n\) for large \(n\).
Theorem 1. Let \(n \geq 2\) be a positive integer. Then for some absolute constant \(c>0\) we have \[3 - (1+o_{n\rightarrow\infty}(1)) \log_n \frac{3\sqrt{3}}{4} \leq t_n \leq 3 - \log_n (1+c),\] where \(o_{n\rightarrow\infty}(1)\) denotes a quantity that tends to \(0\) as \(n\rightarrow\infty\).
Unfortunately the lower bound in Theorem 1 is only meaningful for \(n\) sufficiently large. To complement that, we also prove the following result which is valid for every \(n \geq 3\).
Theorem 2. For any positive integer \(n \geq 3\), we have \[t_n > \log_n E(\{0,1,\cdots,n-1\}) = \log_n \frac{2n^3+n}{3}.\]
A key tool for the proof of both theorems comes from [4], which allows us to pass from studying subsets in \(\mathbb{Z}^d\) to studying functions on \(\mathbb{Z}\). In Section 2 we will describe this tool, outline the proofs, and make some remarks on further directions. The lower bound and the upper bound in Theorem 1 will be proved in Sections 3 and 4, respectively. Theorem 2 will be proved in Section 5.
For a finitely supported function \(f: \mathbb{Z}\rightarrow \mathbb{C}\), we define its Fourier transform \(\widehat{f}: \mathbb{R}/\mathbb{Z}\rightarrow \mathbb{C}\) by the formula \[\widehat{f}(\theta) = \sum_{a \in \mathbb{Z}} f(a) e(-a\theta),\] where \(e(x) = e^{2\pi ix}\). For \(p,q \geq 1\), the \(L^p\)-norm of \(\widehat{f}\) and the \(\ell^q\)-norm of \(f\) are defined by \[\|\widehat{f}\|_p = \left(\int_0^1 |\widehat{f}(\theta)|^p \mathrm{d}\theta\right)^{1/p}, \;\;\|f\|_q = \left(\sum_{a \in \mathbb{Z}} |f(a)|^q\right)^{1/q}.\] For two finitely supported functions \(f, g: \mathbb{Z}\rightarrow \mathbb{C}\), their convolution \(f*g: \mathbb{Z}\rightarrow \mathbb{C}\) is defined by \[f*g(s) = \sum_{a \in \mathbb{Z}} f(a) g(s-a).\] We have the identities \[\|\widehat{f}\|_4^4 = \|f*f\|_2^2 = \sum_{a, b, c \in \mathbb{Z}} f(a) f(b) \overline{f(c) f(a+b-c)}.\] Thus if \(f = 1_A\) is the indicator function of a finite subset \(A \subset \mathbb{Z}\), then \[E(A) = \|1_A*1_A\|_2^2 = \|\widehat{1_A}\|_4^4.\] In Section 3 we will also need to utilize Fourier transforms of functions on \(\mathbb{R}\). For a piecewise continuous function \(g: \mathbb{R}\rightarrow \mathbb{C}\) which has bounded support, we define its Fourier transform \(\widehat{g}: \mathbb{R}\rightarrow \mathbb{C}\) by the formula \[\widehat{g}(y) = \int_{-\infty}^{+\infty} f(x) e(-xy) \mathrm{d}x.\] For two such functions \(g,h\), we define their convolution \(g*h: \mathbb{R}\rightarrow \mathbb{C}\) by \[g*h(z) = \int_{-\infty}^{+\infty} g(x) h(z-x) \mathrm{d}x.\] We have the identities \[\|\widehat{g}\|_4^4 = \|g*g\|_2^2 = \int\int\int g(x_1)g(x_2) \overline{g(x_3)g(x_1+x_2-x_3)} \mathrm{d}x_1 \mathrm{d}x_2 \mathrm{d}x_3.\]
The machinery developed in [4] plays a key role in our proof. We summarize their result in the following proposition. Recall the definition of \(t_n\) from the introduction.
Proposition 3. Let \(n \geq 2\) be a positive integer. We have \(t_n = 4/q_n\), where \(q_n\) is the largest value of \(q\) such that the inequality \(\|\widehat{f}\|_4 \leq \|f\|_q\) holds for any function \(f: \mathbb{Z}\rightarrow \mathbb{R}\) which is supported on an interval of length \(n\).
Proof. This is essentially [4]. First observe that, by translation, we may restrict to those functions \(f: \mathbb{Z}\rightarrow\mathbb{R}\) supported on \(A = \{0,1,\cdots,n-1\}\) in the definition of \(q_n\). Then, in the language of [4], \(q_n\) is the largest value of \(q\) such that \[\label{eq-DE} \operatorname{DE}_{\ell^q\rightarrow L^4}(A) \leq 1,\tag{2}\] where \(\operatorname{DE}_{\ell^q\rightarrow L^4}(A)\) is the operator norm of the linear map \(\ell^q(A) \rightarrow L^4(\mathbb{R}/\mathbb{Z})\) defined by the Fourier transform \(f \mapsto \widehat{f}\). By [4], 2 is equivalent to the statement that an inequality of the form \[E(X) \leq |X|^{4/q}\] holds for all subsets \(X \subset A^d\) and \(d \geq 1\). It follows that \(t_n = 4/q_n\) by the definition of \(t_n\). ◻
We remark that, by the Hausdorff-Young inequality, we always have \[\|\widehat{f}\|_4 \leq \|f\|_{4/3}.\] Hence \(q_n \geq 4/3\) and this recovers the trivial bound \(t_n \leq 3\). Moreover, the \(\ell^{4/3}\)-norm and the \(\ell^q\)-norm for \(q > 4/3\) are related by the inequalities \[\label{eq:q-4473} \|f\|_q \leq \|f\|_{4/3} \leq |\operatorname{supp} f|^{3/4-1/q} \cdot \|f\|_q,\tag{3}\] where \(|\operatorname{supp}f|\) denotes the size of the support of \(f\).
In view of Proposition 3, the lower and upper bounds in Theorem 1 follow from Propositions 4 and 5 below, respectively. In the remainder of this section, we discuss the main ideas behind the proofs of these two propositions and make some remarks about the quality of our bounds.
In view of Proposition 3, the lower bound for \(t_n\) in Theorem 1 is equivalent to the following proposition.
Proposition 4. Let \(\varepsilon> 0\) and let \(n\) be sufficiently large in terms of \(\varepsilon\). Let \[q = \frac{4}{3 - (1+\varepsilon)\log_n\frac{3\sqrt{3}}{4}}.\] There exists a function \(f: \mathbb{Z}\rightarrow \mathbb{R}\) which is supported on an interval of length \(n\), such that \(\|\widehat{f}\|_4 > \|f\|_q\).
Our motivation for the construction of \(f\) in Proposition 4 comes from the Babenko-Beckner inequality [5], [6], a sharpened form of the Hausdorff-Young inequality for functions on \(\mathbb{R}\) (and more generally on \(\mathbb{R}^d\)). It asserts that for any function \(g: \mathbb{R}\rightarrow \mathbb{R}\) we have \[\label{Beckner} \|\widehat{g}\|_4 \leq \left(\frac{4\sqrt{3}}{9}\right)^{1/4} \|g\|_{4/3}.\tag{4}\] Moreover, equality is achieved when \(g\) is the Gaussian function \(g(x) = e^{-x^2}\). In other words, Gaussian functions (and similarly their dilated versions) maximize the \(\widehat{L}_4\)-norm, if we hold the \(\ell^{4/3}\)-norm fixed. If we take \(g(x) = e^{-x^2/A}\) with \(A \approx n^2\) (so that \(g\) is essentially supported on an interval of length \(\approx n\)), then direct computations show that \[\frac{\|g\|_{4/3}}{\|g\|_q} = c A^{\frac{1}{2}(\frac{3}{4}-\frac{1}{q})},\] where \(c\) is an explicit constant depending on \(q\) and \(c\approx 1\) when \(q \approx 4/3\). By our choice of \(A\) and \(q\), we have \[A^{\frac{1}{2}(\frac{3}{4}-\frac{1}{q})} \approx n^{\frac{3}{4}-\frac{1}{q}} = n^{\frac{1}{4}(1+\varepsilon)\log_n\frac{3\sqrt{3}}{4}} \approx \left(\frac{3\sqrt{3}}{4}+c\right)^{1/4}\] for some constant \(c=c(\varepsilon) > 0\). Hence this function \(g(x)\) satisfies \[\|\widehat{g}\|_4 = \left(\frac{4\sqrt{3}}{9}\right)^{1/4} \|g\|_{4/3} \approx \left(\frac{4\sqrt{3}}{9}\right)^{1/4} \left(\frac{3\sqrt{3}}{4} + c\right)^{1/4}\|g\|_q > \|g\|_q.\] If we define \(f: \mathbb{Z}\rightarrow \mathbb{R}\) by sampling the values of \(g(x)\) at integral points, then we may expect that \[\|\widehat{f}\|_4 \approx \|\widehat{g}\|_4, \;\;\|f\|_q \approx \|g\|_q,\] and thus we should also have \(\|\widehat{f}\|_4 > \|f\|_q\). The details are worked out in Section 3.
In view of Proposition 3, the upper bound for \(t_n\) in Theorem 1 is equivalent to the following proposition.
Proposition 5. Let \(n \geq 2\) be a positive integer and let \(f: \mathbb{Z}\rightarrow \mathbb{R}\) be a function which is supported on a set of size \(n\). Let \[q = \frac{4}{3 - \log_n(1+c)}\] for some sufficiently small absolute constant \(c > 0\). Then \(\|\widehat{f}\|_4 \leq \|f\|_q\).
The starting point of our proof of Proposition 5 is the inequality \[\label{eq:HY} \|\widehat{f}\|_4 \leq \|f\|_{4/3}\tag{5}\] which follows from the Hausdorff-Young inequality or Young’s convolution inequality. By Hölder’s inequality (see 3 ) and the definition of \(q\), we have \[\|f\|_{4/3} \leq n^{3/4 - 1/q} \|f\|_q = (1+c)^{1/4} \|f\|_q.\] Thus the proof is already complete unless \[\|\widehat{f}\|_4 \geq (1+c)^{-1/4} \|f\|_{4/3},\] and thus a key part of our argument is to analyze when equality almost holds in 5 . Note that equality holds exactly in 5 when \(f\) is supported on a singleton set. We prove in Proposition 8 that if equality almost holds in 5 , then \(f\) is well approximated by a function \(f_0\) which is supported on a singleton set, up to an error \(g\) which is small in \(\ell^{4/3}\)-norm. Clearly the function \(f_0\) satisfies \(\|\widehat{f_0}\|_4 = \|f_0\|_q\). The remaining task is then to show that the error \(g\) can only swing the inequality in the desired direction. The details are carried out in Section 4.
We remark that Proposition 8 is not new. In fact, it is a special case of [7] (see also [8] for an analogous result in Euclidean spaces) and of [9]. As it turns out, our proof idea is the same as that in [9], which in turn has its origin from [10]. For completeness, we still give a self-contained proof of it in Section 4.
Our proof of the lower bounds for \(t_n\) is not constructive, which motivates the question of constructing explicit subsets of \(\{0,1,\cdots,n-1\}^d\) with large additive energies.
Question 6. For sufficiently large \(n\), construct a subset \(A \subset \{0,1,\cdots,n-1\}^d\) for some \(d\) such that \(E(A) \geq |A|^t\), where \[t = 3 - (1+o_{n\rightarrow\infty}(1)) \log_n \frac{3\sqrt{3}}{4}.\]
A possible candidate for such a set \(A\) is the set of lattice points in a \(d\)-dimensional ball \(B_d \subset \mathbb{R}^d\) (with an appropriate choice of \(d\) and an appropriate center and radius). This choice is motivated by results in [11] which implies, roughly speaking, that such a set \(A\) maximizes the additive energy among all genuinely \(d\)-dimensional subsets of \(\mathbb{Z}^d\) of a given cardinality. Moreover, \(E(A) \approx E(B_d)\) and it follows from the computations in [1] that \[E(B_d) = \left(\frac{4\sqrt{3}}{9} + o_{d\rightarrow\infty}(1)\right)^d |B_d|^3,\] where \(|B_d|\) denotes the Lebesgue measure of \(B_d\).
Next we speculate the asymptotic behavior of \(t_n\) as \(n\rightarrow\infty\). Note that if \(g: \mathbb{R}\rightarrow \mathbb{R}\) is a (continuous) function supported on an interval of length \(n\) and \[q = \frac{4}{3-\log_n\frac{3\sqrt{3}}{4}},\] then \[\|\widehat{g}\|_4 \leq \left(\frac{4\sqrt{3}}{9}\right)^{1/4} \|g\|_{4/3} \leq \left(\frac{4\sqrt{3}}{9}\right)^{1/4} n^{3/4-1/q} \|g\|_q = \|g\|_q,\] where the first inequality follows from the Babenko-Beckner inequality 4 and the second inequality follows from Hölder’s inequality (a continuous version of 3 ). Based on this, it is perhaps reasonable to conjecture that a similar bound holds for discrete functions.
Conjecture 7. Let \(\varepsilon> 0\) and let \(n\) be sufficiently large in terms of \(\varepsilon\). Let \[q = \frac{4}{3 - (1-\varepsilon)\log_n\frac{3\sqrt{3}}{4}}.\] Then for any function \(f: \mathbb{Z}\rightarrow \mathbb{R}\) which is supported on an interval of length \(n\), we have \(\|\widehat{f}\|_4 \leq \|f\|_q\).
In particular, the conjecture would imply that \[t_n = 3 - (1+o_{n\rightarrow\infty}(1)) \log_n \frac{3\sqrt{3}}{4}.\] So perhaps the lower bound in Theorem 1 is sharp up to the error in \(o(1)\).
In this section we prove Proposition 4. Throughout this section, let \(\varepsilon>0\) be small and let \(n = 2k+1\) be sufficiently large in terms of \(\varepsilon\). We will construct a function \(f: \mathbb{Z}\rightarrow \mathbb{R}\) supported on \(\{-k,\cdots,k\}\) such that \(\|\widehat{f}\|_4 > \|f\|_q\), where \[q = \frac{4}{3-(1+\varepsilon) \log_n \frac{3\sqrt{3}}{4}}.\]
Define \(g: \mathbb{R}\rightarrow \mathbb{R}\) by \(g(x) = \exp(-x^2/A)\), where \(A = k^{2-\varepsilon/10}\).
Lemma 1. We have \(\|\widehat{g}\|_4 \geq (1+c\varepsilon)\|g\|_q\) for some absolute constant \(c > 0\).
Proof. One can compute that \[\widehat{g}(y) = (\pi A)^{1/2} e^{-\pi^2 A y^2},\] and hence \[\|\widehat{g}\|_4^4 = (\pi A)^2 \int_{-\infty}^{\infty} e^{-4\pi^2 A y^2} \mathrm{d}y = \frac{1}{2} (\pi A)^{3/2}.\] On the other hand, we have \[\|g\|_q^q = \int_{-\infty}^{\infty} e^{-qx^2/A} \mathrm{d}x = \left(\frac{\pi A}{q}\right)^{1/2}.\] It follows that \[\frac{\|\widehat{g}\|_4}{\|g\|_q} = \left(\frac{1}{4} q^{4/q} \pi^{3-4/q} A^{3-4/q}\right)^{1/8}.\] By our choice of \(A\), we have \[A^{3-4/q} = \exp\left( \left(2-\frac{\varepsilon}{10}\right) (\log k) (1+\varepsilon)\log_n\frac{3\sqrt{3}}{4} \right) \geq \exp\left((2+\varepsilon)\log\frac{3\sqrt{3}}{4}\right) \geq (1+c\varepsilon) \frac{27}{16}.\] for some absolute constant \(c>0\). By choosing \(k\) to be sufficiently large in terms of \(\varepsilon\), we may ensure that \(q\) is sufficiently close to \(4/3\) so that \[\frac{1}{4} q^{4/q} \pi^{3-4/q} \geq \left(1-\frac{c\varepsilon}{2}\right) \frac{1}{4} \left(\frac{4}{3}\right)^3 = \left(1-\frac{c\varepsilon}{2}\right) \frac{16}{27}.\] Combining the two inequalities above, we conclude that \[\frac{\|\widehat{g}\|_4}{\|g\|_q} \geq \left[(1+c\varepsilon)\left(1-\frac{c\varepsilon}{2}\right)\right]^{1/8} \geq 1 + \frac{c\varepsilon}{100}.\] ◻
Now we truncate \(g\) to have bounded support. Set \(M = \lfloor k^{1-\varepsilon/100}\rfloor\). Let \(g_M: \mathbb{R}\rightarrow \mathbb{R}\) be the truncation of \(g\) defined by \[g_M(x) = \begin{cases} g(x) & \text{if } -M \leq x < M, \\ 0 & \text{otherwise.} \end{cases}\]
Lemma 2. We have \(\|\widehat{g_M}\|_4 \geq \|\widehat{g}\|_4 - \exp(-k^{\varepsilon/20})\) and \(\|g_M\|_q \leq \|g\|_q\).
Proof. The inequality \(\|g_M\|_q \leq \|g\|_q\) follows trivially from the definition of \(g_M\). Concerning the \(L^4\)-norm of their Fourier transforms, we have by the triangle inequality, Hausdorff-Young inequality, and Hölder’s inequality that \[\|\widehat{g}\|_4 - \|\widehat{g_M}\|_4 \leq \|\widehat{g-g_M}\|_4 \leq \|g-g_M\|_{4/3} \leq \|g-g_M\|_{\infty}^{1/4} \|g-g_M\|_1^{3/4}.\] Since \[\|g-g_M\|_{\infty} \leq g(M) = \exp(-M^2/A) \leq \exp(-k^{\varepsilon/15})\] and \[\|g-g_M\|_1 \leq \|g\|_1 = \int_{-\infty}^{\infty} e^{-x^2/A} \mathrm{d}x = (\pi A)^{1/2} \ll k,\] it follows that \[\|g-g_M\|_{\infty}^{1/4} \|g-g_M\|_1^{3/4} \leq \exp(-k^{\varepsilon/20}),\] once \(k\) is large enough in terms of \(\varepsilon\). ◻
Now we discretize \(g_M\). Define \(f: \mathbb{Z}\rightarrow \mathbb{R}\) by \(f(m) = g_M(m)\) for \(m \in \mathbb{Z}\). Then \(f\) is supported on \(\{-M,\cdots,M\} \subset \{-k,\cdots,k\}\).
Lemma 3. For \(m \in \mathbb{Z}\), let \(I_m = [m, m+1)\). Then \[\sup_{x \in I_m} |g_M(x) - f(m)| \ll k^{-1/2} f(m)\] for every \(m \in \mathbb{Z}\).
Proof. If \(m \geq M\) or \(m \leq -M-1\), then \(f(m) = 0\) and \(g_M(x) = 0\) for every \(x \in I_m\), and hence the conclusion holds trivially. Now assume that \(m \in \{-M, \cdots, M-1\}\), so that \(I_m \subset [-M, M)\) and thus \(g_M(x) = g(x)\) for \(x \in I_m\). Hence for \(x \in I_m\) we have \[|g_M(x) - f(m)| = |g(x) - g(m)| \leq \sup_{y \in [x,m]} |g'(y)| = \frac{2}{A} \sup_{y \in I_m} |yg(y)| \leq \frac{2}{A}(1+|m|) \sup_{y \in I_m} g(y)\] Since \[g(m+1) = g(m) e^{-(2m+1)/A} \leq g(m) e^{2M/A} \leq 2g(m),\] it follows that \[|g_M(x) - f(m)| \ll \frac{M}{A} g(m) \ll k^{-1/2} g(m).\] ◻
Lemma 4. We have \(\|\widehat{g_M}\|_4 \leq (1 + O(k^{-1/2})) \|\widehat{f}\|_4\) and \(\|g_M\|_q = (1 + O(k^{-1/2})) \|f\|_q\).
Proof. Note that \[\begin{align} \|\widehat{g_M}\|_4^4 &= \int\int\int g_M(x_1)g_M(x_2)g_M(x_3)g_M(x_1+x_2-x_3) \mathrm{d}x_1 \mathrm{d}x_2 \mathrm{d}x_3 \\ &= \sum_{a_1,a_2,a_3,a_4 \in \mathbb{Z}} \int\int\int g_M\vert_{I_{a_1}}(x_1) g_M\vert_{I_{a_2}}(x_2) g_M\vert_{I_{a_3}}(x_3) g_M\vert_{I_{a_4}}(x_1+x_2-x_3) \mathrm{d}x_1 \mathrm{d}x_2 \mathrm{d}x_3. \end{align}\] By Lemma 3 we have \[g_M\vert_{I_a}(x) = (1+O(k^{-1/2})) f(a) 1_{I_a}(x)\] for any \(a \in \mathbb{Z}\) and \(x \in \mathbb{R}\). Hence \[\|\widehat{g_M}\|_4^4 = \left(1 + O(k^{-1/2})\right) \sum_{a_1,a_2,a_3,a_4 \in \mathbb{Z}} f(a_1) f(a_2) f(a_3) f(a_4) I(a_1,a_2,a_3,a_4),\] where \[I(a_1,a_2,a_3,a_4) = \int\int\int 1_{I_{a_1}}(x_1) 1_{I_{a_2}}(x_2) 1_{I_{a_3}}(x_3) 1_{I_{a_4}}(x_1+x_2-x_3) \mathrm{d}x_1 \mathrm{d}x_2 \mathrm{d}x_3.\] By shifting the variables \(x_1,x_2,x_3\) in the integral above, we see that \[I(a_1,a_2,a_3,a_4) = I(0, 0, 0, a_3+a_4-a_1-a_2).\] It follows that \[\|\widehat{g_M}\|_4^4 = \left(1 + O(k^{-1/2})\right) \sum_{a \in \mathbb{Z}} I(0,0,0,a) \sum_{\substack{a_1,a_2,a_3,a_4 \in \mathbb{Z}\\ a_3+a_4-a_1-a_2=a}} f(a_1) f(a_2) f(a_3) f(a_4)\] By Fourier analysis, we have \[\sum_{\substack{a_1,a_2,a_3,a_4 \in \mathbb{Z}\\ a_3+a_4-a_1-a_2=a}} f(a_1) f(a_2) f(a_3) f(a_4) = \int_0^1 |\widehat{f}(\theta)|^4 e(a\theta) \mathrm{d}\theta \leq \|f\|_4^4.\] Hence \[\|\widehat{g_M}\|_4^4 \leq \left(1 + O(k^{-1/2})\right) \|f\|_4^4 \sum_{a \in \mathbb{Z}} I(0,0,0,a) = \left(1 + O(k^{-1/2})\right) \|f\|_4^4.\] This proves the first bound in the lemma. For the second bound concerning the \(L^q\)-norms, note that \[\|f\|_q^q - \|g_M\|_q^q = \sum_{a \in \mathbb{Z}} f(a)^q - \int_{-\infty}^{\infty} g_M(x)^q \mathrm{d}x = \sum_{a \in \mathbb{Z}} \left(f(a)^q - \int_a^{a+1} g_M(x)^q \mathrm{d}x\right).\] By Lemma 3 we have \[\int_a^{a+1} g_M(x)^q \mathrm{d}x = (1+O(k^{-1/2})) f(a)^q\] for every \(a \in \mathbb{Z}\). It follows that \[\|f\|_q^q - \|g_M\|_q^q = O\left(k^{-1/2} \sum_{a \in \mathbb{Z}} f(a)^q\right) = O\left(k^{-1/2} \|f\|_q^q\right).\] This proves the second bound in the lemma. ◻
We may now complete the proof of Proposition 4 by combining the lemmas above. Indeed, by Lemmas 2 and 4 we have \[\|f\|_q \leq (1 + O(k^{-1/2})) \|g_M\|_q \leq (1 + O(k^{-1/2})) \|g\|_q\] and \[\|\widehat{f}\|_4 \geq (1 - O(k^{-1/2})) \|\widehat{g_M}\|_4 \geq (1 - O(k^{-1/2})) \left(\|\widehat{g}\|_4 - \exp(-k^{\varepsilon/20})\right).\] Since \(\|\widehat{g}\|_4 \asymp A^{3/8}\), we have \[\|\widehat{f}\|_4 \geq (1 - O(k^{-1/2})) \|\widehat{g}\|_4.\] It follows from Lemma 1 that \[\frac{\|\widehat{f}\|_4}{\|f\|_q} \geq (1-O(k^{-1/2})) \frac{\|\widehat{g}\|_4}{\|g\|_q} \geq (1 - O(k^{-1/2})) (1 + c\varepsilon) > 1,\] once \(k\) is large enough in terms of \(\varepsilon\).
In this section we prove Proposition 5. As explained in Section 2, a key ingredient is an approximate inverse theorem for Young’s convolution inequality, Proposition 8 below, which is a special case of results in [7], [9]. For completeness, we give a self-contained proof of it. In preparation for the proof, we start with establishing an approximate inverse theorem for Hölder’s inequality, Lemma 7, which is a special case of [9].
In this section, all implied constants are allowed to depend on the exponents \(p,q,r\).
Lemma 5. Let \(p,q \in (1,+\infty)\) be exponents with \(1/p + 1/q = 1\). Let \(a, b\) be non-negative reals. Suppose that \[\frac{a^p}{p} + \frac{b^q}{q} \leq (1 + \delta)ab\] for some sufficiently small constant \(\delta > 0\). Then \(a^p = (1 + O(\delta^{1/2}))b^q\).
Proof. If \(ab=0\), then the conclusion holds trivially. Henceforth assume that \(a,b > 0\). By Taylor’s theorem applied to the function \(\psi(x) = \log x\) at the point \(x_0 = a^p/p + b^q/q\), we have \[\psi(a^p) = \psi(x_0) + (a^p - x_0) \psi'(x_0) + \frac{1}{2} (a^p-x_0)^2 \psi''(\xi_1)\] and \[\psi(b^q) = \psi(x_0) + (b^q - x_0) \psi'(x_0) + \frac{1}{2} (b^q-x_0)^2 \psi''(\xi_2)\] for some \(\xi_1,\xi_2\) lying between \(a^p\) and \(b^q\). Since \[a^p - x_0 = \frac{a^p - b^q}{q}, \;\;b^q-x_0 = \frac{b^q-a^p}{p},\] it follows that \[\frac{1}{p}\psi(a^p) + \frac{1}{q}\psi(b^q) = \psi(x_0) + \frac{(a^p-b^q)^2}{2pq^2} \psi''(\xi_1) + \frac{(a^p-b^q)^2}{2p^2q}\psi''(\xi_2).\] Since \(\psi''(x) = -1/x^2\), we have \[\psi''(\xi_i) \leq -\min\left(\frac{1}{a^{2p}}, \frac{1}{b^{2q}}\right).\] From hypothesis we have \[\frac{1}{p}\psi(a^p) + \frac{1}{q}\psi(b^q) - \psi(x_0) = \log a + \log b - \log\left(\frac{a^p}{p} + \frac{b^q}{q}\right) \geq -\log(1+\delta) \geq - \delta.\] Hence it follows that \[-\delta \leq -(a^p-b^q)^2\left(\frac{1}{2pq^2} + \frac{1}{2p^2q}\right) \min\left(\frac{1}{a^{2p}}, \frac{1}{b^{2q}}\right) = -\frac{(a^p-b^q)^2}{2pq} \min\left(\frac{1}{a^{2p}}, \frac{1}{b^{2q}}\right),\] and thus \[(a^p - b^q)^2 \ll \delta \max(a^{2p}, b^{2q}).\] The desired conclusion follows immediately. ◻
Lemma 6. Let \(p,q,r \in (1,+\infty)\) be exponents with \(1/p + 1/q + 1/r = 1\). Let \(a, b, c\) be non-negative reals. Suppose that \[\frac{a^p}{p} + \frac{b^q}{q} + \frac{c^r}{r} \leq (1 + \delta)abc\] for some sufficiently small constant \(\delta > 0\). Then \(a^p = (1 + O(\delta^{1/2}))b^q = (1 + O(\delta^{1/2})c^r\).
Proof. We may assume that \(abc > 0\), since otherwise the conclusion holds trivially. Choose exponent \(p' \in (1,+\infty)\) such that \(1/p + 1/p' = 1\). Let \[d = \left(\frac{p'}{q} b^q + \frac{p'}{r} c^r\right)^{1/p'}.\] Then \[\frac{a^p}{p} + \frac{b^q}{q} + \frac{c^r}{r} = \frac{a^p}{p} + \frac{d^{p'}}{p'} \geq ad.\] From hypothesis it follows that \(d \leq (1+\delta)bc\), which can be rewritten as \[\frac{x^{q'}}{q'} + \frac{y^{r'}}{r'} \leq (1+\delta)^{p'} xy,\] where \[q' = \frac{q}{p'}, \;\;r' = \frac{r}{p'}, \;\;x = b^{p'}, \;\;y = c^{q'}.\] Note that \(1/q' + 1/r' = 1\). Hence by Lemma 5 it follows that \[x^{q'} = (1 + O(\delta^{1/2})) y^{r'},\] which implies that \[b^q = (1 + O(\delta^{1/2})) c^r.\] Similarly, one can also prove that \(a^p = (1 + O(\delta^{1/2})) c^r\). ◻
Lemma 7. Let \(p,q,r \in (1,+\infty)\) be exponents with \(1/p + 1/q + 1/r = 1\). Let \(a_1,\cdots,a_n\), \(b_1,\cdots,b_n\), \(c_1,\cdots,c_n\) be non-negative reals such that \[\sum_{i=1}^n a_i^p = \sum_{i=1}^n b_i^q = \sum_{i=1}^n c_i^r = 1.\] Suppose that \[\sum_{i=1}^n a_ib_ic_i \geq 1 - \delta\] for some sufficiently small constant \(\delta > 0\). Then we have \[a_i^p = (1 + O(\delta^{1/4})) b_i^q = (1 + O(\delta^{1/4})) c_i^r\] for each \(i\) outside an exceptional set \(E\) satisfying \[\sum_{i \in E} (a_i^p + b_i^q + c_i^r) \ll \delta^{1/2}.\]
Proof. For each \(i\) we have \[a_ib_ic_i \leq \frac{a_i^p}{p} + \frac{b_i^q}{q} + \frac{c_i^r}{r}.\] Let \(E \subset \{1,2,\cdots,n\}\) be the exceptional set of indices \(i\) such that \[\frac{a_i^p}{p} + \frac{b_i^q}{q} + \frac{c_i^r}{r} \geq (1+\delta^{1/2}) a_ib_ic_i.\] Then \[\delta \geq \sum_{i=1}^n \left(\frac{a_i^p}{p} + \frac{b_i^q}{q} + \frac{c_i^r}{r} - a_ib_ic_i\right) \gg \delta^{1/2} \sum_{i \in E} \left(\frac{a_i^p}{p} + \frac{b_i^q}{q} + \frac{c_i^r}{r}\right),\] and hence \(\sum_{i \in E} (a_i^p + b_i^q + c_i^r) \ll \delta^{1/2}\). For \(i \notin E\), Lemma 6 implies that \[a_i^p = (1 + O(\delta^{1/4})) b_i^q = (1 + O(\delta^{1/4})) c_i^r.\] This concludes the proof. ◻
In this section, all implied constants are allowed to depend on the exponents \(p,q,r\). Before proving the approximate inverse of Young’s inequality, we need the following standard result in additive combinatorics.
Lemma 8. Let \(G\) be an abelian group and let \(X, Y \subset G\) be finite subsets with \(|X| = |Y| = N\). Let \(\varepsilon\in (0, 1/20)\) and let \(\delta > 0\) be sufficiently small in terms of \(\varepsilon\). Let \(M \subset X \times Y\) be a subset with \(|M| \geq (1-\delta) N^2\). Suppose that the restricted sumset \[X+_MY := \{x+y: (x,y) \in M\}\] has size at most \((1+\varepsilon)N\). Then there exists a coset \(x+H\) of a subgroup \(H \subset G\) such that \(|X \setminus (x+H)| \leq \varepsilon N\) and \(|(x+H) \setminus X| \leq 3\varepsilon N\).
Proof. By an almost-all version of the Balog-Szemeredi-Gowers theorem as in [12] (see also [13] for a version with \(G = \mathbb{Z}\) and [14] for an asymmetric version), one can find subsets \(X' \subset X\) and \(Y' \subset Y\) such that \[|X'| \geq (1-\varepsilon)N, \;\;|Y'| \geq (1-\varepsilon)N, \;\;|X'+Y'| \leq |X+_MY| + \varepsilon N \leq (1+2\varepsilon)N.\] By Kneser’s theorem [15] (see [2]), we have \[|X'+Y'| \geq |X'| + |Y'| - |H|,\] where \(H \subset G\) is the subgroup defined by \[H = \{h \in G: X'+Y'+h = X'+Y'\}.\] It follows that \(|H| \geq (1-4\varepsilon)N\) and hence \(|X'+Y'| < 2|H|\). Since \(X'+Y'\) is the union of cosets of \(H\), it must be a single coset of \(H\), and thus \(X'\) is contained in a single coset \(x+H\) of \(H\). Hence \[|X\setminus (x+H)| \leq |X\setminus X'| \leq \varepsilon N\] and \[|(x+H) \setminus X| \leq |(x+H) \setminus X'| = |X'+Y'| - |X'| \leq 3\varepsilon N.\] ◻
Proposition 8. Let \(p,q,r \in (1,+\infty)\) be exponents with \(1/p + 1/q = 1 + 1/r\). Let \(f,g: \mathbb{Z}\rightarrow\mathbb{C}\) be finitely-supported functions such that \(\|f\|_p = \|g\|_q = 1\). Suppose that \[\|f*g\|_r \geq 1-\delta\] for some sufficiently small constant \(\delta > 0\). Then there exists a singleton set \(\{x_0\}\) for some \(x_0 \in \mathbb{Z}\) such that \[\|f - f(x_0)1_{\{x_0\}}\|_p^p \ll \delta^{1/8}.\]
Proof. By replacing \(f,g\) by \(|f|, |g|\), we may assume that \(f,g\) takes non-negative real values. For every \(x \in \mathbb{Z}\) we have \[(f*g)(x) = \sum_{y\in\mathbb{Z}} f(x-y) g(y) = \sum_{y \in \mathbb{Z}} f(x-y)^{p/r} g(y)^{q/r} \cdot f(x-y)^{(r-p)/r} \cdot g(y)^{(r-q)/r}.\] By Hölder’s inequality, we have \[\label{HY-eq1} (f*g)(x) \leq \left(\sum_{y \in \mathbb{Z}} f(x-y)^p g(y)^q \right)^{\frac{1}{r}} \left(\sum_{y \in \mathbb{Z}} f(x-y)^p\right)^{\frac{r-p}{pr}} \left(\sum_{y \in \mathbb{Z}} g(y)^q\right)^{\frac{r-q}{qr}}.\tag{6}\] Since \(\|f\|_p = \|g\|_q = 1\), it follows that \[(f*g)(x)^r \leq \sum_{y \in \mathbb{Z}} f(x-y)^p g(y)^q.\] Let \(E_1 \subset \mathbb{Z}\) be the exceptional set of \(x \in \mathbb{Z}\) such that \[(f*g)(x)^r \leq (1 - \delta^{1/2}) \sum_{y \in \mathbb{Z}} f(x-y)^p g(y)^q.\] From hypothesis we have \[1 - (1-\delta)^r \geq \sum_{x \in \mathbb{Z}} \left(\sum_{y \in \mathbb{Z}} f(x-y)^p g(y)^q - (f*g)(x)^r\right) \geq \delta^{1/2} \sum_{x \in E_1} \sum_{y \in \mathbb{Z}} f(x-y)^p g(y)^q\] and hence \[\label{HY-exceptional1} \sum_{(x,y) \in E_1\times \mathbb{Z}} f(x-y)^p g(y)^q \ll \delta^{1/2}.\tag{7}\] For each \(x \notin E_1\), we have almost equality in 6 , and hence by Lemma 7 applied to the three sequences \[a_x(y) = \frac{f(x-y)^{p/r} g(y)^{q/r}}{h(x)^{1/r}}, \;\;b_x(y) = f(x-y)^{(r-p)/r}, \;\;c_x(y) = g(y)^{(r-q)/r},\] where \[h(x) = \sum_{z \in \mathbb{Z}} f(x-z)^p g(z)^q,\] we conclude that \[\label{HY-eq2} \frac{f(x-y)^pg(y)^q}{h(x)} = (1 + O(\delta^{1/8})) f(x-y)^p = (1 + O(\delta^{1/8})) g(y)^q\tag{8}\] for each \(y\) outside an exceptional set \(E_2(x)\) satisfying \[\label{HY-exceptional2} \sum_{y \in E_2(x)} f(x-y)^p g(y)^q \ll \delta^{1/4}h(x).\tag{9}\] Define \[E = (E_1 \times \mathbb{Z}) \cup \{(x, y) \in \mathbb{Z}\times \mathbb{Z}: x \notin E_1, y \in E_2(x)\}.\] Then from 7 and 9 it follows that \[\sum_{(x,y) \in E} f(x-y)^p g(y)^q \ll \delta^{1/2} + \delta^{1/4} \sum_{x \in \mathbb{Z}}h(x) \ll \delta^{1/4},\] and 8 holds for every \((x,y) \notin E\).
Now make a change of variables and consider \[E' = \{(x,y) \in \mathbb{Z}\times \mathbb{Z}: (x+y, y) \in E\}.\] Then \[\label{HY-exceptional39} \sum_{(x,y) \in E'} f(x)^p g(y)^q = \sum_{(x,y) \in E} f(x-y)^pg(y)^q \ll \delta^{1/4},\tag{10}\] and we have \[\label{HY-eq3} \frac{f(x)^p g(y)^q}{h(x+y)} = (1 + O(\delta^{1/8}))f(x)^p = (1 + O(\delta^{1/8})) g(y)^q\tag{11}\] for every \((x,y) \notin E'\). Let \(X \subset \mathbb{Z}\) be the set of \(x \in \mathbb{Z}\) such that \[\sum_{y: (x,y) \in E'} g(y)^q \leq \delta^{1/8}.\] Then from 10 it follows that \[\delta^{1/4} \gg \sum_{x \notin X} f(x)^p \sum_{y: (x,y) \in E'} g(y)^q \geq \delta^{1/8} \sum_{x \notin X} f(x)^p,\] and hence \[\label{HY-exceptionalX} \sum_{x\notin X} f(x)^p \ll \delta^{1/8}.\tag{12}\] For every \(x_1, x_2 \in X\), since \[\sum_{y: (x_1,y) \in E'} g(y)^q + \sum_{y: (x_2,y) \in E'} g(y)^q \ll \delta^{1/8},\] there exists \(y \in \mathbb{Z}\) such that \((x_1,y) \notin E'\) and \((x_2,y)\notin E'\). By 11 we have \[f(x_1)^p = (1 + O(\delta^{1/8})) g(y)^q, \;\;f(x_2)^p = (1 + O(\delta^{1/8})) g(y)^q.\] We conclude that there exists a constant \(a \in \mathbb{R}\) such that \[f(x) = (1 + O(\delta^{1/8})) a\] for every \(x \in X\). Moreover, since \[1 = \sum_{x \in \mathbb{Z}} f(x)^p = \sum_{x \in X} f(x)^p + O(\delta^{1/8}) = (1 + O(\delta^{1/8})) a^p |X| + O(\delta^{1/8}),\] we have \[|X| = (1 + O(\delta^{1/8})a^{-p}.\] By symmetry, we may also conclude the existence of a constant \(b \in \mathbb{R}\) such that \[g(y) = (1 + O(\delta^{1/8})) b\] for every \(y \in Y\), where \(Y \subset \mathbb{Z}\) is a subset satisfying \[|Y| = (1 + O(\delta^{1/8})b^{-q}.\] We now return to using the first part of 11 for \((x,y) \in M := (X \times Y)\setminus E'\). First note from 10 that \[\delta^{1/4} \gg \sum_{(x,y) \in (X\times Y) \cap E'} f(x)^p g(y)^q \gg a^p b^q \cdot |(X\times Y) \cap E'| \gg |X|^{-1}|Y|^{-1} \cdot |(X\times Y) \cap E'|,\] and hence \[|M| \geq (1 - O(\delta^{1/4})) |X||Y|.\] For \((x,y) \in M\), 11 implies that \[\frac{a^pb^q}{h(x+y)} = (1 + O(\delta^{1/8}) a^p = (1 + O(\delta^{1/8})) b^q.\] In particular, since \(M\) is non-empty, we have \(a^p = (1 + O(\delta^{1/8})) b^q\) and hence \(|X| = (1 + O(\delta^{1/8})) |Y|\). Moreover, for \(s \in X+_MY\) we have \[h(s) = (1 + O(\delta^{1/8})) a^p.\] Since \(\sum_{s \in \mathbb{Z}}h(s) = 1\), we have \[1 \geq \sum_{s \in X+_MY} h(s) = (1 - O(\delta^{1/8}))a^p \cdot |X+_MY|,\] and hence \[|X+_MY| \leq (1 + O(\delta^{1/8})) |X|.\] We now apply Lemma 8 with \(\varepsilon= 1/100\) (say), after possibly shrinking one of \(X, Y\) slightly so that \(|X| = |Y|\), to conclude that there exists a coset \(x_0 + H\) of a subgroup \(H \subset \mathbb{Z}\) such that \[|X \setminus (x_0+H)| \leq \frac{1}{10}|X|, \;\;|(x_0+H) \setminus X| \leq \frac{1}{10}|X|.\] The only finite subgroup of \(\mathbb{Z}\) is \(H = \{0\}\), and hence it must be that \(X = \{x_0\}\). The desired conclusions follow immediately from 12 . ◻
Let \(f: \mathbb{Z}\rightarrow \mathbb{R}\) be a function which is supported on a set of size \(n \geq 2\). By replacing \(f\) by \(|f|\), we may assume that \(f\) takes non-negative real values. Let \(\delta > 0\) be a sufficiently small absolute constant and let \[q = \frac{4}{3 - \log_n(1+\delta)}\] First consider the case when \[\|\widehat{f}\|_4 \leq (1 - \delta) \|f\|_{4/3}.\] By Hölder’s inequality (see 3 ), we have \[\|f\|_{4/3} \leq n^{3/4-1/q} \|f\|_q = (1+\delta)^{1/4} \|f\|_q.\] It follows that \[\|\widehat{f}\|_4 \leq (1-\delta) (1+\delta)^{1/4} \|f\|_q \leq \|f\|_q.\]
Now suppose that \[\|\widehat{f}\|_4 \geq (1 - \delta) \|f\|_{4/3}.\] By normalization we may assume that \(\|f\|_{4/3} = 1\), and thus \(\|f*f\|_2 = \|\widehat{f}\|_4^2 \geq 1-2\delta\). By Proposition 8, there exists \(x_0 \in \mathbb{Z}\) such that \[\label{proof-upper-bound1} \|f - f(x_0)1_{\{x_0\}}\|_{4/3} \ll \delta^{1/20}.\tag{13}\] By translation we may assume that \(x_0=0\), and we may write \(f\) in the form \(f = f(0)\delta_0 + g\), where \(\delta_0\) is the Kronecker delta function and \(g(0) = 0\). Let \(x = f(0)\) and \(y = \|g\|_{4/3}\). Since \(\|f\|_{4/3}=1\) we have \[x^{4/3} + y^{4/3} = 1.\] From 13 we have \[y = O(\delta^{1/20}), \;\;x = 1 - O(\delta^{1/20}).\] In particular we have \(y/x \leq 0.01\). Since \(f*f = x^2\delta_0 + 2xg + g*g\), we have \[\|f*f\|_2 \leq x\|x\delta_0 + 2g\|_2 + \|g*g\|_2 = x \sqrt{\|x\delta_0\|_2^2 + \|2g\|_2^2} + \|g*g\|_2.\] Using the inequalities \(\|g\|_2 \leq \|g\|_{4/3} = y\) and \(\|g*g\|_2 \leq \|g\|_{4/3}^2 = y^2\), we obtain \[\|f*f\|_2 \leq x\sqrt{x^2 + 4y^2} + y^2 = x^2 \sqrt{1 + \frac{4y^2}{x^2}} + y^2.\] Since \(\sqrt{1+\lambda} \leq 1 + \lambda/2\) for \(\lambda \geq 0\), it follows that \[\|f*f\|_2 \leq x^2\left(1 + \frac{2y^2}{x^2}\right) + y^2 = x^2 + 3y^2.\] On the other hand, note that \[\|f\|_q = (x^q + \|g\|_q^q)^{1/q}.\] Since \(g\) is supported on a set of size \(n\), by Hölder’s inequality we have \[\|g\|_{4/3} \leq n^{3/4 - 1/q} \|g\|_q = (1+\delta)^{1/4} \|g\|_q.\] By choosing \(\delta>0\) to be small enough, we have \(\|g\|_q^q \geq 0.9 \|g\|_{4/3}^q = 0.9y^q\), and hence \[\|f\|_q^2 \geq (x^q + 0.9y^q)^{2/q} = x^2\left(1 + \frac{0.9y^q}{x^q}\right)^{2/q}.\] Since \(4/3 \leq q \leq 3/2\), we have \((1+\lambda)^{2/q} \geq 1+\lambda \geq 1+4\lambda^{2/q}\) for \(0 \leq \lambda \leq 1/64\). Hence \[\|f\|_q^2 \geq x^2\left(1 + 4 \cdot 0.9^{2/q} \cdot \frac{y^2}{x^2}\right) \geq x^2 + 3y^2.\] It follows that \(\|f*f\|_2 \leq \|f\|_q^2\), as desired.
Let \(n \geq 3\) be a positive integer and let \(I\) be the interval \[I = \left\{-\Bigl\lfloor \frac{n-1}{2}\Bigr\rfloor, \cdots, \Bigl\lfloor \frac{n}{2}\Bigr\rfloor\right\}\] which has length \(n\). In view of Proposition 3, it suffices to construct a function \(f: I \rightarrow \mathbb{R}\) such that \(|\widehat{f}\|_4 > \|f\|_q\), where \[q = \frac{4}{\log_n \frac{2n^3+n}{3}}.\] We take \(f = 1_I + \varepsilon\delta_0\) for some small \(\varepsilon> 0\), where \(\delta_0\) is the Kronecker delta function. Note that \(\|\widehat{1_I}\|_4 = \|1_I\|_q\), and we will show that the small adjustment from \(1_I\) to \(f\) swings the inequality in the desired direction.
First note that \[\|f\|_q^q = n-1 + (1+\varepsilon)^q = n + q\varepsilon+ O(\varepsilon^2).\] Hence \[\|f\|_q^4 = n^{4/q} \left(1 + \frac{q\varepsilon}{n} + O\left(\frac{\varepsilon^2}{n}\right)\right)^{4/q} = n^{4/q} \left(1 + \frac{4\varepsilon}{n} + O\left(\frac{\varepsilon^2}{n}\right)\right).\] Since \(n^{4/q} = (2n^3+n)/3\), it follows that \[\label{thm2-eq1} \|f\|_q^4 = \frac{1}{3}(2n^3+n) + \frac{4}{3}(2n^2+1)\varepsilon+ O(n^2\varepsilon^2).\tag{14}\] Now consider the convolution \[f*f = 1_I*1_I + 2\varepsilon 1_I + \varepsilon^2\delta_0.\] We have \[\begin{align} \|f*f\|_2^2 &= \sum_{a \notin I} 1_I*1_I(a)^2 + \sum_{a \in I\setminus \{0\}} (1_I*1_I(a) + 2\varepsilon)^2 + (1_I*1_I(0) + 2\varepsilon+ \varepsilon^2)^2 \\ &= \sum_{a \notin I} 1_I*1_I(a)^2 + \sum_{a \in I} (1_I*1_I(a) + 2\varepsilon)^2 + O(n\varepsilon^2) \\ &= \sum_{a \in \mathbb{Z}} 1_I*1_I(a)^2 + 4\varepsilon\sum_{a \in I} 1_I*1_I(a) + O(n\varepsilon^2) \end{align}\] One can compute that \[\sum_{a \in \mathbb{Z}}1_I*1_I(a)^2 = E(I) = \frac{1}{3}(2n^3+n)\] and \[\sum_{a \in I}1_I*1_I(a) = \Bigl\lceil \frac{3n^2}{4}\Bigr\rceil \geq \frac{3n^2}{4}\] Hence \[\label{thm2-eq2} \|f*f\|_2^2 \geq \frac{1}{3}(2n^3+n) + 3n^2\varepsilon+ O(n\varepsilon^2).\tag{15}\] Comparing 14 with 15 and noting that \[3n^2 > \frac{4}{3}(2n^2+1)\] for every \(n \geq 3\), we conclude that \[\|f*f\|_2^2 > \|f\|_q^4\] for sufficiently small \(\varepsilon> 0\). This completes the proof.