AFTD Auto-Formalizing Theoretical Domains

restricted_cycle_global_eq_iff_support_dvd

theoremverified

For every r and n, the global and one-parameter gcds are equal if and only if the one-parameter gcd divides the exact cycle-support count for every support contained in the interval r+1 through n.

Statement

theorem restricted_cycle_global_eq_iff_support_dvd (r n : ℕ) :
    restricted_cycle_global_gcd r n = restricted_cycle_one_param_gcd r n ↔
    ∀ P ⊆ Finset.Icc (r+1) n,
      restricted_cycle_one_param_gcd r n ∣ restricted_cycle_exact_support_count n P
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 proved in two directions by expressing the global gcd as the gcd of exact cycle-support counts over all subsets of $\{r+1, \dots, n\}$. For the forward direction, equality allows replacing the one-parameter gcd with the global gcd, which divides each individual count because any gcd divides the elements of its underlying set. For the reverse direction, the global gcd already divides the one-parameter gcd, so by divisibility antisymmetry it suffices to show the converse divisibility; this holds because the one-parameter gcd divides every support count and therefore divides their gcd.

  1. If the global gcd equals the one-parameter gcd, then the one-parameter gcd divides the exact cycle-support count for every subset $P \subseteq \{r+1, \dots, n\}$.

    We split the equivalence with `constructor` to prove the forward direction first. Assuming that the global gcd equals the one-parameter gcd and considering an arbitrary subset $P \subseteq \{r+1, \dots, n\}$, we substitute the global gcd in place of the one-parameter gcd. By `restricted_cycle_global_gcd_eq_support_gcd`, the global gcd is the gcd of the exact support counts over the powerset of $\{r+1, \dots, n\}$. Since $P$ belongs to this powerset by `Finset.mem_powerset.mpr`, `Finset.gcd_dvd` implies that the gcd divides the support count of $P$.

    lines 5–8

    uses restricted_cycle_global_gcd_eq_support_gcd, Finset.gcd_dvd, Finset.mem_powerset.mpr

      constructor
      · intro h P hP
        rw [← h, restricted_cycle_global_gcd_eq_support_gcd]
        exact Finset.gcd_dvd (Finset.mem_powerset.mpr hP)
  2. For the reverse implication, it suffices to show that the one-parameter gcd divides the global gcd.

    We assume the divisibility hypothesis that the one-parameter gcd divides each exact support count. By `restricted_cycle_global_gcd_dvd_one_param_gcd`, the global gcd already divides the one-parameter gcd. Applying divisibility antisymmetry on natural numbers (`Nat.dvd_antisymm`), establishing the reverse divisibility suffices to deduce equality.

    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)
  3. The one-parameter gcd divides the global gcd, which finishes the proof.

    Rewriting the global gcd as the gcd of exact support counts over the powerset of $\{r+1, \dots, n\}$ using `restricted_cycle_global_gcd_eq_support_gcd`, we apply `Finset.dvd_gcd_iff.mpr`, which reduces dividing a finite gcd to dividing each term. Since elements of the powerset are subsets of $\{r+1, \dots, n\}$ by `Finset.mem_powerset.mp`, the assumed hypothesis guarantees that the one-parameter gcd divides each count.

    lines 11–12

    uses restricted_cycle_global_gcd_eq_support_gcd, Finset.dvd_gcd_iff.mpr, Finset.mem_powerset.mp

        rw [restricted_cycle_global_gcd_eq_support_gcd]
        exact Finset.dvd_gcd_iff.mpr (fun P hP => h P (Finset.mem_powerset.mp hP))
restricted_cycle_global_gcd_eq_support_gcd
For any $r$ and $n$, the global gcd equals the greatest common divisor of the exact cycle-support counts over all subsets $P \subseteq \{r+1, \dots, n\}$.
Finset.gcd_dvd
For any element $b$ in a finite set $s$, the greatest common divisor of $f$ over $s$ divides $f(b)$.
Finset.mem_powerset.mpr
If a finite set $s$ is a subset of $t$, then $s$ is an element of the powerset of $t$.
Nat.dvd_antisymm
For natural numbers $m$ and $n$, if $m \mid n$ and $n \mid m$, then $m = n$.
restricted_cycle_global_gcd_dvd_one_param_gcd
For any $r$ and $n$, the global gcd divides the one-parameter gcd.
Finset.dvd_gcd_iff.mpr
If a number divides $f(b)$ for every element $b$ in a finite set $s$, then it divides the greatest common divisor of $f$ over $s$.
Finset.mem_powerset.mp
If a finite set $s$ is an element of the powerset of $t$, then $s$ is a subset of $t$.

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_support_dvd (r n : ℕ) :    restricted_cycle_global_gcd r n = restricted_cycle_one_param_gcd r n ↔    ∀ P ⊆ Finset.Icc (r+1) n,      restricted_cycle_one_param_gcd r n ∣ restricted_cycle_exact_support_count n P := by  constructor  · intro h P hP    rw [← h, restricted_cycle_global_gcd_eq_support_gcd]    exact Finset.gcd_dvd (Finset.mem_powerset.mpr hP)  · intro h    apply Nat.dvd_antisymm (restricted_cycle_global_gcd_dvd_one_param_gcd r n)    rw [restricted_cycle_global_gcd_eq_support_gcd]    exact Finset.dvd_gcd_iff.mpr (fun P hP => h P (Finset.mem_powerset.mp hP))
See it in the graphDiscuss this resultChallenge it