AFTD Auto-Formalizing Theoretical Domains

finite_powerset_gcd_sum

theoremverified

The gcd of the sums of f over all subsets of each subset A of U equals the gcd of f over all subsets of U.

Statement

theorem finite_powerset_gcd_sum {α : Type*} [DecidableEq α]
    (U : Finset α) (f : Finset α → ℕ) :
    U.powerset.gcd (fun A => ∑ B ∈ A.powerset, f B) = U.powerset.gcd f
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 1
  • finite_powerset_dvd_sum_iffFor a natural-valued function on the subsets of a finite set U, a natural number divides every subset sum over powersets if and only if it…
Used by 1

The proof, explained

The proof establishes equality by mutual divisibility. In the forward direction, the gcd of the subset sums divides each subset sum by definition, which by the characterization `finite_powerset_dvd_sum_iff` is equivalent to dividing each individual term f(A), and hence their gcd. In the reverse direction, the gcd of f divides each term f(B) for any B ⊆ A ⊆ U, and therefore divides every subset sum and their gcd.

  1. It suffices to show that the gcd of the subset sums and the gcd of f divide each other.

    By the antisymmetry of divisibility on the natural numbers (`Nat.dvd_antisymm`), two numbers are equal if each divides the other.

    line 4

    uses Nat.dvd_antisymm

      apply Nat.dvd_antisymm
  2. The gcd of the subset sums divides the gcd of f over all subsets of U.

    To show that the gcd of the subset sums divides the gcd of f, it suffices by `Finset.dvd_gcd_iff.mpr` to show it divides f(A) for each A ⊆ U. By `Finset.gcd_dvd`, the gcd divides the sum ∑ B ∈ A.powerset, f B for every subset A ⊆ U. Then `finite_powerset_dvd_sum_iff` converts divisibility of all subset sums into divisibility of f(A) for every A ⊆ U, completing this direction.

    lines 5–11

    uses Finset.dvd_gcd_iff.mpr, Finset.gcd_dvd, Finset.mem_powerset.mpr, finite_powerset_dvd_sum_iff, Finset.mem_powerset.mp

      · apply Finset.dvd_gcd_iff.mpr
        have h : ∀ A ⊆ U, U.powerset.gcd (fun A => ∑ B ∈ A.powerset, f B) ∣
            ∑ B ∈ A.powerset, f B := by
          intro A hAU
          exact Finset.gcd_dvd (Finset.mem_powerset.mpr hAU)
        intro A hA
        exact (finite_powerset_dvd_sum_iff U f _).mp h A (Finset.mem_powerset.mp hA)
  3. The gcd of f over all subsets of U divides the gcd of the subset sums.

    By `Finset.dvd_gcd_iff.mpr`, it suffices to show that the gcd of f divides ∑ B ∈ A.powerset, f B for each A ⊆ U. By `Finset.dvd_sum`, a number divides a sum if it divides every summand f(B). For any B ⊆ A ⊆ U, transitivity gives B ⊆ U, so B is in the powerset of U; therefore, `Finset.gcd_dvd` ensures that the gcd of f divides f(B).

    lines 12–17

    uses Finset.dvd_gcd_iff.mpr, Finset.dvd_sum, Finset.gcd_dvd, Finset.mem_powerset.mpr, Finset.mem_powerset.mp

      · apply Finset.dvd_gcd_iff.mpr
        intro A hA
        apply Finset.dvd_sum
        intro B hB
        exact Finset.gcd_dvd (Finset.mem_powerset.mpr
          ((Finset.mem_powerset.mp hB).trans (Finset.mem_powerset.mp hA)))
Nat.dvd_antisymm
If two natural numbers divide each other, they are equal.
Finset.dvd_gcd_iff.mpr
A number divides the gcd of a finite set under f if it divides f(b) for every element b in the set.
Finset.gcd_dvd
The gcd of a finite set under f divides f(b) for every element b in the set.
Finset.mem_powerset.mpr
If a finset A is a subset of U, then A belongs to the powerset of U.
Finset.mem_powerset.mp
If a finset A belongs to the powerset of U, then A is a subset of U.
finite_powerset_dvd_sum_iff
A number d divides the sum of f over all subsets of A for every subset A of U if and only if d divides f(A) for every subset A of U.
Finset.dvd_sum
If a number divides each summand of a finite sum, it divides the entire sum.

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 finite_powerset_gcd_sum {α : Type*} [DecidableEq α]    (U : Finset α) (f : Finset α → ℕ) :    U.powerset.gcd (fun A => ∑ B ∈ A.powerset, f B) = U.powerset.gcd f := by  apply Nat.dvd_antisymm  · apply Finset.dvd_gcd_iff.mpr    have h : ∀ A ⊆ U, U.powerset.gcd (fun A => ∑ B ∈ A.powerset, f B) ∣        ∑ B ∈ A.powerset, f B := by      intro A hAU      exact Finset.gcd_dvd (Finset.mem_powerset.mpr hAU)    intro A hA    exact (finite_powerset_dvd_sum_iff U f _).mp h A (Finset.mem_powerset.mp hA)  · apply Finset.dvd_gcd_iff.mpr    intro A hA    apply Finset.dvd_sum    intro B hB    exact Finset.gcd_dvd (Finset.mem_powerset.mpr      ((Finset.mem_powerset.mp hB).trans (Finset.mem_powerset.mp hA)))
See it in the graphDiscuss this resultChallenge it