wu :: forums - Print Page


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

        riddles >> hard >> Find the Function: f(f(x)) = x^2 - 2
        
(Message started by: william wu on Feb 20^th, 2004, 1:02am)

Title: Find the Function: f(f(x)) = x^2 - 2
Post by william wu on Feb 20^th, 2004, 1:02am

Find a function f such that f(f(x)) = x² - 2.

Note: Don't the answer to this one, but the source is quite esteemed so I'm sure an answer exists. Don't know anything more than the above sentence -- the sets involved could be complex.

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by KarmaBandit on Feb 21^st, 2004, 10:29am

Well, there may be a function that satisfies that, but the domain is not all of [smiley=bbr.gif]. In particular, x cannot be (-1 + [smiley=surd.gif] 5)/2. (If someone knows how to hide this stuff, feel free to edit this post.)

From now on I will refer to (-1 + [smiley=surd.gif] 5)/2 as x₊ and (-1 - [smiley=surd.gif] 5)/2 as x_-.

Let's first find the values such that f(f(x)) = x. This implies that x² - 2 = x. You can check that the only values that satisfy this are 2 and -1. Next, let's find the values such that f(f(f(f(x)))) = x. Again, you can check that the values are 2, -1, x₊, and x_-.

Finally, note that if f(f(f(f(x)))) = x, then f(f(f(f(f(x))))) = f(x); which implies that f(x) is also one of 2, -1, x₊, and x_-. So, now I will show that if x = x₊, then f(x₊) cannot be any of those four, a contradiction.

So, first if f(x₊) = x₊, then we'd also have that f(f(x₊)) = x₊. But we already know the only two values that satisfy that: 2 and -1. So, that doesn't work.

Next, if f(x₊) = 2, then we'd have f(f(f(x₊) = f(f(2)) = 2. That implies that x₊ = f(f(f(f(x₊)))) = f(2). Returning now to f(f(x₊)) = f(2) = x₊, we get the same contradiction as above.

With f(x₊) = -1, the proof is exactly the same as with f(x₊) = 2, above.

Finally, the slightly nontrivial case f(x₊) = x_-. Unfortunately, we now have to build up the four possible cases of f(f(x₊)) and show that none of those are possible. But the recursion will stop there, so hang on.

First, if f(f(x₊)) = x₊, then we get our favorite old contradiction.

Next, if f(f(x₊)) = 2, then applying f twice more would imply that x₊ = 2, which is not true.

Same argument holds for f(f(x₊)) = -1, as usual.

Finally, if f(f(x₊)) = x_-, then that implies that f(x_-) = x_-. Well, applying f a few more times until it loops back to x₊ would imply that x₊ = x_-, a contradiction.

Whew! So, x cannot be x₊, and thus the domain of f cannot be all of [smiley=bbr.gif]. I checked all of my ()'s and f's, but tell me if I made any mistakes... and that includes whether my proof turns out to be garbage :-)

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by towr on Feb 22^nd, 2004, 11:36am

if f(f(x))=x²-2 only had to hold for x [in] [bbr] it wouldn't be to hard.. I could use f(x) = im(x) + i*(re(x)² - 2).
It'd be easier if f(f(x))=x², then f(x) = x^sqrt(2)
Of course neither is the case, so I'm stumped..

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by KarmaBandit on Feb 22^nd, 2004, 12:53pm

That's a really nice function, towr, and is probably as close as we'll get. It floored me for a minute, because I thought I had shown that was impossible. Like you said, though, it only "works" when you restrict the domain to [smiley=bbr.gif]. But when you do that, the operation f(f(x)) suddenly becomes ill-defined since the second f() operates on a pure imaginary number, which is not in the set of things it can act on...

With the assumption that f(x) is still in the domain of f(), as I assumed above, I showed that there are real numbers that simply cannot be in the domain. In my book, that means there is no good function to answer this problem.

If we have to start specifying the domain to be weird things, let me be the first to offer this: f(x) = x, and it's domain is {2}, a single number.

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by towr on Feb 22^nd, 2004, 3:11pm

