erdős #43

← #42 · #44 → (packet.json; erdosproblems.com)

If $A, B \subset {1, \dots, N}$ are two Sidon sets such that $(A - A) \cap (B - B) = {0}$ then is it true that $(2 ∣ A ∣) + (2 ∣ B ∣) \leq (2 f ( N )) + O (1),$ where $f (N)$ is the maximum possible size of a Sidon set in ${1, \dots, N}$ ? If $∣ A ∣ = ∣ B ∣$ then can this bound be improved to $(2 ∣ A ∣) + (2 ∣ B ∣) \leq (1 - c + o (1)) (2 f ( N ))$ for some constant $c > 0$ ?

Worked, still open.

number theory · solved · prize $100 · formalized (Lean) · 0 attempts

machinery: Sidon/B_h,additive-combinatorics

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

This is exactly **Erdős Problem #43**. As of the current public status (edited 20 Dec 2025), the **first (additive $O(1)$) question is still open**, but the **second [[nomath]](“save a fixed constant $c>0$” when $|A|=|B|$)[[/nomath]] is false**.

candidate solution ↗

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

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

candidate solution ↗

formal

AMS 5 11 · solved (literature)

theorem erdos_43.parts.i : answer(False) ↔
    ∃ C : ℝ, ∀ᶠ N in Filter.atTop, ∀ (A B : Finset ℕ),
      A ⊆ Finset.Icc 1 N →
      B ⊆ Finset.Icc 1 N →
      IsSidon (A : Set ℕ) →
      IsSidon (B : Set ℕ) →
      (A - A) ∩ (B - B) = {0} →
      ((A.card.choose 2 + B.card.choose 2 : ℕ) : ℝ) ≤ ((f N).choose 2 : ℝ) + C

formal-conjectures/43.lean ↗

oeis

A003022 — Length of shortest (or optimal) Golomb ruler with n marks.1,3,6,11,17,25,34,44,55,72,85,106,127,151,177,199,216,246,283,333,356,372,425,480,492,553,585 A143824 — Size of the largest subset {x(1),x(2),...,x(k)} of {1,2,...,n} with the property that all differences |x(i)-x(j)| are distinct.0,1,2,2,3,3,3,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,10,10,10 A227590 — a(n) = A003022(n)+1 with a(1)=1.1,2,4,7,12,18,26,35,45,56,73,86,107,128,152,178,200,217,247,284,334,357,373,426,481,493,554,586

links

Vela Sidon frontier (A309370) · verified work

A B₂/Sidon problem — the same object family as Vela's verified Sidon records, where nine improved terms were accepted into OEIS A309370 (the campaign's first external adoption).

OEIS A309370 ↗ · verified-combinatorics (witnesses + verify.py) ↗ · the Erdős campaign

#14Let

A \subseteq N

. Let

B \subseteq N

be the set of integers which are representable in exactly one way as the sum of two elements from

A

.Is it true that for all

ϵ > 0

and large

N

∣{1, \dots, N} \ B ∣ ≫_{ϵ} N^{1/2 - ϵ} ?

Is it possible that

∣{1, \dots, N} \ B ∣ = o (N^{1/2})?

A143824 #30Let

h (N)

be the maximum size of a Sidon set in

{1, \dots, N}

. Is it true that, for every

ϵ > 0

h (N) = N^{1/2} + O_{ϵ} (N^{ϵ})?

A003022 #155Let

F (N)

be the size of the largest Sidon subset of

{1, \dots, N}

. Is it true that for every

k \geq 1

we have

F (N + k) \leq F (N) + 1

for all sufficiently large

N

?A003022 #530Let

ℓ (N)

be maximal such that in any finite set

A \subset R

of size

N

there exists a Sidon subset

S

of size

ℓ (N)

(i.e. the only solutions to

a + b = c + d

S

are the trivial ones). Determine the order of

ℓ (N)

.In particular, is it true that

ℓ (N) \sim N^{1/2}

?A143824 #861Let

f (N)

be the size of the largest Sidon subset of

{1, \dots, N}

and

A (N)

be the number of Sidon subsets of

{1, \dots, N}

. Is it true that

A (N) / 2^{f (N)} \to \infty ?

Is it true that

A (N) = 2^{(1 + o (1)) f (N)} ?

A003022

status