|
Let f,g be polynomials with rational coefficients. Suppose f(Q) = g(Q) (i.e. the sets of values of f and g on the rationals are the same). Then f(x) = g(ax + b) for some rational constants a,b.
Remark. It generalizes to number fields with real embeddings.
Note that the converse is trivial.
Solution
The idea is that (mod the full details) there's a fixed discrete subgroup L of Q such that for any integer x, the rational solutions, viewed in y, of g(y) = f(x) are all in L. To extract the behavior of y as x varies, and compare the coefficients at the same time, i.e. the growth rates, you can consider expressions of the form g(y') - g(y) = f(x+1) - f(x) where y' is the corresponding rational number such that g(y') = f(x+1). By mean value theorem (don't quite need this, since f,g are polynomials so one can potentially do all the computations by algebra) the expression extracts out y' - y in terms of f'(x) and g'(y) roughly, and this gives a good comparison of y as x varies. This is the idea, and I do some computations to show that this works.
Also, simple valuation calculations (plug in this, plug in that rational number, compare the p-adic valuations) don't really seem to get anywhere, as I give plenty of counter examples and point out the problems to the claims of one of the posters below.
 
|
Canada1950 Posts
|
On September 11 2010 05:34 Assault_1 wrote:
so whats the question?
Proving it.
|
Would a non-math major/non-math enthusiast be able to solve this?
|
the sets f(Q) and g(Q) are not counting multiplicity right?
|
On September 11 2010 05:52 Piege wrote:
Would a non-math major/non-math enthusiast be able to solve this?
I don't know the solution yet but I suspect the answer to your question is no.
|
On September 11 2010 05:53 category wrote:
the sets f(Q) and g(Q) are not counting multiplicity right?
They're just sets, not really any structures on them (for ex. ramifications). For example for the functio f(x) = x^2 the set f(Q) is just the set of all squares of rational numbers. We don't care that f(x) = 0 ramifies (and elsewhere unramifies). It's just a naive set.
I wonder if that's what you meant. So yes, I think we're not counting multiplicities here, whatever you mean by that in this context. f(Q) = {y : y = f(a) for some rational a}.
|
lol. I don't know about ramifications. i just meant, eg in the f(x^2) case, does it matter that 1 is obtained twice? but it sounds like no.
i guess for the functions f=x^2 and g=x^4, f(Q) will be larger than g(Q), because some rationals are the square of another rational but are not a fourth power?
|
On September 11 2010 05:59 category wrote:
lol. I don't know about ramifications. i just meant, eg in the f(x^2) case, does it matter that 1 is obtained twice? but it sounds like no.
Right, just count it once. So for example {1,1} = {1}.
i guess for the functions f=x^2 and g=x^4, f(Q) will be larger than g(Q), because some rationals are the square of another rational but are not a fourth power?
That's right.
|
Canada1950 Posts
Then f(x) = g(ax + b) for some rational constants a,b.
whats the domain of x, rational or real?
|
On September 11 2010 06:04 Assault_1 wrote:whats the domain of x, rational or real?
any field containing the rationals. It really doesn't matter, since the condition is only imposed on f(Q) and g(Q). You don't need to "see" bigger fields containing the rationals. Any such field is infinite anyway, so if the condition f(x) = g(ax + b) holds for evaluating x on all rationals then it's identical as polynomials (in the ring Q[x]) so evaluation of x on any field containing Q likewise.
|
On September 11 2010 06:04 Assault_1 wrote:whats the domain of x, rational or real?
i would say, think of it as being the rationals.
but yeah, i am finding this quite hard, though I find the result very interesting.
|
I've noticed that threads like this pop up during the school year...
ITT: TL does your math homework for you
|
On September 11 2010 06:16 sputnik.theory wrote:
I've noticed that threads like this pop up during the school year...
ITT: TL does your math homework for you
Rest assured, I've already solved this. It's not a homework.
|
May I (a non-math major) ask for an example of an f(x) and g(x) polynomial for which this is true.
|
On September 11 2010 06:04 Assault_1 wrote:whats the domain of x, rational or real?
I am guessing the real or complex is fine. Once we can prove this for the real it automatically implies that it's also true for the complex.
On September 11 2010 06:18 Seth_ wrote:
May I (a non-math major) ask for an example of an f(x) and g(x) polynomial for which this is true.
Sure. f(x) = x^2. g(x) = (2x)^2.
|
f(Q) clearly equals g(Q) if f(x)=g(ax+b)
Thus WLOG f and g have integer coefficients that are relatively prime and 0 as their constant terms.
Suppose f(x)=a_nx^n+...a_1*x.
Suppose g(x)=b_nx^n+...+b_1*x.
Let p^r be a prime power dividing a_1 but not b_1, if such a prime power exists. Then f(x) will always be divisible by p either less than or equal to 0 times or more than r times, while g(p) is divisible by p at least once and at most r times.
So this means that f(Q)=g(Q) then a_1= plus/minus b_1
One can continue inductively through all the coefficients
|
Or something like that... don't have time to check everything but should be close 
|
On September 11 2010 06:25 Muirhead wrote:
f(Q) clearly equals g(Q) if f(x)=g(ax+b)
Thus WLOG f and g have integer coefficients that are relatively prime and 0 as their constant terms.
Suppose f(x)=a_nx^n+...a_1*x.
Suppose g(x)=b_nx^n+...+b_1*x.
Let p^r be a prime power dividing a_1 but not b_1, if such a prime power exists. Then f(x) will always be divisible by p either less than or equal to 0 times or more than r times, while g(p) is divisible by p at least once and at most r times.
So this means that f(Q)=g(Q) then a_1= plus/minus b_1
One can continue inductively through all the coefficients
Need a lot more details, and I'm not convinced of this argument either. You're saying WLOG assume 0 as their constant terms? And then you're assuming deg f = deg g (this is true, but you didn't mention how to prove this at all). And then there's the next paragraph which doesn't seem to make much sense to me.
Enjoy your Friday anyway! 
|
Here's an attempt for any field, F:
+ Show Spoiler +
Since f(F)=g(F), g(F) includes f(x) and there must be an element s of F where g(s)=f(x).
Rewrite s in the form ax+b for some a,b in F:
If x = 0, let b = s and a be any number in F.
Then ax+b = a 0 + s = s.
If x is not 0, let a = x^-1, the multiplicative inverse of x in F, and b = s - 1.
Then ax+b = (x^-1) x + (s - 1) = 1 + (s - 1) = s.
In both cases, ax+b = s and g(ax+b) = g(s) = f(x).
Edit: Never mind, I think I misread the problem.
|
I don't really understand the question ._.
all that comes to my mind is let f(x) = x, let g(x) = x (thus, all f(Q) = g(Q)), then f(x) = g(ax + b) for a = 1, b = 0.
|
On September 11 2010 06:35 AlienAlias wrote:
I don't really understand the question ._.
all that comes to my mind is let f(x) = x, let g(x) = x (thus, all f(Q) = g(Q)), then f(x) = g(ax + b) for a = 1, b = 0.
The question is that for *any* two polynomials f,g with rational coefficients satisfying f(Q) = g(Q), there exists some rational constants a,b such that f(x) = g(ax + b).
You've only considered one particular case of f(x) = x and g(x) = x. That's one out of infinitely many f,g satisfying the conditions of the problem.
|
On September 11 2010 06:29 naptiem wrote:Here's an attempt for any field, F: + Show Spoiler +
Since f(F)=g(F), g(F) includes f(x) and there must be an element s of F where g(s)=f(x).
Rewrite s in the form ax+b for some a,b in F:
If x = 0, let b = s and a be any number in F.
Then ax+b = a 0 + s = s.
If x is not 0, let a = x^-1, the multiplicative inverse of x in F, and b = s - 1.
Then ax+b = (x^-1) x + (s - 1) = 1 + (s - 1) = s.
In both cases, ax+b = s and g(ax+b) = g(s) = f(x).
Edit: Never mind, I think I misread the problem.
K. In fact, you can easily come up with counterexamples over the complex or over the reals.
The generalization I have in mind is to number fields with real embeddings, and the significant fact is the existence of a lattice L of F (F is finite extension of Q, with real embedding), i.e. L is free abelian group with rank = [F:Q], and the L sitting in F tensor_Q R, where the latter is given a topology as a vector space, is a discrete subgroup.
|
so basically the question is to prove that if f(x) and g(x) are polynomials (rational etc) of the same degree, there will be some a and b in which f(x) = g(ax + b)? or is there something else in this whole talk of sets and fields that I'm missing?
|
On September 11 2010 06:55 AlienAlias wrote:
so basically the question is to prove that if f(x) and g(x) are polynomials (rational etc) of the same degree, there will be some a and b in which f(x) = g(ax + b)? or is there something else in this whole talk of sets and fields that I'm missing?
No. The question is properly stated as it is. You're adding the assumption that deg f = deg g now, which will follow from the condition f(x) = g(ax + b) but that requires a bit of work still.
|
On September 11 2010 06:57 mieda wrote:Show nested quote +On September 11 2010 06:55 AlienAlias wrote:
so basically the question is to prove that if f(x) and g(x) are polynomials (rational etc) of the same degree, there will be some a and b in which f(x) = g(ax + b)? or is there something else in this whole talk of sets and fields that I'm missing? No. The question is properly stated as it is. You're adding the assumption that deg f = deg g now, which will follow from the condition f(x) = g(ax + b) but that requires a bit of work still.
I'm sorry, I'm just trying to understand the original problem because I'm not exactly sure what Suppose f(Q) = g(Q) (i.e. the sets of values of f and g on the rationals are the same). means. In my first post, I thought this meant the same thing as f(x) = g(x), which means by law of identity they are the same function and thus the question is silly.
However, apparently it involves things by the names of 'sets' and 'embedded fields' and other things I've not heard of before, so I'm trying to see if I can simplify it to terms that I would understand. I saw an example of f(x) = x^2 and g(x) = (2x)^2 for which f(Q) = g(Q), so I figured that whole thing meant the degree was equal.
|
On September 11 2010 07:03 AlienAlias wrote:Show nested quote +On September 11 2010 06:57 mieda wrote:On September 11 2010 06:55 AlienAlias wrote:
so basically the question is to prove that if f(x) and g(x) are polynomials (rational etc) of the same degree, there will be some a and b in which f(x) = g(ax + b)? or is there something else in this whole talk of sets and fields that I'm missing? No. The question is properly stated as it is. You're adding the assumption that deg f = deg g now, which will follow from the condition f(x) = g(ax + b) but that requires a bit of work still. I'm sorry, I'm just trying to understand the original problem because I'm not exactly sure what Show nested quote +Suppose f(Q) = g(Q) (i.e. the sets of values of f and g on the rationals are the same). means. In my first post, I thought this meant the same thing as f(x) = g(x), which means by law of identity they are the same function and thus the question is silly. However, apparently it involves things by the names of 'sets' and 'embedded fields' and other things I've not heard of before, so I'm trying to see if I can simplify it to terms that I would understand. I saw an example of f(x) = x^2 and g(x) = (2x)^2 for which f(Q) = g(Q), so I figured that whole thing meant the degree was equal.
I see. I'll try to clarify what f(Q) = g(Q) means.
First, f(Q) means the set of all numbers in the range of f when you restrict the domain of f on the rationals. So for example, if f(x) = x^2 then f(Q) is the *set* or collection of all numbers y such that there exists some rational number x with y = x^2. For example, 25 is in this set because 25 = 5^2. 25/36 is also in the set because 25/36 = (5/6)^2 . You take the collection of all these numbers y such that there exists some x rational with y = f(x), and that's given a notation f(Q).
Likewise g(Q) is the collection of all numbers y such that there exists (depending on y) some rational number x such that y = g(x).
So the condition f(Q) = g(Q) just says the two sets are equal. In plain terms, it says that for any rational number x, you can find a rational number y (depending on x) such that f(x) = g(y). And vice versa.
|
On September 11 2010 06:29 mieda wrote:Show nested quote +On September 11 2010 06:25 Muirhead wrote:
f(Q) clearly equals g(Q) if f(x)=g(ax+b)
Thus WLOG f and g have integer coefficients that are relatively prime and 0 as their constant terms.
Suppose f(x)=a_nx^n+...a_1*x.
Suppose g(x)=b_nx^n+...+b_1*x.
Let p^r be a prime power dividing a_1 but not b_1, if such a prime power exists. Then f(x) will always be divisible by p either less than or equal to 0 times or more than r times, while g(p) is divisible by p at least once and at most r times.
So this means that f(Q)=g(Q) then a_1= plus/minus b_1
One can continue inductively through all the coefficients Need a lot more details, and I'm not convinced of this argument either. You're saying WLOG assume 0 as their constant terms? And then you're assuming deg f = deg g (this is true, but you didn't mention how to prove this at all). And then there's the next paragraph which doesn't seem to make much sense to me. Enjoy your Friday anyway!
My argument works. By "being divisible by p" k times I mean that the p-adic valuation of the rational number is blah blah... I think I assumed f,g have the same degree but it doesn't affect the argument if they have different agrees.
|
Also my argument works for any number field :D
|
On September 11 2010 07:14 Muirhead wrote:Show nested quote +On September 11 2010 06:29 mieda wrote:On September 11 2010 06:25 Muirhead wrote:
f(Q) clearly equals g(Q) if f(x)=g(ax+b)
Thus WLOG f and g have integer coefficients that are relatively prime and 0 as their constant terms.
Suppose f(x)=a_nx^n+...a_1*x.
Suppose g(x)=b_nx^n+...+b_1*x.
Let p^r be a prime power dividing a_1 but not b_1, if such a prime power exists. Then f(x) will always be divisible by p either less than or equal to 0 times or more than r times, while g(p) is divisible by p at least once and at most r times.
So this means that f(Q)=g(Q) then a_1= plus/minus b_1
One can continue inductively through all the coefficients Need a lot more details, and I'm not convinced of this argument either. You're saying WLOG assume 0 as their constant terms? And then you're assuming deg f = deg g (this is true, but you didn't mention how to prove this at all). And then there's the next paragraph which doesn't seem to make much sense to me. Enjoy your Friday anyway! My argument works. By "being divisible by p" k times I mean that the p-adic valuation of the rational number is blah blah... I think I assumed f,g have the same degree but it doesn't affect the argument if they have different agrees.
p-adic valuation of what? How did you reduce to the relatively prime case? And what is relatively prime?
|
On September 11 2010 07:16 mieda wrote:Show nested quote +On September 11 2010 07:14 Muirhead wrote:On September 11 2010 06:29 mieda wrote:On September 11 2010 06:25 Muirhead wrote:
f(Q) clearly equals g(Q) if f(x)=g(ax+b)
Thus WLOG f and g have integer coefficients that are relatively prime and 0 as their constant terms.
Suppose f(x)=a_nx^n+...a_1*x.
Suppose g(x)=b_nx^n+...+b_1*x.
Let p^r be a prime power dividing a_1 but not b_1, if such a prime power exists. Then f(x) will always be divisible by p either less than or equal to 0 times or more than r times, while g(p) is divisible by p at least once and at most r times.
So this means that f(Q)=g(Q) then a_1= plus/minus b_1
One can continue inductively through all the coefficients Need a lot more details, and I'm not convinced of this argument either. You're saying WLOG assume 0 as their constant terms? And then you're assuming deg f = deg g (this is true, but you didn't mention how to prove this at all). And then there's the next paragraph which doesn't seem to make much sense to me. Enjoy your Friday anyway! My argument works. By "being divisible by p" k times I mean that the p-adic valuation of the rational number is blah blah... I think I assumed f,g have the same degree but it doesn't affect the argument if they have different agrees. p-adic valuation of what? How did you reduce to the relatively prime case? And what is relatively prime?
I'll write it up in more detail later if nobody else gets it by tonight :D. My Friday is filled with the all important and super sexy Starcraft LAN at MIT :D
|
On September 11 2010 07:18 Muirhead wrote:Show nested quote +On September 11 2010 07:16 mieda wrote:On September 11 2010 07:14 Muirhead wrote:On September 11 2010 06:29 mieda wrote:On September 11 2010 06:25 Muirhead wrote:
f(Q) clearly equals g(Q) if f(x)=g(ax+b)
Thus WLOG f and g have integer coefficients that are relatively prime and 0 as their constant terms.
Suppose f(x)=a_nx^n+...a_1*x.
Suppose g(x)=b_nx^n+...+b_1*x.
Let p^r be a prime power dividing a_1 but not b_1, if such a prime power exists. Then f(x) will always be divisible by p either less than or equal to 0 times or more than r times, while g(p) is divisible by p at least once and at most r times.
So this means that f(Q)=g(Q) then a_1= plus/minus b_1
One can continue inductively through all the coefficients Need a lot more details, and I'm not convinced of this argument either. You're saying WLOG assume 0 as their constant terms? And then you're assuming deg f = deg g (this is true, but you didn't mention how to prove this at all). And then there's the next paragraph which doesn't seem to make much sense to me. Enjoy your Friday anyway! My argument works. By "being divisible by p" k times I mean that the p-adic valuation of the rational number is blah blah... I think I assumed f,g have the same degree but it doesn't affect the argument if they have different agrees. p-adic valuation of what? How did you reduce to the relatively prime case? And what is relatively prime? I'll write it up in more detail later if nobody else gets it by tonight :D. My Friday is filled with the all important and super sexy Starcraft LAN at MIT :D
Becareful there, Starcraft can take up all your time even on weekdays if you're not careful  I quit Harvard CSL since I was spending way too much time on ICCUP :p
|
On September 11 2010 07:19 mieda wrote:Show nested quote +On September 11 2010 07:18 Muirhead wrote:On September 11 2010 07:16 mieda wrote:On September 11 2010 07:14 Muirhead wrote:On September 11 2010 06:29 mieda wrote:On September 11 2010 06:25 Muirhead wrote:
f(Q) clearly equals g(Q) if f(x)=g(ax+b)
Thus WLOG f and g have integer coefficients that are relatively prime and 0 as their constant terms.
Suppose f(x)=a_nx^n+...a_1*x.
Suppose g(x)=b_nx^n+...+b_1*x.
Let p^r be a prime power dividing a_1 but not b_1, if such a prime power exists. Then f(x) will always be divisible by p either less than or equal to 0 times or more than r times, while g(p) is divisible by p at least once and at most r times.
So this means that f(Q)=g(Q) then a_1= plus/minus b_1
One can continue inductively through all the coefficients Need a lot more details, and I'm not convinced of this argument either. You're saying WLOG assume 0 as their constant terms? And then you're assuming deg f = deg g (this is true, but you didn't mention how to prove this at all). And then there's the next paragraph which doesn't seem to make much sense to me. Enjoy your Friday anyway! My argument works. By "being divisible by p" k times I mean that the p-adic valuation of the rational number is blah blah... I think I assumed f,g have the same degree but it doesn't affect the argument if they have different agrees. p-adic valuation of what? How did you reduce to the relatively prime case? And what is relatively prime? I'll write it up in more detail later if nobody else gets it by tonight :D. My Friday is filled with the all important and super sexy Starcraft LAN at MIT :D Becareful there, Starcraft can take up all your time even on weekdays if you're not careful I quit Harvard CSL since I was spending way too much time on ICCUP :p
Hm you wouldn't happen to be Arnav Tripathy, Alex Zhai, Zachary Abel, or Yi Sun would you? I imagine you at least know those people
|
On September 11 2010 07:21 Muirhead wrote:Show nested quote +On September 11 2010 07:19 mieda wrote:On September 11 2010 07:18 Muirhead wrote:On September 11 2010 07:16 mieda wrote:On September 11 2010 07:14 Muirhead wrote:On September 11 2010 06:29 mieda wrote:On September 11 2010 06:25 Muirhead wrote:
f(Q) clearly equals g(Q) if f(x)=g(ax+b)
Thus WLOG f and g have integer coefficients that are relatively prime and 0 as their constant terms.
Suppose f(x)=a_nx^n+...a_1*x.
Suppose g(x)=b_nx^n+...+b_1*x.
Let p^r be a prime power dividing a_1 but not b_1, if such a prime power exists. Then f(x) will always be divisible by p either less than or equal to 0 times or more than r times, while g(p) is divisible by p at least once and at most r times.
So this means that f(Q)=g(Q) then a_1= plus/minus b_1
One can continue inductively through all the coefficients Need a lot more details, and I'm not convinced of this argument either. You're saying WLOG assume 0 as their constant terms? And then you're assuming deg f = deg g (this is true, but you didn't mention how to prove this at all). And then there's the next paragraph which doesn't seem to make much sense to me. Enjoy your Friday anyway! My argument works. By "being divisible by p" k times I mean that the p-adic valuation of the rational number is blah blah... I think I assumed f,g have the same degree but it doesn't affect the argument if they have different agrees. p-adic valuation of what? How did you reduce to the relatively prime case? And what is relatively prime? I'll write it up in more detail later if nobody else gets it by tonight :D. My Friday is filled with the all important and super sexy Starcraft LAN at MIT :D Becareful there, Starcraft can take up all your time even on weekdays if you're not careful I quit Harvard CSL since I was spending way too much time on ICCUP :p Hm you wouldn't happen to be Arnav Tripathy, Alex Zhai, Zachary Abel, or Yi Sun would you? I imagine you at least know those people
I do know Zachary, met him at the math lounge. I don't know the rest.
In fact, are you taking a course at Harvard by any chance?
|
I was wondering if it might be useful to prove that the degrees must be equal as an intermediate step. But I have no idea how to prove even that.
|
On September 11 2010 06:25 Muirhead wrote:
f(Q) clearly equals g(Q) if f(x)=g(ax+b)
Thus WLOG f and g have integer coefficients that are relatively prime and 0 as their constant terms.
Suppose f(x)=a_nx^n+...a_1*x.
Suppose g(x)=b_nx^n+...+b_1*x.
Let p^r be a prime power dividing a_1 but not b_1, if such a prime power exists. Then f(x) will always be divisible by p either less than or equal to 0 times or more than r times, while g(p) is divisible by p at least once and at most r times.
So this means that f(Q)=g(Q) then a_1= plus/minus b_1
One can continue inductively through all the coefficients
This is wrong and you should be careful there, it's a common error that a lot of students seem to make. Take f(x) = x^3 + 4x and g(x) = x^3 + x^2 - 2x. the 2-adic valuation (additive) v(4) = 2 and v(2) = 1. Here your r = 2. But v(g(2)) = 3 > 2 = r now.
Also, you seem to be proving that if f(x) = a_n x^n + a_{n-1} x^{n-1} + ... + a_1 x and g(x) = b_n x^n +b_{n-1} x^{n-1} + ... + b_1 x are of those form (no constant terms and contents of f,g are 1) and f(Q) = g(Q), then all the corresponding coefficients are +/- of each other. Here's a counterexample: Take g(x) = x^3 + x^2 - 2x as above. Then g(x+1) = x^3 + 4x^2 + 3x. But -2 and 3 have different 2-adic and 3-adic valuations, even though the images of g(x) and g(x+1) on the rationals are the same.
There are some other road blocks that I can immediately think of in just doing simple valuation calculations, so you'd better write up a detailed attempt. It most likely won't work.
As Richard likes to say, devil's always in the detail :p .
Speaking of which, I remember I was trying to show him some calculations I did with etale cohomology of some rigid analytic spaces (the method I used, as you might know was to compute combinatorially by finding some open affinoids with good reduction - well you need a semistable model also - and you can imagine how complicated it can get with spectral sequences of rapoport-zink) and I was very sure some parts were standard calculations, little did I know he caught one error and proceeded to tell me a lengthy story with "devil's in the detail" as his point. Of course this problem is nowhere as complicated as computing spectral sequences, and does admit elementary solutions, but he taught me to always be careful
Valuation calculations is the first thing one would try for this problem. I think you probably need to do a little more than simple valuation calculations, but who knows.
Edit: Rapoport is visiting Harvard at the moment. If you do algebraic geometry you should probably talk to him while he's still here ^^
|
Looks interesting, I'll have a go. Thinking geometrically seems to give some intuition and I have some vague ideas as to how the specific behaviour of polynomials can come into play, but nothing crystallized yet. Bedtime too anyway so will try again tomorrow
|
On September 11 2010 09:56 KristianJS wrote:Looks interesting, I'll have a go. Thinking geometrically seems to give some intuition and I have some vague ideas as to how the specific behaviour of polynomials can come into play, but nothing crystallized yet. Bedtime too anyway so will try again tomorrow
Great!
|
I just finished typing my solution to this in LaTeX, so anyone who would like to see my solution can PM me!
Edit: I'll post it tomorrow or day after tomorrow probably.
|
Gogogo muirhead! MIT fighting! :D
Remember me mieda? We played on iccup and east before. Do you play sc2 now?
Oh and btw it's not being able to solve problems like these that push me further and further into the less pure land of CS. 
|
On September 11 2010 23:16 FiBsTeR wrote:Gogogo muirhead! MIT fighting! :D Remember me mieda? We played on iccup and east before. Do you play sc2 now? Oh and btw it's not being able to solve problems like these that push me further and further into the less pure land of CS.
Hey Fibster, yea I remember you of course. We were in team "Galois" at iccup for brief time hah!
I don't play sc2 now, since my computer can't run it. But it's better that way, since I wasted too much time on iccup anyway  .
Harvard CSL is all SC2 now. I guess it's the same for MIT CSL?
|
Korea (South)1888 Posts
So, as I understand it, we need to find a way to find the values for a and b? Proving the last statement, that they exist, is trivial.
|
On September 12 2010 00:59 BottleAbuser wrote:
So, as I understand it, we need to find a way to find the values for a and b? Proving the last statement, that they exist, is trivial.
Um, that's not trivial at all, and is actually what you're asked to prove.
|
Korea (South)1888 Posts
Once again I demonstrate my math illiteracy.
Someone mentioned that if the fields are the same, the polynomials of f and g can be proven to be of the same degree.
What if f(x) = x, and g(x) = x^3? The images of both functions are all reals, and they are not of the same degree.
|
On September 12 2010 04:21 BottleAbuser wrote:
Once again I demonstrate my math illiteracy.
Someone mentioned that if the fields are the same, the polynomials of f and g can be proven to be of the same degree.
What if f(x) = x, and g(x) = x^3? The images of both functions are all reals, and they are not of the same degree.
Images over the rational numbers, my friend, over the rational numbers. And I already remarked that you can easily find counter examples over the reals or over the complex
|
On September 12 2010 04:21 BottleAbuser wrote:
Once again I demonstrate my math illiteracy.
Someone mentioned that if the fields are the same, the polynomials of f and g can be proven to be of the same degree.
What if f(x) = x, and g(x) = x^3? The images of both functions are all reals, and they are not of the same degree.
Your choice of f and g does not satisfy the hypothesis he is given. He said f(Q) must equal to g(Q). For your f and g, they are definitely not equal.
In particular, g(Q) is smaller in your case. For example, your g(Q) does not include 2, since there is no rational number whose cube is equal to 2.
Anyways, it's a shame that I am not quite sure how to do this problem nor even understand some of the discussions (although I do have a master degree in mathematics). I have always been somewhat an analyst than an algebraist .
|
Quite stumped with this problem right now. The problem is just the approach to use...The only sort of strategy I've had that seems like it might possibly get anywhere is as follows:
For each rational number x, there is a rational q s.t. f(x)=g(q). If we fix some rational x_0 and restrict to a small neighbourhood in which g is injective, we can define a function h on the rationals such that for every x
g(h(x))=f(x)
Now we'd be done if we can show that h is a polynomial and deg(g)=deg(f), but I dunno if this can be done in any easy way. Showing that h is a polynomial might involve using an argument with the chain rule, but I'm not sure.
I'll think some more but I don't seem to be getting anywhere so far @_@
EDIT: Note by the way that when you restrict to a neighbourhood of x_0 you can WLOG assume that f(x_0)=g(x_0), which may help. My geometric intuition is that if you normalize like this and then look at a rational close to x_0, then f and g must vary continuously and furthermore they have to vary in more or less the same way. But this intuition is too general and is not enough to pin down the solution...
|
On September 12 2010 06:00 KristianJS wrote:
Quite stumped with this problem right now. The problem is just the approach to use...The only sort of strategy I've had that seems like it might possibly get anywhere is as follows:
For each rational number x, there is a rational q s.t. f(x)=g(q). If we fix some rational x_0 and restrict to a small neighbourhood in which g is injective, we can define a function h on the rationals such that for every x
g(h(x))=f(x)
Now we'd be done if we can show that h is a polynomial and deg(g)=deg(f), but I dunno if this can be done in any easy way. Showing that h is a polynomial might involve using an argument with the chain rule, but I'm not sure.
I'll think some more but I don't seem to be getting anywhere so far @_@
EDIT: Note by the way that when you restrict to a neighbourhood of x_0 you can WLOG assume that f(x_0)=g(x_0), which may help. My geometric intuition is that if you normalize like this and then look at a rational close to x_0, then f and g must vary continuously and furthermore they have to vary in more or less the same way. But this intuition is too general and is not enough to pin down the solution...
You can look at it locally at each point, or look at what happens when x and q get very large (from f(x) = g(q)), and perhaps this might give an idea how to show deg f = deg g.
|
On September 12 2010 06:00 KristianJS wrote:
Quite stumped with this problem right now. The problem is just the approach to use...The only sort of strategy I've had that seems like it might possibly get anywhere is as follows:
For each rational number x, there is a rational q s.t. f(x)=g(q). If we fix some rational x_0 and restrict to a small neighbourhood in which g is injective, we can define a function h on the rationals such that for every x
g(h(x))=f(x)
Now we'd be done if we can show that h is a polynomial and deg(g)=deg(f), but I dunno if this can be done in any easy way. Showing that h is a polynomial might involve using an argument with the chain rule, but I'm not sure.
I'll think some more but I don't seem to be getting anywhere so far @_@
EDIT: Note by the way that when you restrict to a neighbourhood of x_0 you can WLOG assume that f(x_0)=g(x_0), which may help. My geometric intuition is that if you normalize like this and then look at a rational close to x_0, then f and g must vary continuously and furthermore they have to vary in more or less the same way. But this intuition is too general and is not enough to pin down the solution...
How about thinking along this line: modulus some details omitted, you can find a global function h(x) for x sufficiently large, so that g(h(x)) = f(x) (as you have written). Clearly |h(x)| -> infinity as x -> infinity. Assume for now h(x) > 0 for x sufficiently large, and start going through integer values of x as x -> infinity. The rational root theorem guarantees that h(x) will always lie in some fixed discrete subgroup of Q (in fact (1/a)*Z where a is the leading coefficient of g).
|
Solution
The idea is that (mod the full details) there's a fixed discrete subgroup L of Q such that for any integer x, the rational solutions, viewed in y, of g(y) = f(x) are all in L. To extract the behavior of y as x varies, and compare the coefficients at the same time, i.e. the growth rates, you can consider expressions of the form g(y') - g(y) = f(x+1) - f(x) where y' is the corresponding rational number such that g(y') = f(x+1). By mean value theorem (don't quite need this, since f,g are polynomials so one can potentially do all the computations by algebra) the expression extracts out y' - y in terms of f'(x) and g'(y) roughly, and this gives a good comparison of y as x varies. This is the idea, and I do some computations to show that this works.
Also, simple valuation calculations (plug in this, plug in that rational number, compare the p-adic valuations) don't really seem to get anywhere, as I give plenty of counter examples to the claims of one of the posters above.
|
I have to admit that the solution to this problem eluded me. I was probably a bit too reluctant to actually start manipulating polynomial expressions and looking for too slick a proof. A nice problem though!
|
So, given that f(x) and g(y) have congruent ranges, prove that they are linear transformations of each other???
Take f(x) = x^3 + 4x and g(x) = x^3 + x^2 - 2x.
Do these functions satisfy the conditions given in the problem?
(for what values of a,b?)
|
On September 13 2010 06:35 gyth wrote:
So, given that f(x) and g(y) have congruent ranges, prove that they are linear transformations of each other???
Yes, that there's an affine coordinate change, y = ax + b
Take f(x) = x^3 + 4x and g(x) = x^3 + x^2 - 2x.
Do these functions satisfy the conditions given in the problem?
(for what values of a,b?)
They don't. But that's a specific counter-example to Muirhead's claim (one of the two). What he wrote is that either v(f(x)) <= 0 or v(f(x)) >= 2, and v(g(p)) is not in that range, with p = 2, based on v(4) = 2 and v(2) = 1. Read what he wrote above. He was claiming in general that if p^r exactly divides a_1 but not b_1 then v(f(x)) <= 0 or v(f(x)) >= 2 and v(g(p)) > 1 and v(g(p)) <= 2. This example certainly has v(g(p)) = 3 though.
The other example, a better one, is g(x) = x^3 + x^2 - 2x and g(x+1) = x^3 + 4x^2 + 3x. Clearly g(x) and g(x+1) share the same image on the ratoinals, but look at the coefficients of g(x+1) and g(x). 3 and -2 have different p-adic valuations for p = 3 and p = 2. Again, read what he proposed as a solution above.
What he thought is that if the coefficients of least degree are not the same (or rather, differ by more than a multiplicative unit of Z, plus/minus 1), then you can find a prime p so that the p-adic valuations of f(x) are always within certain range, and g(p) would not fall within that range. This is *not* true. The second example is actually good enough to kill this type of argument. I left the first example there to make a point that one can write down polynomials randomly and invalidate his argument.
There are some other flaws in his argument, and one crucial flaw among them is that he's trying to prove a_i = +/- b_i for each i. Immediately, you can see something is dead off. But we like to play devil's advocate and assume that for a bit. That's still nowhere near close to proving that f(x) = g(ax + b) for some a,b. You can cook up plenty of examples very easily where f(x) never has the form g(ax + b) and yet the coefficients of f(x) are +/- of corresponding coefficients of g(x).
|
On September 13 2010 05:31 KristianJS wrote:
I have to admit that the solution to this problem eluded me. I was probably a bit too reluctant to actually start manipulating polynomial expressions and looking for too slick a proof. A nice problem though!
Thanks. I'm glad that you were having fun! That is the point of my starting this thread in the first place anyway. I tried to put an interesting fact/problem so more people could enjoy. Maybe I should have waited a big longer to release the solution and you could've produced a proof as well. But then again, Monday is coming up and we'll all be busy, so I felt I should release my solution today.
Maybe a short proof exists, and I have some vague ideas thinking of line bundles, but this will have to wait it seems.
Unlike IMO problems where short solutions exist and one only needs to try some limited number of techniques mixed together, this one actually I think inevitably would require a lot of technical digging if one wants to stick to elementary methods.
When I was involved in IMO back in the days (back then was still Titu coaching MO stuff. Kind of a strange guy.. but a good coach w/e) we would practice with problems from shortlist or longlist, and some of them had solutions that were quite long, really pushing one's technical mastery of the techniques (high school techniques albeit). I got this problem back then and I was proud that I was the only high schooler who could solve this problem in the black team. That didn't help the fact that I was an illegal resident and was not allowed to travel out . .
|
|
|
|
|
|
EPT
