# A Note on Slice Rank and Matchings in Groups

Kevin Pratt

###### Abstract

A multiplicative 3-matching in a group $G$ is a triple of sets
$\\{a_{i}\\},\\{b_{i}\\},\\{c_{i}\\}\subset G$ such that $a_{i}b_{j}c_{k}=1$
if and only if $i=j=k$. Here we record the fact that $\textnormal{PSL}(2,p)$
has no multiplicative 3-matching of size greater than $O(p^{8/3})$, yet the
slice rank of its group algebra’s multiplication tensor is at least
$\Omega(p^{3})$ over any field. This gives a negative answer to a conjecture
of Petrov.

##  1 Introduction

A _multiplicative 3-matching_ in a finite group $G$, hereon abbreviated to a
3-matching, is a triple of subsets
$\\{a_{i}\\}_{i=1}^{m},\\{b_{i}\\}_{i=1}^{m},\\{c_{i}\\}_{i=1}^{m}$ of $G$
such that $a_{i}b_{j}c_{k}=1\iff i=j=k$. Let $M(G)$ denote the largest
size111By size we mean the parameter $m$. of a 3-matching in $G$. This
quantity is of interest in additive combinatorics, as finite groups provide a
model setting for understanding 3-term arithmetic-progression-free sets in the
integers. It also has connections to algorithms for fast matrix multiplication
[CKSU05].

The polynomial method of Croot, Lev, and Pach [CLP17] and Ellenberg and
Gijswijt [EG17], and its formulation in terms of _slice rank_ due to Tao
[Tao16], is a powerful tool for establishing upper bounds on $M(G)$.
Remarkably, it gives an asymptotically tight bound on $M(G)$ in the case of
${\mathbb{F}}_{p}^{n}$ with $p>2$ a fixed prime. Specifically, it shows that
for a certain $c_{p}<p$ we have $M({\mathbb{F}}_{p}^{n})\leq c_{p}^{n}$, and
it is also known that $M({\mathbb{F}}_{p}^{n})\geq c_{p}^{(1-o(1))n}$ [KSS16].
This raises the following question, previously asked in [Pet16]: is the slice
rank bound on $M(G)$ always tight?

We now make these notions formal. We assume throughout that $k$ is an
algebraically closed field222This is without loss of generality for us, since
slice rank can only decrease under field extensions and we will prove a slice
rank lower bound.. Following [TS16, Lemma 1(iv)], the slice rank of a
trilinear form $T:U_{1}\times U_{2}\times U_{3}\to k$ is

${\mathrm{SR}}(T)=\max_{\begin{subarray}{c}V_{i}\leq U_{i}:\\\
T(V_{1},V_{2},V_{3})=0\end{subarray}}{\mathrm{codim}}(V_{1})+{\mathrm{codim}}(V_{2})+{\mathrm{codim}}(V_{3}).$

This can be thought of as an analogue of the “codimension of the kernel”
definition of matrix rank for trilinear forms. To use slice rank to prove
bounds on $M(G)$, we consider the multiplication tensor
$T_{k[G]}:(k^{|G|})^{\times 3}\to k$ of the group algebra $k[G]$, defined as
$T_{k[G]}=\sum_{g,h\in G}x_{g}y_{h}z_{gh}$. The key fact is that
${\mathrm{SR}}(T_{k[G]})$ is at least $M(G)$ for any $k$ [Tao16, Lemma 1];
this is an analogue of the fact that the rank of a matrix is at least the size
of the largest identity-submatrix it contains. Hence upper bounds on
${\mathrm{SR}}(T_{k[G]})$ imply upper bounds on $M(G)$. Motivated by this, we
make the following definition.

######  Definition 1.1.

${\mathrm{SR}}(G)=\min_{k}{\mathrm{SR}}(T_{k[G]})$.

Here the minimum is taken over all algebraically closed fields; crucially, the
characteristic of $k$ can be arbitrary. In the case that
$G={\mathbb{F}}_{p}^{n}$ for example,
${\mathrm{SR}}(T_{{\mathbb{C}}[{\mathbb{F}}_{p}^{n}]})=p^{n}$ [BCC+17,
Corollary b.17] but
${\mathrm{SR}}(T_{{\mathbb{F}}_{p}[{\mathbb{F}}_{p}^{n}]})\leq c_{p}^{n}$.
This leads to the following conjecture, which is slightly weaker than one
appearing in [Pet16]:333The conjecture of [Pet16] asked if $M(G)$ is roughly
the sum of codimensions of subspaces multiplying to 0 in $k[G]$, whereas 1.2
is equivalent to asking if $M(G)$ is roughly the sum of codimensions of
subspaces whose product merely vanishes on the coefficient of 1 in $k[G]$.

