**QUESTION:**

f(f(x)) = x^{4} - 4*x^{3} + 8*x + 2. What is f(x)?

**ANSWERS: **

It is easy to show that for any polynomial f(x),

f(x) - x divides f(f(x)) - x. (A fixed point argument

is nearly, but not quite enough.)

The polynomial (x^4 - 4x^3 + 8x + 2) - x factors as

(x - 2)(x + 1)(x^2 - 3x - 1). From there, we can

check cases to get f(x) = x^2 - 2x - 1.

Naoki Sato

-------------------------------------------------------------------------------

Ed,

I came across mention of a 'similar' problem in Cedric Smith's article

Early Reminiscences to celebrate the sixtieth birthday of Professor W.

T. Tutte. Smith recounted how Tutte asked Smith, Stone and Brooks (his

collaborators on 'Squaring the Square") to find "...a semiexponential

function S(x), that is, one satisfying S(S(x)) = exp x. We tried our

hands, without success, and told Tutte that we could not solve the

problem. Indeed no self-respecting mathematician could be expected to

solve an impossible problem like that, or so we thought. Whereupon he

replied "But I have a solution." He explained , as follows,.

Suppose that @ is a number such that S(@) = @, then clearly exp @ =

S(S(@)) = S(@) = @. By solving (numerically) the equation exp @ = @ we

find possible values for @, such as 0.318 + 1.337i.

Now differentiate repeatedly the defining equation S(S(x)) = exp x, to

get a sequence of equations. Substitute x = @ in these equations; we

find in turn the values of the successive derivatives S'(@),S''(@),...,

and hence the Taylor series for S(x) expanded around @.

After this, the real mathematicians looked at Tutte, the chemist, with

considerable respect.(We could not prove the Taylor series convergent.

Several years later we found out that in fact it was easy to do so,

using methods explained in E. Piccard's book, "Lecons sur Quelques

Equations Functionelles.")"

Stuart Anderson

-------------------------------------------------------------------------------

Ed,

thank you for posting my analysis of the Doppleganger Maze.

I hope the joint PDF file on the problem "f(f(x)) =...." goes in the

direction you asked for; it takes less than two pages, but 47K are needed. Of

course plain text format was unadequate to the subject; I wrote my results

using TeX, that gave a DVI file of just 10K, and I translated it into a PDF

file: I know in fact that DVI format is not so known...

(He also sent a Revised version in DVI format)

Best regards, Claudio Baiocchi

-------------------------------------------------------------------------------

Hi Ed,

Thanks for the interesting puzzle regarding the equation f(f(x)) = x^4 - 4*x^3 + 8*x + 2.

Assuming a quadratic solution for f(x) leads to three solutions (one

real, two complex) :

f(x) = w*x^2 - 2*w*x + 1 - 2*w

where w is one of the cube roots of 1.

It seems like formal power series and/or derivatives could be used to

find other solutions or rule out their existence.

Googling around, it seems most research has focused on f(f(x)) = e^x,

but a few other relevant articles are

http://www.newton.dep.anl.gov/newton/askasci/1993/math/MATH023.HTM

http://ijmms.hindawi.com/volume-30/S0161171202107150.html

http://mathforum.org/epigone/sci.math.research/swooflolglyr/Pine.GSO.4.33.0304110946150.513-100000@u52.math.uiuc.edu

Thanks,

Michael Brundage

Software Design Engineer

Xbox System Software

Microsoft

-------------------------------------------------------------------------------

Hi,

You can find some information about solving f(f(x)) = g(x) on the

following post on the Mathlinks board (you might need to register to

see the .tex attachment mentioned) :

http://www.mathlinks.ro/Forum/viewtopic.php?t=14151

(there are pointers to an article in French about the general problem

and a reference to the fact that the problem has no solution when g(x) is a

quadratic polynomial)

François Glineur

-------------------------------------------------------------------------------

Ed:

If f(f(x)) = x^4-4x^3+8x+2, then f(x)=x^2-2x-1.

There has been a lot of discussion of functional equations of this type

on sci.math. You can search sci.math from http://groups.google.com/ .

Do a search on the term f(f(x)) and you will turn up a lot of interesting

threads.

John A. Shonder

Oak Ridge National Laboratory

-------------------------------------------------------------------------------

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

If f(x) is a polynomial, it is of the form f(x) = x^2 + a*x + b.

Then f(f(x)) = (x^2 + a*x + b)^2 + a*(x^2 + a*x + b) + b

= x^4 + 2a*x^3 + 2b*x^2 + a^2 * x^2 + 2ab*x + b^2 + a*x^2 + a^2 * x +

ab + b

= x^4 + 2a*x^3 + (2b + a^2 + a)*x^2 + (2ab + a^2)*x + (b^2 + ab + b)

This gives a system of equations:

2a = -4

2b + a^2 + a = 0

2ab + a^2 = 8

b^2 + ab + b = 2

From the first equation, a = -2. Then 2b = -2 so b = -1. The last two

equations say 4 + 4 = 8 and 1 + 2 - 1 = 2. So f(x) = x^2 - 2x - 1.

For any nontrivial cases this is going to give more equations than

variables, so it is likely that most problems of this sort (for random

polynomials) are not going to lead to solutions. For the case of

f(f(x)) = a quartic polynomial, the coefficients of x^4, x^3, and x^2

lead to a unique solution for the polynomial, so the coefficient of x

and the constant term need to be some specific values for this to

work.

It may be possible for there to be nonpolynomial solutions where the

nonpolynomial parts cancel out when the function is iterated, but it

doesn't seem likely.

Joseph Devincentis

-------------------------------------------------------------------------------

Howdy, Ed

For this problem, one solution can be found pretty easily. By inspection

one can assume f(x) is of the form x^2 + ax + b, equate f(f(x)) to the given

polynomial, and find f(x) = x^2 - 2x - 1.

I think there will usually be infinitely many solutions for problems of the

sort f(f(x)) = some given g(x), though of course the most interesting

solutions will have a simple form. Several years ago I played around

with various forms and found the form f(x) = (ax+b)/(cx+d) was pretty

interesting. Composition of functions of this form is the same as 2x2

matrix multiplication.

Bob Harris

-------------------------------------------------------------------------------

If f(f(x)) = x^4-4x^3+8x+2, then the only polynomial solution for f(x) is

f(x)=x^2-2x-1, which can be found easily in Mathematica, by guessing

that f must be a quadratic and solving for coefficients.

I think there would be an infinite number of solutions if you allowed

any analytic function for f.

There is a lot of research on iterated functions, but I think in

general these problems are not solvable.

I can find other solutions if I use complex numbers. Three equations to be

exact.

Chris Lomont

-------------------------------------------------------------------------------

An f(x) such that f(f(x)) is x^4 - 4*x^3 + 8*x + 2 is x^2 - 2x - 1.

I found it by supposing that it was of the form x^2+a^x+b, noticing

that a=-2 and substituting it (I worked with paper and pen, so I

wanted to reduce computation).

I do not know how to solve such equations: for example, f(f(x))=x has

at least solutions x and -x ...

--

ciao, maurizio codogno

-------------------------------------------------------------------------------

Quick answer to the problem:

f(f(x)) = x^4 - 4x^3 + 8x + 2;

f(x) = x^2 - 2x -1.

Maybe I'm overlooking something, but for this type of problem, you can

assume it's a polynomial of degree 2. So, f(x) will be of the form:

a(x^2) + b(x) + c.

Then, it's a matter of solving

a(x^2) + b(x) + c, and with x = a(x^2) + b(x) + c, it's then

(a(x^2) + b(x) + c)^2 + b(a(x^2) + b(x) + c) + c.

Expanding all of this out, set it equal to x^4 - 4x^3 + 8x + 2, and

then immediately 'a' = 1, and then 'b' = -2, and c = -1 from that. So

it seems to be just a matter of careful algebra.

I'm sure that doesn't help with the general question of solving

problems like this!

Thanks very much,

Corey Maley

University of Nebraska-Lincoln

-------------------------------------------------------------------------------

Notice the 4th degree polynomial. It seems reasonable that f(x) is

quadratic.

So try f(x)=ax^2 + bx + c

f(f(x)) = a(ax^2 + bx + c)^2 + b(ax^2 + bx + c) + c

Simplify to a polynomial in x

[a^3]x^4 + [2a^2b]x^3 + [2a^2c + ab^2 + ab]x^2 + [2abc + b^2]x + [ac^2

+

bc + c]

Coefficients must be equal, so

a^3 = 1 (From which a=1)

2a^b = -4 (From which, since a=1, b=-2)

2a^2c + ab^2 + ab = 0 (Using a=1 and b=-2, c=-1)

2abc + b^2 = 8 (which it does using a=1, b=-2, c=-1)

ac^2 + bc + c = 2 (which also does)

It seems any problem 'of this type' can be solved in this way, but I

would

hope f(f(x)) is 4th degree or less!

-Jeremy Galvagni

-------------------------------------------------------------------------------

I got this possible solution: f(x)=x^2-2x-1

I got it by turning the polynomial into this form:

(x^2-2x-1)^2-2(x^2-2x-1)-1

Are there more solutions?

Carlos Ueno.

Las Palmas de Gran Canaria

SPAIN

---------------------------------------------------------------------------------------------

Hi Ed,

I assumed f(x) = Ax^2 + Bx + C

f(f(x)) = A(Ax^2 + Bx + C)^2 + B(Ax^2 + Bx + C) + C

= (A^3)x^4 + (2BA^2)x^3 + (2CA^2 + AB^2 + AB)x^2 + (2ABC +

B^2)x + AC^2 + BC + C

A^3 = 1

A=1

2BA^2 = -4

B=-2

2CA^2 + AB^2 + AB = 0

C=-1

f(x) = x^2 - 2x - 1

--

Nathan Stohler

Member of Technical Staff

Lucent Technologies, Inc.

-----------------------------------------------------------------------------------------------

I spent longer thinking about this problem then I planned to, so it's a

good thing that it's Thanksgiving break and I don't need to wake up

particularly early:

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

First off, I assumed that, because we have a nice polynomial with

integer exponents and the highest power is x^4, f(x) can be expressed

as f(x) = ax^2 + bx + c, so:

f(f(x)) = a(ax^2 + bx + c)^2 + b(ax^2 + bx + c) + c

f(f(x)) = a(a^2*x^4 + abx^3 + acx^2 + abx^3 + b^2*x^2 + bcx + acx^2 +

bcx + c^2) + b(ax^2 + bx + c) + c

f(f(x)) = a^3*x^4 + a^2*bx^3 + a^2*cx^2 + a^2*bx^3 + ab^2*x^2 + abcx +

a^2*cx^2 + abcx + ac^2 + abx^2 + b^2*x + bc + c

f(f(x)) = a^3*x^4 + (a^2*b+a^2*b)x^3 + (a^2*c + ab^2 + a^2*c + ab)x^2 +

(abc + abc + b^2)x + (ac^2 + bc + c)

f(f(x)) = Dx^4 + Ex^3 + Fx^2 + Gx + H, where D = a^3, E = 2a^2*b, F =

2a^2*c + ab^2 + ab, G = 2abc + b^2, and H = ac^2 + bc + c.

Since f(f(x)) = x^4 - 4x^3 + 8x + 2 is given, equating coefficients

gives a system of five equations with three variables:

a^3 = 1

2a^2*b = -4

2a^2*c + ab^2 + ab = 0

2abc + b^2 = 8

ac^2 + bc + c = 2

Solving the first equation gives a = 1 (which was pretty obvious from

the given coefficients, but I wanted to be thorough), putting a = 1

into the second equation gives b = -2, and putting both a = 1 and b =

-2 into the third equation gives c = -1, so:

f(x) = x^2 - 2x - 1

The other two equations also check out with the values of a, b, and c,

and evaluating f(f(x)) with f(x) = x^2 - 2x - 1 gives the correct

answer of x^4 - 4x^3 + 8x + 2.

Ili Butterfield

------------------------------------------------------------------------------

This was surprisingly easy for someone who remembers his high-school

algebra. I assumed the equation desired was of the form (x^2) + (Y * x) +

Z. If f(x) = (x^2) + (Y * x) + Z, then

f(f(x)) = (((x^2) + (Y * x) + Z) ^ 2) + Y * ((x^2) + (Y * x) + Z) + Z

= ((x^4) + (2Y * (x^3)) + (((Y^2) + 2Z) * (x^2)) + (2YZ * x) +

(Z^2)) + ((Y * (x^2)) + ((Y^2) * x) + 2Y) + Z

= (x^4) + (2Y * (x^3)) + (((Y^2) + Y + 2Z) * (x^2)) + (2YZ +

(Y^2) + Z) * x) + ((Z^2) + 2Y + Z)

Since we have f(f(x)) = (x^4) - (4 * (x^3)) + (8 * x) + 2, then 2Y = -4,

whence Y = -2.

Simplifying the above equation,

f(f(x)) = (x^4) - (4 * (x^3)) + ((2 + 2Z) * (x^2)) + ((4 - 4Z) * x) + ((Z^2) - Z)

From the coefficient of 0 for (x^2) in the given equation, 2 + 2Z = 0, whence Z = -1.

Checking the other coefficients, we should have 4 - (4*(-1)) = 8 and

((-1^2) - (-1)) = 2. Since they check, the solution is f(x) = (x^2) - (2 * x) - 1.

I'd like to add, I came up with the general equation for f(f(x)) if

f(x) is a quadratic equation. If f(x) = (x^2) + Ax + B, then

f(f(x)) = (x^4) + 2A(x^3) + ((A^2) + A + 2B)(x^2)) + (2AB + (A^2))x +

