/- 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 public import FormalConjectures.Wikipedia.ABC

Erdős Problem 393

References:

    erdosproblems.com/393

    [ErGr80] Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).

    [BeOs92] Berend, Daniel and Osgood, Charles F., On the equation $P(x)=n!$ and a question of Erdős. J. Number Theory 42 (1992), 189-193.

    [BPZ23] Bui, Hung M. and Pratt, Kyle and Zaharescu, Alexandru, Power savings for counting solutions to polynomial-factorial equations. Adv. Math. 422 (2023), Paper No. 109021, 32 pp. arXiv:2204.08423

    [Lu02] Luca, Florian, The Diophantine equation $P(x)=n!$ and a result of M. Overholt. Glas. Mat. Ser. III 37 (2002), 269-273.

    OEIS A388302: the values $f(n)$ for $n \geq 2$.

@[expose] public sectionopen Filter Asymptoticsopen scoped Natnamespace Erdos393

f n is $f(n)$, the minimal $m \geq 1$ such that $n! = a_1 \cdots a_t$ with $a_1 < \cdots < a_t = a_1 + m$. The factors are recorded as a finite set $s \subseteq [a, a + m]$ of natural numbers that contains $a = a_1$ and $a + m = a_t$. Since $m \geq 1$ there are at least two factors, and they are positive because $n! \neq 0$.

Such a factorisation exists for $n \geq 2$. For $n \leq 1$ there is none, since $n! = 1$, and f n is the junk value 0.

noncomputable def f (n : ℕ) : ℕ := sInf {m : ℕ | 1 ≤ m ∧ ∃ a : ℕ, ∃ s ⊆ Finset.Icc a (a + m), a ∈ s ∧ a + m ∈ s ∧ ∏ i ∈ s, i = n !}

For $n \geq 2$ the factorisation $n! = 1 \cdot 2 \cdots n$ exists, so f n is a true minimum and $f(n) \geq 1$.

@[category test, AMS 11] theorem one_le_f (n : ℕ) (hn : 2 ≤ n) : 1 ≤ f n := n:ℕhn:2 ≤ n⊢ 1 ≤ f n n:ℕhn:2 ≤ nhprod:∏ i ∈ Finset.Ico 1 (n + 1), i = n !⊢ 1 ≤ f n refine le_csInf ⟨n - 1, n:ℕhn:2 ≤ nhprod:∏ i ∈ Finset.Ico 1 (n + 1), i = n !⊢ 1 ≤ n - 1 All goals completed! 🐙, 1, Finset.Ico 1 (n + 1), ?_, ?_, ?_, hprod⟩ fun _ hm ↦ hm.1 n:ℕhn:2 ≤ nhprod:∏ i ∈ Finset.Ico 1 (n + 1), i = n !⊢ Finset.Ico 1 (n + 1) ⊆ Finset.Icc 1 (1 + (n - 1)) n:ℕhn:2 ≤ nhprod:∏ i ∈ Finset.Ico 1 (n + 1), i = n !i:ℕhi:i ∈ Finset.Ico 1 (n + 1)⊢ i ∈ Finset.Icc 1 (1 + (n - 1)) n:ℕhn:2 ≤ nhprod:∏ i ∈ Finset.Ico 1 (n + 1), i = n !i:ℕhi:i ∈ Finset.Ico 1 (n + 1)h1:1 ≤ ih2:i < n + 1⊢ i ∈ Finset.Icc 1 (1 + (n - 1)) exact Finset.mem_Icc.2 ⟨h1, n:ℕhn:2 ≤ nhprod:∏ i ∈ Finset.Ico 1 (n + 1), i = n !i:ℕhi:i ∈ Finset.Ico 1 (n + 1)h1:1 ≤ ih2:i < n + 1⊢ i ≤ 1 + (n - 1) All goals completed! 🐙⟩ n:ℕhn:2 ≤ nhprod:∏ i ∈ Finset.Ico 1 (n + 1), i = n !⊢ 1 ∈ Finset.Ico 1 (n + 1) exact Finset.mem_Ico.2 ⟨le_rfl, n:ℕhn:2 ≤ nhprod:∏ i ∈ Finset.Ico 1 (n + 1), i = n !⊢ 1 < n + 1 All goals completed! 🐙⟩ n:ℕhn:2 ≤ nhprod:∏ i ∈ Finset.Ico 1 (n + 1), i = n !⊢ 1 + (n - 1) ∈ Finset.Ico 1 (n + 1) exact Finset.mem_Ico.2 ⟨n:ℕhn:2 ≤ nhprod:∏ i ∈ Finset.Ico 1 (n + 1), i = n !⊢ 1 ≤ 1 + (n - 1) All goals completed! 🐙, n:ℕhn:2 ≤ nhprod:∏ i ∈ Finset.Ico 1 (n + 1), i = n !⊢ 1 + (n - 1) < n + 1 All goals completed! 🐙⟩

