La distance d'une fonction booléenne f de m variables au code de Reed-Muller  est une mesure la non-linearité de f. Il s'agit d'une notion  importante en cryptographie. L'analyse de Fourier est une méthode d'approche normale de  cette question. En particulier, la non-linéarité de f  est égale à

où R(f) est l'amplitude spectrale de f  i.e. le module maximal  de ses coefficients de Fourier.

Un des problèmes majeurs consiste à déterminer la valeur minimale  (rayon spectral) de R(f) lorsque f décrit l'ensemble de toutes les  fonctions booléennes, équivalent à déterminer le rayon de recouvrement du code de Reed-Muller du premier ordre.

Le rayon spectral est facile à calculer lorsque m est pair,  il est réalisé par les fonctions quadratiques non-dégénérée. Le cas impair est encore ouvert, sauf pour  les petites valeurs de m : 3, 5 et 7.

Dans les années 80, Paterson-Wiedemann ont découvert une fonction  booléenne de 15 variables moins linéaire que les fonctions quadratiques : contre-exemple à une conjecture formulée dans les années 70 par Mykkelveit.

Au cours de mon exposé, je  montrerai d'autres contre-exemples  plus linéaire mais mieux structurés construits à partir des sommes de Gauss. Enfin, je discuterai de la conjecture de Patterson et Wiedemann qui affirme l'équivalence asympototique entre le  rayon spectral R(m)   et    2^{m/2}.