/-
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 FormalConjecturesUtilErdős Problem 30
References:
[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 Erdos30Let $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 PointwiseIs 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
have := Finset.two_mul_card_product_filter_gt A 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
lia 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].
@[category textbook, AMS 11]
theorem erdos_30.variants.distinct_sums_card (A : Finset ℕ) (hS : IsSidon (A : Set ℕ)) :
(A + A).card = A.card * (A.card + 1) / 2 := by A:Finset ℕhS:IsSidon ↑A⊢ (A + A).card = A.card * (A.card + 1) / 2
rw [Set.isSidon_iff_le A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂⊢ (A + A).card = A.card * (A.card + 1) / 2 A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂⊢ (A + A).card = A.card * (A.card + 1) / 2] at hS A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂⊢ (A + A).card = A.card * (A.card + 1) / 2
have hAA : A + A = {p ∈ A ×ˢ A | p.1 ≤ p.2}.image (fun p ↦ p.1 + p.2) := by
ext x A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂x:ℕ⊢ x ∈ A + A ↔ x ∈ Finset.image (fun p ↦ p.1 + p.2) ({p ∈ A ×ˢ A | p.1 ≤ p.2}) 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})⊢ (A + A).card = A.card * (A.card + 1) / 2
simp only [Finset.mem_add, Finset.mem_image, Finset.mem_filter, Finset.mem_product, Prod.exists] A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂x:ℕ⊢ (∃ y ∈ A, ∃ z ∈ A, y + z = x) ↔ ∃ a b, ((a ∈ A ∧ b ∈ A) ∧ a ≤ b) ∧ a + b = x 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})⊢ (A + A).card = A.card * (A.card + 1) / 2
constructor mp A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂x:ℕ⊢ (∃ y ∈ A, ∃ z ∈ A, y + z = x) → ∃ a b, ((a ∈ A ∧ b ∈ A) ∧ a ≤ b) ∧ a + b = xmpr A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂x:ℕ⊢ (∃ a b, ((a ∈ A ∧ b ∈ A) ∧ a ≤ b) ∧ a + b = x) → ∃ y ∈ A, ∃ z ∈ A, y + z = x 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})⊢ (A + A).card = A.card * (A.card + 1) / 2
· mp A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂x:ℕ⊢ (∃ y ∈ A, ∃ z ∈ A, y + z = x) → ∃ a b, ((a ∈ A ∧ b ∈ A) ∧ a ≤ b) ∧ a + b = x 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})⊢ (A + A).card = A.card * (A.card + 1) / 2 rintro ⟨a, ha, b, hb, rfl⟩ mp A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂a:ℕha:a ∈ Ab:ℕhb:b ∈ A⊢ ∃ a_1 b_1, ((a_1 ∈ A ∧ b_1 ∈ A) ∧ a_1 ≤ b_1) ∧ a_1 + b_1 = a + b 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})⊢ (A + A).card = A.card * (A.card + 1) / 2
rcases le_total a b with hab | hba mp.inl A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂a:ℕha:a ∈ Ab:ℕhb:b ∈ Ahab:a ≤ b⊢ ∃ a_1 b_1, ((a_1 ∈ A ∧ b_1 ∈ A) ∧ a_1 ≤ b_1) ∧ a_1 + b_1 = a + bmp.inr A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂a:ℕha:a ∈ Ab:ℕhb:b ∈ Ahba:b ≤ a⊢ ∃ a_1 b_1, ((a_1 ∈ A ∧ b_1 ∈ A) ∧ a_1 ≤ b_1) ∧ a_1 + b_1 = a + b 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})⊢ (A + A).card = A.card * (A.card + 1) / 2
· mp.inl A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂a:ℕha:a ∈ Ab:ℕhb:b ∈ Ahab:a ≤ b⊢ ∃ a_1 b_1, ((a_1 ∈ A ∧ b_1 ∈ A) ∧ a_1 ≤ b_1) ∧ a_1 + b_1 = a + b 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})⊢ (A + A).card = A.card * (A.card + 1) / 2 exact ⟨a, b, ⟨⟨ha, hb⟩, hab⟩, rfl⟩ All goals completed! 🐙 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})⊢ (A + A).card = A.card * (A.card + 1) / 2
· mp.inr A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂a:ℕha:a ∈ Ab:ℕhb:b ∈ Ahba:b ≤ a⊢ ∃ a_1 b_1, ((a_1 ∈ A ∧ b_1 ∈ A) ∧ a_1 ≤ b_1) ∧ a_1 + b_1 = a + b 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})⊢ (A + A).card = A.card * (A.card + 1) / 2 exact ⟨b, a, ⟨⟨hb, ha⟩, hba⟩, add_comm b a⟩ All goals completed! 🐙 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})⊢ (A + A).card = A.card * (A.card + 1) / 2
· mpr A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂x:ℕ⊢ (∃ a b, ((a ∈ A ∧ b ∈ A) ∧ a ≤ b) ∧ a + b = x) → ∃ y ∈ A, ∃ z ∈ A, y + z = x 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})⊢ (A + A).card = A.card * (A.card + 1) / 2 rintro ⟨a, b, ⟨⟨ha, hb⟩, _⟩, rfl⟩ mpr A:Finset ℕhS:∀ a₁ ∈ ↑A, ∀ b₁ ∈ ↑A, ∀ a₂ ∈ ↑A, ∀ b₂ ∈ ↑A, a₁ ≤ b₁ → a₂ ≤ b₂ → a₁ + b₁ = a₂ + b₂ → a₁ = a₂ ∧ b₁ = b₂a:ℕb:ℕright✝:a ≤ bha:a ∈ Ahb:b ∈ A⊢ ∃ y ∈ A, ∃ z ∈ A, y + z = a + b 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})⊢ (A + A).card = A.card * (A.card + 1) / 2
exact ⟨a, ha, b, hb, rfl⟩ 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})⊢ (A + A).card = A.card * (A.card + 1) / 2 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})⊢ (A + A).card = A.card * (A.card + 1) / 2
have h_inj : Set.InjOn (fun p : ℕ × ℕ ↦ p.1 + p.2)
(({p ∈ A ×ˢ A | p.1 ≤ p.2} : Finset (ℕ × ℕ)) : Set (ℕ × ℕ)) := by
intro ⟨a₁, b₁⟩ h₁ ⟨a₂, b₂⟩ h₂ heq 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})a₁:ℕb₁:ℕh₁:(a₁, b₁) ∈ ↑({p ∈ A ×ˢ A | p.1 ≤ p.2})a₂:ℕb₂:ℕh₂:(a₂, b₂) ∈ ↑({p ∈ A ×ˢ A | p.1 ≤ p.2})heq:(fun p ↦ p.1 + p.2) (a₁, b₁) = (fun p ↦ p.1 + p.2) (a₂, b₂)⊢ (a₁, b₁) = (a₂, b₂) 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})⊢ (A + A).card = A.card * (A.card + 1) / 2
simp only [Finset.mem_coe, Finset.mem_filter, Finset.mem_product] at h₁ h₂ 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})a₁:ℕb₁:ℕa₂:ℕb₂:ℕheq:(fun p ↦ p.1 + p.2) (a₁, b₁) = (fun p ↦ p.1 + p.2) (a₂, b₂)h₁:(a₁ ∈ A ∧ b₁ ∈ A) ∧ a₁ ≤ b₁h₂:(a₂ ∈ A ∧ b₂ ∈ A) ∧ a₂ ≤ b₂⊢ (a₁, b₁) = (a₂, b₂) 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})⊢ (A + A).card = A.card * (A.card + 1) / 2
have := hS a₁ h₁.1.1 b₁ h₁.1.2 a₂ h₂.1.1 b₂ h₂.1.2 h₁.2 h₂.2 heq 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})a₁:ℕb₁:ℕa₂:ℕb₂:ℕheq:(fun p ↦ p.1 + p.2) (a₁, b₁) = (fun p ↦ p.1 + p.2) (a₂, b₂)h₁:(a₁ ∈ A ∧ b₁ ∈ A) ∧ a₁ ≤ b₁h₂:(a₂ ∈ A ∧ b₂ ∈ A) ∧ a₂ ≤ b₂this:a₁ = a₂ ∧ b₁ = b₂⊢ (a₁, b₁) = (a₂, b₂) 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})⊢ (A + A).card = A.card * (A.card + 1) / 2
exact Prod.ext this.1 this.2 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})⊢ (A + A).card = A.card * (A.card + 1) / 2 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})⊢ (A + A).card = A.card * (A.card + 1) / 2
have h_split : {p ∈ A ×ˢ A | p.1 ≤ p.2} = {p ∈ A ×ˢ A | p.1 < p.2} ∪ A.diag := by
rw [Finset.diag_eq_filter 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})⊢ {p ∈ A ×ˢ A | p.1 ≤ p.2} = {p ∈ A ×ˢ A | p.1 < p.2} ∪ {a ∈ A ×ˢ A | a.1 = a.2} 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})⊢ {p ∈ A ×ˢ A | p.1 ≤ p.2} = {p ∈ A ×ˢ A | p.1 < p.2} ∪ {a ∈ A ×ˢ A | a.1 = a.2} 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.diag⊢ (A + A).card = A.card * (A.card + 1) / 2] 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})⊢ {p ∈ A ×ˢ A | p.1 ≤ p.2} = {p ∈ A ×ˢ A | p.1 < p.2} ∪ {a ∈ A ×ˢ A | a.1 = a.2} 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.diag⊢ (A + A).card = A.card * (A.card + 1) / 2
simp [le_iff_lt_or_eq, Finset.filter_or] 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.diag⊢ (A + A).card = A.card * (A.card + 1) / 2 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.diag⊢ (A + A).card = A.card * (A.card + 1) / 2
have h_disj : Disjoint {p ∈ A ×ˢ A | p.1 < p.2} A.diag := by
rw [Finset.diag_eq_filter 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.diag⊢ Disjoint ({p ∈ A ×ˢ A | p.1 < p.2}) ({a ∈ A ×ˢ A | a.1 = a.2}) 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.diag⊢ Disjoint ({p ∈ A ×ˢ A | p.1 < p.2}) ({a ∈ A ×ˢ A | a.1 = a.2}) 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.diag⊢ (A + A).card = A.card * (A.card + 1) / 2] 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.diag⊢ Disjoint ({p ∈ A ×ˢ A | p.1 < p.2}) ({a ∈ A ×ˢ A | a.1 = a.2}) 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.diag⊢ (A + A).card = A.card * (A.card + 1) / 2
exact Finset.disjoint_filter.2 fun _ _ h₁ h₂ ↦ absurd h₂ h₁.ne 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.diag⊢ (A + A).card = A.card * (A.card + 1) / 2 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.diag⊢ (A + A).card = A.card * (A.card + 1) / 2
have h_tri := Finset.two_mul_card_product_filter_lt A 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 - 1)⊢ (A + A).card = A.card * (A.card + 1) / 2
have h_le : A.card ≤ A.card * A.card := Nat.le_mul_self _ 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 - 1)h_le:A.card ≤ A.card * A.card⊢ (A + A).card = A.card * (A.card + 1) / 2
rw [Nat.mul_sub_one 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⊢ (A + A).card = A.card * (A.card + 1) / 2 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⊢ (A + A).card = A.card * (A.card + 1) / 2] at h_tri 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⊢ (A + A).card = A.card * (A.card + 1) / 2
rw [hAA, 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⊢ (Finset.image (fun p ↦ p.1 + p.2) ({p ∈ A ×ˢ A | p.1 ≤ p.2})).card = A.card * (A.card + 1) / 2 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 Finset.card_image_of_injOn h_inj, 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 + 1) / 2 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 h_split, 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} ∪ A.diag).card = A.card * (A.card + 1) / 2 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 Finset.card_union_of_disjoint h_disj, 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.diag.card = A.card * (A.card + 1) / 2 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
Finset.diag_card, 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 + 1) / 2 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 mul_add_one 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 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] 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
lia 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) := by A:Finset ℕN:ℕhA:A ⊆ Finset.range (N + 1)⊢ A + A ⊆ Finset.range (2 * N + 1)
grw [hA, A:Finset ℕN:ℕhA:A ⊆ Finset.range (N + 1)⊢ Finset.range (N + 1) + Finset.range (N + 1) ⊆ Finset.range (2 * N + 1) Finset.range_add_range 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)
simp [two_mul] 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$.
@[category textbook, AMS 11]
theorem erdos_30.variants.erdos_turan_counting (A : Finset ℕ) (N : ℕ)
(hS : IsSidon (A : Set ℕ)) (hA : A ⊆ Finset.range (N + 1)) :
A.card * (A.card + 1) / 2 ≤ 2 * N + 1 := by A:Finset ℕN:ℕhS:IsSidon ↑AhA:A ⊆ Finset.range (N + 1)⊢ A.card * (A.card + 1) / 2 ≤ 2 * N + 1
rw [← erdos_30.variants.distinct_sums_card A hS A:Finset ℕN:ℕhS:IsSidon ↑AhA:A ⊆ Finset.range (N + 1)⊢ (A + A).card ≤ 2 * N + 1 A:Finset ℕN:ℕhS:IsSidon ↑AhA:A ⊆ Finset.range (N + 1)⊢ (A + A).card ≤ 2 * N + 1] A:Finset ℕN:ℕhS:IsSidon ↑AhA:A ⊆ Finset.range (N + 1)⊢ (A + A).card ≤ 2 * N + 1
simpa using Finset.card_le_card (erdos_30.variants.distinct_sums_in_range A N hA) 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 := by A:Finset ℕN:ℕhS:IsSidon ↑AhA:A ⊆ Finset.range (N + 1)⊢ A.card ≤ (2 * N).sqrt + 1
have h := erdos_30.variants.elementary_difference_count A N hS hA 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
have : (A.card - 1) * (A.card - 1) ≤ 2 * N := (Nat.mul_le_mul_right _ (Nat.sub_le _ _)).trans h 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
have := Nat.le_sqrt.mpr this 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
lia All goals completed! 🐙end Erdos30