$3! = 2 \cdot 3$, so $f(3) = 1$.

@[category test, AMS 11] theorem f_three : f 3 = 1 := le_antisymm (Nat.sInf_le ⟨le_rfl, 2, {2, 3}, ⊢ {2, 3} ⊆ Finset.Icc 2 (2 + 1) All goals completed! 🐙, ⊢ 2 ∈ {2, 3} All goals completed! 🐙, ⊢ 2 + 1 ∈ {2, 3} All goals completed! 🐙, ⊢ ∏ i ∈ {2, 3}, i = 3! All goals completed! 🐙⟩) (one_le_f 3 (⊢ 2 ≤ 3 All goals completed! 🐙))

The factors need not be consecutive integers: $7! = 70 \cdot 72$, so $f(7) \leq 2$.

@[category test, AMS 11] theorem f_seven_le_two : f 7 ≤ 2 := Nat.sInf_le ⟨⊢ 1 ≤ 2 All goals completed! 🐙, 70, {70, 72}, ⊢ {70, 72} ⊆ Finset.Icc 70 (70 + 2) All goals completed! 🐙, ⊢ 70 ∈ {70, 72} All goals completed! 🐙, ⊢ 70 + 2 ∈ {70, 72} All goals completed! 🐙, ⊢ ∏ i ∈ {70, 72}, i = 7! All goals completed! 🐙⟩

The factorisation $n! = 2 \cdot 3 \cdots n$ shows that $f(n) \leq n - 2$ for $n \geq 3$.

n:ℕhn:3 ≤ nhprod:∏ i ∈ Finset.Ico 2 (n + 1), i = n !⊢ f n ≤ n - 2 refine Nat.sInf_le ⟨n:ℕhn:3 ≤ nhprod:∏ i ∈ Finset.Ico 2 (n + 1), i = n !⊢ 1 ≤ n - 2 All goals completed! 🐙, 2, Finset.Ico 2 (n + 1), ?_, ?_, ?_, hprod⟩ n:ℕhn:3 ≤ nhprod:∏ i ∈ Finset.Ico 2 (n + 1), i = n !⊢ Finset.Ico 2 (n + 1) ⊆ Finset.Icc 2 (2 + (n - 2)) n:ℕhn:3 ≤ nhprod:∏ i ∈ Finset.Ico 2 (n + 1), i = n !i:ℕhi:i ∈ Finset.Ico 2 (n + 1)⊢ i ∈ Finset.Icc 2 (2 + (n - 2)) n:ℕhn:3 ≤ nhprod:∏ i ∈ Finset.Ico 2 (n + 1), i = n !i:ℕhi:i ∈ Finset.Ico 2 (n + 1)h1:2 ≤ ih2:i < n + 1⊢ i ∈ Finset.Icc 2 (2 + (n - 2)) exact Finset.mem_Icc.2 ⟨h1, n:ℕhn:3 ≤ nhprod:∏ i ∈ Finset.Ico 2 (n + 1), i = n !i:ℕhi:i ∈ Finset.Ico 2 (n + 1)h1:2 ≤ ih2:i < n + 1⊢ i ≤ 2 + (n - 2) All goals completed! 🐙⟩ n:ℕhn:3 ≤ nhprod:∏ i ∈ Finset.Ico 2 (n + 1), i = n !⊢ 2 ∈ Finset.Ico 2 (n + 1) exact Finset.mem_Ico.2 ⟨le_rfl, n:ℕhn:3 ≤ nhprod:∏ i ∈ Finset.Ico 2 (n + 1), i = n !⊢ 2 < n + 1 All goals completed! 🐙⟩ n:ℕhn:3 ≤ nhprod:∏ i ∈ Finset.Ico 2 (n + 1), i = n !⊢ 2 + (n - 2) ∈ Finset.Ico 2 (n + 1) exact Finset.mem_Ico.2 ⟨n:ℕhn:3 ≤ nhprod:∏ i ∈ Finset.Ico 2 (n + 1), i = n !⊢ 2 ≤ 2 + (n - 2) All goals completed! 🐙, n:ℕhn:3 ≤ nhprod:∏ i ∈ Finset.Ico 2 (n + 1), i = n !⊢ 2 + (n - 2) < n + 1 All goals completed! 🐙⟩

$1! = 1$ is not a product of two or more distinct positive integers, so f 1 is the junk value 0.

