A zero in the nontrivial spectrum of a power permutation
Let $p$ be a prime, $q = p^n > 2$, $F = \mathbb{F}_q$ and $\operatorname{Tr} \colon F \to \mathbb{F}_p$ the absolute trace. For a positive integer $d$ and $a \in F$ let $$W_{F,d}(a) = \sum_{x \in F} \exp\!\left(\frac{2\pi i}{p} \operatorname{Tr}(x^d - a x)\right).$$ If $\gcd(d, q-1) = 1$, then $x \mapsto x^d$ permutes $F$, so $W_{F,d}(0) = 0$, and the numbers $W_{F,d}(a) - 1$ with $a \ne 0$ are the periodic cross-correlation values of a $p$-ary m-sequence of period $q - 1$ with its decimation by $d$. Helleseth showed that these values are all rational integers exactly when $d \equiv 1 \pmod{p-1}$. Katz proved that $W_{F,d}(a) = 0$ for some $a \ne 0$ whenever $W_{F,d}$ takes exactly three values on $F \setminus \{0\}$. The same conclusion holds for Niho exponents (Charpin for $p = 2$; Helleseth, Lahtonen and Rosendahl in general; another proof by Nguyen for odd $p$) and for further families of exponents, among them one found by Wu, Feng, Li and Helleseth through complete permutation polynomials. Aubry and Langevin proved that $\prod_{a \ne 0} W_{F,d}(a) \equiv 0 \pmod 3$ whenever $\gcd(d, q-1) = 1$ and $d \equiv 1 \pmod{p-1}$.
Problem. Let $d$ be a positive integer with $\gcd(d, q-1) = 1$ and $d \equiv 1 \pmod{p-1}$. Is there always an $a \in F \setminus \{0\}$ with $W_{F,d}(a) = 0$?
Source: Helleseth (1971, master's thesis; 1976, Conjecture 5.1), as a cross-correlation value −1 of m-sequences; with the proviso q > 2 as in Katz (2019), Conjecture 11.1.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- NT — Number Theory
- Secondary
- IT
- Keywords
- AIM Open Applied Problems, m-sequences, power permutations, Weil sums
References
@mastersthesis{helleseth1971,
author = {Helleseth, Tor},
title = {Krysskorrelasjonsfunksjonen mellom maksimale sekvenser over {GF}(q)},
school = {Universitetet i Bergen},
year = {1971},
}
@article{helleseth1976,
author = {Helleseth, Tor},
title = {Some results about the cross-correlation function between two maximal linear sequences},
journal = {Discrete Math.},
volume = {16},
number = {3},
year = {1976},
pages = {209--232},
doi = {10.1016/0012-365X(76)90100-X},
}
@incollection{katz2019,
author = {Katz, Daniel J.},
title = {Weil sums of binomials: properties, applications and open problems},
booktitle = {Combinatorics and Finite Fields: Difference Sets, Polynomials, Pseudorandomness and Applications},
editor = {Schmidt, Kai-Uwe and Winterhof, Arne},
series = {Radon Series on Computational and Applied Mathematics},
volume = {23},
publisher = {De Gruyter},
address = {Berlin},
year = {2019},
pages = {109--134},
doi = {10.1515/9783110642094-007},
eprint = {1805.10452},
archivePrefix = {arXiv},
}
@article{katz2012,
author = {Katz, Daniel J.},
title = {Weil sums of binomials, three-level cross-correlation, and a conjecture of {H}elleseth},
journal = {J. Combin. Theory Ser. A},
volume = {119},
number = {8},
year = {2012},
pages = {1644--1659},
doi = {10.1016/j.jcta.2012.05.003},
}
@article{charpin2004,
author = {Charpin, Pascale},
title = {Cyclic codes with few weights and {N}iho exponents},
journal = {J. Combin. Theory Ser. A},
volume = {108},
number = {2},
year = {2004},
pages = {247--259},
doi = {10.1016/j.jcta.2004.07.001},
}
@article{helleseth2007,
author = {Helleseth, Tor and Lahtonen, Jyrki and Rosendahl, Petri},
title = {On {N}iho type cross-correlation functions of $m$-sequences},
journal = {Finite Fields Appl.},
volume = {13},
number = {2},
year = {2007},
pages = {305--317},
doi = {10.1016/j.ffa.2005.09.004},
}
@article{nguyen2022,
author = {Nguyen, Liem},
title = {On {W}eil sums, conjectures of {H}elleseth, and {N}iho exponents},
journal = {J. Number Theory},
volume = {234},
year = {2022},
pages = {240--258},
doi = {10.1016/j.jnt.2021.06.022},
eprint = {2006.15726},
archivePrefix = {arXiv},
}
@article{wu2023,
author = {Wu, Gaofei and Feng, Keqin and Li, Nian and Helleseth, Tor},
title = {New results on the $-1$ conjecture on cross-correlation of $m$-sequences based on complete permutation polynomials},
journal = {IEEE Trans. Inform. Theory},
volume = {69},
number = {6},
year = {2023},
pages = {4035--4044},
doi = {10.1109/TIT.2023.3238994},
}
@incollection{aubry2013,
author = {Aubry, Yves and Langevin, Philippe},
title = {On a conjecture of {H}elleseth},
booktitle = {Algebraic Informatics (CAI 2013)},
editor = {Muntean, Traian and Poulakis, Dimitrios and Rolland, Robert},
series = {Lecture Notes in Comput. Sci.},
volume = {8080},
publisher = {Springer},
address = {Heidelberg},
year = {2013},
pages = {113--118},
doi = {10.1007/978-3-642-40663-8_12},
}
@misc{aim-helleseth-vanishing,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{A zero in the nontrivial spectrum of a power permutation}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/606-helleseth-vanishing.md},
note = {Entry 606 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00353, "A zero in the nontrivial spectrum of a power permutation", clopen.solutions.