A Certified Lower Bound for the Erdos Minimum Overlap Constant

Technical companion to Erdos Minimum Overlap: Certifying Both Ends of a Gap. That post is the narrative; this one is the derivation. It corresponds to the preprint and is written to be checked, not skimmed.

A note on notation. This site renders GitHub-flavoured Markdown and has no math typesetting, so mathematical symbols appear as Unicode and code spans rather than typeset formulas. Nothing is lost but elegance.

Abstract

Let mu denote the Erdos minimum overlap constant. We prove mu ≥ 0.3803953, improving the best published lower bound 0.37912 of Kim and Pilanci by 1.28e-3 and White's 0.379005 by 1.39e-3. The bound augments White's Fourier-analytic convex program with Bochner moment-matrix and polynomial-moment constraints over a cover of the residual parameter region.

The methodological point is not the augmentation but the certification. Each of the twelve dual certificates underlying the cover is verified by a Jansson-Chaykin-Keil a-posteriori bound computed in directed-rounding interval arithmetic, with the dual multipliers read from the same solve that produced the certificate. No step trusts the solver's status flag, its iteration log, or its floating-point arithmetic. This replaces a convenient but unjustified convention — taking a solver-reported objective less a fixed margin — and because the certified values exceed that convention at every centre, imposing rigour raises the bound rather than costing anything.

We give the bound in two tiers, and separately certify mu ≤ 0.380859056614806899090596051449 in exact rational arithmetic. We also correct the record: the value 0.380856 in current circulation is not an upper bound on mu.

1. The problem

Erdos asked, for a partition of the integers 1 through 2n into two sets A and B of size n, how small the largest difference-multiplicity

max over k of  #{ (a,b) in A x B : a - b = k }

can be made. Writing M(n) for that minimum, the limit mu = lim M(n)/n exists, and admits a continuous formulation:

taken over measurable h : [0,2] → [0,1] with integral 1, where both h and 1 − h are extended by zero outside [0,2].

The two sides are attacked by disjoint machinery. Upper bounds are exhibitions: any admissible h supplies one, and the current records come from large-scale automated search. Lower bounds are exclusions: they must rule out every h at once, which requires a certified relaxation. This paper is about the lower side.

State of the art

	bound	source
Lower, published	0.37912	Kim and Pilanci, ICML 2026
Lower, prior	0.379005	White, Acta Arithmetica 2023
Lower, this work	0.3803953	—
Upper, certified here	0.3808590566	arena witness, exact arithmetic

2. Results

Theorem 1. mu ≥ 0.3803953.

Theorem 2. mu ≥ 0.380000, using only the twelve certificates of Section 4 together with White's published Table 2.

Theorem 3. mu ≤ 0.380859056614806899090596051449, certified in exact rational arithmetic.

Theorem 2 deserves comment. It is numerically weaker than Theorem 1 but rests on a far shorter chain: our own contribution enters only through twelve interval-arithmetic certificates, and everything outside the residual region is quoted from a peer-reviewed paper. Where the two differ in spirit — one maximally strong, one maximally defensible — I would rather a reader take the second.

What is not claimed. Nothing here closes the gap, and Section 7 gives a containment argument showing this family of relaxations cannot: it is bounded above by roughly 0.38065 at the parameters of the extremal function, some 2.1e-4 short of the certified upper bound. Section 8 records five further approaches ruled out with proofs. Those exclusions are a substantive part of the contribution — they say where the remaining difficulty is not.

3. The augmented program

White's program tracks a competitor through cell averages of a function M on a grid of N cells, together with the first T Fourier coefficients (c_k, d_k) of the associated density f, subject to linear and second-order-cone constraints indexed by a parameter triple theta = (E(M), c1, d1). We add two families:

1. Bochner moment-matrix PSD. For f and for 1 − f, the Hermitian Toeplitz matrix of Fourier coefficients is positive semidefinite. Imposed at truncation level 40.
2. Polynomial-moment positivity. The integral of x^(2k) f is nonnegative for k ≤ 10, expressed in (c,d) through the Fourier expansion of x^(2k), with an analytic remainder bounding the truncated tail.

