AFTD Auto-Formalizing Theoretical Domains

restricted_cycle_global_gcd_eq_one_param_of_family_dvd

theoremverified

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

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).

  1. 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).

    line 3

    uses Nat.dvd_antisymm, restricted_cycle_global_gcd_dvd_one_param_gcd, Finset.dvd_gcd_iff.mpr

      exact 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

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

/-- 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)
See it in the graphDiscuss this resultChallenge it