# Existence of hyperelliptic curve with specific number of points in a family

Hi,

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.)

-
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

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.

-
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