Erdős minimum overlap

This notebook is a self-contained mathematical and computational companion to the Erdős minimum overlap section in the paper.

The task template, including the prompt given to the agents, is available here.

The outline is as follows:

• 1. Problem Definitions
• 2. S1. A new lower bound of $0.380552$.
• 3. Comparison with AlphaEvolve on the upper bound
• 4. Additional findings

The required packages are:

• Python 3.10 or later
• NumPy
• IPython
• A C compiler with the MPFI, MPFR, and GMP libraries

Run the notebook from its own directory, from top to bottom. The lower-bound replay uses directed MPFI arithmetic and stops if these libraries are unavailable; it has no floating-point substitute. Set MPFI_PREFIX only for a nonstandard installation. The four interval rows usually take 15–30 minutes.

1. Problem Definitions

Erdős’s minimum-overlap problem asks how evenly two complementary parts of an interval can avoid one another under translation. The constant below is its continuum form for balanced partitions of long integer intervals.

Let $\chi=\mathbf 1_{[-1,1]}$. An admissible profile is a measurable function $f\colon\mathbb R\to[0,1]$, supported on $[-1,1]$, with $\int f=1$. Put $g=\chi-f$ and

Both $f$ and $g$ are nonnegative and have mass one. Hence $C_f\ge0$, $\int C_f=1$, and $\operatorname{supp}C_f\subset[-2,2]$.

The published bounds used for comparison in the paper are

from Kim and Pilanci (2026) and Ye et al. (2026), respectively.

The next cell loads the shared packages, authenticates both local inputs, and reads the certificate arrays without pickle.

2. S1. A new lower bound of $0.380552$.

Theorem 2.1.

The minimum-overlap constant $\mu$ satisfies

We first prove why the finite certificate format implies a global theorem, then replay its four rows.

2.1 Phase-coupled Fourier support

Lemma 2.2.

For a real frequency $\xi$, define

with $s(0)=1$. If $s(\xi)\ne0$, then every admissible profile satisfies

Proof. Use the Fourier convention $\widehat h(\xi)=\int h(t)e^{-i\xi t}\,dt$ and write $\widehat f(\xi)=a+ib$. With the stated correlation orientation, the transform of $C_f$ is $\widehat f(-\xi)\widehat g(\xi)$. Since $\widehat\chi(\xi)=2s(\xi)$, comparison of real and imaginary parts gives, up to the irrelevant sign convention for $Q$,

Completing the square in $a$ yields

At a zero of $s$, the same identities instead give $Q=0$ and $P=-a^2-b^2\le0$. $\square$

An equivalent form, used by the certificate, is the support inequality

Indeed, substitute the preceding inequality and maximize the resulting concave quadratic over $Q$. At a zero of $s$, both sides of the support inequality are zero or the left side is negative, so the support form extends there as well. This formulation retains the sine information and permits arbitrary real, rather than only harmonic, frequencies.

2.2 The four-row certificate

Lemma 2.3 (one valid dual row).

Choose finitely many real frequencies $\xi_k$, numbers $\alpha_k>0,\beta_k$, and a quadratic polynomial, and put

If

then every admissible $f$ with overlap first moment $m=\int xC_f(x)\,dx$ obeys

Proof. Let $G_+=\max(G,0)$. Since $0\le C_f\le M(f)$ and $\int G_+\le1$,

The first two overlap moments are

To see the second identity, view $C_f$ as the density of $U-T$, where independent variables $T$ and $U$ have densities $f$ and $g$. Their means are opposite, while $\int t^2(f(t)+g(t))\,dt=\int_{-1}^{1}t^2\,dt=2/3$. Applying Lemma 2.2’s support form frequency by frequency now gives the stated $q(m)$. $\square$

The box constraint and the bathtub principle imply $|\int tf(t)\,dt|\le1/2$, hence $|m|\le1$. Reflection changes the sign of $m$ without changing $M(f)$, so it suffices to cover $m\in[0,1]$.

Certificate verification.

Each stored row is a decimal specification of $a_0,a_1,a_2$ and the triples $(\xi_k,\alpha_k,\beta_k)$. MPFI parses each decimal into an outward-rounded 128-bit interval. The accompanying C verifier then:

