Geometric stability via information theory
- School of Computer Science and Engineering
- Hebrew University of Jerusalem
- Faculty of Mathematics and Computer Science
- Weizmann Institute of Science
- More about Ehud Friedgut
Geometric stability via information theory, Discrete Analysis, 2016:10, 28pp.
Let A be a subset of R3. Then we can project A onto the xy-plane, the yz-plane and the xz-plane. If we are given the areas of these projections, how large can the volume of A be? A natural example to consider is when A is a cuboid aligned with the coordinate axes. In that case the volume of A is the square root of the product of the areas of the projections. That turns out to be the best we can do, by a famous result of Loomis and Whitney.
The Loomis-Whitney inequality is the following more general statement. Let g1,…,gd be non-negative functions defined on Rd−1 and for 1≤i≤d let ˜πi:Rd→Rd−1 be the projection that removes the ith coordinate from a vector. Then
To see how this relates to the statement about volumes, consider the case where each gi takes values 0 and 1. Then we can think of gi as the characteristic function of a set Ai, and ∏(gi∘˜πi) is then the characteristic function of the largest set A such that ˜πi(A)⊂Ai for each i. Also, ‖gi‖d−1=|Ai|1/(d−1), so the right-hand side is equal to the product of the (d−1)th roots of the volumes of the Ai. Setting d=3 we obtain the result stated in the first paragraph.
The Loomis-Whitney inequality has been further generalized. For example, the uniform-cover inequality of Chung, Frankl, Graham and Shearer (which is equivalent to the Box Theorem of Bollobás and Thomason) relates the volume of a set to the volumes of lower-dimensional projections (where these dimensions may differ), and the Brascamp-Lieb inequality can be used to relate the volume of a set to the volumes of projections that are not necessarily orthogonal to each other.
Given any inequality, it is natural to try to characterize the equality cases, which for the Loomis-Whitney and uniform-cover inequalities are given by products of subsets of R. It is also interesting, and often very useful, to understand the near-equality cases. The aim here tends to be to prove stability results, which state that if equality almost holds, then the example for which it almost holds is close (in some appropriate sense) to one for which it holds exactly. This paper proves stability versions of the Loomis-Whitney and uniform-cover inequalities, and obtains as a consequence a stability version of the edge-isoperimetric inequality in the grid Zd. This last inequality states that if A is a subset of Zd of cardinality m, then the number of edges incident with points in A is minimized when A is a cuboid (in the obvious sense).
Returning to the result mentioned at the beginning, it follows from the main result of this paper that if A⊂R3 has volume almost as large as the product of the square roots of the areas of its three projections, then there exist three subsets K1,K2,K3⊂R such that the measure of the symmetric difference A△(K1×K2×K3) is small.
To prove a stability version of an inequality, it is sometimes enough to examine carefully the proof that gives the equality cases and replace each step by its “almost” version. For example, it is an easy exercise to prove a stability version of the Cauchy-Schwarz inequality, which will say that if u and v are vectors in an inner-product space and the real part of the inner product ⟨u,v⟩ is at least (1−ϵ)‖u‖2‖v‖2, then the unit vectors u/‖u‖2 and v/‖v‖2 are close. (More precisely, their distance is at most √2ϵ, and this cannot be improved.) A “naive” argument of this kind can be used for the Loomis-Whitney inequality as well (based on the proof of the Loomis-Whitney inequality which uses Hölder’s inequality and induction on the dimension), but it does not give an optimal dependence on the closeness parameter ϵ. In general for stability results, having an optimal dependence is highly desirable, because it means that in a certain sense one has a complete structural characterization of the near-extremal cases. That is, the fact that near-equality holds implies structural information, and that structural information implies that near-equality holds, and if one applies both implications, one ends up back where one started without any appreciable loss of information.
The authors base their arguments on one of the well-known approaches to proving the Loomis-Whitney inequality: entropy methods. The main difficulty they face is that entropy methods yield probability distributions, whereas they need to end up with a set (in fact, a Cartesian product of 1-dimensional sets). Considerable care is needed to prove that in moving back from distributions to sets, they do not throw too much away. This requires them to introduce a new measure of distance, which they call hole weight.