finite_powerset_gcd_sum
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
- restricted_cycle_global_gcd_eq_support_gcdFor every r and n, the global gcd of counts avoiding cycle lengths 1 through r and any additional subset of lengths up to n equals the gcd…
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.
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.
uses
Nat.dvd_antisymmapply Nat.dvd_antisymmThe 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.
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)
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).
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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)))