Helleseth's conjecture in dimension 32

This page reports a verification of Helleseth's conjecture in dimension 32.
Philippe Langevin, Last modification September 21th 2010.

Fourier coefficient

Let m be a positive integer, L the field GF(2,m), q the order of L. For a mapping from L into itself, the Fourier coefficient of f at a is defined by

S(f, a) = sum_{x in L} X( f(x) + ax )
where X is the canonical additive character of L. The set of values S(f, a) when a ranges L is called the spectrum of f.
spec* (f) = { S(f, a ) | a in L*}
In the seventies, two conjectures where proposed by Helleseth concerning the spectra of power permutations f(x) = x^d. They are still open !

Helleseth's conjecture

If d is coprime to q-1 then there exists a non zero element a in L such that

S(x^d, a ) = 0, equivalently 0 lies in spec*(x^d)
note that I checked this claim for m < 26, see this page.

Four values Helleseth's conjecture

Assuming that m is a power of two. If d is coprime to q-1 then

# spec*(x^d) > 3


The goal of this numerical experiment is to check the secondary conjecture in dimension 32, assumming the main conjecture. In other words, we have to check the non existence of a power permutation f with

spec*( f ) = { 0, A, B}
One will find details on these slides, but, denoting by a the minimal dyadic valuation of A and B, and by b the greater one. The candidates to contradict the conjecture must satisfy several conditions * :


We use the fact that the dimension is even to compute efficientely the Fourier coefficient at one of all the power permutations keeping in memory the exponents satisfying S(x^d, 1 ) = 0. The cost of this task is O( q sqrt(q) ). After this, we simply test the list of candidates according to the conditions (*). The total running time was abouth 1 day, no counter example !