Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > sci.math > #313525 > unrolled thread

Is this a generalization of Fermat's Little Theorem?

Back to article view | Back to sci.math

Contents

  Is this a generalization of Fermat's Little Theorem? Robert Delaney <delaneyrm@earthlnk.net> - 2015-08-13 23:20 -0500
    Re: Is this a generalization of Fermat's Little Theorem? Robert Delaney <delaneyrm@earthlnk.net> - 2015-08-13 23:53 -0500
    Re: Is this a generalization of Fermat's Little Theorem? Robert Delaney <delaneyrm@earthlnk.net> - 2015-08-14 00:31 -0500
    Re: Is this a generalization of Fermat's Little Theorem? Simon Roberts <retenshun@twc.com> - 2015-08-14 11:34 -0400
      Re: Is this a generalization of Fermat's Little Theorem? Simon Roberts <retenshun@twc.com> - 2015-08-14 11:52 -0400
        Re: Is this a generalization of Fermat's Little Theorem? quasi <quasi@null.set> - 2015-08-14 15:02 -0400
        Re: Is this a generalization of Fermat's Little Theorem? Simon Roberts <retenshun@twc.com> - 2015-08-14 15:21 -0400
    Re: Is this a generalization of Fermat's Little Theorem? Robert Delaney <delaneyrm@earthlnk.net> - 2015-08-14 15:21 -0500
      Re: Is this a generalization of Fermat's Little Theorem? abu.kuanysh05@gmail.com - 2015-08-15 16:31 -0700
    Re: Is this a generalization of Fermat's Little Theorem? quasi <quasi@null.set> - 2015-08-14 16:42 -0400
      Re: Is this a generalization of Fermat's Little Theorem? Robert Delaney <delaneyrm@earthlnk.net> - 2015-08-14 20:01 -0500
        Re: Is this a generalization of Fermat's Little Theorem? Waldek Hebisch <hebisch@antispam.uni.wroc.pl> - 2015-08-15 18:04 +0000
          Re: Is this a generalization of Fermat's Little Theorem? quasi <quasi@null.set> - 2015-08-15 15:04 -0400
            Re: Is this a generalization of Fermat's Little Theorem? quasi <quasi@null.set> - 2015-08-15 16:41 -0400
              Re: Is this a generalization of Fermat's Little Theorem? quasi <quasi@null.set> - 2015-08-15 17:33 -0400
    Re: Is this a generalization of Fermat's Little Theorem? Simon Roberts <retenshun@twc.com> - 2015-08-15 02:57 -0400
      Re: Is this a generalization of Fermat's Little Theorem? Simon Roberts <retenshun@twc.com> - 2015-08-15 18:43 -0400
    Re: Is this a generalization of Fermat's Little Theorem? Robert Delaney <delaneyrm@earthlnk.net> - 2015-08-15 20:49 -0500
      Re: Is this a generalization of Fermat's Little Theorem? quasi <quasi@null.set> - 2015-08-16 02:59 -0400
        Re: Is this a generalization of Fermat's Little Theorem? Timothy Murphy <gayleard@eircom.net> - 2015-08-16 12:28 +0200
          Re: Is this a generalization of Fermat's Little Theorem? quasi <quasi@null.set> - 2015-08-16 06:32 -0400

Page 1 of 2  [1] 2  Next page →

#313525 — Is this a generalization of Fermat's Little Theorem?

In the thread “An Almost Theorem” on Compuserve²s SciMath forum:

http://forums.compuserve.com/discussions/The_Science_and_Math_Forum/_/_/ws-sciencemath/130471.1 


Alan Listoe proves this theorem for an integer square matrix A of size 
n, prime p, and
integer k:

“A is semisimple over GF(p) if and only if
there is a k such that
A^(p^k) = A (mod p).”

“The problem of finding these domain k's reduces to finding all the
partitions of n, where we interpret the numbers in a partition as the
degrees of the irreducible polynomials. Then the l.c.m. of these
degrees is a k belonging to the minimum domain.”

Here are some examples supporting that theorem. For these examples with 
modulus p I’ll use a complete residue system for p = 2 as (0, 1), p = 3 
as (-1, 0, 1), p = 5 as (-2, -1, 0, 1 ,2), and so on.

Consider matrices of size n = 2. Thus k belongs to (1, 2).

Let
A =
1 2
3 4

For p = 2
A mod p =
1 0
1 0
This matrix can be diagonalized and so is semisimple. It also satisfies
A^2 = A mod p
So k = 1 and the theorem holds.

For p = 3
A mod p =
1 -1
0 1
This can not be diagonalized and its characteristic polynomial is 
reducible, so it is not semisimple.
For k = 1
A^(p^k) = A^p = A^3 mod p =
1 0
0 1
which is not A mod p.
For k = 2
A^(p^k) = A^9 = (A^3)^3 mod p =
1 0
0 1
which is not A mod p.
For k > 2
A^(p^k) = (A^p)^(p^(k-1)) mod p =
1 0
0 1
which is not A mod p for any integer k. Since A mod p is not semisimple 
the theorem holds.

For p = 5
A mod p =
1 2
-2 -1
This matrix cannot be diagonalized over the integers and its 
characteristic polynomial is irreducible over the integers, so it is 
semisimple. So the theorem says there are two possibilities. Either k = 
1 and then the theorem also holds for k = 2, or k = 2. One finds
For k = 1
A^(p^k) = A^p = A^5 mod p =
-1 -2
2 1
which is not A mod p.
For k = 2
A^(p^k) = A^25 mod p =
1 2
-2 -1
which is A mod p, so the theorem holds.

Similar examples hold for higher matrix dimensions. When I see n = 10 
matrices with 100 elements reproduced for many primes with some value 
for k, I am impressed by the power of this theorem.

Given the matrix dimension n here are the possible values for k:

n: (minimum domain for k)
1 (1) (Fermat's Little Theorem)
2 (1, 2)
3 (1, 2, 3)
4 (1, 2, 3, 4)
5 (1, 2, 3, 4, 5, 6)
6 (1, 2, 3, 4, 5, 6)
7 (1, 2, 3, 4, 5, 6, 7, 10, 12)
8 (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15)
9 (2, 3, 4, 5, 6, 7, 8, 9. 10, 12, 14, 15, 20)
10 (2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 20, 21, 30)
11 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30)
12 (3, 4, 5, 6, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30, 35,42, 60)
13 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30,35, 42, 60)
14 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 24,28, 
30, 33, 35, 36, 40, 42, 45, 60, 70, 84)
15 (4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 24, 
26,28, 30, 33, 35, 36, 40, 42, 44, 45, 56, 60, 70, 84, 105)

