1 Almost-Periodicity

Lemma 1.1 Marcinkiewicz-Zygmund inequality

✓

Let \(m\geq 1\). If \(f:G\to \mathbb {R}\) is such that \(\mathbb {E}_x f(x)=0\) and \(\left\lvert f(x)\right\rvert \leq 2\) for all \(x\) then

\[ \mathbb {E}_{x_1,\ldots ,x_n} \left\lvert \sum _{i=1}^n f(x_i)\right\rvert ^{2m} \leq (4mn)^{m}. \]

Proof ▶

Let \(S\) be the left-hand side. Since \(0=\mathbb {E}_y f(y)\) we have, by the triangle inequality, and Hölder’s inequality,

\begin{align} S & = \mathbb {E}_{x_1, \dots , x_n}\left\lvert \sum _i f(x_i) - \mathbb {E}_{y_i} f(y_i)\right\rvert ^{2m} \\ & = \mathbb {E}_{x_1, \dots , x_n} \left\lvert \mathbb {E}_{y_i}\left( \sum _i f(x_i) - f(y_i)\right)\right\rvert ^{2m} \\ & \le \mathbb {E}_{x_1,\dots ,y_n} \left\lvert \sum _i f(x_i) - f(y_i)\right\rvert ^{2m} \end{align}

Changing the role of \(x_i\) and \(y_i\) makes no difference here, but multiplies the \(i\) summand by \(\{ -1,+1\} \), and therefore for any \(\epsilon _i\in \{ -1,+1\} \),

\[ S \leq \mathbb {E}_{x_1,\ldots ,y_n}\left\lvert \sum _i \epsilon _i(f(x_i)-f(y_i))\right\rvert ^{2m}. \]

In particular, if we sample \(\epsilon _i\in \{ -1,+1\} \) uniformly at random, then

\[ S \leq \mathbb {E}_{\epsilon _i} \mathbb {E}_{x_1,\ldots ,y_n}\left\lvert \sum _i \epsilon _i(f(x_i)-f(y_i))\right\rvert ^{2m}. \]

We now change the order of expectation and consider the expectation over just \(\epsilon _i\), viewing the \(f(x_i)-f(y_i)=z_i\), say, as fixed quantities. For any \(z_i\) we can expand \(\mathbb {E}_{\epsilon _i} \lvert \sum _i \epsilon _iz_i\rvert ^{2m}\) and then bound it from above, using the triangle inequality and \(\left\lvert z_i\right\rvert \leq 4\), by

\[ 4^{2m}\sum _{k_1+\cdots +k_n=2m}\binom {2m}{k_1,\ldots ,k_n}\left\lvert \mathbb {E}\epsilon _1^{k_1}\cdots \epsilon _n^{k_n}\right\rvert . \]

The inner expectation vanishes unless each \(k_i\) is even, when it is trivially one. Therefore the above quantity is exactly

\[ \sum _{l_1+\cdots +l_n=m}\binom {2m}{2l_1,\ldots ,2l_n}\leq m^mn^m, \]

since for any \(l_1+\cdots +l_n=m\),

\[ \binom {2m}{2l_1,\ldots ,2l_n}\leq m^m\binom {m}{l_1,\ldots ,l_n}. \]

This can be seen, for example, by writing both sides out using factorials, yielding

\[ \frac{(2m)!}{(2l_1)!\cdots (2l_n)!}\leq \frac{(2m)!}{2^mm!}\frac{m!}{l_1!\cdots l_n!}\leq m^m\frac{m!}{l_1!\cdots l_n!}. \]

Lemma 1.2 Complex-valued Marcinkiewicz-Zygmund inequality

✓

Let \(m\geq 1\). If \(f:G\to \mathbb {C}\) is such that \(\mathbb {E}_x f(x)=0\) and \(\left\lvert f(x)\right\rvert \leq 2\) for all \(x\) then

\[ \mathbb {E}_{x_1,\ldots ,x_n} \left\lvert \sum _{i=1}^n f(x_i)\right\rvert ^{2m} \leq (8mn)^{m}. \]

Proof ▶

Test.

Lemma 1.3

✓

Let \(\epsilon {\gt}0\) and \(m\geq 1\). Let \(A\subseteq G\) and \(f:G\to \mathbb {C}\). If \(k\geq 64m\epsilon ^{-2}\) then the set

\[ L=\{ {\vec{a}}\in A^k : \| \tfrac {1}{k}\sum _{i=1}^kf(x-a_i)-\mu _A\ast f\| _{2m}\leq \epsilon \| f\| _{2m}\} . \]

has size at least \(\lvert A \rvert ^k/2\).

Proof ▶

Note that if \(a\in A\) is chosen uniformly at random then, for any fixed \(x\in G\),

