restricted_cycle_same_cycle_card_bounds
The SameCycle class of any point of Fin n has cardinality at least 1 and at most n.
Statement
theorem restricted_cycle_same_cycle_card_bounds (n : ℕ) (σ : Equiv.Perm (Fin n)) (x : Fin n) : (Finset.univ.filter fun y => σ.SameCycle x y).card ∈ Finset.Icc 1 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- Used by 2
- restricted_cycle_count_as_support_sumIf 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…
- restricted_cycle_all_same_cycle_of_shortIf n is less than 2(r+1), any permutation of Fin n avoiding cycle lengths 1 through r has every two points in the same cycle.
The proof, explained
The proof bounds the size of the cycle containing x by reducing interval membership to separate lower and upper bounds. The lower bound of 1 follows because the cycle contains x itself by reflexivity of the same-cycle relation, making it nonempty. The upper bound of n follows because the cycle is a subset of the full domain Fin n, which has n elements.
It suffices to show that the cycle of x has cardinality at least 1 and at most n.
After enabling classical reasoning, the goal of showing that the cardinality of the cycle class belongs to the closed interval [1, n] is transformed by Finset.mem_Icc.mpr into the two inequalities 1 ≤ |{y | σ.SameCycle x y}| and |{y | σ.SameCycle x y}| ≤ n. The constructor tactic then splits the conjunction into separate goals for the lower and upper bounds.
uses
Finset.mem_Icc.mprclassical apply Finset.mem_Icc.mpr constructor
The cycle of x has cardinality at least 1.
By Finset.one_le_card.mpr, a finite set has cardinality at least 1 if and only if it is nonempty. Since the cycle relation is reflexive (Equiv.Perm.SameCycle.refl), x itself belongs to the cycle, providing an explicit witness that the set is nonempty.
uses
Finset.one_le_card.mpr,Equiv.Perm.SameCycle.refl· apply Finset.one_le_card.mpr exact ⟨x, by simp [Equiv.Perm.SameCycle.refl]⟩
The cycle of x has cardinality at most n.
The cycle is defined by filtering the universal set on Fin n, so it is a subset of Finset.univ by Finset.filter_subset. By Finset.card_le_card, its cardinality is bounded by the cardinality of Finset.univ, which simplifies directly to n.
uses
Finset.card_le_card,Finset.filter_subset· exact (Finset.card_le_card (Finset.filter_subset _ _)).trans_eq (by simp)
Finset.mem_Icc.mpr- An element belongs to the closed interval [a, b] if it is bounded between a and b (that is, a ≤ x and x ≤ b).
Finset.one_le_card.mpr- A finite set has cardinality at least 1 if it is nonempty.
Equiv.Perm.SameCycle.refl- The same-cycle relation is reflexive: every element is in the same cycle as itself.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to the cardinality of the superset.
Finset.filter_subset- Filtering a finite set by a predicate yields a subset of the original set.
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_same_cycle_card_bounds (n : ℕ) (σ : Equiv.Perm (Fin n)) (x : Fin n) : (Finset.univ.filter fun y => σ.SameCycle x y).card ∈ Finset.Icc 1 n := by classical apply Finset.mem_Icc.mpr constructor · apply Finset.one_le_card.mpr exact ⟨x, by simp [Equiv.Perm.SameCycle.refl]⟩ · exact (Finset.card_le_card (Finset.filter_subset _ _)).trans_eq (by simp)