((B^2) + AB + B).

From the coefficient of x^3, you can always find A, and use that and

the coefficient of x^2 to find B. The coefficient of x and the constant, of

course, should check if your values of A and B are a solution.

Darrel C Jones

------------------------------------------------------------------------------

f(x) = x^2 - 2x - 1

Attached is the explanation as well as some discussion regarding these types of problems.

Please let me know what you think. I have a passion for mathematics but have little

time to explore it. I have a degree in mathematics but have been working as a software

engineer for the last ten years.

Thanks,

Will Smith

------------------------------------------------------------------------------

Hi Ed

The solution to the f(f(x)) puzzle is F(x) = x^2 - 2x - 1

Starting with F(x) = ax^2 +bx + c

ffx becomes Px^4 + Qx^3 + Rx^2 + Sx + T

where

P = a^3

Q = 2ba^2

R = 2ca^2+ab^2 + ab

S = 2abc + b^2

T = ac^2 + bc + c

equating PQRST to the terms in ffx = x^4 - 4x^3 + 8x + 2 it is simple

to show that

a = 1

b = -2

c = -1

Rgdz

Pete Kogel

------------------------------------------------------------------------------

Hi!

If you assume the solution is f(x)=ax^2+bx+c, doing the math leads to f(x)=x^2-2x-1,

