A certified lower bound μ ≥ 0.380020 for Erdos’ minimum overlap problem

Jeff Pickhardt

Loading document…

A certified lower bound μ ≥ 0.380020 for Erdos’ minimum overlap problem

Abstract

Let μ denote the limiting constant in Erd˝os’ minimum overlap problem. We prove μ ≥ 0.380020, improving the previous certified lower bound 0.37912; the best known upper bound is 0.380868, so this closes about 51% of the remaining gap. The improvement comes from a constraint family absent from the two preceding Fourier programmes. Writing f + g = 1[−1,1] and ψ = 2f − 1, taking autocorrelations gives the exact identity M (x) + M (−x) = 1 2 Λ(x) − Cψ (x) with Λ = (2 − |x|)+. Since Cψ is a compactly supported autocorrelation, cCψ (ξ) = | bψ(ξ)|2 ≥ 0 for every real ξ, whereas White’s Fourier programme and its recent strengthening use only discrete Fourier-series frequencies. Their lattice constraints are a sparse subsample of a continuum family, and it is refinement of the frequency spacing below that lattice spacing, not extension of the frequency range, that moves the bound. The Boas–Kac–Krein factorisation theorem, sharpened by Ehm–Gneiting–Richards, explains why this family is strong: in dimension one an even compactly supported positive-definite function is exactly the autocorrelation of a real function of half support. The description of the even part of the overlap function is therefore lossless apart from the pointwise bound |ψ| ≤ 1, which enters only through |Cψ | ≤ Λ. The bound is certified by an explicit rational multiplier vector. The certificate carries no feasibility constraints beyond sign conditions, so verification reduces to exact rational arithmetic plus an interval upper bound for one integral of an explicit Lipschitz function; a self-contained verification script is provided.

File Details

v1 paper.pdf