restricted_cycle_global_gcd_eq_one_param_of_family_dvd
If the one-parameter gcd G_3(n) divides the restricted count a_S(n) attached to every set S = {1,2,3} ∪ T of the excluded family, then the global gcd g_3(n) equals G_3(n).
Statement
theorem restricted_cycle_global_gcd_eq_one_param_of_family_dvd (n : ℕ) (h : ∀ S ∈ restricted_cycle_excluded_family 3 n, restricted_cycle_one_param_gcd 3 n ∣ restricted_cycle_perms_count n S) : restricted_cycle_global_gcd 3 n = restricted_cycle_one_param_gcd 3 n- Source
- step towards global_gcd_agreement_r_three_eq
- 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_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_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_excluded_familyThe family of all subsets of {1, ..., n} containing {1, ..., r}.
- 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 proof establishes the equality g_3(n) = G_3(n) by showing that the two natural numbers divide each other. The divisibility g_3(n) ∣ G_3(n) holds in general. Conversely, because G_3(n) is assumed to divide every count a_S(n) in the excluded family, it must also divide their greatest common divisor, which is g_3(n).
The global gcd g_3(n) equals the one-parameter gcd G_3(n).
Equality of natural numbers is proved by mutual divisibility using `Nat.dvd_antisymm`. In one direction, `restricted_cycle_global_gcd_dvd_one_param_gcd 3 n` gives that g_3(n) divides G_3(n). In the other direction, the hypothesis h states that G_3(n) divides the permutation count for every set S in the excluded family; by `Finset.dvd_gcd_iff.mpr`, G_3(n) divides the gcd of all these counts, which is by definition g_3(n).
uses
Nat.dvd_antisymm,restricted_cycle_global_gcd_dvd_one_param_gcd,Finset.dvd_gcd_iff.mprexact Nat.dvd_antisymm (restricted_cycle_global_gcd_dvd_one_param_gcd 3 n) (Finset.dvd_gcd_iff.mpr h)
Nat.dvd_antisymm- if two natural numbers divide each other, then they are equal
restricted_cycle_global_gcd_dvd_one_param_gcd- the global gcd g_r(n) divides the one-parameter gcd G_r(n)
Finset.dvd_gcd_iff.mpr- if a number divides f(b) for every element b in a finite set s, it divides the greatest common divisor of the values f(b) for b in s
- By definition, the global gcd `restricted_cycle_global_gcd 3 n` is the greatest common divisor of the permutation counts over the excluded family `restricted_cycle_excluded_family 3 n`. Consequently, `Finset.dvd_gcd_iff.mpr` applies directly to the hypothesis without needing an explicit unfolding step.
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.
/-- Family-divisibility criterion: G_3(n) dividing every excluded-family count forces g_3(n) = G_3(n). -/theorem restricted_cycle_global_gcd_eq_one_param_of_family_dvd (n : ℕ) (h : ∀ S ∈ restricted_cycle_excluded_family 3 n, restricted_cycle_one_param_gcd 3 n ∣ restricted_cycle_perms_count n S) : restricted_cycle_global_gcd 3 n = restricted_cycle_one_param_gcd 3 n := by exact Nat.dvd_antisymm (restricted_cycle_global_gcd_dvd_one_param_gcd 3 n) (Finset.dvd_gcd_iff.mpr h)