AFTD Auto-Formalizing Theoretical Domains

restricted_cycle_global_gcd_eq_support_gcd

theoremverifiedformalization

For every r and n, the global gcd of counts avoiding cycle lengths 1 through r and any additional subset of lengths up to n equals the gcd of the exact cycle-support counts over all supports contained in the interval r+1 through n.

Statement

theorem restricted_cycle_global_gcd_eq_support_gcd (r n : ℕ) :
    restricted_cycle_global_gcd r n =
      (Finset.Icc (r+1) n).powerset.gcd (fun P => restricted_cycle_exact_support_count n P)
Formalizes
arXiv:2610.40342v1 Proposition 11.3(i), first equality, with proof in Appendix A.5. Exact support counts are defined directly as cardinalities of permutations with that support; thus no unproved recurrence or cycle-type counting formula is assumed. This is a published reduction, not a solution of Question 14.10.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
Used by 1

Read back from the Lean

For all natural numbers $r$ and $n$, the restricted cycle global gcd restricted_cycle_global_gcd r n is equal to the greatest common divisor, over all subsets $P \subseteq \{r+1, \dots, n\}$, of restricted_cycle_exact_support_count n P (the number of permutations of $\mathrm{Fin}\ n$ whose set of cycle lengths is exactly $P$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds by a calculation chain that transforms the definition of the global gcd into the gcd of exact support counts. First, the gcd over the family of excluded sets is reindexed over the subsets T ⊆ {r+1, ..., n}, and then rewritten in terms of their relative complements A = {r+1, ..., n} \ T. Next, each permutation count avoiding {1, ..., r} ∪ ({r+1, ..., n} \ A) is expressed as the sum of exact cycle-support counts over all subsets P ⊆ A. Finally, the algebraic identity gcd_{A ⊆ U} ∑_{P ⊆ A} f(P) = gcd_{P ⊆ U} f(P) simplifies this to the gcd of the exact support counts.

  1. The global gcd equals the gcd over subsets T ⊆ {r+1, ..., n} of the permutation counts avoiding cycle lengths {1, ..., r} ∪ T.

    We unfold the definitions of `restricted_cycle_global_gcd` and `restricted_cycle_excluded_family`. In the definition, the excluded sets are formed by taking the union of {1, ..., r} with each subset T in the powerset of {r+1, ..., n}. Rewriting with `Finset.gcd_image` replaces the gcd over this image family by a gcd indexed directly over T in the powerset of {r+1, ..., n}.

    lines 4–6

    uses Finset.gcd_image

      classical
      unfold restricted_cycle_global_gcd restricted_cycle_excluded_family
      rw [Finset.gcd_image]
  2. Reindexing by relative complements, the gcd over T ⊆ {r+1, ..., n} equals the gcd over A ⊆ {r+1, ..., n} of the counts avoiding {1, ..., r} ∪ ({r+1, ..., n} \\ A).

    Taking relative complements T ↦ {r+1, ..., n} \\ T is a bijection on the powerset of {r+1, ..., n}. By `finite_powerset_gcd_complement`, substituting each subset with its complement leaves the gcd over the powerset unchanged.

    lines 7–12

    uses finite_powerset_gcd_complement

      calc
        _ = (Finset.Icc (r+1) n).powerset.gcd
            (fun A => restricted_cycle_perms_count n
              (Finset.Icc 1 r ∪ (Finset.Icc (r+1) n \ A))) :=
          (finite_powerset_gcd_complement (Finset.Icc (r+1) n)
            (fun T => restricted_cycle_perms_count n (Finset.Icc 1 r ∪ T))).symm
  3. For each A ⊆ {r+1, ..., n}, the count of permutations avoiding {1, ..., r} ∪ ({r+1, ..., n} \\ A) equals the sum over P ⊆ A of the exact cycle-support counts.

    Using `Finset.gcd_congr`, we reduce the equality of the gcds to term-by-term equality for every A in the powerset of {r+1, ..., n}. We convert membership in the powerset to the subset inclusion A ⊆ {r+1, ..., n} using `Finset.mem_powerset.mp`. Then `restricted_cycle_count_as_support_sum` shows that avoiding {1, ..., r} and {r+1, ..., n} \\ A forces all cycle lengths to belong to A, so the total count decomposes into the sum over all possible exact support sets P ⊆ A.

    lines 13–17

    uses Finset.gcd_congr, Finset.mem_powerset.mp, restricted_cycle_count_as_support_sum

        _ = (Finset.Icc (r+1) n).powerset.gcd
            (fun A => ∑ P ∈ A.powerset, restricted_cycle_exact_support_count n P) := by
          apply Finset.gcd_congr rfl
          intro A hA
          exact restricted_cycle_count_as_support_sum r n A (Finset.mem_powerset.mp hA)
  4. The gcd of the subset sums over A ⊆ {r+1, ..., n} equals the gcd of the exact cycle-support counts over all P ⊆ {r+1, ..., n}.

    By `finite_powerset_gcd_sum` applied to U = {r+1, ..., n} and the exact support count function, the gcd over all subsets A of the partial sums ∑_{P ⊆ A} f(P) is equal to the gcd of the individual counts f(P) over all P ⊆ U.

    line 18

    uses finite_powerset_gcd_sum

        _ = _ := finite_powerset_gcd_sum _ _
Finset.gcd_image
The gcd of a function over the image of a finite set under a mapping equals the gcd of the composite function over the domain set.
finite_powerset_gcd_complement
For any finite set U and function f, the gcd of f(U \\ A) over all subsets A ⊆ U equals the gcd of f(T) over all subsets T ⊆ U.
Finset.gcd_congr
If two finite sets are equal and two functions agree pointwise on all elements of the set, then their gcds over that set are equal.
restricted_cycle_count_as_support_sum
For any subset A of {r+1, ..., n}, the number of permutations avoiding cycle lengths in {1, ..., r} ∪ ({r+1, ..., n} \\ A) equals the sum over all P ⊆ A of the number of permutations whose exact set of cycle lengths is P.
Finset.mem_powerset.mp
A finite set belongs to the powerset of U if and only if it is a subset of U (forward direction).
finite_powerset_gcd_sum
For any finite set U and function f, the gcd over all subsets A ⊆ U of the subset sums ∑_{B ⊆ A} f(B) equals the gcd of f(B) over all B ⊆ U.

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_global_gcd_eq_support_gcd (r n : ℕ) :    restricted_cycle_global_gcd r n =      (Finset.Icc (r+1) n).powerset.gcd (fun P => restricted_cycle_exact_support_count n P) := by  classical  unfold restricted_cycle_global_gcd restricted_cycle_excluded_family  rw [Finset.gcd_image]  calc    _ = (Finset.Icc (r+1) n).powerset.gcd        (fun A => restricted_cycle_perms_count n          (Finset.Icc 1 r ∪ (Finset.Icc (r+1) n \ A))) :=      (finite_powerset_gcd_complement (Finset.Icc (r+1) n)        (fun T => restricted_cycle_perms_count n (Finset.Icc 1 r ∪ T))).symm    _ = (Finset.Icc (r+1) n).powerset.gcd        (fun A => ∑ P ∈ A.powerset, restricted_cycle_exact_support_count n P) := by      apply Finset.gcd_congr rfl      intro A hA      exact restricted_cycle_count_as_support_sum r n A (Finset.mem_powerset.mp hA)    _ = _ := finite_powerset_gcd_sum _ _
See it in the graphDiscuss this resultChallenge it