AFTD Auto-Formalizing Theoretical Domains

restricted_cycle_global_gcd_dvd_one_param_gcd

theoremverifiedformalization

For all r and n, the global gcd restricted_cycle_global_gcd r n divides the one-parameter gcd restricted_cycle_one_param_gcd r n.

Statement

theorem restricted_cycle_global_gcd_dvd_one_param_gcd (r n : ℕ) :
    restricted_cycle_global_gcd r n ∣ restricted_cycle_one_param_gcd r n
Formalizes
arXiv:2610.40342 Theorem 5.1
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
Used by 4

Read back from the Lean

For all natural numbers $r$ and $n$, the greatest common divisor of the counts of permutations of $\mathrm{Fin}(n)$ with no cycle lengths in $S$, taken over all $S$ in the "excluded family" (sets of the form $\{1, \dots, r\} \cup T$ where $T \subseteq \{r+1, \dots, n\}$), divides the greatest common divisor of the counts taken over the "one-parameter family" (the set $\{1, \dots, r\}$ together with all sets $\{1, \dots, r\} \cup \{k\}$ for $k \in \{r+1, \dots, n\}$).

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

By definition, both the global gcd and the one-parameter gcd are greatest common divisors of restricted-cycle permutation counts over families of excluded sets. The one-parameter family is a subcollection of the full excluded family, so the global gcd divides the one-parameter gcd by the monotonicity of the finite-set greatest common divisor.

  1. The global gcd restricted_cycle_global_gcd r n divides the one-parameter gcd restricted_cycle_one_param_gcd r n.

    By definition, both quantities are the greatest common divisor of the permutation count function restricted_cycle_perms_count n over their respective families of subsets. Since the one-parameter family is a subset of the full excluded family (restricted_cycle_one_param_family_subset_excluded_family), taking the gcd over the larger set divides the gcd over the subset by Finset.gcd_mono.

    lines 4–5

    uses Finset.gcd_mono, restricted_cycle_one_param_family_subset_excluded_family

      unfold restricted_cycle_global_gcd restricted_cycle_one_param_gcd
      exact Finset.gcd_mono (restricted_cycle_one_param_family_subset_excluded_family r n)
Finset.gcd_mono
If $s_1 \subseteq s_2$ are finite sets, then the greatest common divisor of a function $f$ over $s_2$ divides the greatest common divisor of $f$ over $s_1$.
restricted_cycle_one_param_family_subset_excluded_family
For any parameters $r$ and $n$, the one-parameter family of forbidden cycle-length sets is a subset of the full excluded family.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The global gcd g_r(n) divides the one-parameter gcd G_r(n). -/theorem restricted_cycle_global_gcd_dvd_one_param_gcd (r n : ℕ) :    restricted_cycle_global_gcd r n ∣ restricted_cycle_one_param_gcd r n := by  unfold restricted_cycle_global_gcd restricted_cycle_one_param_gcd  exact Finset.gcd_mono (restricted_cycle_one_param_family_subset_excluded_family r n)
See it in the graphDiscuss this resultChallenge it