restricted_cycle_count_as_support_sum
If A is contained in the interval of lengths from r+1 through n, the number of permutations avoiding lengths 1 through r and avoiding the lengths in that interval outside A equals the sum of exact-support counts over all subsets of A.
Statement
theorem restricted_cycle_count_as_support_sum (r n : ℕ) (A : Finset ℕ)
(hA : A ⊆ Finset.Icc (r+1) n) :
restricted_cycle_perms_count n (Finset.Icc 1 r ∪ (Finset.Icc (r+1) n \ A)) =
∑ P ∈ A.powerset, restricted_cycle_exact_support_count n P- 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 4
- restricted_cycle_length_supportThe finite set of distinct cycle lengths of a permutation of Fin n, defined by the cardinalities of its SameCycle equivalence classes.…
- restricted_cycle_exact_support_countThe number of permutations of Fin n with set of distinct cycle lengths exactly P, including fixed points as cycles of length 1.
- restricted_cycle_same_cycle_card_boundsThe SameCycle class of any point of Fin n has cardinality at least 1 and at most 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_gcd_eq_support_gcdFor every r and n, the global gcd of counts avoiding cycle lengths 1 through r and any additional subset of lengths up to n equals the gcd…
The proof, explained
The theorem states that counting permutations of n elements avoiding cycle lengths in {1, ..., r} ∪ ({r+1, ..., n} \ A) is equivalent to summing exact-support counts over all subsets P ⊆ A. The proof first expresses this sum of exact-support counts as the number of permutations whose cycle-length support is contained in A, using fiberwise summation over the powerset of A. It then reduces the equality of set sizes to an equivalence of predicates for each individual permutation σ: avoiding the forbidden cycle lengths is equivalent to having all cycle lengths lie in A. This equivalence holds because every cycle length must be an integer between 1 and n, and A is assumed to be a subset of {r+1, ..., n}.
The sum of exact-support counts over all subsets of A equals the number of permutations whose cycle-length support is a subset of A.
By definition, the exact-support count for a set P is the number of permutations whose cycle lengths form exactly the set P. Applying fiberwise summation (Finset.sum_card_fiberwise_eq_card_filter) over all P in the powerset of A, the sum of these fiber counts equals the total number of permutations whose cycle-length support belongs to the powerset of A.
uses
Finset.sum_card_fiberwise_eq_card_filterclassical simp only [restricted_cycle_exact_support_count] rw [Finset.sum_card_fiberwise_eq_card_filter]
It suffices to show that for every permutation σ, avoiding cycle lengths in {1, ..., r} ∪ ({r+1, ..., n} \ A) is equivalent to having cycle-length support in the powerset of A.
Unfolding the definition of restricted_cycle_perms_count, the goal equates the cardinalities of two filtered sets of permutations. To show their sizes are equal, congr 1 reduces the goal to showing the sets themselves are identical, which Finset.filter_congr further reduces to showing that their membership conditions are logically equivalent for every permutation σ.
uses
Finset.filter_congrunfold restricted_cycle_perms_count congr 1 apply Finset.filter_congr
For any permutation σ, having cycle-length support in the powerset of A is equivalent to requiring that every element's cycle length belongs to A.
Introduce σ. By definition, the cycle-length support of σ is the image of the elementwise cycle-length function. The image is a subset of A (that is, an element of the powerset of A) if and only if the cycle length of every element x belongs to A, using Finset.mem_powerset and Finset.image_subset_iff.
uses
Finset.mem_coe,Finset.mem_powerset,Finset.image_subset_iff,Finset.mem_univ,forall_constintro σ hσ simp only [Finset.mem_coe, Finset.mem_powerset, restricted_cycle_length_support, Finset.image_subset_iff, Finset.mem_univ, forall_const]
It suffices to prove each implication of the equivalence separately.
Split the if-and-only-if statement into two implications.
constructorIf a permutation avoids all cycle lengths in {1, ..., r} ∪ ({r+1, ..., n} \ A), then the cycle length of every element belongs to A.
Assume σ avoids the forbidden cycle lengths and consider an arbitrary element x. By restricted_cycle_same_cycle_card_bounds, the cycle length of x is between 1 and n. Suppose for contradiction that this length does not belong to A. If it were at most r, it would lie in {1, ..., r}, which is forbidden; thus linear arithmetic shows it must be at least r + 1. But then it lies in {r+1, ..., n} \ A, which is also forbidden, yielding a contradiction.
uses
restricted_cycle_same_cycle_card_bounds,Finset.mem_union,Finset.mem_sdiff,Finset.mem_Icc· intro h x have hx := restricted_cycle_same_cycle_card_bounds n σ x specialize h x simp only [Finset.mem_union, Finset.mem_sdiff, Finset.mem_Icc] at h hx by_contra hnot apply h right exact ⟨⟨by omega, hx.2⟩, hnot⟩
Conversely, if every element's cycle length belongs to A, then no element's cycle length lies in {1, ..., r} ∪ ({r+1, ..., n} \ A).
Assume every element's cycle length belongs to A. Because A ⊆ {r+1, ..., n}, every cycle length is at least r + 1. If any cycle length were in {1, ..., r}, this would contradict being at least r + 1 by linear arithmetic. If it were in {r+1, ..., n} \ A, it would not belong to A, contradicting the assumption that all cycle lengths lie in A.
uses
Finset.mem_union,Finset.mem_sdiff,Finset.mem_Icc· intro h x hx have hAx := hA (h x) simp only [Finset.mem_union, Finset.mem_sdiff, Finset.mem_Icc] at hx hAx rcases hx with hx | hx · omega · exact hx.2 (h x)
Finset.sum_card_fiberwise_eq_card_filter- Summing the cardinalities of the fibers of a map g over a target set t equals the cardinality of the preimage of t in the source set.
Finset.filter_congr- Two filtered finite sets are equal if their filtering predicates are logically equivalent on all elements of the base set.
Finset.mem_coe- An element belongs to a finite set coerced to a set if and only if it belongs to the finite set.
Finset.mem_powerset- A finite set belongs to the powerset of another finite set if and only if it is a subset of it.
Finset.image_subset_iff- The image of a finite set under a function is a subset of a target set if and only if the image of every element lies in the target set.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set univ.
forall_const- A universal quantification over a nonempty domain whose body is constant is equivalent to the body itself.
restricted_cycle_same_cycle_card_bounds- The size of the cycle containing any element x under a permutation of n elements is an integer between 1 and n inclusive.
Finset.mem_union- An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
Finset.mem_sdiff- An element belongs to the difference of two finite sets if and only if it belongs to the first and not the second.
Finset.mem_Icc- An integer belongs to the closed interval [a, b] if and only if it is between a and b inclusive.
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_as_support_sum (r n : ℕ) (A : Finset ℕ) (hA : A ⊆ Finset.Icc (r+1) n) : restricted_cycle_perms_count n (Finset.Icc 1 r ∪ (Finset.Icc (r+1) n \ A)) = ∑ P ∈ A.powerset, restricted_cycle_exact_support_count n P := by classical simp only [restricted_cycle_exact_support_count] rw [Finset.sum_card_fiberwise_eq_card_filter] unfold restricted_cycle_perms_count congr 1 apply Finset.filter_congr intro σ hσ simp only [Finset.mem_coe, Finset.mem_powerset, restricted_cycle_length_support, Finset.image_subset_iff, Finset.mem_univ, forall_const] constructor · intro h x have hx := restricted_cycle_same_cycle_card_bounds n σ x specialize h x simp only [Finset.mem_union, Finset.mem_sdiff, Finset.mem_Icc] at h hx by_contra hnot apply h right exact ⟨⟨by omega, hx.2⟩, hnot⟩ · intro h x hx have hAx := hA (h x) simp only [Finset.mem_union, Finset.mem_sdiff, Finset.mem_Icc] at hx hAx rcases hx with hx | hx · omega · exact hx.2 (h x)