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

It follows that

Proof ▶

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

\[ e^{tx}\le \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}\le \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)\\ & \le \prod _{\gamma \in \Gamma }\left( \cosh \lvert \widehat{f}(\gamma )\rvert +\Re c_\gamma \gamma (x)\sinh \lvert \widehat{f}(\gamma )\rvert \right). \end{align*}

Therefore

\[ \mathop{ \mathchoice {\vcenter {\hbox{{\@tempdima +4\p@ \@tempdima 2.0002\@tempdima \divide \@tempdima \p@ \@tempcnta \@tempdima \@tempdimb \f@size \p@ \def\@tempa {1.09545}\@whilenum {\@tempcnta {\gt}\z@ }\do {\advance \m@ne \@tempdimb 1.09545\@tempdimb }\PackageWarning{relsize}{Font size ??? is too small.\MessageBreak Using 999pt instead}\@tempdimb =999pt\def\@tempa {\relax }\@tempdima -\@m \p@ \let\rs@size \rs@lookup \@tempdima 100\@tempdima }\relax $\mathbb {E}$}}} {\kern 0pt\mathbb {E}} {\kern 0pt\mathbb {E}} {\kern 0pt\mathbb {E}} }\displaylimits _x e^{\Re f(x)}\le \mathop{ \mathchoice {\vcenter {\hbox{{\@tempdima +4\p@ \@tempdima 2.0002\@tempdima \divide \@tempdima \p@ \@tempcnta \@tempdima \@tempdimb \f@size \p@ \def\@tempa {1.09545}\@whilenum {\@tempcnta {\gt}\z@ }\do {\advance \m@ne \@tempdimb 1.09545\@tempdimb }\PackageWarning{relsize}{Font size ??? is too small.\MessageBreak Using 999pt instead}\@tempdimb =999pt\def\@tempa {\relax }\@tempdima -\@m \p@ \let\rs@size \rs@lookup \@tempdima 100\@tempdima }\relax $\mathbb {E}$}}} {\kern 0pt\mathbb {E}} {\kern 0pt\mathbb {E}} {\kern 0pt\mathbb {E}} }\displaylimits _x \prod _{\gamma \in \Gamma } \left( \cosh \lvert \widehat{f}(\gamma )\rvert +\Re c_\gamma \gamma (x)\sinh \lvert \widehat{f}(\gamma )\rvert \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 _3=\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

The conclusion now follows using $\cosh (x) \le 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 }\le 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 4\sqrt{pe} \lVert f\rVert _2$.

Proof ▶

It is enough to show that $\lVert \Re f\rVert _p \le 2\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 4\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 $ \mathop{ \mathchoice {\vcenter {\hbox{{\@tempdima +4\p@ \@tempdima 2.0002\@tempdima \divide \@tempdima \p@ \@tempcnta \@tempdima \@tempdimb \f@size \p@ \def\@tempa {1.09545}\@whilenum {\@tempcnta {\gt}\z@ }\do {\advance \m@ne \@tempdimb 1.09545\@tempdimb }\PackageWarning{relsize}{Font size ??? is too small.\MessageBreak Using 999pt instead}\@tempdimb =999pt\def\@tempa {\relax }\@tempdima -\@m \p@ \let\rs@size \rs@lookup \@tempdima 100\@tempdima }\relax $\mathbb {E}$}}} {\kern 0pt\mathbb {E}} {\kern 0pt\mathbb {E}} {\kern 0pt\mathbb {E}} }\displaylimits \exp |\Re f| \le 2\exp (\frac p2) = (2\sqrt e)^p$. 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!} = \mathop{ \mathchoice {\vcenter {\hbox{{\@tempdima +4\p@ \@tempdima 2.0002\@tempdima \divide \@tempdima \p@ \@tempcnta \@tempdima \@tempdimb \f@size \p@ \def\@tempa {1.09545}\@whilenum {\@tempcnta {\gt}\z@ }\do {\advance \m@ne \@tempdimb 1.09545\@tempdimb }\PackageWarning{relsize}{Font size ??? is too small.\MessageBreak Using 999pt instead}\@tempdimb =999pt\def\@tempa {\relax }\@tempdima -\@m \p@ \let\rs@size \rs@lookup \@tempdima 100\@tempdima }\relax $\mathbb {E}$}}} {\kern 0pt\mathbb {E}} {\kern 0pt\mathbb {E}} {\kern 0pt\mathbb {E}} }\displaylimits \frac{|\Re f|^p}{p!} \le \mathop{ \mathchoice {\vcenter {\hbox{{\@tempdima +4\p@ \@tempdima 2.0002\@tempdima \divide \@tempdima \p@ \@tempcnta \@tempdima \@tempdimb \f@size \p@ \def\@tempa {1.09545}\@whilenum {\@tempcnta {\gt}\z@ }\do {\advance \m@ne \@tempdimb 1.09545\@tempdimb }\PackageWarning{relsize}{Font size ??? is too small.\MessageBreak Using 999pt instead}\@tempdimb =999pt\def\@tempa {\relax }\@tempdima -\@m \p@ \let\rs@size \rs@lookup \@tempdima 100\@tempdima }\relax $\mathbb {E}$}}} {\kern 0pt\mathbb {E}} {\kern 0pt\mathbb {E}} {\kern 0pt\mathbb {E}} }\displaylimits \exp |\Re f| \]

Rearranging, $\lVert \Re f\rVert _p \le 2 p\sqrt{e} = 2 \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}\le E_{2m}(\Delta ;\nu ). \]

Proof ▶

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

\[ \eta \lVert f\rVert _1\left\lvert \Delta \right\rvert \le \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 \le \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\le \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 \le \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}\le \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}\le 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) \le (32e m \left\lvert A\right\rvert )^m$.

Proof ▶

By Lemma 2.9 and Lemma 2.3

\begin{align*} E_{2m}(A) & = \mathop{ \mathchoice {\vcenter {\hbox{{\@tempdima +4\p@ \@tempdima 2.0002\@tempdima \divide \@tempdima \p@ \@tempcnta \@tempdima \@tempdimb \f@size \p@ \def\@tempa {1.09545}\@whilenum {\@tempcnta {\gt}\z@ }\do {\advance \m@ne \@tempdimb 1.09545\@tempdimb }\PackageWarning{relsize}{Font size ??? is too small.\MessageBreak Using 999pt instead}\@tempdimb =999pt\def\@tempa {\relax }\@tempdima -\@m \p@ \let\rs@size \rs@lookup \@tempdima 100\@tempdima }\relax $\mathbb {E}$}}} {\kern 0pt\mathbb {E}} {\kern 0pt\mathbb {E}} {\kern 0pt\mathbb {E}} }\displaylimits _\gamma \left\lvert \hat1_A(\gamma )\right\rvert ^{2m} \\ & = \lVert \hat1_A\rVert _{2m}^{2m} \\ & \le (4\sqrt{2em})^{2m} \lVert \hat1_A\rVert _2^{2m} \\ & = (32em)^m \lVert 1_A\rVert _2^{2m} \\ & = (32em)^m \left\lvert A\right\rvert ^m \end{align*}

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 \le 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 \le 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 \le \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 )\le m!K^m. \]

On the other hand, by Lemma 2.8,

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

Rearranging these bounds, we have

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

Therefore $K\le \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}\le e$.