/- Copyright 2025 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Erdős Problem 30

References:

    erdosproblems.com/30

    [ErTu41] Erdős, P. and Turán, P., On a problem of Sidon in additive number theory, and on some related problems. J. London Math. Soc. 16 (1941), 212-215.

    [Li69] Lindström, B., An inequality for $B_2$-sequences. J. Combinatorial Theory 6 (1969), 211-212.

    [Si38] Singer, J., A theorem in finite projective geometry and some applications to number theory. Trans. Amer. Math. Soc. 43 (1938), 377-385.

    [BFR23] Balogh, J., Füredi, Z. and Roy, S., An upper bound on the size of Sidon sets. Amer. Math. Monthly 130 (2023), 437-445.

    [OB22] O'Bryant, K., On the size of finite Sidon sets. arXiv:2207.07800 (2022).

    [CHO25] Carter, D., Hunter, Z. and O'Bryant, K., On the diameter of finite Sidon sets. Acta Math. Hungar. 175 (2025), 108-126.

See also Ben Green's Open Problem 31 (formalised in FormalConjectures/GreensOpenProblems/31.lean).

@[expose] public sectionnamespace Erdos30

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

noncomputable abbrev h (N : ℕ) : ℕ := Finset.maxSidonSubsetCard (Finset.Icc 1 N)open Filteropen scoped Asymptotics Pointwise

Is it true that, for every $\varepsilon > 0$, $h(N) = \sqrt N + O_{\varepsilon}(N^\varepsilon)$

@[category research open, question, AMS 11] theorem erdos_30 : ∀ᵉ (ε > 0), (fun N => h N - (N : Real).sqrt) =O[atTop] fun N => (N : ℝ)^(ε : ℝ) := ⊢ ∀ ε > 0, (fun N ↦ ↑(h N) - √↑N) =O[atTop] fun N ↦ ↑N ^ ε All goals completed! 🐙

A stronger conjecture: is it true that $h(N) = \sqrt N + O(1)$? Erdős thought this was perhaps too optimistic.

@[category research open, question, AMS 11] theorem erdos_30.variants.O_one : (fun N => h N - (N : ℝ).sqrt) =O[atTop] fun _ => (1 : ℝ) := ⊢ (fun N ↦ ↑(h N) - √↑N) =O[atTop] fun x ↦ 1 All goals completed! 🐙

Erdős and Turán [ErTu41] proved $h(N) \le \sqrt N + O(N^{1/4})$.

This is an upper bound only. A statement with =O would also assert the lower bound $h(N) \ge \sqrt N - O(N^{1/4})$, which is not part of this result.

@[category research solved, AMS 11] theorem erdos_30.variants.erdos_turan : ∃ C : ℝ, ∀ᶠ N in atTop, (h N : ℝ) ≤ (N : ℝ).sqrt + C * (N : ℝ) ^ (4⁻¹ : ℝ) := ⊢ ∃ C, ∀ᶠ (N : ℕ) in atTop, ↑(h N) ≤ √↑N + C * ↑N ^ 4⁻¹ All goals completed! 🐙

The proofs of Erdős–Turán [ErTu41] and Lindström [Li69] in fact give, for all $N$, $h(N) \le N^{1/2} + N^{1/4} + 1$.

@[category research solved, AMS 11] theorem erdos_30.variants.lindstrom (N : ℕ) : (h N : ℝ) ≤ (N : ℝ).sqrt + (N : ℝ) ^ (4⁻¹ : ℝ) + 1 := N:ℕ⊢ ↑(h N) ≤ √↑N + ↑N ^ 4⁻¹ + 1 All goals completed! 🐙

Balogh, Füredi and Roy [BFR23] proved $h(N) \le N^{1/2} + 0.998 N^{1/4}$ for all sufficiently large $N$.

@[category research solved, AMS 11] theorem erdos_30.variants.balogh_furedi_roy : ∀ᶠ N in atTop, (h N : ℝ) ≤ (N : ℝ).sqrt + (0.998 : ℝ) * (N : ℝ) ^ (4⁻¹ : ℝ) := ⊢ ∀ᶠ (N : ℕ) in atTop, ↑(h N) ≤ √↑N + 0.998 * ↑N ^ 4⁻¹ All goals completed! 🐙