on 02/22/04 at 12:53:27, KarmaBandit wrote:

That's a really nice function, towr, and is probably as close as we'll get. It floored me for a minute, because I thought I had shown that was impossible.

I think your right. It took me a while to understand your whole proof, but I think it's correct.

[e]after some googling I found http://www.obm.org.br/eureka/eureka17.pdf
which has the same problem, and if my understanding of brazilian portugese isn't totally off also the same solution (pg 42/44)..[/e]

Quote:

Like you said, though, it only "works" when you restrict the domain to [smiley=bbr.gif]. But when you do that, the operation f(f(x)) suddenly becomes ill-defined since the second f() operates on a pure imaginary number, which is not in the set of things it can act on...

I don't so much restrict the domain of f to [bbr], as the condition of f(f(x)) = x²-2 to only x [in][bbr].
So the function is well-defined for [bbc], but f(f(x)) = x²-2 simply doesn't hold for other x [notin] [bbr].

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by KarmaBandit on Feb 22^nd, 2004, 8:10pm

Good find on google too! That's exactly where I copied my post from :-)

If at first you can't succeed, google and take the credit! Err, something like that, anyway... *hides*

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by towr on Feb 23^rd, 2004, 12:31am

What about if we take f:[bbz][to][bbz] ?
::[hide]
just to start of with
f:{-2,-1,0,1,2} -> {-2,-1,0,1,2}
f(0) = 1
f(1) = -2
f(-2) = -1
f(-1) = 2
f(2) = -1

It's a matter of making the correct graph, can this be extended to [bbz] ? I think so.
We could also try guassian integers (a+bi, where a and b are integers)
[/hide]::

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by Barukh on Feb 23^rd, 2004, 5:32am

on 02/22/04 at 12:53:27, KarmaBandit wrote:

…I thought I had shown that was impossible…

I think your demonstration is wrong. Here’s the place in your proof which seems unjustified:

on 02/21/04 at 10:29:35, KarmaBandit wrote:

Finally, note that if f(f(f(f(x)))) = x, then f(f(f(f(f(x))))) = f(x); which implies that f(x) is also one of 2, -1, x₊, and x_-.

Why?

The following is a solution for f: [smiley=bbr.gif][smiley=to.gif] [smiley=bbr.gif] and it shows there's nothing special with x₊, and x_- (In fact, that’s reverse engineering: first, I saw the answer in another forum, and then tried to reconstruct the possible reasoning).