######  Conjecture 1.2.

${\mathrm{SR}}(G)\leq M(G)\cdot|G|^{o(1)}$.

In this work we note that $\textnormal{PSL}(2,p)$ has no large 3-matchings but
has high slice rank over any field, so 1.2 is false. Both of these facts are
in large part due to the lower bound of [LS74] on the dimensions of nontrivial
irreducible representations of $\textnormal{PSL}(2,p)$. The fact that
$\textnormal{PSL}(2,p)$ has no large 3-matching follows almost immediately
from Gowers’s result on quasirandom groups [Gow08]. We now give a quick proof
of this.

######  Proposition 1.3.

$M(\textnormal{PSL}(2,p))\leq O(p^{8/3})$.

###### Proof.

A triple of subsets $A,B,C\subset G$ is called product-free if $abc\neq 1$ for
all $a\in A,b\in B,c\in C$. If $A,B,C$ is a 3-matching of size $m$, then there
is a product-free triple of sets in $G$ of size $m^{\prime}:=\lfloor
m/3\rfloor$ consisting of
$\\{a_{i}\\}_{i=1}^{m^{\prime}},\\{b_{i}\\}_{i=m^{\prime}+1}^{2m^{\prime}},\\{c_{i}\\}_{i=2m^{\prime}+1}^{3m^{\prime}}$.
In [Gow08] it is shown that $\textnormal{PSL}(2,p)$ does not contain product-
free subsets larger than $O(p^{8/3})$, so the proposition follows. ∎

In the next section we the following slice rank lower bound.

######  Theorem 1.4.

${\mathrm{SR}}(\textnormal{PSL}(2,p))\geq\Omega(p^{3})$.

##  2 Proof of Theorem 1.4

If $A$ is a finite dimensional algebra over $k$, we let $T_{A}\in A^{*}\otimes
A^{*}\otimes A$ denote its multiplication tensor. If $e_{1},\ldots,e_{n}$ is a
basis of $A$ with dual basis $e_{1}^{*},\ldots,e_{n}^{*}$, this tensor is
given in coordinates by $\sum_{1\leq i,j\leq n}e_{i}^{*}\otimes
e_{j}^{*}\otimes(e_{i}\cdot e_{j})$. We can view this as a trilinear form, for
instance by linearly mapping $e_{i}^{*}\otimes e_{j}^{*}\otimes e_{k}$ to the
monomial $x_{i}y_{j}z_{k}$, and define its slice rank as in the introduction.
We write ${\mathrm{SR}}(A)$ for the slice rank of the multiplication tensor of
$A$.

Now we recall some basic facts about slice rank, namely that it is
nonincreasing under linear transformations, and that the slice rank of an
algebra is nonincreasing under quotients.

######  Lemma 2.1.

[TS16, Lemma 3] Let $T=\sum c_{ijk}u_{i}\otimes v_{j}\otimes w_{k}\in U\otimes
V\otimes W$, and let
$A\in{\textnormal{Hom}}(U,U^{\prime}),B\in{\textnormal{Hom}}(V,V^{\prime}),C\in{\textnormal{Hom}}(W,W^{\prime})$.
Then ${\mathrm{SR}}(\sum c_{ijk}A(u_{i})\otimes B(v_{j})\otimes
C(w_{k}))\leq{\mathrm{SR}}(T)$.

######  Lemma 2.2.

If $I$ is a two-sided ideal of $A$, then
${\mathrm{SR}}(A/I)\leq{\mathrm{SR}}(A)$.

###### Proof.

