Let be a finite set, and let be its projections to the corresponding two-planes. Denoting by the cardinality of a set , we have the following inequality:
This generalizes to sets in higher dimensions and projections to subspaces of possibly different dimensions. As long as each coordinate appears at least times on the right, the size of 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 functions of two variables, we have
Taking to be indicators of projections of to the -planes, the bound follows. However, proving the inequality for requires some work.
There is a different inequality, involving entropy of random variables, whose proof (and generalizations) are much more conceptual. Namely, if are random variables and denotes entropy, we have
Below the fold are the definitions, a proof, and an application. Continue reading