Loomis–Whitney inequality

In mathematics, the Loomis–Whitney inequality is a result in geometry, which in its simplest form, allows one to estimate the "size" of a ${\displaystyle d}$-dimensional set by the sizes of its ${\displaystyle (d-1)}$-dimensional projections. The inequality has applications in incidence geometry, the study of so-called "lattice animals", and other areas.

The result is named after the American mathematicians Lynn Harold Loomis and Hassler Whitney, and was published in 1949.

Statement of the inequality

Fix a dimension ${\displaystyle d\geq 2}$  and consider the projections

${\displaystyle \pi _{j}:\mathbb {R} ^{d}\to \mathbb {R} ^{d-1},}$ 

${\displaystyle \pi _{j}:x=(x_{1},\dots ,x_{d})\mapsto {\hat {x}}_{j}=(x_{1},\dots ,x_{j-1},x_{j+1},\dots ,x_{d}).}$ 

For each 1 ≤ j ≤ d, let

${\displaystyle g_{j}:\mathbb {R} ^{d-1}\to [0,+\infty ),}$ 

${\displaystyle g_{j}\in L^{d-1}(\mathbb {R} ^{d-1}).}$ 

Then the Loomis–Whitney inequality holds:

${\displaystyle \left\|\prod _{j=1}^{d}g_{j}\circ \pi _{j}\right\|_{L^{1}(\mathbb {R} ^{d})}=\int _{\mathbb {R} ^{d}}\prod _{j=1}^{d}g_{j}(\pi _{j}(x))\,\mathrm {d} x\leq \prod _{j=1}^{d}\|g_{j}\|_{L^{d-1}(\mathbb {R} ^{d-1})}.}$ 

Equivalently, taking ${\displaystyle f_{j}(x)=g_{j}(x)^{d-1},}$  we have

${\displaystyle f_{j}:\mathbb {R} ^{d-1}\to [0,+\infty ),}$ 

${\displaystyle f_{j}\in L^{1}(\mathbb {R} ^{d-1})}$ 

implying

${\displaystyle \int _{\mathbb {R} ^{d}}\prod _{j=1}^{d}f_{j}(\pi _{j}(x))^{1/(d-1)}\,\mathrm {d} x\leq \prod _{j=1}^{d}\left(\int _{\mathbb {R} ^{d-1}}f_{j}({\hat {x}}_{j})\,\mathrm {d} {\hat {x}}_{j}\right)^{1/(d-1)}.}$ 

A special case

The Loomis–Whitney inequality can be used to relate the Lebesgue measure of a subset of Euclidean space ${\displaystyle \mathbb {R} ^{d}}$  to its "average widths" in the coordinate directions. This is in fact the original version published by Loomis and Whitney in 1949 (the above is a generalization).^[1]

Let E be some measurable subset of ${\displaystyle \mathbb {R} ^{d}}$  and let

${\displaystyle f_{j}=\mathbf {1} _{\pi _{j}(E)}}$ 

be the indicator function of the projection of E onto the jth coordinate hyperplane. It follows that for any point x in E,

${\displaystyle \prod _{j=1}^{d}f_{j}(\pi _{j}(x))^{1/(d-1)}=1.}$ 

Hence, by the Loomis–Whitney inequality,

${\displaystyle |E|\leq \prod _{j=1}^{d}|\pi _{j}(E)|^{1/(d-1)},}$ 

and hence

${\displaystyle |E|\geq \prod _{j=1}^{d}{\frac {|E|}{|\pi _{j}(E)|}}.}$ 

The quantity

${\displaystyle {\frac {|E|}{|\pi _{j}(E)|}}}$ 

can be thought of as the average width of ${\displaystyle E}$  in the ${\displaystyle j}$ th coordinate direction. This interpretation of the Loomis–Whitney inequality also holds if we consider a finite subset of Euclidean space and replace Lebesgue measure by counting measure.

The following proof is the original one^[1]

Proof

Overview: We prove it for unions of unit cubes on the integer grid, then take the continuum limit. When ${\displaystyle d=1,2}$ , it is obvious. Now induct on ${\displaystyle d+1}$ . The only trick is to use Hölder's inequality for counting measures.

Enumerate the dimensions of ${\displaystyle \mathbb {R} ^{d+1}}$  as ${\displaystyle 0,1,...,d}$ .

Given ${\displaystyle N}$  unit cubes on the integer grid in ${\displaystyle \mathbb {R} ^{d+1}}$ , with their union being ${\displaystyle T}$ , we project them to the 0-th coordinate. Each unit cube projects to an integer unit interval on ${\displaystyle \mathbb {R} }$ . Now define the following:

• ${\displaystyle I_{1},...,I_{k}}$  enumerate all such integer unit intervals on the 0-th coordinate.

• Let ${\displaystyle T_{i}}$  be the set of all unit cubes that projects to ${\displaystyle I_{i}}$ .

• Let ${\displaystyle N_{j}}$  be the area of ${\displaystyle \pi _{j}(T)}$ , with ${\displaystyle j=0,1,...,d}$ .

• Let ${\displaystyle a_{i}}$  be the volume of ${\displaystyle T_{i}}$ . We have ${\displaystyle \sum _{i}a_{i}=N}$ , and ${\displaystyle a_{i}\leq N_{0}}$ .

