finite_powerset_gcd_complement
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
- 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 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.
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.
uses
Nat.dvd_antisymmapply Nat.dvd_antisymmThe 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.
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
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.
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
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_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)