An algorithm for higher-order Fourier analysis (joint work with P. Candela and B. Szegedy)

Date/heure
14 novembre 2024
14:30 - 15:30

Lieu
Salle Döblin

Oratrice ou orateur
Diego González Sánchez

Catégorie d'évènement
Séminaire de Théorie des Nombres de Nancy-Metz


Résumé

Decomposing functions in terms of higher-order harmonics is a central topic in higher-order Fourier analysis. In its simplest form, such a decomposition is as follows. For a bounded function defined on a finite abelian group $f: Z\to \mathbb{C}$, we write it as $f=f_s+f_r+f_e$ where: $f_s$ is the sum of « a few » Fourier characters with large amplitudes, $f_r$ is a function whose largest Fourier amplitude is « small » (which is the same as having a small Gowers $U^2$ norm), and $f_e$ is small in $L^2$. Higher-order analogues where we ask $f_r$ to be small in the Gowers $U^d$ norm for $d\ge 3$ are interesting as we may use them to, e.g., prove Szemerédi’s theorem with good quantitative bounds. Many results guarantee that such a decomposition exists, but few are implementable in applied scenarios. In this talk, we will present a practical approach to finding such a decomposition in the $U^3$ case and demonstrate its performance on synthetic data.