Entropy and set projections

Let {A\subset {\mathbb Z}^3} be a finite set, and let {A_{xy}, A_{yz}, A_{xz} } be its projections to the corresponding two-planes. Denoting by {\# S} the cardinality of a set {S}, we have the following inequality:

\displaystyle  \left(\# A\right)^2 \leq \left(\# A_{xy}\right)\left(\# A_{yz}\right) \left(\# A_{xy}\right)

This generalizes to sets in higher dimensions and projections to subspaces of possibly different dimensions. As long as each coordinate appears at least {n} times on the right, the size of {\left(\# A\right)^n} is bounded by the product of the projections.

One proof of the above inequality is via a mixed version of Cauchy-Schwartz or Holder-type inequalities. For {f,g,h} functions of two variables, we have

\displaystyle  \begin{array}{rcl}  \left(\int \int \int f\left(x,y\right) g\left(y,z\right) h\left(x,z\right) dx\, dy\, dz\right)^2 \leq\\ \leq\left(\int \int f\left(x,y\right)dx\, dy\right) \cdot \left(\int \int g\left(y,z\right)dy\, dz\right) \left(\int \int h\left(x,z\right)dx \, dz\right) \end{array}

Taking {f,g,h} to be indicators of projections of {A} to the {2}-planes, the bound follows. However, proving the inequality for {f,g,h} requires some work.

There is a different inequality, involving entropy of random variables, whose proof (and generalizations) are much more conceptual. Namely, if {X,Y,Z} are random variables and {H\left(-\right)} denotes entropy, we have

\displaystyle  2H\left(X,Y,Z\right) \leq H\left(X,Y\right) + H\left(Y,Z\right) + H\left(X,Z\right)

Below the fold are the definitions, a proof, and an application. Continue reading

Advertisements