Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

An arithmetic inequality between the least and greatest prime factors

Proved
SubnormalCover.minFac_pred_mul_prod_le

by burkh4rt · Sep 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsgroup-theory

A purely arithmetic inequality. Let N≥2N\ge 2N≥2 and let p1<⋯<prp_1<\dots<p_rp1​<⋯<pr​ be the distinct prime divisors of NNN, so that p∗=p1p_*=p_1p∗​=p1​ is the smallest and p∗=prp^{*}=p_rp∗=pr​ the largest. Then

p∗∏t=1rpt−1pt  ≥  p∗−1.p^{*}\prod_{t=1}^{r}\frac{p_t-1}{p_t}\;\ge\;p_*-1 .p∗t=1∏r​pt​pt​−1​≥p∗​−1.

The proof is a downward induction: pr∏t≤rpt−1pt=(pr−1)∏t<rpt−1pt≥pr−1∏t<rpt−1ptp_r\prod_{t\le r}\frac{p_t-1}{p_t}=(p_r-1)\prod_{t<r}\frac{p_t-1}{p_t}\ge p_{r-1}\prod_{t<r}\frac{p_t-1}{p_t}pr​∏t≤r​pt​pt​−1​=(pr​−1)∏t<r​pt​pt​−1​≥pr−1​∏t<r​pt​pt​−1​, since pr>pr−1p_r>p_{r-1}pr​>pr−1​ forces pr−1≥pr−1p_r-1\ge p_{r-1}pr​−1≥pr−1​; iterating down to t=1t=1t=1 leaves p1⋅p1−1p1=p1−1p_1\cdot\frac{p_1-1}{p_1}=p_1-1p1​⋅p1​p1​−1​=p1​−1.

Formalization note. Denominators are cleared, so the statement is the N\mathbb{N}N-inequality (p∗−1)∏p∣Np≤p∗∏p∣N(p−1)(p_*-1)\prod_{p\mid N}p\le p^{*}\prod_{p\mid N}(p-1)(p∗​−1)∏p∣N​p≤p∗∏p∣N​(p−1); all truncated subtractions are exact (Nat.minFac N≥2\texttt{Nat.minFac }N\ge 2Nat.minFac N≥2 and every p≥2p\ge 2p≥2). The hypothesis 2≤N2\le N2≤N is essential rather than cosmetic: at N=0N=0N=0 Mathlib's conventions (minFac 0=2\texttt{minFac }0=2minFac 0=2, primeFactors 0=∅\texttt{primeFactors }0=\varnothingprimeFactors 0=∅, maxPrimeFac 0=0\texttt{maxPrimeFac }0=0maxPrimeFac 0=0) make the inequality read 1≤01\le 01≤0, which is false.

Preamble
import Mathlib
import Definitions.Def_BFFPyramidal_arithmetic
Formal statement
namespace SubnormalCover

open BFFPyramidal

theorem minFac_pred_mul_prod_le {N : ℕ} (hN : 2 ≤ N) :
    (Nat.minFac N - 1) * ∏ p ∈ N.primeFactors, p
      ≤ maxPrimeFac N * ∏ p ∈ N.primeFactors, (p - 1) := by
  sorry

end SubnormalCover
Source
Z.-W. Sun, On the Herzog-Schönheim conjecture for uniform covers of groups, J. Algebra 273 (2004) 153-175, https://doi.org/10.1016/S0021-8693(03)00526-X, Sun, proof of Theorem 4.3(i): the chain pr∏t=1rpt−1pt≥pr−1∏t=1r−1pt−1pt≥⋯≥p1p1−1p1=p∗−1p_r\prod_{t=1}^r\frac{p_t-1}{p_t}\ge p_{r-1}\prod_{t=1}^{r-1}\frac{p_t-1}{p_t}\ge\cdots\ge p_1\frac{p_1-1}{p_1}=p_*-1pr​∏t=1r​pt​pt​−1​≥pr−1​∏t=1r−1​pt​pt​−1​≥⋯≥p1​p1​p1​−1​=p∗​−1 (page 172)
Read-back