1. covers all of $[-2,2]$ by recursively bisected cells;
2. encloses $G$ on each cell by a midpoint Taylor formula and the global bound $2|a_2|+\sum_k(|\alpha_k|+|\beta_k|)\xi_k^2$ for $|G''|$;
3. integrates sign-certified positive runs with an interval antiderivative;
4. charges every unresolved terminal cell by $\operatorname{width}\max\{\sup G,0\}$, so a missed or tangential zero cannot invalidate the result; and
5. evaluates the Fourier support charge with directed rounding, rejecting any row for which $\alpha_k$ is not rigorously positive when $\beta_k\ne0$, and subtracts a conservative $2\times10^{-12}$ guard from the constant coefficient of $q$.

Thus budget_pass=true proves the continuous positive-part condition, not merely a grid sample. The final cover calculation uses the printed outward lower coefficients as exact decimal rationals.

Optional regeneration. The numerical witnesses can be regenerated with witness_generation/generate_witness.py. Regeneration is not required to verify the lower bound; the source is included for completeness.

The next cell authenticates and unpacks the four dual rows, then compiles the directed-interval verifier used by the certificate.

The next cell runs the verifier on all four rows and rejects any row whose continuous positive-part budget is not certified.

The next cell checks the four mean intervals with exact rational arithmetic, prints their certified floors, and computes the gap-closing percentage used in the paper.

Proof of Theorem 2.1. The four closed intervals meet exactly and cover $[0,1]$; reflection covers negative first moments. Lemma 2.3 therefore proves Theorem 2.1 for every admissible measurable profile. $\square$

Station Reference.

The certificate architecture is recorded in Archives #22, #31, and #49. The dense-frequency rows and completion work are recorded in Archive #53 and Research Center Evaluations #1038, #1042, and #1045. The run produced the phase-coupled relaxation, decisive witnesses, and a certificate above $0.38055$. The directed MPFI replay and one same-method bridge row were completed afterward; all four serialized rows are verified without trusting the optimizer.

Related Work. White (2023) retained complex Fourier phase data and used conic optimization. Kim and Pilanci (2026) added Toeplitz and Bochner moment constraints and proved the previous lower bound $0.37912$. The theorem above instead uses a generator-eliminated support inequality at arbitrary real frequencies, a dense nonharmonic frequency comb, and an outward-rounded certificate. It appears to give the first published lower bound above $0.37912$.

3. Comparison with AlphaEvolve on the upper bound

Theorem 3.1.

There is an admissible 2,048-cell step profile whose continuum overlap satisfies

Proof. Give the interval $[-1,1]$ $N=2048$ cells of width $h=2/N$ and let $w_j$ be the value on cell $j$. Every stored binary64 value is interpreted as its exact dyadic rational. The stored sum misses $N/2$ by a tiny positive amount; the code adds that exact deficit to one interior coordinate and proves that all values remain in $[0,1]$.

At an aligned shift $kh$,

where only indices for which both cells exist are included. The code enumerates all $2N-1$ aligned shifts using Python integers. For arbitrary real shift, the correlation of two equal-grid step functions is affine between consecutive aligned shifts, so its global maximum occurs at one of the enumerated breakpoints. The finite exact computation is therefore a proof for every real shift, not a sampled approximation. $\square$

The next cell interprets the stored profile as exact dyadic rationals, repairs its mass, and checks every aligned shift with integer arithmetic.

Station Reference.

The profile comes from Research Center Evaluation #1681, initialized from the seed retained by Evaluation #1637; Archive #41 records the construction lineage. The exact mass correction and integer replay verify the stored profile without altering the construction method.

Related Work. Georgiev et al. (2025) reported $0.380924$, and Yüksekgönül et al. (2026) later reported an asymmetric construction near $0.380876$. Ye et al. (2026) subsequently gave the sharper published upper bound $0.380868$. Thus it independently improves the AlphaEvolve value while remaining above the current published record.

4. Additional findings

These are additional results that may be interesting but are not included in the spotlight.

4.1 Exact geometry under averaging and interpolation

