Conjectured linear complexity of generalized cyclotomic binary sequences

About 9 years old · traced to

Let pp be an odd prime, let n≥1n\geq 1, and let s∞s^\infty be the generalized cyclotomic binary sequence of period pnp^n defined by the characteristic set C1(pn)\mathcal{C}_1^{(p^n)} in the source. Let D0(p)D^{(p)}_0 be the corresponding generalized cyclotomic class, and define

δ(t)={1,if t is even,0,if t is odd.\delta(t)=\begin{cases}1,&\text{if }t\text{ is even},\\0,&\text{if }t\text{ is odd}. \end{cases}

Linear-complexity conjecture. If 2p−1≢1(modp2)2^{p-1}\not\equiv 1\pmod {p^2}, then the linear complexity LL of s∞s^\infty is

L={pn−p−12−δ(pn+12),if 2∈D0(p),pn−δ(pn+12),if 2∉D0(p).L=\begin{cases}p^n-\dfrac{p-1}{2}-\delta\left(\dfrac{p^n+1}{2}\right),&\text{if }2\in D^{(p)}_0,\\p^n-\delta\left(\dfrac{p^n+1}{2}\right),&\text{if }2\notin D^{(p)}_0. \end{cases}

The claim predicts the linear complexity for all permitted primes and periods, extending the case n=2n=2 discussed in the cited work; its resolution is not established by the supplied source context.

References

Primary source

Vladimir Edemskiy, “The linear complexity of new binary cyclotomic sequences of period p^n”, arXiv:1712.03947 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.