wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> LINEAR FUNCTION
        
(Message started by: Pietro K.C. on Oct 16^th, 2002, 8:11pm)

Title: LINEAR FUNCTION
Post by Pietro K.C. on Oct 16^th, 2002, 8:11pm

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.

Title: Re: LINEAR FUNCTION
Post by Icarus on Sep 11^th, 2006, 3:51pm

Since this has been sitting for nearly 4 years, I thought I would post a step along the way:

Choose an arbitrary x₀ and define x_n = g(x_n-1) for all n. Note that {x_n} satisfies x_n+2 = ax_n+1 + bx_n. Hence x_n = Arⁿ + Bsⁿ, where A and B are constants depending on the choice of x₀, and r, s are the roots of the characteristic equation r² - ar - b = 0. The condition that 0 < a,b < 1/2 implies that -sqrt(2)/2 < r,s < 1. It follows that x_n --> 0 as n --> oo. Taking the limit in the defining equation x_n = g(x_n-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.

Title: Re: LINEAR FUNCTION
Post by Deedlit on Sep 12^th, 2006, 4:53am

Here's the rest of the proof:

[hideb]
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 x_n 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 y_n by y₀ = x₀, and y_n+1 = g^-1(y_n). Then y_n = A(1/r)ⁿ + B(1/s)ⁿ. Now the negative root dominates, so y_n 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.[/hideb]

Title: Re: LINEAR FUNCTION
Post by Icarus on Sep 12^th, 2006, 4:11pm

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?

Title: Re: LINEAR FUNCTION
Post by Deedlit on Sep 13^th, 2006, 2:27pm

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 lim_{x -> infinity} g(x) = c for some finite c, or lim_{x -> -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.

Title: Re: LINEAR FUNCTION
Post by Icarus on Sep 13^th, 2006, 6:59pm

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?