Let $ G $ be a finite group. Let $ (\pi,V) $ be a faithful representation of $ G $. Then every irrep of $ G $ is contained in some tensor power of $ V $. See
https://mathoverflow.net/questions/18194/faithful-representations-and-tensor-powers
In particular this answer
https://mathoverflow.net/a/192103/387190
shows that every irrep shows up in some tensor power less than or equal to the size of $ G $.
I am interested in a tighter bound. In particular, replacing the size of $ G $ by just the number of conjugacy classes of $ G $.
That is:
Let $ G $ be a finite group with $ k $ conjugacy classes. Let $ (\pi,V) $ be a faithful representation of $ G $. Does every irrep of $ G $ appear as a subrepresentation of
$$
\bigoplus_{j=1}^k V^{\otimes j}
$$
In other words, does every irrep of $ G $ appear in some small tensor power $ V^{\otimes j} $ for $ j \leq k $.
Best Answer
Yes, in fact we can write down an even better bound than this. If $\chi$ is a faithful character and $\psi$ is an irreducible character, then for $n \ge 1$ the sequence $\langle \chi^n, \psi \rangle$ satisfies a linear recurrence relation of order the number $d$ of distinct nonzero values that the character $\chi$ takes (which satisfies $d \le c(G)$, the number of conjugacy classes, but can be strictly less than it). (We need to take $n \ge 1$ so we can ignore the zero values.) Hence if it is zero for $n = 1, \dots d$ then it vanishes identically (since we can compute the rest of the terms using the linear recurrence). So any of the other arguments which show that this sequence is not identically zero in fact show that $\langle \chi^n, \psi \rangle \neq 0$ for some $\boxed{ 1 \le n \le d }$.
This argument can be extended slightly to give a proof, which is also given in the linked MO thread. We just consider the generating function
$$\sum_{n \ge 0} \langle \chi^n, \psi \rangle t^n = \sum_{n \ge 0} \frac{1}{|G|} \sum_{g \in G} \chi^n(g^{-1}) \psi(g) t^n = \frac{1}{|G|} \sum_{g \in G} \frac{\psi(g)}{1 - \chi(g^{-1}) t}.$$
Because $\chi$ is faithful, $g = e$ is the only element satisfying $\chi(g) = \chi(e)$, so the corresponding term $\frac{\psi(e)}{1 - \chi(e) t}$ is not canceled out by any other term in the above sum (it is the dominant singularity of the generating function), so the above generating function is nonzero and hence has some nonzero coefficient. Alternatively we can use a Vandermonde matrix, which is also alluded to in the linked MO thread.
As a simple application of this stronger bound, if we take $\chi$ to be the character of the regular representation then $d = 1$ which gives that every irreducible appears in the regular representation. Of course we knew this already but it's nice to see that this result is strong enough to give it.
As a more interesting application, let $V$ be the $n$-dimensional permutation representation of $S_n$. The character of this representation is the number of fixed points of a permutation, which takes exactly $d = n-1$ distinct nonzero values, namely $1, 2, \dots n-2, n$ (so excluding $n-1$). We conclude that every irreducible of $S_n$ appears in $V^{\otimes k}$ for some $1 \le k \le n - 1$, which is much better than either the bound $|S_n| = n!$ or the bound $|c(S_n)| = p(n)$. We ought to have a similar bound for induced representations but I don't know what that bound should be exactly.