MathDB

A lower-bound conjecture for the 2-adic complexity of LSB sequences of p-ary m-sequences

From papers

Let pp be any odd prime, let nn be a positive integer, and set N=pn−1N=p^n-1. Let {st}t=0N−1\{s_t\}_{t=0}^{N-1} be the LSB sequence of a pp-ary mm-sequence of order nn, and let CpC_p denote a constant depending only on pp and not on nn. The 2-adic complexity conjecture. The 2-adic complexity Φ2(s)\Phi_{2}(s) of {st}t=0N−1\{s_t\}_{t=0}^{N-1} is bounded below by

Φ2(s)≥p+12(p−1)N−Cp,\Phi_{2}(s)\geq \frac{p+1}{2(p-1)}N-C_p,

and this lower bound is larger than N/2N/2 when n≥2n\geq 2. The result would show that these LSB sequences have 2-adic complexity exceeding half their period, supporting their resistance to rational approximation attacks; the stated bound is established in the paper for several specific primes, while the general assertion for every odd prime remains open.

Progress summary

Open

Partial calculations support the conjecture, but no general proof or counterexample has appeared, so the question remains open for arbitrary odd primes.

Sun, Wang, Yan, and Zhao proposed the conjecture in 2017: the LSB sequences of odd-prime pp-ary mm-sequences should have 22-adic complexity exceeding half their period by a prime-dependent linear margin. The paper explicitly says that a complete proof for every odd prime was not obtained.

Known results

  • Explicit lower bounds were proved for several primes, including p=3,5,7,11,17p=3,5,7,11,17, and 3131.
  • For p<20p<20, the bounds have main term N/2+N/(p−1)−CpN/2+N/(p-1)-C_p, hence exceed N/2N/2 for n≥2n\geq 2.
  • Similar methods and calculations were reported for p=23,29p=23,29, and 3131, but not extended to all odd primes.
  • The corresponding 2020 publication continues to label the all-prime assertion a conjecture rather than a theorem.

Current status (as of August 2026): The conjecture is established only for selected primes, while the asserted lower bound for every odd prime remains open; no public proof, counterexample, or claimed AI solution was found.

Sources
Sources & referencesView supporting material

Primary source

Yuhua Sun, Qiuyan Wang, Tongjiang Yan and Chun'e Zhao, “Autocorrelation and Lower Bound on the 2-Adic Complexity of LSB Sequence of p-ary m-Sequence”, arXiv:1702.00822 (2020).

finite-fieldsm-sequencessequence-complexity

Solutions 0

No solutions have been posted yet.