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.