For positive integers $n$ and $d$ satisfying $d = n-1$, let the $d$-dimensional regular simplex of side-length $\sqrt{2}$ be $X = \{(x_1, x_2, \cdots, x_n) \in \mathbb{R}^n: x_1+x_2+\cdots + x_n = 1, x_i \ge 0\}$. How many translates of the set $\frac12 X = \{\frac12 x: x \in X\}$ are necessary to cover $X$? Rotation is not allowed!

The volume bound yields a lower bound of $2^d = 2^{n-1}$. The best upper bound I can get is the following construction: It's obvious that $n$ translates of $(1-\frac{1}{n})X$ can cover $X$ (this follows from the fact that among any $n$ nonnegative real numbers with sum $1$, at least one of them must be $\ge \frac{1}{n}$). Iterating this, we get that $n^k$ translates of $(1-\frac{1}{n})^k X$ can cover $X$. Choosing $k = cn$ yields an upper bound of $n^{cn} \approx d^{cd}$ for some constant $c$.

The vast gulf between the lower bound and the upper bound invites the question: Is the true answer exponential in $n$? That is, does there exist $c$ such that $c^n$ translates always suffice to cover $X$?

Idea #1 for improving the lower bound: If we can find points $P_1, P_2, \cdots, P_r \in X$ with the property that $\| P_i - P_j \|_{L_1} > 1$ for $i \not= j$, then it's easy to show that no two points $P_i$ can be part of the same translate of $\frac12 X$, implying that the answer is at least $r$. How might we construct such points $P_i$? I tried a random maximal packing using translates of $\frac14 X - \frac14 X$, but this appears not to work. Perhaps a suitably chosen lattice? Or take a sparse subset of the $n!$ points $(p_1, p_2, \cdots, p_n)$ satisfying $\{p_1, p_2, \cdots, p_n\} = \{\frac12, \frac14, \frac18, \cdots, \frac{1}{2^{n-1}}, \frac{1}{2^{n-1}}\}$?

Idea #2 for improving the lower bound: If we can construct a weight function $\rho: X \rightarrow \mathbb{R}_{\ge 0}$, then a lower bound would be $$\frac{\int_X \rho}{\sup_v \int_{\frac12 X + v} \rho}.$$ (Inspired by the proof that one cannot cover a unit disk with a collection of strips the sum of whose widths is $< 2$.) But I don't think the simple weight function $\rho(x_1,x_2,\cdots,x_n) = x_1^2 + x_2^2 + \cdots + x_n^2$ will work, as it concentrates all the weight away from the center of $X$.


The following argument can probably be optimized, but it's the easiest I see at the moment. I think that you can cover $X$ by $8^n$ translates of $X/2$.

Fix $d$. Define by $\vec{v}$ the vector $(1, \ldots, 1)$, and by $\vec{v}^\perp$ the orthogonal subspace to $\vec{v}$ in $\mathbb{R}^d$.

Clearly the "filled simplex" $X' = \{(x_1, \ldots, x_n) \ : \ \sum x_i \leq 1, x_i \geq 0\}$ contains the cube $[0, 1/n]^n$. Therefore, $X'/2$ contains the cube $C = [0, \frac{1}{2n}]^n$, which implies that the projection of $C$ to $\vec{v}^\perp$ is contained in the projection of $X'/2$ to $\vec{v}^{\perp}$, which is a translate of $X/2$.

Finally, note that $X$ can be covered by translates of $C$ as follows: for each vector $\vec{m} = (m_1, \ldots, m_n)$ of nonnegative integers, take an associated translate $C + \frac{\vec{m}}{2n}$. These translates cover the positive octant in $\mathbb{R}^d$ and so clearly cover $X$. A translate $C + \frac{\vec{m}}{2n}$ has nonempty intersection with $X$ iff $n \leq \sum m_i \leq 2n$. The number of such translates needed to cover $X$ is thus bounded from above by the number of $\vec{m}$ summing to less than or equal to $2n$, which is ${3n \choose n}$ and so less than $2^{3n} = 8^n$.

But then after projecting to $\vec{v}^\perp$, the projections of the fewer than $8^n$ translates of $C$ cover a translate of $X$, and each projection of a translate of $C$ is contained in a translate of $X/2$ as argued above. So, $X$ is covered by $8^n$ translates of $X/2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.