How would one prove that a function is a polynomial? I can't seem to find anything about this on the internet. I would like to know if there are any unique properties that only polynomials can satisfy. Given properties of a function, can these properties be used to prove that a function is a polynomial. I would like to do this without actually constructing the polynomial. What I mean is something like this: One can show that the sine function is not a polynomial without deriving an actual formula. You just use the property that a polynomial has finite degree.

EDIT: My function is only defined on the positive integers. So I am not sure how to use the ideas of complex analysis.

  • 1
    $\begingroup$ A minor extension of Liouville's theorem: If $f: \mathbb{C} \to \mathbb{C}$ is holomorphic, and $|f(z)| = O(|z|^N)$ as $|z|\to \infty$, then $f$ is a polynomial of degree $\leq N$. Is this the sort of thing you are looking for? $\endgroup$ – David E Speyer Jun 30 '15 at 21:08
  • $\begingroup$ Yes exactly David Speyer thank you: +1 $\endgroup$ – Halbort Jun 30 '15 at 21:09
  • 1
    $\begingroup$ A classic strengtening of @AnthonyQuas's answer: suppose that for any $x$ there exists $n=n(x)$ so that $f^{(n)}(x)=0$. Then $f$ is a polynomial. mathoverflow.net/questions/34059/… $\endgroup$ – Otis Chodosh Jun 30 '15 at 21:20
  • 3
    $\begingroup$ Only defined on the positive integers? Take Anthony's suggestion, and convert to this: take the difference finitely many times, and get identically zero. The difference $\Delta F$ of $F$ is: $\Delta F(n) = F(n+1)-F(n)$. $\endgroup$ – Gerald Edgar Jul 1 '15 at 1:01
  • 1
    $\begingroup$ I think perhaps by the way it was phrased. If it were something like: "What conditions on a function imply that it is a polynomial, if I am only allowed to use its values on the integers?" Otherwise it looks like a total rookie question. It is best to specify what sort of function, and what the domain is. Is it defined on $\mathbb{R}$? $\mathbb{C}$? Is it smooth? Analytic? Merely continuous? $\endgroup$ – David Roberts Jul 1 '15 at 3:04

This is the same answer as given several times already. It is prefaced with a few facts on Taylor series to make it seem familiar. First recall that a real function $f(x)$ well enough behaved at $x=0$ has a Taylor series $$f(x)=\sum_0^{\infty}a_k\frac{x^k}{k!} $$ valid in some interval. And

f(x) is a polynomial if there is an $K$ with $a_k=0$ when $k \gt K$ (and the interval of validity is the entire real line.)

Similarly, any real function $f(n)$ defined on $\mathbb{N}$ (a.k.a. a sequence) has a unique expansion $$f(n)=\sum_0^{\infty}a_k\frac{(n)_k}{k!}.$$

valid on all the domain. And

$f$ is a polynomial (on $\mathbb{N}$) exactly if there is an $K$ with $a_k=0$ when $k \gt K.$

This leaves several things to explain.

For the Taylor series, $a_k=(D^kf)\ (0)$ where $D=\frac{d}{dx}$ is the differential operator which sends $f(x)$ to the derivative $f'(x)$.

For sequences on $\mathbb{N}$, $a_k=(\Delta^kf)\ (0)$ where $\Delta$ is the difference operator which sends the sequence


to the sequence of differences


Also, $(n)_k=n(n-1)(n-2)\cdots(n-k+1)$ is the falling factorial. Of course the question concerned $\mathbb{Z}$ rather than $\mathbb{N}.$

For the domain $\mathbb{Z},$ we can first restrict to $\mathbb{N}$, determine if we have a polynomial and, if so, then check that the expansion is valid on all of $\mathbb{Z}.$

The expressions $\frac{(n)_k}{k!}$ were used point out the relation to Taylor series. Note, however, that $\frac{(n)_k}{k!}=\binom{n}{k}$ is a binomial coefficient.

Examination of these sequences $\binom{n}{k}$ make it clear that they constitute a basis (of sorts) for the space of sequence defined on $\mathbb{N}.$ The first few are

$$\begin{array}{cccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \cdots \\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\cdots\\ 0 & 0 & 1 & 3 & 6 & 10 & 15 & 21\cdots \\ 0 & 0 & 0 & 1 & 4 & 10 & 20 & 35 \cdots\\ 0 & 0 & 0 & 0 & 1 & 5 & 15 & 35\cdots \end{array}$$ Clearly there is a unique linear combination of these sequences for any target sequence. Although the sum is potentially infinite, it is finite for each fixed value of $n.$

Furthermore, $f$ takes integer values on all of $\mathbb{N}$ exactly if the $a_k$ are all integers.


If it satisfies a linear difference equation with characteristic polynomial $(t-1)^m $ for some $m$, the sequence is a polynomial.

This is essentially equivalent to the statement by Gerald Edgar in a comment, that taking iterated differences, we eventually reach a constant sequence.

So, more formally, $\{s_n\}$ is a sequence that is given by a polynomial iff there is an $m$ such that $$ \sum_{j=0}^m s_{i+j} (-1)^j\binom{m}{j} = 0$$ for all $i$. Note that $\sum_{j=0}^m t^j (-1)^j\binom{m}{j} =(t-1)^m$, which explains the connection.

For example, my favourite proof that the number of skew semi-standard Young tableaux of shape $n\lambda$, is a polynomial in $n$, uses this observation. I recently put a paper on arxiv that basically uses this idea.

A third way to reformulate this, is that the generating function can be expressed as $$\sum_{j=0}^\infty s_i t^i = \frac{c_0 + c_1t \cdots + c_{m-1}t^{m-1}}{(1-t)^m}$$ for some $c_i$.

  • $\begingroup$ Could you provide an example please? $\endgroup$ – Halbort Jul 1 '15 at 4:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.