Sur la non-linearite des fonctions booleennes
<|reference_start|>Sur la non-linearite des fonctions booleennes: Boolean functions on the space $F_{2}^m$ are not only important in the theory of error-correcting codes, but also in cryptography, where they occur in private key systems. In these two cases, the nonlinearity of these function is a main concept. In this article, I show that the spectral amplitude of boolean functions, which is linked to their nonlinearity, is of the order of $2^{m/2}\sqrt{m}$ in mean, whereas its range is bounded by $2^{m/2}$ and $2^m$. Moreover I examine a conjecture of Patterson and Wiedemann saying that the minimum of this spectral amplitude is as close as desired to $2^{m/2}$. I also study a weaker conjecture about the moments of order 4 of their Fourier transform. This article is inspired by works of Salem, Zygmund, Kahane and others about the related problem of real polynomials with random coefficients.<|reference_end|>
@article{rodier2003sur,
    title={Sur la non-linearite des fonctions booleennes},
    author={Francois Rodier},
    journal={arXiv preprint arXiv:math/0306395},
    year={2003},
    doi={10.4064/aa115-1-1},
    archivePrefix={arXiv},
    eprint={math/0306395},
    primaryClass={math.NT cs.IT math.IT}
}