Kernels and Defaults

Philippe Langevin and Patrick Solé

I3S, 250 Av. A. Einstein, 06560 Valbonne, France.

The set of boolean function from the space ${\mathbb{F} _2}^m$ into the field ${\mathbb{F} _2}$ is a metric space. The hamming distance between the boolean functions f and g is equal to wt(f+g) where wt(h) is the weight of the function h, i.e. the number of solutions of the equation f(x)+1=0. The distance between the boolean function f and the space of all the affine functions, say $\delta(f)$, measures the non-linearity of f, the function of maximal non-linearity are called bent functions, they are of a great interest for cryptographic applications.

In this context, the Fourier transform is one of the basic tools. The Fourier transform of f at the point ais $\hat f(a)=\sum_{x in F2^m} (-1)^{a.x+f(x)}$.The importance of the Fourier transform lies in the simple formula :

$$\delta(f)=2^{m-1}-{1/2} \sup_{a} \vert \hat f(a) \vert$$

which motivates the definition of spectral radius $R(m)=\inf_{f} \sup_{a} \hat f(a)$. One of the most exciting conjectures about Reed-Muller codes states that R(m) is equivalent to 2^m/2; If we denote $R_k(m)=\inf_{\deg(f)=k} \sup_{a} \vert \hat f(a) \vert$ then it is well know that R₂(m) is not equivalent to 2^m/2, the value of R₃(m) are known for even m, and when m=3,5,7,9,11,13. In that paper, I present a new way to study R₃(m). I generalize the classical notions of kernels and defaults that we meet in the theory of a quadratic forms. I apply these notions in the case of cubics to obtain the nice formula :

$$\sum_{a} (\hat f(a))^4 = 2^{2m} [k(f)-2d(f)]$$

where k(f) is the cardinality of the kernel of f and d(f) is the number of default of f, this formula can be used to estimate $\delta(f)$. We give numerical results for small values of m and we study the non defective case.