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

Question

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.

Answer 1

(I agree with the comment that there isn't exactly a question here, but I'll try to make some useful comments.)

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.

(Note the connection to your other question---a characteristic factor is a notion of structure, and generally the two are exactly equivalent.)

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

The randomness Tao is talking about in the structure/randomness dichotomy is what's left over after you've approximated a function as well as possible using some family of functions (the most common example being functions given by nilsystems with certain parameters).