Sur la non-linéarité des fonctions booléennes (Q4829485)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2120185
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Sur la non-linéarité des fonctions booléennes |
scientific article; zbMATH DE number 2120185 |
Statements
Sur la non-linéarité des fonctions booléennes (English)
0 references
29 November 2004
0 references
covering radius
0 references
error-correcting code
0 references
cryptography
0 references
nonlinearity
0 references
Boolean function
0 references
random polynomial
0 references
Fourier transform
0 references
0.8611822724342346
0 references
0.8361250162124634
0 references
0.8312572836875916
0 references
0.8257896900177002
0 references
Boolean functions on the space \(F_2^m\) have important applications in the theory of error correcting codes, specifically the Reed-Muller codes, and in cryptography, specifically in private key systems. The nonlinearity of the functions plays an important role in both applications. Inspired by the results from Salem, Zygmund and Kahane on real polynomials with random coefficients the author investigates the degree of nonlinearity of these functions. Defining the spectral amplitude of a function \(g\) by \[ S(g) = \sup_{v \in F_2^m} | \sum_{x \in F_2^m} (-1)^{g(x) + v \cdot x}| \] he shows that the degree of nonlinearity, defined by the minimum over affine functions \(h\) of \(d(g,h)\) where \(d\) is the Hamming distance, is \(2^{m-1} - \tfrac12 S(g).\) Using the spectral amplitude he is able to show that nearly all Boolean functions in \(m\) variables have nonlinearity between \(2^{m-1} - 2^{\frac{m}{2}-1} \sqrt{2m\log (2) }\) and \(2^{m-1} - 2^{\frac{m}{2} - 2}\sqrt{m \log(2)}.\) Moreover he shows that the nonlinearity is of the order of \(2^{\frac{m}{2}} \sqrt{m}.\) Two conjectures are studied. The first by Patterson and Wiedemann conjectures that the minimum of the spectral amplitude approaches \(2^{\frac{m}{2}}\) and the second concerns the moments of order 4 of their Fourier transform.
0 references