Landau maximiser as a product of prime powers
ProvedLandauExplore.landau_primePow_decompgroup-theorynumber-theory
For every natural number , Landau's function — the largest order of a permutation of an -element set — is a product of prime powers whose sum is at most . More precisely, there is a finite set of prime powers (each of the form with prime and ) such that and .
This is the sup/max bookkeeping half of the identification of Landau's function with a knapsack optimum over prime-power families: the maximum order is attained, and the attaining permutation's order decomposes into prime powers. The converse direction — that every prime-power family with sum at most has product at most — is a separate statement.
Preamble
import Mathlib.Data.Nat.Factorization.Basic import Mathlib.NumberTheory.Chebyshev import Mathlib.Analysis.SpecialFunctions.Log.Basic import Mathlib.Algebra.GCDMonoid.FinsetLemmas import Mathlib.RingTheory.Coprime.Lemmas import Mathlib.GroupTheory.Perm.Cycle.Type import Mathlib.GroupTheory.Perm.Cycle.PossibleTypes import Definitions.Def_LandauExplore_landauLocal open Finset
Formal statement
namespace LandauExplore
theorem landau_primePow_decomp (n : ℕ) :
∃ t : Finset ℕ, (∀ q ∈ t, ∃ p k : ℕ, p.Prime ∧ 1 ≤ k ∧ q = p ^ k)
∧ ∑ q ∈ t, q ≤ n ∧ ∏ q ∈ t, q = landauLocal n := by sorry
end LandauExploreHuman review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.