Let $\varphi:A\to A/I$ be the quotient map. Let $e_{1},\ldots,e_{n}$ be a
basis for $A$. Since $\varphi$ is an onto linear map, there exists
$S\subseteq[n]$ so that $\\{\varphi(e_{i})\\}_{i\in S}$ is a basis of $A/I$.
Let $P:A\to A/I$ be given by $P(e_{i})=\varphi(e_{i})$ for $i\in S$, and
$P(e_{i})=0$ if $i\notin S$. Similarly define $P^{\prime}:A^{*}\to(A/I)^{*}$
by $P^{\prime}(e_{i}^{*})=P(e_{i})^{*}$. Applying $P^{\prime}$ to the first
two factors of $T_{A}$ and $P$ to the third, we obtain $T_{A/I}$. By Lemma 2.1
this proves the claim. ∎

For an algebra $A$, we denote by ${\mathop{\textup{missing}}{Irr}}(A)$ the set
of non-isomorphic irreducible representations of $A$ over $k$. Recall that in
the ordinary (i.e., characteristic 0) representation theory of finite groups,
representations are completely reducible, and in particular the group algebra
$k[G]$ is isomorphic to a direct sum of matrix algebras. While this is false
when the characteristic of the field divides the order of the group, we still
have the following.

######  Definition 2.3.

The radical of $A$, denoted $\textnormal{J}(A)$, is the two-sided ideal of all
elements of $A$ which act by 0 on all irreducible representations of $A$.

######  Lemma 2.4.

[EGH+11, Theorem 2.12] Let $A$ be a finite-dimensional algebra. Then

$A/\textnormal{J}(A)\cong\bigoplus_{V\in{\mathop{\textup{missing}}{Irr}}(A)}{\mathrm{End}}(V).$

We will use the following fact, which says that the slice rank of direct sums
of matrix multiplication tensors is maximal.

######  Lemma 2.5.

[BCC+17, Proposition B.6] For any field $k$,
${\mathrm{SR}}(\bigoplus_{i=1}^{m}{\mathrm{End}}(k^{d_{i}}))=\sum_{i=1}^{m}d_{i}^{2}$.

The proof of Theorem 1.4 will go as follows. By Lemma 2.4,
$k[G]/\textnormal{J}(k[G])$ is a direct sum of matrix algebras, one for each
irreducible representation of $k[G]$. So by Lemma 2.5,
$k[G]/\textnormal{J}(k[G])$ has full slice rank, and by Lemma 2.2 this is a
lower bound on the slice rank of $k[G]$. So if we can show that there are many
sufficiently large irreps of $G$, we conclude that ${\mathrm{SR}}(k[G])$ is
large. To give an example of when this fails dramatically, when $G$ is any
$p$-group, the only irrep of $G$ when $k$ has characteristic $p$ is the
trivial one [S+77, Corollary of Proposition 26], so this argument only says
that ${\mathrm{SR}}(k[G])\geq 1$.

###### Proof of Theorem 1.4.

Let $G=\textnormal{PSL}(2,p)$ and let $k$ be a field of characteristic $\ell$.
First, if $\ell=0$ or $\ell$ is coprime to $|G|=(p-1)p(p+1)/2$, then $k[G]$ is
semisimple and so by Lemma 2.5 the slice rank of $k[G]$ equals
$|G|=\Omega(p^{3})$. Next, if $\ell=p$, then the irreps of ${\mbox{SL}}(2,p)$
are given by the action of $G$ on homogeneous polynomials in two variables of
degree up to $p-1$ with coefficients in $k$ [Alp93, p. 15]; since the center
of ${\mbox{SL}}(2,p)$ acts trivially on even degree polynomials, these are
also irreps of $\textnormal{PSL}(2,p)$ (in fact, all of them). By Lemma 2.4
the dimension of $k[G]/\textnormal{J}(k[G])$ is then
$\sum_{i=0}^{(p-1)/2}(2i+1)^{2}\geq\Omega(p^{3})$, so the claim holds.

So suppose $\ell\neq p$ divides $|G|=(p-1)p(p+1)/2$. By [Alp93, I.3 Theorem
2], the number of irreducible representations of $G$ equals the number of
conjugacy classes having order coprime to $\ell$. Next we show that there are
$\Omega(p)$ such conjugacy classes of $G$. This follows from the more general
bound of [HM22, Theorem 6.1]; here we sketch a proof for the special case of
$\textnormal{PSL}(2,p)$. See [FH13, p. 71] for a reference on conjugacy
classes of ${\mbox{SL}}(2,p)$, which we adapt to $\textnormal{PSL}(2,p)$. Most
elements in $G$ are either conjugate to an element of the _split torus_ , a
cyclic subgroup of order $(p-1)/2$, or the _non-split torus_ , a cyclic
subgroup of order $(p+1)/2$. The number of non-conjugate elements in the split
torus is at least $(p-3)/4$, and the number of non-conjugate elements in the
non-split torus is at least $(p-5)/4$ (with the exact values depending on
$p\bmod 4$). Because the orders of these tori are coprime, all conjugacy
classes of elements in at least one of the subgroups have order coprime to
$\ell$. So there are at least $(p-5)/4$ such conjugacy classes.

