Proof. By nesting of norms, it suffices to prove the case $p=2k$ for some $k\in \mathbb{N}$. Write $X={\sum }_{i=1}^n{X}_i$, and assume ${\sum }_{i=1}^n\parallel X_i{\parallel }_{L^{\infty }(\mathbb{P})}^2=1$. Note that in fact ${\sum }_{i=1}^n\parallel X_i{\parallel }_{L^2(\mathbb{P})}^2={\sum }_{i=1}^n\parallel X_i{\parallel }_{L^{\infty }(\mathbb{P})}^2$, hence ${\sum }_{i=1}^n\parallel X_i{\parallel }_{L^2(\mathbb{P})}^2=1$.

By Chernoff’s inequality (Example 2.5), for all $𝜃>0$ we have

$$\mathbb{P}(|X|\ge 𝜃)\le 4\exp \left(-\frac{{𝜃}^2}{4}\right),$$

and so using the fact that $\mathbb{P}(|X|\le t)={\int }_0^t{\rho }_X(s)ds$ we have

We shall show by induction on $k$ that $I(K)\le 2^{2k}\frac{{(2k)}^k}{4k}$. Indeed, when $k=1$,

For $k>1$, integrate by parts to find that

Proof. Let $f\in L^p({𝔽}_2^n)$ and write $g={\sum }_{\gamma \in \mathrm{\Gamma }}\widehat{f}(\gamma )\gamma$. Then

$$\begin{array}{llllll}\hfill \parallel \widehat{f}{\parallel }_{l^2(\mathrm{\Gamma })}^2& =\sum _{\gamma \in \mathrm{\Gamma }}|\widehat{f}(\gamma ){|}^2& \hfill & & \hfill & \\ \hfill & ={⟨\widehat{f},\widehat{g}⟩}_{l^2(\widehat{{𝔽}_2^n})}& \hfill & & \hfill & \\ \hfill & ={⟨f,g⟩}_{L^2({𝔽}_2^n)}& \hfill & \text{by }\text{Plancherel’s identity}& \hfill & & \hfill & \end{array}$$

which is bounded above by $\parallel f{\parallel }_{L^p({𝔽}_2^n)}\parallel g{\parallel }_{L^{p^{\prime }}({𝔽}_2^n)}$ where $\frac{1}{p}+\frac{1}{p^{\prime }}=1$, using Hölder’s inequality.

By Rudin’s Inequality,

$$\parallel g{\parallel }_{L^{p^{\prime }}({𝔽}_2^n)}=O\left(\sqrt{p^{\prime }}\parallel \widehat{g}{\parallel }_{l^2(\mathrm{\Gamma })}\right)=O\left(\sqrt{\frac{p}{p-1}}\parallel \widehat{f}{\parallel }_{l^2(\mathrm{\Gamma })}\right).\square$$

Proof. Let $\mathrm{\Gamma }\subseteq {\mathrm{Spec}}_{\rho }({𝟙}_A)$ be a maximal linearly independent set. Let $H=⟨{\mathrm{Spec}}_{\rho }({𝟙}_A)⟩$. Clearly $\dim (H)=|\mathrm{\Gamma }|$. By Corollary 3.3, for all $p\in (1,2]$,

$${(\rho \alpha )}^2|\mathrm{\Gamma }|\le \sum _{\gamma \in \mathrm{\Gamma }}|\widehat{{𝟙}_A}(\gamma ){|}^2=\parallel \widehat{{𝟙}_A}{\parallel }_{l^2(\mathrm{\Gamma })}^2=O\left(\frac{p}{p-1}\parallel {𝟙}_A{\parallel }_{L^p({𝔽}_2^n)}^2\right),$$

so

$$|\mathrm{\Gamma }|=O\left({\rho }^{-2}{\alpha }^{-2}{\alpha }^{2∕p}\frac{p}{p-1}\right).$$

Set $p=1+{(\log {\alpha }^{-1})}^{-1}$ to get $|\mathrm{\Gamma }|=O({\rho }^{-2}{\alpha }^{-2}({\alpha }^2\cdot e^2)(\log {\alpha }^{-1}+1))$. □

