AFTD Auto-Formalizing Theoretical Domains

restricted_cycle_global_eq_of_short

theoremverified

For every r and every positive n less than 2(r+1), the global restricted-cycle gcd equals its one-parameter gcd.

Statement

theorem restricted_cycle_global_eq_of_short (r n : ℕ) (hn0 : 0 < n) (hn : n < 2 * (r+1)) :
    restricted_cycle_global_gcd r n = restricted_cycle_one_param_gcd r n
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 7

The proof, explained

The global restricted-cycle gcd always divides the one-parameter gcd because the one-parameter family is a subset of the full excluded family. For the reverse divisibility when n < 2(r+1), every excluded set S ⊇ [1, r] has permutation count either 0 or equal to the count for the base interval [1, r], which implies that the base count divides the global gcd. Since [1, r] itself belongs to the one-parameter family, the one-parameter gcd divides this base count and thus divides the global gcd by transitivity. The two gcds are therefore equal by antisymmetry of divisibility on ℕ.

  1. The permutation count for the base interval [1, r] divides the global restricted-cycle gcd.

    We work under classical logic so that set membership is decidable. To show that the count for [1, r] divides the global gcd (the gcd over all sets in the excluded family), it suffices to show that it divides the count for each set S in that family (Finset.dvd_gcd_iff.mpr). By definition, any such set S has the form [1, r] ∪ T for some T ⊆ [r+1, n] (Finset.mem_image.mp). Since [1, r] ⊆ [1, r] ∪ T (Finset.subset_union_left) and n < 2(r+1), the lemma restricted_cycle_count_zero_or_base_of_short shows that the permutation count for [1, r] ∪ T is 0 if n ∈ [1, r] ∪ T and equals the count for [1, r] otherwise. In either case, the base count divides the count for S, as any number divides 0 and any number divides itself.

    lines 3–10

    uses Finset.dvd_gcd_iff.mpr, Finset.mem_image.mp, restricted_cycle_count_zero_or_base_of_short, Finset.subset_union_left

      classical
      have hbase : restricted_cycle_perms_count n (Finset.Icc 1 r) ∣
          restricted_cycle_global_gcd r n := by
        apply Finset.dvd_gcd_iff.mpr
        intro S hS
        obtain ⟨T, hT, rfl⟩ := Finset.mem_image.mp hS
        rw [restricted_cycle_count_zero_or_base_of_short r n hn0 hn _ Finset.subset_union_left]
        split_ifs <;> simp
  2. The one-parameter gcd divides the permutation count for the base interval [1, r].

    The one-parameter family is defined by inserting the base interval [1, r] into a collection of single-element extensions. In particular, [1, r] belongs to this family (Finset.mem_insert_self). Because the gcd of a family divides the value at every member of the family (Finset.gcd_dvd), the one-parameter gcd divides the permutation count for [1, r].

    lines 11–14

    uses Finset.gcd_dvd, Finset.mem_insert_self

      have hone : restricted_cycle_one_param_gcd r n ∣
          restricted_cycle_perms_count n (Finset.Icc 1 r) := by
        apply Finset.gcd_dvd
        exact Finset.mem_insert_self _ _
  3. The global restricted-cycle gcd equals the one-parameter gcd.

    The global gcd divides the one-parameter gcd by restricted_cycle_global_gcd_dvd_one_param_gcd. In the opposite direction, the one-parameter gcd divides the base count, which in turn divides the global gcd, so by transitivity of divisibility the one-parameter gcd divides the global gcd. Because these two natural numbers divide each other, they are equal by Nat.dvd_antisymm.

    lines 15–16

    uses restricted_cycle_global_gcd_dvd_one_param_gcd, Nat.dvd_antisymm

      exact Nat.dvd_antisymm (restricted_cycle_global_gcd_dvd_one_param_gcd r n)
        (hone.trans hbase)
Finset.dvd_gcd_iff.mpr
An element divides the gcd of a finite set of values if it divides each value in the set.
Finset.mem_image.mp
If an element belongs to the image of a set under a function, it is the image of some element of that set.
restricted_cycle_count_zero_or_base_of_short
For 0 < n < 2(r+1), the number of permutations avoiding cycle lengths in a set S containing [1, r] is 0 if n ∈ S and equals the count for [1, r] otherwise.
Finset.subset_union_left
A finite set is a subset of its union with any other set.
Finset.gcd_dvd
The greatest common divisor of a function's values on a finite set divides the function's value at any element of that set.
Finset.mem_insert_self
An element belongs to the set obtained by inserting it into an existing finite set.
Nat.dvd_antisymm
Two natural numbers that divide each other are equal.
restricted_cycle_global_gcd_dvd_one_param_gcd
The global restricted-cycle gcd divides the one-parameter restricted-cycle gcd.

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_of_short (r n : ℕ) (hn0 : 0 < n) (hn : n < 2 * (r+1)) :    restricted_cycle_global_gcd r n = restricted_cycle_one_param_gcd r n := by  classical  have hbase : restricted_cycle_perms_count n (Finset.Icc 1 r) ∣      restricted_cycle_global_gcd r n := by    apply Finset.dvd_gcd_iff.mpr    intro S hS    obtain ⟨T, hT, rfl⟩ := Finset.mem_image.mp hS    rw [restricted_cycle_count_zero_or_base_of_short r n hn0 hn _ Finset.subset_union_left]    split_ifs <;> simp  have hone : restricted_cycle_one_param_gcd r n ∣      restricted_cycle_perms_count n (Finset.Icc 1 r) := by    apply Finset.gcd_dvd    exact Finset.mem_insert_self _ _  exact Nat.dvd_antisymm (restricted_cycle_global_gcd_dvd_one_param_gcd r n)    (hone.trans hbase)
See it in the graphDiscuss this resultChallenge it