[math-fun] Toe-curling classical number-theory problem
The following kept me at bay for an embarrassing length of time, despite my conviction that there just had to be a simple, one --- well, maybe three --- line proof (there is). Question (elementary): for p odd prime, show that the order of any element of PGL(2, p) divides some member of {p-1, p, p+1} . Rider (harder): locate where the @£$%^&* this might be concealed amidst the 330-odd densely obfuscated pages of L. E. Dickson (1901, 1958) "Linear groups with an exposition of the Galois field theory" Some things were quite definitely not better in the old days! Fred Lunnon
Fred, Let F=GF(p^2) as a vector space over GF(p). Let sigma be the matrix which raises an element of F to the p-th power. Every 2 by 2 matrix can be written uniquely as a*sigma + b, where a and b are elements of F. In modern terms you want to show that every element in GL_2 is in a Cartan subgroup -- a conjugate of multiplication by an element of F and its powers, or in a Borel subgroup, which is conjugate to the subgroup of powers of F. Victor Sent from my iPhone On Mar 20, 2013, at 21:19, Fred lunnon <fred.lunnon@gmail.com> wrote:
The following kept me at bay for an embarrassing length of time, despite my conviction that there just had to be a simple, one --- well, maybe three --- line proof (there is).
Question (elementary): for p odd prime, show that the order of any element of PGL(2, p) divides some member of {p-1, p, p+1} .
Rider (harder): locate where the @£$%^&* this might be concealed amidst the 330-odd densely obfuscated pages of L. E. Dickson (1901, 1958) "Linear groups with an exposition of the Galois field theory"
Some things were quite definitely not better in the old days!
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Fred, another interesting question: what are the maximal subgroups of PGL_2(GF(p)) (say for p an odd prime)? Hint: besides the Cartan and Borel subgroups, there are a finite collection which is well-known in a different context. Victor On Wed, Mar 20, 2013 at 9:51 PM, Victor S. Miller <victorsmiller@gmail.com>wrote:
Fred, Let F=GF(p^2) as a vector space over GF(p). Let sigma be the matrix which raises an element of F to the p-th power. Every 2 by 2 matrix can be written uniquely as a*sigma + b, where a and b are elements of F. In modern terms you want to show that every element in GL_2 is in a Cartan subgroup -- a conjugate of multiplication by an element of F and its powers, or in a Borel subgroup, which is conjugate to the subgroup of powers of F.
Victor
Sent from my iPhone
On Mar 20, 2013, at 21:19, Fred lunnon <fred.lunnon@gmail.com> wrote:
The following kept me at bay for an embarrassing length of time, despite my conviction that there just had to be a simple, one --- well, maybe three --- line proof (there is).
Question (elementary): for p odd prime, show that the order of any element of PGL(2, p) divides some member of {p-1, p, p+1} .
Rider (harder): locate where the @£$%^&* this might be concealed amidst the 330-odd densely obfuscated pages of L. E. Dickson (1901, 1958) "Linear groups with an exposition of the Galois field theory"
Some things were quite definitely not better in the old days!
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
My favorite is the elliptic subgroup... matrices of the form a b -b a where a^2+b^2 = 1, but where the matrix can't be diagonalized in F_p because the eigenvalues lie in the quadratic extension. I believe there is an exhaustive list of subgroups in COMMENT ON TR01-29: A NOTE ON THE SUBGROUP MEMBERSHIP PROBLEM FOR PSL(2; p) by DENIS XAVIER CHARLES I can send you the .pdf if you like. - Cris On Mar 20, 2013, at 8:17 PM, Victor Miller wrote:
Fred, another interesting question: what are the maximal subgroups of PGL_2(GF(p)) (say for p an odd prime)? Hint: besides the Cartan and Borel subgroups, there are a finite collection which is well-known in a different context.
Victor
On Wed, Mar 20, 2013 at 9:51 PM, Victor S. Miller <victorsmiller@gmail.com>wrote:
Fred, Let F=GF(p^2) as a vector space over GF(p). Let sigma be the matrix which raises an element of F to the p-th power. Every 2 by 2 matrix can be written uniquely as a*sigma + b, where a and b are elements of F. In modern terms you want to show that every element in GL_2 is in a Cartan subgroup -- a conjugate of multiplication by an element of F and its powers, or in a Borel subgroup, which is conjugate to the subgroup of powers of F.
Victor
Sent from my iPhone
On Mar 20, 2013, at 21:19, Fred lunnon <fred.lunnon@gmail.com> wrote:
The following kept me at bay for an embarrassing length of time, despite my conviction that there just had to be a simple, one --- well, maybe three --- line proof (there is).
Question (elementary): for p odd prime, show that the order of any element of PGL(2, p) divides some member of {p-1, p, p+1} .
Rider (harder): locate where the @£$%^&* this might be concealed amidst the 330-odd densely obfuscated pages of L. E. Dickson (1901, 1958) "Linear groups with an exposition of the Galois field theory"
Some things were quite definitely not better in the old days!
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cristopher Moore Professor, Santa Fe Institute The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/
My guess is that Victor's other maximal subgroups have some connection with sporadic simple groups, a topic I have so far managed to avoid. Come to that, every time I think I'm beginning to understand Lie groups, I come a cropper. I can't make head nor tail of the Wikipedia definitions of Cartan and Borel subgroups in the context of finite geometry; even in the more familiar continuous setting, guessing wildly that "Cartan" corresponds to (elliptic) rotation and "Borel" to (parabolic) translation, I am left wondering --- where does does a (hyperbolic) boost roost? In the finite setting |F_q with q = p^k , order dividing q-1, p, q+1 corresponds to hyperbolic, parabolic, elliptic resp. (excepting special cases of identity and involution). Cris's canonical matrix ain't elliptic when p mod 4 = 1 --- discriminant -4 b^2 is a quadratic residue, the roots lie in |F_p , and the projectivity is hyperbolic for b /= 0 . Fred Lunnon On 3/21/13, Cris Moore <moore@santafe.edu> wrote:
My favorite is the elliptic subgroup... matrices of the form
a b -b a
where a^2+b^2 = 1, but where the matrix can't be diagonalized in F_p because the eigenvalues lie in the quadratic extension.
I believe there is an exhaustive list of subgroups in
COMMENT ON TR01-29: A NOTE ON THE SUBGROUP MEMBERSHIP PROBLEM FOR PSL(2; p) by DENIS XAVIER CHARLES
I can send you the .pdf if you like.
- Cris
On Mar 20, 2013, at 8:17 PM, Victor Miller wrote:
Fred, another interesting question: what are the maximal subgroups of PGL_2(GF(p)) (say for p an odd prime)? Hint: besides the Cartan and Borel subgroups, there are a finite collection which is well-known in a different context.
Victor
On Wed, Mar 20, 2013 at 9:51 PM, Victor S. Miller <victorsmiller@gmail.com>wrote:
Fred, Let F=GF(p^2) as a vector space over GF(p). Let sigma be the matrix which raises an element of F to the p-th power. Every 2 by 2 matrix can be written uniquely as a*sigma + b, where a and b are elements of F. In modern terms you want to show that every element in GL_2 is in a Cartan subgroup -- a conjugate of multiplication by an element of F and its powers, or in a Borel subgroup, which is conjugate to the subgroup of powers of F.
Victor
Sent from my iPhone
On Mar 20, 2013, at 21:19, Fred lunnon <fred.lunnon@gmail.com> wrote:
The following kept me at bay for an embarrassing length of time, despite my conviction that there just had to be a simple, one --- well, maybe three --- line proof (there is).
Question (elementary): for p odd prime, show that the order of any element of PGL(2, p) divides some member of {p-1, p, p+1} .
Rider (harder): locate where the @£$%^&* this might be concealed amidst the 330-odd densely obfuscated pages of L. E. Dickson (1901, 1958) "Linear groups with an exposition of the Galois field theory"
Some things were quite definitely not better in the old days!
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cristopher Moore Professor, Santa Fe Institute
The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Fred, The maximal subgroups aren't that obscure :-). Besides the "Cartan" (subgroups conjugate to what you get by multiplying GF(p^2) by a primitive root in that field), and "Borel" matrices conjugate to [[a,b],[0,a]] for some a, b, you can (depending on the congruence class of p) get the rotation groups of the tetrahedron, octahedron or icosahedron. There's a nice elementary proof of this in an old paper: Swinnerton-Dyer, H. "On ℓ-adic representations and congruences for coefficients of modular forms." *Modular functions of one variable III* (1973): 1-55. Incidentally, if you're asking about the maximal orders of elements in SL_2(p) as opposed to PSL_2(p) you need to multiply by 2: for example the matrix [[-1,1],[0,-1]] has order 2p. Victor On Thu, Mar 21, 2013 at 11:56 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
My guess is that Victor's other maximal subgroups have some connection with sporadic simple groups, a topic I have so far managed to avoid.
Come to that, every time I think I'm beginning to understand Lie groups, I come a cropper. I can't make head nor tail of the Wikipedia definitions of Cartan and Borel subgroups in the context of finite geometry; even in the more familiar continuous setting, guessing wildly that "Cartan" corresponds to (elliptic) rotation and "Borel" to (parabolic) translation, I am left wondering --- where does does a (hyperbolic) boost roost?
In the finite setting |F_q with q = p^k , order dividing q-1, p, q+1 corresponds to hyperbolic, parabolic, elliptic resp. (excepting special cases of identity and involution).
Cris's canonical matrix ain't elliptic when p mod 4 = 1 --- discriminant -4 b^2 is a quadratic residue, the roots lie in |F_p , and the projectivity is hyperbolic for b /= 0 .
Fred Lunnon
On 3/21/13, Cris Moore <moore@santafe.edu> wrote:
My favorite is the elliptic subgroup... matrices of the form
a b -b a
where a^2+b^2 = 1, but where the matrix can't be diagonalized in F_p
because
the eigenvalues lie in the quadratic extension.
I believe there is an exhaustive list of subgroups in
COMMENT ON TR01-29: A NOTE ON THE SUBGROUP MEMBERSHIP PROBLEM FOR PSL(2; p) by DENIS XAVIER CHARLES
I can send you the .pdf if you like.
- Cris
On Mar 20, 2013, at 8:17 PM, Victor Miller wrote:
Fred, another interesting question: what are the maximal subgroups of PGL_2(GF(p)) (say for p an odd prime)? Hint: besides the Cartan and Borel subgroups, there are a finite collection which is well-known in a different context.
Victor
On Wed, Mar 20, 2013 at 9:51 PM, Victor S. Miller <victorsmiller@gmail.com>wrote:
Fred, Let F=GF(p^2) as a vector space over GF(p). Let sigma be the matrix which raises an element of F to the p-th power. Every 2 by 2 matrix can be written uniquely as a*sigma + b, where a and b are elements of F. In modern terms you want to show that every element in GL_2 is in a Cartan subgroup -- a conjugate of multiplication by an element of F and its powers, or in a Borel subgroup, which is conjugate to the subgroup of powers of F.
Victor
Sent from my iPhone
On Mar 20, 2013, at 21:19, Fred lunnon <fred.lunnon@gmail.com> wrote:
The following kept me at bay for an embarrassing length of time, despite my conviction that there just had to be a simple, one --- well, maybe three --- line proof (there is).
Question (elementary): for p odd prime, show that the order of any element of PGL(2, p) divides some member of {p-1, p, p+1} .
Rider (harder): locate where the @£$%^&* this might be concealed amidst the 330-odd densely obfuscated pages of L. E. Dickson (1901, 1958) "Linear groups with an exposition of the Galois field theory"
Some things were quite definitely not better in the old days!
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cristopher Moore Professor, Santa Fe Institute
The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Right --- the essential feature which I tend to forget is that, while my application is only meaningful over some "real" field ( |R or |F_p ), this high-falutin' theory only makes sense over some "complex" algebraic extension ( |C or |F_p^2 --- sort of) where rotations and boosts are conjugate, even if they are palpably non-isomorphic for practical purposes. Those polyhedral groups are unexpected if they turn up over |F_p rather than |F_p^k . Fred Lunnon On 3/22/13, Victor Miller <victorsmiller@gmail.com> wrote:
Fred, The maximal subgroups aren't that obscure :-). Besides the "Cartan" (subgroups conjugate to what you get by multiplying GF(p^2) by a primitive root in that field), and "Borel" matrices conjugate to [[a,b],[0,a]] for some a, b, you can (depending on the congruence class of p) get the rotation groups of the tetrahedron, octahedron or icosahedron. There's a nice elementary proof of this in an old paper:
Swinnerton-Dyer, H. "On ℓ-adic representations and congruences for coefficients of modular forms." *Modular functions of one variable III* (1973): 1-55.
Incidentally, if you're asking about the maximal orders of elements in SL_2(p) as opposed to PSL_2(p) you need to multiply by 2: for example the matrix [[-1,1],[0,-1]] has order 2p.
Victor
On Thu, Mar 21, 2013 at 11:56 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
My guess is that Victor's other maximal subgroups have some connection with sporadic simple groups, a topic I have so far managed to avoid.
Come to that, every time I think I'm beginning to understand Lie groups, I come a cropper. I can't make head nor tail of the Wikipedia definitions of Cartan and Borel subgroups in the context of finite geometry; even in the more familiar continuous setting, guessing wildly that "Cartan" corresponds to (elliptic) rotation and "Borel" to (parabolic) translation, I am left wondering --- where does does a (hyperbolic) boost roost?
In the finite setting |F_q with q = p^k , order dividing q-1, p, q+1 corresponds to hyperbolic, parabolic, elliptic resp. (excepting special cases of identity and involution).
Cris's canonical matrix ain't elliptic when p mod 4 = 1 --- discriminant -4 b^2 is a quadratic residue, the roots lie in |F_p , and the projectivity is hyperbolic for b /= 0 .
Fred Lunnon
On 3/21/13, Cris Moore <moore@santafe.edu> wrote:
My favorite is the elliptic subgroup... matrices of the form
a b -b a
where a^2+b^2 = 1, but where the matrix can't be diagonalized in F_p
because
the eigenvalues lie in the quadratic extension.
I believe there is an exhaustive list of subgroups in
COMMENT ON TR01-29: A NOTE ON THE SUBGROUP MEMBERSHIP PROBLEM FOR PSL(2; p) by DENIS XAVIER CHARLES
I can send you the .pdf if you like.
- Cris
On Mar 20, 2013, at 8:17 PM, Victor Miller wrote:
Fred, another interesting question: what are the maximal subgroups of PGL_2(GF(p)) (say for p an odd prime)? Hint: besides the Cartan and Borel subgroups, there are a finite collection which is well-known in a different context.
Victor
On Wed, Mar 20, 2013 at 9:51 PM, Victor S. Miller <victorsmiller@gmail.com>wrote:
Fred, Let F=GF(p^2) as a vector space over GF(p). Let sigma be the matrix which raises an element of F to the p-th power. Every 2 by 2 matrix can be written uniquely as a*sigma + b, where a and b are elements of F. In modern terms you want to show that every element in GL_2 is in a Cartan subgroup -- a conjugate of multiplication by an element of F and its powers, or in a Borel subgroup, which is conjugate to the subgroup of powers of F.
Victor
Sent from my iPhone
On Mar 20, 2013, at 21:19, Fred lunnon <fred.lunnon@gmail.com> wrote:
The following kept me at bay for an embarrassing length of time, despite my conviction that there just had to be a simple, one --- well, maybe three --- line proof (there is).
Question (elementary): for p odd prime, show that the order of any element of PGL(2, p) divides some member of {p-1, p, p+1} .
Rider (harder): locate where the @£$%^&* this might be concealed amidst the 330-odd densely obfuscated pages of L. E. Dickson (1901, 1958) "Linear groups with an exposition of the Galois field theory"
Some things were quite definitely not better in the old days!
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cristopher Moore Professor, Santa Fe Institute
The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Right. The eigenvalues of a b -b a are a +/- b sqrt(-1) . So if -1 has a square root in F_p (i.e. if -1 is a quadratic residue, which happens if p mod 4 = 1) then we can diagonalize this matrix. More generally, I guess one defines "elliptic" matrices as follows. Let g be a fixed non-quadratic residue, i.e. an element of F_p that doesn't have a square root in F_p. Then consider matrices a , b gb , a where a^2 - gb^2 = 1. (Exercise: show these matrices form a subgroup.) Then the eigenvectors are (1, +/- sqrt(g)) and the eigenvalues are a +/- b sqrt(g). Cris On Mar 22, 2013, at 6:27 AM, Victor Miller wrote:
Cris's canonical matrix ain't elliptic when p mod 4 = 1 --- discriminant -4 b^2 is a quadratic residue, the roots lie in |F_p , and the projectivity is hyperbolic for b /= 0 .
participants (4)
-
Cris Moore -
Fred lunnon -
Victor Miller -
Victor S. Miller