Proof. First assume the distribution of the $X_i$’s is symmetric, i.e. $\mathbb{P}(X_i=a)=\mathbb{P}(X_i=-a)$ for all $a\in ℝ$. Partition the probability space $\mathrm{\Omega }$ into sets ${\mathrm{\Omega }}_1,{\mathrm{\Omega }}_2,\dots ,{\mathrm{\Omega }}_M$, write ${\mathbb{P}}_j$ for the induced measure on ${\mathrm{\Omega }}_j$ such that all $X_i$’s are symmetric and take at most 2 values. By Khintchine’s inequality, for each $j\in [M]$,

$$\begin{array}{llll}\hfill {\parallel \sum _{i=1}^n{X}_i\parallel }_{L^p({\mathbb{P}}_j)}^p& =O\left(p^{p∕2}{\left(\sum _{i=1}^n\parallel X_i{\parallel }_{L^2({\mathbb{P}}_j)}^2\right)}^{p∕2}\right)& \hfill & \\ \hfill & =O\left(p^{p∕2}{\parallel \sum _{i=1}^n|X_i{|}^2\parallel }_{L^{p∕2}({\mathbb{P}}_j)}^{p∕2}\right)& \hfill & \end{array}$$

so summing over all $j$ and taking $p$-th roots gives the symmetric case. Now suppose the $X_i$’s are arbitrary, and let $Y_1,\dots ,Y_n$ be such that $Y_i\sim X_i$ and $X_1,X_2,\dots ,X_n,Y_1,Y_2,\dots ,Y_n$ are all independent. Applying the symmetric case to $X_i-Y_i$,

$$\begin{array}{llll}\hfill {\parallel \sum _{i=1}^n(X_i-Y_i)\parallel }_{L^p(\mathbb{P}\times \mathbb{P})}& =O\left(p^{\frac{1}{2}}{\parallel \sum _{i=1}^n|X_i-Y_i{|}^2\parallel }_{L^{p∕2}(\mathbb{P}\times \mathbb{P})}^{\frac{1}{2}}\right)& \hfill & \\ \hfill & =O\left(p^{\frac{1}{2}}{\parallel \sum _{i=1}^n|X_i-Y_i{|}^2\parallel }_{L^{p∕2}(\mathbb{P})}^{\frac{1}{2}}\right)& \hfill & \end{array}$$

But then

$$\begin{array}{lllll}\hfill {\parallel \sum _{i=1}^n{X}_i\parallel }_{L^p(\mathbb{P})}={\parallel \sum _{i=1}^n{X}_i-\underset{=0}{\underbrace{{𝔼}^Y\sum _{i=1}^n{Y}_i}}\parallel }_{L^p(\mathbb{P})}^p& & \hfill & & \hfill \\ \hfill & ={𝔼}^X{\left|\sum X_i-{𝔼}^Y\sum Y_i\right|}^p& \hfill & & \hfill & \\ \hfill & ={𝔼}^X{\left|{𝔼}^Y\sum (X_i-Y_i)\right|}^p& \hfill & & \hfill & \\ \hfill & \le {𝔼}^X{𝔼}^Y{\left|\sum (X_i-Y_i)\right|}^p& \hfill & \text{by Jensen say}& \hfill & & \hfill & \\ \hfill & ={\parallel \sum (X_i-Y_i)\parallel }_{L^p(\mathbb{P}\times \mathbb{P})}^p& \hfill & & \hfill & \end{array}$$

concluding the proof. □

Proof. The main idea is to approximate

$$f\ast {\mu }_A(y)={𝔼}_{x}f(y-x){\mu }_A(x)={𝔼}_{x\in A}f(y-x)$$

by $\frac{1}{m}{\sum }_{i=1}^{m}f(y-z_i)$, where $z_i$ are sampled independently and uniformly from $A$, and $m$ is to be chosen later.

For each $y\in G$, define $Z_i(y)={\tau }_{-zi}f(y)-f\ast {\mu }_A(y)$. For each $y\in G$, these are independent random variables with mean $0$, so by Marcinkiewicz-Zygmund,

