What conditions imply that a function over $\mathbb{Z}$ is a polynomial?

Question

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.

Answer 1

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

Answer 2

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

$f(0),f(1),f(2),f(3),\cdots$

to the sequence of differences

$f(1)-f(0),f(2)-f(1),f(3)-f(2),f(4)-f(3)\cdots$

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.