# Thread: Looking for special polynomials

1. ## Looking for special polynomials

Hello,

I look for ALL polynomials with the two following qualities:

1) All co-efficients of p are in N
2) An function f exists with f(f(f(x)))=p(n) for all n in N. (The domain of f is N and the co-domain of f is N, too)

N is the set of all natural numbers WITH 0: N={0, 1, 2, 3, 4, ...}

___________________________________________

I have no idea how to solve this problem, so I started to find examples for such polynomials p.

1. Obviously p=x^{3 * z} for all z ∈ N is such an polynomial.
2. All q=x^{z} with z ∈ N and 3|z are NOT such polynomials p.
3. I calculated f(f(f(x))) with f(x)=x^2+x. Hence p(x)=x^8+4*x^7+8*x^6+10*x^5+9*x^4+6*x^3+3*x^2+x is an polynomial, which I look for.
4. I calculated f(f(f(x))) with f(x)=x^2+2*x. Hence p(x)=x^8+8*x^7+28*x^6+56*x^5+70*x^5+56*x^3+28*x^2+ 8x is an polynomial, which I look for.

So, how do I find all other polynomials p ?

Sanwich

2. Originally Posted by Sandwich
Hello,

I look for ALL polynomials with the two following qualities:

1) All co-efficients of p are in N
2) An function f exists with f(f(f(x)))=p(n) for all n in N. (The domain of f is N and the co-domain of f is N, too)

N is the set of all natural numbers WITH 0: N={0, 1, 2, 3, 4, ...}

___________________________________________

I have no idea how to solve this problem, so I started to find examples for such polynomials p.

1. Obviously p=x^{3 * z} for all z ∈ N is such an polynomial.
2. All q=x^{z} with z ∈ N and 3|z are NOT such polynomials p.
3. I calculated f(f(f(x))) with f(x)=x^2+x. Hence p(x)=x^8+4*x^7+8*x^6+10*x^5+9*x^4+6*x^3+3*x^2+x is an polynomial, which I look for.
4. I calculated f(f(f(x))) with f(x)=x^2+2*x. Hence p(x)=x^8+8*x^7+28*x^6+56*x^5+70*x^5+56*x^3+28*x^2+ 8x is an polynomial, which I look for.

So, how do I find all other polynomials p ?

Sanwich
If $f(x)$ is any polynomial with coefficients in $\mathbb{N}$ then $p(x)=f(f(f(x)))$ is a polynomial with coefficients in $\mathbb{N}$. Similarly you should be able to show that if any coefficient of a polynomial $f(x)$ is not in $\mathbb{N}$ then $p(x)=f(f(f(x)))$ has a coefficient not in $\mathbb{N}$ (check this last bit, I have only looked at a sketch proof and there may be an error in it).

Now the question remains are there any non-polynomial functions $f(x)$ such that $f(f(f(x)))$ is a polynomial (with coefficients in $\mathbb{N}$ )?

CB

3. Hello,

I am not sure, whether these are the right ideas:

I assume, that I could show that f(x) is an polynomial with coefficients in .
(because if f is not polynomial, f(f(f(x))) is not polynomial; if f has coefficient which are not in N f(f(f(x))) hat coefficients not in N, too.)

The next problem is, that not all polynomials p are polynomials with p(x)=f(f(f(x))) for all x and for a special f:
For example p(x)=2*x is an polynomial with coefficients in N, but f with 2*x=f(f(f(x))) does not exists!

So what is the special thing of the polynomials p, I look for??

4. Originally Posted by Sandwich
if f is not polynomial, f(f(f(x))) is not polynomial
I think that is what you will have to prove, I think it may be true but don't know off hand how to prove it.

If you can prove the above you will have (probably) all polynomials p(x) with coefficients in N such that there exists an f(x) such that f(f(f(x))) are in:

S = {f(f(f(x))); f(x) a polynomial with coeficients in N}

CB

5. Hello CaptainBlack,

could you please give me an example of an function f with f(f(f(x)))=2*x ?

6. Sorry, I meant:
could you please give me an example of an function f with f(f(f(x)))=x^2 ?

I thing there does not exist a function f which is a polynomial and which coefficients are in N.

7. Originally Posted by Sandwich
Sorry, I meant:
could you please give me an example of an function f with f(f(f(x)))=x^2 ?

I thing there does not exist a function f which is a polynomial and which coefficients are in N.
Is $p(x)=x^2$ in $S$? No, but contary to my previous assumption if $f(x)=x^{2^{1/3}}$ then $f(f(f(x)))=x^2$, so there are no-polynomial functions $f(x)$ such that $f(f(f(x)))$ is a polynomial with coefficients in $\mathbb{N}$ (Of course this is only well defined for positive reals, but can be extended to all reals without much difficulty, but we are apparently only interested in its definition on the naturals ...)

CB

8. But now there is another problem:

If p(x)=2*x and f(x)=x^(2/3), so f(f(f(x)))=p(x) for all x, this function f would be contrary to 2): If the domain of f is N the co-domain of f is NOT N.

And if we do not find any other function f which fulfils 2), p(x)=x^2 is an polynomial for which I do not look for.

Hence the set of polynomials I look for is a subset of the set of polynomials with coefficints in N. But which polynomials are elements of this set?

9. Oppss... forgot about that, but you still have not shown that there is no polynomial p(x) with the required properties where f is a non-polynomial (at least as far as I can see).

Also the set of polynomials S is a subset of the set you seek (and may be is the set you seek).

CB

10. ## f ist not necessarily a polynomial

consider the function

f(x)=x+5 for 3|x
f(x)=x-1 otherwise

this yields p(x)=x+3