Test whether a given function is polynomial 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:

*

*Choose a maximum degree n of the "polynomial" you are testing.

*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]$$

*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,...]

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


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.
