AFTD Auto-Formalizing Theoretical Domains

restricted_cycle_global_gcd_eq_one_param_gcd_3_5

theoremverifiedformalization

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.

  1. 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`).

    line 3

        restricted_cycle_global_gcd 3 5 = restricted_cycle_one_param_gcd 3 5 := rfl

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
See it in the graphDiscuss this resultChallenge it