[proofplan]
We build many well-separated points in the unit ball of the $k$-sparse vectors by choosing many supports of size $k$ with small pairwise intersections. The lower embedding inequality makes their images in $\mathbb{R}^n$ separated, while the upper inequality keeps all images inside one Euclidean ball. Comparing the volumes of disjoint small balls contained in a larger ball gives an exponential upper bound on the size of the separated set in terms of $n$. The combinatorial lower bound on the number of sparse points then forces $n\gtrsim k\log(d/k)$.
[/proofplan]
[step:Construct exponentially many sparse unit vectors with fixed separation]
We first construct a finite set $M\subset T$ satisfying
\begin{align*}
|M|\geq \exp(\gamma k\log(d/k))
\end{align*}
and
\begin{align*}
|x-z|\geq 1
\end{align*}
for all distinct $x,z\in M$, where $\gamma>0$ is a universal constant.
Let $N:=\lfloor d/k\rfloor$. Since $1\leq k\leq d/2$, we have $N\geq2$. Choose pairwise disjoint subsets
\begin{align*}
P_1,\dots,P_k\subset\{1,\dots,d\}
\end{align*}
such that $|P_j|=N$ for each $j\in\{1,\dots,k\}$. Let $\mathcal{S}$ denote the family of all subsets $S\subset\bigcup_{j=1}^k P_j$ satisfying $|S\cap P_j|=1$ for every $j\in\{1,\dots,k\}$. Thus every $S\in\mathcal{S}$ has cardinality $k$, and
\begin{align*}
|\mathcal{S}|=N^k.
\end{align*}
Let $\rho:\mathcal{S}\times\mathcal{S}\to\{0,1,\dots,k\}$ denote the block Hamming distance
\begin{align*}
\rho(S,R):=|\{j\in\{1,\dots,k\}: S\cap P_j\neq R\cap P_j\}|.
\end{align*}
We choose a maximal subfamily $\mathcal{F}\subset\mathcal{S}$ with $\rho(S,R)>k/2$ whenever $S,R\in\mathcal{F}$ are distinct. Maximality means that the closed $\rho$-balls of radius $\lfloor k/2\rfloor$ centred at elements of $\mathcal{F}$ cover $\mathcal{S}$. For a fixed $S\in\mathcal{S}$, the number of $R\in\mathcal{S}$ with $\rho(S,R)\leq k/2$ is at most
\begin{align*}
\sum_{\ell=0}^{\lfloor k/2\rfloor}\binom{k}{\ell}(N-1)^\ell
\leq
2^k N^{k/2}.
\end{align*}
The last inequality uses $\binom{k}{\ell}\leq 2^k$ after summing over all choices of the changed blocks, and $(N-1)^\ell\leq N^{k/2}$ for $0\leq\ell\leq k/2$. Therefore
\begin{align*}
|\mathcal{F}|
\geq
\frac{N^k}{2^kN^{k/2}}
=
\left(\frac{N}{4}\right)^{k/2}.
\end{align*}
If $N\geq8$, then $N\geq d/(2k)$ gives
\begin{align*}
|\mathcal{F}|
\geq
\left(\frac{d}{8k}\right)^{k/2}.
\end{align*}
For each $S\in\mathcal{F}$, define the vector $u_S\in\mathbb{R}^d$ by
\begin{align*}
(u_S)_i=
\begin{cases}
k^{-1/2}, & i\in S,\cr
0, & i\notin S.
\end{cases}
\end{align*}
Then $u_S\in\Sigma_k$ and
\begin{align*}
|u_S|^2=\sum_{i\in S}k^{-1}\,=1,
\end{align*}
so $u_S\in T$. Define
\begin{align*}
M:=\{u_S:S\in\mathcal{F}\}\subset T.
\end{align*}
For distinct $S,R\in\mathcal{F}$, the condition $\rho(S,R)>k/2$ implies
\begin{align*}
|S\cap R|<k/2.
\end{align*}
Therefore
\begin{align*}
|u_S-u_R|^2
=
\frac{|S\triangle R|}{k}
=
\frac{2k-2|S\cap R|}{k}
\geq 1.
\end{align*}
Since $d/k\geq8$ in this case, the preceding lower bound for $|\mathcal{F}|=|M|$ implies $|M|\geq\exp(\gamma_1 k\log(d/k))$ for a universal constant $\gamma_1>0$.
It remains to handle $2\leq N<8$. Choose a fixed subset $Q\subset\{1,\dots,d\}$ with $|Q|=k$. Let $h:(\{-1,1\}^Q)\times(\{-1,1\}^Q)\to\{0,1,\dots,k\}$ denote the Hamming distance
\begin{align*}
h(\varepsilon,\delta):=|\{i\in Q:\varepsilon_i\neq\delta_i\}|.
\end{align*}
Choose a maximal subset $\mathcal{E}\subset\{-1,1\}^Q$ such that $h(\varepsilon,\delta)>k/4$ whenever $\varepsilon,\delta\in\mathcal{E}$ are distinct. Maximality implies that the closed Hamming balls of radius $\lfloor k/4\rfloor$ centred at elements of $\mathcal{E}$ cover $\{-1,1\}^Q$. For a fixed sign vector, such a ball has cardinality at most
\begin{align*}
\sum_{\ell=0}^{\lfloor k/4\rfloor}\binom{k}{\ell}
\leq
\exp(k H_0(1/4)),
\end{align*}
where $H_0(t):=-t\log t-(1-t)\log(1-t)$ is the binary entropy function with natural logarithms. Hence
\begin{align*}
|\mathcal{E}|
\geq
\exp(k(\log 2-H_0(1/4))).
\end{align*}
After decreasing the constant to cover the finitely many small values of $k$, there is a universal constant $\gamma_2>0$ such that $|\mathcal{E}|\geq\exp(\gamma_2 k)$. Since $2\leq d/k<8$, $\log(d/k)$ is bounded above and below by positive universal constants, so $|\mathcal{E}|\geq\exp(\gamma_3 k\log(d/k))$ for a universal constant $\gamma_3>0$.
For each $\varepsilon\in\mathcal{E}$, define $v_\varepsilon\in\mathbb{R}^d$ by
\begin{align*}
(v_\varepsilon)_i=
\begin{cases}
k^{-1/2}\varepsilon_i, & i\in Q,\cr
0, & i\notin Q.
\end{cases}
\end{align*}
Then $v_\varepsilon\in\Sigma_k$, $|v_\varepsilon|=1$, and therefore $v_\varepsilon\in T$. Define $M:=\{v_\varepsilon:\varepsilon\in\mathcal{E}\}$. If $\varepsilon\neq\delta$, then
\begin{align*}
|v_\varepsilon-v_\delta|^2
=
\frac{4h(\varepsilon,\delta)}{k}
\geq 1.
\end{align*}
Combining the cases $N\geq8$ and $2\leq N<8$, there is a universal constant $\gamma>0$ such that
\begin{align*}
|M|\geq \exp(\gamma k\log(d/k))
\end{align*}
and $|x-z|\geq1$ for all distinct $x,z\in M$.
[guided]
The goal is to produce many points in $T$ that cannot be too close to each other. We use only supports, not signs. The delicate point is that a crude greedy argument over all $k$-subsets loses too much when $d/k$ is bounded, so we build the supports with a block structure.
Let $N:=\lfloor d/k\rfloor$. Since $k\leq d/2$, there are at least two available coordinates per block. Choose pairwise disjoint blocks
\begin{align*}
P_1,\dots,P_k\subset\{1,\dots,d\}
\end{align*}
with $|P_j|=N$ for every $j\in\{1,\dots,k\}$. Let $\mathcal{S}$ be the set of supports that choose exactly one coordinate from each block:
\begin{align*}
\mathcal{S}:=\{S\subset\bigcup_{j=1}^k P_j: |S\cap P_j|=1 \text{ for every } j\in\{1,\dots,k\}\}.
\end{align*}
Every element of $\mathcal{S}$ has cardinality $k$, and there are $N$ independent choices in each of the $k$ blocks, so
\begin{align*}
|\mathcal{S}|=N^k.
\end{align*}
Define the block Hamming distance $\rho:\mathcal{S}\times\mathcal{S}\to\{0,1,\dots,k\}$ by
\begin{align*}
\rho(S,R):=|\{j\in\{1,\dots,k\}:S\cap P_j\neq R\cap P_j\}|.
\end{align*}
We choose $\mathcal{F}\subset\mathcal{S}$ maximal under the requirement that distinct elements have $\rho$-distance greater than $k/2$. Because of maximality, every $R\in\mathcal{S}$ lies within $\rho$-distance at most $k/2$ of some chosen $S\in\mathcal{F}$; otherwise we could add $R$ to $\mathcal{F}$.
For a fixed $S\in\mathcal{S}$, count the supports $R\in\mathcal{S}$ with $\rho(S,R)\leq k/2$. If exactly $\ell$ blocks are changed, there are $\binom{k}{\ell}$ choices of those blocks and at most $(N-1)^\ell$ choices for the new coordinates. Hence the ball of radius $\lfloor k/2\rfloor$ has cardinality at most
\begin{align*}
\sum_{\ell=0}^{\lfloor k/2\rfloor}\binom{k}{\ell}(N-1)^\ell
\leq
2^kN^{k/2}.
\end{align*}
Since these balls cover $\mathcal{S}$, division gives
\begin{align*}
|\mathcal{F}|\geq \frac{N^k}{2^kN^{k/2}}=\left(\frac{N}{4}\right)^{k/2}.
\end{align*}
For $N\geq8$, this is at least $(d/(8k))^{k/2}$ because $N=\lfloor d/k\rfloor\geq d/(2k)$. Now define, for each $S\in\mathcal{F}$, the normalized indicator vector $u_S\in\mathbb{R}^d$ by
\begin{align*}
(u_S)_i=
\begin{cases}
k^{-1/2}, & i\in S,\cr
0, & i\notin S.
\end{cases}
\end{align*}
This vector is $k$-sparse and has norm one:
\begin{align*}
|u_S|^2=\sum_{i\in S}k^{-1}=1.
\end{align*}
Hence $u_S\in T$. Let
\begin{align*}
M:=\{u_S:S\in\mathcal{F}\}.
\end{align*}
If $S,R\in\mathcal{F}$ are distinct, then $\rho(S,R)>k/2$. In each block where the choices differ, one coordinate belongs to $S\setminus R$ and one coordinate belongs to $R\setminus S$, so $|S\cap R|=k-\rho(S,R)<k/2$. Therefore
\begin{align*}
|u_S-u_R|^2
=
\frac{|S\triangle R|}{k}
=
\frac{2k-2|S\cap R|}{k}
\geq 1.
\end{align*}
Since $d/k\geq8$ in this case, this gives $|M|\geq\exp(\gamma_1 k\log(d/k))$ for a universal constant $\gamma_1>0$.
For the remaining bounded ratios $2\leq N<8$, supports alone with separation greater than $k/2$ are not the right tool: a binary code of relative distance greater than $1/2$ has no positive exponential rate. Instead we keep one support fixed and use signs. Choose a fixed set $Q\subset\{1,\dots,d\}$ with $|Q|=k$. Define the Hamming distance $h:(\{-1,1\}^Q)\times(\{-1,1\}^Q)\to\{0,1,\dots,k\}$ by
\begin{align*}
h(\varepsilon,\delta):=|\{i\in Q:\varepsilon_i\neq\delta_i\}|.
\end{align*}
Choose $\mathcal{E}\subset\{-1,1\}^Q$ maximal under the condition that distinct sign vectors have Hamming distance greater than $k/4$. Maximality means that the Hamming balls of radius $\lfloor k/4\rfloor$ centred at $\mathcal{E}$ cover the whole sign cube. A ball of this radius has cardinality at most
\begin{align*}
\sum_{\ell=0}^{\lfloor k/4\rfloor}\binom{k}{\ell}
\leq
\exp(kH_0(1/4)),
\end{align*}
where $H_0(t):=-t\log t-(1-t)\log(1-t)$ is the binary entropy function with natural logarithms. Since $H_0(1/4)<\log 2$, division by the largest possible ball gives
\begin{align*}
|\mathcal{E}|
\geq
\exp(k(\log 2-H_0(1/4))).
\end{align*}
After decreasing the constant to handle the finitely many small values of $k$, this is at least $\exp(\gamma_2 k)$ for a universal constant $\gamma_2>0$. Because $2\leq d/k<8$, the quantities $k$ and $k\log(d/k)$ are comparable by universal constants, so $|\mathcal{E}|\geq\exp(\gamma_3 k\log(d/k))$ for a universal constant $\gamma_3>0$.
For each $\varepsilon\in\mathcal{E}$, define $v_\varepsilon\in\mathbb{R}^d$ by
\begin{align*}
(v_\varepsilon)_i=
\begin{cases}
k^{-1/2}\varepsilon_i, & i\in Q,\cr
0, & i\notin Q.
\end{cases}
\end{align*}
Then $v_\varepsilon$ is supported on $Q$, so it is $k$-sparse, and
\begin{align*}
|v_\varepsilon|^2=\sum_{i\in Q}k^{-1}=1.
\end{align*}
Thus $v_\varepsilon\in T$. Let $M:=\{v_\varepsilon:\varepsilon\in\mathcal{E}\}$. If $\varepsilon\neq\delta$, the vector $v_\varepsilon-v_\delta$ has magnitude $2k^{-1/2}$ exactly on the $h(\varepsilon,\delta)$ coordinates where the signs differ. Hence
\begin{align*}
|v_\varepsilon-v_\delta|^2
=
\frac{4h(\varepsilon,\delta)}{k}
\geq 1.
\end{align*}
Combining the two cases, there is a universal constant $\gamma>0$ such that $M\subset T$, $|M|\geq\exp(\gamma k\log(d/k))$, and $|x-z|\geq1$ for distinct $x,z\in M$.
[/guided]
[/step]
[step:Use the embedding inequalities to separate the image points]
For distinct $x,z\in M$, the lower distortion inequality gives
\begin{align*}
|Ax-Az|=|A(x-z)|\geq a|x-z|\geq a.
\end{align*}
Thus the open Euclidean balls
\begin{align*}
B(Ax,a/2):=\{y\in\mathbb{R}^n:|y-Ax|<a/2\},\qquad x\in M,
\end{align*}
are pairwise disjoint.
Also, since $0\in T$ and $x\in T$, the upper distortion inequality applied to the pair $(x,0)$ gives
\begin{align*}
|Ax|=|A(x-0)|\leq b|x|\leq b.
\end{align*}
Hence every ball $B(Ax,a/2)$ is contained in $B(0,b+a/2)$.
[/step]
[step:Compare Euclidean volumes in the image space]
Let $\mathcal{L}^n$ denote $n$-dimensional [Lebesgue measure](/page/Lebesgue%20Measure) on $\mathbb{R}^n$. For $y\in\mathbb{R}^n$ and $r>0$, define the open Euclidean ball
\begin{align*}
B(y,r):=\{w\in\mathbb{R}^n:|w-y|<r\}.
\end{align*}
Let $\omega_n:=\mathcal{L}^n(B(0,1))$ denote the $n$-dimensional Lebesgue measure of the Euclidean unit ball in $\mathbb{R}^n$. Since the balls $B(Ax,a/2)$ are pairwise disjoint and contained in $B(0,b+a/2)$, finite additivity and monotonicity of Lebesgue measure give
\begin{align*}
|M|\,\omega_n(a/2)^n
=
\sum_{x\in M}\mathcal{L}^n(B(Ax,a/2))
\leq
\mathcal{L}^n(B(0,b+a/2))
=
\omega_n(b+a/2)^n.
\end{align*}
Cancelling $\omega_n>0$ yields
\begin{align*}
|M|\leq \left(\frac{b+a/2}{a/2}\right)^n
=
\left(1+2\frac{b}{a}\right)^n
\leq
(1+2C)^n.
\end{align*}
[/step]
[step:Rearrange the packing estimate to obtain the lower bound on $n$]
Combining the lower bound for $|M|$ with the volume upper bound gives
\begin{align*}
\exp(\gamma k\log(d/k))
\leq
|M|
\leq
(1+2C)^n.
\end{align*}
Taking logarithms,
\begin{align*}
\gamma k\log(d/k)\leq n\log(1+2C).
\end{align*}
Define
\begin{align*}
c(C):=\frac{\gamma}{\log(1+2C)}>0.
\end{align*}
Then
\begin{align*}
n\geq c(C)\,k\log(d/k).
\end{align*}
This is the desired lower bound.
[/step]