\[ \mathbb {E}f(x-a_i)= \frac{1}{\left\lvert A\right\rvert }\sum _{a\in A}f(x-a)=\frac{1}{\left\lvert A\right\rvert }1_{A}\ast f(x)=\mu _A\ast f(x). \]

Therefore, if we choose \(a_1,\ldots ,a_k\in A\) independently uniformly at random, for any fixed \(x\in G\) and \(1\leq i\leq k\), the random variable \(f(x-a_i)-f\ast \mu _A(x)\) has mean zero. By the Marcinkiewicz-Zygmund inequality Lemma 1.1, therefore,

\begin{multline*} \mathbb {E}\left\lvert \frac{1}{k}\sum _i f(x-a_i)-f\ast \mu _A(x)\right\rvert ^{2m} \leq \\ (16m/k)^mk^{-1} \mathbb {E}\sum _i \left\lvert f(x-a_i)-f\ast \mu _A(x)\right\rvert ^{2m}. \end{multline*}

We now sum both sides over all \(x\in G\). By the triangle inequality, for any fixed \(1\leq i\leq k\) and \(a_i\in A\),

\begin{align*} \sum _{x\in G} \left\lvert f(x-a_i)-f\ast \mu _A(x)\right\rvert ^{2m} & \leq 2^{2m-1}\sum _{x\in G}\left\lvert f(x-a_i)\right\rvert ^{2m}+\sum _{x\in G}\left\lvert f\ast \mu _A(x)\right\rvert ^{2m}\\ & \leq 2^{2m-1}\left( \lVert f\rVert _{2m}^{2m}+\lVert f\ast \mu _A\rVert _{2m}^{2m}\right). \end{align*}

We note that \(\lVert \mu _A\rVert _1=\frac{1}{\left\lvert A\right\rvert }\sum _{x\in A}1_{A}(x)=\left\lvert A\right\rvert /\left\lvert A\right\rvert =1\), and hence by Young’s inequality, \(\lVert f\ast \mu _A\rVert _{2m}\leq \lVert f\rVert _{2m}\), and so

\[ \sum _{x\in G} \left\lvert f(x-a_i)-f\ast \mu _A(x)\right\rvert ^{2m}\leq 2^{2m}\lVert f\rVert _{2m}^{2m}. \]

It follows that

\[ \mathbb {E}_{a_1,\ldots ,a_k\in A}\lVert \frac{1}{k}\sum _i\tau _{a_i}f-f\ast \mu _A\rVert _{2m}^{2m}\leq (64m/k)^m\lVert f\rVert _{2m}^{2m}. \]

In particular, if \(k\geq 64\epsilon ^{-2}m\) then the right-hand side is at most \((\frac{\epsilon }{2}\lVert f\rVert _{2m})^{2m}\) as required.

Lemma 1.4

✓

Let \(A\subseteq G\) and \(f:G\to \mathbb {C}\). Let \(\epsilon {\gt}0\) and \(m\geq 1\) and \(k\geq 1\). Let

\[ L=\{ {\vec{a}}\in A^k : \| \tfrac {1}{k}\sum _{i=1}^kf(x-a_i)-\mu _A\ast f\| _{2m}\leq \epsilon \| f\| _{2m}\} . \]

If \(t\in G\) is such that \({\vec{a}}\in L\) and \({\vec{a}}+(t,\ldots ,t)\in L\) then

\[ \| \tau _t(\mu _A\ast f)-\mu _A\ast f\| _{2m}\leq 2\epsilon \| f\| _{2m}. \]

Proof ▶

Test.

Lemma 1.5

✓

Let \(A\subseteq G\) and \(k\geq 1\) and \(L\subseteq A^k\). Then there exists some \({\vec{a}}\in L\) such that

