restricted_cycle_card_eq_of_short
If n is less than 2(r+1), the cycle containing any point of a permutation avoiding lengths 1 through r has cardinality n.
Statement
theorem restricted_cycle_card_eq_of_short (r n : ℕ) (hn : n < 2 * (r+1)) (σ : Equiv.Perm (Fin n)) (hσ : ∀ x : Fin n, (Finset.univ.filter fun y => σ.SameCycle x y).card ∉ Finset.Icc 1 r) (x : Fin n) : (Finset.univ.filter fun y => σ.SameCycle x y).card = 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 1
- 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.
- Used by 1
- 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…
The proof, explained
The proof establishes that the cycle containing $x$ is the entire set $\mathrm{Fin}\; n$, so its cardinality must be $n$. The crucial step uses the auxiliary lemma `restricted_cycle_all_same_cycle_of_short`, which shows that when $n < 2(r+1)$ and all cycles avoid lengths from $1$ through $r$, every element of $\mathrm{Fin}\; n$ belongs to a single cycle.
The cycle containing $x$ is the entire domain $\mathrm{Fin}\; n$.
We show that the set $\{y \in \mathrm{Fin}\; n \mid \sigma.\text{SameCycle}(x, y)\}$ equals the full universal set $\mathrm{Finset.univ}$. By extensionality, this requires that every $y \in \mathrm{Fin}\; n$ lies in the same cycle as $x$, which is provided by the lemma `restricted_cycle_all_same_cycle_of_short`.
uses
restricted_cycle_all_same_cycle_of_shortclassical have h : (Finset.univ.filter fun y => σ.SameCycle x y) = Finset.univ := by ext y simp [restricted_cycle_all_same_cycle_of_short r n hn σ hσ x y]
The cardinality of the cycle containing $x$ is $n$.
Rewriting the cycle using the fact that it equals $\mathrm{Finset.univ}$ leaves the goal of computing the cardinality of the full domain $\mathrm{Fin}\; n$, which simplifies directly to $n$.
rw [h] simp
restricted_cycle_all_same_cycle_of_short- If a permutation on an $n$-element set avoids cycle lengths between $1$ and $r$, and $n < 2(r+1)$, then all elements belong to the same cycle.
- The tactic `classical` on line 6 enables classical logic so that Lean can treat arbitrary predicates as decidable; this is a formal bookkeeping detail with no mathematical counterpart.
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_card_eq_of_short (r n : ℕ) (hn : n < 2 * (r+1)) (σ : Equiv.Perm (Fin n)) (hσ : ∀ x : Fin n, (Finset.univ.filter fun y => σ.SameCycle x y).card ∉ Finset.Icc 1 r) (x : Fin n) : (Finset.univ.filter fun y => σ.SameCycle x y).card = n := by classical have h : (Finset.univ.filter fun y => σ.SameCycle x y) = Finset.univ := by ext y simp [restricted_cycle_all_same_cycle_of_short r n hn σ hσ x y] rw [h] simp