Author |
Topic: LINEAR FUNCTION (Read 1275 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
LINEAR FUNCTION
« on: Oct 16th, 2002, 8:11pm » |
 Quote  Modify
|
Here's a good one I found among the Putnam exams...
Suppose g is a real-valued continuous function of one variable such that
g(g(x)) = a*g(x) + bx for all real x,
where a,b are real numbers lying in the open interval (0,1/2).
Prove that g(x) = cx for some constant c.
|
| « Last Edit: Dec 10th, 2002, 8:38am by Pietro K.C. » |
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: LINEAR FUNCTION
« Reply #1 on: Sep 11th, 2006, 3:51pm » |
Quote Modify
|
Since this has been sitting for nearly 4 years, I thought I would post a step along the way:
Choose an arbitrary x0 and define xn = g(xn-1) for all n. Note that {xn} satisfies xn+2 = axn+1 + bxn. Hence xn = Arn + Bsn, where A and B are constants depending on the choice of x0, and r, s are the roots of the characteristic equation r2 - ar - b = 0. The condition that 0 < a,b < 1/2 implies that -sqrt(2)/2 < r,s < 1. It follows that xn --> 0 as n --> oo. Taking the limit in the defining equation xn = g(xn-1) gives g(0) = 0.
Also, if g(x) = y, then g(y) = ay + bx, and hence x = (g(y) - ay)/b. So g is invertible.
|
|
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
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: LINEAR FUNCTION
« Reply #2 on: Sep 12th, 2006, 4:53am » |
Quote Modify
|
Here's the rest of the proof:
| hidden: |
Since g is one-to-one and continuous, it is strictly monotonic. Suppose that both A and B are not zero. Note that the positive root of the characteristic equation has greater magnitude than the negative one. So xn becomes dominated by the larger root as n goes to infinity, and so eventually has the same sign. So g must be increasing. Now define yn by y0 = x0, and yn+1 = g-1(yn). Then yn = A(1/r)n + B(1/s)n. Now the negative root dominates, so yn eventually alternates sign. So g is decreasing, a contradiction.
So g(x) = rx or g(x) = sx for all x. If g is increasing, then g(x) = rx for all x; if g is decreasing, then g(x) = sx for all x. |
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: LINEAR FUNCTION
« Reply #3 on: Sep 12th, 2006, 4:11pm » |
Quote Modify
|
Nice. The next question is:
What happens if we loosen the condition that a, b are between 0 and 1/2? Are there other continuous functions that satisfy g(g(x)) = g(x) + x, for instance?
|
|
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
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: LINEAR FUNCTION
« Reply #4 on: Sep 13th, 2006, 2:27pm » |
Quote Modify
|
I just noticed there's a hole in our proof; we don't know just from x = (g(y) - ay)/b that g is fully invertible, since the equation only holds for y in the image of f.
We can patch it up as follows: If g is not surjective, then by continuity we have either that limx -> infinity g(x) = c for some finite c, or limx -> -infinity g(x) = c. In the first case, for any e > 0, sufficiently large x implies that bx = g(g(x)) - a g(x) < c + e - a (c - e), a contradiction. In the second case we get bx > c - e - a (c + e).
Of course this could have all been intuitively obvious to you.
It looks like that the facts about a and b that we used were that b != 0, for injectivity, and that the roots of x^2 - ax - b were unequal in magnitude, of opposite sign (so b > 0), and bounded between -1 and 1.
Suppose that we remove that last requirement. We still have the fact the the sequence we defined above is eventually always alternating in one direction, and this means that g must not be increasing. However, the fact that the sequence is eventually always positive in the other direction doesn't seem to contradict g being decreasing. However, a decreasing g can have only one accumulation point, and it couldn't be zero. If the positive root is not equal to 1, the sequence must eventually go to either zero or infinity; so the only possibility is that the positive root is 1.
This takes care of g(g(x)) = g(x) + x, whose characteristic equation has roots phi and 1 - phi.
What about when the positive root is 1? Then the equation becomes g(g(x)) = (1-b)g(x) + bx. Any function of the form g(x) = c - bx will satisfy this equation. This remains true if b is negative. Are these the only other solutions?
Edit: Yes. Any decreasing solution g has a unique fixed point c. Assume without loss of generality that the negative root is greater than -1, so that the postive root dominates. (if not, replace g with g-1.) Then c is the accumulation point. So for any x we have x = c + d, g(x) = c - bd. So h(x) = g(x) - c satisfies h(x) = bx, as desired.
|
| « Last Edit: Sep 13th, 2006, 6:00pm by Icarus » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: LINEAR FUNCTION
« Reply #5 on: Sep 13th, 2006, 6:59pm » |
Quote Modify
|
I hadn't noticed that your proof relied on g being surjective. So, no, it is not intuitively obvious to me either. (Let me note here that I hadn't gotten any farther than what I had posted before, so the proof is yours.)
The case when b = 0 has only minor interest: One merely has to identify an interval closed under multiplication by a: if a < 0, these consist of (-oo, K) U (K, oo) and (-K, K) (open or closed is immaterial here, and K >=0 is arbitrary). If a>0, you can also have just the positive or just the negative sides. Choose one of these intervals and any continuous function g mapping the remainder of the line into your chosen set. Within the interval, define g(x) = ax. All solutions are of this form.
What happens when b < 0?
|
|
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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print