Can anyone find a counter-example to Listoe’s theorem?

Bob

[toc] | [next] | [standalone]

#313526

On 2015-08-14 04:20:29 +0000, Robert Delaney said:

> In the thread “An Almost Theorem” on Compuserve²s SciMath forum:
> 
> http://forums.compuserve.com/discussions/The_Science_and_Math_Forum/_/_/ws-sciencemath/130471.1 
> 
> 
> Alan Listoe proves this theorem for an integer square matrix A of size 
> n, prime p, and
> integer k:
> 
> “A is semisimple over GF(p) if and only if
> there is a k such that
> A^(p^k) = A (mod p).”
> 
> “The problem of finding these domain k's reduces to finding all the
> partitions of n, where we interpret the numbers in a partition as the
> degrees of the irreducible polynomials. Then the l.c.m. of these
> degrees is a k belonging to the minimum domain.”
> 
> Here are some examples supporting that theorem. For these examples with 
> modulus p I’ll use a complete residue system for p = 2 as (0, 1), p = 3 
> as (-1, 0, 1), p = 5 as (-2, -1, 0, 1 ,2), and so on.
> 
> Consider matrices of size n = 2. Thus k belongs to (1, 2).
> 
> Let
> A =
> 1 2
> 3 4
> 
> For p = 2
> A mod p =
> 1 0
> 1 0
> This matrix can be diagonalized and so is semisimple. It also satisfies
> A^2 = A mod p
> So k = 1 and the theorem holds.
> 
> For p = 3
> A mod p =
> 1 -1
> 0 1
> This can not be diagonalized and its characteristic polynomial is 
> reducible, so it is not semisimple.
> For k = 1
> A^(p^k) = A^p = A^3 mod p =
> 1 0
> 0 1
> which is not A mod p.
> For k = 2
> A^(p^k) = A^9 = (A^3)^3 mod p =
> 1 0
> 0 1
> which is not A mod p.
> For k > 2
> A^(p^k) = (A^p)^(p^(k-1)) mod p =
> 1 0
> 0 1
> which is not A mod p for any integer k. Since A mod p is not semisimple 
> the theorem holds.
> 
> For p = 5
> A mod p =
> 1 2
> -2 -1
> This matrix cannot be diagonalized over the integers and its 
> characteristic polynomial is irreducible over the integers, so it is 
> semisimple. So the theorem says there are two possibilities. Either k = 
> 1 and then the theorem also holds for k = 2, or k = 2. One finds
> For k = 1
> A^(p^k) = A^p = A^5 mod p =
> -1 -2
> 2 1
> which is not A mod p.
> For k = 2
> A^(p^k) = A^25 mod p =
> 1 2
> -2 -1
> which is A mod p, so the theorem holds.
> 
> Similar examples hold for higher matrix dimensions. When I see n = 10 
> matrices with 100 elements reproduced for many primes with some value 
> for k, I am impressed by the power of this theorem.
> 
> Given the matrix dimension n here are the possible values for k:
> 
> n: (minimum domain for k)
> 1 (1) (Fermat's Little Theorem)
> 2 (1, 2)
> 3 (1, 2, 3)
> 4 (1, 2, 3, 4)
> 5 (1, 2, 3, 4, 5, 6)
> 6 (1, 2, 3, 4, 5, 6)
> 7 (1, 2, 3, 4, 5, 6, 7, 10, 12)
> 8 (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15)
> 9 (2, 3, 4, 5, 6, 7, 8, 9. 10, 12, 14, 15, 20)
> 10 (2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 20, 21, 30)
> 11 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30)
> 12 (3, 4, 5, 6, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30, 35,42, 60)
> 13 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30,35, 42, 60)
> 14 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 24,28, 
> 30, 33, 35, 36, 40, 42, 45, 60, 70, 84)
> 15 (4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 24, 
> 26,28, 30, 33, 35, 36, 40, 42, 44, 45, 56, 60, 70, 84, 105)
> 
> Can anyone find a counter-example to Listoe’s theorem?
> 
> Bob

Sorry, that list of k values was found by trial and error (lots of work 
there!). The computed values do have all the missing lowest values 1, 
2, ... . They occur rarely as n gets larger. And they do agree with the 
obsrved values. It's late so I'll post the computed values of k later.

Bob

[toc] | [prev] | [next] | [standalone]

#313528

I stayed up late. Here's the computed k list.


n: (minimum domain for k)
1 (1) (Fermat's Little Theorem)
2 (1, 2)
3 (1, 2, 3)
4 (1, 2, 3, 4)
5 (1, 2, 3, 4, 5, 6)
6 (1, 2, 3, 4, 5, 6)
7 (1, 2, 3, 4, 5, 6, 7, 10, 12)
8 (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15)
9 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 20)
10 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 20, 21, 30)
11 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30)
12 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 
30, 35, 42, 60)
13 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 
24, 28, 30, 35, 36, 40, 42, 60)
14 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 
24, 28, 30, 33, 35, 36, 40, 42, 45, 60, 70, 84)
15 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 
24, 26, 28, 30, 33, 35, 36, 40, 42, 44, 45, 56, 60, 70, 84, 105)

Bob

[toc] | [prev] | [next] | [standalone]

#313542

On Thu, 13 Aug 2015 23:20:29 -0500, Robert Delaney
<delaneyrm@earthlnk.net> wrote:

>In the thread “An Almost Theorem” on Compuserve²s SciMath forum:
>
>http://forums.compuserve.com/discussions/The_Science_and_Math_Forum/_/_/ws-sciencemath/130471.1 
>
>
>Alan Listoe proves this theorem for an integer square matrix A of size 
>n, prime p, and
>integer k:
>
>“A is semisimple over GF(p) if and only if
>there is a k such that
>A^(p^k) = A (mod p).”

A^(p^k) = A^([(p-1) + 1]^k} = (binomial expansion) =  
A^((p-1)Q + 1) = A^(p-1)Q * A = A (mod p) Q is an integer