O'Bryant [OB22] proved $h(N) \le N^{1/2} + 0.99703 N^{1/4}$ for all sufficiently large $N$.

@[category research solved, AMS 11] theorem erdos_30.variants.obryant : ∀ᶠ N in atTop, (h N : ℝ) ≤ (N : ℝ).sqrt + (0.99703 : ℝ) * (N : ℝ) ^ (4⁻¹ : ℝ) := ⊢ ∀ᶠ (N : ℕ) in atTop, ↑(h N) ≤ √↑N + 0.99703 * ↑N ^ 4⁻¹ All goals completed! 🐙

Carter, Hunter and O'Bryant [CHO25] proved $h(N) \le N^{1/2} + 0.98183 N^{1/4} + O(1)$. This is the current record upper bound.

@[category research solved, AMS 11] theorem erdos_30.variants.carter_hunter_obryant : ∃ C : ℝ, ∀ᶠ N in atTop, (h N : ℝ) ≤ (N : ℝ).sqrt + (0.98183 : ℝ) * (N : ℝ) ^ (4⁻¹ : ℝ) + C := ⊢ ∃ C, ∀ᶠ (N : ℕ) in atTop, ↑(h N) ≤ √↑N + 0.98183 * ↑N ^ 4⁻¹ + C All goals completed! 🐙

Singer's construction [Si38] shows $h(N) \ge (1 - o(1)) N^{1/2}$ for all $N$.

@[category research solved, AMS 11] theorem erdos_30.variants.singer : ∀ ε > (0 : ℝ), ∀ᶠ N : ℕ in atTop, (1 - ε) * (N : ℝ).sqrt ≤ h N := ⊢ ∀ ε > 0, ∀ᶠ (N : ℕ) in atTop, (1 - ε) * √↑N ≤ ↑(h N) All goals completed! 🐙

Combining Singer's lower bound [Si38] with the Erdős–Turán upper bound [ErTu41]: $h(N) \sim N^{1/2}$.

@[category research solved, AMS 11] theorem erdos_30.variants.isEquivalent_sqrt : (fun N => (h N : ℝ)) ~[atTop] fun N => (N : ℝ).sqrt := ⊢ (fun N ↦ ↑(h N)) ~[atTop] fun N ↦ √↑N All goals completed! 🐙

The counting argument of Erdős and Turán [ErTu41]: a Sidon set $A \subseteq {0, \dots, N}$ has $|A|(|A| - 1) \le 2N$, because the $|A|(|A|-1)/2$ positive differences of $A$ are distinct and lie in ${1, \dots, N}$.

A:Finset ℕN:ℕhS:IsSidon ↑AhA:A ⊆ Finset.range (N + 1)h_inj:Set.InjOn (fun p ↦ p.1 - p.2) ↑({p ∈ A ×ˢ A | p.2 < p.1})h_sub:Finset.image (fun p ↦ p.1 - p.2) ({p ∈ A ×ˢ A | p.2 < p.1}) ⊆ Finset.Icc 1 Nthis:{p ∈ A ×ˢ A | p.2 < p.1}.card ≤ N + 1 - 1⊢ A.card * (A.card - 1) ≤ 2 * N A:Finset ℕN:ℕhS:IsSidon ↑AhA:A ⊆ Finset.range (N + 1)h_inj:Set.InjOn (fun p ↦ p.1 - p.2) ↑({p ∈ A ×ˢ A | p.2 < p.1})h_sub:Finset.image (fun p ↦ p.1 - p.2) ({p ∈ A ×ˢ A | p.2 < p.1}) ⊆ Finset.Icc 1 Nthis✝:{p ∈ A ×ˢ A | p.2 < p.1}.card ≤ N + 1 - 1this:2 * {p ∈ A ×ˢ A | p.2 < p.1}.card = A.card * (A.card - 1)⊢ A.card * (A.card - 1) ≤ 2 * N All goals completed! 🐙

For a Sidon set $A$, $|A + A| = |A|(|A|+1)/2$: the sums $a + b$ with $a \le b$ are pairwise distinct [ErTu41].

