Author |
Topic: Generalized Wilson's and un-Wilson's (Read 1293 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
Generalized Wilson's and un-Wilson's
« on: Jan 4th, 2008, 9:08pm » |
 Quote  Modify
|
One of the staples of any introductory class in number theory is Wilson's theorem: for every prime number p,
(p-1)! + 1 is divisible by p
What's more, a natural number n divides (n-1)! + 1 only if n is prime, so you get a 100% accurate, but very inefficient, primality test.
It is possible to generalize both halves of the theorem. The first is straightforward, but might be enjoyable if you can't recall the proof of Wilson's:
1. For any finite field F, the product of all nonzero elements of F is -1. (Alternatively, (1+product) equals zero.)
The second half, however, holds a little surprise:
2. Let R be a finite commutative ring with unity, and p be the product of all its nonzero elements. If R is not a field, then p = 0, except for one single ring, up to unique isomorphism, in the entire category of finite commutative rings with unity. Which ring is that?
(It is still the case that 1+p is invertible, which gives a nice unified way of distinguishing cases (1) and (2). As a starting point, you may like to prove p nilpotent, which implies 1+p invertible.)
|
| « Last Edit: Jan 4th, 2008, 9:14pm by Pietro K.C. » |
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Generalized Wilson's and un-Wilson's
« Reply #1 on: Jan 6th, 2008, 2:12pm » |
Quote Modify
|
Am I missing something? In your case 2, Pietro, when R is not a field, I seem to have found two non-isomorphic examples when p=/=0.
Let A be the 2x2 matrix with a 1 in the upper right corner, zeros elsewhere. Then Z2(I,A), the algebra over Z2 generated by A and the 2x2 identity matrix I has the property that the product of all of its non-identity elements is nonzero. But this is also true of the non-isomorphic ring Z4!
|
| « Last Edit: Jan 6th, 2008, 2:14pm by ecoist » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Generalized Wilson's and un-Wilson's
« Reply #2 on: Jan 6th, 2008, 5:51pm » |
Quote Modify
|
You're right. If p is not 0 or -1, then R is a local ring of order 4, with residue field of order 2, but there are 2 possibilities.
Moreover, each of the 4 possibilities for p occurs exactly once among the isomorphism classes of rings of order 4:
| hidden: | If |R|=4, then R+, a group of order 4, is either Z4 or Z22.
In the former case, distributivity uniquely determines the multiplication, so R=Z4 (with usual multiplication), and p=2.
In the latter case, R is a vector space of dimension 2 over the field F2. So if x is an element distinct from 0 and 1, then R = {0,1,x,1+x}, and the multiplication on R is uniquely determined by the value of x2.
If x2=0, as in ecoist's example, R = F2[x]/(x2), and p=x. And if x2=1, then (1+x)2=0, so this results in an isomorphic ring.
If x2=x, then R = F2[x]/(x2-x) consists solely of idempotents; in fact R = Z2 x Z2 with coordinate-wise multiplication. In this case p=0.
Finally, if x2=x+1, then R = F2[x]/(x2+x+1) = F4 is the field with 4 elements, and p=-1. |
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Generalized Wilson's and un-Wilson's
« Reply #3 on: Jan 6th, 2008, 5:58pm » |
Quote Modify
|
on Jan 6th, 2008, 5:51pm, Eigenray wrote:
Welcome back! 
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Generalized Wilson's and un-Wilson's
« Reply #4 on: Jan 8th, 2008, 1:43am » |
Quote Modify
|
Ah yes, of course, you are all correct. I had gotten as far as realizing that the ring was of the form
{0, 1, a, 1+a}
where all these are distinct and a2=a+a=0; whence I hastily concluded that this ring was Z2[X]/(X2) (the quotient ring). But one may have 1+1=a, giving Z4 as a model.
I hit upon this by accident while trying to come up with an intuitive explanation of why Wilson's theorem is only true whenever it can be proved in the "obvious" manner (via inverses etc). In other words, Wilson's theorem "detects" field structure, which allows the simple proof to go through.
I was confident that the product of all nonzero elements would come out to be zero for anything not a field, but lo and behold, I found a "unique" ring that behaved differently! It seemed a pretty simple, global characterization of such a unique object, so I thought I'd share it here.
Oh well, I'm only half as impressed now.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Generalized Wilson's and un-Wilson's
« Reply #5 on: Jan 8th, 2008, 4:49am » |
Quote Modify
|
Thanks, Aryabhatta. Last semester wasn't very good but I don't think not posting here helped much. I just ended up procrastinating less (more?) efficiently.
on Jan 8th, 2008, 1:43am, Pietro K.C. wrote:| whence I hastily concluded that this ring was Z2[X]/(X2) (the quotient ring). But one may have 1+1=a, giving Z4 as a model. |
|
Heh. Z4 was actually my first thought (as the smallest non-field Zn). Then I proved uniqueness to myself by working out that R must have 4 elements, at which point I stopped because there were only a few cases to consider and I already 'knew' what the result would be. So ecoist's post caught me by surprise too.
Anyway, it's a nice bit of trivia. Equivalently, these are the only commutative rings with a unique non-zero non-unit. What about rings with exactly 2?
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Generalized Wilson's and un-Wilson's
« Reply #6 on: Jan 9th, 2008, 12:21am » |
Quote Modify
|
Generalizing directly from the last two examples, we get Z9 and Z2[X]/(X3). Mixing them up gives Z3[X]/(X2).
I haven't got a complete argument yet. Could there be some sort of decomposition phenomenon lurking here?
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Generalized Wilson's and un-Wilson's
« Reply #7 on: Jan 9th, 2008, 7:17pm » |
Quote Modify
|
Z2[x]/(x3) actually has 4 non-units (3 of them non-zero). But the other two are the unique rings with 3 non-units.
Any finite commutative ring R is a product of local rings (Ri, mi). But the number of non-units of R depends only on the numbers |Ri| and |mi|, so a complete characterization of rings with n non-units would rely on a characterization of finite commutative local rings with a given order and residue field.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print