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
$0.380871$	[T2026]	TogetherAI
$0.380868$	[YLTLYSTYLLGDHZSWZSHMELCZX2026]	SimpleTES

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.
[T2026] Together AI. Einsteinarena-new-sota: State-of-the-art results on open math problems, 2026. URL https://github.com/togethercomputer/EinsteinArena-new-SOTA.
[YLTLYSTYLLGDHZSWZSHMELCZX2026] Haotian Ye, Haowei Lin, Jingyi Tang, Yizhen Luo, Caiyin Yang, Chang Su, Rahul Thapa, Rui Yang, Ruihua Liu, Zeyu Li, Chong Gao, Dachao Ding, Guangrong He, Miaolei Zhang, Lina Sun, Wenyang Wang, Yuchen Zhong, Zhuohao Shen, Di He, Jianzhu Ma, Stefano Ermon, Tongyang Li, Xiaowen Chu, James Zou, Yuzhi Xu, Evaluation-driven Scaling for Scientific Discovery, https://arxiv.org/abs/2604.19341