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 (Université de Renyi)

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:ZC, we write it as f=fs+fr+fe where: fs is the sum of « a few » Fourier characters with large amplitudes, fr is a function whose largest Fourier amplitude is « small » (which is the same as having a small Gowers U2 norm), and fe is small in L2. Higher-order analogues where we ask fr to be small in the Gowers Ud norm for d3 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 U3 case and demonstrate its performance on synthetic data.