AFTD Auto-Formalizing Theoretical Domains

restricted_cycle_count_as_support_sum

theoremverified

If A is contained in the interval of lengths from r+1 through n, the number of permutations avoiding lengths 1 through r and avoiding the lengths in that interval outside A equals the sum of exact-support counts over all subsets of A.

Statement

theorem restricted_cycle_count_as_support_sum (r n : ℕ) (A : Finset ℕ)
    (hA : A ⊆ Finset.Icc (r+1) n) :
    restricted_cycle_perms_count n (Finset.Icc 1 r ∪ (Finset.Icc (r+1) n \ A)) =
      ∑ P ∈ A.powerset, restricted_cycle_exact_support_count n P
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 4
Used by 1

The proof, explained

The theorem states that counting permutations of n elements avoiding cycle lengths in {1, ..., r} ∪ ({r+1, ..., n} \ A) is equivalent to summing exact-support counts over all subsets P ⊆ A. The proof first expresses this sum of exact-support counts as the number of permutations whose cycle-length support is contained in A, using fiberwise summation over the powerset of A. It then reduces the equality of set sizes to an equivalence of predicates for each individual permutation σ: avoiding the forbidden cycle lengths is equivalent to having all cycle lengths lie in A. This equivalence holds because every cycle length must be an integer between 1 and n, and A is assumed to be a subset of {r+1, ..., n}.

  1. The sum of exact-support counts over all subsets of A equals the number of permutations whose cycle-length support is a subset of A.

    By definition, the exact-support count for a set P is the number of permutations whose cycle lengths form exactly the set P. Applying fiberwise summation (Finset.sum_card_fiberwise_eq_card_filter) over all P in the powerset of A, the sum of these fiber counts equals the total number of permutations whose cycle-length support belongs to the powerset of A.

    lines 5–7

    uses Finset.sum_card_fiberwise_eq_card_filter

      classical
      simp only [restricted_cycle_exact_support_count]
      rw [Finset.sum_card_fiberwise_eq_card_filter]
  2. It suffices to show that for every permutation σ, avoiding cycle lengths in {1, ..., r} ∪ ({r+1, ..., n} \ A) is equivalent to having cycle-length support in the powerset of A.

    Unfolding the definition of restricted_cycle_perms_count, the goal equates the cardinalities of two filtered sets of permutations. To show their sizes are equal, congr 1 reduces the goal to showing the sets themselves are identical, which Finset.filter_congr further reduces to showing that their membership conditions are logically equivalent for every permutation σ.

    lines 8–10

    uses Finset.filter_congr

      unfold restricted_cycle_perms_count
      congr 1
      apply Finset.filter_congr
  3. For any permutation σ, having cycle-length support in the powerset of A is equivalent to requiring that every element's cycle length belongs to A.

    Introduce σ. By definition, the cycle-length support of σ is the image of the elementwise cycle-length function. The image is a subset of A (that is, an element of the powerset of A) if and only if the cycle length of every element x belongs to A, using Finset.mem_powerset and Finset.image_subset_iff.

    lines 11–13

    uses Finset.mem_coe, Finset.mem_powerset, Finset.image_subset_iff, Finset.mem_univ, forall_const

      intro σ hσ
      simp only [Finset.mem_coe, Finset.mem_powerset, restricted_cycle_length_support, Finset.image_subset_iff,
        Finset.mem_univ, forall_const]
  4. It suffices to prove each implication of the equivalence separately.

    Split the if-and-only-if statement into two implications.

    line 14

      constructor
  5. If a permutation avoids all cycle lengths in {1, ..., r} ∪ ({r+1, ..., n} \ A), then the cycle length of every element belongs to A.

    Assume σ avoids the forbidden cycle lengths and consider an arbitrary element x. By restricted_cycle_same_cycle_card_bounds, the cycle length of x is between 1 and n. Suppose for contradiction that this length does not belong to A. If it were at most r, it would lie in {1, ..., r}, which is forbidden; thus linear arithmetic shows it must be at least r + 1. But then it lies in {r+1, ..., n} \ A, which is also forbidden, yielding a contradiction.

    lines 15–22

    uses restricted_cycle_same_cycle_card_bounds, Finset.mem_union, Finset.mem_sdiff, Finset.mem_Icc

      · intro h x
        have hx := restricted_cycle_same_cycle_card_bounds n σ x
        specialize h x
        simp only [Finset.mem_union, Finset.mem_sdiff, Finset.mem_Icc] at h hx
        by_contra hnot
        apply h
        right
        exact ⟨⟨by omega, hx.2⟩, hnot⟩
  6. Conversely, if every element's cycle length belongs to A, then no element's cycle length lies in {1, ..., r} ∪ ({r+1, ..., n} \ A).

    Assume every element's cycle length belongs to A. Because A ⊆ {r+1, ..., n}, every cycle length is at least r + 1. If any cycle length were in {1, ..., r}, this would contradict being at least r + 1 by linear arithmetic. If it were in {r+1, ..., n} \ A, it would not belong to A, contradicting the assumption that all cycle lengths lie in A.

    lines 23–28

    uses Finset.mem_union, Finset.mem_sdiff, Finset.mem_Icc

      · intro h x hx
        have hAx := hA (h x)
        simp only [Finset.mem_union, Finset.mem_sdiff, Finset.mem_Icc] at hx hAx
        rcases hx with hx | hx
        · omega
        · exact hx.2 (h x)
