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



How many regular d-dimensional simplices of side length 1/2 are required to cover a regular d-dimensional simplex of side length 1?
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$.


UPDATE: I claim that $X$ can in fact be covered by $\binom{2d}{d}$ translates of $X/2$. To see this, I want to use an affine transformation to consider $Y = \{(x\_1, \ldots, x\_d) \ : \ x\_i \geq 0, \sum x\_i \leq 2d\}$ instead; clearly the answers for $X$ and $Y$ are the same.


Now, we simply note that any $\vec{y} \in Y$ can be written as $\vec{v} + \vec{w}$, where $\vec{v} \in (\mathbb{N}\_0)^d$ is the coordinatewise floor of $\vec{y}$. If the sum of $\vec{v}$ is less than or equal to $d$, we leave it alone. If it's greater than $d$, then we redefine $\vec{v}$ to be any coordinatewise smaller vector with entries in $\mathbb{N}\_0$ and sum exactly $d$ (and define $\vec{w} = \vec{y} - \vec{v}$).


In either case, $\vec{w}$ has nonnegative entries and sum at most $d$; in the former case this is because all entries are in $[0,1)$, and in the latter case since its sum is exactly the sum of $\vec{y}$ minus $d$. Therefore, $\vec{w} \in Y/2$.


The set of possible $\vec{v}$ is exactly the set $S = \{(n\_1, \ldots, n\_d) \ : \ n\_i \in \mathbb{N}\_0, \sum n\_i \leq d\}$. $S$ is in bijective correspondence with the set of $d$-element subsets of $\{1, \ldots, 2d\}$; for any such
subset $T$ with elements $t\_1 < t\_2 < \ldots t\_d$, define
$\phi(T) = (n\_1, \ldots, n\_d)$ by $n\_1 = t\_1 - 1$ and $n\_i = t\_i - t\_{i-1} - 1$ for $i > 1$. Therefore, $|S| = \binom{2d}{d}$.


We've shown that $Y \subset S + (Y/2)$, so $Y$ is covered by $\binom{2d}{d}$ translates of $Y/2$.