>
>“The problem of finding these domain k's reduces to finding all the
>partitions of n, where we interpret the numbers in a partition as the
>degrees of the irreducible polynomials. Then the l.c.m. of these
>degrees is a k belonging to the minimum domain.”
>
>Here are some examples supporting that theorem. For these examples with 
>modulus p I’ll use a complete residue system for p = 2 as (0, 1), p = 3 
>as (-1, 0, 1), p = 5 as (-2, -1, 0, 1 ,2), and so on.
>
>Consider matrices of size n = 2. Thus k belongs to (1, 2).
>
>Let
>A =
>1 2
>3 4
>
>For p = 2
>A mod p =
>1 0
>1 0
>This matrix can be diagonalized and so is semisimple. It also satisfies
>A^2 = A mod p
>So k = 1 and the theorem holds.
>
>For p = 3
>A mod p =
>1 -1
>0 1
>This can not be diagonalized and its characteristic polynomial is 
>reducible, so it is not semisimple.
>For k = 1
>A^(p^k) = A^p = A^3 mod p =
>1 0
>0 1
>which is not A mod p.
>For k = 2
>A^(p^k) = A^9 = (A^3)^3 mod p =
>1 0
>0 1
>which is not A mod p.
>For k > 2
>A^(p^k) = (A^p)^(p^(k-1)) mod p =
>1 0
>0 1
>which is not A mod p for any integer k. Since A mod p is not semisimple 
>the theorem holds.
>
>For p = 5
>A mod p =
>1 2
>-2 -1
>This matrix cannot be diagonalized over the integers and its 
>characteristic polynomial is irreducible over the integers, so it is 
>semisimple. So the theorem says there are two possibilities. Either k = 
>1 and then the theorem also holds for k = 2, or k = 2. One finds
>For k = 1
>A^(p^k) = A^p = A^5 mod p =
>-1 -2
>2 1
>which is not A mod p.
>For k = 2
>A^(p^k) = A^25 mod p =
>1 2
>-2 -1
>which is A mod p, so the theorem holds.
>
>Similar examples hold for higher matrix dimensions. When I see n = 10 
>matrices with 100 elements reproduced for many primes with some value 
>for k, I am impressed by the power of this theorem.
>
>Given the matrix dimension n here are the possible values for k:
>
>n: (minimum domain for k)
>1 (1) (Fermat's Little Theorem)
>2 (1, 2)
>3 (1, 2, 3)
>4 (1, 2, 3, 4)
>5 (1, 2, 3, 4, 5, 6)
>6 (1, 2, 3, 4, 5, 6)
>7 (1, 2, 3, 4, 5, 6, 7, 10, 12)
>8 (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15)
>9 (2, 3, 4, 5, 6, 7, 8, 9. 10, 12, 14, 15, 20)
>10 (2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 20, 21, 30)
>11 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30)
>12 (3, 4, 5, 6, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30, 35,42, 60)
>13 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30,35, 42, 60)
>14 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 24,28, 
>30, 33, 35, 36, 40, 42, 45, 60, 70, 84)
>15 (4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 24, 
>26,28, 30, 33, 35, 36, 40, 42, 44, 45, 56, 60, 70, 84, 105)
>
>Can anyone find a counter-example to Listoe’s theorem?
>
>Bob

[toc] | [prev] | [next] | [standalone]

#313545

On Fri, 14 Aug 2015 11:34:42 -0400, Simon Roberts <retenshun@twc.com>
wrote:

>On Thu, 13 Aug 2015 23:20:29 -0500, Robert Delaney
><delaneyrm@earthlnk.net> wrote:
>
>>In the thread “An Almost Theorem” on Compuserve²s SciMath forum:
>>
>>http://forums.compuserve.com/discussions/The_Science_and_Math_Forum/_/_/ws-sciencemath/130471.1 
>>
>>
>>Alan Listoe proves this theorem for an integer square matrix A of size 
>>n, prime p, and
>>integer k:
>>
>>“A is semisimple over GF(p) if and only if
>>there is a k such that
>>A^(p^k) = A (mod p).”
>
>A^(p^k) = A^([(p-1) + 1]^k} = (binomial expansion) =  
>A^((p-1)Q + 1) = A^(p-1)Q * A = A (mod p) Q is an integer
>
A^(p^k) = A^([(p-1) + 1]^k) = (binomial expansion)  
A^((p-1)Q + 1) = AA^[(p-1)Q ] = A (mod p)  (Q is an integer)


>>
>>“The problem of finding these domain k's reduces to finding all the
>>partitions of n, where we interpret the numbers in a partition as the
>>degrees of the irreducible polynomials. Then the l.c.m. of these
>>degrees is a k belonging to the minimum domain.”
>>
>>Here are some examples supporting that theorem. For these examples with 
>>modulus p I’ll use a complete residue system for p = 2 as (0, 1), p = 3 
>>as (-1, 0, 1), p = 5 as (-2, -1, 0, 1 ,2), and so on.
>>
>>Consider matrices of size n = 2. Thus k belongs to (1, 2).
>>
>>Let
>>A =
>>1 2
>>3 4
>>
>>For p = 2
>>A mod p =
>>1 0
>>1 0
>>This matrix can be diagonalized and so is semisimple. It also satisfies
>>A^2 = A mod p
>>So k = 1 and the theorem holds.
>>
>>For p = 3
>>A mod p =
>>1 -1
>>0 1
>>This can not be diagonalized and its characteristic polynomial is 
>>reducible, so it is not semisimple.
>>For k = 1
>>A^(p^k) = A^p = A^3 mod p =
>>1 0
>>0 1
>>which is not A mod p.
>>For k = 2
>>A^(p^k) = A^9 = (A^3)^3 mod p =
>>1 0
>>0 1
>>which is not A mod p.
>>For k > 2
>>A^(p^k) = (A^p)^(p^(k-1)) mod p =
>>1 0
>>0 1
>>which is not A mod p for any integer k. Since A mod p is not semisimple 
>>the theorem holds.
>>
>>For p = 5
>>A mod p =
>>1 2
>>-2 -1
>>This matrix cannot be diagonalized over the integers and its 
>>characteristic polynomial is irreducible over the integers, so it is 
>>semisimple. So the theorem says there are two possibilities. Either k = 
>>1 and then the theorem also holds for k = 2, or k = 2. One finds
>>For k = 1
>>A^(p^k) = A^p = A^5 mod p =
>>-1 -2
>>2 1
>>which is not A mod p.
>>For k = 2
>>A^(p^k) = A^25 mod p =
>>1 2
>>-2 -1
>>which is A mod p, so the theorem holds.
>>
>>Similar examples hold for higher matrix dimensions. When I see n = 10 
>>matrices with 100 elements reproduced for many primes with some value 
>>for k, I am impressed by the power of this theorem.
>>
>>Given the matrix dimension n here are the possible values for k:
>>
>>n: (minimum domain for k)
>>1 (1) (Fermat's Little Theorem)
>>2 (1, 2)
>>3 (1, 2, 3)
>>4 (1, 2, 3, 4)
>>5 (1, 2, 3, 4, 5, 6)
>>6 (1, 2, 3, 4, 5, 6)
>>7 (1, 2, 3, 4, 5, 6, 7, 10, 12)
>>8 (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15)
>>9 (2, 3, 4, 5, 6, 7, 8, 9. 10, 12, 14, 15, 20)
>>10 (2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 20, 21, 30)
>>11 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30)
>>12 (3, 4, 5, 6, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30, 35,42, 60)
>>13 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30,35, 42, 60)
>>14 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 24,28, 
>>30, 33, 35, 36, 40, 42, 45, 60, 70, 84)
>>15 (4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 24, 
>>26,28, 30, 33, 35, 36, 40, 42, 44, 45, 56, 60, 70, 84, 105)
>>
>>Can anyone find a counter-example to Listoe’s theorem?
>>
>>Bob

