CS Paper Radar

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

Joonas Pääkkönen

cs.IT math.COmath.NT ·submitted 2026-11-11 15:48 UTC · v1
theorycode/dataunusual

Abstract

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.

Comment
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)

Closest papers

Nearest neighbours by meaning across the whole index.

Spatially Coupled MacKay-Neal Codes Achieve Capacity on BMS Channels at Fixed Degrees

cs.IT ·2026-09-14 ·Kenta Kasai
code/data similarity 0.49
Abstract · 43 pages; expanded preliminaries, proof explanations, BEC comparison, and historical context; exact certificates and verification software: …

We establish two degree-dependent results for spatially coupled MacKay-Neal codes on binary-input memoryless symmetric channels. The ensembles use uniform random smoothing and shorten both variable types outside the active chain. For $r=g=3$, every integer $\ell\geq4$, and each channel of capacity greater than $R=r/\ell$, there is a sequence of code realizations whose actual transmitted rate tends to $R$ and whose average sum-product bit error tends to zero. For $r=g=2$ and each $\ell\in\{3,4,5\}$, an interval of binary symmetric channels has capacity greater than $R$ but retains positive transmitted-bit error under terminated density evolution as chain length grows relative to coupling width. Both results follow from the signs of the same density-valued potential at uncoupled fixed points. The degree-three proof combines analytic bounds for $\ell\geq33$ with exact interval certificates for $4\leq\ell\leq32$, followed by threshold saturation and a projection argument for the actual rate. The degree-two proof analytically constructs a fixed point with negative potential and controls both boundary contributions. We relate the potential and the degree-two bifurcation condition to earlier statistical-mechanical predictions. The finite certificates and verification software are available in a versioned supplement.

0.59

Learning Finite-Memory Binary Sources

cs.IT math.PR ·2026-10-29 ·Maciej Skorski
similarity 0.49
Abstract

Estimating biased finite-memory sources from a single trajectory is a fundamental problem with practical impact, for example in estimating entropy for cryptography. We study order-$d$ binary sources whose conditional probabilities have bias at most $ε$, and establish *sharp* sample complexity bounds: relative accuracy $γ$ with confidence $1-δ$ needs $γ^{-2}\,(\tfrac12-ε)^{-d}\,(\log d+\log\tfrac1δ)$ samples up to constants depending on $ε$, with matching upper and lower bounds and no dependence on mixing time or spectral gap. The proof rests on a sharp bound on expected hitting times of the sliding-window (de Bruijn) chain, which stay of order $1/π(w)$ uniformly in $d$ exactly when $ε<\tfrac3{10}$, and on majorization of the window masses by those of independent biased coins. Applied to published entropy-source validations, the bounds show that their trace lengths may be underpowered: $10^6$ bits cannot resolve all transitions of an $8$-bit model to better than about $4.5\%$ relative error.

0.17

Absence of critical scaling in the Schelling segregation model

