Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The multiplicity bound is at least two (arithmetic ingredient)

Proved
BFFPyramidal.two_le_multiplicity_bound_arith

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

combinatoricscoset-partitionsgroup-theoryherzog-schonheim

For every integer l≥2l \ge 2l≥2,

⌊P(l) φ(l)l⌋+1  ≥  2,\left\lfloor \frac{P(l)\,\varphi(l)}{l} \right\rfloor + 1 \;\ge\; 2,⌊lP(l)φ(l)​⌋+1≥2,

equivalently P(l) φ(l)≥lP(l)\,\varphi(l) \ge lP(l)φ(l)≥l, where P(l)P(l)P(l) is the greatest prime factor of lll and φ\varphiφ is Euler's totient function.

This arithmetic inequality is what turns the multiplicity bound of Berger-Felzenbaum-Fraenkel into the Herzog-Schönheim conjecture for pyramidal groups: the bound always forces at least two subgroups of equal order. The hypothesis l≥2l \ge 2l≥2 cannot be dropped — at l=1l = 1l=1 one has P(1)=0P(1) = 0P(1)=0 and the left-hand side is 111.

Formalization note. This is a statement of pure arithmetic: no group appears in it. It is separated out because it is the ingredient that turns the multiplicity bound into the Herzog-Schönheim conjecture.

The floor is natural-number division, which truncates, so the statement is 2 ≤ (maxPrimeFac l * Nat.totient l) / l + 1.

Preamble
import Mathlib
import Definitions.Def_BFFPyramidal_arithmetic
Formal statement
namespace BFFPyramidal

theorem two_le_multiplicity_bound_arith (l : ℕ) (hl : 2 ≤ l) :
    2 ≤ (maxPrimeFac l * Nat.totient l) / l + 1 := by
  sorry

end BFFPyramidal
Source
Berger--Felzenbaum--Fraenkel 1987, Remark on the multiplicity of a partition of a group into cosets, Fund. Math. 128 (1987) 139-144, https://doi.org/10.4064/fm-128-3-139-144, p. 139, the remark following the Theorem ("Note that x≥2x \ge 2x≥2")
Read-back

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

Read-back: BFFPyramidal.two_le_multiplicity_bound_arith

The declaration asserts a single arithmetic inequality, universally quantified over one explicit natural-number variable. There are no implicit arguments, no instance-implicit (typeclass) arguments, no type variables, and no existential quantifiers anywhere in the statement.

Statement. For every natural number lll, and under the single hypothesis

2≤l,2 \le l,2≤l,

the conclusion is

2  ≤  ⌊P(l) φ(l)l⌋+1.2 \;\le\; \left\lfloor \frac{P(l)\,\varphi(l)}{l} \right\rfloor + 1 .2≤⌊lP(l)φ(l)​⌋+1.

Both the hypothesis and the conclusion are non-strict inequalities (≤\le≤, in that direction: the constant 222 is the smaller side in both). The quantifier order is: lll first, then the hypothesis 2≤l2 \le l2≤l as an assumption, then the conclusion; i.e. the whole claim is ∀l∈N,  2≤l⇒2≤⌊P(l)φ(l)/l⌋+1\forall l \in \mathbb{N},\; 2 \le l \Rightarrow 2 \le \lfloor P(l)\varphi(l)/l\rfloor + 1∀l∈N,2≤l⇒2≤⌊P(l)φ(l)/l⌋+1. The variable lll ranges over N\mathbb{N}N (so it includes 000 and 111, which the hypothesis then excludes), and every quantity appearing — P(l)P(l)P(l), φ(l)\varphi(l)φ(l), the quotient, and the sum — is a natural number, not a rational or real number.

