4
$\begingroup$

Let $p(x)$ be a polynomial with integer coefficients, which is not constant. Then is this condition possible: $p(x)=3^{x}$ whenever $x \in \mathbb{N}$.

Motivation: https://mathoverflow.net/questions/34059/if-f-is-infinitely-differentiable-then-f-coincides-with-a-polynomial

  • 1
    @Pete.L. Clark: Apologies for misunderstanding your previous quotation2010-10-06

10 Answers 10

2

Suppose that $p(x)$ exists and has degree $n$. $\lim_{x\to\infty}\frac{p(x)}{x^{n+1}}=0$ and $\lim_{x\to\infty}\frac{3^x}{x^{n+1}}\to\infty$, but $\frac{p(x)}{x^{n+1}}=\frac{3^x}{x^{n+1}}$ for all $x\in\mathbb{N}$, so it is impossible for the first limit to be finite and the second limit to be unbounded.

18

No, a polynomial can't grow exponentially as $x\to\infty$.

  • 3
    @Chandru1: show that $\lim_{x\to\infty}p(x)/3^x=0$ for all polynomials $p$, by induction on the degree of $p$, using, for example, l'Hôpital's rule to do the inductive step.2010-10-04
14

Yet another proof: if $p$ is a nonzero polynomial with real coefficients then $\lim_{n\to\infty}\frac{p(n+1)}{p(n)}=1$ which certainly doesn't hold for $p(x)=3^x$.

14

A polynomial of degree $n$ has the property that $p(x+1) - p(x)$ is a polynomial of degree $n-1$. After taking $n$ finite differences you reach a contradiction.

  • 0
    Well, after taking N finite differences (in this problem) you get 2^N=0. This could be a contradiction or not depending on what other assumptions are made.2010-10-05
13

$\rm\ p(x) = 3^x\:$ on $\rm\:\mathbb N\ \Rightarrow\ p(2x) = p(x)^2\:$ on $\rm\:\mathbb N \ \Rightarrow\ p(2x) = p(x)^2\:$ contra degree comparison.

  • 4
    What can I say? I'm a stickler for details!2010-10-09
9

The answer depends on the ring (which the question did not specify) where $x$ and $p(x)$ take their values. Polynomials with integer coefficients, and non-negative powers of integers such as $3^n$, can be evaluated in any ring, so the question makes sense in this generality.

In a ring where 2=0 (such as the integers modulo 2), $3^n = 1^n$, and any polynomial with $p(0)=p(1)=1$ is an example. It should be an interesting problem to determine all rings where there is such a $p(x)$.

ADDED: Let's consider the situation over an arbitrary commutative ring $R$ with unit. $Q(x) = p(x+1)- 3p(x)$ is zero (as a function) for all $x$ in the image of $\mathbb{Z}$ in $R$. If $R$ is of characteristic different from $2$, $\deg Q = \deg P$ (as polynomials). In characteristic 0 having zeros at all integers is enough to force $Q = 0$ as a polynomial, and there are no examples. In finite characteristic n > 1, we also have $p(n) = 3^n = p(0) = 1$ so that $n | (3^n - 1)$. If $n$ is prime then $n | (3^n - 3)$ so that $n | 2$ and thus $n=2$. If $n$ is not prime, and $q$ is a prime dividing $n$, then an example in $R$ is an example in $R/q$ which has prime characteristic $q$ and therefore $q=2$. So the only remaining possibility is a ring where $2^k = 0$, for k > 1. For such rings there are examples because in the binomial expansion of $(1+2)^n = 1 + 2n + 2n(n-1) + 4n(n-1)(n-2)/3 + 2n(n-1)(n-2)(n-3)/3 + \dots$ all terms are congruent modulo $2^k$ to polynomials with integer coefficients, and all terms of degree higher than $2^k - 1$ vanish on the integers modulo $2^k$.

ADDED-2: one can see that $2^k=0$ more directly by writing $p(n+1)-p(n) = 2p(n)$ (for images of integer $n$ in our ring). This means that $\Delta^k p(n) = 2^k p(n)$ and for k > deg(P) this will be zero, then set $n=0$ to get $0 = 2^k p(0)= 2^k$. [Note that this argument applies to $p(n)$ for integer $n$ only, not $p(x)$ as an abstract polynomial or a polynomial evaluated at non-integer values of $x$.]

Conclusion: there are polynomials $p(x)$ such that $p(n)=3^n$ for all $n \geq 0$ (with the polynomial considered as a function on the commutative ring-with-unit $R$) if and only if in this ring, $2^k = 0$ for some positive integer $k$.

6

$\rm\ p(x+1) = 3\:p(x)\:$ on $\rm\:\mathbb N\ \Rightarrow\ p(x+1) = 3\:p(x)\ \Rightarrow\ p(-1) = 1/3\ $ contra $\rm\ p(x)\in \mathbb Z[x]\:$.

Or, continuing, $\rm\ p(-n) = 3^{-n}\: \Rightarrow \ p(x)\:p(-x) = 1\:$ on $\rm\:\mathbb N\ \Rightarrow\ p(-x)\:p(x) = 1\ $ contra degree comparison. This proof works over much more general coefficient rings, e.g. $\mathbb Q\:$.

3

Suppose $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0 = 3^x$ for $x \in \mathbb N$.

Then $a_n (x+1)^n + a_{n-1} (x+1)^{n-1} + \cdots + a_0 = 3 a_n x^n + 3 a_{n-1} x^{n-1} + \cdots + 3 a_0$.

But the coefficient of $x^n$ on the LHS is $a_n$ and on the RHS it is $3 a_n$.

This contradicts the assumption.

  • 0
    @Qiaochu Yuan - The argument shows that all coefficients must be$0$but the constant coefficient is 1 (base case of the induction is not written because it is trivial - infact it's not even induction, just case analysis $0$ or $x+1$).2010-10-04
3

If so then then the values of $\rm\: q(x) = p(x^2)\:$ are all powers of 3, contradicting the fact that infinitely many primes must occur among the values of a nonconstant $\rm\: p(x) \in \mathbb Z[x]\:$, by way of a simple Euclid-like proof.

3

Here's another argument (at the other end of the real line!):

Such a polynomial would have to be non-constant, which means that it tends to $\infty$ or $-\infty$ as $x\to-\infty$. But this is impossible, since $3^x \to 0$ as $x\to-\infty$.

  • 3
    Oops, sorry. The question said $x\in\mathbb{N}$, not $x\in\mathbb{Z}$ as I thought for a moment. Well, never mind, I'll leave the answer here anyway, since it shows that a polynomial cannot *decay* exponentially either...2010-10-04