OpenFrontiers
Join
← Back to the index
OP-11992OpenCombinatorics

Erdős minimum overlap constant (C1bC_{1b})

Erdős minimum overlap constant: determine C1bC_{1b} or improve its bounds; the repository records 0.379005 (lower) and 0.380868 (upper).

MSC 11B75 · Other combinatorial number theory

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

C1bC_{1b} is the largest constant for which one has

sup⁡x∈[−2,2]∫−11f(t)g(x+t) dt≥C1b\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]→[0,1]f,g: [-1,1] \to [0,1] with f+g=1f+g=1 on [−1,1][-1,1] and ∫Rf=1\int_{\mathbb{R}} f = 1, where we extend f,gf,g by zero outside of [−1,1][-1,1].

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

  • The problem of determining C1bC_{1b} is known to be equivalent to Erdős problem #36. That is to say, C1bC_{1b} is known [H2016] to also be largest constant such that, whenever NN is large and {1,…,2N}\{1,\dots,2N\} is partitioned into two equal subsets A,BA,B, then there is an xx such that there are ≥(C1b−o(1))N\geq (C_{1b} - o(1))N solutions to a−b=xa-b=x with a∈Aa \in A and b∈Bb \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 (from the repository page)

  • [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

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 0.379005; best known upper bound 0.380868. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
1/2=0.51/2=0.5 [E1955]
4/9=0.4444…4/9=0.4444\dots Erdős (unpublished)
5/12=0.41666…5/12 = 0.41666\dots [MRS1956]
0.40.4 [MRS1956]
0.3856940.385694 Haugland (unpublished, 1993)
0.3820020.382002 [H1996]
0.3809260.380926 [H2016]
0.3809240.380924 [GGSWT2025] AlphaEvolve
0.3808760.380876 [YKLBMWKCZGS2026] TTT-Discover
0.3808710.380871 [T2026] TogetherAI
0.3808680.380868 [YLTLYSTYLLGDHZSWZSHMELCZX2026] SimpleTES

Known lower bounds

Bound Reference Comments
1/4=0.251/4=0.25 [E1955]
1−1/2≈0.2928931-1/\sqrt{2} \approx 0.292893 Scherk (unpublished, 1955)
(4−6)/5≈0.310102(4-\sqrt{6})/5 \approx 0.310102 [S1958]
4−15≈0.356393\sqrt{4-\sqrt{15}} \approx 0.356393 [M1959]
0.3790050.379005 [W2022]
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Erdős minimum overlap constant ($C_{1b}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.