Ahlswede–Daykin inequality¶

A four-functions inequality on a finite distributive lattice that lifts a pointwise join–meet product bound to corresponding sums over subsets.

Version: v2 · 2026-09-19 · History
Domain-specific #: 3234
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Combinatorics → Mathematics

Core Idea¶

If nonnegative functions α, β, γ, and δ satisfy α(x)β(y)≤γ(x∨y)δ(x∧y), the Ahlswede–Daykin theorem bounds products of sums over sets by sums over their join and meet closures. Distributivity permits an induction that pairs lattice elements and preserves log-supermodular product structure, turning local four-function domination into a global correlation inequality. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

No faithful explanation at this level. All three agree a five-year-old version collapses into a generic 'if it holds for each pair it holds for the totals' slogan, which is false without the finite distributive lattice, nonnegativity and the exact join-meet four-function hypothesis.

The Sticker Score Promise

Imagine collections of stickers. For any two collections you can make a 'combined' collection (every sticker in either one) and a 'shared' collection (only the stickers in both). Now suppose you have four scoring rules that give each collection a score of zero or more, and they obey one small promise: for any two collections, score one of the first times score two of the second is never more than score three of the combined times score four of the shared. The Ahlswede–Daykin inequality says that small promise, checked pair by pair, is enough to make the same kind of promise true for whole groups of collections when you add up their scores.

Four Functions Theorem

The Ahlswede–Daykin inequality, also called the four functions theorem, turns a local rule into a global one. The setting is a finite distributive lattice, a structure where any two elements have a 'join' (like a union) and a 'meet' (like an intersection) that behave well together; the subsets of a set with union and intersection are the standard example. You have four functions α, β, γ, δ that are never negative, and you assume α(x)β(y) ≤ γ(x∨y)δ(x∧y) for every pair x, y. The conclusion is that for any two families A and B, the sum of α over A times the sum of β over B is at most the sum of γ over all joins a∨b times the sum of δ over all meets a∧b. The exact conditions matter: drop nonnegativity or distributivity, or change the conventions, and the conclusion is no longer guaranteed.

Let L be a finite distributive lattice and α, β, γ, δ: L → [0, ∞). The Ahlswede–Daykin (four functions) theorem states that if α(x)β(y) ≤ γ(x∨y)δ(x∧y) holds pointwise for all x, y ∈ L, then for all subsets A, B ⊆ L, α(A)β(B) ≤ γ(A∨B)δ(A∧B), where f(S) denotes Σ_{s∈S} f(s), A∨B = {a∨b : a∈A, b∈B}, and A∧B = {a∧b : a∈A, b∈B}. The hypothesis is local, a four-function domination condition on pairs; the conclusion is a global correlation inequality on set sums. The proof is an induction that uses distributivity to pair up lattice elements while preserving the log-supermodular product structure. It belongs to combinatorics, but its identity is narrower than the topic: the carrier must really be a finite distributive lattice, the functions nonnegative, and the hypothesis and conclusion stated with the theorem's exact join/meet conventions. Checking an application means typing the carrier and testing each condition, not relying on resemblance to other correlation inequalities.

Scope of Application¶

Ahlswede–Daykin inequality belongs to combinatorics and is useful where the analyst can specify the typed combinatorics carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, then evaluate the carrier is a finite distributive lattice, all functions are nonnegative, and the pointwise join–meet hypothesis and set-sum conclusion use the theorem’s exact conventions. The scope is broad within that domain but bounded by the need for the carrier is a finite distributive lattice, all functions are nonnegative, and the pointwise join–meet hypothesis and set-sum conclusion use the theorem’s exact conventions. The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the carrier is a finite distributive lattice, all functions are nonnegative, and the pointwise join–meet hypothesis and set-sum conclusion use the theorem’s exact conventions the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test. A bare label is insufficient because the name Ahlswede–Daykin inequality can be used for a formal identity, an implementation, or a neighboring result unless carrier and convention are stated.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Ahlswede–Daykin inequality. Ahlswede–Daykin inequality compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed combinatorics carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the carrier is a finite distributive lattice, all functions are nonnegative, and the pointwise join–meet hypothesis and set-sum conclusion use the theorem’s exact conventions independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of combinatorics because they reuse the typed combinatorics carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, Distributivity permits an induction that pairs lattice elements and preserves log-supermodular product structure, turning local four-function domination into a global correlation inequality., and type the carrier, state every parameter and convention in the definition, test that the carrier is a finite distributive lattice, all functions are nonnegative, and the pointwise join–meet hypothesis and set-sum conclusion use the theorem’s exact conventions, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Ahlswede–Daykin inequality Domain-specific

Parents (1) — outgoing typed relations

Ahlswede–Daykin inequality is a kind of Constraint Prime

What makes it its own entry: the domain-specific identity determined by the carrier is a finite distributive lattice, all functions are nonnegative, and the pointwise join–meet hypothesis and set-sum conclusion use the theorem’s exact conventions.

Hierarchy path (1) — routes to 1 parentless root

Ahlswede–Daykin inequality → is a kind of Constraint

Neighborhood in Abstraction Space¶

Ahlswede–Daykin inequality sits in a crowded region of the domain-specific corpus (10^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Combinatorial Enumeration & Sequences (38 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25