2 Chang’s lemma

Definition 2.1 Dissociation ✓

We say that \(A\subseteq G\) is dissociated if, for any \(m\geq 1\), and any \(x\in G\), there is at most one \(A'\subset A\) of size \(\left\lvert A'\right\rvert =m\) such that

\[ \sum _{a\in A'}a=x. \]

Lemma 2.2 Rudin’s exponential inequality

If the discrete Fourier transform of \(f : G \longrightarrow \mathbb {C}\) has dissociated support, then \(\mathbb {E}\exp (\Re f) \le \exp (\frac{\lVert f\rVert _2^2}2)\).

Proof ▼

Using the convexity of \(t\mapsto e^{tx}\) (for all \(x\geq 0\) and \(t\in [-1,1]\)) we have

\[ e^{tx}\leq \cosh (x)+t\sinh (x). \]

It follows (taking \(x=\lvert z\rvert \) and \(t=\Re (z)/\lvert z\rvert \)) that, for any \(z\in \mathbb {C}\),

\[ e^{\Re z}\leq \cosh (\lvert z\rvert )+\Re (z/\lvert z\rvert )\sinh (\lvert z\rvert ). \]

In particular, if \(c_\gamma \in \mathbb {C}\) with \(\lvert c_\gamma \rvert =1\) is such that \(\widehat{f}(\gamma )=c_\gamma \lvert \widehat{f}(\gamma )\rvert \), then

\begin{align*} e^{\Re f(x)} & = \exp \left( \Re \sum _{\gamma \in \Gamma }\widehat{f}(\gamma )\gamma (x)\right)\\ & =\prod _{\gamma \in \Gamma } \exp \left( \Re \widehat{f}(\gamma )\gamma (x)\right)\\ & \leq \prod _{\gamma \in \Gamma }\left( \cosh (\lvert \widehat{f}(\gamma )\rvert )+\Re c_\gamma \gamma (x)\sinh (\lvert \widehat{f}(\gamma ))\right). \end{align*}

Therefore

\[ \mathbb {E}_x e^{\Re f(x)}\leq \mathbb {E}_x \left( \cosh (\lvert \widehat{f}(\gamma )\rvert )+\Re c_\gamma \gamma (x)\sinh (\lvert \widehat{f}(\gamma ))\right). \]

Using \(\Re z=(z+\overline{z})/2\) the product here can be expanded as the sum of

\[ \prod _{\gamma \in \Gamma _2}\frac{c_\gamma }{2}\prod _{\gamma \in \Gamma _3}\frac{\overline{c_\gamma }}{2}\left(\prod _{\gamma \in \Gamma _1}\cosh (\lvert \widehat{f}(\gamma )\rvert )\right)\left(\prod _{\gamma \in \Gamma _2\cup \Gamma _3}\sinh (\lvert \widehat{f}(\gamma )\rvert )\right)\left(\sum _{\gamma \in \Gamma _2}\gamma -\sum _{\lambda \in \Gamma _3}\lambda \right)(x) \]

as \(\Gamma _1\sqcup \Gamma _2\sqcup \Gamma _3=\Gamma \) ranges over all partitions of \(\Gamma \) into three disjoint parts. Using the definition of dissociativity we see that

\[ \sum _{\gamma \in \Gamma _2}\gamma -\sum _{\lambda \in \Gamma _3}\lambda \neq 0 \]

unless \(\Gamma _2=\Gamma _2=\emptyset \). In particular summing this term over all \(x\in G\) gives \(0\). Therefore the only term that survives averaging over \(x\) is when \(\Gamma _1=\Gamma \), and so

\[ \mathbb {E}_x e^{\Re f(x)}\leq \prod _{\gamma \in \Gamma } \cosh (\lvert \widehat{f}(\gamma )\rvert ). \]

The conclusion now follows using \(\cosh (x) \leq e^{x^2/2}\) and \(\sum _{\gamma \in \Gamma }\lvert \widehat{f}(\gamma )\rvert ^2=\| f\| _2^2\). The second conclusion follows by applying it to \(f(x)\) and \(-f(x)\) and using

\[ e^{\left\lvert y\right\rvert }\leq e^y+e^{-y}. \]

Lemma 2.3 Rudin’s inequality ✓

If the discrete Fourier transform of \(f : G \longrightarrow \mathbb {C}\) has dissociated support and \(p \ge 2\) is an integer, then \(\lVert f\rVert _p \le 2 * \sqrt{pe} \lVert f\rVert _2\).

Proof ▼

It is enough to show that \(\lVert \Re f\rVert _p \le \sqrt{pe} \lVert f\rVert _2\) as then

\[ \lVert f\rVert _p \le \lVert \Re f\rVert _p + \lVert i \Im f\rVert _p = \lVert \Re f\rVert _p + \lVert \Re (-if)\rVert _p \le 2 \sqrt{pe} \lVert f\rVert _2 \]

If \(f = 0\), the result is obvious. So assume \(f \ne 0\). \(\lVert f\rVert _2 {\gt} 0\), so WLOG \(\lVert f\rVert _2 = \sqrt p\).

Rudin’s exponential inequality for \(f\) becomes \(\mathbb {E}\exp |\Re f| \le \exp (\frac p2)\). Using \(\frac{x^p}{p!} \le e^x\) for positive \(x\), we get

\[ \frac{\lVert \Re f\rVert _p^p}{p^p} \le \frac{\lVert \Re f\rVert _p^p}{p!} = \mathbb {E}\frac{|\Re f|^p}{p!} \le \mathbb {E}\exp |\Re f| \]

Rearranging, \(\lVert \Re f\rVert _p \le p\sqrt{e} = \sqrt{pe} \lVert f\rVert _2\).

Definition 2.4 Large spectrum ✓

Let \(G\) be a finite abelian group and \(f:G\to \mathbb {C}\). Let \(\eta \in \mathbb {R}\). The \(\eta \)-large spectrum is defined to be

\[ \Delta _\eta (f) = \{ \gamma \in \widehat{G} : \lvert \widehat{f}(\gamma )\rvert \geq \eta \lVert f\rVert _1\} . \]

Definition 2.5 Weighted energy ✓

Let \(\Delta \subseteq \widehat{G}\) and \(m\geq 1\). Let \(\nu :G\to \mathbb {C}\). Then

\[ E_{2m}(\Delta ;\nu )=\sum _{\gamma _1,\ldots ,\gamma _{2m}\in \Delta }\left\lvert \widehat{\nu }(\gamma _1+\cdots -\gamma _{2m})\right\rvert . \]

Definition 2.6 Energy ✓

Let \(G\) be a finite abelian group and \(A\subseteq G\). Let \(m\geq 1\). We define

\[ E_{2m}(A)=\sum _{a_1,\ldots ,a_{2m}\in A}1_{a_1+\cdots -a_{2m}=0}. \]

Lemma 2.7 ✓

Let \(G\) be a finite abelian group and \(f:G\to \mathbb {C}\). Let \(\nu :G\to \mathbb {R}_{\geq 0}\) be such that whenever \(\left\lvert f\right\rvert \neq 0\) we have \(\nu \geq 1\). Let \(\Delta \subseteq \Delta _\eta (f)\). Then, for any \(m\geq 1\).

\[ \eta ^{2m}\frac{\lVert f\rVert _1^2}{\lVert f\rVert _2^2}\left\lvert \Delta \right\rvert ^{2m}\leq E_{2m}(\Delta ;\nu ). \]

Proof ▼

By definition of \(\Delta _\eta (f)\) we know that

\[ \eta \lVert f\rVert _1\left\lvert \Delta \right\rvert \leq \sum _{\gamma \in \Delta } \lvert \widehat{f}(\gamma )\rvert . \]

There exists some \(c_\gamma \in \mathbb {C}\) with \(\lvert c_\gamma \rvert =1\) for all \(\gamma \) such that

\[ \lvert \widehat{f}(\gamma )\rvert =c_\gamma \widehat{f}(\gamma )=c_\gamma \sum _{x\in G}f(x)\overline{\gamma (x)}. \]

Interchanging the sums, therefore,

\[ \eta \lVert f\rVert _1\left\lvert \Delta \right\rvert \leq \sum _{x\in G}f(x)\sum _{\gamma \in \Delta } c_\gamma \overline{\gamma (x)}. \]

By Hölder’s inequality the right-hand side is at most

\[ \left( \sum _x \left\lvert f(x)\right\rvert \right)^{1-1/m}\left( \sum _x \left\lvert f(x)\right\rvert \left\lvert \sum _{\gamma \in \Delta }c_\gamma \overline{\gamma (x)}\right\rvert ^m\right)^{1/m}. \]

Taking \(m\)th powers, therefore, we have

\[ \eta ^m\left\lvert \Delta \right\rvert ^m\lVert f\rVert _1\leq \sum _{x}\left\lvert f(x)\right\rvert \left\lvert \sum _{\gamma \in \Delta }c_\gamma \overline{\gamma (x)}\right\rvert ^m. \]

By assumption we can bound \(\left\lvert f(x)\right\rvert \leq \left\lvert f(x)\right\rvert \nu (x)^{1/2}\), and therefore by the Cauchy-Schwarz inequality the right-hand side is bounded above by

\[ \lVert f\rVert _2\left( \sum _x \nu (x)\left\lvert \sum _{\gamma \in \Delta }c_\gamma \overline{\gamma (x)}\right\rvert ^{2m}\right)^{1/2}. \]

Squaring and simplifying, we deduce that

\[ \eta ^{2m}\left\lvert \Delta \right\rvert ^{2m}\frac{\lVert f\rVert _1^2}{\lVert f\rVert _2^2}\leq \sum _x \nu (x)\left\lvert \sum _{\gamma \in \Delta }c_\gamma \overline{\gamma (x)}\right\rvert ^{2m}. \]

Expanding out the power, the right-hand side is equal to

\[ \sum _x \nu (x)\sum _{\gamma _1,\ldots ,\gamma _{2m}}c_{\gamma _1}\cdots \overline{c_{\gamma _{2m}}} (\overline{\gamma _1}\cdots \gamma _{2m})(x). \]

Changing the order of summation this is equal to

\[ \sum _{\gamma _1,\ldots ,\gamma _{2m}}c_{\gamma _1}\cdots \overline{c_{\gamma _{2m}}} \widehat{\nu }(\gamma _1\cdots \overline{\gamma _{2m}}). \]

The result follows by the triangle inequality.

Lemma 2.8 ✓

Let \(G\) be a finite abelian group and \(f:G\to \mathbb {C}\). Let \(\Delta \subseteq \Delta _\eta (f)\). Then, for any \(m\geq 1\).

\[ N^{-1}\eta ^{2m}\frac{\lVert f\rVert _1^2}{\lVert f\rVert _2^2}\left\lvert \Delta \right\rvert ^{2m}\leq E_{2m}(\Delta ). \]

Proof ▼

Apply Lemma 2.7 with \(\nu \equiv 1\), and use the fact that \(\sum _x \lambda (x)\) is \(N\) if \(\lambda \equiv 1\) and \(0\) otherwise.

Lemma 2.9 ✓

If \(A\subset G\) and \(m\geq 1\) then

\[ E_{2m}(A) = \sum _x 1_A^{(m)}(x)^2. \]

Proof ▼

Expand out definitions.

Lemma 2.10

If \(A\subseteq G\) is dissociated then \(E_{2m}(A) \leq (8e m \left\lvert A\right\rvert )^m\).

Proof ▼

By Lemma 2.9

\[ E_{2m}(A) = \sum _x 1_A^{(m)}(x)^2. \]

By the definition of dissociativity, \(1_A^{(m)}(x)\leq m!\) for all \(x\in G\). We are done since

\[ \sum _x 1_A^{(m)}(x) = \left\lvert A\right\rvert ^m. \]

TODO(Thomas): This proof is wrong.

Lemma 2.11 ✓

If \(A\subseteq G\) contains no dissociated set with \(\geq K+1\) elements then there is \(A'\subseteq A\) of size \(\left\lvert A'\right\rvert \leq K\) such that

\[ A\subseteq \left\{ \sum _{a\in A'}c_aa : c_a\in \{ -1,0,1\} \right\} . \]

Proof ▼

Let \(A'\subseteq A\) be a maximal dissociated subset (this exists and is non-empty, since trivially any singleton is dissociated). We have \(\left\lvert A'\right\rvert \leq K\) by assumption.

Let \(S\) be the span on the right-hand side. It is obvious that \(A'\subseteq S\). Suppose that \(x\in A\backslash A'\). Then \(A'\cup \{ x\} \) is not dissociated by maximality. Therefore there exists some \(y\in G\) and two distinct sets \(B,C\subseteq A'\cup \{ x\} \) such that

\[ \sum _{b\in B}b = y = \sum _{c\in C} c. \]

If \(x\not\in B\) and \(x\not\in C\) then this contradicts the dissociativity of \(A'\). If \(x\in B\) and \(x\in C\) then we have

\[ \sum _{b\in B\backslash x}b=y-x=\sum _{c\in C\backslash x}c, \]

again contradicting the dissociativity of \(A'\). Without loss of generality, therefore, \(x\in B\) and \(x\not\in C\). Therefore

\[ x=\sum _{c\in C}c - \sum _{b\in B\backslash x}b \]

which is in the span as required.

Theorem 2.12 Chang’s lemma ✓

Let \(G\) be a finite abelian group and \(f:G\to \mathbb {C}\). Let \(\eta {\gt}0\) and \(\alpha =N^{-1}\lVert f\rVert _1^2/\lVert f\rVert _2^2\). There exists some \(\Delta \subseteq \Delta _\eta (f)\) such that

\[ \left\lvert \Delta \right\rvert \leq \lceil e\mathcal{L}(\alpha )\eta ^{-2}\rceil \]

and

\[ \Delta _\eta (f)\subseteq \left\{ \sum _{\gamma \in \Delta }c_\gamma \gamma : c_\gamma \in \{ -1,0,1\} \right\} . \]

Proof ▼

By Lemma 2.11 it suffices to show that \(\Delta _\eta (f)\) contains no dissociated set with at least

\[ K= \lceil e\mathcal{L}(\alpha )\eta ^{-2}\rceil +1 \]

many elements. Suppose not, and let \(\Delta \subseteq \Delta _\eta (f)\) be a dissociated set of size \(K\). Then by Lemma 2.10 we have, for any \(m\geq 1\),

\[ E_{2m}(\Delta )\leq m!K^m. \]

On the other hand, by Lemma 2.8,

\[ \eta ^{2m}\alpha K^{2m}\leq E_{2m}(\Delta ). \]

Rearranging these bounds, we have

\[ K^m \leq m! \alpha ^{-1}\eta ^{-2m}\leq m^m\alpha ^{-1}\eta ^{-2m}. \]

Therefore \(K\leq \alpha ^{-1/m}m\eta ^{-2}\). This is a contradiction to the choice of \(K\) if we choose \(m=\mathcal{L}(\alpha )\), since \(\alpha ^{-1/m}\leq e\).