A remark on truncation, which is the trap in this subject. Truncating a series inside a valid inequality, without an analytic bound on the discarded tail, silently strengthens the constraint and inflates the resulting bound. This failure mode retracted two intermediate results during this work. Every truncated sum in the final program carries a proved remainder.

The residual region

White's divide-and-conquer reduces the problem to a single box: combining his Table 2 shows that either mu ≥ 0.37925, or the extremal function's parameters satisfy

0    ≤ E(M*) ≤ 0.06
0.35 ≤ c1*   ≤ 0.45
-0.02 ≤ d1*  ≤ 0.02

All twelve of our centres lie in this box, and it is what binds in Theorem 1.

4. Certification

This is the paper's main content.

4.1 Why solver-reported bounds are not bounds

A conic program solved by an interior-point method returns an approximate primal-dual pair. The dual objective lower-bounds the primal optimum only if the dual point is feasible, and an interior-point iterate is feasible only up to its residual. It is therefore not sound to report a dual objective, or a solver's printed objective less an ad-hoc margin, as a lower bound.

Both are widespread. This project did the second for months: it anchored each certificate at solver value − 1e-5, a margin chosen for comfort rather than derived from anything. Worse, the helper that was supposed to guard this gated on the wrong column of the solver's iteration table — CLARABEL prints iter pcost dcost gap pres dres, and the code read pres, the primal residual, while calling it the dual residual. The docstring even described the correction that ought to be applied, and the implementation never applied it.

4.2 The Jansson bound

Write the canonical form as: minimise c'x subject to Ax + s = b, s in a cone K. Let z be the approximate conic dual the solver returns. Following Jansson, Chaykin and Keil (2007), for every primal-feasible x:

c'x  ≥  -b'z  +  pen_zs  -  pen_Dx

  pen_zs = sum_j min(0, lambda_min(z_j)) * sbar_j     ≤ 0
  pen_Dx = sum_i |D_i| * xbar_i                       ≥ 0,   D = c + A'z

where xbar_i are a-priori bounds on the model variables and sbar_j bound the slack sizes. Write p_lo for the right-hand side, evaluated with every arithmetic step in directed-rounding interval arithmetic and with verified enclosures for the per-cone minimum eigenvalues.

4.3 The transport proposition

The step that makes this usable inside a parameter cover is the following. Moving theta within the residual region changes only the right-hand side b of the four parameter-dependent constraints; the matrix A and the objective c are untouched. Hence:

• -b(theta)'z = -b(theta_c)'z + shift_c(theta) exactly, with shift_c White's dual-objective transport;
• pen_Dx is theta-independent, since D does not involve b and the xbar_i are fixed model bounds;
• pen_zs is theta-independent when it vanishes, i.e. when z lies in the dual cone.

The driver asserts pen_zs = 0 at every centre and refuses to emit one otherwise. It held at all twelve. Crucially the multipliers defining shift_c are read from the same solve that produced p_lo: pairing a certificate from one solve with multipliers from another is unsound, because p_lo bounds the dual objective of one specific z.

4.4 The certified anchors

At N = 48,000, comparing the old convention against the certificate:

centre	convention	certified p_lo	gain
row1	0.380698115	0.381572848708	+8.75e-4
row2	0.380677211	0.381665700133	+9.89e-4
row3	0.381042228	0.382537653309	+1.50e-3
row4	0.380338114	0.380505566439	+1.67e-4
row5	0.380611839	0.380710285038	+9.85e-5
row6	0.380436448	0.380552510960	+1.16e-4
row7	0.382003546	0.385119737480	+3.12e-3
cde1	0.380346079	0.380447891266	+1.02e-4
cde2	0.380377646	0.380525911216	+1.48e-4
cde3	0.380302283	0.380413948769	+1.12e-4
cde4	0.380606798	0.381353402400	+7.47e-4
cde5	0.380393675	0.380795566289	+4.02e-4

Every certified value exceeds the convention it replaces. Imposing rigour raised the bound.

5. Proof of Theorem 1

