AFTD Auto-Formalizing Theoretical Domains

finite_powerset_dvd_sum_iff

theoremverified

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).

  1. 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.

    line 5

      constructor
  2. For 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.

    lines 6–9

    uses Finset.strongInductionOn

      · intro h A
        induction A using Finset.strongInductionOn with
        | _ A ih =>
          intro hAU
  3. 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).

    lines 10–15

    uses Finset.dvd_sum, Finset.mem_erase.mp, Finset.mem_powerset.mp, Finset.ssubset_iff_subset_ne.mpr

          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)
  4. 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).

    lines 16–19

    uses Finset.sum_erase_add, Finset.mem_powerset_self, Nat.dvd_add_iff_left, Nat.add_comm

          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)
  5. 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).

    lines 20–23

    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

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)
See it in the graphDiscuss this resultChallenge it