wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Generalized Wilson's and un-Wilson's
        
(Message started by: Pietro K.C. on Jan 4^th, 2008, 9:08pm)

Title: Generalized Wilson's and un-Wilson's
Post by Pietro K.C. on Jan 4^th, 2008, 9:08pm

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.)

Title: Re: Generalized Wilson's and un-Wilson's
Post by ecoist on Jan 6^th, 2008, 2:12pm

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.

[hide]Let A be the 2x2 matrix with a 1 in the upper right corner, zeros elsewhere. Then Z₂(I,A), the algebra over Z₂ 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 Z₄![/hide]

Title: Re: Generalized Wilson's and un-Wilson's
Post by Eigenray on Jan 6^th, 2008, 5:51pm

You're right. If p is not 0 or -1, then [hide]R is a local ring of order 4, with residue field of order 2[/hide], but there are 2 possibilities.

Moreover, each of the 4 possibilities for p occurs exactly once among the isomorphism classes of rings [hide]of order 4[/hide]:
[hideb]If |R|=4, then R⁺, a group of order 4, is either Z₄ or Z₂².

In the former case, distributivity uniquely determines the multiplication, so R=Z₄ (with usual multiplication), and p=2.

In the latter case, R is a vector space of dimension 2 over the field F₂. 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 x².

If x²=0, as in ecoist's example, R = F₂[x]/(x²), and p=x. And if x²=1, then (1+x)²=0, so this results in an isomorphic ring.

If x²=x, then R = F₂[x]/(x²-x) consists solely of idempotents; in fact R = Z₂ x Z₂ with coordinate-wise multiplication. In this case p=0.

Finally, if x²=x+1, then R = F₂[x]/(x²+x+1) = F₄ is the field with 4 elements, and p=-1.[/hideb]

Title: Re: Generalized Wilson's and un-Wilson's
Post by Aryabhatta on Jan 6^th, 2008, 5:58pm

on 01/06/08 at 17:51:58, Eigenray wrote:

<snip>

Welcome back! :)

Title: Re: Generalized Wilson's and un-Wilson's
Post by Pietro K.C. on Jan 8^th, 2008, 1:43am

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 a²=a+a=0; whence I hastily concluded that this ring was Z₂[X]/(X²) (the quotient ring). But one may have 1+1=a, giving Z₄ 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. :)

Title: Re: Generalized Wilson's and un-Wilson's
Post by Eigenray on Jan 8^th, 2008, 4:49am

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 01/08/08 at 01:43:12, Pietro K.C. wrote:

whence I hastily concluded that this ring was Z₂[X]/(X²) (the quotient ring). But one may have 1+1=a, giving Z₄ as a model.

Heh. Z₄ was actually my first thought (as the smallest non-field Z_n). 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?

Title: Re: Generalized Wilson's and un-Wilson's
Post by Pietro K.C. on Jan 9^th, 2008, 12:21am

Generalizing directly from the last two examples, we get Z₉ and Z₂[X]/(X³). Mixing them up gives Z₃[X]/(X²).

I haven't got a complete argument yet. Could there be some sort of decomposition phenomenon lurking here?

Title: Re: Generalized Wilson's and un-Wilson's
Post by Eigenray on Jan 9^th, 2008, 7:17pm

Z₂[x]/(x³) 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 (R_i, m_i). But the number of non-units of R depends only on the numbers |R_i| and |m_i|, 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.