4
$\begingroup$

This is a version of this question of Klim Efremenko.

Let $r>2$ be a natural number, say $r=3$ or $r=10$. Let $G$ be a finite group and $\rho$ be an irreducible complex representation of $G$. We consider the following minimum $m=m(r,G,\rho)$: $$ m(r,G,\rho)= {\rm min\ rank} \sum_{i=1}^r c_i \rho(g_i), $$ where the $r$ elements $g_1, ... , g_r$ are arbitrary $r$ elements of $G$, and $c_1, ..., c_r$ are arbitrary complex numbers, not all of which are 0.

We want $m(r,G,\rho)$ to be small compared to ${\rm dim}\,\rho$. What can be said about $m(r,G,\rho)$ when the order $|G|$ tends to infinity? Say, for $r=10$, can one find $(G,\rho)$ such that $$ \frac{{\rm dim}\,\rho}{ m(10,G,\rho)} > \log^{200} |G|\ ? $$

For example, for $G=S_n$ and $G={\rm GL}(n,\mathbb{F}_q)$, the irreducible representations are classified. What can be said on $m(r,G,\rho)$ in these cases?

$\endgroup$
5
  • 1
    $\begingroup$ In which context does this question arise, i.e. is there a particular reason why you are interested in properties of sums or linear combinations of values of a representation? -- Unless you know a particular reason why this is not so, it seems conceivable that these matrices are additively more-or-less unrelated, and that your question is thus very hard, but not very interesting. $\endgroup$
    – Stefan Kohl
    Dec 29, 2014 at 17:02
  • 2
    $\begingroup$ I think this may be tricky for the natural irreducible representation of degree $n-1$ of the symmetric group $S_{n}$, though I can't give precise statements. $\endgroup$ Dec 29, 2014 at 18:59
  • 2
    $\begingroup$ @StefanKohl This question arises in the work of Klim Efremenko on locally decodable codes, see his paper ocf.berkeley.edu/~klimefre/papers/Induced.pdf $\endgroup$ Dec 30, 2014 at 11:57
  • $\begingroup$ @Andreas Thom : Can you prove it? I would like to see the proof. $\endgroup$ Dec 30, 2014 at 12:19
  • $\begingroup$ @Geoff Robinson: for the natural irreducible representation of degree $n−1$ of the symmetric group $S_n$ it is easy to see that: $m(2,G,\rho)=1$. To see it take $id-(1,2)$, where $(1,2)$ permutation of $1$ and $2$. The only problem with this example is that $\log|G|>dim \rho$. $\endgroup$ Dec 30, 2014 at 12:23

1 Answer 1

3
$\begingroup$

This answer shows that one cannot find $(G,\rho)$ as required if $G$ is supposed to be group of Lie type defined over a large field.

Let $G$ be a group of Lie type defined over a field with $q$ elements. Let $\rho$ be an irreducible representation of $G$ which is not $1$-dimensional. Gluck (D. Gluck. Sharper character value estimates for groups of Lie type, J. Algebra 174 (1995), 229-266.) proved that there exists a constant (independent of $G$ and $\rho$) so that

$$|{\rm tr}(\rho(g))| \leq C \cdot \dim(\rho) \cdot q^{-1/2},$$ whenever $g$ is non-trival.

Let's assume that $\rho$ is unitary and denote by $\|.\|$ the spectral norm. Now, let $f \in {\mathbb C}[G]$, $f= \sum_{i=1}^r c_i g_i$ with $g_i \neq g_j$ for $i \neq j$. We get

$${\rm tr}(\rho(f)^*\rho(f)) \leq {\rm rank}(\rho(f)) \cdot \|\rho(f)\|^2,$$ and \begin{eqnarray*} {\rm tr}(\rho(f)^*\rho(f)) &=& \sum_{i,j=1}^r c_i \bar{c_j} \cdot {\rm tr}(\rho(g_ig_j^{-1}))\\ &\geq & \dim(\rho) \cdot \sum_{i=1}^r |c_i|^2 - C \cdot \dim(\rho) \cdot q^{-1/2} \cdot \sum_{i \neq j} |c_i \bar{c_j}| \\ &\geq & \dim(\rho) \cdot \left(1/r - C \cdot q^{-1/2} \right) \cdot \left(\sum_{i=1}^r |c_i| \right)^2 \\ &\geq & \dim(\rho) \cdot \left(1/r - C \cdot q^{-1/2} \right) \cdot \|\rho(f)\|^2, \end{eqnarray*} where I used Gluck's result and the basic estimate $$\sum_{i=1}^r |c_i| \leq r^{1/2} \cdot \left(\sum_{i=1}^r |c_i|^2 \right)^{1/2}.$$

Combining the two bounds for ${\rm tr}(\rho(f)^*\rho(f))$ we get $$\dim(\rho) \cdot \left(1/r - C \cdot q^{-1/2} \right) \cdot \|\rho(f)\|^2 \leq {\rm rank}(\rho(f)) \cdot \|\rho(f)\|^2.$$ and hence $$\frac{\dim(\rho)}{{\rm rank}(\rho(f))} \leq \frac1{1/r - C \cdot q^{-1/2}} \leq r + 2 C \cdot r^2 \cdot q^{-1/2},$$ for $q$ large.

There are similar character estimates for the symmetric group, comparing an arbitrary character with the character that counts fixed points of the permutation. These estimates probably show that the symmetric groups cannot work either (at least not in a way that is essentially better than for the standard representation).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.