# How many regular d-dimensional simplices of side length 1/2 are required to cover a regular d-dimensional simplex of side length 1?

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