[smiley=blacksquare.gif][hide]
Assume that f(x) has an inverse function, f^-1(x). Then, the problem becomes to find f(x) such that f(x) = f^-1(x²-2). Recall that cos(2x) = 2cos²(x) – 1; this “suggests” to look for f(x) ~ cos(2g(x)) and f^-1(x) ~ cos(g(x)). Thus we arrive at: f(x) = k cos([sqrt]2arrcos(x/k)). Solve for k:
f(f(x)) = k cos([sqrt]2arccos(cos([sqrt]2arccos(x/k)))
= k cos(2arccos(x/k))
= 2k (x/k)² – k
= x² – 2,
so k = 2 (note that we are just lucky; take another number instead of 2 and see there won’t be a solution).

Note that this function is defined only for |x| <= 2. Fortunately, if |x| > 2, we may use hyperbolic cosine cosh(x) which obeys the same double-angle identity. Finally, we have:
f(x) = 2 cos([sqrt]2arccos(x/2)), |x| <= 2,
f(x) = 2 cosh([sqrt]2arccosh(|x|/2)), |x| > 2.
[/hide][smiley=blacksquare.gif]

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by rmsgrey on Feb 23^rd, 2004, 6:06am

As an observation, it seems like we should be able to choose f such that f(-x)=f(x) since f(f(-x))=f(f(x)). For instance, replacing f(1)=-2 with f(1)=2 in Towr's function makes it hold. Extending Towr's function is simple enough:
::[hide]
between consecutive values which are f(f(x)) there are always an even number of integers which are not. By pairing them off so that f(x)=x+1 and f(x+1)=f(f(x)) for each pair (x,x+1) we get a function that maps every integer which isn't f(f(x)) for some x onto some other integer with f(x)>x for x>2. To assign the rest, we need only observe that the least value, k, for which f(k) is undefined is of the form f(j=f(i)) for some i<j<k so f(k) must be f(f(j))=j²-2. By repeating this for each least element, the desired function f can be constructed for all x>2. Including Towr's function for -3<x<3 (changing it so f(1)=2) and setting f(x)=f(-x) for x<-3 gives a function which has f(-x)=f(x) and f(f(x))=x²-2 for all integers, with f(x)>=-1
[/hide]::
[e]OK, Barukh's managed to find an explicit function on [bbr], so my construction on [bbz] is obsolete - just take the intersection of his function with [bbz]. At least his function is even, so I was right about that (even if I have no support for my reasoning to get there)[/e]

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by towr on Feb 23^rd, 2004, 7:17am

(sigh finally, the problem resolved itself, and I can post here again.. stupid thread, pretending not to exist when I try to post, for at least half an hour. Yet still readable, taunting me.. grr)

on 02/23/04 at 05:32:54, Barukh wrote:

I think your demonstration is wrong. Here’s the place in your proof which seems unjustified:

Why?

because you can replace x in ffff(x)=x, by f(y) to get fffff(y)=f(y)
I was stuck there a few times as well..

And try filling in -[sqrt]5/2 - 1/2 into your function..
I get f(f(-[sqrt]5/2 - 1/2) = 2 cos([pi] (2 [sqrt]2 + 2/5)) [ne] [sqrt]5/2 - 1/2
-2 doesn't seem to work either..

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by Barukh on Feb 23^rd, 2004, 9:56am

on 02/23/04 at 07:17:30, towr wrote:

because you can replace x in ffff(x)=x, by f(y) to get fffff(y)=f(y)
I was stuck there a few times as well..

Sorry, still doesn't make sense to me... ::)

Quote:

And try filling in -[sqrt]5/2 - 1/2 into your function..
I get f(f(-[sqrt]5/2 - 1/2) = 2 cos([pi] (2 [sqrt]2 + 2/5)) [ne] [sqrt]5/2 - 1/2
-2 doesn't seem to work either..

towr, I don't know how did you get the values, but if you wrote a program, beware that you probably won't get correspondence for every x, such that [sqrt]2acos(x/2) > [pi] - that's because of principal values the functions return.

Also, did it work for (-1 + [sqrt]5)/2? If yes, the proof should have a flaw in it!

That the function is suitable for, let's say -2, here's again the symbolic derivation:

f(f(-2)) = 2cos([sqrt]2acos(2cos([sqrt]2acos(-2/2))/2))
= 2cos([sqrt]2acos(cos([sqrt]2[pi])))
= 2cos([sqrt]2[sqrt]2[pi])
= 2cos(2[pi])
= 2 = (-2)² -2.

The case x_- is even more formal.

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by towr on Feb 23^rd, 2004, 10:48am

on 02/23/04 at 09:56:24, Barukh wrote:

Sorry, still doesn't make sense to me... ::)

If f(f(f(f(x)))) = x implies x [in] {-[phi], -1, [phi]-1, 2} (which was adequately shown)
then f(f(f(f(f(y))))) = f(y) implies also f(y) [in] {-[phi], -1, [phi]-1, 2} and since this is equivalent to f(f(f(f(f(x))))) = f(x), this means y [in] {-[phi], -1, [phi]-1, 2} as well
I don't see what's the problem here..

([phi] is of course the golden ratio )

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by KarmaBandit on Feb 23^rd, 2004, 6:03pm

OK, I'll take a shot at explaning that line also-- since I also got stumped on it for awhile (and it was in Italian or something also!)

So you buy the line about f(f(f(f(x)))) = x [smiley=bigto.gif] x [smiley=in.gif] {-1, 2, x_-, x₊}, right?

The conclusion about f(x) follows by first acting on both sides again with f(), yielding: f(f(f(f(f(x))))) = f(x).

Now, call f(x) = y. Rewriting that last line, f(f(f(f(y)))) = y. But, we've seen this before and it implies that y [smiley=in.gif] {-1, 2, x_-, x₊}. QED.

This is an important step, since it shows that the function acting on any of those numbers will just cycle you back to one of those numbers again. I bet this is a general approach for problems of this type, and could perhaps give us some info about f(f(x)) = x² - a.

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by Barukh on Feb 24^th, 2004, 9:33am

on 02/23/04 at 10:48:47, towr wrote:

I don't see what's the problem here..

The problem is that I am too stupid! Thank you (and Karmabandit) for pointing this out...

OK, now I have this proof that there cannot be such an f: [smiley=bbr.gif][smiley=to.gif][smiley=bbr.gif], with certain values explicitly given; on the other hand, there is this f: [smiley=bbr.gif][smiley=to.gif][smiley=bbr.gif], given in my post, which - analytically - gives the desired result for every x!

How to reconcile these two contradictory results? ::) The best way I've found is that my 'f' is not actually a function, but a multivalued relation, that is, for every x it takes several (in fact, infinitely many) values. This is because acos() is multivalued. More than that, to actually get the properties stated in the problem and proved in Karma's theorem, we actually need to choose the values differently at different steps!

Let me illustrate this with x₊ (all the computations performed using Google Calculator (http://www.google.com/help/features.html#calculator)):

x = x₊ = (-1 + sqrt(5)) / 2 = 0.618033989
f(x) = 2 * cos(sqrt(2) * acos(0.618033989 / 2)) = -0.409790819
f(f(x)) = 2 * cos(sqrt(2) * acos(-0.409790819 / 2)) = -1.61803399 = x₊² - 2 = x_-
f(f(f(x))) = 2 * cos(sqrt(2) * (acos(-1.61803399 / 2) - pi)) = 1.26103497
f(f(f(f(x)))) = 2 * cos(sqrt(2) * acos(1.26103497 / 2)) = 0.618033999 = x₊.

Note the "- pi" term in the computation of f(f(f(x))) in order to get the desired result.

Any comments?..

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by KarmaBandit on Feb 24^th, 2004, 6:57pm

Well, Barukh, I think your function is great! Not only does it work right on x₊, but it also works right on f(x₊)! So, unlike my previous gripes with towr's function which acted on a member not in its domain, yours works great!

It appears that my proof relied heavily on my ability to throw an f() onto anything I wanted to, including f(f(x₊)). Without adding the "-pi" like you did, that number is not in the domain of your function. Since my proof relied on being able to do that in order to show that x₊ wasn't in the domain, the proof was wrong!

But, it can be saved. My goal wasn't really to show that x₊ isn't in the domain, but to show that some number is. So, as you pointed out, there are cases where other numbers aren't in the domain, but x₊ is! So, let's rephrase the result as: fⁿ(x₊) is not in the domain of f, for some small number n < 5. (That's f applied n times).

But, your function definitely disproved my post as stated! Good job!

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by pcbouhid on Nov 11^th, 2005, 8:30am

I have a proof that such functions doesn´t exist. But, I would need some few drawings that I can´t make here. Those who are interested in knowing it, feel free to write me : paulo.bouhid@globo.com, and I´ll sent it by email. BTW, I´m brazilian.

//Edited by Icarus to add attachment//

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by Icarus on Nov 12^th, 2005, 6:39am

Welcome to the wu forums, pcbouhid. I have added your proof (or actually, as you stated in your e-mail, the proof of some anonymous Brazilian student) as an attachment to your post. (I did make a few corrections in the translation into English, but all were very minor.)

You are not our first Brazilian contributor. In particular, Pietro K.C. is another Brazilian who has made substantial contributions (particularly, look for his posts here in the Hard forum, and in the Putnam forum - he has made several to the latter that have not be answered). Unfortunately, I haven't noticed anything from him in a while. Anyway, more Brazilian input is always welcome. One of the wonderful things about this community is that while the site itself is American, we make up only a small minority of the major contributors.

_______________________________________________________

For those unable to view the MS Word document, I will point that while nicely stated, it is essentially the same proof KarmaBandit has already given. I.e., it is a proof that no such function exists from all of R --> R, because there are certain values (the ones KarmaBandit pointed out) that cannot be in its domain.

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by pcbouhid on Nov 16^th, 2005, 4:26am

Tk you, Icarus, and as I said in my email to you, I intend to be a regular contributor, as I am in another site (an English site). Right now I´ll look for how to post a challenge, my first one. Cheers.

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by Joe Fendel on Nov 16^th, 2005, 4:06pm

on 02/23/04 at 00:31:03, towr wrote:

Yes, it can be extended inductively on [bbz]:

[hide]Start with your function on the integers of absolute value <= 2.

For integers x < -2, set f(x) = f(-x). Thus we can concentrate on only positive integers.

For x > 3, there are two cases:
1) If x = f(y) for some y between 2 and x, then f(x) = y^2 - 2.
2) Otherwise, f(x) is the smallest integer that is both
a. Greater than x and
b. Also not equal to f(y) for any y between 2 and x (exclusive).

Thus f(3) = f(-3) = 4, f(4) = f(-4) = 7, f(5) = f(-5) = 6, f(6) = f(-6) = 23, f(7) = f(-7) = 14, ...

[/hide]

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by Michael_Dagg on Nov 29^th, 2005, 10:03am

That particular right-hand side shows up a lot in various contexts, e.g. the Chebyshev polynomials and trig identities. If F(x) = x^2 - 2, then F(2cos(u)) = 4cos^2(u) - 2 = 2(cos(2u)).

That is, if D(x) = 2x, and C(x) = cos(x), then F o D o C = D o C o D, or equivalently D^(-1) o F o D = C o D o C^(-1). If you know how conjugation works in group theory, you'll recognize an answer here: writing S(x) = sqrt(2) x, we have D = S o S so C o D o C^(-1) = (C o S o C^(-1)) o (C o S o C^(-1)), while if F = f o f, we have D^(-1) o F o D = (D^(-1) o f o D) o (D^(-1) o f o D). So you can solve the problem by letting (D^(-1) o f o D) = (C o S o C^(-1)), i.e. f = D o (C o S o C^(-1)) o D^(-1). That is, f(x) = 2cos(sqrt(2) * arccos(x/2)).

Indeed this answer checks out numerically - but only when -1.2<x<2 (approximately). For larger x, arccos(x/2) is undefined, and for smaller x, the values of f o f disagree with F because of ambiguity in choosing branches of the arccosine. This particular f is smooth near x=0 and so we may compute its Taylor series, which then defines a complex-analytic function on the region of convergence. When both x and f(x) lie in that region we will have f(f(x)) = x^2 - 2. But the Taylor series does not converge everywhere, which means this f does not extend to an analytic function on the whole complex plane.

This in itself does not mean that the problem has no complex-analytic solution, because (I guess) this f isn't the only one to have f o f = F locally. But I think one can still rule out the existence of an entire solution: it should be true that one can prove from Liouville's theorem that an entire function f for which f o f is a polynomial must itself be a polynomial (which is clearly not the case when f o f = x^2-2 ).

I don't know about solutions defined on the whole real line. I suspect there is none but it's very easy to get fooled by the analytic case. Without analyticity, there's much more manoeuvring room among real functions.

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by paul_h on Nov 29^th, 2005, 3:26pm

Geeish! I find it difficult to follow all those compositions so I did not bother. That function definitely works although the interval is limited.

But its the first explicit function shown thus far.

The fact of the existence of a complex solution is pretty darn interesting.

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by Michael_Dagg on Nov 29^th, 2005, 6:36pm

What I said was [referring to previous development], my statement does not mean that the problem [has] a complex-analytic solution.

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by Icarus on Nov 29^th, 2005, 7:24pm

on 11/29/05 at 15:26:39, paul_h wrote:

Geeish! I find it difficult to follow all those compositions so I did not bother.

It isn't that bad if you don't think of them as compositions, but rather as a non-commutative "multiplication" of functions - much like matrix multiplication, which is actually the composition of the linear maps from Rⁿ --> Rⁿ that the matrices represent.

The reasoning is also simplified a bit if you replace C = cos x with G = 2cos x. Then G^-1 = Arccos(x/2).

The identity that Dr. Dagg starts with is just FG = GD, so F = GDG^-1, and D = G^-1FG. Defining the function S(x) = sqrt(2)x, we see that S² = D. Define f = GSG^-1. Then:

f² = GSG^-1GSG^-1 = GS²G^-1 = GDG^-1 = F. I.e. f(f(x)) = x² - 2

In a group, the above logic is unassailable. Unfortunately, this is not in a group. In order for the logic to work, G must have a 2-sided inverse. It is obvious that GG^-1 = 2cos(Arccos(x/2)) = x. But the other direction is not so clear:
Arccos((2cos x)/2) = x + 2k[pi] for some integer k, with the value of k depending on the value of x, and the branch of the arccos function we've chosen.

(To avoid writing sqrt(2) everywhere, let q = sqrt(2).)

In order for everything to work, we must restrict the domain of cosine to only those values that match the branch of our Arccos function. (Call the restricted function Cos x, so f(x) = 2Cos(q Arccos(x/2)).) Then we have to restrict the domain of f so that that qArccos(x/2) will lie within the domain of Cos. Finally, the formula f(f(x)) = x² - 2 will only hold for x with the property that f(x) is in this restricted domain.

We start by assuming the standard branch for Arccos x. So
Cos x : [0, pi] --> [-1, 1]
Arccos x : [-1, 1] --> [0, pi].
We must have qArccos(x/2) <= pi. Since Cos is decreasing, x >= 2cos (pi/q) = -1.21.... So we define the domain of f to be [-1.21..., 2].

Lastly, we must have f(x) within the domain of f for the recursion formula to hold at x. So f(x) >= -1.21... (the upper limit is always satisfied). Arccos is also decreasing, so qArccos(x/2) <= Arccos (-0.605...), or Arccos (x/2) <= 1.5707... = pi/2. So x/2 >= cos(pi/2) = 0.

Thus the formula only holds for x in [0,2]. But it does hold for all x within that range.

________________________________________

Another consequence of Michael's calculation is that it is reversible. This means that if we were dealing with nice single-valued inverses, it would amount to a uniqueness proof as well, up to the uniqueness of the function S as the sole solution to S² = D (-S is also a solution, but -S gives us the same function f). If we require S to be continuous, I believe S and -S are the only solutions, and thus any continuous function f satisying the functional equation must be of the form f(x) = 2Cos(qArccos(x/2)), though possibly with different choices of domain and cosine branch.

//To show you how slow I can be at posting, when I started this post, Michael had not posted the reply that precedes it.//

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by Icarus on Nov 29^th, 2005, 7:58pm

Concerning the question of complex-analytic solutions. Any such solution must once again be of the form 2Cos(sqrt(2)Arccos(z/2)) for appropriate branches of those functions, and with z restricted to values for which f(z) is still within the domain of f. Without examing the question closely enough to be sure. I suspect you can get the functional equation to hold for all z within the half-strip {z c C : 0<= Re(z) <= 2, im(z) >= 0}.

And one should note that KarmaBandit/pcbouhid's proof (both obtained from Brazillian websites) does show that you cannot define a function f: R --> R (continuous or not) that satisfies the equation for every x in its domain. f(x) = 2Cos(sqrt(2)Arccos(x/2)) only works because for any x <> 2, f(f(f(...f(x))...) will eventually fall out of the domain. But if f is defined on all of R, this never occurs, and KarmaBandit's logic holds.

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by Michael_Dagg on Nov 30^th, 2005, 3:24pm

That is very good Icarus - you have great talent, and I know that members of this forum (including myself) appreciate your participation as moderator.

A couple of things I have noticed recently with the forum, besides it being slow, is words or several words being repeated when a post occurs. One of your posts (I think the one about the poles in contour integration) has a repeated sequence of words. Last evening I was looking for the thread entitled [differential equations on torus] and never could find it. I then search for it and the results contained what appeared to me as html tags in the link text instead of the thread/topic name. After I followed the link the thread appeared in the normal list. It is possible I actually missed seeing the thread in the list but nevertheless the search feature was returning garbage.

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by Icarus on Nov 30^th, 2005, 7:00pm

Thanks. In one of my posts, a more likely answer is my habit of posting without previewing, and my habit of constantly rephrasing. I often fail to completely delete the earlier phrasing, and as a result, odd bits tend to creep in that my editing misses as I am mentally anticipating, and miss the repetition or extraneous bits.

Unfortunately, moderating powers don't allow me to address the problems you've described (and if they did, I would have to defer to towr for them, as my html is only rudimentary, and I don't know java at all). Basically, all towr and I can do is modify or remove any post, lock and unlock threads (or make them "sticky"), and move threads to other forums. Anything more requires William, who hasn't been around much. His last post was Oct 3rd, and the one before that was May 27th.

________________________________________

As I have thought more about this problem today, I am less sure that S(x) = sqrt(2)x, and its opposite, are the only continuous, or even the only analytic, functions satisfying S(S(x)) = 2x. While I do not have another example for it, the similar equation g(g(x)) = x has an entire family of solutions that are analytic where they are defined. In addition to the obvious g(x) = x and g(x) = -x, all of the functions g(x) = a/x, with a <> 0, satisfy the functional equation.

I think I will post the question of uniqueness of S in the Putnam forum.

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by ace on Dec 3^rd, 2005, 12:26pm

That's nice. You see those kinds of exotic compositions in cohomology.

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by xxxx4eec on Dec 15^th, 2005, 3:10am

f(f(x))=x^2-2
tyr derivative!
f'(x)^2=2x
f'(x)=sqr(2x)
then integral!

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by towr on Dec 15^th, 2005, 3:55am

on 12/15/05 at 03:10:35, xxxx4eec wrote:

f(f(x))=x^2-2
tyr derivative!
f'(x)^2=2x
f'(x)=sqr(2x)
then integral!

except the derivitive isn't f'(x)^2=2x but f'(f(x))*f'(x)=2x

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by Michael_Dagg on Dec 21^st, 2005, 7:00am

While I have not been looking for a complex f satisfying f(f(z)) = z^2 - 2 for all z in C, I did mention my real solution to a colleague who recently sent me this note:

There is no entire function f such that f(f(z)) = z^2 - 2 for
all complex z. Take a look at (1.1) on the first page of the paper
by Walter Bergweiler entitled "Proof of a conjecture of Gross con-
cerning fixed-points", Mathematische Zeitschrift 204 (1990),381-390.
(Take alpha to be the constant function 0 and P(z) to be the poly-
nomial z^2 - z - 2.)

Edit again: Eigenray and I were posting at the same time. I removed the link to the paper since he provides it below.

Title: Re: Find the Function: f(f(x)) = x^2 - 2
Post by Eigenray on Dec 21^st, 2005, 7:17pm

The article Michael Dagg cites is available [link=http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D173519]online[/link].

I gave an argument [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1133407656]here[/link] that shows that if f is entire and f(f(z)) converges to infinity as z does, then f is a polynomial. It's based on the proof that the only entire univalent functions are linear.

Here's a surprising result: a quadratic polynomial p(z) defined on all of C has no iterative roots at all: there is no function f:C->C with f(f(z))=p(z) for all z. A proof (purely combinatorial) appears in "When is f(f(z)) = az² + bz + c?", R. E. Rice; B. Schweizer; A. Sklar. The American Mathematical Monthly, Vol. 87, No. 4. (Apr., 1980), pp. 252-263.

The case of R is different: writing p(x) = ax² + (b+1)x + c, then p has iterative roots f:R->R iff b²-4ac < 1.