Maths problem: if f(f(x)) = some given g(x), what is f(x) ?

[Nancarrow]

Hi, I came across a teaser on a maths website:

If f(f(x)) = x^4 - 4x^3 + 8x + 2, what is f(x)?

Well I solved it fairly easily, but I had to use my 'mathematical intuition' - it seemed 'obvious' that the answer was some quadratic in x, then I just crunched through the algebra.

My question is really, is there a more general, systematic way of solving problems of this type? One that doesn't involve having a lucky guess as to what form the answer might take?
While I think of it, is there a special name for these types of equations (ones where functions are plugged back into themselves)?

Oh that's three questions. Well my maths ability varies greatly :) .

[Pullet]

it's been too long since algebra.
What's the answer you came up with?

[MMI]

I do not have an answer, but your question brought to mind the final method one of my professor's described for solving a differential equation:

You stare at the equation until a solution occurs to you.

[Snarky_Kong]

You'd use the chain rule for integration. It's been a while since I've used it. Hold on a second.

[ultrafilter]

Er, integration?

Anyway, if f2 = g, I believe that f is said to be a composite root of g. That should give you something to Google on.

[Bippy the Beardless]

largest term is x^4 so the function must be quadratic
ax^2+bx+c
f(f(x)) = a^2x^4 +2abx^3+(b^2+2ac)x^2+2bcx+c

= x^4 -4 x^3 +8x +2

ergo a=+/-1 c=2 2bc=8 ergo 4b=8 ergo b=2
try a=+1 doesn't work
try a=-1 hey it works.

SImply knowing the highest term allows you to know the form of the polynomial and it's highest power term.

Of course for non polinomial functions or odd highest power solution polynimials things will rapidly get complex.

[Snarky_Kong]