[toc] | [prev] | [next] | [standalone]

#313556

Simon Roberts wrote:
>Simon Roberts wrote:
>>Robert Delaney wrote:
>>>
>>>In the thread “An Almost Theorem” on Compuserve²s SciMath forum:
>>>
>>>http://forums.compuserve.com/discussions/The_Science_and_Math_Forum/_/_/ws-sciencemath/130471.1 
>>>
>>>Alan Listoe proves this theorem for an integer square 
>>>matrix A of size n, prime p, and integer k:
>>>
>>>“A is semisimple over GF(p) if and only if there is a k such 
>>>that A^(p^k) = A (mod p).”
>>
>>A^(p^k) = A^([(p-1) + 1]^k} = (binomial expansion) =  
>>A^((p-1)Q + 1) = A^(p-1)Q * A = A (mod p) Q is an integer
>
>A^(p^k) = A^([(p-1) + 1]^k) = (binomial expansion)  
>A^((p-1)Q + 1) = AA^[(p-1)Q ] = A (mod p)  (Q is an integer)

In this problem, the symbol A is not an integer -- it's an 
n x n matrix with integer components, so your "simplification"
AA^[(p-1)Q ] = A (mod p) is not a valid simplification.

quasi

[toc] | [prev] | [next] | [standalone]

#313557

>>>Alan Listoe proves this theorem for an integer square matrix A of size 
>>>n, prime p, and
>>>integer k:
>>>
>>>“A is semisimple over GF(p) if and only if
>>>there is a k such that
>>>A^(p^k) = A (mod p).”
>>
>>A^(p^k) = A^([(p-1) + 1]^k} = (binomial expansion) =  
>>A^((p-1)Q + 1) = A^(p-1)Q * A = A (mod p) Q is an integer
>>
>A^(p^k) = A^([(p-1) + 1]^k) = (binomial expansion)  
>A^((p-1)Q + 1) = AA^[(p-1)Q ] = A (mod p)  (Q is an integer)

I apologise. You were talking about a square matrix, A. Over my head.
I Hope you may find this helpful anyway.

>>>
>>>Bob

[toc] | [prev] | [next] | [standalone]

#313559

On 2015-08-14 04:20:29 +0000, Robert Delaney said:

> In the thread “An Almost Theorem” on Compuserve²s SciMath forum:
> 
> http://forums.compuserve.com/discussions/The_Science_and_Math_Forum/_/_/ws-sciencemath/130471.1 
> 
> 
> Alan Listoe proves this theorem for an integer square matrix A of size 
> n, prime p, and
> integer k:
> 
> “A is semisimple over GF(p) if and only if
> there is a k such that
> A^(p^k) = A (mod p).”
> 
> “The problem of finding these domain k's reduces to finding all the
> partitions of n, where we interpret the numbers in a partition as the
> degrees of the irreducible polynomials. Then the l.c.m. of these
> degrees is a k belonging to the minimum domain.”
> 
> Here are some examples supporting that theorem. For these examples with 
> modulus p I’ll use a complete residue system for p = 2 as (0, 1), p = 3 
> as (-1, 0, 1), p = 5 as (-2, -1, 0, 1 ,2), and so on.
> 
> Consider matrices of size n = 2. Thus k belongs to (1, 2).
> 
> Let
> A =
> 1 2
> 3 4
> 
> For p = 2
> A mod p =
> 1 0
> 1 0
> This matrix can be diagonalized and so is semisimple. It also satisfies
> A^2 = A mod p
> So k = 1 and the theorem holds.
> 
> For p = 3
> A mod p =
> 1 -1
> 0 1
> This can not be diagonalized and its characteristic polynomial is 
> reducible, so it is not semisimple.
> For k = 1
> A^(p^k) = A^p = A^3 mod p =
> 1 0
> 0 1
> which is not A mod p.
> For k = 2
> A^(p^k) = A^9 = (A^3)^3 mod p =
> 1 0
> 0 1
> which is not A mod p.
> For k > 2
> A^(p^k) = (A^p)^(p^(k-1)) mod p =
> 1 0
> 0 1
> which is not A mod p for any integer k. Since A mod p is not semisimple 
> the theorem holds.
> 
> For p = 5
> A mod p =
> 1 2
> -2 -1
> This matrix cannot be diagonalized over the integers and its 
> characteristic polynomial is irreducible over the integers, so it is 
> semisimple. So the theorem says there are two possibilities. Either k = 
> 1 and then the theorem also holds for k = 2, or k = 2. One finds
> For k = 1
> A^(p^k) = A^p = A^5 mod p =
> -1 -2
> 2 1
> which is not A mod p.
> For k = 2
> A^(p^k) = A^25 mod p =
> 1 2
> -2 -1
> which is A mod p, so the theorem holds.
> 
> Similar examples hold for higher matrix dimensions. When I see n = 10 
> matrices with 100 elements reproduced for many primes with some value 
> for k, I am impressed by the power of this theorem.
> 
> Given the matrix dimension n here are the possible values for k:
> 
> n: (minimum domain for k)
> 1 (1) (Fermat's Little Theorem)
> 2 (1, 2)
> 3 (1, 2, 3)
> 4 (1, 2, 3, 4)
> 5 (1, 2, 3, 4, 5, 6)
> 6 (1, 2, 3, 4, 5, 6)
> 7 (1, 2, 3, 4, 5, 6, 7, 10, 12)
> 8 (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15)
> 9 (2, 3, 4, 5, 6, 7, 8, 9. 10, 12, 14, 15, 20)
> 10 (2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 20, 21, 30)
> 11 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30)
> 12 (3, 4, 5, 6, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30, 35,42, 60)
> 13 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30,35, 42, 60)
> 14 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 24,28, 
> 30, 33, 35, 36, 40, 42, 45, 60, 70, 84)
> 15 (4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 24, 
> 26,28, 30, 33, 35, 36, 40, 42, 44, 45, 56, 60, 70, 84, 105)
> 
> Can anyone find a counter-example to Listoe’s theorem?
> 
> Bob

