finite_powerset_dvd_sum_iff
For 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 divides every function value on a subset of U.
Statement
theorem finite_powerset_dvd_sum_iff {α : Type*} [DecidableEq α] (U : Finset α) (f : Finset α → ℕ) (d : ℕ) : (∀ A ⊆ U, d ∣ ∑ B ∈ A.powerset, f B) ↔ (∀ A ⊆ U, d ∣ f A)
- 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- Used by 1
- finite_powerset_gcd_sumThe 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.
The proof, explained
The equivalence is proved in two directions. The backward direction is immediate: if d divides f(B) for every B ⊆ U, then it divides any sum of these values, including the powerset sum for any A ⊆ U. The forward direction proceeds by strong induction on A under strict inclusion. Splitting the powerset sum for A into the value f(A) and the sum over all proper subsets of A, the induction hypothesis ensures that d divides each term in the latter sum; since d divides both this partial sum and the total powerset sum, it must also divide f(A).
The equivalence is split into the forward and backward implications.
We apply `constructor` to split the bi-implication into two separate goals: first showing that if d divides every powerset sum then it divides every function value, and second showing the converse.
constructorFor the forward direction, the goal reduces by strong induction to proving d ∣ f(A) assuming the claim holds for all strict subsets of A.
Assuming that d divides the powerset sum of every subset of U, we consider an arbitrary A ⊆ U. We proceed by strong induction on A ordered by strict inclusion (⊂) using `Finset.strongInductionOn`. This yields the induction hypothesis that d ∣ f(t) for every proper subset t ⊂ A with t ⊆ U.
uses
Finset.strongInductionOn· intro h A induction A using Finset.strongInductionOn with | _ A ih => intro hAU
d divides the sum over all proper subsets of A, ∑_{B ∈ P(A) ∖ {A}} f(B).
By `Finset.dvd_sum`, it suffices to show that d ∣ f(B) for each B in A.powerset.erase A. Such a B is an element of P(A) not equal to A (by `Finset.mem_erase.mp`), which means B ⊆ A (by `Finset.mem_powerset.mp`) and thus B ⊂ A (by `Finset.ssubset_iff_subset_ne.mpr`). Since A ⊆ U, transitivity gives B ⊆ U, and the induction hypothesis applies to show d ∣ f(B).
uses
Finset.dvd_sum,Finset.mem_erase.mp,Finset.mem_powerset.mp,Finset.ssubset_iff_subset_ne.mprhave hrest : d ∣ ∑ B ∈ A.powerset.erase A, f B := by apply Finset.dvd_sum intro B hB obtain ⟨hne, hsub⟩ := Finset.mem_erase.mp hB have hBA : B ⊆ A := Finset.mem_powerset.mp hsub exact ih B (Finset.ssubset_iff_subset_ne.mpr ⟨hBA, hne⟩) (hBA.trans hAU)
d ∣ f(A), completing the forward direction.
Since A ∈ P(A) (by `Finset.mem_powerset_self`), `Finset.sum_erase_add` decomposes the total sum ∑_{B ∈ P(A)} f(B) into (∑_{B ∈ P(A) ∖ {A}} f(B)) + f(A). By assumption, d divides this total sum. Because d also divides the proper-subsets sum from the previous step, `Nat.dvd_add_iff_left` (along with `Nat.add_comm` to reorder the terms) implies that d divides the remaining term f(A).
uses
Finset.sum_erase_add,Finset.mem_powerset_self,Nat.dvd_add_iff_left,Nat.add_commhave heq := Finset.sum_erase_add A.powerset f (Finset.mem_powerset_self A) have hall := h A hAU rw [← heq] at hall exact (Nat.dvd_add_iff_left hrest).mpr (by simpa only [Nat.add_comm] using hall)
In the backward direction, d divides the powerset sum ∑_{B ∈ P(A)} f(B) for any A ⊆ U.
Assuming d ∣ f(B) for all B ⊆ U, we take any A ⊆ U. By `Finset.dvd_sum`, it is enough to show that d ∣ f(B) for each B ∈ P(A). Since B ∈ P(A) means B ⊆ A (by `Finset.mem_powerset.mp`), transitivity gives B ⊆ U, so the hypothesis immediately implies d ∣ f(B).
uses
Finset.dvd_sum,Finset.mem_powerset.mp· intro h A hAU apply Finset.dvd_sum intro B hB exact h B ((Finset.mem_powerset.mp hB).trans hAU)
Finset.strongInductionOn- A property holds for all finite sets if, whenever it holds for all strict subsets of a set, it holds for the set itself.
Finset.dvd_sum- If a number divides each term in a finite sum, it divides the sum.
Finset.mem_erase.mp- If an element belongs to s ∖ {a}, then it is not equal to a and belongs to s.
Finset.mem_powerset.mp- If a set belongs to the powerset of s, then it is a subset of s.
Finset.ssubset_iff_subset_ne.mpr- If a set is a subset of another and distinct from it, then it is a strict subset.
Finset.sum_erase_add- For any element a ∈ s, the sum of f over s equals the sum of f over s ∖ {a} plus f(a).
Finset.mem_powerset_self- Every finite set is an element of its own powerset.
Nat.dvd_add_iff_left- If k divides n, then k divides m if and only if k divides m + n.
Nat.add_comm- Addition of natural numbers is commutative: n + m = m + n.
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_dvd_sum_iff {α : Type*} [DecidableEq α] (U : Finset α) (f : Finset α → ℕ) (d : ℕ) : (∀ A ⊆ U, d ∣ ∑ B ∈ A.powerset, f B) ↔ (∀ A ⊆ U, d ∣ f A) := by constructor · intro h A induction A using Finset.strongInductionOn with | _ A ih => intro hAU have hrest : d ∣ ∑ B ∈ A.powerset.erase A, f B := by apply Finset.dvd_sum intro B hB obtain ⟨hne, hsub⟩ := Finset.mem_erase.mp hB have hBA : B ⊆ A := Finset.mem_powerset.mp hsub exact ih B (Finset.ssubset_iff_subset_ne.mpr ⟨hBA, hne⟩) (hBA.trans hAU) have heq := Finset.sum_erase_add A.powerset f (Finset.mem_powerset_self A) have hall := h A hAU rw [← heq] at hall exact (Nat.dvd_add_iff_left hrest).mpr (by simpa only [Nat.add_comm] using hall) · intro h A hAU apply Finset.dvd_sum intro B hB exact h B ((Finset.mem_powerset.mp hB).trans hAU)