cs.GT cond-mat.stat-mechcs.MA ·2026-08-17 ·Mouhssine Rifaki
theoryunusual similarity 0.49
Abstract · 24 pages, 16 figures, 6 appendices. Over 12,500 simulation runs on periodic grids up to L = 320; Chebyshev radii r_0 up to 6 (k = 168 neighb…

We find no evidence of critical scaling in the Schelling segregation model, in either the Moore neighborhood or its dense-spectrum extension to Chebyshev radii up to $r_0 = 6$ ($k = 168$ neighbors). On periodic grids up to $L = 320$ with 50 trials per point (> 12,500 runs), every finite-size scaling diagnostic in the Moore baseline fails: the per-$L$ $T_c$ does not drift, Var$(S) \sim L^{-2.02 \pm 0.09}$ matches trivial averaging, $γ/ν\approx 0$, and the scaling collapse never reaches a finite optimum. The 8-site Moore neighborhood restricts satisfaction to ratios $j/k$ with $k \leq 8$, giving $S(T)$ a staircase structure with 23 rational thresholds; discreteness alone does not forbid criticality (cf. the Ising model), but the scaling evidence rules it out empirically. A branching-ratio calculation predicts subcritical cascades of mean size $1/(1-R)$ and is validated by perturbation experiments to within 15%; the multiscalar dissimilarity length stays finite across the transition. The dense-spectrum extension strengthens the negative verdict: across $r_0 \in {3,4,5,6}$ on $L \in {40,80,160}$ the Binder cumulant has no $L$-curve crossing and the per-$L$ $T_c$ drift is monotonic and unsaturated; at $r_0 = 4$, extending to $L = 320$ gives $α= -2.70$, below the critical boundary $α= -2$, dissolving an apparent $α= +0.81$ signal visible only on $L \in {40,80}$. The mechanism is the absence of long-range correlation in equilibrium plus deterministic high-$k$ dynamics, not the staircase structure. With a Beta-distributed heterogeneous tolerance, the intolerant tail drives segregation even at moderate population-average tolerance. The staircase theorem and cascade mechanism together account for the Schelling transition without invoking critical phenomena.

0.31

A class of Niho type four-valued cross-correlation functions between sequences of different periods

cs.IT ·2026-10-25 ·Yao Yao, Yufei Wang, Yongbo Xia, Nian Li, Xiangyong Zeng
similarity 0.47
Abstract

Determining the cross-correlation distributions between $m$-sequences and their decimated sequences is an important problem in sequence design. For two positive integers $n$ and $k$ with $n=2k$, this paper investigates the cross-correlation function between a binary $m$-sequence $\{u(t)\}$ of period $2^{n}-1$ and its $2^{\gcd(s,k)}+1$ short-period decimated sequences $\{u(dt+l)\}$, where the decimation $d=\frac{2^s}{2^s+1}(2^k-1)+1$ satisfies $1<s<n$ and $v_2(s)>v_2(k)$. The cross-correlation function is proved to be four-valued and its value distribution is completely determined. Several previously known binary cross-correlation functions are included in our result as special cases.

0.26

Sharp Minimax Limits and Compatibility Spectra for Critical Near-DFT Index-Only Frequency Estimation

eess.SP ·2026-09-01 ·Armon Rasooli, Mohammad Sadegh Narimani
similarity 0.47
Abstract

An $M$-channel discrete Fourier transform (DFT) channelizer routes an on-grid sinusoid to a single output. When each frame reports only one energy-proportional channel index, signed sub-bin frequency estimation becomes nonregular: dark-channel probability is quadratic in the offset, whereas orientation enters cubically. We study $N$ independent labeled reports under a known uniform-replacement probability $ε_N$ and a single deterministic unitary shared by all frequencies and frames, constrained to routing defect $τ/N$. If $\sqrt{N}ε_N \to λ< \infty$, we establish an attained global-in-frequency minimax limit at the critical scales $N^{-1/4}$ for frequency offset, $N^{-1/2}$ for unitary perturbation and replacement, and $N^{-1}$ for routing defect. The effective unitary tangent is a symmetric complete-graph edge field modulo one centering nuisance, and its first variation is a radius-dependent weighted divergence. For $λ>0$, evaluation at $k$ distinct normalized offset magnitudes yields an exact Fourier-Cauchy nullity spectrum: $\lfloor(M-1)/2\rfloor$ evaluations are necessary and sufficient, for every choice of distinct magnitudes, to certify neutrality at all magnitudes. The terminal nullspace has a greatest-common-divisor dimension formula and positive-definite aggregate curvature. Consequently, exact DFT routing is uniquely minimax within the complete critical tangent class for $M=3$, whereas every positive critical defect budget strictly improves the minimax constant for $M\geq4$. The analysis also yields a smallest-prime curvature-visibility law and, for $M\geq5$, discontinuous compatibility geometry but a continuous minimax value at the zero critical replacement floor $λ=0$.

0.24

A $(\log n)^{1/4}$ Bound for the Komlós Problem

cs.DM math.COcs.DS ·2026-09-08 ·Eren Ercan
theory similarity 0.46
Abstract · 28 pages, 1 figure. Lean formalization and exact-arithmetic certificate included as ancillary files

Let $A\in\mathbb{R}^{m\times n}$ have columns of Euclidean norm at most one. We prove that $\operatorname{disc}(A)\le2395\left(1+\log_+\frac n9\right)^{1/4}+2\sqrt2$. Here $\log_+t=\max\{0,\log t\}$. Building on Bansal and Jiang's affine spectral independence framework, we remove the $(\log\log n)^{7/4}$ factor from their bound. The fourth root comes from balancing the logarithmic decrease in the alive dimension against the fourth power of the row thresholds. Historical exponential sums control the covariance budget across size classes with summable thresholds. An exact threshold-sum certificate gives the coefficient $2395$, and rounding at most eight remaining fractional coordinates costs $2\sqrt2$. The finite construction also gives partial colourings from any prescribed starting point and at any prescribed depth, preserving existing signs. We formalize the partial- and full-colouring theorems in Lean, including the finite trajectory, exact threshold sum and final rounding, with Bansal--Jiang Theorem A.4 as the sole external research theorem assumption.

0.37

Sharp Lovasz-Theta Bounds on Random Graphs

cs.CC cs.DMmath.CO ·2026-09-24 ·Aaron Potechin, Jeff Xu
publishedtheory similarity 0.46
Abstract · FOCS'26

It is well known that the \Lovasz-Theta function of a random graph $G(n,\tfrac{1}{2})$ is $Θ(\sqrt{n})$. More precisely, it is tightly concentrated in the interval \( [\sqrt{n},\, 2\sqrt{n}], \) where the upper bound follows from an explicit dual witness for the associated semidefinite program. Numerical evidence and heuristic arguments suggest that the true value is $(1+o(1))\sqrt{n}$. However, closing this gap has remained a longstanding challenge, resisting existing techniques even in light of recent progress on sharp algorithmic thresholds and non-asymptotic free probability. In this work, we resolve this question by proving that the \Lovasz-Theta function of $G(n,\tfrac{1}{2})$ is $(1+o_n(1))\sqrt{n}$ with high probability, determining its asymptotic value up to vanishing relative error.

0.20

The threshold for online balancing of i.i.d. binary vectors

cs.DS math.PRmath.CO ·2026-09-14 ·Dylan J. Altschuler, Konstantin Tikhomirov
theory similarity 0.45
Abstract · Supersedes and replaces arxiv.org/abs/2509.02432, which has the same lower bound, but only has an upper bound for the ultra-sparse regime

Consider the task of online vector balancing for stochastic arrivals $X_1,\ldots,{X_T}$, where the $X_i$ are independent uniformly random $d$--sparse binary vectors in $\{0,1\}^n$. This is a random analogue of the online Beck--Fiala problem. We show that uniformly for $2\le d\le n/2$ and $T = Θ(n)$, the optimal online prefix discrepancy $\max\limits_{t\leq T}\left\|\sum_{i=1}^tσ_i X_i\right\|_\infty$ is of order \[ Θ\big(\max\{\sqrt d,\log\log n\}\big). \] The upper bound is achieved by an efficient online algorithm. Thus, for $d\le(\log\log n)^2$, the optimal discrepancy is $Θ(\log\log n)$ and is independent of the sparsity up to constant factors, whereas above this scale it is $Θ(\sqrt d)$, matching the order of the offline discrepancy. This identifies the threshold at which sparsity begins to govern the online discrepancy of the random Beck--Fiala model.

0.44