Patterson–Wiedemann conjecture on the minimum Fourier amplitude of Boolean functions

From papers

Let VmV_m be the mm-dimensional vector space over 22, and let ff range over all functions from VmV_m to {±1}\{\pm1\}. Write f^\widehat f for the Fourier transform of ff and f^\|\widehat f\|_\infty for its supremum norm.

Patterson–Wiedemann conjecture.

limminfff^2m/2=1.\lim_{m\to\infty}\inf_f\frac{\|\widehat f\|_\infty}{2^{m/2}}=1.

This is the reformulation of the conjecture of Patterson and Wiedemann concerning the covering radius of the first-order Reed–Muller code, or equivalently the non-linearity of Boolean functions. The supplied text gives no resolution status.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Francois Rodier, “Sur la non-linearite des fonctions booleennes”, arXiv:math/0306395 (2003).

Solutions 0

No solutions have been posted yet.