0
$\begingroup$

Let $t \in (0, 1)$ and define $P_t(k)$ to be cardinality of the largest set of $t$-separated points (i.e., for any distinct pair of points, the Euclidean distance is strictly larger than $t > 0$) of the set $$ S(k) = \{x \in \mathbb{R}^d : \|x\|_2 \leq 1, \|x\|_0 \leq k\}. $$ Above $\|x\|_0$ is the number of nonzero entries.

It is possible to show that for some constant $C > 0$, we have $$ \log P_t(k) \leq C \, k \log \Big(\frac{e d}{k t}\Big), $$ for every $t \in (0, 1)$ and every positive integer $k \leq d$.

Can this inequality be reversed? Is it true that for some $c > 0$ we have $$ \log P_t(k) \geq c\, k \log \Big(\frac{e d}{k t}\Big), $$ for all $t \in (0, 1)$ and every positive integer $k \leq d$?

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .