AFTD Auto-Formalizing Theoretical Domains

restricted_cycle_count_zero_or_base_of_short

theoremverified

For 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 otherwise equals the count excluding only lengths 1 through r.

Statement

theorem restricted_cycle_count_zero_or_base_of_short (r n : ℕ) (hn0 : 0 < n)
    (hn : n < 2 * (r+1)) (S : Finset ℕ) (hS : Finset.Icc 1 r ⊆ S) :
    restricted_cycle_perms_count n S =
      if n ∈ S then 0 else restricted_cycle_perms_count n (Finset.Icc 1 r)
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 2
  • 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.
  • restricted_cycle_perms_countFor a natural number n and a finite set S of natural numbers, the number of permutations σ of Fin n such that for every element x of Fin…
Used by 1

The proof, explained

The proof proceeds by case analysis on whether n ∈ S. The key observation is that when n < 2(r+1), any permutation with no cycle lengths in {1, ..., r} must consist entirely of cycles of length n (by restricted_cycle_card_eq_of_short). Consequently, if n ∈ S, no such permutation can exist and the count is 0; while if n ∉ S, avoiding S is equivalent to avoiding {1, ..., r}, so the two counts coincide.

  1. The problem reduces to two cases: n ∈ S and n ∉ S.

    We unfold the definition of restricted_cycle_perms_count, which counts permutations whose cycle lengths all avoid the excluded set S. Splitting into cases on the condition n ∈ S, we must show that the count is 0 if n ∈ S, and that it equals the count excluding {1, ..., r} if n ∉ S.

    lines 5–7

      classical
      unfold restricted_cycle_perms_count
      split_ifs with hmem
  2. When n ∈ S, it suffices to show that no permutation avoids all cycle lengths in S.

    To prove the count is zero, it suffices to show that the set of valid permutations is empty. We assume for contradiction that there exists a permutation σ in this set. Simplifying the set membership condition yields that for every element x, the cycle containing x has length not in S.

    lines 8–11

    uses Finset.card_eq_zero.mpr, Finset.eq_empty_iff_forall_notMem.mpr, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_coe

      · apply Finset.card_eq_zero.mpr
        apply Finset.eq_empty_iff_forall_notMem.mpr
        intro σ hσ
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_coe] at hσ
  3. The permutation σ has no cycle of length between 1 and r.

    Because the excluded set S contains the interval {1, ..., r}, any cycle length that avoids S must also avoid {1, ..., r}.

    lines 12–15

        have hb : ∀ x : Fin n,
            (Finset.univ.filter fun y => σ.SameCycle x y).card ∉ Finset.Icc 1 r := by
          intro x hx
          exact hσ x (hS hx)
  4. A contradiction arises because every element belongs to an n-cycle, but n ∈ S.

    Since n > 0, we can pick the element 0. Because n < 2(r+1) and σ has no cycle length in {1, ..., r}, restricted_cycle_card_eq_of_short implies that the cycle containing 0 has length exactly n. But σ avoids all cycle lengths in S, meaning n ∉ S, which contradicts the case assumption n ∈ S.

    lines 16–18

    uses restricted_cycle_card_eq_of_short

        let x : Fin n := ⟨0, hn0⟩
        apply hσ x
        simpa only [restricted_cycle_card_eq_of_short r n hn σ hb x] using hmem
  5. When n ∉ S, it suffices to show that avoiding cycle lengths in S is equivalent to avoiding cycle lengths in {1, ..., r}.

    To show that the two sets of permutations have the same cardinality, it suffices to show that they are identical as sets. By filter congruence, this reduces to showing that for any permutation σ, the condition that all its cycle lengths avoid S is logically equivalent to the condition that all its cycle lengths avoid {1, ..., r}.

    lines 19–23

    uses Finset.filter_congr, Finset.mem_coe

      · congr 1
        apply Finset.filter_congr
        intro σ hσ
        simp only [Finset.mem_coe]
        constructor
  6. If σ has no cycle lengths in S, then it has no cycle lengths in {1, ..., r}.

    Since {1, ..., r} ⊆ S, any cycle length outside S is automatically outside {1, ..., r}.

    lines 24–25

        · intro h x hx
          exact h x (hS hx)
  7. If σ has no cycle lengths in {1, ..., r}, then it has no cycle lengths in S.

    Suppose σ has no cycle lengths in {1, ..., r}. Since n < 2(r+1), restricted_cycle_card_eq_of_short ensures that every cycle of σ has length n. Since n ∉ S, no cycle length belongs to S.

    lines 26–27

    uses restricted_cycle_card_eq_of_short

        · intro h x
          simpa only [restricted_cycle_card_eq_of_short r n hn σ h x] using hmem
Finset.card_eq_zero.mpr
A finite set has cardinality zero if it is empty.
Finset.eq_empty_iff_forall_notMem.mpr
A set is empty if no element belongs to it.
Finset.mem_filter
An element belongs to a filtered set 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.
true_and
The conjunction True ∧ P simplifies to P.
Finset.mem_coe
Membership in the set coercion of a finset is equivalent to membership in the finset.
Finset.filter_congr
Two filtered finsets are equal if their defining predicates agree on all elements of the base finset.
restricted_cycle_card_eq_of_short
If n < 2(r+1) and a permutation of an n-element set has no cycle lengths in {1, ..., r}, then every cycle has length n.

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_count_zero_or_base_of_short (r n : ℕ) (hn0 : 0 < n)    (hn : n < 2 * (r+1)) (S : Finset ℕ) (hS : Finset.Icc 1 r ⊆ S) :    restricted_cycle_perms_count n S =      if n ∈ S then 0 else restricted_cycle_perms_count n (Finset.Icc 1 r) := by  classical  unfold restricted_cycle_perms_count  split_ifs with hmem  · apply Finset.card_eq_zero.mpr    apply Finset.eq_empty_iff_forall_notMem.mpr    intro σ hσ    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_coe] at hσ    have hb : ∀ x : Fin n,        (Finset.univ.filter fun y => σ.SameCycle x y).card ∉ Finset.Icc 1 r := by      intro x hx      exact hσ x (hS hx)    let x : Fin n := ⟨0, hn0⟩    apply hσ x    simpa only [restricted_cycle_card_eq_of_short r n hn σ hb x] using hmem  · congr 1    apply Finset.filter_congr    intro σ hσ    simp only [Finset.mem_coe]    constructor    · intro h x hx      exact h x (hS hx)    · intro h x      simpa only [restricted_cycle_card_eq_of_short r n hn σ h x] using hmem
See it in the graphDiscuss this resultChallenge it