The Ahlswede–Daykin inequality (Ahlswede & Daykin 1978), also known as the four functions theorem (or inequality), is a correlation-type inequality for four functions on a finite distributive lattice. It is a fundamental tool in statistical mechanics and probabilistic combinatorics (especially random graphs and the probabilistic method). The inequality states that if f 1 , f 2 , f 3 , f 4 {\displaystyle f_{1},f_{2},f_{3},f_{4}} are nonnegative functions on a finite distributive lattice such that
f 1 ( x ) f 2 ( y ) ≤ f 3 ( x ∨ y ) f 4 ( x ∧ y ) {\displaystyle f_{1}(x)f_{2}(y)\leq f_{3}(x\vee y)f_{4}(x\wedge y)}
for all x, y in the lattice, then
f 1 ( X ) f 2 ( Y ) ≤ f 3 ( X ∨ Y ) f 4 ( X ∧ Y ) {\displaystyle f_{1}(X)f_{2}(Y)\leq f_{3}(X\vee Y)f_{4}(X\wedge Y)}
for all subsets X, Y of the lattice, where
f ( X ) = ∑ x ∈ X f ( x ) {\displaystyle f(X)=\sum _{x\in X}f(x)}
and
X ∨ Y = { x ∨ y ∣ x ∈ X , y ∈ Y } {\displaystyle X\vee Y=\{x\vee y\mid x\in X,y\in Y\}}
X ∧ Y = { x ∧ y ∣ x ∈ X , y ∈ Y } . {\displaystyle X\wedge Y=\{x\wedge y\mid x\in X,y\in Y\}.}
The Ahlswede–Daykin inequality can be used to provide a short proof of both the Holley inequality and the FKG inequality. It also implies the XYZ inequality. For a proof, see the original article (Ahlswede & Daykin 1978) or (Alon & Spencer 2000).
Generalizations The "four functions theorem" was independently generalized to 2k functions in (Aharoni & Keich 1996) and (Rinott & Saks 1991).
History The story of the discovery of the Ahlswede–Daykin inequality was described in the Introduction to the A. Ahlswede et al. book:
"The history of the idea of the AD-inequality is very interesting. As Daykin came to a visit to Bielefeld, Ahlswede was just wallpapering. He stood on the ladder, and Daykin wanted to tell him from a newly proven inequality. The declaration was complicated, and Ahlswede said that probably a more general (and easier) theorem should hold. He made directly—on the ladder—a proposal which already was the AD-inequality."
References
Sources Ahlswede, Rudolf; Daykin, David E. (1978), "An inequality for the weights of two families of sets, their unions and intersections", Probability Theory and Related Fields, 43 (3): 183–185, CiteSeerX 10.1.1.380.8629, doi:10.1007/BF00536201, ISSN 0178-8051, MR 0491189, S2CID 120659862 {{citation}}: Cite uses deprecated parameter |citeseerx= (help) Alon, N.; Spencer, J. H. (2000), The probabilistic method. Second edition. With an appendix on the life and work of Paul Erdős., Wiley-Interscience, New York, ISBN 978-0-471-37046-8, MR 1885388 Fishburn, P.C. (2001) [1994], "Ahlswede–Daykin inequality", Encyclopedia of Mathematics, EMS Press Aharoni, Ron; Keich, Uri (1996), "A Generalization of the Ahlswede Daykin Inequality", Discrete Mathematics, 152 (1–3): 1–12, doi:10.1016/0012-365X(94)00294-S Rinott, Yosef; Saks, Michael (1991), "Correlation inequalities and a conjecture for permanents", Combinatorica, 13 (3): 269–277, doi:10.1007/BF01202353, S2CID 206791629