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

About 23 years old · traced to

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.

lim⁡m→∞inf⁡f∥f^∥∞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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.