MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


the following question was posed to me, it apparently has applications for linear codes. Let n>1, and $K = \rm{GF}(2^n)$. Let $k$ be coprime to $2^n-1$. Does there always exist $a \neq 0$ in $K$ such that the curve

$y^2+y = x^k+ax$

has exactly $2^n$ affine solutions? (I ran some computer checks [although only for quite small n and k] without finding a counterexample.)

share|cite|improve this question
FWIW: WLOG k<=2^n-1 (because x^{2^n}=x for all x in K) so for any n the problem is a finite one. I wrote a computer program which now says it has checked your claim for n<=12 (but I'm no programmer...) – Kevin Buzzard Nov 10 '09 at 21:02
up vote 2 down vote accepted

I think that this is equivalent to a known open question. Here are the details. For $K:=\mathbb{F}\_{2^n}$, the function $f:y\mapsto y+y^2:K\to K$ is $\mathbb{F}_2$-linear, and its kernel $\{0,1\}$ has dimension 1. The image is therefore of dimension $n-1$, and for $z$ in the image, the fiber $f^{-1}(z)$ has exactly 2 elements.

Hence, to prove that $y^2+y=x^k+ax$ has exactly $2^n$ solutions for some fixed $a\in K$, we have to show that $|\{x\in K|x^k+ax\in \mathrm{Im}(f)\}|=2^{n-1}$.

Since $\sigma:y\mapsto y^2$ is a generator of the Galois group of $K/\mathbb{F}\_2$, Hilbert's Theorem 90 (in additive form) says that $z\in \mathrm{Im}(f)$ if and only if $\mathrm{Tr}(z)=0$, where $\mathrm{Tr}$ stands for the trace map from $K$ to $\mathbb{F}_2$.

So the problem is equivalent to showing that there exists an $a\neq 0$ in $K$ such that $|\{x\in K|\mathrm{Tr}(x^k+ax)=0\}|=2^{n-1}$. In other words, we would like to show that there exists a nonzero $a\in K$ such that $$ S_k(a):=\sum_{x\in K}(-1)^{\mathrm{Tr}(x^k+ax)}=0. $$

Apparently, this question was addressed in the coding community. In detail, in [1, p. 258], the following conjecture (of Helleseth) is mentioned:

``Conjecture 3. For any $m$ and $k$ such that $\mathrm{gcd}(2^m-1,k)=1$, the sum $\sum_{x\in\mathbb{F}_{2^m}}(-1)^{\mathrm{Tr}(x^k+ax)}$ is null for at least one nonzero $a$.'' (Note that $n$ in the current question is $m$ in 1).

It seems that in [1, Corollary 1, p. 253], Conjecture 3 is proved for even $m$ and for certain values of $k$ (the ``Niho exponents,'' defined on p. 252 of 1).

Interestingly, at least at a first glance it seems that 1 has nothing to say on $k\in\{1,\ldots,2^{n-1}\}$, but to me it seems that this case is trivial (am I missing something?): Consider a normal basis for $K/\mathbb{F}\_2$, that is, a basis $B$ consisting of an orbit of an element $\gamma\in K$ under the Galois group of $K/\mathbb{F}_2$ (the $i$th element of $B$ is $b_i:=\gamma^{2^i}$ for $i\in\{0,\ldots,n-1\}$).

From the linearity of the trace and the fact that the trace is onto, we must have $\mathrm{Tr}(b)=1$ for at least one element $b\in B$, and from $\mathrm{Tr}(b^2)=\mathrm{Tr}(b)$ we then have $\mathrm{Tr}(b)=1$ for all $b\in B$. So the trace of an element in $K$ is just the modulo-2 sum of the coefficients in its decomposition according to the basis $B$.

Let $a$ be any element in the trace-dual basis of $B$, say $\mathrm{Tr}(ab_i)=\delta_{i,0}$. Then for $k=2^j$, if we write $x=\sum_i \alpha_i b_i$, we get: $\mathrm{Tr}(ax)=\alpha_0$, $\mathrm{Tr}(x^k)=\mathrm{Tr}(x)=\sum \alpha_i$ (sum in $\mathbb{F}_2$). These agree for half of the $x\in K$, as required.

That's about it. I hope at least some of this makes sense :) I also hope that the original person asking this question didn't actually want to solve the above open question by converting it to a question about curves, for then this answer is useless.

1 P. Charpin, ``Cyclic codes with few weights and Niho exponents,'' Journal of Combinatorial Theory, Series A 108 (2004) 247--259.

share|cite|improve this answer
I think some of your LaTex needs fixing... – Yemon Choi Feb 1 '10 at 6:28
Thank you. Unfortunately, I don't actually see the jsMath. Instead, I prepared a LaTeX file and compiled it, hoping that this will be enough. When I pasted the .tex source here, I saw some problems with "F underscore 2$ and the like (underscores were missing etc.). Because I am blind to the jsMath errors, could you please tell me what is the main error (hoping such exists)? Is it after things like "F underscore 2"? A hint on how to fix it will be greatly appreciated. – user2734 Feb 1 '10 at 6:41
Looking at your source, it seems that you have an unwanted double-dollar after several (all?) occurrences of {\mathbb F}, and this is unbalancing things. Do you want to have a go fixing this, or would you like me to have a try? – Yemon Choi Feb 1 '10 at 6:43
It will really really help if you agree to try. Thank you very much for offering this! – user2734 Feb 1 '10 at 7:05
@YC: I've just seen that you have edited this. Thanks a lot for your help! – user2734 Feb 1 '10 at 7:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.