n: (minimum domain for k)
1 (1) (Fermat's Little Theorem)

was too cryptic. Consider the  one-dimensional (n = 1) matrix A whose 
sole element is integer a. A is clearly semisimple, so Listoe’s Theorem 
holds with k = 1. Therefore

A^p = A mod p

which implies

a^p = a mod p

for any integer a and any prime p, which is Fermat’s Little Theorem. 
This is why I regard Listoe’s Theorem a generalization of Fermat’s 
Little Theorem.

Bob

[toc] | [prev] | [next] | [standalone]

#313659

well, more to lOOk at, later

> n: (minimum domain for k)
> 1 (1) (Fermat's Little Theorem)
> 
> was too cryptic. Consider the  one-dimensional (n = 1) matrix A whose 
> sole element is integer a. A is clearly semisimple, so Listoe's Theorem 
> holds with k = 1. Therefore
> 
> A^p = A mod p
> 
> which implies
> 
> a^p = a mod p
> 
> for any integer a and any prime p, which is Fermat's Little Theorem. 
> This is why I regard Listoe's Theorem a generalization of Fermat's 
> Little Theorem.
> 
> Bob

[toc] | [prev] | [next] | [standalone]

#313563

Robert Delaney wrote:
>
>In the thread “An Almost Theorem” on Compuserve²s SciMath forum:
>
>http://forums.compuserve.com/discussions/The_Science_and_Math_Forum/_/_/ws-sciencemath/130471.1 
>
>Alan Listoe proves this theorem for an integer square matrix A 
>of size n, prime p, and integer k:
>
>“A is semisimple over GF(p) if and only if there is a k such 
>that A^(p^k) = A (mod p).”

I don't think it's true.

Let n = 2, p = 3, A = [[0,-1],[1,-1]].

Then A is semisimple, but A^3 = I, hence there are no integers
k such that A^(p^k) = A (mod p).

quasi

[toc] | [prev] | [next] | [standalone]

#313580

On 2015-08-14 20:42:40 +0000, quasi said:

> Robert Delaney wrote:
>> 
>> In the thread “An Almost Theorem” on Compuserve²s SciMath forum:
>> 
>> http://forums.compuserve.com/discussions/The_Science_and_Math_Forum/_/_/ws-sciencemath/130471.1 
>> 
>> 
>> Alan Listoe proves this theorem for an integer square matrix A
>> of size n, prime p, and integer k:
>> 
>> “A is semisimple over GF(p) if and only if there is a k such
>> that A^(p^k) = A (mod p).”
> 
> I don't think it's true.
> 
> Let n = 2, p = 3, A = [[0,-1],[1,-1]].
> 
> Then A is semisimple, but A^3 = I, hence there are no integers
> k such that A^(p^k) = A (mod p).
> 
> quasi

Agreed. The theorem is not true.

Bob

[toc] | [prev] | [next] | [standalone]

#313619

Robert Delaney <delaneyrm@earthlnk.net> wrote:
> On 2015-08-14 20:42:40 +0000, quasi said:
> 
> > Robert Delaney wrote:
> >> 
> >> In the thread ?An Almost Theorem? on Compuserve?s SciMath forum:
> >> 
> >> http://forums.compuserve.com/discussions/The_Science_and_Math_Forum/_/_/ws-sciencemath/130471.1 
> >> 
> >> 
> >> Alan Listoe proves this theorem for an integer square matrix A
> >> of size n, prime p, and integer k:
> >> 
> >> ?A is semisimple over GF(p) if and only if there is a k such
> >> that A^(p^k) = A (mod p).?
> > 
> > I don't think it's true.
> > 
> > Let n = 2, p = 3, A = [[0,-1],[1,-1]].
> > 
> > Then A is semisimple, but A^3 = I, hence there are no integers
> > k such that A^(p^k) = A (mod p).
> > 
> > quasi
> 
> Agreed. The theorem is not true.

Hmm, let B = [[2,0], [1, 1]], then

B^(-1)AB = [[1, 1], [0, 1]] mod 3

I would say that under any reasonable definition A mod 3 is
_not_ semisimple.
 
-- 
                              Waldek Hebisch
hebisch@antispam.uni.wroc.pl 

[toc] | [prev] | [next] | [standalone]

#313626

Waldek Hebisch wrote:
>Robert Delaney wrote:
>>quasi said:
>>>Robert Delaney wrote:
>>>> 
>>>>In the thread "An Almost Theorem" on Compuserve's SciMath forum:
>>>> 
>>>>http://forums.compuserve.com/discussions/The_Science_and_Math_Forum/_/_/ws-sciencemath/130471.1 
>>>> 
>>>>Alan Listoe proves this theorem for an integer square matrix A
>>>>of size n, prime p, and integer k:
>>>> 
>>>>"A is semisimple over GF(p) if and only if there is a k such
>>>>that A^(p^k) = A (mod p)."
>>> 
>>>I don't think it's true.
>>> 
>>>Let n = 2, p = 3, A = [[0,-1],[1,-1]].
>>> 
>>>Then A is semisimple, but A^3 = I, hence there are no integers
>>>k such that A^(p^k) = A (mod p).
>> 
>>Agreed. The theorem is not true.
>
>Hmm, let B = [[2,0], [1, 1]], then
>
>B^(-1)AB = [[1, 1], [0, 1]] mod 3
>
>I would say that under any reasonable definition A mod 3 
>is _not_ semisimple.

Right -- A is semisimple over Q, but not semisimple mod 3.

I missed that.

Then in fact, Listoe's theorem is true. The proof is not hard.

quasi

[toc] | [prev] | [next] | [standalone]

#313636

quasi wrote:
>Waldek Hebisch wrote:
>>Robert Delaney wrote:
>>>quasi said:
>>>>Robert Delaney wrote:
>>>>> 
>>>>>In the thread "An Almost Theorem" on Compuserve's SciMath forum:
>>>>> 
>>>>>http://forums.compuserve.com/discussions/The_Science_and_Math_Forum/_/_/ws-sciencemath/130471.1 
>>>>> 
>>>>>Alan Listoe proves this theorem for an integer square matrix A
>>>>>of size n, prime p, and integer k:
>>>>> 
>>>>>"A is semisimple over GF(p) if and only if there is a k such
>>>>>that A^(p^k) = A (mod p)."
>>>> 
>>>>I don't think it's true.
>>>> 
>>>>Let n = 2, p = 3, A = [[0,-1],[1,-1]].
>>>> 
>>>>Then A is semisimple, but A^3 = I, hence there are no integers
>>>>k such that A^(p^k) = A (mod p).
>>> 
>>>Agreed. The theorem is not true.
>>
>>Hmm, let B = [[2,0], [1, 1]], then
>>
>>B^(-1)AB = [[1, 1], [0, 1]] mod 3
>>
>>I would say that under any reasonable definition A mod 3 
>>is _not_ semisimple.
>
>Right -- A is semisimple over Q, but not semisimple mod 3.
>
>I missed that.
>
>Then in fact, Listoe's theorem is true. The proof is not hard.

Actually, my proof is for the case where A is nonsingular.

In other words, my "not hard" proof is for the following 
special case of Listoe's Theorem ...

Proposition:

Let p be a prime. If A is an n x n integer matrix such that 
det(A) != 0, there exists a positive integer k such that 
A^(p^k) = A (mod p) iff A is semisimple mod p.

I'll omit the proof for now.

I'll have to think about the singular case.

quasi

[toc] | [prev] | [next] | [standalone]

#313644

quasi wrote:
>quasi wrote:
>>Waldek Hebisch wrote:
>>>Robert Delaney wrote:
>>>>quasi said:
>>>>>Robert Delaney wrote:
>>>>>> 
>>>>>>In the thread "An Almost Theorem" on Compuserve's SciMath forum:
>>>>>> 
>>>>>>http://forums.compuserve.com/discussions/The_Science_and_Math_Forum/_/_/ws-sciencemath/130471.1 
>>>>>> 
>>>>>>Alan Listoe proves this theorem for an integer square matrix A
>>>>>>of size n, prime p, and integer k:
>>>>>> 
>>>>>>"A is semisimple over GF(p) if and only if there is a k such
>>>>>>that A^(p^k) = A (mod p)."
>>>>> 
>>>>>I don't think it's true.
>>>>> 
>>>>>Let n = 2, p = 3, A = [[0,-1],[1,-1]].
>>>>> 
>>>>>Then A is semisimple, but A^3 = I, hence there are no integers
>>>>>k such that A^(p^k) = A (mod p).
>>>> 
>>>>Agreed. The theorem is not true.
>>>
>>>Hmm, let B = [[2,0], [1, 1]], then
>>>
>>>B^(-1)AB = [[1, 1], [0, 1]] mod 3
>>>
>>>I would say that under any reasonable definition A mod 3 
>>>is _not_ semisimple.
>>
>>Right -- A is semisimple over Q, but not semisimple mod 3.
>>
>>I missed that.
>>
>>Then in fact, Listoe's theorem is true. The proof is not hard.
>
>Actually, my proof is for the case where A is nonsingular.
>
>In other words, my "not hard" proof is for the following 
>special case of Listoe's Theorem ...
>
>Proposition:
>
>Let p be a prime. If A is an n x n integer matrix such that 
>det(A) != 0, there exists a positive integer k such that 
>A^(p^k) = A (mod p) iff A is semisimple mod p.
>
>I'll omit the proof for now.
>
>I'll have to think about the singular case.

I see now how to handle both cases at once.

I'm a little low on time now, but I'll post my proof either
later tonight or tomorrow (if the proof still works then).

quasi

[toc] | [prev] | [next] | [standalone]

#313591

If A is semi simple and A is reduced to the diagonal matrix B then,

B^(p^k) = B (mod p) for all k.  This may be obvious.

det(A^(p^k)) = det(A) (mod p) if A is semi simple.



If A is not semi simple:

det(A^(p^k)) = [det(A)]^(p^k)  = det(A) (mod p),

for all k.

This may be obvious as well.

I can't tell if A is reduced to B:

B^(p^k) =B (mod p) for some k.

I would guess not. 

[toc] | [prev] | [next] | [standalone]

#313655

On Sat, 15 Aug 2015 02:57:21 -0400, Simon Roberts <retenshun@twc.com>
wrote:

>If A is semi simple and A is reduced to the diagonal matrix B then,
>
>B^(p^k) = B (mod p) for all k.  This may be obvious.
>
>det(A^(p^k)) = det(A) (mod p) if A is semi simple.
>
>
>
>If A is not semi simple:
>
>det(A^(p^k)) = [det(A)]^(p^k)  = det(A) (mod p),
>
>for all k.
>
>This may be obvious as well.
>
>I can't tell if A is reduced to B:

reduced is the wrong word since A is irriducable. 

>

What is a non semisimple martix called? 

>B^(p^k) =B (mod p) for some k.
>
>I would guess not. 

I hope this helped.

[toc] | [prev] | [next] | [standalone]

#313674

On 2015-08-14 04:20:29 +0000, Robert Delaney said:

> In the thread “An Almost Theorem” on Compuserve²s SciMath forum:
> 
> http://forums.compuserve.com/discussions/The_Science_and_Math_Forum/_/_/ws-sciencemath/130471.1 
> 
> 
> Alan Listoe proves this theorem for an integer square matrix A of size 
> n, prime p, and
> integer k:
> 
> “A is semisimple over GF(p) if and only if
> there is a k such that
> A^(p^k) = A (mod p).”
> 
> “The problem of finding these domain k's reduces to finding all the
> partitions of n, where we interpret the numbers in a partition as the
> degrees of the irreducible polynomials. Then the l.c.m. of these
> degrees is a k belonging to the minimum domain.”
> 
> Here are some examples supporting that theorem. For these examples with 
> modulus p I’ll use a complete residue system for p = 2 as (0, 1), p = 3 
> as (-1, 0, 1), p = 5 as (-2, -1, 0, 1 ,2), and so on.
> 
> Consider matrices of size n = 2. Thus k belongs to (1, 2).
> 
> Let
> A =
> 1 2
> 3 4
> 
> For p = 2
> A mod p =
> 1 0
> 1 0
> This matrix can be diagonalized and so is semisimple. It also satisfies
> A^2 = A mod p
> So k = 1 and the theorem holds.
> 
> For p = 3
> A mod p =
> 1 -1
> 0 1
> This can not be diagonalized and its characteristic polynomial is 
> reducible, so it is not semisimple.
> For k = 1
> A^(p^k) = A^p = A^3 mod p =
> 1 0
> 0 1
> which is not A mod p.
> For k = 2
> A^(p^k) = A^9 = (A^3)^3 mod p =
> 1 0
> 0 1
> which is not A mod p.
> For k > 2
> A^(p^k) = (A^p)^(p^(k-1)) mod p =
> 1 0
> 0 1
> which is not A mod p for any integer k. Since A mod p is not semisimple 
> the theorem holds.
> 
> For p = 5
> A mod p =
> 1 2
> -2 -1
> This matrix cannot be diagonalized over the integers and its 
> characteristic polynomial is irreducible over the integers, so it is 
> semisimple. So the theorem says there are two possibilities. Either k = 
> 1 and then the theorem also holds for k = 2, or k = 2. One finds
> For k = 1
> A^(p^k) = A^p = A^5 mod p =
> -1 -2
> 2 1
> which is not A mod p.
> For k = 2
> A^(p^k) = A^25 mod p =
> 1 2
> -2 -1
> which is A mod p, so the theorem holds.
> 
> Similar examples hold for higher matrix dimensions. When I see n = 10 
> matrices with 100 elements reproduced for many primes with some value 
> for k, I am impressed by the power of this theorem.
> 
> Given the matrix dimension n here are the possible values for k:
> 
> n: (minimum domain for k)
> 1 (1) (Fermat's Little Theorem)
> 2 (1, 2)
> 3 (1, 2, 3)
> 4 (1, 2, 3, 4)
> 5 (1, 2, 3, 4, 5, 6)
> 6 (1, 2, 3, 4, 5, 6)
> 7 (1, 2, 3, 4, 5, 6, 7, 10, 12)
> 8 (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15)
> 9 (2, 3, 4, 5, 6, 7, 8, 9. 10, 12, 14, 15, 20)
> 10 (2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 20, 21, 30)
> 11 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30)
> 12 (3, 4, 5, 6, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30, 35,42, 60)
> 13 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30,35, 42, 60)
> 14 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 24,28, 
> 30, 33, 35, 36, 40, 42, 45, 60, 70, 84)
> 15 (4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 24, 
> 26,28, 30, 33, 35, 36, 40, 42, 44, 45, 56, 60, 70, 84, 105)
> 
> Can anyone find a counter-example to Listoe’s theorem?
> 
> Bob

