restricted_cycle_count_zero_or_base_of_short
For 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 otherwise equals the count excluding only lengths 1 through r.
Statement
theorem restricted_cycle_count_zero_or_base_of_short (r n : ℕ) (hn0 : 0 < n) (hn : n < 2 * (r+1)) (S : Finset ℕ) (hS : Finset.Icc 1 r ⊆ S) : restricted_cycle_perms_count n S = if n ∈ S then 0 else restricted_cycle_perms_count n (Finset.Icc 1 r)
- 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 2
- restricted_cycle_card_eq_of_shortIf n is less than 2(r+1), the cycle containing any point of a permutation avoiding lengths 1 through r has cardinality n.
- 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…
- Used by 1
- 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.
The proof, explained
The proof proceeds by case analysis on whether n ∈ S. The key observation is that when n < 2(r+1), any permutation with no cycle lengths in {1, ..., r} must consist entirely of cycles of length n (by restricted_cycle_card_eq_of_short). Consequently, if n ∈ S, no such permutation can exist and the count is 0; while if n ∉ S, avoiding S is equivalent to avoiding {1, ..., r}, so the two counts coincide.
The problem reduces to two cases: n ∈ S and n ∉ S.
We unfold the definition of restricted_cycle_perms_count, which counts permutations whose cycle lengths all avoid the excluded set S. Splitting into cases on the condition n ∈ S, we must show that the count is 0 if n ∈ S, and that it equals the count excluding {1, ..., r} if n ∉ S.
classical unfold restricted_cycle_perms_count split_ifs with hmem
When n ∈ S, it suffices to show that no permutation avoids all cycle lengths in S.
To prove the count is zero, it suffices to show that the set of valid permutations is empty. We assume for contradiction that there exists a permutation σ in this set. Simplifying the set membership condition yields that for every element x, the cycle containing x has length not in S.
uses
Finset.card_eq_zero.mpr,Finset.eq_empty_iff_forall_notMem.mpr,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_coe· apply Finset.card_eq_zero.mpr apply Finset.eq_empty_iff_forall_notMem.mpr intro σ hσ simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_coe] at hσ
The permutation σ has no cycle of length between 1 and r.
Because the excluded set S contains the interval {1, ..., r}, any cycle length that avoids S must also avoid {1, ..., r}.
have hb : ∀ x : Fin n, (Finset.univ.filter fun y => σ.SameCycle x y).card ∉ Finset.Icc 1 r := by intro x hx exact hσ x (hS hx)
A contradiction arises because every element belongs to an n-cycle, but n ∈ S.
Since n > 0, we can pick the element 0. Because n < 2(r+1) and σ has no cycle length in {1, ..., r}, restricted_cycle_card_eq_of_short implies that the cycle containing 0 has length exactly n. But σ avoids all cycle lengths in S, meaning n ∉ S, which contradicts the case assumption n ∈ S.
uses
restricted_cycle_card_eq_of_shortlet x : Fin n := ⟨0, hn0⟩ apply hσ x simpa only [restricted_cycle_card_eq_of_short r n hn σ hb x] using hmem
When n ∉ S, it suffices to show that avoiding cycle lengths in S is equivalent to avoiding cycle lengths in {1, ..., r}.
To show that the two sets of permutations have the same cardinality, it suffices to show that they are identical as sets. By filter congruence, this reduces to showing that for any permutation σ, the condition that all its cycle lengths avoid S is logically equivalent to the condition that all its cycle lengths avoid {1, ..., r}.
uses
Finset.filter_congr,Finset.mem_coe· congr 1 apply Finset.filter_congr intro σ hσ simp only [Finset.mem_coe] constructor
If σ has no cycle lengths in S, then it has no cycle lengths in {1, ..., r}.
Since {1, ..., r} ⊆ S, any cycle length outside S is automatically outside {1, ..., r}.
· intro h x hx exact h x (hS hx)
If σ has no cycle lengths in {1, ..., r}, then it has no cycle lengths in S.
Suppose σ has no cycle lengths in {1, ..., r}. Since n < 2(r+1), restricted_cycle_card_eq_of_short ensures that every cycle of σ has length n. Since n ∉ S, no cycle length belongs to S.
uses
restricted_cycle_card_eq_of_short· intro h x simpa only [restricted_cycle_card_eq_of_short r n hn σ h x] using hmem
Finset.card_eq_zero.mpr- A finite set has cardinality zero if it is empty.
Finset.eq_empty_iff_forall_notMem.mpr- A set is empty if no element belongs to it.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
true_and- The conjunction True ∧ P simplifies to P.
Finset.mem_coe- Membership in the set coercion of a finset is equivalent to membership in the finset.
Finset.filter_congr- Two filtered finsets are equal if their defining predicates agree on all elements of the base finset.
restricted_cycle_card_eq_of_short- If n < 2(r+1) and a permutation of an n-element set has no cycle lengths in {1, ..., r}, then every cycle has length n.
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_count_zero_or_base_of_short (r n : ℕ) (hn0 : 0 < n) (hn : n < 2 * (r+1)) (S : Finset ℕ) (hS : Finset.Icc 1 r ⊆ S) : restricted_cycle_perms_count n S = if n ∈ S then 0 else restricted_cycle_perms_count n (Finset.Icc 1 r) := by classical unfold restricted_cycle_perms_count split_ifs with hmem · apply Finset.card_eq_zero.mpr apply Finset.eq_empty_iff_forall_notMem.mpr intro σ hσ simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_coe] at hσ have hb : ∀ x : Fin n, (Finset.univ.filter fun y => σ.SameCycle x y).card ∉ Finset.Icc 1 r := by intro x hx exact hσ x (hS hx) let x : Fin n := ⟨0, hn0⟩ apply hσ x simpa only [restricted_cycle_card_eq_of_short r n hn σ hb x] using hmem · congr 1 apply Finset.filter_congr intro σ hσ simp only [Finset.mem_coe] constructor · intro h x hx exact h x (hS hx) · intro h x simpa only [restricted_cycle_card_eq_of_short r n hn σ h x] using hmem