# number of characters needed to separate conjugacy classes

It is very well-known that, if $G$ is a finite group, then the (complex) characters of $G$ separate the conjugacy classes; that is, if $g, h \in G$ are not conjugate, then there exists a character $\chi$ such that $\chi(g) \ne \chi(h)$. However, I have been wondering about the minimal number of characters needed to separate all the classes.

Consider the (very basic) example $G=C_n$, a cyclic group of order $n$. Then it is possible to find a single character $\chi$ which is injective on $G$, so the answer is $1$ in this case.

Looking at a few character tables using GAP, it seems the answer is often 1.

Is there any literature on this? Any reason why this number could be much easier to determine than I think? Is it always 1 ? I may very well have overlooked something simple.

Note that the answer would be different if you only allowed irreducible characters (then for $C_2\times C_2$, it is 2); it's also different if you allow virtual characters, I guess.

Thanks!

Pierre

You always find a character which distinguishes between the distinct conjugacy classes. Let $\delta_k$ be the characteristic function of the $k$-th conjugacy class. Set $f=\delta_1+2\delta_2+3\delta_3+\dots$. Then clearly $f$ distinguishes the conjugacy classes. As a class function, $f$ is a complex linear combination of the irreducible characters. Write $f=a+ib$, where $a$ and $b$ are real linear combinations of irreducible characters. Then, for a suitable real number $\lambda$, $g=a+\lambda b$ also distinguishes the conjugacy classes. Now $g$ is a real linear combination of the irreducibles. Replacing the real coefficients by sufficiently good rational approximations, we still have the separating property. Now multiply by an integer to obtain a virtual character, and finally add a suitably large multiple of the regular character to obtain the required character.

Note added: The question actually doesn't have much to do with character theory, since the following far more general fact holds: If in a complex matrix there are no two equal columns, then there is a nonnegative integral linear combination of the rows such that the entries are pairwise distinct. This can for instance be proven by induction on the number of columns.

• Very nice! and it's actually quite easy. But you've saved me a lot of time. Thanks! – Pierre Apr 27 '17 at 13:52

Obviously Peter Müller's argument is perfectly fine. Here is a different way of doing it.

This algorithm yields a character that separates the conjugacy classes. It is terrible to compute with.

Index a set of representatives of the conjugacy classes $\{g_i\}$. Associate to every character $\chi$, the set of ordered pairs $$D(\chi) = \left\{ (g_i,g_j): g_i \neq g_j, { \mathrm {but } }\ \chi(g_i) = \chi(g_j)\right\}.$$

Now we show that if $D(\chi)$ is nonempty, there exists an irreducible character $\chi'$ and a positive integer $N$ (depending on $\chi$ and $\chi'$) such that $D(N\chi + \chi')$ is strictly contained in $D(\chi)$.

To see this, set $s$ to be the infimum of $|\chi(g_i) - \chi(g_j)|$ over all pairs of distinct representatives $(g_i,g_j)$ that are not in $D(\chi)$ (this is an infimum over a finite set of nonzero numbers). Pick $(g,h) \in D(\chi)$; there exists an irreducible $\chi'$ such that $\chi'(g) \neq \chi'(h)$. Select $N$ a positive integer so large that $Ns > 2\chi'(1)$, and set $\psi = N\chi + \chi'$, a character.

If $\chi(g) \neq \chi(g')$, then $\psi (g) -\psi(g') = \left( N(\chi(g) - \chi(g')\right) + (\chi' (g) - \chi(g'))$; the first parenthesized term has absolute value at least $Ns$, while the second one has absolute value at most $2 \chi'(1)$. Hence $D(\psi)$ is contained in $D(\chi)$. On the other hand, $(g,h)$ is not in $D(\psi)$, since $\psi(g) - \psi (h) = \chi'(g) - \chi'(h)$.

This process (begin with any nontrivial character, and continue) must terminate, resulting in a character $\rho$ with empty $D(\rho)$, which is exactly what we want.

Here is a contribution (answering a weaker question, and certainly not definitive, but it might suggest a direction for others to pursue). For the symmetric group, a single virtual character will do the job ( for a general finite group $G$, a single algebraic integer combination of characters of $G$ will do the job).

Let $G$ be a finite group and $\{x_{1},x_{2},\ldots, x_{k} \}$ be a full set of representatives for the distinct conjugacy classes of $G$. For $1 \leq i \leq k,$ let $\theta_{i} = \sum_{\chi \in {\rm Irr}(G)}\chi(x_{i}^{-1})\chi,$ which is an algebraic integer combination of characters of $G$. By the orthogonality relations, we have $\theta_{i}(x_{j}) = \delta_{ij}|C_{G}(x_{i})|.$

Let $\{p_{1},p_{2}, \ldots,p_{k} \}$ be a set of distinct primes, each greater than $|G|$. Let $\psi = \sum_{i=1}^{k} p_{i} \theta_{i},$ which is an integer-valued algebraic integer combination of irreducible characters of $G.$ Note that whenever $i \neq j,$ the integer $\psi(x_{i})$ is divisible by $p_{i},$ but $\psi(x_{j})$ is not. Hence $\psi$ takes $k$ distinct values.

In the case that $G$ is the symmetric group $S_{n},$ the irreducible characters of $G$ are all rational-valued, so that $\psi$ is a virtual character of $G.$