AFTD Auto-Formalizing Theoretical Domains

restricted_cycle_global_eq_iff_family_dvd

theoremverified

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

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.

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

    line 5

      constructor
  2. If 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.

    lines 6–8

    uses Finset.gcd_dvd

      · intro h S hS
        rw [← h]
        exact Finset.gcd_dvd hS
  3. 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.

    lines 9–10

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

    line 11

    uses Finset.dvd_gcd_iff.mpr

        exact 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

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