Author |
Topic: Find the Function: f(f(x)) = x^2 - 2 (Read 6836 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Find the Function: f(f(x)) = x^2 - 2
« on: Feb 20th, 2004, 1:02am » |
 Quote  Modify
|
Find a function f such that f(f(x)) = x2 - 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.
|
| « Last Edit: Feb 20th, 2004, 1:05am by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
KarmaBandit
Newbie
Gender:
Posts: 16
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #1 on: Feb 21st, 2004, 10:29am » |
Quote Modify
|
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 x2 - 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 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #2 on: Feb 22nd, 2004, 11:36am » |
Quote Modify
|
if f(f(x))=x2-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 - 2).
It'd be easier if f(f(x))=x2, then f(x) = xsqrt(2)
Of course neither is the case, so I'm stumped..
|
| « Last Edit: Feb 22nd, 2004, 11:36am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
KarmaBandit
Newbie
Gender:
Posts: 16
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #3 on: Feb 22nd, 2004, 12:53pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #4 on: Feb 22nd, 2004, 3:11pm » |
Quote Modify
|
on Feb 22nd, 2004, 12:53pm, 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)) = x2-2 to only x [in][bbr].
So the function is well-defined for [bbc], but f(f(x)) = x2-2 simply doesn't hold for other x [notin] [bbr].
|
| « Last Edit: Feb 22nd, 2004, 3:16pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
KarmaBandit
Newbie
Gender:
Posts: 16
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #5 on: Feb 22nd, 2004, 8:10pm » |
Quote Modify
|
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*
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #6 on: Feb 23rd, 2004, 12:31am » |
Quote Modify
|
What about if we take f:[bbz][to][bbz] ?
::
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)
::
|
| « Last Edit: Feb 23rd, 2004, 12:38am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #7 on: Feb 23rd, 2004, 5:32am » |
Quote Modify
|
on Feb 22nd, 2004, 12:53pm, 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 Feb 21st, 2004, 10:29am, 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]
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(x2-2). Recall that cos(2x) = 2cos2(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)2 – k
= x2 – 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.
[smiley=blacksquare.gif]
|
| « Last Edit: Feb 23rd, 2004, 5:34am by Barukh » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2874
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #8 on: Feb 23rd, 2004, 6:06am » |
Quote Modify
|
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:
::
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))=j2-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))=x2-2 for all integers, with f(x)>=-1
::
[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]
|
| « Last Edit: Feb 23rd, 2004, 6:13am by rmsgrey » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #9 on: Feb 23rd, 2004, 7:17am » |
Quote Modify
|
(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 Feb 23rd, 2004, 5:32am, 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..
|
| « Last Edit: Feb 23rd, 2004, 7:24am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #10 on: Feb 23rd, 2004, 9:56am » |
Quote Modify
|
on Feb 23rd, 2004, 7:17am, 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 -2.
The case x- is even more formal.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #11 on: Feb 23rd, 2004, 10:48am » |
Quote Modify
|
on Feb 23rd, 2004, 9:56am, 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 )
|
| « Last Edit: Feb 23rd, 2004, 11:00am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
KarmaBandit
Newbie
Gender:
Posts: 16
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #12 on: Feb 23rd, 2004, 6:03pm » |
Quote Modify
|
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)) = x2 - a.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #13 on: Feb 24th, 2004, 9:33am » |
Quote Modify
|
on Feb 23rd, 2004, 10:48am, 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):
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 - 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?..
|
|
IP Logged |
|
|
|
KarmaBandit
Newbie
Gender:
Posts: 16
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #14 on: Feb 24th, 2004, 6:57pm » |
Quote Modify
|
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: fn(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!
|
| « Last Edit: Feb 24th, 2004, 7:13pm by KarmaBandit » |
IP Logged |
|
|
|
pcbouhid
Uberpuzzler
Gender:
Posts: 647
|
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//
|
| « Last Edit: Nov 12th, 2005, 6:21am by Icarus » |
IP Logged |
Don´t follow me, I´m lost too.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #16 on: Nov 12th, 2005, 6:39am » |
Quote Modify
|
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.
|
|
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
|
|
|
pcbouhid
Uberpuzzler
Gender:
Posts: 647
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #17 on: Nov 16th, 2005, 4:26am » |
Quote Modify
|
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.
|
|
IP Logged |
Don´t follow me, I´m lost too.
|
|
|
Joe Fendel
Junior Member
Posts: 68
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #18 on: Nov 16th, 2005, 4:06pm » |
Quote Modify
|
on Feb 23rd, 2004, 12:31am, towr wrote:What about if we take f:[bbz][to][bbz] ?
::
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)
:: |
|
Yes, it can be extended inductively on [bbz]:
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, ...
|
|
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #19 on: Nov 29th, 2005, 10:03am » |
Quote Modify
|
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.
|
| « Last Edit: Nov 30th, 2005, 6:36pm by Michael Dagg » |
IP Logged |
Regards,
Michael Dagg
|
|
|
paul_h
Guest
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #20 on: Nov 29th, 2005, 3:26pm » |
Quote Modify
 Remove
|
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.
|
|
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #21 on: Nov 29th, 2005, 6:36pm » |
Quote Modify
|
What I said was [referring to previous development], my statement does not mean that the problem [has] a complex-analytic solution.
|
| « Last Edit: Nov 30th, 2005, 3:42am by Michael Dagg » |
IP Logged |
Regards,
Michael Dagg
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #22 on: Nov 29th, 2005, 7:24pm » |
Quote Modify
|
on Nov 29th, 2005, 3:26pm, 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 Rn --> Rn 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 S2 = D. Define f = GSG-1. Then:
f2 = GSG-1GSG-1 = GS2G-1 = GDG-1 = F. I.e. f(f(x)) = x2 - 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)) = x2 - 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 S2 = 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.//
|
| « Last Edit: Nov 29th, 2005, 7:28pm by Icarus » |
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
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #23 on: Nov 29th, 2005, 7:58pm » |
Quote Modify
|
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.
|
|
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
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Find the Function: f(f(x)) = x^2 - 2
« Reply #24 on: Nov 30th, 2005, 3:24pm » |
Quote Modify
|
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.
|
|
IP Logged |
Regards,
Michael Dagg
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
PROOF_OF_x2_-2.doc