From the thread on CompuServe:

Message 35 contains Alan Listoe’s proof:

“Yes. I don't know how to prove the equivalence of the different
definitions of "semisimple matrix". But if you accept the "minimal
polynomial is squarefree" definition (I found it on the Wikipedia page
for Semisimple), then this "necessary" part is not hard.

For, if some k exists such that A^(p^k) = A (mod p), then the matrix
A(mod p) over GF(p) satisfies the polynomial over GF(p),
X^(p^k)-X. Therefore the minimal polynomial of A(mod p) is a divisor of
X^(p^k)-X.
But as X^(p^k)-X has no repeated factors, the minimal polynomial also
has no repeated factors. That is to say, A(mod p) is semisimple.

I proved the "sufficient" part in an earlier message, but I will
summarize it here:
Suppose A(mod p) is semisimple. Let M(X) be the minimal polynomial over
GF(p) of A(mod p). Then M has no repeated factors. Let k be the l.c.m.
of the degrees of the irreducible factors of M. Then each factor of M
has degree dividing k, therefore each factor of M divides X^(p^k)-X.
And as M has no repeated factors, M divides X^(p^k)-X. Therefore A(mod
p) satisfies the equation X^(p^k)-X=0, that is
A^(p^k) = A (mod p).

Putting Necessary and Sufficient together, we have:

