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