restricted_cycle_perms_count_antitone
Adding excluded cycle lengths can only decrease the number of qualifying permutations.
Statement
theorem restricted_cycle_perms_count_antitone (n : ℕ) (S T : Finset ℕ) (h : S ⊆ T) :
restricted_cycle_perms_count n T ≤ restricted_cycle_perms_count n S- 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 1
- 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…
The proof, explained
By definition, `restricted_cycle_perms_count n S` counts permutations of n elements whose cycle lengths avoid the set S. When S ⊆ T, any permutation whose cycle lengths avoid T necessarily avoids S as well. Therefore, the set of qualifying permutations for T is a subset of that for S, and the inequality follows because the cardinality of a subset cannot exceed the cardinality of the superset.
It suffices to show that any permutation with cycle lengths avoiding T also has cycle lengths avoiding S.
Unfolding the definition of `restricted_cycle_perms_count`, each quantity is the cardinality of the set of permutations whose cycle lengths avoid the given set of excluded lengths. By `Finset.card_le_card`, showing that the size for T is at most that for S reduces to showing the inclusion of the corresponding sets of permutations.
uses
Finset.card_le_cardunfold restricted_cycle_perms_count apply Finset.card_le_card
Given a permutation σ whose cycle lengths all avoid T, it suffices to prove that every cycle length of σ avoids S.
We introduce an arbitrary permutation σ in the set for T. Simplifying the condition for membership in the filtered universal set using `Finset.mem_filter`, `Finset.mem_univ`, and `true_and`, our hypothesis becomes that the cycle size of every element x is not in T, and our goal is to show the cycle size of every x is not in S.
uses
Finset.mem_filter,Finset.mem_univ,true_andintro σ hσ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hσ ⊢
No cycle length of σ can belong to S.
For any element x, suppose for contradiction that the size of the cycle containing x belongs to S. Since S ⊆ T by hypothesis h, this cycle size would also belong to T, contradicting the assumption that σ has no cycle lengths in T.
intro x hx exact hσ x (h hx)
Finset.card_le_card- A subset of a finite set has cardinality at most that of the superset.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the base set and satisfies the filter predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal set.
true_and- The conjunction of True and p simplifies to p.
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_perms_count_antitone (n : ℕ) (S T : Finset ℕ) (h : S ⊆ T) : restricted_cycle_perms_count n T ≤ restricted_cycle_perms_count n S := by unfold restricted_cycle_perms_count apply Finset.card_le_card intro σ hσ simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hσ ⊢ intro x hx exact hσ x (h hx)