Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that f(x) is a polynomial

  1. Aug 19, 2010 #1
    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. jcsd
  3. Aug 19, 2010 #2
    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?
  4. Aug 19, 2010 #3
    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
  5. Aug 19, 2010 #4
    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!!!!!
  6. Aug 20, 2010 #5
    I thought about it for 10 min. and I'm not getting anywhere. Seems like a difficult problem. Where did you get it?
  7. Aug 20, 2010 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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 [tex]f(x)=x^{2^{\frac{1}{3}}}[/tex], f(f(f(x))) is x2 and there is no possible choice of f(x) that is a polynomial
  8. Aug 20, 2010 #7
    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.
  9. Aug 20, 2010 #8
    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.
  10. Aug 20, 2010 #9
    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 [itex]\in[/itex] R[x] such that P(n) = F(n) for all n [itex]\in[/itex] N.

    With this definition, then adriank has provided a counterexample. His f maps N to N, f(f(f(n))) = n for all n [itex]\in[/itex] N and so is a (strictly increasing) polynomial according to the above definition. However, f is neither a polynomial nor strictly increasing.
  11. Aug 20, 2010 #10


    User Avatar
    Science Advisor

    That's not true in general, consider n(n+1)/2.
  12. Aug 20, 2010 #11


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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


    Then f(f(f(x)))=x+6
  13. Aug 20, 2010 #12
    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?

  14. Aug 21, 2010 #13


    User Avatar
    Science Advisor
    Homework Helper

    I think maybe the question means that the order of growth is polynomial, [itex]\exists k:f(x)\in O(x^k)[/itex].
  15. Aug 21, 2010 #14
    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???
  16. Aug 21, 2010 #15
    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.

    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
  17. Aug 21, 2010 #16
    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
  18. Aug 21, 2010 #17
    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?
  19. Aug 21, 2010 #18
    False. Not all functions are constant, strictly decreasing, or strictly increasing.
  20. Aug 21, 2010 #19


    User Avatar
    Science Advisor
    Homework Helper

    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.
  21. Aug 21, 2010 #20
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook