The Brunn-Minkowski Theorem

Today I want to prove the Brunn-Minkowski inequality. Let $\mu$ be the lebesgue measure. For any two sets $A, B \subset \mathbb{R}^d$ define $ A+B=\{a+b:a\in A, b\in B\}$. The Brunn-Minkowski theorem then states that if $A$,$B$ and $A+B$ are all measurable then the following inequality holds $$\mu (A+B)^{1/d} \geq \mu (A)^{1/d} + \mu (B)^{1/d}$$

We will first prove this for the case that $A,B$ are cuboids(with axe parallel  edges):

Let $A$ be a cube with side lengths $a_1,...,a_n$ and $B$ a cube with side length $b_1,...b_n$. Then $A+B$ is a cube with side lengths $a_1+b_1,...a_n+b_n$. Thus we have:

\begin{equation}
\begin{split}
& \frac{ \mu (A)^{1/n} + \mu (B)^{1/n}} {\mu (A+B)^{1/n}}
 =\frac{(\prod_{i=1}^n a_i)^{1/n}+(\prod_{i=1}^n b_i)^{1/n}}{(\prod_{i=1}^n a_i+b_i)^{1/n}} \\
& = (\prod_{i=1}^n  \frac{ a_i}{a_i+b_i})^{1/n}+(\prod_{i=1}^n \frac{ b_i}{ a_i+b_i})^{1/n} \\
& \leq \frac{1}{n} \sum_{i=1}^n  \frac{ a_i}{a_i+b_i}+\frac{1}{n} \sum_{i=1}^n \frac{ b_i}{ a_i+b_i}=1
\end{split}
\end{equation}
Now comes the cool part. We proof the inequality in the case that $A,B$ are finite unions of cuboids with disjoint interior.For this we do induction over the the number of cubes in the union $A \cup B$. We already dealt with the case when $A$ and $B$ are cuboids. So we may assume that $A$ is the union of at least two cuboids. Furthermore we may assume without loss of generality that the hyperplane $\{x \in \mathbb{R}: x_1=0\}$ seperates two cubes in $A$.
Define the sets $$A^+=\{x\in A: x_1 \geq 0\}, A^-=\{x\in A: x_1 \leq 0\}, B^+=\{x\in B: x_1 \geq 0\}, B^-=\{x\in B: x_1 \leq 0\},$$
Because $B$ is bounded we have $\frac{\mu(B^++te_2}{\mu(B+te_2)}$ is equal to $1$ for $t$ sufficiently large and $0$ for $-t$ sufficiently large. Since the map $ t \mapsto \frac{\mu(B^++te_2}{\mu(B+te_2)}$ is continuous we conclude that there exists $t$ such that $\frac{\mu(B^++te_2)}{\mu(B+te_2)}=\frac{\mu(A^++te_2)}{\mu(A+te_2)}$. So we can assume that  $\frac{\mu(B^+}{\mu(B)}=\frac{\mu(A^+)}{\mu(A)}$. Since $A^+$ is a strict subset of $A$ the sets $A^+ \cup B^+$ and $A^- \cup B^-$ are made up of fewer cuboids then $A \cup B$. We have
\begin{equation}
\begin{split}
& \mu(A+ B)\geq \mu(A^+ + B^+)+\mu(A^- + B^-) \\
& \geq (\mu(A^+)^{1/n} +\mu(B^+)^{1/n})^n+(\mu(A^-)^{1/n} +\mu(B^-)^{1/n})^n \\
&=\mu(A^+)(1+(\frac{\mu(B^+)}{\mu(A^+)})^{1/n})^n+\mu(A^-)(1+(\frac{\mu(B^-)}{\mu(A^-)})^{1/n})^n \\
&= (\mu(A^+)+\mu(A^-))(1+(\frac{\mu(B)}{\mu(A)})^{1/n})^n \\
&= (\mu(A)^{1/n}+\mu(B)^{1/n})^n
\end{split}
\end{equation}
So by induction we are done. Now we can approximate any open set by boxes. So the inequalities follows for open sets. Now the inequality easily follows for measurable sets, because any measurable set can be approximated by open sets.





			
The Brunn-Minkowski Theorem

Chaos princess

A couple of weeks ago a friend told me this nice puzzle. The situation is as follows: A king wants to wed one of his three daughters to a prince. Since the three princess are triplets he leaves the choice to the prince, but there is one crux: the first princess always lies (we call her the false princess or sometimes jus False), the second one always says the truth (we call her the true princess or just True) and the third princess randomly lies or tells the truth (we call her the chaos princess). The prince shall ask only one question to one princess for which the answer is either yes or no. Only the princess to whom he is posing the question is allowed to answer. After that he must choose one princess who will then become his wife. It is forbidden to pose questions which are neither true or false. For example you are not allowed to ask: “is this sentence wrong?”.

Remark: The chaos princess response should be thought of as depending on the flip of a fair coin hidden in her brain: if the coin comes down heads, she speaks truly; if tails, falsely.

Question: What should the prince ask if he doesn’t want to marry the chaos princess?

Before answering this question let’s first try to solve two easier puzzles.

1st Puzzle: If the situation is the same as described above but the false princess is also a true princess, how can we find with one yes-no question one of the true princess?

2nd Puzzle: Now assume you know that you are speaking to the True or False princess and you want to know whether Dushanbe is in Kirghizia or not. You are allowed to ask one yes-or-no question. How can you identify the right answer (of course, here we assume that both princess know the correct answer).

Solution to 1: Go to the middle princess and ask her: “Is the left princess the chaos princess?”. If the answer is “YES”, take the princess on the right. If the answer is “NO”, take the princess on the left. So why does this work? If the middle princess is the chaos princess, then the answer is irrelevant because you will not take the princess in the middle anyway. If the princess in the middle is one of the true princess, then the answer will be truthful and our strategy will work as well.

Solution to 2: If we ask the question “Are you True if and only if Dushanbe is in Kirghizia?”, then there are four possibilities:

  1. The princess is true + Dushanbe is in Kirghizia: Then the answer is YES.
  2. The princess is true + Dushanbe is not in Kirghizia: Then the answer is NO.
  3. The princess is False + Dushanbe is in Kirghizia: The equivalence is wrong, hence the answer will be YES, because you are talking to False.
  4. The princess is False + Dushanbe is not in Kirghizia: Then the equivalence is correct (because both statements are wrong) and you will therefore get the answer NO.

Note that there is nothing special about the question: “Is Dushanbe in Kirghizia?”. If A is any statement, then we get the right answer to the question “Are you True iff A is true?”, i.e. we get the answer “YES” if A is true and the answer “NO” if A is not true.

Now let put the two puzzles together to answer the initial question!

We go to the middle princess and ask her the following question: “Are you true iff the left princess is not the random princess?”, if the answer is “YES”, then we take the left princess as our bride. If the answer is “NO”, then we marry the right princess. Using Puzzle 2 we will always get the correct answer when asking the true or false princess, thus by Puzzle 1 we will never marry the chaos princess.

Remark: By the way Dushanbe is in Tajikistan not in Khirgizia.

Chaos princess