but I found an easier (?) way.

Differentiating with regard to x, we get f'(f(x)).f'(x)= 4x^3-12x^2+8= (x^2-2x-2)(x-1).

Since f(x) seemed to be a quadratic, f'(x) could be proportional to (x-1), and thus f(x)

proportional to x^2-2x+c. Since it is obvious that the coefficient of the leading term

should be 1 (so f(f(x)) gets an x^4 term), all that remains is finding c. Setting x=0,

f(f(0))= f(c)= 2, so c^2-2c+c=2, and c=2 or c=-1; the second value produces the

correct answer.

Best regards,

Federico Kereki

--------------------------------------------------------------------------------

f(x) = x^2 - 2*x - 1

I found this by observing that the leading term had to be x^2,

so I set f(x) = x^2 + b*x + c and expanded f(f(x)), then matched

coefficients of each power of x from highest order down to

determine the parameters b and c.

Doug Gwyn

--------------------------------------------------------------------------------

Hi,

I'm sending you the solution for composite function based problem;

Given that f(f(x)) = x^4 - 4*x^3 + 8*x + 2; we have to find f(x);

By seeing f(f(x)) we can assume that f(x) is polynomial of degree n.

say f(x) = sum (Pi * x^i) | where i varies from 0 to n.

then f((fx)) will also be a polynomial of degree n^n.