Finally, since the minimum dimension of a nontrivial irrep of $G$ is at least
$(p-1)/2$ in characteristic $\ell\neq p$ [LS74], we conclude by Lemma 2.4 that
$\dim k[G]/\textnormal{J}(k[G])\geq\Omega(p^{3})$, and thus by Lemma 2.5
${\mathrm{SR}}(k[G])\geq\Omega(p^{3})$. ∎

One might wonder if all sufficiently quasirandom groups (groups with no small
nontrivial irreps over ${\mathbb{C}}$) have high slice rank. Here is a
conjecture towards this question.

######  Conjecture 2.6.

For a fixed $\varepsilon>0$, let $G$ be a group of order $n$ that is
$n^{\varepsilon}$-quasirandom. Then for all fields $k$, we have the uniform
bound of $\dim k[G]/\textnormal{J}(k[G])\geq\Omega(n)$.

##  3 Acknowledgments

I thank Ryan O’Donnell for feedback on a previous draft, and Josh Grochow for
helpful clarifications.

## References

  * [Alp93] Jonathan L Alperin, _Local representation theory: Modular representations as an introduction to the local representation theory of finite groups_ , Cambridge University Press, 1993.
  * [BCC+17] Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A Grochow, and Chris Umans, _Which groups are amenable to proving exponent two for matrix multiplication?_ , arXiv preprint arXiv:1712.02302 (2017).
  * [CKSU05] Henry Cohn, Robert Kleinberg, Balázs Szegedy, and Christopher Umans, _Group-theoretic algorithms for matrix multiplication_ , Proceedings of the 46th Annual Symposium on Foundations of Computer Science (FOCS 2005), IEEE Computer Society, 2005, pp. 379–388.
  * [CLP17] Ernie Croot, Vsevolod F Lev, and Péter Pál Pach, _Progression-free sets in are exponentially small_ , Annals of Mathematics (2017), 331–337.
  * [EG17] Jordan S Ellenberg and Dion Gijswijt, _On large subsets of with no three-term arithmetic progression_ , Annals of Mathematics (2017), 339–343.
  * [EGH+11] Pavel I Etingof, Oleg Golberg, Sebastian Hensel, Tiankai Liu, Alex Schwendner, Dmitry Vaintrob, and Elena Yudovina, _Introduction to representation theory_ , vol. 59, American Mathematical Soc., 2011.
  * [FH13] William Fulton and Joe Harris, _Representation theory: a first course_ , vol. 129, Springer Science & Business Media, 2013.
  * [Gow08] W. T. Gowers, _Quasirandom groups_ , Combin. Probab. Comput. 17 (2008), no. 3, 363–387.
  * [HM22] Nguyen Ngoc Hung and Attila Maróti, _p-regular conjugacy classes and p-rational irreducible characters_ , Journal of Algebra 607 (2022), 387–425.
  * [KSS16] Robert Kleinberg, Will Sawin, and David E Speyer, _The growth rate of tri-colored sum-free sets_ , arXiv preprint arXiv:1607.00047 (2016).
  * [LS74] Vicente Landazuri and Gary M. Seitz, _On the minimal degrees of projective representations of the finite Chevalley groups_ , J. Algebra 32 (1974), 418–443.
  * [Pet16] Fedor Petrov, _Combinatorial results implied by many zero divisors in a group ring_ , arXiv preprint arXiv:1606.03256 (2016).
  * [S+77] Jean-Pierre Serre et al., _Linear representations of finite groups_ , vol. 42, Springer, 1977.
  * [Tao16] Terence Tao, _Symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound_ , 2016, Available at https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/.
  * [TS16] Terence Tao and Will Sawin, _Notes on the “slice rank” of tensors_ , 2016, Available at https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors/.