Skip to content

Erdős Problem #1161

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: solved (not automatically the live result).
Subject areas: group theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Erdős Problem #1161. How many permutations have a specified order, and which integer order is the most frequent?

\[ f_k(n)=\#\{\sigma\in S_n:\mathrm{ord}(\sigma)=k\},\quad\max_k f_k(n)\sim(n-1)!. \]

Let f_k(n) be the number of permutations of S_n of order EXACTLY k (order = lcm of disjoint cycle lengths). Which k maximize f_k(n)? Let k be a positive integer and n sufficiently large; a conditional inequality f_k(n)≥(n-1)! has a divisibility criterion involving lcm(1,…,n-k). A verbal statement 'k minimal such that [1,..,n-k] divides k' must be source-parsed precisely: n-k may be zero/negative and minimality ranges over k.

A small example

Exact permutation enumeration S_n for 1≤n≤7 via cycle decomposition computes histogram of orders and modal orders, stored in phase19 receipt; sum over k f_k(n)=n! checked for each n. In S3: 1 identity, 3 transpositions order2, 2 three-cycles order3; modal order 2 has frequency3, matching (n-1)!=2 only in scale not equality. No eventual criterion inferred from n≤7.

What is known

https://www.erdosproblems.com/1161 SOLVED by Adrian Beker [Be25d], 2025 arXiv:2510.11698 'The most probable order of a random permutation'. Primary abstract says max_m P(order=m)∼1/n so max f_k(n)∼(n-1)!, and for all sufficiently large n maximizers are exactly k least positive satisfying divisibility by all integers ≤n-k. The catalogue records an additional threshold f_k(n)≥(n-1)! implies divisibility. These are asymptotic / eventually exact, not a claimed exact small-n formula.

GCL's current state

Authenticated source-bound original-issue audit reports the mathematical status, external source attribution and independently tested bounded evidence. The deterministic programme is ci/erdos_compendium_007_phase19_checks.py.

This source return is PARTIAL. Neither an original-source proof review, Lean kernel certification, independent critical approval nor protected V2 admission has been completed.

What remains

ERDOS-1161-BEKER-MODAL-001: source-lock arXiv:2510.11698 and proof, precisely check 'least k' quantifier against website threshold language, verify asymptotic normalizing n!, determine exact cycle-type maximizers n≤20 from integer partitions with certified arithmetic and compare.

Original 2025 proof, precise eventually-maximizing k expression and paper publication status not independently adjudicated. External SOLVED.

Sources and claim boundaries

https://www.erdosproblems.com/1161 ; https://arxiv.org/abs/2510.11698 ; [Va99,5.72], [Be25d]. Exact n≤7 permutation order enumeration independently verified.

Unaccepted editorial manuscript. The exact finite examples are independently checked; all general published claims await primary source fidelity review. A source-notation conflict is not a new theorem.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2432 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction