Demostrar que $|S|^2\le |S_x|\cdot |S_y|\cdot |S_z|$

Question

Sea $S$ sea un conjunto finito de puntos en un espacio tridimensional. Sea $S_x,S_y,S_z$ son los conjuntos formados por la proyección ortogonal de los puntos de $S$ en los planos yz,zx,xy,respectivamente. Demostrar que $$|S|^2\le |S_x|\cdot |S_y|\cdot |S_z|$$ donde $|A|$ denotan el número de elementos del conjunto finito $A$ (Nótese que la proyección ortogonal de un punto sobre un lugar es el pie de la perpendicular de ese punto al plano)

Answer 1

Reproduzco la prueba usando entropía debida a Jaikumar Radhakrishnan, que está disponible en sus apuntes "Entropía y conteo" en su página web: http://www.tcs.tifr.res.in/~jaikumar/

Elige un punto $(x,y,z)$ de $S$ uniformemente al azar.

Tenemos:

$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]$ .

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

Para reducir $B$ suma las tres últimas ecuaciones y utiliza: $H[y] \geq H[y|x]$ y $H[z|x],H[z|y] \geq H[z|x,y]$ .

Esto da: $B \geq 2A$ .

Tenga en cuenta que $A=\log_2 |S|$ y $H[x,y] \leq \log_2 |S_z|$ etc.

Answer 2

Mínimo de LHD es cuando esos puntos fila como rectángulo. Ponga $S_z=k,n=km-l,k> l\geq 0$

$S_x=n, S_y=m$

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

Si l=0, todos esos puntos fila en todos los puntos de red del rectángulo, LHD=RHD.