wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Automorphisms of Rationals
        
(Message started by: william wu on May 18^th, 2007, 1:41am)

Title: Automorphisms of Rationals
Post by william wu on May 18^th, 2007, 1:41am

Characterize all automorphisms of the rationals under addition.

-------------------------------------------------------------------------
Definition of "Automorphism of Rationals Under Addition"

An automorphism over the rationals under addition is a function F such that

1. F(a) is a rational number, where a is any rational number.

2. F(a + b) = F(a) + F(b), where a and b are rational numbers.

3. If a is not equal to b, then F(a) is not equal to F(b).

4. Finally, for every rational number y, there exists a rational number x such that F(x) = y.

We would like to find all such functions F.

Sidenotes for anyone curious: (1) states that the function maps the rationals to the rationals. (2) states that F is a homomorphism. (3) and (4) say that F is actually a bijective homomorphism, which is an isomorphism. Since we are mapping the group to itself, we call that an automorphism.

Title: Re: Automorphisms of Rationals
Post by Obob on May 18^th, 2007, 8:02am

If you define what "automorphism" means, I think this would be a good problem for easy or medium.

Title: Re: Automorphisms of Rationals
Post by Michael_Dagg on May 18^th, 2007, 12:04pm

Any additive homomorphism defined on the rationals will be
determined by the image of 1. That should make it
possible to analyse all of the possibilities.

Title: Re: Automorphisms of Rationals
Post by william wu on May 18^th, 2007, 12:05pm

I would like to see it in easy or medium too, but I think what the problem asks for probably seems very strange unless one has the corresponding background. If we could dress up the problem with a storyline that makes the problem seem less strange, then perhaps we could move it.

Title: Re: Automorphisms of Rationals
Post by Michael_Dagg on May 21^st, 2007, 10:03pm

You can solve this problem by working with the image of 1.

A similar but slightly different idea working the sums of 1's was
given by Pietro K.C. [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1174021523]here[/link].

Title: Re: Automorphisms of Rationals
Post by Michael_Dagg on May 22^nd, 2007, 2:23pm

That is, it is fairly easy to see that an automorphism with respect
to addition of the rationals or of any vector space over the rationals
will actually be linear with respect to multiplication by rational
numbers, (i.e. if r and x are rational numbers and f is the
automorphism, then f(rx) = r f(x) -- not f(r)f(x) ).

This means that in the case of the rational numbers, if you
know f(x) for any non-zero x, then f(y) is completely
determined for all y. In particular, f(y) = y f(1).

Title: Re: Automorphisms of Rationals
Post by ecoist on May 22^nd, 2007, 3:17pm

Correct me if I am wrong, but wasn't it Wu's purpose to leave this problem to less seasoned puzzlers? (Although I like M_D's suggestion to extend this problem to vector spaces over the rationals; and, perhaps, to the automorphism groups of the additive structure of finite fields)

Title: Re: Automorphisms of Rationals
Post by Michael_Dagg on May 22^nd, 2007, 5:05pm

Thanks for the kind remarks, ecoist.

Q is a vector space: the linear transformations
of a one-dimensional vector space correspond to the
field elements, and the one-to-one and onto linear
transformations correspond to the non-zero field elements.

Title: Re: Automorphisms of Rationals
Post by ecoist on May 22^nd, 2007, 6:39pm

You're welcome, M_D.

I particularly like the question extended to the field Q[x]/(p(x)), where p is an irreducible polynomial in Q[x].

Why can't "f is an automorphism" be replaced by "f is a 1-1 onto function on the rationals satisfying f(x+y)=f(x)+f(y), for all rationals x and y", and place the problem in Medium?

And another question. Is the problem below too easy for Putnam but too esoteric for Easy or Medium?

Let T be a transitive relation on {1,...,n}. Define M_T to be the set of all nxn matrices (a_ij) over a field F such that a_ij=0 whenever (i,j) is not in T. Show that M_T is closed under matrix multiplication (and addition and scalar multiplication).

Title: Re: Automorphisms of Rationals
Post by Obob on May 22^nd, 2007, 7:44pm

Yes, ecoist, thats what I originally meant by my comment. I didn't mean to bury the problem; rather I was hoping it could be stated in a way that somebody less experienced with the subject matter could attempt it.

And your question is too easy for putnam, seeing as [hide]it follows directly from the definition[/hide], but is too esoteric for anything else since one does not learn about "transitive relations" without some serious study of mathematics.

Title: Re: Automorphisms of Rationals
Post by ecoist on May 22^nd, 2007, 8:42pm

I guess I like the idea of posting easy and medium problems for Putnam for those with "some serious study of mathematics" (bravo, Wu!), especially if those accustomed to tackling more challenging problems hold off posting solutions long enough to give less seasoned puzzlers a chance to submit solutions. What a thrill if you can reach higher than you have before! But if you can climb a mountain, what joy is there in surmounting a mole hill?

Title: Re: Automorphisms of Rationals
Post by Michael_Dagg on May 22^nd, 2007, 8:54pm

> I particularly like the question extended to the field
> Q[x]/(p(x)), where p is an irreducible polynomial in Q[x].

So where would you put this one -- easy, medium, you
didn't say, but just said that was what you'd like.

If I stepped it up to a p-adic field then where would
you put this one? (course we know)

Title: Re: Automorphisms of Rationals
Post by ecoist on May 22^nd, 2007, 9:24pm

I would put them all in Putnam. And I would be ecstatic when seasoned puzzlers like you, M_D, are inspired to suggest interesting related problems!

Title: Re: Automorphisms of Rationals
Post by JP05 on May 23^rd, 2007, 5:40pm

Again, isn't this like throwing dust in our eyes: no one has say what f(1) equals!!!!!!!!!!!!!! Pardon me, but higher level or not I see this kind of thing here all the time where it is assumed that everyone knows the *result* when in fact there could be others that don't including me. I notice that if I put f(x) = -x f(1), I get a function that satisfies the rules. It takes rationals and gives rationals and is clearly 1-2-1 and *onto* the rationals.

Please explain for the dummy.

Title: Re: Automorphisms of Rationals
Post by Obob on May 23^rd, 2007, 5:43pm

The point is that f(1) can be any nonzero rational number whatsoever. So if one function f satisfies the rule, your observation shows that so does the function whose value at 1 is -f(1).

Title: Re: Automorphisms of Rationals
Post by ecoist on May 23^rd, 2007, 7:39pm

I don't think anyone is "throwing dust" in your eyes, JP05, just dropping hints. Here's another hint. Identify functions that you know are automorphisms (but have more familiar descriptions) and try to prove that any automorphism f is one of those you've identified. The value of f at 1 is central to showing that f equals one of those identified functions.

Title: Re: Automorphisms of Rationals
Post by Icarus on May 23^rd, 2007, 8:23pm

The problem asks you to find ALL automorphisms. Different values of f(1) just provide different automorphisms.

It should be obvious that for any fixed rational number r other than 0, f(x) = rx is an automorphism (r=0 works for #1 and #2, but fails for properties #3 and #4 in William's list).

The harder part of the question is "are there any other automorphisms, or does this catch them all"? Induction can help you out there.

Title: Re: Automorphisms of Rationals
Post by ecoist on May 23^rd, 2007, 8:36pm

I think "induction" does throw a little "dust in our eyes". At least my eyes, anyway.

Title: Re: Automorphisms of Rationals
Post by Icarus on May 23^rd, 2007, 8:54pm

That is because you are thinking more "high-powered" than I am. Given the nature of JP05's comments, I think a lower-tech approach may be more accessible to him.

In particular, for a given automorphism f(x) with f(1) = r for some rational number r, what can you say about f(nx) in terms of f(x), where n is a positive integer? Induction is quite helpful here. Once you've found f(nx), the rest is algebra.

Title: Re: Automorphisms of Rationals
Post by ecoist on May 27^th, 2007, 9:34pm

Isn't

nx=x+...+x (n times)

"lower-tech"? Oh, I see now; the dust just left my eyes! One could use induction on this equation to derive a formula for f(nx). My "high-powered" (read, "lazy") approach was to just skip over induction.

Title: Re: Automorphisms of Rationals
Post by Grimbal on May 28^th, 2007, 2:22pm

All this gets a bit complicated. I don't understand all the words. Here is a simple proof:
[hide]From F(a + b) = F(a) + F(b) we get easily: F(n·a) = n·F(a)
From there, F(p/q) = 1/q·q·F(p/q) = 1/q·F(q·p/q) = 1/q·F(p·1) = 1/q·p·F(1) = p/q·F(1)
Which defines F for all rationals.
The remaining conditions only imply F(1)<>0.
[/hide]