1
$\begingroup$

Terry Tao gives this oblique definition of quasirandom group in his notes 3

$G$ is quasi-random (of order $D$) if all non-trivial unitary representations $\rho: G \to U(H)$ have dimension at least $D$.

There is nothing random about this representation, and the size of these irreducible representations doesn't make it more random.

There is someting kind of mixing about it, I guess:

Let $G$ be a finite $D$ quasi-random group and $f,g \in \ell^2(G)$ such that $\mathbb{E}[f] = \mathbb{E}[g] = 0$ then $$ \|f \ast g\|_{\ell^2(G)} \leq \frac{1}{\sqrt{D}} \; |G| \; \big\|f\big\|_{\ell^2(G)} \; \big\|g\big\|_{\ell^2(G)} $$

Not knowing any better, I'd say this looks somewhat like the Cauchy-Schwarz inequality and I'd expect to use it in the same way.


I don't know what it means to say a group $(G, \cdot)$ is quasi-random. Are there any combinatorial objects which are "quasi-random" associated to $G$ ?

In the case of $\mathrm{SL}(2, \mathbb{F}_p)$ we find it is $\frac{p-1}{2}$-quasirandom. Can you randomly generate objects using the group $\mathrm{SL}(2, \mathbb{F}_p)$ ?

$\endgroup$
6
  • 6
    $\begingroup$ I think the terminology either originates in, or was inspired by, this paper arxiv.org/abs/0710.3877 $\endgroup$
    – Yemon Choi
    May 25, 2016 at 18:49
  • 3
    $\begingroup$ I thought that the terminology originated with Gowers, and the notion was introduced to produce large product-free sets in non-Abelian groups. Gowers has a paper titled "Quasirandom groups" ( available online) in which he considers ${\rm PSL}(2,q)$ and uses the fact that it has no non-trivial irreducible character of degree less than $\frac{q-1}{2}$. $\endgroup$ May 25, 2016 at 19:04
  • $\begingroup$ @YemonChoi : Oops sorry, I see we are referring to the same paper! $\endgroup$ May 25, 2016 at 19:05
  • 4
    $\begingroup$ I don't have the background/intuition to answer that question at a conceptual level, but Gowers's paper does briefly review known notions of "quasi-random graph", and I think it is that definition which is supposed to be relevant to behvaiour of ${\rm SL}(2,p)$ $\endgroup$
    – Yemon Choi
    May 26, 2016 at 2:21
  • 1
    $\begingroup$ Specifically, see Theorem 3.3 in Gowers. If $A$, $B$ and $C$ are subsets of $G$ then, if multiplication were a random map $G \times G \to G$, you would predict that the number of solutions to $ab=c$ with $a \in A$, $b \in B$, $c \in C$, would be about $|A| |B| |C|/|G|$. In a $D$-quasirandom group, if $|A| |B| |C| > |G|^3/(\epsilon^2 D)$, then the number of such solutions is at least $(1- \epsilon) |A| |B| |C|/|G|$. So, when $D$ is large, the hypothesis is easier to satisfy. $\endgroup$ Feb 25, 2022 at 15:41

0

Your Answer

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