restricted_cycle_all_same_cycle_of_short
If 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.
Statement
theorem restricted_cycle_all_same_cycle_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 y : Fin n, σ.SameCycle x y
- 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_same_cycle_card_boundsThe SameCycle class of any point of Fin n has cardinality at least 1 and at most n.
- Used by 1
- 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.
The proof, explained
The proof proceeds by contradiction. If two elements belonged to distinct cycles, each cycle would have size at least r + 1 because cycle lengths must be at least 1 and cannot fall in {1, ..., r}. Since distinct cycles are disjoint, their union would have size at least 2(r + 1), contradicting the fact that the total number of elements n is strictly less than 2(r + 1).
For every element x, the cycle containing x contains at least r + 1 elements.
Every cycle has at least one element by `restricted_cycle_same_cycle_card_bounds` and `Finset.mem_Icc.mp`. By assumption `hσ`, the cycle size does not lie in the interval [1, r], as unpacked by `Finset.mem_Icc`. Linear integer arithmetic (`omega`) deduces that the cycle size must therefore be at least r + 1.
uses
restricted_cycle_same_cycle_card_bounds,Finset.mem_Icc.mp,Finset.mem_Iccclassical have hlarge (x : Fin n) : r+1 ≤ (Finset.univ.filter fun y => σ.SameCycle x y).card := by have hb := (Finset.mem_Icc.mp (restricted_cycle_same_cycle_card_bounds n σ x)).1 have hx := hσ x simp only [Finset.mem_Icc] at hx omega
Assume for contradiction that there exist two points x and y in different cycles.
We introduce arbitrary points x and y and assume the negation of σ.SameCycle x y for a proof by contradiction (`by_contra`).
intro x y by_contra hxy
The cycle of x and the cycle of y are disjoint.
Using `Finset.disjoint_left.mpr`, we suppose there is an element z belonging to both cycles. Unfolding membership in the filtered universal finsets using `Finset.mem_filter`, `Finset.mem_univ`, and `true_and`, we have that x is in the same cycle as z, and y is in the same cycle as z. By symmetry and transitivity of the cycle relation, x and y must be in the same cycle, contradicting the assumption.
uses
Finset.disjoint_left.mpr,Finset.mem_filter,Finset.mem_univ,true_andhave hd : Disjoint (Finset.univ.filter fun z => σ.SameCycle x z) (Finset.univ.filter fun z => σ.SameCycle y z) := by apply Finset.disjoint_left.mpr intro z hx hy simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx hy exact hxy (hx.trans hy.symm)
The cardinality of the union of the two cycles equals the sum of their individual cardinalities.
Because the two cycles are disjoint, `Finset.card_union_of_disjoint` equates the size of their union to the sum of their sizes.
uses
Finset.card_union_of_disjointhave hc := Finset.card_union_of_disjoint hdThe cardinality of the union of the two cycles is at most n.
The union is a subset of all elements of Fin n (`Finset.subset_univ`), so by `Finset.card_le_card` its cardinality is bounded by that of Finset.univ, which simplifies to n.
uses
Finset.card_le_card,Finset.subset_univhave hu : ((Finset.univ.filter fun z => σ.SameCycle x z) ∪ (Finset.univ.filter fun z => σ.SameCycle y z)).card ≤ n := by calc _ ≤ (Finset.univ : Finset (Fin n)).card := Finset.card_le_card (Finset.subset_univ _) _ = n := by simp
A contradiction is reached, proving that all elements lie in the same cycle. automation
Specialising the lower bound to x and y gives that each cycle has at least r + 1 elements. Their disjoint union therefore has size at least 2(r + 1), but its size is also at most n < 2(r + 1). Linear arithmetic (`omega`) derives False from this contradiction.
have hx := hlarge x have hy := hlarge y omega
Finset.mem_Icc.mp- An element of a closed interval [a, b] satisfies both a ≤ x and x ≤ b.
restricted_cycle_same_cycle_card_bounds- For any permutation σ of Fin n and any element x, the size of the cycle containing x is between 1 and n inclusive.
Finset.mem_Icc- An element x belongs to the closed interval [a, b] if and only if a ≤ x and x ≤ b.
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element of the first set belongs to the second.
Finset.mem_filter- An element belongs to a filtered finset 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 `Finset.univ`.
true_and- The proposition `True ∧ p` simplifies to `p`.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most the cardinality of the other.
Finset.subset_univ- Every finite set of elements of a finite type is a subset of `Finset.univ`.
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_all_same_cycle_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 y : Fin n, σ.SameCycle x y := by classical have hlarge (x : Fin n) : r+1 ≤ (Finset.univ.filter fun y => σ.SameCycle x y).card := by have hb := (Finset.mem_Icc.mp (restricted_cycle_same_cycle_card_bounds n σ x)).1 have hx := hσ x simp only [Finset.mem_Icc] at hx omega intro x y by_contra hxy have hd : Disjoint (Finset.univ.filter fun z => σ.SameCycle x z) (Finset.univ.filter fun z => σ.SameCycle y z) := by apply Finset.disjoint_left.mpr intro z hx hy simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx hy exact hxy (hx.trans hy.symm) have hc := Finset.card_union_of_disjoint hd have hu : ((Finset.univ.filter fun z => σ.SameCycle x z) ∪ (Finset.univ.filter fun z => σ.SameCycle y z)).card ≤ n := by calc _ ≤ (Finset.univ : Finset (Fin n)).card := Finset.card_le_card (Finset.subset_univ _) _ = n := by simp have hx := hlarge x have hy := hlarge y omega