AFTD Auto-Formalizing Theoretical Domains

restricted_cycle_same_cycle_card_bounds

theoremverified

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

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.

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

    lines 3–5

    uses Finset.mem_Icc.mpr

      classical
      apply Finset.mem_Icc.mpr
      constructor
  2. 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.

    lines 6–7

    uses Finset.one_le_card.mpr, Equiv.Perm.SameCycle.refl

      · apply Finset.one_le_card.mpr
        exact ⟨x, by simp [Equiv.Perm.SameCycle.refl]⟩
  3. 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.

    line 8

    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

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