restricted_cycle_global_gcd_dvd_one_param_gcd
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
- 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…
- restricted_cycle_one_param_family_subset_excluded_familyFor any natural numbers r and n, the one-parameter family restricted_cycle_one_param_family r n is a subset of…
- restricted_cycle_one_param_familyThe one-parameter family of subsets of {1, ..., n} consisting of {1, ..., r, k} for r < k ≤ n together with {1, ..., r}.
- restricted_cycle_perms_countFor a natural number n and a finite set S of natural numbers, the number of permutations σ of Fin n such that for every element x of Fin…
- restricted_cycle_excluded_familyThe family of all subsets of {1, ..., n} containing {1, ..., r}.
- Used by 4
- restricted_cycle_global_eq_iff_support_dvdFor every r and n, the global and one-parameter gcds are equal if and only if the one-parameter gcd divides the exact cycle-support count…
- restricted_cycle_global_eq_of_shortFor every r and every positive n less than 2(r+1), the global restricted-cycle gcd equals its one-parameter gcd.
- restricted_cycle_global_eq_iff_family_dvdFor every r and n, equality of the global and one-parameter gcds is equivalent to divisibility of every excluded-family count by the…
- restricted_cycle_global_gcd_eq_one_param_of_family_dvdIf the one-parameter gcd G_3(n) divides the restricted count a_S(n) attached to every set S = {1,2,3} ∪ T of the excluded family, then the…
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.
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.
uses
Finset.gcd_mono,restricted_cycle_one_param_family_subset_excluded_familyunfold 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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)