restricted_cycle_global_gcd_eq_one_param_gcd_3_5
For r = 3 and n = 5, restricted_cycle_global_gcd 3 5 = restricted_cycle_one_param_gcd 3 5.
Statement
theorem restricted_cycle_global_gcd_eq_one_param_gcd_3_5 :
restricted_cycle_global_gcd 3 5 = restricted_cycle_one_param_gcd 3 5- Formalizes
- arXiv:2610.40342 Question 14.10
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- restricted_cycle_global_gcdThe global gcd g_r(n) is the greatest common divisor of the counts restricted_cycle_perms_count n S over all sets S in…
- restricted_cycle_one_param_gcdThe one-parameter gcd G_r(n) is the greatest common divisor of the counts restricted_cycle_perms_count n S over all sets S in…
Read back from the Lean
The greatest common divisor of the number of permutations of a 5-element set having no cycle lengths in $S$, evaluated over all sets $S$ of the form $\{1, 2, 3\} \cup T$ for $T \subseteq \{4, 5\}$, is equal to the greatest common divisor of the same counts evaluated over the restricted family of sets $S \in \{\{1, 2, 3\}, \{1, 2, 3, 4\}, \{1, 2, 3, 5\}\}$ (that is, $T = \emptyset$ or $T = \{k\}$ for $k \in \{4, 5\}$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem states that for parameters $r = 3$ and $n = 5$, the global greatest common divisor of the restricted cycle permutation counts coincides with the one-parameter greatest common divisor. Because both sides are explicit finite combinatorial computations on fixed parameters, the equality is verified directly by reflexivity (`rfl`), as both sides evaluate to 24.
restricted_cycle_global_gcd 3 5 = restricted_cycle_one_param_gcd 3 5
Both `restricted_cycle_global_gcd 3 5` and `restricted_cycle_one_param_gcd 3 5` are closed, computable expressions counting permutations of a 5-element set with restricted cycle lengths and computing the greatest common divisor of those counts. Lean reduces both sides definitionally to 24, so the equality holds by reflexivity (`rfl`).
restricted_cycle_global_gcd 3 5 = restricted_cycle_one_param_gcd 3 5 := rfl
- The equality is established by Lean's kernel through definitional reduction (`rfl`): both sides are finite combinatorial expressions that evaluate to 24.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- For r = 3 and n = 5, the global gcd and the one-parameter gcd agree. -/theorem restricted_cycle_global_gcd_eq_one_param_gcd_3_5 : restricted_cycle_global_gcd 3 5 = restricted_cycle_one_param_gcd 3 5 := rfl