• Let ${\displaystyle T_{ij}}$  be ${\displaystyle \pi _{j}(T_{i})}$  for all ${\displaystyle j=1,...,d}$ .

• Let ${\displaystyle a_{ij}}$  be the area of ${\displaystyle T_{ij}}$ . We have ${\displaystyle \sum _{i}a_{ij}=N_{j}}$ .

By induction on each slice of ${\displaystyle T_{i}}$ , we have ${\displaystyle a_{i}^{d-1}\leq \prod _{j=1}^{d}a_{ij}}$ 

Multiplying by ${\displaystyle a_{i}\leq N_{0}}$ , we have ${\displaystyle a_{i}^{d}\leq N_{0}\prod _{j=1}^{d}a_{ij}}$ 

Thus

$${\displaystyle N=\sum _{i}a_{i}\leq \sum _{i}N_{0}^{1/d}\prod _{j=1}^{d}a_{ij}^{1/d}=N_{0}^{1/d}\sum _{i=1}^{k}\prod _{j=1}^{d}a_{ij}^{1/d}}$$

 

Now, the sum-product can be written as an integral over counting measure, allowing us to perform Holder's inequality:

$${\displaystyle \sum _{i=1}^{k}\prod _{j=1}^{d}a_{ij}^{1/d}=\int _{i}\prod _{j=1}^{d}a_{ij}^{1/d}=\left\|\prod _{j=1}^{d}a_{\cdot ,j}^{1/d}\right\|_{1}\leq \prod _{j}\|a_{\cdot ,j}^{1/d}\|_{d}=\prod _{j=1}^{d}\left(\sum _{i=1}^{k}a_{ij}\right)^{1/d}}$$

 

Plugging in ${\displaystyle \sum _{i}a_{ij}=N_{j}}$ , we get ${\displaystyle N^{d}\leq \prod _{j=0}^{d}N_{j}}$ 

Corollary. Since ${\displaystyle 2|\pi _{j}(E)|\leq |\partial E|}$ , we get a loose isoperimetric inequality:

$${\displaystyle |E|^{d-1}\leq 2^{-d}|\partial E|^{d}}$$

 

Iterating the theorem yields ${\displaystyle |E|\leq \prod _{1\leq j<k\leq d}|\pi _{j}\circ \pi _{k}(E)|^{{\binom {d-1}{2}}^{-1}}}$  and more generally^[2]

$${\displaystyle |E|\leq \prod _{j}|\pi _{j}(E)|^{{\binom {d-1}{k}}^{-1}}}$$

 

where ${\displaystyle \pi _{j}}$  enumerates over all projections of ${\displaystyle \mathbb {R} ^{d}}$  to its ${\displaystyle d-k}$  dimensional subspaces.

Generalizations

The Loomis–Whitney inequality is a special case of the Brascamp–Lieb inequality, in which the projections π_j above are replaced by more general linear maps, not necessarily all mapping onto spaces of the same dimension.

References

1. Loomis, L. H.; Whitney, H. (1949). "An inequality related to the isoperimetric inequality". Bulletin of the American Mathematical Society. 55 (10): 961–962. doi:10.1090/S0002-9904-1949-09320-5. ISSN 0273-0979.
2. Burago, Yurii D.; Zalgaller, Viktor A. (2013-03-14). Geometric Inequalities. Springer Science & Business Media. p. 95. ISBN 978-3-662-07441-1.

Sources

• Alon, Noga; Spencer, Joel H. (2016). The probabilistic method. Wiley Series in Discrete Mathematics and Optimization (Fourth edition of 1992 original ed.). Hoboken, NJ: John Wiley & Sons, Inc. ISBN 978-1-119-06195-3. MR 3524748. Zbl 1333.05001.
• Boucheron, Stéphane; Lugosi, Gábor; Massart, Pascal (2013). Concentration inequalities. A nonasymptotic theory of independence. Oxford: Oxford University Press. doi:10.1093/acprof:oso/9780199535255.001.0001. ISBN 978-0-19-953525-5. MR 3185193. Zbl 1279.60005.
• Burago, Yu. D.; Zalgaller, V. A. (1988). Geometric inequalities. Grundlehren der mathematischen Wissenschaften. Vol. 285. Translated by Sosinskiĭ, A. B. Berlin: Springer-Verlag. doi:10.1007/978-3-662-07441-1. ISBN 3-540-13615-0. MR 0936419. Zbl 0633.53002.
• Hadwiger, H. (1957). Vorlesungen über Inhalt, Oberfläche und Isoperimetrie. Grundlehren der mathematischen Wissenschaften. Vol. 93. Berlin–Göttingen–Heidelberg: Springer-Verlag. doi:10.1007/978-3-642-94702-5. ISBN 3-642-94702-6. MR 0102775. Zbl 0078.35703.
• Loomis, L. H.; Whitney, H. (1949). "An inequality related to the isoperimetric inequality". Bulletin of the American Mathematical Society. 55 (10): 961–962. doi:10.1090/S0002-9904-1949-09320-5. MR 0031538. Zbl 0035.38302.