# higher fourier analysis: splitting periodic parts and 'nilsequence' noise?

In Fourier Analysis notes by Terence Tao (and "algebraic" version by Balasz Szegedy) there seem to be two versions of Fourier analysis floating around:

• To decompose periodic functions $$L^2(S^1)$$ into modes $$x \mapsto e^{2\pi i n x}$$
• To correlate functions $$f: \mathbb{Z} \to \mathbb{R}$$ with purely periodic sequences $$x \mapsto e^{2\pi i \xi n}$$.

While I am familiar with Fourier analysis on the circle $$L^2(S^1)$$ and Finite Fourier analysis, the starting point for Roth's theorem and this "higher order" discussion seems to be harmonic analysis on sequences indexed by the integers $$\ell^2(\mathbb{Z})$$.

One proof of Roth's theorem involves taking an arbitrary positive upper density set $$A \subset \mathbb{Z}$$ and examining it's Fourier decomposition i.e. correlation with periodic sequences $$\langle \mathbf{1}_A \big| e^{2\pi i n x}\rangle, x \in \mathbb{R}$$

They consider Fourier analysis on the circle as a limit of finite Fourier analysis $$\lim_{N \to \infty} L^2(\mathbb{Z}_N) = L^2(S^1) \text{ or maybe } L^2(\mathbb{Z})$$

When hunting for more sophisticated patterns (like 4-step arithmetic sequences) they use "higher" fourier analysis and correlations with quadratic phases. However, that doesn't seem to be enough: they also look for correlations with nilsequences.

$$e^{2\pi in^2}$$ is an example of elements of $$\ell^2(\mathbb{Z})$$ that are orthogonal to all linear phases. We can turn this into a subset of the integers by considering a Bohr-like set $$\big\{ n: \big|\big|n^2 \alpha - \theta \big|\big|_{\mathbb{R}/\mathbb{Z}} < \epsilon \big\}$$

I was wondering if there does there exists a Fourier decomposition which takes into account the quadratic and nilsequences phases?

E.g. spanned by $$n \mapsto e^{an^2 + b n}$$ with $$a,b \in \mathbb{R}$$.

### Experiments

I plotted $$\phi: n \mapsto (n\sqrt{3} \; \% \; 10) + 0.1(n^2 \sqrt{2} \; \% \; 10)$$ and it looks mildly periodic with some 'noise' as one might expect. However, this sequence is not totally random since $$\phi(n) - 3\phi(n+1) + 3\phi(n+2)- \phi(n+3) \approx 0$$.

EDIT I posted this a while ago and unsure of the language... REVISED. Not totally sure about my figures -- I seem to be turning on the quadratic term as you move from the left to right figure. The result looks Fourier-random.

• What is the question? It might be helpful to clarify. – Steven Gubkin May 18 '12 at 17:08

First, a key idea in this area is that there can be different notions of structure corresponding to different questions, and for each notion of structure, a corresponding notion of randomness. If one's notion of structure is given by Fourier analysis, periodic, or nearly periodic, functions are structured, and functions which are completely non-periodic, like $n\mapsto e(n^2)$, are random.
But for some purposes we want to consider other notions of structure. $n\mapsto e(n^2)$ is an example of a function which looks random relative to the periodic functions, but is actually quite structured. (That it looks random is really quite misleading, and I think somewhat sensitive to the way you plotted it, since I recall looking at plots of related functions which make clear that they have a structure, just not a periodic one.)