The Marica–Schönheim inequality
ProvedFamousTheorems.marica_schonheim_inequalityThe Marica–Schönheim inequality. Let be a finite family of elements of a generalised Boolean algebra, for example a finite family of sets. Then the family of differences has at least as many elements as :
Marica and Schönheim proved it in 1969 and used it to settle the squarefree case of Graham's conjecture on greatest common divisors: for squarefree positive integers , some quotient is at least .
Formalization note. Mathlib's Finset.card_le_card_diffs. s.diffs s is the finset .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem marica_schonheim_inequality {α : Type*} [DecidableEq α] [GeneralizedBooleanAlgebra α] (s : Finset α) : s.card ≤ (s.diffs s).card := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Finset.card_le_card_diffs`. Proof here reduces to that Mathlib result.