arXiv:2611.15635 · v1

An Empirical Square-Root Law for the Degree Discrepancy of Binary m-Sequences

首次提交 2026-11-11 23:48

版本更新 2026-11-11 23:48

雷达观测 2026-11-13 14:16

摘要

Let $k\ge 2$, $N=2^k$, $M=N-1$ and let $Δ(r)$ be the range, over all starting offsets, of the total-variation degree discrepancy of a length-$r$ window of a primitive binary linear feedback shift register (LFSR) of period $M$. Degree-discrepancy profiles for every $k\le 28$ support the scaling $\max_r Δ(r)=Θ(\sqrt{N})=Θ(2^{k/2})$. The tabulated peaks are maxima on a discrete grid, hence lower bounds on the exhaustive maximum. The normalized peaks $d_k=\max_{r\in R_k}Δ(r)/2^{k/2}$ oscillate between values near 1/2 and values that approach, but do not exceed, 1. The data suggest $\liminf d_k=1/2$ and $\limsup d_k\le 1$. We conjecture the same square-root law for the exhaustive maximum, with those normalized envelopes. A Brownian-bridge heuristic accounts for the square-root scale. The same profiles do not place the recorded maximizer at mid-path: after folding by the complement identity $Δ(M-r)=Δ(r)$, the median of $\min(ρ^*_k,1-ρ^*_k)$ is 0.35, and several $k$ (notably 16 and 28) peak on a short window. Mid-horizon $Δ$ remains a large fraction of the peak, so the square-root scale can still come from a Brownian-bridge envelope. The same range has two readings of the starting offset: a pairing fragment in serial-knockout scheduling, and a change to the plaintext on an LFSR orbit. The location of the maximizer is not part of the conjecture. Open questions that separate the conjecture from a theorem are listed.

作者备注：15 pages, 2 figures, 2 tables. Code and data: https://github.com/fv2fm2z7rk-droid/An-Empirical-Square-Root-Law-for-the-Degree-Discrepancy-of-Binary-m-Sequences (archived at https://doi.org/10.5281/zenodo.24139931)