10
$\begingroup$

Suppose a group $G$ acts on a set $\Omega$. Call a subset $A \subset G$ regular (or sharply transitive or simply transitive or...) if for every two points $\omega_1, \omega_2 \in \Omega$ there is a unique $a \in A$ such that $\omega_1^a = \omega_2$. This generalizes the concept of a regular subgroup to subsets.

Consider the action of $G = \def\PSL{{\text{PSL}}}\def\F{{\mathbf{F}}}\def\projline{{\mathbf{P}^1 \F_q}}\PSL(2, q)$ on the projective line $\Omega = \projline$. It is not hard to prove that $G$ has a regular subgroup if and only if $q \not\equiv 1 \pmod 4$. Indeed if $q$ is even then there is a cyclic regular subgroup, and if $q \equiv 3 \pmod 4$ then there is a dihedral regular subgroup, while if $q \equiv 1 \pmod 4$ then any subgroup of order $q+1$ must contain an element of order $2$, but every element of order $2$ has eigenvalues $\pm i$ and hence two fixed points. But could $G$ yet have a regular subset?

Does $G = \PSL(2, q)$ for $ q \equiv 1 \pmod 4$ acting on $\projline$ have a regular subset?

The answer is no for $q = 5, 9, 13, 17$, by direct computation.

$\endgroup$
6
  • $\begingroup$ Can you give an example of a regular subset that doesn't induce a regular subgroup? $\endgroup$ Aug 15, 2019 at 19:08
  • 2
    $\begingroup$ Any coset of a regular subgroup is a regular subset. $\endgroup$ Aug 15, 2019 at 22:10
  • 2
    $\begingroup$ @StevenStadnicki For $S_n$ and its standard action, regular subsets correspond exactly with $n\times n$ Latin squares, and there are many more of these than subgroups. In particular $A_6$ has no regular subgroup but it does have a regular subset (you need a $6\times 6$ Latin square with all rows even). $\endgroup$ Aug 16, 2019 at 6:38
  • $\begingroup$ I wonder whether it is realted to orthogonal Latin squares of size $q+1=4k+2$ which were assumed by Euler to not exist (disproved by R.C. Bose, S.S. Shrikhande and E.T. Parker). $\endgroup$ Aug 16, 2019 at 9:54
  • $\begingroup$ @RichardLyonsThe cosets are what I meant by 'inducing' a regular subgroup, though I should perhaps have phrased it the other way around. I really like the $A_6$ example, though; that's very helpful to me. Thank you! $\endgroup$ Aug 16, 2019 at 14:25

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ This is exactly the sort of parity obstruction I was hoping to find, thank you! I'm sure there is a very simple way of expressing it now that you've found it, but I think I might have learned something about how to do maths from your answer. $\endgroup$ Aug 16, 2019 at 22:56
  • 1
    $\begingroup$ I have proved that your $M$ indeed works, though I'm still working on a higher-level understanding of what's going on. To prove that it works reduces to showing for every fixed-point-free $g \in G$, say $\def\eps{\epsilon} g = (a, \eps b ; b, a)$ where $\eps$ is nonsquare and $a^2 - \eps b^2 = 1$, there are an odd number of finite $x$ mapped to a finite point $x^g$ such that $x^g - x$ is square. This is equivalent to showing that $(x^2 - \eps)/(x - a/b) = z^2$ has an odd number of solutions $x$. You can check that there is exactly one value of $z^2$ for which this equation has a double root. $\endgroup$ Aug 17, 2019 at 8:27
  • 1
    $\begingroup$ There are 3 degrees of freedom in your choice of $M$: you can translate by $J$, $I$, or by the matrix which is $1$ if $x = \infty$ or $y = \infty$ but not both. This accounts for your 8 observed choices. $\endgroup$ Aug 17, 2019 at 8:31
  • 2
    $\begingroup$ @FedorPetrov Your element $g$ fixes $\infty$, so it's not considered. $\endgroup$ Aug 17, 2019 at 8:49
  • $\begingroup$ Thank you for the pointer to your paper! I'm afraid it had escaped my notice, and is of course highly relevant. $\endgroup$ Aug 17, 2019 at 14:44
4
$\begingroup$

This is an attempt to understand the very nice argument by Peter Mueller (completed by OP, Sean Eberhard, in the comments). I am not completely happy with it, and would like to encourage others to look for more conceptual explanations.