Chain rule (http://mathworld.wolfram.com/ChainRule.html)

So g'(x)=f'(x)*f'(x)

4x^3-12x^2+8=2*f'(x)

f'(x)=2x^3-6x^2+4

f(x)=1/2x^4-2x^3+4x+c

You would then plug that into itself to solve for c.

[puggyfish]

IANAM, but I would guess that there is no general way to solve for nested functions.

<MathWorld> (http://mathworld.wolfram.com/NestedFunction.html)

Certainly, Mathematica has trouble with the simple polynomial you give. On the other hand, I would be surprised if a general solution to

f(f(x)) = Polynomial in x

were not possible, just on gut feeling.

Perhaps Nest[f,x,n] = Polynomial in x

can also be solved in general. Any offers?

[Snarky_Kong]

Err, that doesn't look right, I'm sure I'll be corrected shortly. It's finals week, that's my excuse.

[Pullet]

Now I remember why it's been so long since I've studied algebra.
Have fun, y'all, I'm bailing.

[CalMeacham]

I think some of you folks are a tad confused. He's not looking for a solution to (f(x))^2 = g(x), but of f(f(x))=g(x). Tht is, if you substitute the function f(x) in place of x in the function f(x), then set tha equa to g(x).

As far as I know, there isn't a general way to solve this but this sort of math isn't my forte. This kind of thinf became popular and important when computers and especially hand calculaors became available. I note that it wasn't until that happened that people really started fooling around with such recursive and self-referential formulas. A lot of the work was done by calculators and computers using the brute force method of crunching it through -- people wrote programs t draw Mandelbro sets. They didn't derive formulas for it. So I suspect that there isn't a general way to do this. (There are probably a few specialized cases that are soluble analytically. I'll bet you con solve the case for one iteration using the Method of robenius. But it's probabl more trouble than it's wortyh.)

[ultrafilter]

There probably is a general solution to f2 = g when g is an even-degree polynomial.

Consider the case where g(x) = x. Certainly f = g is a solution. But so is any invertible function on the set where its inverse exists. That should give you some idea of the complexity of the problem.

[Splanky]

Snarky- The problem is this:

g'(x) = f'(f(x))*f'(x) in this case. I tried differentiation, I don't think setting up a differential equation will help (it gets very messy).

[Cabbage]

Chain rule (http://mathworld.wolfram.com/ChainRule.html)

So g'(x)=f'(x)*f'(x)

4x^3-12x^2+8=2*f'(x)

f'(x)=2x^3-6x^2+4

f(x)=1/2x^4-2x^3+4x+c

You would then plug that into itself to solve for c.
Actually, g'(x) = f'(f(x))*f'(x)

Also, f'(x)*f'(x)=[f'(x)]^2, not 2*f'(x).

As for the problem, I don't know of a general solution for this sort of problem, but I think it should be pretty straightforward when you're dealing with polynomials. Simply figure out what the degree of f should be, then figure out what the coefficients are.

[ultrafilter]

Also, if g(x) = xn, f(x) = xsqrt(n) is a solution. But if g(x) = xn + 1 and n is odd, what will you do?

[Snarky_Kong]

Actually, g'(x) = f'(f(x))*f'(x)

Also, f'(x)*f'(x)=[f'(x)]^2, not 2*f'(x).

As for the problem, I don't know of a general solution for this sort of problem, but I think it should be pretty straightforward when you're dealing with polynomials. Simply figure out what the degree of f should be, then figure out what the coefficients are.

See, I knew there were , painfully simply, errors I was making.

[Cabbage]

Yeah, it won't be so straightforward for polynomials as I first thought. Like ultrafilter mentioned, even degree polynomials might be easier, but even then you may have non-polynomial solutions.

[Cabbage]

ultrafilter, now that I think about it a bit more, I think you might have been thinking of polynomials with perfect square degree, rather than even degree. Then, it will be easy to find polynomial solutions only if they exist.

For example, f(f(x))=x^9 has the obvious solution f(x)=x^3 (there may be other solutions).

What about f(f(x))=x^6 + 1? I don't know a solution offhand, but I think it's clear no solution can be a polynomial in x.

[MikeS]

There probably is a general solution to f2 = g when g is an even-degree polynomial.


Not necessarily. First of all, if f(x) is a degree-n polynomial, then f(f(x)) is a degree-n2 polynomial. Maybe you meant "if g is a polynomial with square degree?"

But even that doesn't work. If f(x) is of the form ax2 + bx + c, then

f(f(x)) = a2 x4 + 2 a2 b x3 + a (2ac + b2 + b) x2 + b (2ac + b) x + c (b + ac + 1)

There aren't any values of a, b, and c that would correspond to certain values of the coefficients. For example, if the coefficient of the x4 is non-zero and the coefficient of the x3 is zero, then that means that b must be zero; but if the coefficient of the x1 is non-zero, then we're screwed.

For general n, this won't work because we have n2 + 1 equations that must be satisfied by n + 1 variables (i.e., the coefficients of the polynomial f.)

On preview, I see I've conveniently ignored the possibility on non-polynomial solutions. I'll have to think about this a little more.

[ultrafilter]

ultrafilter, now that I think about it a bit more, I think you might have been thinking of polynomials with perfect square degree, rather than even degree. Then, it will be easy to find polynomial solutions only if they exist.

When I wrote that, I wasn't thinking specifically of polynomial solutions. f(x) = xsqrt(2) is fine by me, cause I'm interested in finding all the solutions we can.

According to this page (http://www.math.niu.edu/~rusin/known-math/99/sqrt_exp), there is a solution to f2 = exp, but it's not single-valued and is not known to be unique.

[Splanky]

After some algebra, I worked out that there are 6 possible polynomials for which

f(f(x)) = g(x) is true

f(x) = ±x^2 -2x +c

c can be any 3 of the solutions to to c^3 -8c^2 + c - 2 = 0
(All three solutions to this polynomial are real)



Then again, that's only polynomials. Lord knows how to show that there are/aren't non-polynomial solutions.

[ultrafilter]

A little more searching turned up this page (http://reglos.de/lars/ffx.html), which has a whole lot of references on the topic.

[Splanky]

Actually, I'm tired, and I've lost track of my work. I thought my polynomial had three distinct zeros, but I just checked and the one in my previous post doesn't (only one real zero). Unless I'm making another mistake there are only 2 polynomials for f(x).

[ultrafilter]

Depends. Are we working in R ® R or C ® C?

[Splanky]

Well I'm assuming we're not dealing with complex solutions.

Anyway, I looked over my work and I think I caught my mistake. (Maybe someone could check my work for me).

If you take MikeS's work and set the coefficients of the two polynomials equal to each other, you get this system:

a^2 = 1
2*a^2 * b = -4
a(2ac +b^2 +b) = 8
c(b + ac +1) =2

I get that b = -2 (always)
a = -1 or 1
-c^3 +16c^2 - c = 2
^This is the right polynomial, I think. It DOES have 3 real solutions.

[nivlac]

f(x) = x2 - 2x -1 works. Just a little intelligent trial and error. Don't believe there's a general solution approach.