In our case f(f(x)) is of degree 4, hence n^n = 4 => n =2;

Hence we can assume that f(x) = P0*x^2 + P1*x + P2;

Now we can express f(f(x)) in terms of P0,P1 and P2;

After expressing f(f(x)) in terms of P0, P1 and P2 we can compare it

with the given function and hence find the solution.

I guess this is a generic method of finding solutions for such problems

Any comments on this will be fully accepted and analyzed.

Regards

Punit Kishore

--------------------------------------------------------------------------------

Hi Ed,

With regard to the puzzle

f(f(x)) = x^4-4*x^3+8*x+2, I think that f(x)=x^2-2*x-1.

Mark Hudson

------------------------------------------------------------------------------

The function f(x) such that f(f(x)) = x^4 - 4x^3 + 8x + 2 is :

x^2 - 2x -1

I'm not sure about anything wrote about the subject since I came up

with my own method, If your interested about my method, I'd be happy to explain

:)

many thanks Leigh Shepperson

-------------------------------------------------------------------------------

Hi,

It's just a series of N equations with N unknowns as far as I can see.

Answer: X^2 - 2x -1.

Pierre Baillargeon

-------------------------------------------------------------------------------

f(x)=x^2-2x-1

Thanks for mentioning Google Scholar, it's wonderful! Earl Gose