Denote $\Omega:=P^1\mathbb{F}_q=\mathbb{F}_q\cup \infty$, so that $|\Omega|=q+1$ and the group $G=PSL(2,q)$ acts on $\Omega$ by projective transformations. Assume that $S\subset G=PSL(2,q)$, $|S|=q+1$ is chosen so that $$\sum_{s\in S} \mathbb{1}_{s(i)=j}=1,\quad\forall i,j\in \Omega.$$ Then the same holds for the set $g_0S$ for any $g_0\in G$, thus we may suppose that $id\in S$, therefore other elements of $S$ do not have fixed points. Denote by $G^\star$ the set of fixed-point-free elements from 𝐺 together with 1, we have $S\subset G^\star$. Consider the function $M(i,j)$ on $\Omega\times \Omega$ defined as $$ M(i,j)=\begin{cases}1,\, \text{if}\,\, i=\infty,\, j\ne \infty\\ 1,\, \text{if}\,\, i,j\in \mathbb{F}_q,\chi(i-j)=1\\ 0,\, \text{otherwise}.\end{cases} $$ Here $\chi$ is a quadratic character of $\mathbb{F}_q$ (Legendre symbol if $q$ is prime). We get $$ \sum_{i,j\in \Omega,s\in S} M(i,j)\mathbb{1}_{s(i)=j}=\sum_{i,j\in \Omega} M(i,j)=q+q(q-1)/2 $$ is odd. Thus to get a contradiction it suffices to prove that $$ \sum_{i,j\in \Omega} M(i,j)\mathbb{1}_{s(i)=j} $$ is even for any fixed element $s\in G^\star$. For $s=id$ all summands are just zeroes. If $s$ does not have fixed point, than $$ \sum_{i,j\in \Omega} M(i,j)\mathbb{1}_{s(i)=j}=1+\sum_{i\in \mathbb{F}_q} M(i,s(i))=1+\left|i\in \mathbb{F}_q:\chi(s(i)-i)=1\right|. $$ Note that for fixed $\alpha\in \mathbb{F}_q$, the equation $$s(x)-x=\alpha\quad \quad (1)$$ is quadratic with respect to $x$, thus it has even number of roots unless it has a double root. We prove that there exists unique quadratic residue $\alpha$ for which (1) has a double root, the result would follow.

It may be proved by straightforward calculations, but let me give an argument if not conceptual, but at least almost calculations-free.

First of all, we use the following characterization of $PSL(2,q)$ (probably well known, but I did not see it before.)

Lemma. A projective transformation $s(x)=\frac{ax+b}{cx+d}, c\ne 0$, belongs to $PSL(2,q)$ if and only if the equation $s'(x)=1$ has two roots in $\mathbb{F}_q$.

Proof. Note that both properties are preserved when we replace $s(x)$ to $s(x)+C$ and $s(x+C)$ for constant $C\in \mathbb{F}_q$. So we may suppose that $a=0$ (subtract constant $a/c$ from $s(x)$) and also that $d=0$ (replace $s(x)$ by $s(x-d/c)$). So $s(x)=M/x$ for some constant $M$, and both conditions say that $-M$ is a non-zero square.

Next observation concerns the discriminants of the quadratic equation and critical values of corresponding functions. For the equation $f(x)=-x^2+2ax-b=0$, we all know that its discriminant $a^2-b$ equals $f(x_0)$, where $x_0=a$ is the critical value. But we deal with a slightly different equation $h(x):=s(x)-x=0$. After shifting the variable we get a function of the form $h_0(x)=-A/x+B-x$. Its discriminant is $D=B^2-4A$, and the critical values are $x_1=\sqrt{A},x_2=-\sqrt{A}$, so in our situation $A$ is a square by Lemma. Also we get $$D=h_0(x_1)h_0(x_2).$$

Since $h(x)=s(x)-x$ does not have roots, $D$ is not a square. Thus exactly one of two values of $h$ at critical points is a square. This value is the unique appropriate $\alpha$, as desired.

$\endgroup$
1
  • $\begingroup$ Interesting characterization of PSL(2,K) as a subgroup of PGL(2,K) for fields $K$ of characteristic $\ne2$ (I haven't seen that before), and nice finish of the argument! $\endgroup$ Aug 17, 2019 at 15:01
4
$\begingroup$

I have come across some references for this problem, which amount to a solution very different from the (beautiful) one given by Peter Mueller, and which also goes further. It turns out that it is possible to show directly that a sharply transitive subset of $\mathrm{PGL}_2(q)$ acting on $\mathbf{P}^1$ must be a coset of a subgroup. Since the subgroups of $\mathrm{PGL}_2(q)$ are classified, so are regular subsets.

This result is due to Bader, Lunardon, and Thas, who classified flocks of the hyperbolic quadric $\mathcal{Q} \subset \mathbf{P}^3$. The solution was given in the following two papers.

Thas, J. A., Flocks, maximal exterior sets, and inversive planes, Finite geometries and combinatorial designs, Proc. AMS Spec. Sess., Lincoln/NE (USA) 1987, Contemp. Math. 111, 187-218 (1990). ZBL0728.51010.

Bader, Laura; Lunardon, Guglielmo, On the flocks of (Q^+(3,q)), Geom. Dedicata 29, No. 2, 177-183 (1989). ZBL0673.51010.

On the face of it the problem these authors study is different, but it is equivalent. A flock is a partition of a quadric into conics. The quadric $\mathcal{Q}$ can be taken without loss of generality to be the subset $\det A = 0$ of the space $M_2(K) / Z$ of $2\times2$ matrices up to scalars. Each conic can be identified with the plane it spans and hence by duality with a point of $\mathbf{P}^3 = M_2(K)/Z$. The condition that the planes intersect $\mathcal{Q}$ in disjoint subsets is equivalent to saying that the the corresponding points define a regular subset (or maximal exterior set, as they call it).

The equivalence is explicit in the introduction here:

Bonisoli, Arrigo; Korchmáros, Gábor, Flocks of hyperbolic quadrics and linear groups containing homologies, Geom. Dedicata 42, No. 3, 295-309 (1992). ZBL0756.51009.

I took some time to boil off all the geometry, and I wrote up what was left here: https://arxiv.org/abs/2105.02760

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.