Prove that $|S|^2\le |S_x|\cdot |S_y|\cdot |S_z|$

Question

Let $S$ be a finite set of points in three- dimensional space. Let $S_x,S_y,S_z$ be the sets consisting of the orthogonal projection of the points of $S$ onto the yz-plane,zx-plane,xy-plane,respectively. Prove that $$|S|^2\le |S_x|\cdot |S_y|\cdot |S_z|$$, where $|A|$ denote the number of elements in the finite set $A$.(Note that the orthogonal projection of a point onto a place is the foot of perpendicular from that point to the plane)

Answer 1

I reproduce the proof using entropy due to Jaikumar Radhakrishnan, which is available in his notes "Entropy and Counting" at his website: http://www.tcs.tifr.res.in/~jaikumar/

Pick a point $(x,y,z)$ from $S$ uniformly at random.

We have:

$H[x,y,z] = H[x]+H[y|x]+H[z|x,y]$.

$H[x,y] = H[x]+H[y|x]$.

$H[y,z] = H[y]+H[z|y]$.

$H[z,x] = H[x]+H[z|x]$.

Let $A=H[x,y,z]$ and $B=H[x,y]+H[y,z]+H[z,x]$.

To lower-bound $B$, add the last three equations and use: $H[y] \geq H[y|x]$ and $H[z|x],H[z|y] \geq H[z|x,y]$.

This gives: $B \geq 2A$.

Now note that $A=\log_2 |S|$ and $H[x,y] \leq \log_2 |S_z|$ etc.

Answer 2

Minimum of LHD is when those points row like rectangle. Put $S_z=k,n=km-l,k> l\geq 0$

$S_x=n, S_y=m$

then $$S_xS_yS_z=nmk\geq n(n+l)\geq n^2$$

If l=0, all those points row at all lattice points of rectangle, LHD=RHD.