Quasirandom groups enjoy interleaved mixing
Quasirandom groups enjoy interleaved mixing, Discrete Analysis 2023:14, 4 pp. In 1985 Babai and Sós asked whether there is a constant $c>0$ such that every group of order $n>1$ has a product-free subset of size at least $cn$, where this means a set $A$ such that it is not possible to find $a,...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Diamond Open Access Journals
2023-09-01
|
| Series: | Discrete Analysis |
| Online Access: | https://doi.org/10.19086/da.84738 |
| _version_ | 1797693249694990336 |
|---|---|
| author | Harm Derksen Emanuele Viola |
| author_facet | Harm Derksen Emanuele Viola |
| author_sort | Harm Derksen |
| collection | DOAJ |
| description | Quasirandom groups enjoy interleaved mixing, Discrete Analysis 2023:14, 4 pp.
In 1985 Babai and Sós asked whether there is a constant $c>0$ such that every group of order $n>1$ has a product-free subset of size at least $cn$, where this means a set $A$ such that it is not possible to find $a,b,c\in A$ with $ab=c$. A fairly straightforward argument shows that if the group is Abelian, then the answer is yes with $c=3/7$. (The constant comes from the fact that if the group is cyclic and $n$ is even then the odd elements form a sum-free set of size $n/2$, while for odd $n$ one can check that a suitable "middle third" of elements gives an example of size $\lfloor(n+1)/3\rfloor$. These examples are best possible, and the smallest ratio happens to occur when $n=7$.) However, for general groups there is no obvious construction, and in a 2008 paper Gowers showed that the answer is in general negative. More precisely, he defined a $d$-_quasirandom group_ to be a group with no non-trivial representation of dimension less than $d$, and proved that the largest product-free subset of a $d$-quasirandom group has cardinality $O(nd^{-1/3})$. This, combined with the fact that $d$-quasirandom groups exist with arbitrarily large $d$ (in fact, the group $\text{PSL}_2(q)$, which is of order roughly $q^3$, is $q$-quasirandom, so one can take $d$ to be of order of magnitude $n^{1/3}$), gives the negative answer in a strong form.
In a later paper, motivated by an application to cryptography, Gowers and Viola (the second author of this paper) obtained an extension of the above result for the group $G=\text{SL}_2(q)$, and with less good bounds for all non-Abelian simple groups, which are quasirandom. (The bounds in the latter case were improved by Shalev.) In qualitative terms, their result stated that if $t$ is a fixed positive integer and $A$ and $B$ are large subsets of $G^t$, and if we pick $(a_1,\dots,a_t)$ and $(b_1,\dots,b_t)$ uniformly and independently at random from $A^t$ and $B^t$, respectively, then the "interleaved product" $a_1b_1a_2b_2\dots a_tb_t$ is approximately uniformly distributed in the strong sense that the probability that for every $x\in G$ the probability that it takes the value $x$ is approximately $1/|G|$.
The proof was somewhat complicated, as it required a detailed analysis of the conjugacy classes of $\text{SL}_2(q)$ and a use of the Lang-Weil theorem. In this paper, the authors give a much simpler proof, with the added benefit that it applies not just to $\text{SL}_2(q)$ and to non-Abelian simple groups, but to all quasirandom groups, with a good dependence on the quasirandomness parameter in all cases.
There have been various other cases of results first established for specific quasirandom groups, and only later proved for all quasirandom groups, usually with simpler arguments. It is a pleasant surprise each time this happens. The argument in this paper is a particularly good example of the phenomenon: indeed, it seems appropriate to say that it is the "book proof" of the result. |
| first_indexed | 2024-03-12T02:39:50Z |
| format | Article |
| id | doaj.art-fa999f52d4a045a39920531fcc53a607 |
| institution | Directory Open Access Journal |
| issn | 2397-3129 |
| language | English |
| last_indexed | 2024-03-12T02:39:50Z |
| publishDate | 2023-09-01 |
| publisher | Diamond Open Access Journals |
| record_format | Article |
| series | Discrete Analysis |
| spelling | doaj.art-fa999f52d4a045a39920531fcc53a6072023-09-04T08:19:53ZengDiamond Open Access JournalsDiscrete Analysis2397-31292023-09-01Quasirandom groups enjoy interleaved mixingHarm DerksenEmanuele ViolaQuasirandom groups enjoy interleaved mixing, Discrete Analysis 2023:14, 4 pp. In 1985 Babai and Sós asked whether there is a constant $c>0$ such that every group of order $n>1$ has a product-free subset of size at least $cn$, where this means a set $A$ such that it is not possible to find $a,b,c\in A$ with $ab=c$. A fairly straightforward argument shows that if the group is Abelian, then the answer is yes with $c=3/7$. (The constant comes from the fact that if the group is cyclic and $n$ is even then the odd elements form a sum-free set of size $n/2$, while for odd $n$ one can check that a suitable "middle third" of elements gives an example of size $\lfloor(n+1)/3\rfloor$. These examples are best possible, and the smallest ratio happens to occur when $n=7$.) However, for general groups there is no obvious construction, and in a 2008 paper Gowers showed that the answer is in general negative. More precisely, he defined a $d$-_quasirandom group_ to be a group with no non-trivial representation of dimension less than $d$, and proved that the largest product-free subset of a $d$-quasirandom group has cardinality $O(nd^{-1/3})$. This, combined with the fact that $d$-quasirandom groups exist with arbitrarily large $d$ (in fact, the group $\text{PSL}_2(q)$, which is of order roughly $q^3$, is $q$-quasirandom, so one can take $d$ to be of order of magnitude $n^{1/3}$), gives the negative answer in a strong form. In a later paper, motivated by an application to cryptography, Gowers and Viola (the second author of this paper) obtained an extension of the above result for the group $G=\text{SL}_2(q)$, and with less good bounds for all non-Abelian simple groups, which are quasirandom. (The bounds in the latter case were improved by Shalev.) In qualitative terms, their result stated that if $t$ is a fixed positive integer and $A$ and $B$ are large subsets of $G^t$, and if we pick $(a_1,\dots,a_t)$ and $(b_1,\dots,b_t)$ uniformly and independently at random from $A^t$ and $B^t$, respectively, then the "interleaved product" $a_1b_1a_2b_2\dots a_tb_t$ is approximately uniformly distributed in the strong sense that the probability that for every $x\in G$ the probability that it takes the value $x$ is approximately $1/|G|$. The proof was somewhat complicated, as it required a detailed analysis of the conjugacy classes of $\text{SL}_2(q)$ and a use of the Lang-Weil theorem. In this paper, the authors give a much simpler proof, with the added benefit that it applies not just to $\text{SL}_2(q)$ and to non-Abelian simple groups, but to all quasirandom groups, with a good dependence on the quasirandomness parameter in all cases. There have been various other cases of results first established for specific quasirandom groups, and only later proved for all quasirandom groups, usually with simpler arguments. It is a pleasant surprise each time this happens. The argument in this paper is a particularly good example of the phenomenon: indeed, it seems appropriate to say that it is the "book proof" of the result.https://doi.org/10.19086/da.84738 |
| spellingShingle | Harm Derksen Emanuele Viola Quasirandom groups enjoy interleaved mixing Discrete Analysis |
| title | Quasirandom groups enjoy interleaved mixing |
| title_full | Quasirandom groups enjoy interleaved mixing |
| title_fullStr | Quasirandom groups enjoy interleaved mixing |
| title_full_unstemmed | Quasirandom groups enjoy interleaved mixing |
| title_short | Quasirandom groups enjoy interleaved mixing |
| title_sort | quasirandom groups enjoy interleaved mixing |
| url | https://doi.org/10.19086/da.84738 |
| work_keys_str_mv | AT harmderksen quasirandomgroupsenjoyinterleavedmixing AT emanueleviola quasirandomgroupsenjoyinterleavedmixing |