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?

• Can you divide by $X$? If so, then consider the following algorithm: (0) Start with $d = 0$. (1) Substitute $f$ with $f - f(0)$. (2) If $f$ is the zero polynomial return $d$. (3) Substitute $f$ with $f/X$ and $d$ with $d+1$. Go back to 1). – A.P. Jul 6 '15 at 22:22
• @A.P. : how do you know that your polynomial is the zero polynomial by evaluating it on a finite numbers of values? for every $n$ values, there is always a non zero polynomial that has these points as a root – Tryss Jul 6 '15 at 22:24
• @Tryss Sorry if I wasn't clear. Since others already pointed out that evaluation at finitely many points isn't enough to determine the degree of a polynomial, I thought I would suggest a simple working algorithm. Basically, I simply answered the question in the title. That's why I wrote a comment and not a proper answer, by the way. – A.P. Jul 6 '15 at 22:27
• It may be worth noting that for $k=\mathbb Z$ and if we additonally know $|a_i|\le M$ for all $i$, one can determine $f$ completely, that is: the degreee $n$ and all coefficients $a_i$ of $f(X)=a_0+a_1X+\ldots +a_nX^n$, in just two evaluations. – Hagen von Eitzen Jul 6 '15 at 22:41
• @HagenvonEitzen or if the coefficients are positive. – mrf Jul 6 '15 at 22:43

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

• For finite $\Bbb K$, one can recover $f$ modulo the ideal $\mathcal I$ of polynomials that evaluate to $0$ for every $x \in \Bbb K$; this ideal is principal, generated namely by $\prod_{k \in \Bbb K} (x - k) = x^{\# \Bbb K} - x$. One can thus in the finite case ask for an algorithm that determines the degree of the unique polynomial in the equivalence class modulo $\mathcal I$ of degree $< \# \Bbb K$. – Travis Willse Jul 7 '15 at 7:12
• If the field (is a field and) has characteristic 0, you can follow the infinite algorithm of choosing at each step the unique polynomial $p_n$ of degree at most $n$ which agrees with $f$ on $\{0,1,2,\ldots,n\}$. At each step that is elementary interpolation. So this gives an infinte sequence of polynomials $p_0, p_1, p_2, \ldots$. It is clear that this sequence will be constant from some index $N$, so all $p_i=f$ for $i\ge N$. However, it is clear (from your answer as well) that we have no way of knowing when we are past that $N$. So we can never stop the process "safely". – Jeppe Stig Nielsen Jul 7 '15 at 8:38
• The same is true for other infinite fields (no matter if the characteristic is positive): The values (i.e. the "evaluation mapping" for $f$) does specify the polynomial (including its degree), but a finite subset of values is clearly not enough. But the polynomial can be reconstructed from its values at $\aleph_0$ distinct points. – Jeppe Stig Nielsen Jul 7 '15 at 8:43
• @Travis Yes, that is cool. That algorithm would just be the usual Lagrange interpolation given the $\# \mathbb{K}$ pairs $(x_i,y_i)$ of arguments an corresponding values. – Jeppe Stig Nielsen Jul 7 '15 at 8:52

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.

For $K=\mathbb{R}$ or $\mathbb{C}$, if the degree of f is unknown, you can't find f by evaluating it on a finite number of points.

Indeed, let's have n points, you have an infinite number of polynomials that pass by these points