AFTD Auto-Formalizing Theoretical Domains

restricted_cycle_all_same_cycle_of_short

theoremverified

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
Used by 1

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).

  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.

    lines 6–11

    uses restricted_cycle_same_cycle_card_bounds, Finset.mem_Icc.mp, Finset.mem_Icc

      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
  2. 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`).

    lines 12–13

      intro x y
      by_contra hxy
  3. 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.

    lines 14–19

    uses Finset.disjoint_left.mpr, Finset.mem_filter, Finset.mem_univ, true_and

      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)
  4. 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.

    line 20

    uses Finset.card_union_of_disjoint

      have hc := Finset.card_union_of_disjoint hd
  5. The 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.

    lines 21–25

    uses Finset.card_le_card, Finset.subset_univ

      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
  6. 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.

    lines 26–28

      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

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
See it in the graphDiscuss this resultChallenge it