$$\begin{array}{llll}\hfill {\parallel \sum _{i=1}^m{Z}_i(y)\parallel }_{L^p(\mathbb{P})}^p& =O\left(p^{p∕2}{\parallel \sum _{i=1}^m|Z_i(y){|}^2\parallel }_{L^{p∕2}(\mathbb{P})}^{p∕2}\right)& \hfill & \\ \hfill & =O\left(p^{p∕2}{𝔼}_{(z_1,\dots ,z_m)\in A^m}{\left|\sum _{i=1}^m|Z_i(y){|}^2\right|}^{p∕2}\right)& \hfill & \end{array}$$

By Hölder with $\frac{1}{p^{\prime }}+\frac{2}{p}=1$, we get

$$\begin{array}{llll}\hfill {\left|\sum _{i=1}^m|Z_i(y){|}^2\right|}^{p∕2}& \le {\left(\sum _{i=1}^m{1}^{p^{\prime }}\right)}^{\frac{1}{p^{\prime }}\cdot \frac{p}{2}}{\left(\sum _{i=1}^m|Z_i(y){|}^{2\cdot p∕2}\right)}^{\frac{2}{p}\cdot \frac{p}{2}}& \hfill & \\ \hfill & \le {\left(\sum _{i=1}^m{1}^{p^{\prime }}\right)}^{\frac{p}{2}-1}{\left(\sum _{i=1}^m|Z_i(y){|}^{2\cdot p∕2}\right)}^{\frac{2}{p}\cdot \frac{p}{2}}& \hfill & \\ \hfill & =m^{p∕2-1}\sum _{i=1}^m|Z_i(y){|}^p& \hfill & \end{array}$$

so

$${\parallel \sum _{i=1}^m{Z}_i(y)\parallel }_{L^p(\mathbb{P})}^p=O\left(p^{p∕2}{m}^{p∕2-1}{𝔼}_{(z_1,\dots ,z_m)\in A^m}\sum _{i=1}^m|Z_i(y){|}^p\right).$$

Summing over all $y\in G$, we have

$${𝔼}_{y\in G}{\parallel \sum _{i=1}^m{Z}_i(y)\parallel }_{L^p(\mathbb{P})}^p=O\left(p^{p∕2}{m}^{p∕2-1}{𝔼}_{(z_1,\dots ,z_m)\in A^m}\sum _{i=1}^m{𝔼}_{y\in G}|Z_i(y){|}^p\right)$$

with

$$\begin{array}{llll}\hfill {\left({𝔼}_{y\in G}|Z_i(y){|}^p\right)}^{\frac{1}{p}}& =\parallel Z_i{\parallel }_{L^p(G)}& \hfill & \\ \hfill & =\parallel {\tau }_{-z_i}f-f\ast {\mu }_A{\parallel }_{L^p(G)}& \hfill & \\ \hfill & \le ,\parallel {\tau }_{-z_i}f{\parallel }_{L^p(G)}+\parallel f\ast {\mu }_A{\parallel }_{L^p(G)}& \hfill & \\ \hfill & \le \parallel f{\parallel }_{L^p(G)}+\parallel f{\parallel }_{L^q(G)}\parallel {\mu }_A{\parallel }_{L^1(G)}& \hfill & \\ \hfill & \le 2\parallel f{\parallel }_{L^p(G)}& \hfill & \end{array}$$

by Young / Hölder ($\parallel f\ast g{\parallel }_{L^r(G)}\le \parallel f{\parallel }_{L^p(G)}\parallel g{\parallel }_{L^q(G)}$ where $1+\frac{1}{r}=\frac{1}{p}+\frac{1}{q}$).

So we have

$${𝔼}_{(z_1,\dots ,z_m)\in A^m}{𝔼}_{y\in G}{\left|\sum _{i=1}^m{Z}_i(y)\right|}^p=O\left(p^{p∕2}{m}^{p∕2-1}\sum _{i=1}^m{(2\parallel f{\parallel }_{L^p(G)})}^p\right)=O({(4p)}^{p∕2}{m}^{p∕2}\parallel f{\parallel }_{L^p(G)}^p).$$

