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

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.