Erdős minimum overlap constant

Description of constant

$C_{1b}$ is the largest constant for which one has $\sup_{x \in [-2,2]} \int_{-1}^1 f(t) g(x+t)\ dt\geq C_{1b}$ for all non-negative $f,g: [-1,1] \to [0,1]$ with $f+g=1$ on $[-1,1]$ and $\int_{\mathbb{R}} f = 1$, where we extend $f,g$ by zero outside of $[-1,1]$.

Known upper bounds

Bound	Reference	Comments
$1/2=0.5$	[E1955]
$4/9=0.4444\dots$	Erdős (unpublished)
$5/12 = 0.41666\dots$	[MRS1956]
$0.4$	[MRS1956]
$0.385694$	Haugland (unpublished, 1993)
$0.382002$	[H1996]
$0.380927$	[H2016]
$0.380924$	[GGSWT2025]	AlphaEvolve
$0.380876$	[YKLBMWKCZGS2026]	TTT-Discover

Known lower bounds

Bound	Reference	Comments
$1/4=0.25$	[E1955]
$1-1/\sqrt{2} \approx 0.292893$	Scherk (unpublished, 1955)
$(4-\sqrt{6})/5 \approx 0.310679$	[S1958]
$\sqrt{4-\sqrt{15}} \approx 0.356393$	[M1959]
$0.379005$	[W2022]

Additional comments and links

The problem of determining $C_{1b}$ is known to be equivalent to Erdős problem #36. That is to say, $C_{1b}$ is known [H2016] to also be largest constant such that, whenever $N$ is large and ${1,\dots,2N}$ is partitioned into two equal subsets $A,B$, then there is an $x$ such that there are $\geq (C_{1b} - o(1))N$ solutions to $a-b=x$ with $a \in A$ and $b \in B$.
AlphaEvolve repository page for this problem
The Wikipedia page for this problem
Haugland’s page for this problem.
See also the page here for the autocorrelation constant related to Sidon sets.

References

[GGSWT2025] Georgiev, Bogdan; Gómez-Serrano, Javier; Tao, Terence; Wagner, Adam Zsolt. Mathematical exploration and discovery at scale. arXiv:2511.02864
[E1955] Erdős, Pál. Problems and results in additive number theory. Colloque sur la Théorie des Nombres, Bruxelles, 1955, 127-137 (1956).
[H1996] Haugland, J. K., Advances in the minimum overlap problem. J. Number Theory 58 (1996), no. 1, 71-78.
[H2016] Haugland, J. K., The minimum overlap problem revisited. arXiv:1609.08000 (2016).
[M1959] Moser, L., On the minimum overlap problem of Erdos, Acta Arith. 5 (1959), 117-119.
[MRS1956] Motzkin, T. S.; Ralston, K. E.; Selfridge, J. L., Minimal overlap under translation. Abstract Bull. Amer. Math. Soc. 62, 558 (1956).
[S1958] Swierczkowski, S., On the intersection of a linear set with the translation of its complement. Colloq. Math. 5 (1958), 185-197.
[W2022] White, E. P., Erdős’ minimum overlap problem. arXiv:2201.05704 (2022).
[YKLBMWKCZGS2026] Yuksekgonul, Mert; Koceja, Daniel; Li, Xinhao; Bianchi, Federico; McCaleb, Jed; Wang, Xiaolong; Kautz, Jan; Choi, Yejin; Zou, James; Guestrin, Carlos; Sun, Yu. Learning to Discover at Test Time, 2026.