/- 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 FormalConjecturesUtil

Erdős Problem 819

References:

    erdosproblems.com/819

    [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⟩)) := A:Finset ℕ⊢ #(A + A) ≤ #(Finset.image (Sym2.lift ⟨fun a b ↦ a + b, ⋯⟩) A.sym2) A:Finset ℕx:ℕhx:x ∈ A + A⊢ x ∈ Finset.image (Sym2.lift ⟨fun a b ↦ a + b, ⋯⟩) A.sym2 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 All goals completed! 🐙 _ ≤ #A.sym2 := Finset.card_image_le

With $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}$.

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; All goals completed! 🐙 _ ≤ (N + Real.sqrt N) / 2 := 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 All goals completed! 🐙def erdos_819.answer : ℕ → ℝ := sorry

Let $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 := ⊢ (fun N ↦ ↑(f N)) ~[atTop] erdos_819.answer 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 : ℝ) := ⊢ ∀ ε > 0, ∀ᶠ (N : ℕ) in atTop, (3 / 8 - ε) * ↑N ≤ ↑(f N) 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.

ε:ℝhε:ε > 0N:ℕhN:⌈1 / (4 * ε ^ 2)⌉₊ ≤ NhN':1 / (4 * ε ^ 2) ≤ ↑Nh1:1 ≤ 4 * ε ^ 2 * ↑Nhs:√↑N ≤ 2 * ε * ↑N⊢ ↑(f N) ≤ (1 / 2 + ε) * ↑N All goals completed! 🐙end Erdos819