Finset.sum_card_fiberwise_eq_card_filter
Summing the cardinalities of the fibers of a map g over a target set t equals the cardinality of the preimage of t in the source set.
Finset.filter_congr
Two filtered finite sets are equal if their filtering predicates are logically equivalent on all elements of the base set.
Finset.mem_coe
An element belongs to a finite set coerced to a set if and only if it belongs to the finite set.
Finset.mem_powerset
A finite set belongs to the powerset of another finite set if and only if it is a subset of it.
Finset.image_subset_iff
The image of a finite set under a function is a subset of a target set if and only if the image of every element lies in the target set.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set univ.
forall_const
A universal quantification over a nonempty domain whose body is constant is equivalent to the body itself.
restricted_cycle_same_cycle_card_bounds
The size of the cycle containing any element x under a permutation of n elements is an integer between 1 and n inclusive.
Finset.mem_union
An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
Finset.mem_sdiff
An element belongs to the difference of two finite sets if and only if it belongs to the first and not the second.
Finset.mem_Icc
An integer belongs to the closed interval [a, b] if and only if it is between a and b inclusive.

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_as_support_sum (r n : ℕ) (A : Finset ℕ)    (hA : A ⊆ Finset.Icc (r+1) n) :    restricted_cycle_perms_count n (Finset.Icc 1 r ∪ (Finset.Icc (r+1) n \ A)) =      ∑ P ∈ A.powerset, restricted_cycle_exact_support_count n P := by  classical  simp only [restricted_cycle_exact_support_count]  rw [Finset.sum_card_fiberwise_eq_card_filter]  unfold restricted_cycle_perms_count  congr 1  apply Finset.filter_congr  intro σ hσ  simp only [Finset.mem_coe, Finset.mem_powerset, restricted_cycle_length_support, Finset.image_subset_iff,    Finset.mem_univ, forall_const]  constructor  · intro h x    have hx := restricted_cycle_same_cycle_card_bounds n σ x    specialize h x    simp only [Finset.mem_union, Finset.mem_sdiff, Finset.mem_Icc] at h hx    by_contra hnot    apply h    right    exact ⟨⟨by omega, hx.2⟩, hnot⟩  · intro h x hx    have hAx := hA (h x)    simp only [Finset.mem_union, Finset.mem_sdiff, Finset.mem_Icc] at hx hAx    rcases hx with hx | hx    · omega    · exact hx.2 (h x)
See it in the graphDiscuss this resultChallenge it