The cover value at a parameter point is Cover(theta) = max over c of Phi_c(theta), a maximum of valid conditional lower bounds and hence itself one. Theorem 1 follows from bounding Cover below on every region of a partition of the parameter space.

5.1 Rigorous box minima

On a box we grid and add a Lipschitz cell-error term eps = L_max * half-diagonal, with L_max the maximum gradient magnitude of the quadratics Phi_c on that box. Since a minimum of a maximum of concave quadratics need not be attained at a corner, the grid-plus-Lipschitz value is the rigorous box minimum.

An observation that cost me three separate detours. The certified duals are steeper than the convention they replace — L_max rises from 0.149 to 0.380 on the residual region — so a single grid pays more than twice the eps it used to, absorbing about half the gain. Adaptive subdivision, recomputing L_max per sub-box, drives eps to 4.1e-8 and recovers it:

method	floor	eps
single 4001² grid	0.3802897673	4.92e-6
adaptive, depth 12	0.3803949736	4.02e-7
adaptive, depth 20	0.3803953504	2.50e-8

An honest certificate costs Lipschitz slack, and the payment is always resolution, never mathematics. The same pattern recurred on the region cover.

5.2 The regions

On the residual region this gives Cover ≥ 0.3803953504, attained near (h, p) = (0.00281, 0.39219). The remaining regions:

region	floor	margin over core
core	0.3803954	binding
R16	0.3803961	+7e-7
R17	0.3803972	+1.8e-6
R9	0.3803979	+2.5e-6
R6	0.3804601	+6.5e-5
R7	0.3805539	+1.6e-4

so the residual region binds and Theorem 1 follows. Those three top margins matter for what comes next: any future gain on the core meets them immediately.

5.3 The robust tier

White's Table 2 is headed "Optimum lower bound" and he uses its entries as such, writing that the first line shows "either mu ≥ 0.38 or E(M*) ≤ 0.75". Taking his published bounds for the seventeen regions outside the residual set, and supplying only our own certified cover for the remaining strip and the residual region, gives Theorem 2. Nothing else is load-bearing.

6. The upper bound, and a correction

6.1 A certified upper bound

Any admissible step function gives an upper bound, but the published values are float64 evaluations of float64 iterates. Every construction I examined fails exact feasibility, by between 1e-16 and 4e-14 in mass — harmless in size, but enough that the stated bounds were not theorems as written.

The fix is to snap the construction to an exactly feasible rational point and evaluate all 2n − 1 signed lags in integer arithmetic. Applied to the best publicly downloadable witness, after a local polish:

whose decimal expansion, rounded upward as an upper bound must be, is 0.380859056614806899090596051449. No floating-point step enters the chain.

A detail worth flagging for anyone evaluating these constructions: the supremum is over both lag signs. The record witnesses attain theirs at negative lags (−33 for one, −328 for another), so a scan over nonnegative lags silently reports a number that is too small — and too small in the flattering direction.

6.2 The value 0.380856 is not a bound

A figure of 0.380856 is currently quoted as the best known upper bound. It is not one.

The construction it derives from is genuinely admissible — 4096 cells, mass exactly right, values in range. But its objective is 0.3809489501030183. The reported value is recovered bit-for-bit only by dividing by a cell count of 4096.9999999999 rather than 4096:

max(corr) * 2 / 4096              = 0.3809489501030183   <- honest
max(corr) * 2 / 4097              = 0.38085596768903174
max(corr) * 2 / 4096.9999999999   = 0.38085596768904106  <- matches the stored value

and that constant appears verbatim in the generating program. The honest value is worse than constructions from four years earlier. The authors identified and repaired this in their own repository a month after publication; the paper appears not to have been revised, and the figure continues to propagate.

I note it because a lower-bound paper that quotes a false upper bound misstates the size of the open gap — and because the mechanism is instructive. An automated search was rewarded for a number its own evaluator would accept, and it found a way to make that number smaller.

7. What this architecture cannot do

An earlier version of this work asserted an explicit saturation ceiling of 0.380713. That derivation does not hold: its own per-row table yields a value exceeding the certified upper bound, and the published figure substitutes a min-over-rows quantity for the theorem's per-row right-hand side. It is withdrawn and replaced by the following, which needs no sensitivity linearisation.

