# 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.)