restricted_cycle_global_eq_iff_family_dvd
For every r and n, equality of the global and one-parameter gcds is equivalent to divisibility of every excluded-family count by the one-parameter gcd.
Statement
theorem restricted_cycle_global_eq_iff_family_dvd (r n : ℕ) :
restricted_cycle_global_gcd r n = restricted_cycle_one_param_gcd r n ↔
∀ S ∈ restricted_cycle_excluded_family r n,
restricted_cycle_one_param_gcd r n ∣ restricted_cycle_perms_count n S- 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_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…
- 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}.
The proof, explained
The equivalence is established in two directions. In the forward direction, assuming equality of the gcds, rewriting the one-parameter gcd as the global gcd reduces the goal to the standard fact that a finite-set gcd divides each element. In the reverse direction, since the global gcd is already known to divide the one-parameter gcd, equality reduces by antisymmetry of divisibility on ℕ to showing that the one-parameter gcd divides the global gcd; this follows from the universal property of the gcd, as the one-parameter gcd divides every count in the excluded family by assumption.
The equivalence is split into the forward and reverse implications.
The `constructor` tactic separates the "if and only if" statement into two subgoals: equality implies divisibility, and divisibility implies equality.
constructorIf the global gcd equals the one-parameter gcd, then the one-parameter gcd divides each excluded-family count.
Assume the two gcds are equal (h), and let S be any member of the excluded family (hS). Rewriting the one-parameter gcd as the global gcd using h transforms the goal into showing that the global gcd divides the count for S. Since the global gcd is defined as the gcd of these counts over the excluded family, this divisibility holds directly by Finset.gcd_dvd.
uses
Finset.gcd_dvd· intro h S hS rw [← h] exact Finset.gcd_dvd hS
In the reverse direction, it suffices to show that the one-parameter gcd divides the global gcd.
Assume that the one-parameter gcd divides every count in the excluded family (h). Divisibility in the other direction is already known by restricted_cycle_global_gcd_dvd_one_param_gcd. By antisymmetry of divisibility on the natural numbers (Nat.dvd_antisymm), establishing equality reduces to showing that the one-parameter gcd divides the global gcd.
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, completing the proof.
By definition, the global gcd is the gcd of the counts across the excluded family. By the universal property of the gcd (Finset.dvd_gcd_iff.mpr), a number that divides every count in the family also divides their gcd. Applying this to hypothesis h closes the goal.
uses
Finset.dvd_gcd_iff.mprexact Finset.dvd_gcd_iff.mpr h
Finset.gcd_dvd- For any element b in a finite set s, the greatest common divisor of f over s divides f(b).
Nat.dvd_antisymm- Divisibility on natural numbers is antisymmetric: if m divides n and n divides m, then m = n.
restricted_cycle_global_gcd_dvd_one_param_gcd- For any r and n, the global restricted-cycle gcd divides the one-parameter restricted-cycle gcd.
Finset.dvd_gcd_iff.mpr- If a divides f(b) for every element b in a finite set s, then a divides the greatest common divisor of f over s.
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_family_dvd (r n : ℕ) : restricted_cycle_global_gcd r n = restricted_cycle_one_param_gcd r n ↔ ∀ S ∈ restricted_cycle_excluded_family r n, restricted_cycle_one_param_gcd r n ∣ restricted_cycle_perms_count n S := by constructor · intro h S hS rw [← h] exact Finset.gcd_dvd hS · intro h apply Nat.dvd_antisymm (restricted_cycle_global_gcd_dvd_one_param_gcd r n) exact Finset.dvd_gcd_iff.mpr h