Is there an algorithm to compute the degree of a polynomial?

Let $f\in k[X]$ be a polynomial in one unknown over any field (or any nice enough commutative ring, I imagine - it shouldn't matter) and suppose that all we can do to understand $f$ is to evaluate it at any $x\in k$. Trivially, if $\deg f$ is known then so is $f$, for instance by finding the values of $f$ at $\{0,\dots,\deg f-1\}$ and taking successive differences. But what if $\deg f$ is unknown? The most obvious thing to do to try and compute successive differences at $\{0\},\{0,1\},\{0,1,2\},\dots$ and wait for a pattern to occur, but my preliminary intuition tells me that this does not necessarily work. In short, is it possible to compute $\deg f$ (and thus $f$) from evaluation at (finitely many) points?

Solution 1:

No. If the field is finite, you can't reconstruct $f$ even by computing $f(x)$ for every $x \in \mathbb{K}$. There are only a finite number of functions from $\mathbb{K}$ to $\mathbb{K}$, but infinitely many polynomials. For example $x^3+x$ evaluates to $0$ for every $x\in\mathbb{Z}_2$.

If the field is infinite, and you evaluate on a finite set of points, there is a polynomial $p$ vanishing on the given set, so again you have no chance of identifying $f$. (If $f$ is a possible solution, then so is $f+p$.)

Added: Curiously enough, if you have a polynomial in $\mathbb{Z}[x]$ and know that all the coefficients are positive, you can reconstruct $f$ by computing just two values. (Compute $f(1)$ to get a bound on the degree and the size of the coefficients, then compute $f(n)$ for a sufficiently large $n$ and read the coefficients off the base-$n$ expansion of $f(n)$. Fill in the details!) Even more cheating, compute $f(x)$ where $x$ is transcendental over $\mathbb{K}$.

Solution 2:

Given values of $f$ at $n$ different points in $\mathbb{R}$, there are infinitely many polynomials of each degree $m\geq n$ that take on those values. Unless you have some bound on the degree, you won't be able to find it by sampling finitely many points, because you'll never know whether it might be much higher than you think.

In a finite field, specifying the value at every point in the field will certainly suffice. No, that's wrong.