Author 
Topic: Automorphisms of Rationals (Read 3907 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Automorphisms of Rationals
« on: May 18^{th}, 2007, 1:41am » 
Quote Modify

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.

« Last Edit: May 18^{th}, 2007, 12:07pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



Obob
Senior Riddler
Gender:
Posts: 489


Re: Automorphisms of Rationals
« Reply #1 on: May 18^{th}, 2007, 8:02am » 
Quote Modify

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


IP Logged 



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Automorphisms of Rationals
« Reply #2 on: May 18^{th}, 2007, 12:04pm » 
Quote Modify

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.


IP Logged 
Regards, Michael Dagg



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Automorphisms of Rationals
« Reply #3 on: May 18^{th}, 2007, 12:05pm » 
Quote Modify

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.


IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Automorphisms of Rationals
« Reply #4 on: May 21^{st}, 2007, 10:03pm » 
Quote Modify

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

« Last Edit: May 21^{st}, 2007, 10:04pm by Michael Dagg » 
IP Logged 
Regards, Michael Dagg



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Automorphisms of Rationals
« Reply #5 on: May 22^{nd}, 2007, 2:23pm » 
Quote Modify

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 nonzero x, then f(y) is completely determined for all y. In particular, f(y) = y f(1).

« Last Edit: May 22^{nd}, 2007, 2:27pm by Michael Dagg » 
IP Logged 
Regards, Michael Dagg



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Automorphisms of Rationals
« Reply #6 on: May 22^{nd}, 2007, 3:17pm » 
Quote Modify

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)


IP Logged 



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Automorphisms of Rationals
« Reply #7 on: May 22^{nd}, 2007, 5:05pm » 
Quote Modify

Thanks for the kind remarks, ecoist. Q is a vector space: the linear transformations of a onedimensional vector space correspond to the field elements, and the onetoone and onto linear transformations correspond to the nonzero field elements.

« Last Edit: May 22^{nd}, 2007, 5:07pm by Michael Dagg » 
IP Logged 
Regards, Michael Dagg



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Automorphisms of Rationals
« Reply #8 on: May 22^{nd}, 2007, 6:39pm » 
Quote Modify

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

« Last Edit: May 22^{nd}, 2007, 6:41pm by ecoist » 
IP Logged 



Obob
Senior Riddler
Gender:
Posts: 489


Re: Automorphisms of Rationals
« Reply #9 on: May 22^{nd}, 2007, 7:44pm » 
Quote Modify

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 it follows directly from the definition, but is too esoteric for anything else since one does not learn about "transitive relations" without some serious study of mathematics.

« Last Edit: May 22^{nd}, 2007, 7:45pm by Obob » 
IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Automorphisms of Rationals
« Reply #10 on: May 22^{nd}, 2007, 8:42pm » 
Quote Modify

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?


IP Logged 



Michael Dagg
Senior Riddler
Gender:
Posts: 500


Re: Automorphisms of Rationals
« Reply #11 on: May 22^{nd}, 2007, 8:54pm » 
Quote Modify

> 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 padic field then where would you put this one? (course we know)

« Last Edit: May 22^{nd}, 2007, 8:57pm by Michael Dagg » 
IP Logged 
Regards, Michael Dagg



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Automorphisms of Rationals
« Reply #12 on: May 22^{nd}, 2007, 9:24pm » 
Quote Modify

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!


IP Logged 



JP05
Guest


Re: Automorphisms of Rationals
« Reply #13 on: May 23^{rd}, 2007, 5:40pm » 
Quote Modify
Remove

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 121 and *onto* the rationals. Please explain for the dummy.


IP Logged 



Obob
Senior Riddler
Gender:
Posts: 489


Re: Automorphisms of Rationals
« Reply #14 on: May 23^{rd}, 2007, 5:43pm » 
Quote Modify

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

« Last Edit: May 23^{rd}, 2007, 5:43pm by Obob » 
IP Logged 



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Automorphisms of Rationals
« Reply #15 on: May 23^{rd}, 2007, 7:39pm » 
Quote Modify

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.


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Automorphisms of Rationals
« Reply #16 on: May 23^{rd}, 2007, 8:23pm » 
Quote Modify

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.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Automorphisms of Rationals
« Reply #17 on: May 23^{rd}, 2007, 8:36pm » 
Quote Modify

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


IP Logged 



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Automorphisms of Rationals
« Reply #18 on: May 23^{rd}, 2007, 8:54pm » 
Quote Modify

That is because you are thinking more "highpowered" than I am. Given the nature of JP05's comments, I think a lowertech 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.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Automorphisms of Rationals
« Reply #19 on: May 27^{th}, 2007, 9:34pm » 
Quote Modify

Isn't nx=x+...+x (n times) "lowertech"? 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 "highpowered" (read, "lazy") approach was to just skip over induction.


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527


Re: Automorphisms of Rationals
« Reply #20 on: May 28^{th}, 2007, 2:22pm » 
Quote Modify

All this gets a bit complicated. I don't understand all the words. Here is a simple proof: 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.


IP Logged 



