Erdős Problem 43

Reference: erdosproblems.com/43

@[reducible, inline]

noncomputable abbrev Erdos43.f (N : ℕ) : ℕ

Let $f(N)$ be the maximum possible size of a Sidon set in $\{1,\ldots,N\}$.

Equations

• Erdos43.f N = (Finset.Icc 1 N).maxSidonSubsetCard

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

If $A$ and $B$ are Sidon sets in $\{1,\ldots,N\}$ with $(A-A)\cap(B-B)=\{0\}$, is it true that $$\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq\binom{f(N)}{2}+O(1)?$$

The answer is no; the Erdős Problems page notes that this follows from the solution to Erdős Problem 42.

theorem Erdos43.erdos_43.parts.ii : False ↔ ∃ c > 0, ∃ (o : ℕ → ℝ), o =o[Filter.atTop] 1 ∧ ∀ᶠ (N : ℕ) in Filter.atTop, ∀ (A B : Finset ℕ), A ⊆ Finset.Icc 1 N → B ⊆ Finset.Icc 1 N → IsSidon ↑A → IsSidon ↑B → A.card = B.card → (A - A) ∩ (B - B) = {0} → ↑(A.card.choose 2 + B.card.choose 2) ≤ (1 - c + o N) * ↑((f N).choose 2)

If $A$ and $B$ are equal-sized Sidon sets in $\{1,\ldots,N\}$ with $(A-A)\cap(B-B)=\{0\}$, can the bound be improved to $$\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2} \leq (1-c+o(1))\binom{f(N)}{2}$$ for some constant $c>0$?

The answer is no; the Erdős Problems page records a negative answer due to Barreto.