AFTD Auto-Formalizing Theoretical Domains

finite_powerset_gcd_complement

theoremverified

Complementing each subset inside a finite universe preserves the gcd of the function values over all subsets.

Statement

theorem finite_powerset_gcd_complement {α : Type*} [DecidableEq α]
    (U : Finset α) (f : Finset α → ℕ) :
    U.powerset.gcd (fun A => f (U \ A)) = 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
Used by 1

The proof, explained

The proof establishes the equality of the two greatest common divisors by mutual divisibility on the natural numbers. Because complementation A ↦ U \ A maps the powerset of U into itself and is an involution on subsets of U, the terms being evaluated are in bijection. In each direction, the universal property of the gcd reduces the goal to showing divisibility for each subset, which holds because the complement of any subset is again a member of the powerset.

  1. Equality of the two greatest common divisors reduces to mutual divisibility.

    By antisymmetry of divisibility on the natural numbers (Nat.dvd_antisymm), two numbers are equal if each divides the other. This splits the equality into two divisibility goals: showing that the gcd of f(U \ A) divides the gcd of f(A), and conversely.

    line 4

    uses Nat.dvd_antisymm

      apply Nat.dvd_antisymm
  2. The gcd of f(U \ A) over all subsets A of U divides the gcd of f(A) over all subsets A of U.

    By Finset.dvd_gcd_iff.mpr, to show that a number divides the gcd of f over the powerset of U, it suffices to show it divides f(A) for every subset A ⊆ U. For any such A, its complement U \ A is also a subset of U (by Finset.sdiff_subset and Finset.mem_powerset.mpr), so by definition of the gcd (Finset.gcd_dvd), the gcd over all complements divides f(U \ (U \ A)). Since A ⊆ U, the double complement U \ (U \ A) simplifies to A by Finset.sdiff_sdiff_eq_self and Finset.mem_powerset.mp, giving the required divisibility.

    lines 5–9

    uses Finset.dvd_gcd_iff.mpr, Finset.mem_powerset.mpr, Finset.sdiff_subset, Finset.gcd_dvd, Finset.sdiff_sdiff_eq_self, Finset.mem_powerset.mp

      · apply Finset.dvd_gcd_iff.mpr
        intro A hA
        have hc : U \ A ∈ U.powerset := Finset.mem_powerset.mpr Finset.sdiff_subset
        have hd := Finset.gcd_dvd (f := fun A => f (U \ A)) hc
        simpa only [Finset.sdiff_sdiff_eq_self (Finset.mem_powerset.mp hA)] using hd
  3. The gcd of f(A) over all subsets A of U divides the gcd of f(U \ A) over all subsets A of U.

    Similarly, by Finset.dvd_gcd_iff.mpr, it suffices to show that the gcd of f over the powerset divides f(U \ A) for every subset A of U. Since U \ A ⊆ U (via Finset.sdiff_subset and Finset.mem_powerset.mpr), the complement U \ A belongs to the powerset of U, so the gcd divides f(U \ A) directly by Finset.gcd_dvd.

    lines 10–12

    uses Finset.dvd_gcd_iff.mpr, Finset.gcd_dvd, Finset.mem_powerset.mpr, Finset.sdiff_subset

      · apply Finset.dvd_gcd_iff.mpr
        intro A hA
        exact Finset.gcd_dvd (Finset.mem_powerset.mpr Finset.sdiff_subset)
Nat.dvd_antisymm
Two natural numbers are equal if each divides the other.
Finset.dvd_gcd_iff.mpr
If a number divides f(b) for all b in a finite set s, then it divides the greatest common divisor of f over s.
Finset.mem_powerset.mpr
A finite set belongs to the powerset of t if it is a subset of t.
Finset.sdiff_subset
For any finite sets s and t, the difference s \ t is a subset of s.
Finset.gcd_dvd
The greatest common divisor of a function f over a finite set s divides f(b) for any element b in s.
Finset.sdiff_sdiff_eq_self
If t is a subset of s, then the double complement s \ (s \ t) equals t.
Finset.mem_powerset.mp
If a finite set belongs to the powerset of t, then it 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 finite_powerset_gcd_complement {α : Type*} [DecidableEq α]    (U : Finset α) (f : Finset α → ℕ) :    U.powerset.gcd (fun A => f (U \ A)) = U.powerset.gcd f := by  apply Nat.dvd_antisymm  · apply Finset.dvd_gcd_iff.mpr    intro A hA    have hc : U \ A ∈ U.powerset := Finset.mem_powerset.mpr Finset.sdiff_subset    have hd := Finset.gcd_dvd (f := fun A => f (U \ A)) hc    simpa only [Finset.sdiff_sdiff_eq_self (Finset.mem_powerset.mp hA)] using hd  · apply Finset.dvd_gcd_iff.mpr    intro A hA    exact Finset.gcd_dvd (Finset.mem_powerset.mpr Finset.sdiff_subset)
See it in the graphDiscuss this resultChallenge it