What the Lean code literally says, in plain math · claude-opus-5

Setting. Let NNN be a natural number (an implicit argument, universally quantified) with the single hypothesis 2≤N2 \le N2≤N; this excludes N=0N = 0N=0 and N=1N = 1N=1, so NNN has at least one prime factor.

Conclusion. An inequality of natural numbers:

(p(N)−1)⋅∏p ∈ P(N)p    ≤    P(N)⋅∏p ∈ P(N)(p−1),\big(p(N) - 1\big)\cdot \prod_{p \,\in\, \mathbb{P}(N)} p \;\;\le\;\; P(N)\cdot \prod_{p \,\in\, \mathbb{P}(N)} (p-1),(p(N)−1)⋅p∈P(N)∏​p≤P(N)⋅p∈P(N)∏​(p−1),

where:

  • P(N):=primeFactors(N)\mathbb{P}(N) := \mathrm{primeFactors}(N)P(N):=primeFactors(N) is Mathlib's finite set of distinct primes dividing NNN (so each prime appears exactly once regardless of multiplicity); by convention primeFactors(0)=primeFactors(1)=∅\mathrm{primeFactors}(0) = \mathrm{primeFactors}(1) = \varnothingprimeFactors(0)=primeFactors(1)=∅, but 2≤N2 \le N2≤N makes P(N)\mathbb{P}(N)P(N) nonempty. The left-hand product is therefore the radical (squarefree kernel) of NNN, and the right-hand product is ∏p∣N(p−1)\prod_{p \mid N}(p-1)∏p∣N​(p−1).
  • p(N):=minFac(N)p(N) := \mathrm{minFac}(N)p(N):=minFac(N) is Mathlib's least prime factor, with the junk conventions minFac(0)=2\mathrm{minFac}(0) = 2minFac(0)=2 and minFac(1)=1\mathrm{minFac}(1) = 1minFac(1)=1; under 2≤N2 \le N2≤N it is the genuine smallest prime dividing NNN, so p(N)≥2p(N) \ge 2p(N)≥2.
  • P(N):=maxPrimeFac(N)P(N) := \mathrm{maxPrimeFac}(N)P(N):=maxPrimeFac(N) is the platform definition sup⁡q∈P(N)q\sup_{q \in \mathbb{P}(N)} qsupq∈P(N)​q, the supremum of the set of prime factors taken in N\mathbb{N}N with bottom element 000; thus P(0)=P(1)=0P(0) = P(1) = 0P(0)=P(1)=0, while for 2≤N2 \le N2≤N it is the greatest prime dividing NNN.
  • All subtractions are truncated natural-number subtraction; since every p∈P(N)p \in \mathbb{P}(N)p∈P(N) satisfies p≥2p \ge 2p≥2 and p(N)≥2p(N) \ge 2p(N)≥2 under the hypothesis, no truncation to 000 occurs here, and ≤\le≤ is the usual order on N\mathbb{N}N (non-strict).

Degenerate cases. The hypothesis 2≤N2 \le N2≤N removes the two inputs (N∈{0,1}N \in \{0,1\}N∈{0,1}) on which P(N)\mathbb{P}(N)P(N) is empty (both products would then be the empty product 111) and on which minFac\mathrm{minFac}minFac and maxPrimeFac\mathrm{maxPrimeFac}maxPrimeFac take their conventional values. When NNN is a prime power qeq^eqe, both sides read (q−1)⋅q≤q⋅(q−1)(q-1)\cdot q \le q \cdot (q-1)(q−1)⋅q≤q⋅(q−1), an equality. No primality, squarefreeness, or bound on the number of prime factors of NNN is assumed, and multiplicities of the primes in NNN play no role in either side.

Human review
  • Endorsed by Shuze Chen · Sep 14, 2026

  • Endorsed by burkh4rt · Sep 14, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me