A is semisimple over GF(p) if and only if
there is a k such that
A^(p^k) = A (mod p).”

In Message 37, where n is the size of square matrix A:

“The problem of finding these domain k's reduces to finding all the
partitions of n, where we interpret the numbers in a partition as the
degrees of the irreducible polynomials. Then the l.c.m. of these
degrees is a k belonging to the minimum domain.”

Bob

[toc] | [prev] | [next] | [standalone]

#313686

Robert Delaney wrote:
>Robert Delaney wrote:
>>
>>In the thread “An Almost Theorem” on Compuserve²s SciMath forum:
>> 
>>http://forums.compuserve.com/discussions/The_Science_and_Math_Forum/_/_/ws-sciencemath/130471.1 
>> 
>>Alan Listoe proves this theorem for an integer square matrix A 
>>of size n, prime p, and integer k:
>> 
>>“A is semisimple over GF(p) if and only if
>>there is a k such that
>>A^(p^k) = A (mod p).”

For sci.math, when quoting someone, please use the ordinary 
ASCII character ", not “ since some newsreaders cannot display 
the character “ correctly. Alternatively, simply indicate that 
the text that follows is a quote and just indent the quoted text 
(no need for double quotes).

>>“The problem of finding these domain k's reduces to finding
>>all the partitions of n, where we interpret the numbers in a
>>partition as the degrees of the irreducible polynomials. Then 
>>the l.c.m. of these degrees is a k belonging to the minimum 
>>domain.”
>> 
>>Here are some examples supporting that theorem. For these 
>>examples with modulus p. I’ll use a complete residue system 
>>for p = 2 as (0, 1), p = 3 as (-1, 0, 1), p = 5 as 
>>(-2, -1, 0, 1 ,2), and so on.
>> 
>>Consider matrices of size n = 2. Thus k belongs to (1, 2).
>> 
>>Let
>> A =
>> 1 2
>> 3 4
>> 
>>For p = 2
>> A mod p =
>> 1 0
>> 1 0
>>
>>This matrix can be diagonalized and so is semisimple. It also
>>satisfies A^2 = A mod p So k = 1 and the theorem holds.
>> 
>>For p = 3
>> A mod p =
>> 1 -1
>> 0 1
>>This can not be diagonalized and its characteristic polynomial 
>>is reducible, so it is not semisimple.

