Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 11 / 3

The Ahlswede–Daykin inequality, also called the four functions theorem, concerns nonnegative functions $\alpha ,\beta ,\gamma ,\delta$ on $\mathcal{P}([n])$. IfthenProve it by induction on $n$. The case $n=0$ is the single assumed inequality. For the induction step, sum each function over the last coordinate to obtain ${\alpha }^{\prime },{\beta }^{\prime },{\gamma }^{\prime },{\delta }^{\prime }$ on $\mathcal{P}([n-1])$. For fixed $A,B$ in this smaller cube, set $a_i=\alpha (A\cup i\{n\})$, $b_i=\beta (B\cup i\{n\})$, $c_i=\gamma ((A\cup B)\cup i\{n\})$, and $d_i=\delta ((A\cap B)\cup i\{n\})$, where $i\{n\}$ is empty for $i=0$ and $\{n\}$ for $i=1$.

The hypotheses give $a_0{b}_0\le c_0{d}_0$, $a_1{b}_1\le c_1{d}_1$ and $a_0{b}_1,a_1{b}_0\le c_1{d}_0$. The two-point four-functions inequality shows that these imply $(a_0+a_1)(b_0+b_1)\le (c_0+c_1)(d_0+d_1)$. Here is its key algebra: put $x=a_0{b}_1$, $y=a_1{b}_0$, $M=c_1{d}_0$, $N=c_0{d}_1$. Then $x,y\le M$ and $xy\le MN$. If $M>0$, $(M-x)(M-y)\ge 0$ gives $x+y\le M+xy/M\le M+N$; if $M=0$, both cross terms vanish. Adding the two diagonal bounds proves the claim.

Thus the primed functions satisfy the same hypothesis, and the induction hypothesis applies. Their totals equal the original totals, completing the proof.

In the four functions theorem, take $\alpha =1_{\mathcal{A}}$, $\beta =1_{\mathcal{B}}$, $\gamma =1_{\mathcal{A}\vee \mathcal{B}}$ and $\delta =1_{\mathcal{A}\wedge \mathcal{B}}$, where the union and intersection of set families are the collections of all pairwise unions and intersections.

If $\alpha (A)\beta (B)=1$, then $A\cup B\in \mathcal{A}\vee \mathcal{B}$ and $A\cap B\in \mathcal{A}\wedge \mathcal{B}$, so the pointwise hypothesis holds. Otherwise its left side is zero. Summing these indicator functions gives

Complement the members of $\mathcal{B}$ in the fixed ground set: $\mathcal{C}=\{[n]\setminus B:B\in \mathcal{B}\}$, so $|\mathcal{C}|=|\mathcal{B}|$. The set difference identitiesshow that $\mathcal{A}\wedge \mathcal{C}=\mathcal{A}-\mathcal{B}$, while complementation bijects $\mathcal{A}\vee \mathcal{C}$ with $\mathcal{B}-\mathcal{A}$. Applying the four functions theorem to $\mathcal{A},\mathcal{C}$ therefore givesThe products count distinct resulting sets, with repeated pairwise differences included only once.