It is well-known that the order of $GL(2, p)$ is $(p^2-1)(p^2-p) = (p-1)^2(p+1)p.$ It is easy to construct matrices of orders $(p-1)$ and $p$ (diagonal and parabolic, respectively), but the only way that leaps to mind of constructing an element of order $p+1$ is by constructing the companion matrix of the irreducible polynomial whose root is the multiplicative generator of $GF( p^2)$ and then raising it to $p-1$st power - this is quite non-explicit. I assume there is no explicit construction which works for all $p,$ but I could be wrong: is there?
$\begingroup$
$\endgroup$
5
asked Dec 3, 2015 at 12:51
-
$\begingroup$ The characteristic polynomial of such matrix is an irreducible (quadratix) factor of $\Phi_{p+1}(x)\mod p$. So, the tasks to find such matrix and to find such factor are equivalent. $\endgroup$– Ilya BogdanovCommented Dec 3, 2015 at 14:25
-
1$\begingroup$ Such a matrix will have determinant -1, and if you could find a trace that works explicitly you could find a non-residue mod p explicitly. Though this can be done quickly, I don't think there's any known way that fits your notion of "explicit". $\endgroup$– paul MonskyCommented Dec 3, 2015 at 15:05
-
$\begingroup$ @paulMonsky Could you elaborate on your comment? In any case, as noted in my comment to Geoff, even to find a matrix of order $p-1$ we need to find a primitive root, so I suppose it is not unreasonable to suppose that such a root is known (of course, it is also a non-residue...) $\endgroup$– Igor RivinCommented Dec 3, 2015 at 15:08
-
$\begingroup$ @Igor Rivin It seems to me that once you say that it's not unreasonable to suppose that a primitive root is known or even that a non-residue is known you've sidestepped the notion of "explicitness". I imagine that on the GRH there's a small trace that will work, so that you can construct your matrix quickly and deterministically, but I don't think this would satisfy you. $\endgroup$– paul MonskyCommented Dec 3, 2015 at 15:38
-
$\begingroup$ @paulMonsky Again, the point is that even to construct a matrix of order $p-1$ you need to know a primitive root, so it is hard to hope for anything more, but maybe the knowledge of one primitive root is enough... $\endgroup$– Igor RivinCommented Dec 3, 2015 at 15:52
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
6
Here's a construction of sorts, which works for odd $p$ : find an element $d \in \mathbb{F}_{p}$ such that $-d$ is a non-square. Then the polynomial $x^{2}+d$ is irreducible in $\mathbb{F}_{p}[x]$. The matrices in $\{ \left( \begin{array}{clcr} a & b\\-db & a \end{array} \right) \}$ with $a, b \in \mathbb{F}_{p}$ (not both zero) form a cyclic group of order $p^{2}-1$. Admittedly, this is only very slightly more explicit than that outlined in the question.
answered Dec 3, 2015 at 13:46
-
2$\begingroup$ The fact that this group is cyclic is not obvious: it is isomorphic to $K^\times$ where $K={\mathbb F}_p[\sqrt{-d}]$. This answer seems to be a rephrasing of the construction evocked in the question. $\endgroup$ Commented Dec 3, 2015 at 14:20
-
$\begingroup$ Is it correct to say that $\begin{pmatrix}0 & 1\\-d & 0\end{pmatrix}$ is the generator? $\endgroup$ Commented Dec 3, 2015 at 14:27
-
2$\begingroup$ @Denis Serre: Yes, as I indicated in the answer, I am not going far beyond what is suggested in the question (but I think a little). It is in fact "obvious" that the given group is cyclic: those matrices, together with the zero matrix, form a finite division ring ( so a field), by Schur's Lemma, since they are the matrices commuting with an irreducible (cyclic) algebra. $\endgroup$ Commented Dec 3, 2015 at 14:42
-
2$\begingroup$ So, we don't know which the generator is? If we did, notice that to find the matrix of order $p-1$ we need to find a primitive root mod p, which we call $r.$ Now, $r$ is not a square, so we can take $d=-r$ in your construction, which means that it is no harder to find an element of order $p+1$ than of order $p-1.$ Of course, if we do not know the generator, that's different... $\endgroup$ Commented Dec 3, 2015 at 14:49
-
2$\begingroup$ If you restrict to the subgroup where $\det = a^2+d b^2=1$, that will give you a cyclic subgroup of order $p+1$. I doubt there is any way to get an explicit generator though; this should be as hard as asking for an explicit primitive root in $\mathbb{F}_p$, and there is no good method for that. $\endgroup$ Commented Dec 3, 2015 at 16:08
$\begingroup$
$\endgroup$
Here is a slightly different way to think about this, though I admit that it is not really "explicit". Let $E$ be the field of order $p^2$, so $E$ is a two-dimensional vector space over the subfield $F$ of order $p$. The multiplicative group of $E$ is cyclic of order $p^2 - 1$, so if $x$ is a generator, then multiplication by $x$ is an $F$-linear transformation of $E$ with multiplicative order $p^2 - 1$. Now by choosing any $F$-basis for $E$, this linear transformation determines a matrix which is an element of $GL(2,p)$ having order $p^2 - 1$. A suitable power of this matrix has order $p+1$.
$\begingroup$
$\endgroup$
As the discussion shows, there really isn't any explicit construction which works for all primes $p$. (Here you really want to specify that $p$ is odd, however, to avoid trivialities.) It may or may not help to put the question into a somewhat broader framework; but anyway it's harmless to consider the same question for an arbitrary power $q$ of $p$.
This begins historically with the work of Frobenius and Schur on characters of $G=\mathrm{SL}_2(\mathbb{F_q})$, followed by study of higher rank algebraic groups close to finite simple groups of Lie type (by many people including Brauer, Steinberg, Green, Macdonald, Deligne-Lusztig). It's almost equivalent to study general or special linear groups here. From the perspective of finite subgroups of semisimple algebraic groups over an algebraically closed field of characteristic $p$, one sees in the concrete case of $G$ that there are two distinct types of "maximal tori" over $\mathbb{F}_q$: the "split" diagonal group of order $q-1$ and the "anisotropic" (similar to "compact") group of order $q+1$. Here the anisotropic torus becomes diagonal over a quadratic extension of $\mathbb{F}_q$. (In general the types of finite tori are parametrized by something like the conjugacy classes in the Weyl group, here of order 2.)
Unfortunately there is no all-purpose recipe for a matrix of order $q+1$, which over $\mathbb{F}_{q^2}$ is diagonalizable but not over $\mathbb{F}_q$: the best one can do using ordinary linear algebra is to specify the rational canonical form $$\begin{pmatrix} 0 & -1 \\ 1 & \theta + \theta^q \end{pmatrix},$$ where $\theta$ is a primitive $(q+1)$-th root of unity in the big field (so $\theta^{-1}= \theta^q$). Here $\theta$ and its inverse are the eigenvalues of the matrix in question.
Some textbooks on characters of finite groups treat $G$ as an example, and there is a 2011 Springer text Representations of $\mathrm{SL}_2(\mathbb{F}_q)$ by Cedric Bonnafe which uses $G$ to introduce ideas from the Deligne-Lusztig theory.
answered Dec 3, 2015 at 19:16