The two arithmetic functions, unfolded.

  • φ\varphiφ is Euler's totient function, Mathlib's standard Nat.totient, with the usual conventions φ(0)=0\varphi(0) = 0φ(0)=0 and φ(1)=1\varphi(1) = 1φ(1)=1.

  • P(l)P(l)P(l) is a definition supplied by the accompanying definitions file, not a standard library notion. It is the greatest prime factor of lll, defined as the supremum (maximum) of the finite set of prime divisors of lll, taken with the convention that the supremum of the empty set is 000. Consequently:

    • P(0)=0P(0) = 0P(0)=0 and P(1)=0P(1) = 0P(1)=0, since neither 000 nor 111 has any prime factor recorded in that set (Mathlib's set of prime factors of 000 is empty);
    • for l≥2l \ge 2l≥2, P(l)P(l)P(l) is the largest prime ppp with p∣lp \mid lp∣l, so 2≤P(l)≤l2 \le P(l) \le l2≤P(l)≤l.

    Note that this is the greatest prime factor, not the least; the definitions file remarks that the least prime factor is a different function.

Truncating operations. The division P(l)φ(l)/lP(l)\varphi(l) / lP(l)φ(l)/l is natural-number (floor) division: it is ⌊P(l)φ(l)/l⌋\lfloor P(l)\varphi(l)/l \rfloor⌊P(l)φ(l)/l⌋, and by Lean's convention division by 000 yields 000 (relevant only if l=0l = 0l=0, which the hypothesis excludes). There is no natural-number subtraction in the statement. Because of the floor, the conclusion is not equivalent to the real-number statement P(l)φ(l)/l+1≥2P(l)\varphi(l)/l + 1 \ge 2P(l)φ(l)/l+1≥2; unfolding, the conclusion says exactly

⌊P(l) φ(l)l⌋  ≥  1,equivalentlyl  ≤  P(l) φ(l).\left\lfloor \frac{P(l)\,\varphi(l)}{l} \right\rfloor \;\ge\; 1, \qquad\text{equivalently}\qquad l \;\le\; P(l)\,\varphi(l).⌊lP(l)φ(l)​⌋≥1,equivalentlyl≤P(l)φ(l).

Degenerate and boundary behaviour.

  • l=0l = 0l=0: excluded by the hypothesis. Had it been allowed, the left expression would be 0⋅0/0+1=10\cdot 0 / 0 + 1 = 10⋅0/0+1=1, and the claim would be false.
  • l=1l = 1l=1: excluded by the hypothesis. Had it been allowed, P(1)φ(1)/1+1=0⋅1+1=1P(1)\varphi(1)/1 + 1 = 0\cdot 1 + 1 = 1P(1)φ(1)/1+1=0⋅1+1=1, and the claim would again be false.
  • So the hypothesis 2≤l2 \le l2≤l is used (the statement is false without it at l∈{0,1}l \in \{0,1\}l∈{0,1}), it is satisfiable (every l≥2l \ge 2l≥2 satisfies it, so the theorem is not vacuous), and the boundary case l=2l = 2l=2 gives P(2)φ(2)/2+1=2⋅1/2+1=2P(2)\varphi(2)/2 + 1 = 2\cdot 1/2 + 1 = 2P(2)φ(2)/2+1=2⋅1/2+1=2, meeting the bound with equality.
  • For a prime l=pl = pl=p: P(p)φ(p)/p+1=⌊p(p−1)/p⌋+1=pP(p)\varphi(p)/p + 1 = \lfloor p(p-1)/p \rfloor + 1 = pP(p)φ(p)/p+1=⌊p(p−1)/p⌋+1=p.

What the statement does not involve. The definitions file also defines a divisor-closure operation D(R)=⋃m∈R{d:d∣m}D(R) = \bigcup_{m \in R} \{d : d \mid m\}D(R)=⋃m∈R​{d:d∣m} on finite sets of naturals and a measure μ(S)=∑m∈Sφ(m)\mu(S) = \sum_{m \in S} \varphi(m)μ(S)=∑m∈S​φ(m); neither of these appears in the statement being audited. Nothing in the statement mentions groups, subgroups, multiplicities, pyramidal structures, or any object other than the natural number lll and the two arithmetic functions above, despite the declaration's name. The statement is a pure inequality between natural numbers.

Proof status. The proof body of the declaration is sorry: the theorem is asserted but not proved in this artifact.

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

  • Endorsed by burkh4rt · Sep 13, 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