Erdős Problem 859

Reference: erdosproblems.com/859

def Erdos859.DivisorSumSet (t : ℕ) : Set ℕ

DivisorSumSet t is the set of natural numbers n such that t can be represented as a sum of distinct divisors of n.

Equations

• Erdos859.DivisorSumSet t = {n : ℕ | ∃ s ⊆ n.divisors, t = ∑ i ∈ s, i}

theorem Erdos859.erdos_859.variants.erdos_upper_lower_bounds : ∃ c₃ > 0, ∃ c₄ > 0, ∃ (t₀ : ℕ), ∀ᶠ (t : ℕ) in Filter.atTop, ∃ (dₜ : ℝ), (DivisorSumSet t).HasDensity dₜ ∧ 1 / Real.log ↑t ^ c₃ < dₜ ∧ dₜ < 1 / Real.log ↑t ^ c₄

A weaker version of the problem proved by Erdos: The density dₜ of DivisorSumSet (t : ℕ) is bounded from below by 1 / log (t) ^ c₃ and from above by 1 / log (t) ^ c₄ for some positive constants c₃ and c₄.

theorem Erdos859.erdos_859 : ∃ c₁ > 0, ∃ c₂ > 0, ∃ (d : ℕ → ℝ), (∀ t > 0, (DivisorSumSet t).HasDensity (d t)) ∧ Asymptotics.IsEquivalent Filter.atTop (fun (t : ℕ) => d t) fun (t : ℕ) => c₁ / Real.log ↑t ^ c₂

The density of the divisor sum set is asymptotically equivalent to $c_1 / \log(t)^{c_2}$.

theorem Erdos859.erdos_859.variants.trivial_case : DivisorSumSet 0 = Set.univ

A case where we can easily calculate the density of DivisorSumSet t is that of t=0.

theorem Erdos859.erdos_859.variants.positive_density (t : ℕ) : (DivisorSumSet t).HasPosDensity

An easy sanity check is to prove that for every natural number t the density dₜ is a positive number. Hint: investigate some multiplicative structure of DivisorSumSet t.