You mean the characteristic polynomial is not squarefree, so it
is not semisimple.

>>For k = 1
>> A^(p^k) = A^p = A^3 mod p =
>> 1 0
>> 0 1
>>which is not A mod p.
>>
>>For k = 2
>> A^(p^k) = A^9 = (A^3)^3 mod p =
>> 1 0
>> 0 1
>>which is not A mod p.
>>
>>For k > 2
>> A^(p^k) = (A^p)^(p^(k-1)) mod p =
>> 1 0
>> 0 1
>>which is not A mod p for any integer k. Since A mod p is 
>>not semisimple, the theorem holds.
>> 
>>For p = 5
>> A mod p =
>> 1 2
>> -2 -1
>>This matrix cannot be diagonalized over the integers and its
>>characteristic polynomial is irreducible over the integers, so 
>>it is semisimple. 

For A to be semisimple mod 5, the characteristic polynomial 
needs to be squarefree mod 5 (which it is). It's not enough
for the characteristic polynomial to be irreducible over the
integers.

>>So the theorem says there are two possibilities. Either 
>>k = 1 and then the theorem also holds for k = 2, or k = 2. 
>>One finds
>>
>>For k = 1
>> A^(p^k) = A^p = A^5 mod p =
>> -1 -2
>> 2 1
>>which is not A mod p.
>>
>>For k = 2
>> A^(p^k) = A^25 mod p =
>> 1 2
>> -2 -1
>>which is A mod p, so the theorem holds.
>> 
>>Similar examples hold for higher matrix dimensions. When I see 
>>n = 10 matrices with 100 elements reproduced for many primes 
>>with some value for k, I am impressed by the power of this 
>>theorem.
>> 
>>Given the matrix dimension n here are the possible values for k:
>> 
>> n: (minimum domain for k)
>> 1 (1) (Fermat's Little Theorem)
>> 2 (1, 2)
>> 3 (1, 2, 3)
>> 4 (1, 2, 3, 4)
>> 5 (1, 2, 3, 4, 5, 6)
>> 6 (1, 2, 3, 4, 5, 6)
>> 7 (1, 2, 3, 4, 5, 6, 7, 10, 12)
>> 8 (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 15)
>> 9 (2, 3, 4, 5, 6, 7, 8, 9. 10, 12, 14, 15, 20)
>> 10 (2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 20, 21, 30)
>> 11 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30)
>> 12 (3, 4, 5, 6, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30, 35,42, 60)
>> 13 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 21, 24, 28, 30,35, 42, 60)
>> 14 (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 24,28, 
>> 30, 33, 35, 36, 40, 42, 45, 60, 70, 84)
>> 15 (4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 21, 22, 24, 
>> 26,28, 30, 33, 35, 36, 40, 42, 44, 45, 56, 60, 70, 84, 105)
>> 
>>Can anyone find a counter-example to Listoe’s theorem?

Given that Listoe actually _proved_ it, why would there be a 
counterexample?

>From the thread on CompuServe:
>
>Message 35 contains Alan Listoe’s proof:
>
>“Yes. I don't know how to prove the equivalence of the 
>different definitions of "semisimple matrix". But if you 
>accept the "minimal polynomial is squarefree" definition 
>(I found it on the Wikipedia page for Semisimple), then this
>"necessary" part is not hard.
>
>For, if some k exists such that A^(p^k) = A (mod p), then the 
>matrix A(mod p) over GF(p) satisfies the polynomial over GF(p),
>X^(p^k)-X. Therefore the minimal polynomial of A(mod p) is a 
>divisor of X^(p^k)-X. But as X^(p^k)-X has no repeated factors, 
>the minimal polynomial also has no repeated factors. That is to 
>say, A(mod p) is semisimple.
>
>I proved the "sufficient" part in an earlier message, but I 
>will summarize it here: Suppose A(mod p) is semisimple. Let 
>M(X) be the minimal polynomial over GF(p) of A(mod p). Then M 
>has no repeated factors. Let k be the l.c.m. of the degrees of 
>the irreducible factors of M. Then each factor of M has degree 
>dividing k, therefore each factor of M divides X^(p^k)-X. And 
>as M has no repeated factors, M divides X^(p^k)-X. Therefore 
>A(mod p) satisfies the equation X^(p^k)-X=0, that is
>A^(p^k) = A (mod p).
>
>Putting Necessary and Sufficient together, we have:
>
>A is semisimple over GF(p) if and only if
>there is a k such that
>A^(p^k) = A (mod p).”
>
>In Message 37, where n is the size of square matrix A:
>
>“The problem of finding these domain k's reduces to finding 
>all the partitions of n, where we interpret the numbers in a
>partition as the degrees of the irreducible polynomials. Then 
>the l.c.m. of these degrees is a k belonging to the minimum 
>domain.”

The proof excerpted above is along the same lines as the proof 
I had in mind. It looks good to me.

quasi

[toc] | [prev] | [next] | [standalone]

#313700

quasi wrote:


> You mean the characteristic polynomial is not squarefree, so it
> is not semisimple.

A tiny observation, probably not relevant here:
It is not necessary for the characteristic polynomial of a matrix
to be square-free for the matrix to be semisimple.
The minimal polynomial must be square-free.

-- 
Timothy Murphy  
gayleard /at/ eircom.net
School of Mathematics, Trinity College, Dublin

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | sci.math

csiph-web