7
$\begingroup$

The Loomis-Whitney inequality implies that if $A\subset\mathbb Z^n$ is a finite, non-empty set of size $K:=|A|$, then, denoting by $K_1,\dotsc,K_n$ the sizes of the projections of $A$ onto the coordinate hyperplanes, we have $$ K_1\dotsb K_n\ge K^{n-1}. \tag{$\ast$} $$

This a necessary, but in general not sufficient condition; say, it holds true for $n=3$, $K=5$, and $K_1=K_2=K_3=3$, but there seems to not exist a configuration of five points in $\mathbb Z^3$ with three-point projections onto each of the coordinate hyperplanes.

Are there any known conditions, independent from ($\ast$), that integers $K,K_1,\dotsc,K_n\ge 1$ with $K\ge\max\{K_1,\dotsc,K_n\}$ must satisfy, given that $K$ is the size of a finite set in $\mathbb Z^n$, and $K_i$ are the sizes of its projections onto the coordinate hyperplanes?

$\endgroup$
4
  • $\begingroup$ Is this this corollary of BT theorem really stronger than LW inequality? It looks absolutely equivalent. $\endgroup$ Commented Jan 17, 2016 at 16:59
  • $\begingroup$ @Fedor Petrov: how would you derive BT from LW? $\endgroup$
    – Seva
    Commented Jan 17, 2016 at 17:01
  • $\begingroup$ Define $q_i:=K/K_i$. Then by LW we have $\prod q_i\leqslant K$. Then there exist $l_i\geqslant q_i$ such that $\prod l_i=K$, for example $l_i:=q_i$ for $i<n$, $l_n:=K/(q_1\dots q_{n-1})$. $\endgroup$ Commented Jan 17, 2016 at 17:37
  • $\begingroup$ @Fedor Petrov: you are right; I was sure that BT is strictly stronger than LW and have not checked carefully. I "simplified" my question following your remark. $\endgroup$
    – Seva
    Commented Jan 17, 2016 at 17:58

2 Answers 2

4
$\begingroup$

I think there are some extra conditions, especially for $n\geq 4$. For example, when $n=4$ we have

$$ K^5 \leq K_1^3K_2^3K_3K_4, $$ which is clearly independent to the Loomis-Whitney $K^3\leq K_1K_2K_3K_4$.

These can be proved using non-Shannon entropy inequalities (since the Loomis-Whitney inequality can be proved using entropy and the Shannon inequalities this is not too surprising).

For example, the above inequality comes from the Zhang-Yeung inequality, which gives the following relationship between the entropy of any 4 discrete random variables:

$$ 2H(U)+2H(V)+H(Y)+H(X,Y)+H(U,V,X)+4H(U,V,Y) \leq H(X,U)+H(X,V)+3H(U,V)+3H(V,Y)+3H(U,Y), $$

which, in view of $H(U,V)\leq H(U)+H(V)$, implies

$$ H(Y)+H(X,Y)+H(U,V,X)+4H(U,V,Y) \leq H(X,U)+H(X,V)+H(U,V)+3H(V,Y)+3H(U,Y). $$

Let $A\subset \mathbb{Z}^4$ be a finite set of points, and choose a point uniformly at random from $A$. For the four random variables select a pair of coordinates as follows: $U$ is $(1,3)$, $V$ is $(2,4)$, $Y$ is $(3,4)$ and $X$ is $(1,2)$. Just writing the number for the induced random variable on the appropriate coordinate, the above inequality gives

$$ H(3,4)+5H(1,2,3,4) \leq H(1,2,3)+H(1,2,4)+3H(2,3,4)+3H(1,3,4).$$

Using the fact that entropy is non-negative and that entropy of a random variable taking at most $N$ values is at most $\log N$ gives the result.

I haven't tried, but presumably one could play similar games with other $n\geq 4$ using generalisations and extensions of the Zhang-Yeung inequality. It would be interesting to know whether there are other relations available for $n=3$, since we know that there are no non-Shannon entropy inequalities for at most three random variables.

$\endgroup$
2
$\begingroup$

Dust off this question (thanks to Thomas Bloom), it was in fact intended to check whether the inequality $$ nK \le K_1 + \dotsb + K_n + \frac12\,K\log_2 K $$ is known (see this paper, particularly the Concluding Remarks section, for the context and the proof).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .