Author |
Topic: Automorphisms of Rationals (Read 3885 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Automorphisms of Rationals
« on: May 18th, 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 18th, 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 18th, 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 18th, 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 18th, 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 21st, 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 21st, 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 22nd, 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 non-zero x, then f(y) is completely
determined for all y. In particular, f(y) = y f(1).
|
| « Last Edit: May 22nd, 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 22nd, 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 22nd, 2007, 5:05pm » |
Quote Modify
|
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.
|
| « Last Edit: May 22nd, 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 22nd, 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 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 MT to be the set of all nxn matrices (aij) over a field F such that aij=0 whenever (i,j) is not in T. Show that MT is closed under matrix multiplication (and addition and scalar multiplication).
|
| « Last Edit: May 22nd, 2007, 6:41pm by ecoist » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Automorphisms of Rationals
« Reply #9 on: May 22nd, 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 22nd, 2007, 7:45pm by Obob » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Automorphisms of Rationals
« Reply #10 on: May 22nd, 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 22nd, 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 p-adic field then where would
you put this one? (course we know)
|
| « Last Edit: May 22nd, 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 22nd, 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 23rd, 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 1-2-1 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 23rd, 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 23rd, 2007, 5:43pm by Obob » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Automorphisms of Rationals
« Reply #15 on: May 23rd, 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 23rd, 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 23rd, 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 23rd, 2007, 8:54pm » |
Quote Modify
|
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.
|
|
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 27th, 2007, 9:34pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Automorphisms of Rationals
« Reply #20 on: May 28th, 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print