← All papers
First page of An improved lower bound for the minimum-autocorrelation constant

An improved lower bound for the minimum-autocorrelation constant

Shenai Chen, EnHao Gu

math.GM Oct 8, 2026 · v1
A Lean 4.19.0/Mathlib development formalizes the Bernstein certificate, overlap integrals, admissibility, mass formula and ordinary-function witness bounds for the autocorrelation lower bound.
We construct nonnegative bounded compactly supported functions on the real line that give the lower bound $\mathcal{A}\ge 0.4103779774321214877852987\ldots$ for the minimum-autocorrelation constant. This improves the explicitly certified bound $2378625/5958277=0.39921356\ldots$ reported by Russell. The construction combines a point mass with a monotone degree-ten polynomial density; a one-sided atom-removal argument then produces ordinary functions. Its numerical content reduces to exact rational polynomial identities and 20 Bernstein subinterval certificates. The finite certificate, actual overlap integrals, admissibility, mass formula, and ordinary-function witness bounds have been formalized in Lean 4.19.0; the pinned proof sources and recorded audit are supplied. The passage to the supremum constant is given separately as a mathematical argument. As applications, the same construction yields an upper bound below $1.5610183$ for the large-multiplicity generalized-difference-basis coefficient and a feasible squared mass below $2.436778$ for a continuous sparse-ruler relaxation. An appendix quantifies the loss under independent sampling followed by completion. No improved bound for the complete sparse ruler constant, or global optimality of the construction, is asserted.

The minimum-autocorrelation constant A is the supremum, over nonnegative L^1 functions, of the least autocorrelation on shifts in [0,1] divided by squared mass. The best explicitly certified lower bound was Russell's 0.39921356, against the Fourier upper bound 0.41077.

The construction combines a point mass with a monotone degree-ten polynomial density built from Chebyshev polynomials and given by exact rational parameters. A one-sided atom-removal argument then turns this into ordinary bounded, compactly supported functions. The numerical inequalities reduce to exact rational polynomial identities and 20 Bernstein subinterval certificates. The certificate, the actual overlap and mass integrals, admissibility, and the witness bounds are formalized in Lean 4.19.0 with Mathlib; the final supremum step and the applications are argued on paper only.

The construction gives A ≥ 0.4103779774..., improving the previous certified bound. The same construction gives an upper bound below 1.5610183 for the large-multiplicity generalized-difference-basis coefficient and a feasible squared mass below 2.436778 for a continuous sparse-ruler relaxation.

Polynomial / intervalDegreeAccepted leavesMax depth
P' on [0,1]910
g0-γ on [0,b]2110
g1-γ on [b,w]21136
g2-γ on [w,c0]1143
g3-γ on [c0,1]010
Bernstein certificate summary