Nice Exponent

computed in April 2013


Let K be a finite field.
Let s be positive integer.
For all y in K*, p(y) denotes the number of pre-images of y by
f : x -> x^s + ( 1 - x )^s.
that is
p(y) := # { x | x^s + ( 1 - x )^s = y }
An exponent s is said to be nice when y->p(y) takes at most three values.


Using the notion of Zech logarithm it is very easy to determine the number of nice exponents over small fields. Let n the order of K*. Let t be a primitive root of K. Any non zero element x of K is a power of t. There exists a uniq residue j modulo n such that

x = t^j
It is the logarithm of x. By definition the logarithm of 1+x is called the Zech logarithm of x. Assuming p is odd, the logarithm of the image of x by the map f
j * s + zech[ s * ( zech[ x + n / 2 ] - j )
just because
f(x) = x^s ( 1 + ( ( 1 - x ) / x )^s )
For our numerical experiment, given a finite field K:=GF(p,m) of order q, we proceed in two steps. First, we compute the table of zech logarithm it is about O( qm). Using this table, the distribution of the images by f are easy to compute and the total runtime is about O(q^2).

Numerical data

We compute the distribution for all the finite fields (not prime ) of characteristic less or equal to 31, having an order less than 2^20.
In the files below, lines like
#field is GF(3,9)
 13121  : 1 : 3 : 9841 [ 0] 9840 [ 2]   1 [ 3]
means that the exponent 13121 is nice for the field GF(3,9) : 9841 elements have no preimage, 9840 have two antecedants. Note that N(1,0) = 0 is not reported in the files.


On the basis of that numerical experiment, for a field of odd characteristic p, one may conjecture :

if s is a nice exponent 0 and 2 are multiplicities of pre-image size. In particular, this claim implies Hellesth's conjecture concerning Fourier spectra of power permutations in an hyper-quadratic extension of GF(p).

Up to equivalence, on a prime field p such that gcd(p-1,3)=1 the nice exponents are 3 and p-2. For the other p, nice exponents do not exist.

Philippe Langevin Last modifications March 23th 2013, March 31th 2015.