9
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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...) $\endgroup$ Nov 10, 2009 at 21:02

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I think some of your LaTex needs fixing... $\endgroup$
    – Yemon Choi
    Feb 1, 2010 at 6:28
  • $\begingroup$ 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. $\endgroup$
    – user2734
    Feb 1, 2010 at 6:41
  • $\begingroup$ 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? $\endgroup$
    – Yemon Choi
    Feb 1, 2010 at 6:43
  • $\begingroup$ It will really really help if you agree to try. Thank you very much for offering this! $\endgroup$
    – user2734
    Feb 1, 2010 at 7:05
  • $\begingroup$ @YC: I've just seen that you have edited this. Thanks a lot for your help! $\endgroup$
    – user2734
    Feb 1, 2010 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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