The minimum-overlap problem is invariant under reflection, but this symmetry does not imply that averaging a profile with its reflection improves it. We derive an exact identity showing that reflection averaging adds a correction equal to one quarter of the autocorrelation of the asymmetric part; at zero shift, this is the positive penalty $\|f-\mathcal Rf\|_2^2/4$. We also prove that interpolation between two profiles acquires an analogous correction determined by the autocorrelation of their difference. These identities explain why asymmetric profiles can outperform their symmetrizations and why a straight path between two good constructions can pass through profiles with substantially larger overlap.

Write

Theorem 4.1 (symmetrization identity).

If $f_s=(f+\mathcal Rf)/2$ and $d=f-\mathcal Rf$, then

Proof. Since $C_f=R_{f,\chi}-R_f$, its first term is linear in $f$ and its second is quadratic. The evenness of $\chi$ gives $R_{\mathcal Rf,\chi}(x)=R_{f,\chi}(-x)$. Expanding $R_{f_s}$ bilinearly and collecting terms leaves

At $x=0$ the correction is $\|f-\mathcal Rf\|_2^2/4$. Thus reflection averaging need not improve the objective: it can create a new central-overlap cost. $\square$

Theorem 4.2 (chord-curvature identity).

For admissible profiles $a,b$ and $f_\lambda=(1-\lambda)a+\lambda b$,

Proof. The term $R_{f_\lambda,\chi}$ is linear in $\lambda$. Expanding $R_{f_\lambda}$ and subtracting it from that linear term gives

This exact correction explains why a straight interpolation between two good profiles can cross a substantial overlap barrier. $\square$

Station Reference.

The symmetrization identity is recorded in Archive #19 and Research Center Evaluations #351 and #373. The chord-curvature identity is recorded in Archive #60 and Evaluations #1124, #1129, and #1143.

Related Work. Correlation algebra, reflection symmetry, and polarization identities for quadratic functionals are classical. White (2023) analyzed an even-overlap restriction in a simplified linear program before passing to the unrestricted problem with a convex program. Applied here, polarization gives exact formulas for the change in overlap under reflection averaging and affine interpolation.

4.2 A rigorous local self-energy plateau

We use the self-energy $c=\int f^2$ to follow the minimum-overlap problem from the constant profile toward Boolean profiles. For the constrained optimum $\mu_{\mathrm{se}}(c)$, the zero-shift overlap gives the universal lower bound $1-c$, and we prove that this bound is attained throughout a nontrivial interval beginning at $c=1/2$. The proof compares the linear loss of the constant profile under translation with the quadratic autocorrelation of a mean-zero perturbation. Along the constructed family $f_s=\frac12+s\phi$, the zero shift remains globally maximizing for sufficiently small $|s|$, providing a rigorous starting point for studying when off-center maximizers appear along controlled deformations.

For $c\in[1/2,1]$, define the constrained optimum

The identity $C_f(0)=\int f(1-f)=1-c$ immediately gives $\mu_{\mathrm{se}}(c)\ge1-c$.

Theorem 4.3 (local plateau).

There exists $\varepsilon>0$ such that

Proof. Choose a nonzero $\phi\in C_c^1((-1,1))$ with $\int\phi=0$ and $\|\phi\|_2=1$. Let its support have distance $r>0$ from the two endpoints, put $B=\|\phi\|_\infty$, $K=\|\phi'\|_2^2$, and set

For $|s|\le s_0$, the function $f_s=\tfrac12+s\phi$ is admissible and $\int f_s^2=\tfrac12+s^2$. Write $A_\phi(x)=\int\phi(t)\phi(t+x)\,dt$. If $|x|<r$, the two linear boundary terms vanish because the translated interval still contains $\operatorname{supp}\phi$, and therefore

Translation in $L^2$ gives

so the chosen bound on $s$ makes the difference negative for $0<|x|<r$. For $|x|\ge r$, the unperturbed triangular overlap is at most $1/2-r/4$; Cauchy–Schwarz and $|A_\phi|\le1$ give

Thus zero is the global maximizing shift and $M(f_s)=C_{f_s}(0)=1-(1/2+s^2)$. Taking $s=\sqrt{c-1/2}$ attains the universal lower bound throughout the stated interval. $\square$

Station Reference.

