restricted_cycle_global_eq_of_short
For every r and every positive n less than 2(r+1), the global restricted-cycle gcd equals its one-parameter gcd.
Statement
theorem restricted_cycle_global_eq_of_short (r n : ℕ) (hn0 : 0 < n) (hn : n < 2 * (r+1)) :
restricted_cycle_global_gcd r n = restricted_cycle_one_param_gcd r n- Source
- Helper for global_gcd_agreement_r_ge_four, OP-746, inbox IN-440. arXiv:2610.40342v1 Proposition 11.3(i) and Appendix A.5 give the support decomposition. No novelty claim; the uniform conjecture in Question 14.10 remains open.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- restricted_cycle_count_zero_or_base_of_shortFor positive n less than 2(r+1) and an excluded set S containing lengths 1 through r, the restricted count is zero when S contains n and…
- restricted_cycle_global_gcd_dvd_one_param_gcdFor 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.
- 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_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_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_excluded_familyThe family of all subsets of {1, ..., n} containing {1, ..., r}.
The proof, explained
The global restricted-cycle gcd always divides the one-parameter gcd because the one-parameter family is a subset of the full excluded family. For the reverse divisibility when n < 2(r+1), every excluded set S ⊇ [1, r] has permutation count either 0 or equal to the count for the base interval [1, r], which implies that the base count divides the global gcd. Since [1, r] itself belongs to the one-parameter family, the one-parameter gcd divides this base count and thus divides the global gcd by transitivity. The two gcds are therefore equal by antisymmetry of divisibility on ℕ.
The permutation count for the base interval [1, r] divides the global restricted-cycle gcd.
We work under classical logic so that set membership is decidable. To show that the count for [1, r] divides the global gcd (the gcd over all sets in the excluded family), it suffices to show that it divides the count for each set S in that family (Finset.dvd_gcd_iff.mpr). By definition, any such set S has the form [1, r] ∪ T for some T ⊆ [r+1, n] (Finset.mem_image.mp). Since [1, r] ⊆ [1, r] ∪ T (Finset.subset_union_left) and n < 2(r+1), the lemma restricted_cycle_count_zero_or_base_of_short shows that the permutation count for [1, r] ∪ T is 0 if n ∈ [1, r] ∪ T and equals the count for [1, r] otherwise. In either case, the base count divides the count for S, as any number divides 0 and any number divides itself.
uses
Finset.dvd_gcd_iff.mpr,Finset.mem_image.mp,restricted_cycle_count_zero_or_base_of_short,Finset.subset_union_leftclassical have hbase : restricted_cycle_perms_count n (Finset.Icc 1 r) ∣ restricted_cycle_global_gcd r n := by apply Finset.dvd_gcd_iff.mpr intro S hS obtain ⟨T, hT, rfl⟩ := Finset.mem_image.mp hS rw [restricted_cycle_count_zero_or_base_of_short r n hn0 hn _ Finset.subset_union_left] split_ifs <;> simp
The one-parameter gcd divides the permutation count for the base interval [1, r].
The one-parameter family is defined by inserting the base interval [1, r] into a collection of single-element extensions. In particular, [1, r] belongs to this family (Finset.mem_insert_self). Because the gcd of a family divides the value at every member of the family (Finset.gcd_dvd), the one-parameter gcd divides the permutation count for [1, r].
uses
Finset.gcd_dvd,Finset.mem_insert_selfhave hone : restricted_cycle_one_param_gcd r n ∣ restricted_cycle_perms_count n (Finset.Icc 1 r) := by apply Finset.gcd_dvd exact Finset.mem_insert_self _ _
The global restricted-cycle gcd equals the one-parameter gcd.
The global gcd divides the one-parameter gcd by restricted_cycle_global_gcd_dvd_one_param_gcd. In the opposite direction, the one-parameter gcd divides the base count, which in turn divides the global gcd, so by transitivity of divisibility the one-parameter gcd divides the global gcd. Because these two natural numbers divide each other, they are equal by Nat.dvd_antisymm.
uses
restricted_cycle_global_gcd_dvd_one_param_gcd,Nat.dvd_antisymmexact Nat.dvd_antisymm (restricted_cycle_global_gcd_dvd_one_param_gcd r n) (hone.trans hbase)
Finset.dvd_gcd_iff.mpr- An element divides the gcd of a finite set of values if it divides each value in the set.
Finset.mem_image.mp- If an element belongs to the image of a set under a function, it is the image of some element of that set.
restricted_cycle_count_zero_or_base_of_short- For 0 < n < 2(r+1), the number of permutations avoiding cycle lengths in a set S containing [1, r] is 0 if n ∈ S and equals the count for [1, r] otherwise.
Finset.subset_union_left- A finite set is a subset of its union with any other set.
Finset.gcd_dvd- The greatest common divisor of a function's values on a finite set divides the function's value at any element of that set.
Finset.mem_insert_self- An element belongs to the set obtained by inserting it into an existing finite set.
Nat.dvd_antisymm- Two natural numbers that divide each other are equal.
restricted_cycle_global_gcd_dvd_one_param_gcd- The global restricted-cycle gcd divides the one-parameter restricted-cycle gcd.
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.
theorem restricted_cycle_global_eq_of_short (r n : ℕ) (hn0 : 0 < n) (hn : n < 2 * (r+1)) : restricted_cycle_global_gcd r n = restricted_cycle_one_param_gcd r n := by classical have hbase : restricted_cycle_perms_count n (Finset.Icc 1 r) ∣ restricted_cycle_global_gcd r n := by apply Finset.dvd_gcd_iff.mpr intro S hS obtain ⟨T, hT, rfl⟩ := Finset.mem_image.mp hS rw [restricted_cycle_count_zero_or_base_of_short r n hn0 hn _ Finset.subset_union_left] split_ifs <;> simp have hone : restricted_cycle_one_param_gcd r n ∣ restricted_cycle_perms_count n (Finset.Icc 1 r) := by apply Finset.gcd_dvd exact Finset.mem_insert_self _ _ exact Nat.dvd_antisymm (restricted_cycle_global_gcd_dvd_one_param_gcd r n) (hone.trans hbase)