Choose $m=O({𝜀}^{-2}p)$ so that the RHS is at most ${(\frac{𝜀}{4}\parallel f{\parallel }_{L^p(G)})}^p$. whence

$${𝔼}_{(z_1,\dots ,z_m)\in A^m}\underset{=(\ast )}{\underbrace{{𝔼}_{y\in G}{\left|\frac{1}{m}\sum _{i=1}^m{\tau }_{-zi}f(y)-f\ast {\mu }_A(y)\right|}^p}}=O({(4p)}^{p∕2}{m}^{p∕2}\parallel f{\parallel }_{L^p(G)}^p)={\left(\frac{𝜀}{4}\parallel f{\parallel }_{L^p(G)}\right)}^p.$$

Write

$$L=\left\{z=(z_1,\dots ,z_m)\in A^m:(\ast )\le {\left(\frac{𝜀}{2}\parallel f{\parallel }_{L^p(G)}\right)}^p\right\}.$$

By Markov inequality, since

$$𝔼(\ast )\le {\left(\frac{𝜀}{4}\parallel f{\parallel }_{L^p(G)}\right)}^p=2^{-p}{\left(\frac{𝜀}{2}\parallel f{\parallel }_{L^p(G)}\right)}^p,$$

we have

$$\frac{|A^m\setminus L|}{|A^m|}=\mathbb{P}\left((\ast )\ge {\left(\frac{𝜀}{2}\parallel f{\parallel }_{L^p(G)}\right)}^p\right)\le \mathbb{P}((\ast )\ge 2^p𝔼(\ast ))\le 2^{-p}$$

so $|L|\ge \left(1-\frac{1}{2^p}\right)|A{|}^m\ge \frac{1}{2}|A{|}^m$. Let

$$D=\{\underset{m}{\underbrace{(b,b,\dots ,b)}}:b\in B\}.$$

Now $L+D\subseteq {(A+B)}^m$, whence

$$|L+D|\le |A+B{|}^m\le K^m|A{|}^m\le 2K^m|L|.$$

By Lemma 1.17,

$$E(L,D)\ge \frac{|L{|}^2|D{|}^2}{|L+D|}\ge \frac{1}{2}{K}^{-m}|D{|}^2|L|$$

so there are at least $\frac{|D{|}^2}{2K^m}$ pairs $(d_1,d_2)\in D\times D$ such that $r_{L-L}(d_2-d_1)>0$. In particular, there exists $b\in ub$ and $X\subseteq B-b$ of size $|X|\ge \frac{|D|}{2K^m}=\frac{|B|}{2K^m}$ such that for all $x\in X$, there exists $l_2(x)\in L$ such that for all $i\in [m]$, $l_1{(x)}_i-l_2{(x)}_i=x$. But then for each $x\in X$, by the triangle inequality,

$$\begin{array}{llll}\hfill \parallel {\tau }_{-x}f\ast {\mu }_A-f\ast {\mu }_A{\parallel }_{L^p(G)}& \le {\parallel {\tau }_{-x}f\ast {\mu }_A-{\tau }_{-x}\left(\frac{1}{m}\sum _{i=1}^m{\tau }_{-l_2{(x)}_i}f\right)\parallel }_{L^p(G)}& \hfill & \\ \hfill & +{\parallel {\tau }_{-x}\left(\frac{1}{m}\sum _{i=1}^m{\tau }_{-l_2(x_i)}f\right)-f\ast {\mu }_A\parallel }_{L^p(G)}& \hfill & \\ \hfill & ={\parallel f\ast {\mu }_A-\frac{1}{m}\sum _{i=1}^m{\tau }_{-l_2{(x)}_i}f\parallel }_{L^p(G)}& \hfill & \\ \hfill & +{\parallel \frac{1}{m}\sum _{i=1}^m{\tau }_{-x-l_2{(x)}_i}f-f\ast {\mu }_A\parallel }_{L^p(G)}& \hfill & \\ \hfill & \le 2\cdot \frac{𝜀}{2}\parallel f{\parallel }_{L^p(G)}& \hfill & \end{array}$$

by definion of $L$. □