m:ℕhm:1 ≤ ma:ℕs:Finset ℕha:a ∈ shb:a + m ∈ shs:∏ i ∈ s, i = 1!h1:a ∣ 1h2:a + m ∣ 1⊢ False m:ℕhm:1 ≤ ma:ℕs:Finset ℕha:a ∈ shb:a + m ∈ shs:∏ i ∈ s, i = 1!h1:a ∣ 1h2:a + m ∣ 1ha1:a = 1⊢ False m:ℕhm:1 ≤ ma:ℕs:Finset ℕha:a ∈ shb:a + m ∈ shs:∏ i ∈ s, i = 1!h1:a ∣ 1h2:a + m ∣ 1ha1:a = 1hb1:a + m = 1⊢ False All goals completed! 🐙

Let $f(n)$ denote the minimal $m\geq 1$ such that $$n! = a_1\cdots a_t$$ with $a_1<\cdots <a_t=a_1+m$. What is the behaviour of $f(n)$?

We formalise the question as: does $f(n) \to \infty$? A result of Luca [Lu02] implies a positive answer, conditional on the $abc$ conjecture (see Erdos393.erdos_393.variants.luca).

@[category research open, question, AMS 11] theorem erdos_393 : Tendsto f atTop atTop := ⊢ Tendsto f atTop atTop All goals completed! 🐙

Erdős and Graham [ErGr80, p. 76] write that they do not even know whether $f(n) = 1$ for infinitely many $n$, that is, whether a factorial is the product of two consecutive integers infinitely often.

@[category research open, question, AMS 11] theorem erdos_393.variants.infinitely_often_one : {n : ℕ | f n = 1}.Infinite := ⊢ {n | f n = 1}.Infinite All goals completed! 🐙

Let $F_m(N)$ count the number of $n \leq N$ such that $f(n) = m$. A theorem of Berend and Osgood [BeOs92] implies that, for each fixed $m$, $F_m(N) = o(N)$, that is, ${n : f(n) = m}$ has natural density $0$.

They proved that, for every $P \in \mathbb{Z}[x]$ of degree at least $2$, the set of $n$ such that $P(x) = n!$ has an integer solution has density $0$. For $m \geq 1$ this applies because $f(n) = m$ gives $n! = P(a_1)$ for one of the finitely many polynomials $P(x) = \prod_{j \in S} (x + j)$ with ${0, m} \subseteq S \subseteq {0, \ldots, m}$. For $m = 0$ the set is ${0, 1}$ (the junk values), so the statement is trivial.

@[category research solved, AMS 11] theorem erdos_393.variants.berend_osgood (m : ℕ) : {n : ℕ | f n = m}.HasDensity 0 := m:ℕ⊢ {n | f n = m}.HasDensity 0 All goals completed! 🐙

A theorem of Bui, Pratt, and Zaharescu [BPZ23] implies that, for each fixed $m$, $$F_m(N) \ll_m N^{33/34},$$ where $F_m(N)$ is the number of $n \leq N$ such that $f(n) = m$.

They proved that, for every $P \in \mathbb{Z}[x]$ of degree at least $2$, the number of $N \leq n < 2N$ such that $P(x) = n!$ has an integer solution is $\ll_P N^{33/34}$. Summing over the finitely many polynomials in Erdos393.erdos_393.variants.berend_osgood and over the dyadic ranges $[2^i, 2^{i+1})$ gives the bound for $n \leq N$.

@[category research solved, AMS 11] theorem erdos_393.variants.bui_pratt_zaharescu (m : ℕ) : (fun N : ℕ ↦ (({n : ℕ | f n = m} ∩ Set.Iic N).ncard : ℝ)) =O[atTop] (fun N : ℕ ↦ (N : ℝ) ^ (33 / 34 : ℝ)) := m:ℕ⊢ (fun N ↦ ↑({n | f n = m} ∩ Set.Iic N).ncard) =O[atTop] fun N ↦ ↑N ^ (33 / 34) All goals completed! 🐙

Luca [Lu02] proved that the $abc$ conjecture implies that, for every $P \in \mathbb{Z}[x]$ of degree at least $2$, the equation $P(x) = n!$ has only finitely many solutions. As remarked on erdosproblems.com, this implies that $f(n) \to \infty$, conditional on the $abc$ conjecture (ABC.abc).

@[category research solved, AMS 11, formal_proof using lean4 at "https://palomar-registry.org/entry.html?id=PALOMAR-2026-11-02-000011"] theorem erdos_393.variants.luca (habc : type_of% ABC.abc) : Tendsto f atTop atTop := habc:∀ (ε : ℝ), 0 < ε → {(a, b, c) | 0 < a ∧ 0 < b ∧ 0 < c ∧ {a, b, c}.Pairwise Nat.Coprime ∧ a + b = c ∧ ↑(ABC.radical (a * b * c)) ^ (1 + ε) < ↑c}.Finite⊢ Tendsto f atTop atTop All goals completed! 🐙end Erdos393