Skip to main content
4 of 4
Added a remark
Peter Mueller
  • 22.5k
  • 1
  • 75
  • 107

This is not a complete solution of the problem, but only an outline of a possible strategy, along with some numerical evidence: Let $S$ be a subset of $G=\operatorname{PSL}(2,q)$. For $g\in G$ let $P_g$ be the permutation matrix of $g$, and let $J$ be the all-$1$-matrix of the same size. Then regularity of $S$ is equivalent to $\sum_{g\in S}P_g=J$. Thus the existence of a regular subset of $G$ is equivalent to the existence of a solution of \begin{equation} \sum_{g\in G}x_gP_g=J \end{equation} for $x_g\in\{0,1\}$.

If there is a regular subset, then we may assume that it contains $1$, so the remaining elements are fixed-point-free. Let $G^\star$ be the set of fixed-point-free elements from $G$ together with $1$. Then the existence of a regular subset is equivalent to the $0$-$1$-solvability of \begin{equation} \sum_{g\in G^\star}x_gP_g=J. \end{equation} Now it seems to be the case that this system of linear equations in the $x_g$ isn't even solvable over $\mathbb F_2$. I have verified that for all $q\le 89$.

How could one prove that in general? Let $V$ be the space of $(q+1)\times(q+1)$ matrices over $\mathbb F_2$. Then $V\times V\to\mathbb F_2$, $(U,V)\mapsto\operatorname{trace}(UV)$ is a nondegenerate bilinear form on $V$.

From that we get the following: If the system is not solvable, then there is a matrix $M$ which is orthogonal to the space of matrices generated by the left hand side, but is not orthogonal to $J$. The converse holds of course too.

Thus we are left to find $M$ such that $\operatorname{trace}(P_gM)=0$ for all $g\in G^\star$, and $\operatorname{trace}(JM)=1$.

One may even make some additional assumptions on $M$. For $h\in G$ set $M^h=P_h^{-1}MP_h$. If $H$ is a subgroup of $G$ of odd order, and $M$ fulfills the assumptions from above, then $\sum_{h\in H}M^h$ fulfills this assumption too.

Thus in the search for $M$ we may restrict to those matrices for which $M^h=M$ for all $h\in H$. If $q$ is a power of the prime $p$, and $H$ is a $p$-Sylow subgroup of $G$, then it seems to be that there are exactly $8$ choices for such an $M$, no matter what $q$ is.

A working family of matrices $M$ seems to be as follows: Use $\mathbb F_q\cup\{\infty\}$ to number the rows and columns of $M$. Then $M[i,j]=1$ if and only if either $j=\infty$, $i\in\mathbb F_q$, or $i,j\in\mathbb F_q$ are distinct and $i-j$ is a square.

To prove that this $M$ works reduces to a concrete question about $\mathbb F_q$ which shouldn't be hard to prove.

I would be curious to learn the background or the motivation of this question.

Remark: It would be interesting to see other methods for proving non-existence of regular sets of permutations. Some years ago I worked with Theo Grundhöfer and Gabor Nagy on such questions. In most cases, the non-solvability of the first displayed equation modulo a prime was the most successful technique. In those cases, one could even choose $M$ as a rank $1$ matrix, which allowed for a direct and easy to use argument (we called it contradicting subsets lemma, see Lemma 2 in https://arxiv.org/abs/1005.1598). The special features of your question seem to be: (a) One really has to work with the second displayed equation, the first one does not give a contradiction, and (b) For $q\ge9$ it seems that there is no matrix $M$ as above (with no assumption on $H$-symmetry) of rank $1$, so the contradicting subsets lemma does not work here.

Peter Mueller
  • 22.5k
  • 1
  • 75
  • 107