2
$\begingroup$

Let $G$ be a finite group, and let $Q$ be a probability measure on $G$. Suppose that $Q$, as a function on $G$, is supported on a conjugacy class $C$. We denote by $Q^{*k}$ the $k$-fold convolution of $Q$ with itself - again a class function. We denote by $U$ the uniform probability measure on $G$.

Let $H$ be a finite set, and suppose we have a class function $F:G\to H$. I am interested in upper-bounding the sum $$\sum_{x \in H} |P_{Q^{*k}}(F(g)=x) - P_{U}(F(g)=x)|,$$ where $g$ is a random element from $G$ chosen w.r.t. $Q^{*k}$ or $U$.

  1. Is there a general method for bounding such sums?
  2. Are there examples in the literature where special cases of this problem has been studied?

I have seen two extreme cases of this problem that have been studied before, but although in both cases one can adapt the methods in order to upper-bound the sum above, I feel that such a naive adaptation is not satisfactory. I describe these cases now.

One approach becomes optimal when $F$ is close to being injective. Indeed, by the triangle inequality, $$\sum_{x \in H} |P_{Q^{*k}}(F(g)=x) - P_{U}(F(g)=x)|\le ||Q^{*k} - U||_{1},$$ and Diaconis and Shahshani, in their 'the upper bound lemma', have proven that $$\|Q^{*k} - U\|_{1} \le \sqrt{|G|} \|Q^{*k}-U\|_{2} \le \Big( \sum_{\rho \text{ non trivial}} \mathrm{dim}(\rho)^2 |\frac{\chi_{\rho}(c)}{\chi_{\rho}(1) }|^{2k} \Big)^{1/2}.$$ Here $\rho$ is an irreducible representation of $G$, $\chi_{\rho}$ its character, and $c$ an arbitrary element in $C$.

A second approach becomes optimal when $F$ is far from being injective. Given a class function $f:G\to \mathbb{C}$, one can bound a sum of the form $|E_{Q^{*k}} f(g) - E_{U} f(g)|$ by $$|E_{Q^{*k}} f(g) - E_{U} f(g)| \le \sum_{\rho \text{ non trivial}} |\hat{f_\rho}| \mathrm{dim}(\rho) |\frac{\chi_{\rho}(c)}{\chi_{\rho}(1)}|^k.$$ Applying this with $f(g) = 1_{F(g)=x}$ (for any $x \in H$), we get a bound on each summand of our original sum.

  1. Is there a third approach, which uses some kind of trade-off between the two? Can it help if $H$ is abelian (but $F$ is not a group homom')?.
$\endgroup$
2
  • 1
    $\begingroup$ If $F$ is not constant on conjugacy classes, then why should $1_{F(g)=x}$ be a class function? $\endgroup$ Feb 20, 2018 at 22:26
  • $\begingroup$ @BenjaminSteinberg You are of course correct, I forgot to mention that $F$ is a class function (although not a complex-valued one...). I have edited the question accordingly. $\endgroup$ Feb 20, 2018 at 22:29

0

Your Answer

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