Numerically, at the parameters of the extremal function, that limit is about 0.38065, pinned two independent ways — Richardson extrapolation on an N-ladder, and complementary slackness with the entire cell-envelope slack removed. Since the certified upper bound is 0.3808591, this architecture is at least 2.1e-4 short at the single parameter point where the extremal function lives, before any loss from the cover.

Two corollaries sharpen where the slack is not:

• An exact moment-body program, which dominates the present program plus any further constraint family on the f-side, exceeds the certified anchor by only 3.77e-5 at the binding centre — and that headroom shrinks as N grows. The f-side is closed.
• The discretisation direction obeys a clean law, val(N) ≈ 0.380541649 − 3.9724/N, fitted on N = 48,000 and 96,000 and reproducing N = 20,000 to 2e-6. About 8.3e-5 remains unrealised as N grows without bound.

8. Approaches ruled out

Five, each with a proof rather than a failed experiment.

Discretisation-error bounds. One would like mu ≥ M_n − eps_n with M_n the n-cell minimum. The cell-average projection error satisfies C(P_n h)(md) = C_h(md) + A_e(md) at lattice lags, and the sequence m → A_e(md) is positive-definite, so its maximum sits at m = 0 and equals the entire detail energy. Positivity therefore forces the error to be maximally adverse rather than allowing it to be signed — the opposite of what one hopes. The sharpest lattice-only bound is ≤ 0 for every n. Required eps_n at n = 256 is 6.7e-4; provable is about 0.36.

Single-weight lag averaging. Replacing the supremum over lags by an average against a weight w makes the objective concave in h when w is positive-definite, so the infimum sits at an extreme point, and the extreme points are indicators. The reduction is correct and vacuous: the resulting bound is capped at 0.3294738 for any single probability weight, and at exactly 1/4 for positive-definite ones, by an exact rational certificate over 51 explicit adversaries. Collapsing the supremum costs at least 0.05, while the extreme-point structure gained is free information — indicators are weak-* dense and the functional is weak-* continuous, so the infimum over the whole set already equals the infimum over indicators.

Argmax disjunctions. If a feasible set is contained in the union of the branch conditions, then the minimum over branches of the constrained infima equals the unconstrained infimum, exactly. Branching on which lag attains the maximum is therefore identically worthless, at every discretisation, level, solver and tolerance.

Sharpened cell envelopes. Replacing the cell-minimum bound by the sharp mass-and-cap (bathtub) bound is valid and strictly dominant, with the tangent at zero reproducing White's line exactly. It is nonetheless contained in the same continuum program — a Richardson extrapolator for the discretisation wearing a constraint's clothing, obtainable more cheaply by increasing N.

Moment-body cuts on the f-side. Valid, free of truncation traps, and genuinely outside the Bochner cone at every finite level. Capped at 3.8e-5 by the meter above. Dead on magnitude, not on mathematics.

9. Reproducibility

All code and data are in the project repository. Every headline number was regenerated from scratch in a clean environment; the full-space driver reproduces its stored result byte-identically. Two independent re-implementations of the cover extension agree to more than ten significant digits.

One explicit warning for anyone reading that repository: the helper historically used there to extract "rigorous" bounds from solver logs is not a certificate. It applies no correction for dual infeasibility, and its eligibility test read the primal residual while naming it the dual residual. Both defects are now documented in the code itself. No number in this write-up depends on it.

References

1. E. P. White, A new bound for Erdos' minimum overlap problem, Acta Arithmetica 208 (2023), 235–255. arXiv:2201.05704
2. S. Kim and M. Pilanci, AI-assisted discovery of convex relaxations via dual agents, ICML 2026, PMLR 306. arXiv:2606.31182
3. C. Jansson, D. Chaykin and C. Keil, Rigorous error bounds for the optimal value in semidefinite programming, SIAM J. Numer. Anal. 46 (2007), 180–200.
4. J. K. Haugland, A new upper bound on the constant in the Erdos minimum overlap problem, 2016. arXiv:1609.08000