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

Erdős Problem 1054

References:

@[expose] public sectionnamespace Erdos1054open Filter Asymptotics

Let $f(n)$ be the minimal integer $m$ such that $n$ is the sum of the $k$ smallest divisors of $m$ for some $k\geq 1$.

noncomputable def f (n : ℕ) : ℕ := open scoped Classical in if h : ∃ᵉ (m) (k ≥ 1), n = ∑ i < k, Nat.nth (· ∈ m.divisors) i then Nat.find h else 0

Let $f(n)$ be the minimal integer $m$ such that $n$ is the sum of the $k$ smallest divisors of $m$ for some $k\geq 1$. Is it true that $f(n)=o(n)$?

The strong claim that $f(n)=o(n)$ was disproved by Tao in the comments to 468, in which he proves that the upper density of ${ n : f(n)\leq \delta n}$ is $\ll \delta^2$.

@[category research solved, question, AMS 11, formal_proof using lean4 at "https://github.com/linrock/math-proofs/blob/0917cd01090b52088aa82b09c8c84689047b8171/erdos-1054/Solution.lean#L97"] theorem erdos_1054.parts.i : ¬ (fun n ↦ (f n : ℝ)) =o[atTop] (fun n ↦ (n : ℝ)) := ⊢ ¬(fun n ↦ ↑(f n)) =o[atTop] fun n ↦ ↑n All goals completed! 🐙

Let $f(n)$ be the minimal integer $m$ such that $n$ is the sum of the $k$ smallest divisors of $m$ for some $k\geq 1$. Is it true that $f(n)=o(n)$ for almost all $n$?

No: combining the Tao–Kovač small-ratio bound $#{n \leq X : 0 < f(n) \leq \delta n} \ll \delta^2 X$ with the fact that almost all odd integers are represented (or via the lower-density bound below), $f(n)$ is not $o(n)$ along any density-one set $A$.

@[category research solved, question, AMS 11, formal_proof using lean4 at "https://github.com/linrock/math-proofs/blob/0917cd01090b52088aa82b09c8c84689047b8171/erdos-1054/Solution.lean#L103"] theorem erdos_1054.parts.ii : ¬ ∃ (A : Set ℕ), A.HasDensity 1 ∧ (fun (n : A) ↦ (f ↑n : ℝ)) =o[atTop] (fun n ↦ (n : ℝ)) := ⊢ ¬∃ A, A.HasDensity 1 ∧ (fun n ↦ ↑(f ↑n)) =o[atTop] fun n ↦ ↑↑n All goals completed! 🐙

Let $f(n)$ be the minimal integer $m$ such that $n$ is the sum of the $k$ smallest divisors of $m$ for some $k\geq 1$. Is it true that $\limsup f(n)/n=\infty$?

Yes: for every $A \geq 1$, a positive lower density of odd integers satisfy $f(n) > A n$, so $\limsup f(n)/n = \infty$.

@[category research solved, question, AMS 11, formal_proof using lean4 at "https://github.com/linrock/math-proofs/blob/0917cd01090b52088aa82b09c8c84689047b8171/erdos-1054/Solution.lean#L110"] theorem erdos_1054.parts.iii : ∃ (A : Set ℕ), A.HasDensity 1 ∧ atTop.limsup (fun n ↦ (f n : EReal) / n) = ⊤ := ⊢ ∃ A, A.HasDensity 1 ∧ limsup (fun n ↦ ↑(f n) / ↑n) atTop = ⊤ All goals completed! 🐙

Let $f(n)$ be the minimal integer $m$ such that $n$ is the sum of the $k$ smallest divisors of $m$ for some $k\geq 1$. Show that $f$ is undefined at $n=2$, i.e. we get the junk value $0$.

m:ℕk:ℕhk:k ≥ 1hsum:2 = 1 + ∑ x ∈ (Finset.Iio k).erase 0, Nat.nth (fun x ↦ x ∈ m.divisors) xhm:m ≠ 0hk0:0 ∈ Finset.Iio ki:ℕhi_mem:i ∈ (Finset.Iio k).erase 0hi_ne:Nat.nth (fun x ↦ x ∈ m.divisors) i ≠ 0⊢ False m:ℕk:ℕhk:k ≥ 1hsum:2 = 1 + ∑ x ∈ (Finset.Iio k).erase 0, Nat.nth (fun x ↦ x ∈ m.divisors) xhm:m ≠ 0hk0:0 ∈ Finset.Iio ki:ℕhi_mem:i ∈ (Finset.Iio k).erase 0hi_ne:Nat.nth (fun x ↦ x ∈ m.divisors) i ≠ 0h2:2 ≤ Nat.nth (fun x ↦ x ∈ m.divisors) i⊢ False m:ℕk:ℕhk:k ≥ 1hsum:2 = 1 + ∑ x ∈ (Finset.Iio k).erase 0, Nat.nth (fun x ↦ x ∈ m.divisors) xhm:m ≠ 0hk0:0 ∈ Finset.Iio ki:ℕhi_mem:i ∈ (Finset.Iio k).erase 0hi_ne:Nat.nth (fun x ↦ x ∈ m.divisors) i ≠ 0h2:2 ≤ Nat.nth (fun x ↦ x ∈ m.divisors) ithis:2 ≤ ∑ x ∈ (Finset.Iio k).erase 0, Nat.nth (fun x ↦ x ∈ m.divisors) x⊢ False All goals completed! 🐙

Let $f(n)$ be the minimal integer $m$ such that $n$ is the sum of the $k$ smallest divisors of $m$ for some $k\geq 1$. Show that $f$ is undefined at $n=5$, i.e. we get the junk value $0$.

m:ℕk:ℕhk:k ≥ 1hm:m ≠ 0p:ℕ → Prop := fun x ↦ x ∈ m.divisorshsum:5 = ∑ i < k, Nat.nth p ihpdef:p = fun x ↦ x ∈ m.divisorshfin:(Set.ofPred p).Finitehg0:Nat.nth p 0 = 1hlb:∀ j < hfin.toFinset.card, j + 1 ≤ Nat.nth p jrefute4:Nat.nth p 1 ≠ 4hk3:3 ≤ khg2:Nat.nth p 2 ≠ 0hc3:2 < hfin.toFinset.cardhg1:1 + 1 ≤ Nat.nth p 1hg2':2 + 1 ≤ Nat.nth p 2hsub:1 + Nat.nth p 1 + Nat.nth p 2 ≤ ∑ i < k, Nat.nth p i⊢ False All goals completed! 🐙end Erdos1054