restricted_cycle_global_eq_iff_support_dvd
For 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 for every support contained in the interval r+1 through n.
Statement
theorem restricted_cycle_global_eq_iff_support_dvd (r n : ℕ) :
restricted_cycle_global_gcd r n = restricted_cycle_one_param_gcd r n ↔
∀ P ⊆ Finset.Icc (r+1) n,
restricted_cycle_one_param_gcd r n ∣ 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 5
- 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_global_gcd_eq_support_gcdFor 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…
- restricted_cycle_global_gcd_dvd_one_param_gcdFor all r and n, the global gcd restricted_cycle_global_gcd r n divides the one-parameter gcd restricted_cycle_one_param_gcd r n.
- 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_one_param_gcdThe one-parameter gcd G_r(n) is the greatest common divisor of the counts restricted_cycle_perms_count n S over all sets S in…
The proof, explained
The equivalence is proved in two directions by expressing the global gcd as the gcd of exact cycle-support counts over all subsets of $\{r+1, \dots, n\}$. For the forward direction, equality allows replacing the one-parameter gcd with the global gcd, which divides each individual count because any gcd divides the elements of its underlying set. For the reverse direction, the global gcd already divides the one-parameter gcd, so by divisibility antisymmetry it suffices to show the converse divisibility; this holds because the one-parameter gcd divides every support count and therefore divides their gcd.
If the global gcd equals the one-parameter gcd, then the one-parameter gcd divides the exact cycle-support count for every subset $P \subseteq \{r+1, \dots, n\}$.
We split the equivalence with `constructor` to prove the forward direction first. Assuming that the global gcd equals the one-parameter gcd and considering an arbitrary subset $P \subseteq \{r+1, \dots, n\}$, we substitute the global gcd in place of the one-parameter gcd. By `restricted_cycle_global_gcd_eq_support_gcd`, the global gcd is the gcd of the exact support counts over the powerset of $\{r+1, \dots, n\}$. Since $P$ belongs to this powerset by `Finset.mem_powerset.mpr`, `Finset.gcd_dvd` implies that the gcd divides the support count of $P$.
uses
restricted_cycle_global_gcd_eq_support_gcd,Finset.gcd_dvd,Finset.mem_powerset.mprconstructor · intro h P hP rw [← h, restricted_cycle_global_gcd_eq_support_gcd] exact Finset.gcd_dvd (Finset.mem_powerset.mpr hP)
For the reverse implication, it suffices to show that the one-parameter gcd divides the global gcd.
We assume the divisibility hypothesis that the one-parameter gcd divides each exact support count. By `restricted_cycle_global_gcd_dvd_one_param_gcd`, the global gcd already divides the one-parameter gcd. Applying divisibility antisymmetry on natural numbers (`Nat.dvd_antisymm`), establishing the reverse divisibility suffices to deduce equality.
uses
Nat.dvd_antisymm,restricted_cycle_global_gcd_dvd_one_param_gcd· intro h apply Nat.dvd_antisymm (restricted_cycle_global_gcd_dvd_one_param_gcd r n)
The one-parameter gcd divides the global gcd, which finishes the proof.
Rewriting the global gcd as the gcd of exact support counts over the powerset of $\{r+1, \dots, n\}$ using `restricted_cycle_global_gcd_eq_support_gcd`, we apply `Finset.dvd_gcd_iff.mpr`, which reduces dividing a finite gcd to dividing each term. Since elements of the powerset are subsets of $\{r+1, \dots, n\}$ by `Finset.mem_powerset.mp`, the assumed hypothesis guarantees that the one-parameter gcd divides each count.
uses
restricted_cycle_global_gcd_eq_support_gcd,Finset.dvd_gcd_iff.mpr,Finset.mem_powerset.mprw [restricted_cycle_global_gcd_eq_support_gcd] exact Finset.dvd_gcd_iff.mpr (fun P hP => h P (Finset.mem_powerset.mp hP))
restricted_cycle_global_gcd_eq_support_gcd- For any $r$ and $n$, the global gcd equals the greatest common divisor of the exact cycle-support counts over all subsets $P \subseteq \{r+1, \dots, n\}$.
Finset.gcd_dvd- For any element $b$ in a finite set $s$, the greatest common divisor of $f$ over $s$ divides $f(b)$.
Finset.mem_powerset.mpr- If a finite set $s$ is a subset of $t$, then $s$ is an element of the powerset of $t$.
Nat.dvd_antisymm- For natural numbers $m$ and $n$, if $m \mid n$ and $n \mid m$, then $m = n$.
restricted_cycle_global_gcd_dvd_one_param_gcd- For any $r$ and $n$, the global gcd divides the one-parameter gcd.
Finset.dvd_gcd_iff.mpr- If a number divides $f(b)$ for every element $b$ in a finite set $s$, then it divides the greatest common divisor of $f$ over $s$.
Finset.mem_powerset.mp- If a finite set $s$ is an element of the powerset of $t$, then $s$ is a subset of $t$.
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_eq_iff_support_dvd (r n : ℕ) : restricted_cycle_global_gcd r n = restricted_cycle_one_param_gcd r n ↔ ∀ P ⊆ Finset.Icc (r+1) n, restricted_cycle_one_param_gcd r n ∣ restricted_cycle_exact_support_count n P := by constructor · intro h P hP rw [← h, restricted_cycle_global_gcd_eq_support_gcd] exact Finset.gcd_dvd (Finset.mem_powerset.mpr hP) · intro h apply Nat.dvd_antisymm (restricted_cycle_global_gcd_dvd_one_param_gcd r n) rw [restricted_cycle_global_gcd_eq_support_gcd] exact Finset.dvd_gcd_iff.mpr (fun P hP => h P (Finset.mem_powerset.mp hP))