/-
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 1193
References:
[Er80] Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115.
@[expose] public sectionopen AdditiveCombinatorics Setnamespace Erdos1193Let $A\subset \mathbb{N}$ and let $g(n)$ be a non-decreasing function of $n$ which is always $>0$.
Is the lower density of $${ n : 1_A\ast 1_A(n)=g(n)}$$ always $0$?
The answer is trivially no to both questions: indeed if $A=\mathbb{N}$ (assuming $0\in\mathbb{N}$) then $1_A\ast 1_A(n)=n+1$ for all $n$. Presumably Erdős had some additional restrictions on either $g$ or $A$ in mind, but these are not recorded in [Er80].
hset:{n | sumRep univ n = n + 1} = univh:∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.lowerDensity = 0this:1 = 0⊢ False
norm_num at this All goals completed! 🐙Let $A\subset \mathbb{N}$ and let $g(n)$ be a non-decreasing function of $n$ which is always $>0$.
Is the upper density of $${ n : 1_A\ast 1_A(n)=g(n)}$$ always $<c$ for some constant $c<1$?
The answer is trivially no to both questions: indeed if $A=\mathbb{N}$ (assuming $0\in\mathbb{N}$) then $1_A\ast 1_A(n)=n+1$ for all $n$. Presumably Erdős had some additional restrictions on either $g$ or $A$ in mind, but these are not recorded in [Er80].
@[category research solved, question, AMS 5 11]
theorem erdos_1193.parts.ii :
¬ ∃ c < (1 : ℝ), ∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ n, 0 < g n) →
{n : ℕ | sumRep A n = g n}.upperDensity < c := by ⊢ ¬∃ c < 1, ∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.upperDensity < c
have hset : {n : ℕ | sumRep Set.univ n = n + 1} = Set.univ := by ext n n:ℕ⊢ n ∈ {n | sumRep univ n = n + 1} ↔ n ∈ univ hset:{n | sumRep univ n = n + 1} = univ⊢ ¬∃ c < 1, ∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.upperDensity < c; simp [sumRep_def] hset:{n | sumRep univ n = n + 1} = univ⊢ ¬∃ c < 1, ∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.upperDensity < c hset:{n | sumRep univ n = n + 1} = univ⊢ ¬∃ c < 1, ∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.upperDensity < c
rintro ⟨c, hc, h⟩ hset:{n | sumRep univ n = n + 1} = univc:ℝhc:c < 1h:∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.upperDensity < c⊢ False
have := h Set.univ (fun n => n + 1) (fun _ _ h => by hset:{n | sumRep univ n = n + 1} = univc:ℝhc:c < 1h✝:∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.upperDensity < cx✝¹:ℕx✝:ℕh:x✝¹ ≤ x✝⊢ (fun n ↦ n + 1) x✝¹ ≤ (fun n ↦ n + 1) x✝ hset:{n | sumRep univ n = n + 1} = univc:ℝhc:c < 1h:∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.upperDensity < cthis:{n | sumRep univ n = n + 1}.upperDensity < c⊢ False simpa using h All goals completed! 🐙 hset:{n | sumRep univ n = n + 1} = univc:ℝhc:c < 1h:∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.upperDensity < cthis:{n | sumRep univ n = n + 1}.upperDensity < c⊢ False) (fun n => Nat.succ_pos n) hset:{n | sumRep univ n = n + 1} = univc:ℝhc:c < 1h:∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.upperDensity < cthis:{n | sumRep univ n = n + 1}.upperDensity < c⊢ False
rw [hset, hset:{n | sumRep univ n = n + 1} = univc:ℝhc:c < 1h:∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.upperDensity < cthis:univ.upperDensity < c⊢ False hset:{n | sumRep univ n = n + 1} = univc:ℝhc:c < 1h:∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.upperDensity < cthis:1 < c⊢ False show (Set.univ : Set ℕ).upperDensity = 1 from
Filter.Tendsto.limsup_eq HasDensity.univ_nat_hasDensity_one hset:{n | sumRep univ n = n + 1} = univc:ℝhc:c < 1h:∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.upperDensity < cthis:1 < c⊢ False hset:{n | sumRep univ n = n + 1} = univc:ℝhc:c < 1h:∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.upperDensity < cthis:1 < c⊢ False] at this hset:{n | sumRep univ n = n + 1} = univc:ℝhc:c < 1h:∀ (A : Set ℕ) (g : ℕ → ℕ), Monotone g → (∀ (n : ℕ), 0 < g n) → {n | sumRep A n = g n}.upperDensity < cthis:1 < c⊢ False
linarith All goals completed! 🐙set_option linter.style.formal_proof_palomar false inIndeed if $A=\mathbb{N}$ (assuming $0\in\mathbb{N}$) then $1_A\ast 1_A(n)=n+1$ for all $n$.
@[category research solved, AMS 5 11, formal_proof using lean4 at "https://github.com/plby/lean-proofs/blob/main/src/v4.29.1/ErdosProblems/Erdos1193.lean"]
theorem erdos_1193.variants.sumRep_univ (n : ℕ) : sumRep (Set.univ : Set ℕ) n = n + 1 := by n:ℕ⊢ sumRep univ n = n + 1
sorry All goals completed! 🐙Erdős writes the upper density can be positive, but he believes it is bounded away from $1$.
@[category research solved, AMS 5 11]
theorem erdos_1193.variants.upper_density_pos :
∃ (A : Set ℕ) (g : ℕ → ℕ), Monotone g ∧ (∀ n, 0 < g n) ∧
0 < {n : ℕ | sumRep A n = g n}.upperDensity := by ⊢ ∃ A g, Monotone g ∧ (∀ (n : ℕ), 0 < g n) ∧ 0 < {n | sumRep A n = g n}.upperDensity
have hset : {n : ℕ | sumRep Set.univ n = n + 1} = Set.univ := by ext n n:ℕ⊢ n ∈ {n | sumRep univ n = n + 1} ↔ n ∈ univ hset:{n | sumRep univ n = n + 1} = univ⊢ ∃ A g, Monotone g ∧ (∀ (n : ℕ), 0 < g n) ∧ 0 < {n | sumRep A n = g n}.upperDensity; simp [sumRep_def] hset:{n | sumRep univ n = n + 1} = univ⊢ ∃ A g, Monotone g ∧ (∀ (n : ℕ), 0 < g n) ∧ 0 < {n | sumRep A n = g n}.upperDensity hset:{n | sumRep univ n = n + 1} = univ⊢ ∃ A g, Monotone g ∧ (∀ (n : ℕ), 0 < g n) ∧ 0 < {n | sumRep A n = g n}.upperDensity
refine ⟨Set.univ, fun n => n + 1, fun _ _ h => by hset:{n | sumRep univ n = n + 1} = univx✝¹:ℕx✝:ℕh:x✝¹ ≤ x✝⊢ (fun n ↦ n + 1) x✝¹ ≤ (fun n ↦ n + 1) x✝ simpa using h All goals completed! 🐙, fun n => Nat.succ_pos n, ?_⟩
rw [hset, hset:{n | sumRep univ n = n + 1} = univ⊢ 0 < univ.upperDensity hset:{n | sumRep univ n = n + 1} = univ⊢ 0 < 1 show (Set.univ : Set ℕ).upperDensity = 1 from
Filter.Tendsto.limsup_eq HasDensity.univ_nat_hasDensity_one hset:{n | sumRep univ n = n + 1} = univ⊢ 0 < 1 hset:{n | sumRep univ n = n + 1} = univ⊢ 0 < 1] hset:{n | sumRep univ n = n + 1} = univ⊢ 0 < 1
norm_num All goals completed! 🐙end Erdos1193