Test whether a given function is polynomial

Question

You have a black box function to which you can give real number inputs and from which you can receive real number outputs. How would you test whether it is likely to be a polynomial?

One expensive idea is to use finite differences:

1. Choose a maximum degree n of the "polynomial" you are testing.
2. Choose a consecutive sequence with random step size, and evaluate the function there to get an output sequence. E.g., $$[ 2, 2.3, 2.6, 2.9,\dots] \to [ 4.81, 5.02, 5.05, 4.90,\dots]$$
3. Using the output sequence as S[0], define S[n] so that its k^th entry S[n][k] = S[n-1][k+1]-S[n-1][k]. E.g. S[1] = [5.02-4.81,5.05-5.02,4.90-5.05,...] = [0.21,0.03,-0.15,...]
4. If the function is a polynomial (of degree at most n), then the sequence S[n+1] should be all zeros.

Some issues about programming this method:

• Would be expensive for large n
• If S[0] has large values, computer arithmetic will produce bad results for S[1] and beyond.

Answer 1

I think the largest problem here is that given things like Taylor series, every function can eventually be closely approximated as a polynomial. As such, even a finite range of measured outputs of a blackbox representing a sine function will might yield a polynomial. Measuring a large range is computationally difficult as higher powers tend to yield very large values for increasing inputs. Anyway, this is what I would do: Suppose you an input set $x\in \mathbb{R}^{n+1\times1}$ and the corresponding output set $S\in \mathbb{R}^{n+1\times1}$, where $n$ is the estimated polynomial order (or better, larger than). Then the polynomial itself can be estimated as follows:

1. create a square matrix $X = \begin{bmatrix}x^0 & x^1 & x^2 & ... & x^{n}\end{bmatrix} \in \mathbb{R}^{n\times n}$ containing numerical powers of the input vector.
2. Suppose we construct $A = \begin{bmatrix} a_0 & a_1 & ... & a_{n} \end{bmatrix}^T$ representing the black box polynomial parameters such that $f(x) = a_0 + a_1x+a_2x^2 + ... + a_{n}x^{n}$. Then $f(x) = XA$.
3. use the output vector $S$ to compute $A$ as follows: $A = X^{-1}S$, provided that $X$ is invertible (which should be the case if all entries of $x$ are unique).

If the black box does represent a perfect polynomial, the resulting $A$ vector should be unique and every entry with a higher order than this polynomial should be a flat zero (or approaching floating precision). The uniqueness can be verified by plugging in various different input sets.

This method can become just as troublesome for very large orders of $n$ and can yield just an estimated Taylor series of the function (at least I tested it with a sine function and it did return the Taylor series expansion of it, where the even powers had a parameters smaller than $1e^{-7}$).

Answer 2

I don't know much about "likely". But $N+1$ distinct points uniquely determine a degree $\le N$ polynomial by Lagrange interpolation. If the obtained points are $(x_i, y_i)$, for $i=0, \ldots N$, then first define:

$$L_{N, j}(x) = \prod_{k \ne j}^{N}\frac{x-x_k}{x_j-x_k}$$ (which is clearly a polynomial of degree $N$). The unique polynomial passing through those points is $$p(x) = \sum_{j=0}^{n}y_j L_{N, j}(x),$$ which is a polynomial of degree at most $N$. If you compute one more point from your black box, then you can compare it with this polynomial to see whether it fits.

By the same argument, there is no way to deterministically rule out polynomials given a finite set of input values, since the polynomial described above can always be constructed.

If you choose a constant step size (like $1$), your $p(x_{N+1})$ may be easy to calculate. In that case, you would need to only compute

$$\sum_{j=0}^{n}y_{j}\prod_{j \ne k}(x_{N+1} - x_j) = \sum_{j=0}^{n}y_{j}\prod_{j \ne k}(N+1-j)$$

which doesn't sound over-complex.