The self-energy parameter and the identity $C_f(0)=1-c$ are recorded in Archive #5. The local plateau theorem and explicit-$\varepsilon$ proof are recorded in Archive #71, answering the local part of Question Room Discussion #12. Archive #73 and Research Center Evaluations #1309, #1311, and #1318 record numerical exploration beyond the proved local interval.

Related Work. Scalar deformations of the minimum-overlap functional go back to Świerczkowski (1958) and Moser and Murdeshwar (1966), who parameterized the problem by mass and derived bounds near mass $1/2$. Parameterizing instead by the self-energy $\int f^2$, and the resulting exact local plateau, appear to be new.

4.3 Exact constructions for the periodic companion problem

We place the two-unit active interval on a circle of circumference $L$ and determine when the average lower bound $1/L$ is attained exactly. Equality is equivalent to assigning every nonzero Fourier mode of the active arc wholly to one side of the partition. Using this criterion, we construct constant-overlap optimizers for every $L=2+1/(2q)$ and an additional rational optimizer at $L=12/5$. The resulting Dirichlet-kernel ladder and ten-level rational construction provide explicit solvable models of how the boundary gap and Fourier spectrum interact.

This section concerns a companion problem, not a new bound on the original interval constant. Let $\mathbb T_L$ be a circle of circumference $L\ge2$, let $a$ be the indicator of an arc of length two, require $0\le f\le a$ and $\int_{\mathbb T_L}f=1$, put $g=a-f$, and define the cyclic overlap

Write $\mu_{\mathrm{per}}(L)$ for the infimum of $\max_xC_{\mathrm{per}}(x)$ over these periodic profiles.

Preliminary observation. Fubini gives

so $\max_x C_{\mathrm{per}}(x)\ge1/L$. Equality holds exactly when the overlap is constant. Since

this is equivalent to the Fourier-mask condition

Theorem 4.4 (an infinite exact Dirichlet-kernel ladder).

For every integer $q\ge1$,

Proof. Put $N=4q+1$, divide the circle into $N$ cells of width $1/(2q)$, use the first $4q$ cells as the active arc and the last as the gap, and for every residue $j\pmod N$ define

The last value is zero. The inequalities

show $0\le f_j\le1$. Root-of-unity summation gives $\sum_jf_j=2q$, hence the step function has mass one. At a nonzero finite Fourier mode, the arc indicator has coefficient $-e^{2\pi ik/N}$. The profile has that same coefficient for $k\in\{\pm1,\ldots,\pm q\}$ and coefficient zero at every other nonzero mode. Thus it satisfies the Fourier-mask condition above. The cell-shape factor vanishes at every nonzero continuum mode divisible by $N$, so the finite mask covers all continuum Fourier modes. The overlap is constant at its mean $1/L=2q/(4q+1)$. $\square$

Theorem 4.5 (a rational tight point at $L=12/5$).

At $L=12/5$, ten active cells and two gap cells, all of width $1/5$, admit the exact active levels

The ten active levels give $\mu_{\mathrm{per}}(12/5)=5/12$.

Proof. The levels lie in $[0,1]$ and sum to five, so both $f$ and its arc complement have mass one. The exact computation below proves that all twelve aligned cyclic correlations equal $5/12$. A cyclic correlation of equal-grid step functions is affine between consecutive aligned shifts, so it is identically $5/12$ for every real shift. The averaging bound supplies the matching lower bound. $\square$

The next cell checks the mass, box constraints, and all twelve aligned cyclic overlaps of the rational $L=12/5$ construction exactly.

Station Reference.

The periodic averaging bound, Fourier-mask observation, and Dirichlet ladder are recorded in Archive #59 and its correction, with Research Center Evaluations #1084, #1089, #1096, #1127, and #1134; the companion problem arose in Question Room Discussion #10. The rational $L=12/5$ construction is recorded in Archive #79 and Evaluation #1430.

Related Work. Martos et al. (2023) study the minimum-overlap problem on finite abelian groups and obtain upper and lower bounds. Their setting provides finite-group background for the periodic companion problem. Here the Dirichlet-kernel construction gives an infinite ladder of exact optimizers, while the $L=12/5$ construction gives a further rational optimizer outside that ladder.