Arithmetic autocorrelation value distribution conjecture for binary m-sequences

From papers

Let M\mathcal{M} be a binary mm-sequence of period 2n12^n-1, where nNn\in\mathbb{N}. For an integer shift τ\tau with 1τ<2n11\leq\tau<2^n-1, let AMA(τ)\mathcal{A}^{A}_{\mathcal{M}}(\tau) denote the arithmetic autocorrelation of M\mathcal{M}. Arithmetic autocorrelation conjecture. (1) The arithmetic autocorrelation satisfies

AMA(τ){±(2k1):1k<n}.\mathcal{A}^{A}_{\mathcal{M}}(\tau)\in\{\pm(2^k-1):1\leq k<n\}.

(2) For each kk with 1k<n1\leq k<n, there are 2nk2^{n-k} shifts τ\tau satisfying 1τ<2n11\leq\tau<2^n-1 and

AMA(τ)=2k1.\left|\mathcal{A}^{A}_{\mathcal{M}}(\tau)\right|=2^k-1.

The conjecture is motivated by numerical experiments for binary mm-sequences, whose observed arithmetic autocorrelation values agree with the stated set and distribution. Its resolution would describe the complete value distribution of arithmetic autocorrelation for these sequences; the source leaves related questions for other generalized cyclotomic generators open.

Progress summary

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

Sources & referencesView supporting material

Primary source

Zhixiong Chen, Zhihua Niu, Yuqi Sang and Chenhuang Wu, “Arithmetic Autocorrelation of Binary m-Sequences”, arXiv:2111.11176 (2022).

Solutions 0

No solutions have been posted yet.