wu :: forums
« wu :: forums - Generalized Wilson's and un-Wilson's »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 12:18pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Eigenray, towr, william wu, SMQ, Grimbal, Icarus)
   Generalized Wilson's and un-Wilson's
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Generalized Wilson's and un-Wilson's  (Read 1276 times)
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Generalized Wilson's and un-Wilson's  
« on: Jan 4th, 2008, 9:08pm »
Quote Quote Modify 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: male
Posts: 405
Re: Generalized Wilson's and un-Wilson's  
« Reply #1 on: Jan 6th, 2008, 2:12pm »
Quote Quote Modify 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: male
Posts: 1948
Re: Generalized Wilson's and un-Wilson's  
« Reply #2 on: Jan 6th, 2008, 5:51pm »
Quote Quote Modify 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: male
Posts: 1321
Re: Generalized Wilson's and un-Wilson's  
« Reply #3 on: Jan 6th, 2008, 5:58pm »
Quote Quote Modify Modify

on Jan 6th, 2008, 5:51pm, Eigenray wrote:

<snip>

 
Welcome back!  Smiley
IP Logged
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: Generalized Wilson's and un-Wilson's  
« Reply #4 on: Jan 8th, 2008, 1:43am »
Quote Quote Modify 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.   Smiley
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: male
Posts: 1948
Re: Generalized Wilson's and un-Wilson's  
« Reply #5 on: Jan 8th, 2008, 4:49am »
Quote Quote Modify 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
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: Generalized Wilson's and un-Wilson's  
« Reply #6 on: Jan 9th, 2008, 12:21am »
Quote Quote Modify 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: male
Posts: 1948
Re: Generalized Wilson's and un-Wilson's  
« Reply #7 on: Jan 9th, 2008, 7:17pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board