\[ \# \{ t\in G : {\vec{a}}+(t,\ldots ,t)\in L\} \geq \frac{\lvert L\rvert }{\lvert A+S\rvert ^k}\lvert S\rvert . \]

Proof ▶

Test.

Theorem 1.6 \(L_p\) almost periodicity

✓

Let \(\epsilon \in (0,1]\) and \(m\geq 1\). Let \(K\geq 2\) and \(A,S\subseteq G\) with \(\lvert A+S\rvert \leq K\lvert A\rvert \). Let \(f:G\to \mathbb {C}\). There exists \(T\subseteq G\) such that

\[ \lvert T\rvert \geq K^{-512m\epsilon ^{-2}}\lvert S\rvert \]

such that for any \(t\in T\) we have

\[ \| \tau _t(\mu _A\ast f)-\mu _A\ast f\| _{2m}\leq \epsilon \| f\| _{2m}. \]

Proof ▶

Test.

Theorem 1.7 \(L_\infty \) almost periodicity

✓

Let \(\epsilon \in (0,1]\). Let \(K\geq 2\) and \(A,S\subseteq G\) with \(\lvert A+S\rvert \leq K\lvert A\rvert \). Let \(B,C\subseteq G\). Let \(\eta =\min (1,\lvert C\rvert /\lvert B\rvert )\). There exists \(T\subseteq G\) such that

\[ \lvert T\rvert \geq K^{-4096\lceil \mathcal{L}{\eta }\rceil \epsilon ^{-2}}\lvert S\rvert \]

such that for any \(t\in T\) we have

\[ \| \tau _t(\mu _A\ast 1_B\ast \mu _C)-\mu _A\ast 1_B\ast \mu _C\| _{\infty }\leq \epsilon . \]

Proof ▶

Let \(T\) be as given in 1.6 with \(f=1_B\) and \(m=\lceil \mathcal{L}{\eta }\rceil \) and \(\epsilon =\epsilon /e\). (The size bound on \(T\) follows since \(e^2\leq 8\).) Fix \(t\in T\) and let \(F=\tau _t(\mu _A\ast 1_B)-\mu _A\ast 1_B\). We have, for any \(x\in G\),

\[ (\tau _t(\mu _A\ast 1_B\ast \mu _C)-\mu _A\ast 1_B\ast \mu _C)(x)=F\ast \mu _C(x)=\sum _y F(y)\mu _{C}(x-y)=\sum _yF(y)\mu _{x-C}(y). \]

By Hölder’s inequality, this is (in absolute value), for any \(m\geq 1\),

\[ \lVert F\rVert _{2m}\lVert \mu _{x-C}\rVert _{1+\frac{1}{2m-1}}. \]

By the construction of \(T\) the first factor is at most \(\frac{\epsilon }{e}\| 1_B\| _{2m}=\frac{\epsilon }{e}\lvert B\rvert ^{1/2m}\). We have by calculation

\[ \lVert \mu _{x-C}\rVert _{1+\frac{1}{2m-1}}=\lvert x-C\rvert ^{-1/2m}=\lvert C\rvert ^{-1/2m}. \]

Therefore we have shown that

\[ \| \tau _t(\mu _A\ast 1_B\ast \mu _C)-\mu _A\ast 1_B\ast \mu _C\| _{\infty }\leq \frac{\epsilon }{e}(\lvert C\rvert /\lvert B\rvert )^{-1/2m}. \]

The claim now follows since, by choice of \(m\),

\[ (\lvert C\rvert /\lvert B\rvert )^{-1/2m}\leq e \]

(dividing into cases as to whether \(\eta =1\) or not).

Theorem 1.8

✓

Let \(\epsilon \in (0,1]\) and \(k\geq 1\). Let \(K\geq 2\) and \(A,S\subseteq G\) with \(\lvert A+S\rvert \leq K\lvert A\rvert \). Let \(B,C\subseteq G\). Let \(\eta =\min (1,\lvert C\rvert /\lvert B\rvert )\). There exists \(T\subseteq G\) such that

\[ \lvert T\rvert \geq K^{-4096\lceil \mathcal{L}{\eta }\rceil k^2\epsilon ^{-2}}\lvert S\rvert \]

such that

\[ \| \mu _T^{(k)}\ast \mu _A\ast 1_B\ast \mu _C-\mu _A\ast 1_B\ast \mu _C\| _{\infty }\leq \epsilon . \]

Proof ▶

Let \(T\) be as in Theorem 1.7 with \(\epsilon \) replaced by \(\epsilon /k\). Note that, for any \(x\in G\),

\[ \mu _T^{(k)}\ast \mu _A\ast 1_B\ast \mu _C(x)=\frac{1}{\lvert T\rvert ^k}\sum _{t_1,\ldots ,t_k\in T}\tau _{t_1+\cdots +t_k}\mu _A\ast 1_B\ast \mu _C(x). \]

It therefore suffices (by the triangle inequality) to show, for any fixed \(x\in G\) and \(t_1,\ldots ,t_k\in T\), that with \(F=\mu _A\ast 1_B\ast \mu _C\), we have

\[ \lvert \tau _{t_1+\cdots +t_k}F(x)-F(x)\rvert \leq \epsilon . \]

This follows by the triangle inequality applied \(k\) times if we knew that, for \(1\leq l\leq k\),

\[ \lvert \tau _{t_1+\cdots +t_l}F(x)-\tau _{t_1+\cdots +t_{l-1}}F(x)\rvert \leq \epsilon /k. \]

We can write the left-hand side as

\[ \lvert \tau _{t_1+\cdots +t_l}F(x)-\tau _{t_1+\cdots +t_{l-1}}F(x)\rvert =\lvert \tau _{t_l}F(x-t_1-\cdots -t-{l-1})-F(x-t_1-\cdots -t-{l-1})\rvert . \]

The right-hand side is at most

\[ \| \tau _{t_l}F-F\| _\infty \]

and we are done by choice of \(T\).