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
Objectives
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 * :
- S(x^d, 1 ) = 0
- A > sqrt(q) or B > sqrt(q)
- AB < 0
- a > m/4
- b >= m/2
Methodology
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 !