¿Existe un algoritmo para calcular el grado de un polinomio?

Question

Dejemos que $f\in k[X]$ sea un polinomio en una incógnita sobre cualquier campo (o cualquier anillo conmutativo suficientemente bonito, imagino - no debería importar) y supongamos que todo lo que podemos hacer para entender $f$ es evaluarlo en cualquier $x\in k$ . Trivialmente, si $\deg f$ es conocido, entonces también lo es $f$ por ejemplo, encontrando los valores de $f$ en $\{0,\dots,\deg f-1\}$ y tomando diferencias sucesivas. Pero, ¿y si $\deg f$ ¿se desconoce? Lo más obvio es intentar calcular las diferencias sucesivas en $\{0\},\{0,1\},\{0,1,2\},\dots$ y esperar a que se produzca un patrón, pero mi intuición preliminar me dice que esto no necesariamente funciona. En resumen, ¿es posible calcular $\deg f$ (y por lo tanto $f$ ) a partir de la evaluación en (finitamente muchos) puntos?

Answer 1

No. Si el campo es finito, no se puede reconstruir $f$ incluso calculando $f(x)$ por cada $x \in \mathbb{K}$ . Sólo hay un número finito de funciones de $\mathbb{K}$ a $\mathbb{K}$ pero con infinitos polinomios. Por ejemplo $x^3+x$ evalúa a $0$ por cada $x\in\mathbb{Z}_2$ .

Si el campo es infinito, y se evalúa en un conjunto finito de puntos, existe un polinomio $p$ que se desvanece en el conjunto dado, por lo que de nuevo no tiene ninguna posibilidad de identificar $f$ . (Si $f$ es una solución posible, entonces también lo es $f+p$ .)

Añadido: Curiosamente, si se tiene un polinomio en $\mathbb{Z}[x]$ y saber que todos los coeficientes son positivo puede reconstruir $f$ calculando sólo dos valores. (Calcule $f(1)$ para obtener un límite en el grado y el tamaño de los coeficientes, y luego calcular $f(n)$ para un tamaño suficientemente grande $n$ y leer los coeficientes de la base- $n$ ampliación de $f(n)$ . Rellena los detalles). Para hacer más trampas, calcula $f(x)$ donde $x$ es trascendental sobre $\mathbb{K}$ .

Answer 2

Dados los valores de $f$ en $n$ diferentes puntos en $\mathbb{R}$ hay infinitos polinomios de cada grado $m\geq n$ que asumen esos valores. A menos que tengas algún límite en el grado, no podrás encontrarlo muestreando finitamente muchos puntos, porque nunca sabrás si puede ser mucho más alto de lo que crees.

En un campo finito, la especificación del valor en cada punto del campo será ciertamente suficiente. No, eso está mal.

Answer 3

Para $K=\mathbb{R}$ o $\mathbb{C}$ Si el grado de f es desconocido, no se puede encontrar f evaluándola en un número finito de puntos.

En efecto, tengamos n puntos, se tiene un número infinito de polinomios que pasan por estos puntos