Prove that f(x) is a polynomial

[meleck]

Hi can anyone help me please 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.

 

[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?

 

[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

 

[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 there's got to be an expression...its just like saying prove dat dy/dx is a partial differential equation!

 

[hamster143]

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

 

[Office_Shredder]

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)))=x² 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 x² and there is no possible choice of f(x) that is a polynomial

 

[adriank]

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.

 

[hamster143]

Combining these, f(f(f(x)))=x² 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 x² and there is no possible choice of f(x) that is a polynomial

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.

Define f as follows: If n is a natural number, then
f(3n - 2) = 3n - 1
f(3n - 1) = 3n
f(3n) = 3n - 2.

It's not monotonic.

 

[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.

 

[disregardthat]

Furthermore, I'm guessing that the coefficients of any polynomial from the natural numbers to the natural numbers have to be integers.

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

 

[Office_Shredder]

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

 

[Petek]

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

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

 

[CRGreathouse]

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

 

[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?

 

[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.

 

[esahione]

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.

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.

 

[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?

 

[adriank]

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

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

 

[CRGreathouse]

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

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.

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

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.

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.

 

[esahione]

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?

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.

 

[adriank]

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.

They are the same function, and this function can be represented by a polynomial, which is all the original problem asked for.

 

[Petek]

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

I didn't claim that f(x) = 1/x implies that f(f(f(x))) is a polynomial, just that f(f(x)) is. You previously wrote

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 ...

My example shows this statement to be incorrect.

Petek

 

[esahione]

They are the same function, and this function can be represented by a polynomial, which is all the original problem asked for.

You're right.

Thinking about it leads me to believe that the problem asked is equivalent to prove that if a sequence has a strictly monotonic subsequence, which would be f(f(f(n))), we have to show that the sequence itself is strictly monotonic. But this is not true.

 

[jostpuur]

So the original problem got debunked as errorneous? But I guess the following conjecture is still open:

If f:\mathbb{N}\to\mathbb{N} is a strictly monotonic function, and if f\circ f\circ f is a polynomial, then also f is polynomial.

 

[jostpuur]

This is a difficult problem too:

If f:\mathbb{N}\to\mathbb{N} is a strictly monotonic function, and if f\circ f is a polynomial, then also f is polynomial.

 

[jostpuur]

It could be I just debunked my own conjecture. If you define f so that it starts like this:

<br /> f(1) = 1<br />
<br /> f(2) = 3<br />
<br /> f(3) = 4<br />
<br /> f(4) = 9<br />
<br /> f(5) = 10<br />
<br /> f(6) = 11<br />
<br /> f(7) = 12<br />
<br /> f(8) = 13<br />
<br /> f(9) = 16<br />
<br /> f(10) = 25<br />
<br /> f(11) = 36<br />
<br /> f(12) = 49<br />
<br /> f(13) = 64<br />
<br /> f(14) = 65<br />
<br /> f(15) = 66<br />
<br /> f(16) = 81<br />
<br /> \vdots<br />

Then

<br /> (f\circ f)(1) = 1<br />
<br /> (f\circ f)(2) = 4<br />
<br /> (f\circ f)(3) = 9<br />
<br /> (f\circ f)(4) = 16<br />
<br /> (f\circ f)(5) = 25<br />
<br /> (f\circ f)(6) = 36<br />
<br /> (f\circ f)(7) = 49<br />
<br /> (f\circ f)(8) = 64<br />
<br /> (f\circ f)(9) = 81<br />
<br /> \vdots<br />

So that (f\circ f)(n)=n^2. I didn't check rigorously that f(n) can be defined properly for all n, but it looks like possible. Similar counter example probably exists also for f\circ f\circ f claim.

 

[Petek]

That's a nice example. I looked up your function in the On-Line Encyclopedia of Integer Sequences and found http://www.research.att.com/~njas/sequences/A079258 . I looked at some of the references on that page. The sequence doesn't seem to be represented by a simple formula. It seems clear that the values of f(n) can't be represented by a polynomial, just by considering the degree of any such.