Loomis–Whitney inequality

Result in geometry

In mathematics, the Loomis–Whitney inequality is a result in geometry, which in its simplest form, allows one to estimate the "size" of a d {\displaystyle d} -dimensional set by the sizes of its ( d − 1 ) {\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 d ≥ 2 {\displaystyle d\geq 2} and consider the projections

π j : R d → R d − 1 , {\displaystyle \pi _{j}:\mathbb {R} ^{d}\to \mathbb {R} ^{d-1},}
π j : x = ( x 1 , … , x d ) ↦ x ^ j = ( x 1 , … , x j − 1 , x j + 1 , … , x d ) . {\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

g j : R d − 1 → [ 0 , + ∞ ) , {\displaystyle g_{j}:\mathbb {R} ^{d-1}\to [0,+\infty ),}
g j ∈ L d − 1 ( R d − 1 ) . {\displaystyle g_{j}\in L^{d-1}(\mathbb {R} ^{d-1}).}

Then the Loomis–Whitney inequality holds:

‖ ∏ j = 1 d g j ∘ π j ‖ L 1 ( R d ) = ∫ R d ∏ j = 1 d g j ( π j ( x ) ) d x ≤ ∏ j = 1 d ‖ g j ‖ L d − 1 ( R d − 1 ) . {\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 f j ( x ) = g j ( x ) d − 1 , {\displaystyle f_{j}(x)=g_{j}(x)^{d-1},} we have

f j : R d − 1 → [ 0 , + ∞ ) , {\displaystyle f_{j}:\mathbb {R} ^{d-1}\to [0,+\infty ),}
f j ∈ L 1 ( R d − 1 ) {\displaystyle f_{j}\in L^{1}(\mathbb {R} ^{d-1})}

implying

∫ R d ∏ j = 1 d f j ( π j ( x ) ) 1 / ( d − 1 ) d x ≤ ∏ j = 1 d ( ∫ R d − 1 f j ( x ^ j ) d x ^ j ) 1 / ( d − 1 ) . {\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 R d {\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 R d {\displaystyle \mathbb {R} ^{d}} and let

f j = 1 π j ( E ) {\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,

∏ j = 1 d f j ( π j ( x ) ) 1 / ( d − 1 ) = 1. {\displaystyle \prod _{j=1}^{d}f_{j}(\pi _{j}(x))^{1/(d-1)}=1.}

Hence, by the Loomis–Whitney inequality,

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

and hence

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

The quantity

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

can be thought of as the average width of E {\displaystyle E} in the j {\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 d = 1 , 2 {\displaystyle d=1,2} , it is obvious. Now induct on d + 1 {\displaystyle d+1} . The only trick is to use Hölder's inequality for counting measures.

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

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

  • I 1 , . . . , I k {\displaystyle I_{1},...,I_{k}} enumerate all such integer unit intervals on the 0-th coordinate.
  • Let T i {\displaystyle T_{i}} be the set of all unit cubes that projects to I i {\displaystyle I_{i}} .
  • Let N j {\displaystyle N_{j}} be the area of π j ( T ) {\displaystyle \pi _{j}(T)} , with j = 0 , 1 , . . . , d {\displaystyle j=0,1,...,d} .
  • Let a i {\displaystyle a_{i}} be the volume of T i {\displaystyle T_{i}} . We have ∑ i a i = N {\displaystyle \sum _{i}a_{i}=N} , and a i ≤ N 0 {\displaystyle a_{i}\leq N_{0}} .
  • Let T i j {\displaystyle T_{ij}} be π j ( T i ) {\displaystyle \pi _{j}(T_{i})} for all j = 1 , . . . , d {\displaystyle j=1,...,d} .
  • Let a i j {\displaystyle a_{ij}} be the area of T i j {\displaystyle T_{ij}} . We have ∑ i a i j = N j {\displaystyle \sum _{i}a_{ij}=N_{j}} .

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

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

Thus

N = ∑ i a i ≤ ∑ i N 0 1 / d ∏ j = 1 d a i j 1 / d = N 0 1 / d ∑ i = 1 k ∏ j = 1 d a i j 1 / d {\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:

∑ i = 1 k ∏ j = 1 d a i j 1 / d = ∫ i ∏ j = 1 d a i j 1 / d = ‖ ∏ j = 1 d a ⋅ , j 1 / d ‖ 1 ≤ ∏ j ‖ a ⋅ , j 1 / d ‖ d = ∏ j = 1 d ( ∑ i = 1 k a i j ) 1 / d {\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 ∑ i a i j = N j {\displaystyle \sum _{i}a_{ij}=N_{j}} , we get N d ≤ ∏ j = 0 d N j {\displaystyle N^{d}\leq \prod _{j=0}^{d}N_{j}}

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

| E | d − 1 ≤ 2 − d | ∂ E | d {\displaystyle |E|^{d-1}\leq 2^{-d}|\partial E|^{d}}
Iterating the theorem yields | E | ≤ ∏ 1 ≤ j < k ≤ d | π j ∘ π k ( E ) | ( d − 1 2 ) − 1 {\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]
| E | ≤ ∏ j | π j ( E ) | ( d − 1 k ) − 1 {\displaystyle |E|\leq \prod _{j}|\pi _{j}(E)|^{{\binom {d-1}{k}}^{-1}}}
where π j {\displaystyle \pi _{j}} enumerates over all projections of R d {\displaystyle \mathbb {R} ^{d}} to its d − k {\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. ^ a b 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.