A New Proof Of An Ancient Result

Gödel’s Lost Letter and P=NP 2018-05-05

Triangulating proofs to seek a shorter path

Cropped from 2016 Newsday source

Mehtaab Sawhney is an undergraduate student at MIT. His work caught my eye on finding his recent paper with David Stoner about permutations that map all three-term arithmetic progressions mod ${n}$ to non-progressions. Here a progression is an ordered triple ${(a,b,c)}$ where ${a -2b + c = 0 \pmod{n}}$ . The paper addresses when such permutations can be found in certain small subgroups of ${S_n}$ while I am interested in senses by which they are succinct. This made me curious about Sawhney’s other work.

Today Ken and I wish to report on Sawhney’s simple new proof of the famous triangle inequality in ${\mathbb{R}^n}$ .

Sawhney presents his new proof in a short note which has just appeared on p218 of last month’s issue of the College Journal of Mathematics:

An Unusual Proof of the Triangle Inequality.

Summary: A standard proof of triangle inequality requires using Cauchy-Schwarz inequality. The proof here bypasses such tools by instead relying on expectations.

Recall that the triangle inequality for the Euclidean norm on ${n}$ dimensions says that for any vectors ${X}$ and ${Y}$ ,

$\displaystyle || X + Y || \le ||X|| + ||Y||.$

Here as usual the norm of a vector ${V}$ is

$\displaystyle \left( \sum_{i=1}^{n} V_{i}^{2} \right)^{1/2}.$

The “standard proof” he refers to is represented by this one taken from Wikipedia’s triangle inequality article:

$\displaystyle \begin{array}{rcl} ||X + Y\|^2 &=& \langle X + Y, X + Y \rangle \\ \\ &=& ||X||^2 + \langle X, Y \rangle + \langle Y, X \rangle + ||Y||^2 \\ \\ &\le& ||X||^2 + 2|\langle X, Y \rangle| + ||Y||^2 \\ \\ &\le& ||X||^2 + 2||X|| \cdot ||Y|| + ||Y||^2 \\ \\ &=& \left( ||X|| + ||Y||\right)^2. \end{array}$

Here Cauchy-Schwarz is used to obtain line 4. Now Cauchy-Schwarz also requires a few lines to prove—indeed one could write a book about it. It feels like the combined proof is tracing two sides ${X}$ and ${Y}$ of a triangle, when there ought to be a shorter and direct third side. That is what Sawhney offers.

The New Proof

He can prove the triangle inequality in ${n}$ dimensions by only using the trivial one-dimensional version. That is the fact that for the absolute value

$\displaystyle |x+y| \le |x| + |y|,$

where ${x}$ and ${y}$ are real numbers. Well, it needs the notion of mathematical expected value ${E_{x \in S} f(x)}$ . This is formally defined via integration on ${S}$ . But he really only needs that expected value obeys some simple properties that one could say are “expected”: additivity, linearity, and ability to manipulate its argument. The one special property is that the norm of a vector ${V}$ in ${\mathbb{R}^n}$ scales as the expected value of its inner product with a unit vector ${U}$ . Formally:

$\displaystyle \begin{array}{rcl} E_{||U||=1}(U \cdot V) &= &E_{||U||=1} \left( \left| U \cdot \left( \frac{V}{||V||} \right) ||V|| \right| \right) \\ \\&=& ||V|| E_{||U||=1} ( |U \cdot (1,0,\dotsc,0) |) \\ \\ &=& C ||V||, \end{array}$

where ${C}$ is a fixed nonzero constant. For ${n = 2}$ one takes the integral of ${|\cos \theta|}$ over the circle, which is ${4}$ , and divides it by ${2\pi}$ to make an average, so ${C = 2/\pi}$ . The values for higher ${n}$ are different but the difference doesn’t matter, only that ${C}$ is fixed and nonzero. The rest of the proof needs only the 1-dimensional triangle inequality to go from line 1 to line 2:

$\displaystyle \begin{array}{rcl} ||X || + ||Y|| -||X + Y|| &=& \frac{1}{C} E_{||U||=1}( |U \cdot X| + |U \cdot Y| - |U \cdot (X + Y) | ) \\ \\ &\ge& \frac{1}{C} E_{||U||=1}( |U \cdot X + U \cdot Y| - |U \cdot (X + Y) | )\\ \\ &=& \frac{1}{C} E_{||U||=1}( |U \cdot (X + Y)| - |U \cdot (X + Y) | )\\ \\ &=& \frac{1}{C} E_{||U||=1}(0)\\ \\ &=& 0. \end{array}$

Pretty neat. No?

Why Care?

I must say that I was quite surprised to see a radically different proof that did not use Cauchy-Schwarz or some equivalent inequality.

Sawhney’s proof is also one a computer theorist could have found. The idea that he relies on is quite neat: the norm of a vector can be computed by taking random projections. This is not elementary but it is intuitive. It is something that “we all know”—yet we did not make the connection to the triangle inequality. This is another example of the power of expectation as a concept.

As Sawhney remarks in his note, the Cauchy-Schwarz inequality can be proved from the triangle inequality by reversing the flow of the proof cited above from Wikipedia, hence it can now be derived via his proof. But that again would be taking two sides of a triangle, while Cauchy-Schwarz has a direct proof. What’s nice is that now both inequalities have a proof that doesn’t reference the other and have a nice bridge between them.

Open Problems

The obvious open problem is: can we use a similar randomness trick to prove other inequalities? Perhaps there are new proofs to be discovered; perhaps there are open inequalities that can be attacked by this method.