# Prove that f(x) is a polynomial

1. Aug 19, 2010

### meleck

Hi can anyone help me plz or give me a strong hint?
I have to prove this:
If f(x) is a function from natural to natural Numbers and f(f(f(x))) is stricly increasing a polynomial than f(x) is also.

2. Aug 19, 2010

### hamster143

Do you want to prove that, if f(f(f(x))) is a strictly increasing polynomial, then f(x) is also a strictly increasing polynomial?

3. Aug 19, 2010

### meleck

yeah sorry i forgot a word

but that f can be written as a polynomial doen't exclude that it can be written in another form

for exmaple if f(f(f(x))) = x u have a lot of other possibilities

4. Aug 19, 2010

### abbeynewton

well we need to understand d question in detail....i believe dat dere has to be an expression in which f(x) has to b expressed...f(x) is a function of a the variable x...but theres got to be an expression....its just like saying prove dat dy/dx is a partial differential equation!!!!!

5. Aug 20, 2010

### hamster143

I thought about it for 10 min. and I'm not getting anywhere. Seems like a difficult problem. Where did you get it?

6. Aug 20, 2010

### Office_Shredder

Staff Emeritus
This seems like an insane result. If f(f(f(x))) is not a degree that's a cube, then you lose since if f(x) is a polynomial, f(f(f(x))) is the degree of f(x) cubed.

Furthermore, I'm guessing that the coefficients of any polynomial from the natural numbers to the natural numbers have to be integers. If that's the case, then if f(x) is such a polynomial the leading coefficient of f(f(f(x))) has to be a cube as well, along with the constant coefficient (assuming f isn't constant).

Combining these, f(f(f(x)))=x2 is the easiest example which has no polynomial choice of f(x). I'm assuming that when you say 'increasing' you're only referring to on the natural numbers, since that's where f(x) was defined. Then if $$f(x)=x^{2^{\frac{1}{3}}}$$, f(f(f(x))) is x2 and there is no possible choice of f(x) that is a polynomial

7. Aug 20, 2010

I assume your natural numbers don't contain 0.

Define f as follows: If n is a natural number, then
f(3n - 2) = 3n - 1
f(3n - 1) = 3n
f(3n) = 3n - 2.
Then f(f(f(x))) = x, which is a strictly increasing polynomial function of x. But clearly f is not polynomial.

8. Aug 20, 2010

### hamster143

The problem does not say that f must exist for any polynomial f(f(f(x))). It' says that IF there's an f that is integer to integer and strictly increasing, and f(f(f())) is a polynomial, then f itself is a polynomial.

It's not monotonic.

9. Aug 20, 2010

### Petek

In my opinion, the problem hasn't yet been clearly stated. It seems that the OP means

Let N = {1, 2, 3, ...} and suppose that f maps N to N. Also suppose that f(f(f(x))) is a strictly increasing polynomial. Then f is a strictly increasing polynomial.

However, what does it mean for a function that maps N to N to be a polynomial? Is there a standard definition? I suppose we could say that a function F: N --> N is a polynomial if there exists a polynomial P $\in$ R[x] such that P(n) = F(n) for all n $\in$ N.

With this definition, then adriank has provided a counterexample. His f maps N to N, f(f(f(n))) = n for all n $\in$ N and so is a (strictly increasing) polynomial according to the above definition. However, f is neither a polynomial nor strictly increasing.

10. Aug 20, 2010

### disregardthat

That's not true in general, consider n(n+1)/2.

11. Aug 20, 2010

### Office_Shredder

Staff Emeritus
Gah, that's what I get for posting at 4 in the morning

adriank is on the right track. The monotonicity is easy to deal with

f(3n)=3n+1
f(3n+1)=3n+2
f(3n+2)=3n+6

Then f(f(f(x)))=x+6

12. Aug 20, 2010

### Petek

But for your definition of f,

f(1) = 2
f(2) = 6
f(3) = 4
f(4) = 5
f(5) = 9
f(6) = 7

so f isn't monotone either. I don't understand why we need to find a monotonic f. Adriank exhibited a function f: N --> N such that f(f(f(x))) is a strictly increasing polynomial but f isn't a polynomial. Doesn't that suffice to show the problem is incorrect?

Petek

13. Aug 21, 2010

### CRGreathouse

I think maybe the question means that the order of growth is polynomial, $\exists k:f(x)\in O(x^k)$.

14. Aug 21, 2010

### abbeynewton

i think i agree with petek.....dere seems to be a problem wit the question...it seems as if it was framed up without proper checking....meleck who gave u d question???

15. Aug 21, 2010

### esahione

This seems quite trivial to me.

If this is what you want to prove: Let f:N->N. If f(f(f(x))) is a strictly increasing polynomial, then f(x) is a strictly increasing polynomial as well.

Proof:
The constraint that f : N->N means that there can't be any negative number in the image. Therefore, f(n) must always be greater than 0.

Suppose f(f(f(x))) is a strictly increasing polynomial, and f(x) is constant. This means that f(f(f(x))) is constant as well, which is a contradiction. Now suppose f(x) is strictly decreasing. Then, for all n, f(n)>f(n+1), which means that f(f(n))<f(f(n+1)), and f(f(f(n)))>f(f(f(n+1))), which is a contradiction, since f(f(f(x))) is strictly increasing.

Both of these contradictions show that f(x) must be a strictly increasing function.

Now if one wants to show that f(x) is a polynomial, just realize that the composition of polynomial functions is a polynomial. The rest follows from the argument above.

Last edited: Aug 21, 2010
16. Aug 21, 2010

### esahione

I'll elaborate on this a little bit more.

Suppose f(f(f(x))) is a strictly increasing polynomial function. This means that f(x) must be increasing, by the argument given above.

Furthermore, since f(f(f(x))) is a polynomial, and since it is a composition of functions, f(x) must be a polynomial. For instance, f(x)=x^3+6, f(f(x))=(x^3+6)^3+6, and so on. It will always be a polynomial, since you're just multiplying polynomials. To see this in a more logical manner, suppose f(x) is a non-polynomial function. Then, f(f(x)) clearly isn't a polynomial, and neither is f(f(f(x))) which is a contradiction. Therefore, f(x) must be a polynomial.

Last edited: Aug 21, 2010
17. Aug 21, 2010

### Petek

Suppose that we define

f(x) = 1/x, for all x > 0.

Then f isn't a polynomial. However,

f(f(x)) = f (1/x) = x

so f(f(x)) is a polynomial. Also, see adriank's example in post #7 above. That provides an example where f isn't a polynomial but f(f(f(x))) is a polynomial. Can you see why adriank's f, which maps N to N, can't be extended to a polynomial function from R to R?

18. Aug 21, 2010

False. Not all functions are constant, strictly decreasing, or strictly increasing.

19. Aug 21, 2010

### CRGreathouse

Edit: It looks like adriank and Petek have addressed these parts already.

You've shown that f(x) cannot be constant or strictly decreasing, but not that it must be strictly increasing. There are other possibilities.

This shows that if f(x) is a polynomial that f(f(f(x))) is a polynomial, but not that if f(f(f(x))) is a polynomial then f(x) is a polynomial.

20. Aug 21, 2010

### esahione

But your example gives f(f(f(x)))=1/x, which isn't a polynomial.

Here's what I think was Adriank's mistake:
His function isn't f(f(f(x)))=x. His function is f(f(f(3n)))=3n, f(f(f(3n-1)))=3n-1 and f(f(f(3n-2)))=3n-2. While it is true that it is equivalent to f(f(f(x)))=x, it is not a polynomial.

I'll try to write a more rigorous proof in abstract algebra terms.