Find the optimal constant $c > 0$ such that the following holds. For all sufficiently large $N$ , if $A ⊔ B = {1, \dots, 2 N}$ is a partition into two equal parts, so that $∣ A ∣ = ∣ B ∣ = N$ , then there is some $x$ such that the number of solutions to $a - b = x$ with $a \in A$ and $b \in B$ is at least $c N$ .

Worked, still open.

number theory · open · formalized (Lean) · 0 attempts

machinery: minimum-overlap-constant,additive-combinatorics,autocorrelation-difference-counts,LP-relaxation-bound,fourier-analytic-bound,extremal-construction-optimality,subadditive-limit

use this record

vela registry pull vfr_37aec80d874a0239

vela reproduce examples/erdos-problems

evidence

unverified AI candidates (2)

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

Let [ M_x(A,B):=#{(a,b)\in A\times B:\ a-b=x}. ] For a fixed $N$, define the “worst best overlap” [ M(N)\ :=\ \min_{A\sqcup B=[2N],,|A|=|B|=N}\ \max_{x\in\mathbb Z} M_x(A,B). ] Then your statement [[nomath]](“for every partition there exists some $x$ with $M_x(A,B)\ge cN$”)[[/nomath]] is exactly the assertion [ M(N)\ \…

candidate solution ↗

llm-hunter · gpt 5.2, gpt pro 5.2 · unverified

3 LLM attack(s) recorded (gpt 5.2, gpt pro 5.2); unverified.

candidate solution ↗

formal

AMS 5 11 · test (literature)

theorem M_one : M 1 = 1

formal-conjectures/36.lean ↗

oeis

A393584 — a(n) is the minimum, over all partitions {X, Y} of {1..2n} with |X| = |Y|, of the maximum number of pairs (x, y) with the same difference x - y for x in X and y in Y.1,1,2,2,3,3,3,4,4,5,5,5,6,6,6,7,7,8,8,8,9,9,10,10,10,11,11,11,12,12,13,13,13

links

minimum overlap problem · reference

status