/-
Copyright 2026 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 819
References:
[Er91] Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397-406.
[ErFr91] Erdős, P. and Freud, R., On sums of a Sidon-sequence. J. Number Theory 38 (1991), 196-205.
@[expose] public sectionopen Filter Asymptoticsopen scoped Finset Pointwisenamespace Erdos819
$f(N)$ is the maximum of $\lvert (A + A) \cap [1, N] \rvert$ over all
$A \subseteq {1, \ldots, N}$ with $\lvert A \rvert = \lfloor N^{1/2} \rfloor$, where
$\lfloor N^{1/2} \rfloor$ is Nat.sqrt N. Such sets exist for every $N$, since
$\lfloor N^{1/2} \rfloor \leq N$, so the maximum is over a nonempty family.
def f (N : ℕ) : ℕ :=
(Finset.powersetCard (Nat.sqrt N) (Finset.Icc 1 N)).sup
fun A ↦ #((A + A) ∩ Finset.Icc 1 N)Trivial upper bound: $f(N) \leq N$.
@[category API, AMS 5 11]
theorem f_le (N : ℕ) : f N ≤ N := N:ℕ⊢ f N ≤ N
N:ℕA:Finset ℕx✝:A ∈ Finset.powersetCard N.sqrt (Finset.Icc 1 N)⊢ #((A + A) ∩ Finset.Icc 1 N) ≤ N
calc #((A + A) ∩ Finset.Icc 1 N) ≤ #(Finset.Icc 1 N) :=
Finset.card_le_card Finset.inter_subset_right
_ = N := N:ℕA:Finset ℕx✝:A ∈ Finset.powersetCard N.sqrt (Finset.Icc 1 N)⊢ #(Finset.Icc 1 N) = N All goals completed! 🐙Every sum $a + b$ with $a, b \in A$ comes from an unordered pair ${a, b}$, so $\lvert A + A\rvert \leq \binom{\lvert A\rvert + 1}{2}$.
A:Finset ℕ⊢ #(A + A) ≤ #A.sym2
calc #(A + A) ≤ #(A.sym2.image (Sym2.lift ⟨fun a b ↦ a + b, fun a b ↦ add_comm a b⟩)) := by A:Finset ℕ⊢ #(A + A) ≤ #(Finset.image (Sym2.lift ⟨fun a b ↦ a + b, ⋯⟩) A.sym2)
refine Finset.card_le_card fun x hx ↦ ?_ A:Finset ℕx:ℕhx:x ∈ A + A⊢ x ∈ Finset.image (Sym2.lift ⟨fun a b ↦ a + b, ⋯⟩) A.sym2
obtain ⟨a, ha, b, hb, rfl⟩ := Finset.mem_add.1 hx A:Finset ℕa:ℕha:a ∈ Ab:ℕhb:b ∈ Ahx:a + b ∈ A + A⊢ a + b ∈ Finset.image (Sym2.lift ⟨fun a b ↦ a + b, ⋯⟩) A.sym2
exact Finset.mem_image.2 ⟨s(a, b), Finset.mk_mem_sym2_iff.2 ⟨ha, hb⟩, rfl⟩ All goals completed! 🐙
_ ≤ #A.sym2 := Finset.card_image_leWith $k = \lfloor N^{1/2} \rfloor$, we have $f(N) \leq \binom{k+1}{2} = (k^2 + k)/2$, and $k^2 \leq N$, $k \leq N^{1/2}$.
@[category API, AMS 5 11]
theorem f_le_half_add_sqrt (N : ℕ) : (f N : ℝ) ≤ (N + Real.sqrt N) / 2 := by N:ℕ⊢ ↑(f N) ≤ (↑N + √↑N) / 2
have hf : f N ≤ (Nat.sqrt N + 1).choose 2 := by
refine Finset.sup_le fun A hA ↦ ?_ N:ℕA:Finset ℕhA:A ∈ Finset.powersetCard N.sqrt (Finset.Icc 1 N)⊢ #((A + A) ∩ Finset.Icc 1 N) ≤ (N.sqrt + 1).choose 2 N:ℕhf:f N ≤ (N.sqrt + 1).choose 2⊢ ↑(f N) ≤ (↑N + √↑N) / 2
rw [← (Finset.mem_powersetCard.1 hA).2 N:ℕA:Finset ℕhA:A ∈ Finset.powersetCard N.sqrt (Finset.Icc 1 N)⊢ #((A + A) ∩ Finset.Icc 1 N) ≤ (#A + 1).choose 2 N:ℕA:Finset ℕhA:A ∈ Finset.powersetCard N.sqrt (Finset.Icc 1 N)⊢ #((A + A) ∩ Finset.Icc 1 N) ≤ (#A + 1).choose 2 N:ℕhf:f N ≤ (N.sqrt + 1).choose 2⊢ ↑(f N) ≤ (↑N + √↑N) / 2] N:ℕA:Finset ℕhA:A ∈ Finset.powersetCard N.sqrt (Finset.Icc 1 N)⊢ #((A + A) ∩ Finset.Icc 1 N) ≤ (#A + 1).choose 2 N:ℕhf:f N ≤ (N.sqrt + 1).choose 2⊢ ↑(f N) ≤ (↑N + √↑N) / 2
exact (Finset.card_le_card Finset.inter_subset_left).trans (card_add_self_le A) N:ℕhf:f N ≤ (N.sqrt + 1).choose 2⊢ ↑(f N) ≤ (↑N + √↑N) / 2 N:ℕhf:f N ≤ (N.sqrt + 1).choose 2⊢ ↑(f N) ≤ (↑N + √↑N) / 2
have hsq : ((Nat.sqrt N : ℕ) : ℝ) ^ 2 ≤ N := by exact_mod_cast Nat.sqrt_le' N N:ℕhf:f N ≤ (N.sqrt + 1).choose 2hsq:↑N.sqrt ^ 2 ≤ ↑N⊢ ↑(f N) ≤ (↑N + √↑N) / 2 N:ℕhf:f N ≤ (N.sqrt + 1).choose 2hsq:↑N.sqrt ^ 2 ≤ ↑N⊢ ↑(f N) ≤ (↑N + √↑N) / 2
have hle : ((Nat.sqrt N : ℕ) : ℝ) ≤ Real.sqrt N := Real.nat_sqrt_le_real_sqrt N:ℕhf:f N ≤ (N.sqrt + 1).choose 2hsq:↑N.sqrt ^ 2 ≤ ↑Nhle:↑N.sqrt ≤ √↑N⊢ ↑(f N) ≤ (↑N + √↑N) / 2
calc (f N : ℝ) ≤ ((Nat.sqrt N + 1).choose 2 : ℕ) := by N:ℕhf:f N ≤ (N.sqrt + 1).choose 2hsq:↑N.sqrt ^ 2 ≤ ↑Nhle:↑N.sqrt ≤ √↑N⊢ ↑(f N) ≤ ↑((N.sqrt + 1).choose 2) exact_mod_cast hf All goals completed! 🐙
_ = ((Nat.sqrt N : ℝ) ^ 2 + Nat.sqrt N) / 2 := by N:ℕhf:f N ≤ (N.sqrt + 1).choose 2hsq:↑N.sqrt ^ 2 ≤ ↑Nhle:↑N.sqrt ≤ √↑N⊢ ↑((N.sqrt + 1).choose 2) = (↑N.sqrt ^ 2 + ↑N.sqrt) / 2
rw [Nat.cast_choose_two N:ℕhf:f N ≤ (N.sqrt + 1).choose 2hsq:↑N.sqrt ^ 2 ≤ ↑Nhle:↑N.sqrt ≤ √↑N⊢ ↑(N.sqrt + 1) * (↑(N.sqrt + 1) - 1) / 2 = (↑N.sqrt ^ 2 + ↑N.sqrt) / 2 N:ℕhf:f N ≤ (N.sqrt + 1).choose 2hsq:↑N.sqrt ^ 2 ≤ ↑Nhle:↑N.sqrt ≤ √↑N⊢ ↑(N.sqrt + 1) * (↑(N.sqrt + 1) - 1) / 2 = (↑N.sqrt ^ 2 + ↑N.sqrt) / 2] N:ℕhf:f N ≤ (N.sqrt + 1).choose 2hsq:↑N.sqrt ^ 2 ≤ ↑Nhle:↑N.sqrt ≤ √↑N⊢ ↑(N.sqrt + 1) * (↑(N.sqrt + 1) - 1) / 2 = (↑N.sqrt ^ 2 + ↑N.sqrt) / 2; push_cast N:ℕhf:f N ≤ (N.sqrt + 1).choose 2hsq:↑N.sqrt ^ 2 ≤ ↑Nhle:↑N.sqrt ≤ √↑N⊢ (↑N.sqrt + 1) * (↑N.sqrt + 1 - 1) / 2 = (↑N.sqrt ^ 2 + ↑N.sqrt) / 2; ring All goals completed! 🐙
_ ≤ (N + Real.sqrt N) / 2 := by N:ℕhf:f N ≤ (N.sqrt + 1).choose 2hsq:↑N.sqrt ^ 2 ≤ ↑Nhle:↑N.sqrt ≤ √↑N⊢ (↑N.sqrt ^ 2 + ↑N.sqrt) / 2 ≤ (↑N + √↑N) / 2 linarith All goals completed! 🐙def erdos_819.answer : ℕ → ℝ := sorryLet $f(N)$ be maximal such that there exists $A\subseteq {1,\ldots,N}$ with $\lvert A\rvert=\lfloor N^{1/2}\rfloor$ such that $\lvert (A+A)\cap [1,N]\rvert=f(N)$. Estimate $f(N)$.
@[category research open, question value, AMS 5 11]
theorem erdos_819 : (fun N ↦ (f N : ℝ)) ~[atTop] erdos_819.answer := by ⊢ (fun N ↦ ↑(f N)) ~[atTop] erdos_819.answer
sorry All goals completed! 🐙Erdős and Freud [ErFr91] proved $$\left(\frac{3}{8}-o(1)\right)N \leq f(N) \leq \left(\frac{1}{2}+o(1)\right)N.$$
This is the lower bound.
@[category research solved, AMS 5 11]
theorem erdos_819.variants.erdos_freud_lower :
∀ ε > (0 : ℝ), ∀ᶠ N : ℕ in atTop, (3 / 8 - ε) * N ≤ (f N : ℝ) := by ⊢ ∀ ε > 0, ∀ᶠ (N : ℕ) in atTop, (3 / 8 - ε) * ↑N ≤ ↑(f N)
sorry All goals completed! 🐙Erdős and Freud [ErFr91] proved $$\left(\frac{3}{8}-o(1)\right)N \leq f(N) \leq \left(\frac{1}{2}+o(1)\right)N.$$
This is the upper bound.
@[category research solved, AMS 5 11]
theorem erdos_819.variants.erdos_freud_upper :
∀ ε > (0 : ℝ), ∀ᶠ N : ℕ in atTop, (f N : ℝ) ≤ (1 / 2 + ε) * N := by ⊢ ∀ ε > 0, ∀ᶠ (N : ℕ) in atTop, ↑(f N) ≤ (1 / 2 + ε) * ↑N
intro ε hε ε:ℝhε:ε > 0⊢ ∀ᶠ (N : ℕ) in atTop, ↑(f N) ≤ (1 / 2 + ε) * ↑N
filter_upwards [eventually_ge_atTop ⌈1 / (4 * ε ^ 2)⌉₊] with N hN ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N
have hN' : 1 / (4 * ε ^ 2) ≤ (N : ℝ) := (Nat.le_ceil _).trans (by ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ N⊢ ↑⌈1 / (4 * ε ^ 2)⌉₊ ≤ ↑N ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N exact_mod_cast hN All goals completed! 🐙 ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N) ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N
have h1 : 1 ≤ 4 * ε ^ 2 * N := by ⊢ ∀ ε > 0, ∀ᶠ (N : ℕ) in atTop, ↑(f N) ≤ (1 / 2 + ε) * ↑N ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N
rw [div_le_iff₀ (by ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑N⊢ 0 < 4 * ε ^ 2 ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 ≤ ↑N * (4 * ε ^ 2)⊢ 1 ≤ 4 * ε ^ 2 * ↑N ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N positivity All goals completed! 🐙 ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 ≤ ↑N * (4 * ε ^ 2)⊢ 1 ≤ 4 * ε ^ 2 * ↑N ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N)] at hN' ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 ≤ ↑N * (4 * ε ^ 2)⊢ 1 ≤ 4 * ε ^ 2 * ↑N ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N
linarith ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N
-- $\sqrt{N} \leq 2\varepsilon N$, since $N \leq (2\varepsilon N)^2$ once $4\varepsilon^2 N \geq 1$.
have hs : Real.sqrt N ≤ 2 * ε * N := by ⊢ ∀ ε > 0, ∀ᶠ (N : ℕ) in atTop, ↑(f N) ≤ (1 / 2 + ε) * ↑N ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑Nhs:√↑N ≤ 2 * ε * ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N
rw [Real.sqrt_le_left (by ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑N⊢ 0 ≤ 2 * ε * ↑N ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑N⊢ ↑N ≤ (2 * ε * ↑N) ^ 2 ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑Nhs:√↑N ≤ 2 * ε * ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N positivity All goals completed! 🐙 ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑N⊢ ↑N ≤ (2 * ε * ↑N) ^ 2 ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑Nhs:√↑N ≤ 2 * ε * ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N)] ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑N⊢ ↑N ≤ (2 * ε * ↑N) ^ 2 ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑Nhs:√↑N ≤ 2 * ε * ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N
nlinarith [(Nat.cast_nonneg N : (0 : ℝ) ≤ N)] ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑Nhs:√↑N ≤ 2 * ε * ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑Nhs:√↑N ≤ 2 * ε * ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N
linarith [f_le_half_add_sqrt N] All goals completed! 🐙end Erdos819