A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂hAA:A + A = Finset.image (fun p ↦ p.1 + p.2) ({p ∈ A ×ˢ A | p.1 ≤ p.2})h_inj:Set.InjOn (fun p ↦ p.1 + p.2) ↑({p ∈ A ×ˢ A | p.1 ≤ p.2})h_split:{p ∈ A ×ˢ A | p.1 ≤ p.2} = {p ∈ A ×ˢ A | p.1 < p.2} ∪ A.diagh_disj:Disjoint ({p ∈ A ×ˢ A | p.1 < p.2}) A.diagh_tri:2 * {p ∈ A ×ˢ A | p.1 < p.2}.card = A.card * A.card - A.cardh_le:A.card ≤ A.card * A.card⊢ {p ∈ A ×ˢ A | p.1 < p.2}.card + A.card = (A.card * A.card + A.card) / 2 All goals completed! 🐙

If $A \subseteq {0, \dots, N}$ then $A + A \subseteq {0, \dots, 2N}$.

@[category textbook, AMS 11] theorem erdos_30.variants.distinct_sums_in_range (A : Finset ℕ) (N : ℕ) (hA : A ⊆ Finset.range (N + 1)) : A + A ⊆ Finset.range (2 * N + 1) := A:Finset ℕN:ℕhA:A ⊆ Finset.range (N + 1)⊢ A + A ⊆ Finset.range (2 * N + 1) grw [A:Finset ℕN:ℕhA:A ⊆ Finset.range (N + 1)⊢ Finset.range (N + 1) + Finset.range (N + 1) ⊆ Finset.range (2 * N + 1) A:Finset ℕN:ℕhA:A ⊆ Finset.range (N + 1)⊢ Finset.range (N + N + 1) ⊆ Finset.range (2 * N + 1)A:Finset ℕN:ℕhA:A ⊆ Finset.range (N + 1)⊢ Finset.range (N + N + 1) ⊆ Finset.range (2 * N + 1) All goals completed! 🐙

The counting bound of Erdős and Turán [ErTu41] in its sum form: a Sidon set $A \subseteq {0, \dots, N}$ has $|A|(|A| + 1)/2 \le 2N + 1$.

A:Finset ℕN:ℕhS:IsSidon ↑AhA:A ⊆ Finset.range (N + 1)⊢ (A + A).card ≤ 2 * N + 1 All goals completed! 🐙

A weak form of Lindström's bound [Li69], following from erdos_30.variants.elementary_difference_count: a Sidon set $A \subseteq {0, \dots, N}$ has $|A| \le \lfloor \sqrt{2N} \rfloor + 1$.

@[category textbook, AMS 11] theorem erdos_30.variants.lindstrom_weak (A : Finset ℕ) (N : ℕ) (hS : IsSidon (A : Set ℕ)) (hA : A ⊆ Finset.range (N + 1)) : A.card ≤ Nat.sqrt (2 * N) + 1 := A:Finset ℕN:ℕhS:IsSidon ↑AhA:A ⊆ Finset.range (N + 1)⊢ A.card ≤ (2 * N).sqrt + 1 A:Finset ℕN:ℕhS:IsSidon ↑AhA:A ⊆ Finset.range (N + 1)h:A.card * (A.card - 1) ≤ 2 * N⊢ A.card ≤ (2 * N).sqrt + 1 A:Finset ℕN:ℕhS:IsSidon ↑AhA:A ⊆ Finset.range (N + 1)h:A.card * (A.card - 1) ≤ 2 * Nthis:(A.card - 1) * (A.card - 1) ≤ 2 * N⊢ A.card ≤ (2 * N).sqrt + 1 A:Finset ℕN:ℕhS:IsSidon ↑AhA:A ⊆ Finset.range (N + 1)h:A.card * (A.card - 1) ≤ 2 * Nthis✝:(A.card - 1) * (A.card - 1) ≤ 2 * Nthis:A.card - 1 ≤ (2 * N).sqrt⊢ A.card ≤ (2 * N).sqrt + 1 All goals completed! 🐙end Erdos30