restricted_cycle_global_gcd_eq_support_gcd
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
- finite_powerset_gcd_sumThe gcd of the sums of f over all subsets of each subset A of U equals the gcd of f over all subsets of U.
- restricted_cycle_exact_support_countThe number of permutations of Fin n with set of distinct cycle lengths exactly P, including fixed points as cycles of length 1.
- restricted_cycle_count_as_support_sumIf 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…
- finite_powerset_gcd_complementComplementing each subset inside a finite universe preserves the gcd of the function values over all subsets.
- restricted_cycle_global_gcdThe global gcd g_r(n) is the greatest common divisor of the counts restricted_cycle_perms_count n S over all sets S in…
- 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…
- restricted_cycle_excluded_familyThe family of all subsets of {1, ..., n} containing {1, ..., r}.
- Used by 1
- restricted_cycle_global_eq_iff_support_dvdFor every r and n, the global and one-parameter gcds are equal if and only if the one-parameter gcd divides the exact cycle-support count…
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.
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}.
uses
Finset.gcd_imageclassical unfold restricted_cycle_global_gcd restricted_cycle_excluded_family rw [Finset.gcd_image]
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.
uses
finite_powerset_gcd_complementcalc _ = (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
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.
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)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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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 _ _