Computer Science/Discrete Mathematics Seminar II

Let $S$ and $T$ be two dense subsets of $G^n$, where $G$ is the special linear group $\mathrm{SL}(2,q)$ for a prime power $q$. If you sample uniformly a tuple $(s_1,\ldots,s_n)$ from $S$ and a tuple $(t_1,\ldots,t_n)$ from $T$ then their interleaved product $s_1.t_1.s_2.t_2 \ldots s_n.t_n$ is equal to any fixed $g$ in $G$ with probability $(1/|G|)(1 + |G|^{-\Omega(n)})$. Equivalently, the communication complexity of distinguishing tuples whose interleaved product is equal to $g$ from those whose product is equal to a different $g'$ is $\Omega(n \log |G|)$, even if the protocol is randomized and only achieves a small advantage over random guessing. This result is tight and improves on the $\Omega(n)$ bound that follows by reduction from the inner product function. Gowers (2007) and later Babai, Nikolov, and Pyber proved that if $S$, $T$, and $U$ are dense subsets of a simple, non-abelian group $G$ then $STU = g$ with probability $(1/|G|)(1 + o(1))$. For the special case of $G = \mathrm{SL}(2,q)$, this also follows from our result. Unlike previous proofs, ours does not rely on representation theory. Joint work with Timothy Gowers.