-------------------------------------------------------------------------------

FROM SCI.MATH

From: Zdislav V. Kovarik

Subject: Re: "Halfway-functions"

View: Complete Thread (15 articles)

Original Format

Newsgroups: sci.math

Date: 2002-07-06 15:50:07 PST

Punchline: Suppose a>=0, then for f(x) = a * x + b, a half-way

function is

h(x) = x*sqrt(a) + b/(1+sqrt(a))

Explanation below.

On 6 Jul 2002, Joona I Palaste wrote:

: Here is a simple question which can be very

: difficult to answer. Is there, for every

: function f: R->R, a "halfway function" h: R->R,

: so that h(h(x))=f(x)?

This is quite classical (Abel worked on this); a

discussion can be found in

Marek Kuczma: Functional Equations in a Single

Variable

Polish Scientific Publishers, Warsaw 1968

and other, newer books, one written by Kuczma

as a co-author (I don't have it here).

: And furthermore, if the

: answer is yes, then, for every function that is

: expressible as a combination of elementary

: operations and functions, is the "halfway

: function" also expressible as a combination of

: elementary operations and functions?

:

Very unlikely: even something like f(x) = x + x^3

refuses to have an elementary "compositional

square root" (I don't have a proof, but I tried

hard :-(), although a real-analytic solution

is possible.

: I have myself tested some very trivial cases.

: If f(x)=x+a, then h(x)=x+a/2.

: If f(x)=x*a, where a is non-negative, then

: h(x)=x*sqrt(a).

: If f(x)=x*a, where a is negative, we can't easily

: have h: R->R, but we can have h: C->C,

: h(x)=x*sqrt(a), and f(x) ends up being in

: R if x is in R, even if h(x) is not in R.

: But if f(x)=x*a+b, where a is neither 0 or 1, and

: b is not 0, then h(x) is too difficult to find in

: the short time it took me to write this article.

: I haven't even been able to prove such a function

: exists.

:

: Can anyone help me on this? Any answers will be

: appreciated, thanks.

So: if a is not 1 then the function the function

f(x)=a*x+b has a fixed point w, that is, w satisfies

w = a * w + b

Namely, w = b / (1 - a).

Next, when in trouble, change the variable. In our

situation, set x = y(0) + w, f(x) = y(1) + w

(where the index (0) and (1) "counts" the iterations)

so

y(1) + w = a * (y(0) + w) + b

and simplify, remembering that w is a fixed point:

y(1) = a * y(0)

Now the half-way iteration offers itself (and you knew it):

y(1/2) = sqrt(a) * y(0)

Put into original variables: h(x) = y(1/2) + w becomes

h(x) = (x - w) * sqrt(a) + w

and after simplification, you end up with what I wrote on top

of my reply. The simplification actually allows to drop

the restriction that a be not 1.

Kuczma's book has answers and references to fractional

iterations of many other functions, such as exp(x).

Cheers, ZVK(Slavek).