Question
What is the asymptotic robustness-of-magic of a $W$ state over $n$ qubits. Is it $\Theta(n)$? $\Omega(\sqrt{n})$? $O\left(\frac{n}{\lg n} \right)$?
Background
$W$ states are entangled states where exactly one qubit is ON and every qubit has an equal chance of being ON if measured. For example, $W_3 = \frac{1}{\sqrt{3}} \left( |100\rangle + |010\rangle + |001\rangle \right)$.
In the paper "Application of a resource theory for magic states to fault-tolerant quantum computing", Howard and Campbell associate a quantum state $\rho$ with a cost $R(\rho)$ called "robustness of magic" and defined as:
$$R(\rho) = \min_x \sum_i |x_i|; \rho = \sum_i x_i \sigma_i $$
Where each $\sigma_i$ is a state that can be prepared by a stabilizer circuit (i.e. using only H, S, CNOT, and measurement gates). In other words, you try to find a weighted combination of stabilizer states that produce your desired state, and the cost you minimize while doing so is the sum of the weights' magnitudes. The minimum such cost is the robustness of magic of the state.
What I've Tried
The best-scoring decomposition I've found, for the $n$-qubit $W$ state, is:
$$s_{j,k} = X_j \cdot \text{CNOT}_{j\rightarrow k} \cdot H_j \cdot |0\rangle$$
$$S_{j,k} = s_{j,k} \cdot s_{j,k}^\dagger$$
$$W_n = \left(\sum_{j=0}^{n-1} \sum_{k=j+1}^{n-1} \frac{1}{n} S_{j,k} \right) + \left(\sum_{j=0}^{n-1} \frac{2-n}{n}|j\rangle \langle j| \right)$$
Which achieves a cost of $\frac{1}{n} \cdot \frac{n(n-1)}{2} + \frac{n-2}{n}\cdot n = \frac{3}{2}n-\frac{5}{2}$.
The best circuit construction I know for producing a large W state has a T-count that also scales like $\Theta(n)$. For example, here is an example construction that shows how to create a $W_n$ state using $2n-4$ T gates if $n$ is a power of 2:
Note that, if you want to compare the $2n-4$ T-count to the $\frac{3}{2}n - \frac{5}{2}$ potential-robustness-of-magic of the best-I-found decomposition, you must account for the fact that a $|T\rangle$ state's robustness-of-magic is $\sqrt{2}$ (not $1$).
Now, obviously, trying to find better and better decompositions is a reasonable way to upper-bound the robustness of magic... but this strategy will never create a lower-bound. What kinds of strategies do work for making lower bounds on this kind of problem?