AFTD Auto-Formalizing Theoretical Domains

restricted_cycle_card_eq_of_short

theoremverified

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

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.

  1. 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`.

    lines 6–9

    uses restricted_cycle_all_same_cycle_of_short

      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]
  2. 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$.

    lines 10–11

      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.

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