¿Determinar si un polinomio tiene coeficientes negativos?

Question

Dado un polinomio con coeficientes enteros, ¿existe una forma elegante de determinar si el polinomio tiene coeficientes negativos con un número mínimo de consultas sobre el valor del polinomio en ciertos valores. También se puede consultar el valor de la derivada del polinomio a determinados valores.

El número de consultas debe ser al menos inferior al grado del polinomio + 1 que puede determinar el polinomio completo.

Answer 1

NB: Esto no es una solución al problema tal y como se plantea; no me fijé en la palabra "entero" cuando lo escribí. Lo dejo sólo para la posteridad].

Buena pregunta. No has dicho si la pregunta $x$ -a priori, o si los valores resultantes $y$ -valor de uno $x$ -puede utilizarse para decidir qué $x$ para usar a continuación.

Lo que sigue es una "solución" al problema menos interesante cuando los coeficientes son reales, en lugar de estar limitados a los enteros; para el problema de los enteros, la solución de Marcus M. da una buena respuesta].

Suponiendo que la "selección de todos $x$ valores a priori", la respuesta a la pregunta básica es "no". ¿Por qué?

Supongamos que nuestro $x$ -Los valores son $1, \ldots, n$ . Dejemos que $$ p(x) = C (x-1) (x-2) \cdots (x-n) $$ Entonces el correspondiente $y$ -Los valores son todos cero. Pero no se puede decir nada sobre los coeficientes, ya que si $C$ es positivo, entonces el coeficiente de $x^n$ es positivo, mientras que si $C$ es negativo, ese coeficiente es negativo. Así que el $y$ -Los valores por sí solos no dan la información que necesitas en este caso.

Permítanme ser aún más explícito. Veamos el caso en el que el grado $n$ es $1$ . Así que $p(x) = Ax + B$ . Usted tiene que evaluar $p$ a exactamente una $x$ -valor. Digamos que eliges $x = 1$ y se obtiene el resultado $A + B$ y supongamos que es $3$ . Entonces las siguientes son todas las posibilidades: $$ A = 3, B = 0 \\ A = 0, B = 3 \\ A = -10, B = 13 \\ \ldots $$

Answer 2

Esta es una respuesta quizás mala pero técnicamente correcta: Desde $\pi$ es trascendental, el valor $f(\pi)$ determina completamente el polinomio $f$ proporcionó $f$ tiene coeficientes enteros. En particular, esto le dice si hay algún coeficiente negativo. Para el caso de elegir $x$ valores de antemano y donde sus coeficientes son números reales---no enteros, como usted afirma---la respuesta de John Hughes explica por qué eso es imposible.

---

EDIT: Una explicación más detallada, para ayudar a explicarlo. Aquí hay un hecho subyacente

La función $F:\mathbb{Z}[x] \to \mathbb{R}$ definido a través de $f \mapsto f(\pi)$ es inyectiva. Por lo tanto, si se conoce $f(\pi)$ entonces se pueden recuperar los coeficientes de $f$ aplicando $F^{-1}$ .

Para ver que $F$ es inyectiva, supongamos que $F(f_1) = F(f_2)$ . Entonces $f_1(\pi) = f_2(\pi)$ es decir $(f_1 - f_2)(\pi) = 0$ . Sin embargo, como $(f_1 - f_2) \in \mathbb{Z}[x]$ Debemos tener que $f_1 - f_2 = 0$ desde $\pi$ es trascendental sobre $\mathbb{Z}$ . Esto demuestra que $F$ es inyectiva.

Como toda función inyectiva es invertible en su imagen, esto significa que dado el valor $f(\pi)$ los coeficientes de $f$ se puede recuperar invirtiendo $F^{-1}$ . Por supuesto, la creación de un algoritmo para calcular realmente $F^{-1}$ es probablemente imposible en la práctica.

Answer 3

Desgraciadamente, no existe una prueba necesaria y suficiente. Si tienes suerte con tus entradas, y el polinomio tiene efectivamente coeficientes negativos, entonces puedes determinar esto con menos entradas (ejemplo obvio: si conectas incluso una entrada positiva y el resultado es negativo).

Veamos por qué no existe tal prueba. Cada entrada nos proporciona una ecuación lineal. Si buscamos nuestro polinomio $$f(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_n x^n,$$ entonces sabiendo, digamos $f(2) = 4$ nos dice que $$4 = a_0 + 2a_1 + 4a_2 + \ldots + 2^n a_n.$$ Si obtenemos $n+1$ de estas ecuaciones, obtenemos un sistema de $n + 1$ ecuaciones lineales en $n + 1$ variables, que (como resulta) tiene una solución única, que nos dice el polinomio.

Cada ecuación, geométricamente, representa un "hiperplano": un $n$ -espacio dimensional de soluciones, en $\mathbb{R}^{n+1}$ . A medida que recogemos más ecuaciones, intersecamos estos hiperplanos, quitando dimensiones (en $3$ dimensiones, digamos, dos de estos planos se cruzarán en una línea, y un tercero se cruzará en un punto único). Si tomamos $n + 1$ Esto da como resultado un punto cuyas coordenadas son nuestro polinomio.

Por lo tanto, si tomamos menos ecuaciones, nos quedamos con un espacio afín no trivial de soluciones, por lo que me refiero a una línea, un plano o un equivalente de mayor dimensión.

Ahora, si queremos garantizar una solución negativa, lo que buscamos es un conjunto de soluciones que echa de menos el ortante positivo del $\mathbb{R}^{n+1}$ es decir, el cono convexo de puntos que sólo tienen coordenadas positivas. Es posible que tengamos suerte y que nuestro conjunto de soluciones no se encuentre en este conjunto por completo.

Pero, puede que nunca lleguemos a la situación en la que nuestro conjunto de soluciones afines no triviales se encuentre totalmente ¡dentro de este ortante! Nunca podremos contener ni siquiera una recta allí, ya que al salir en una dirección siempre se obtendrá una solución con coeficiente negativo. Es decir, como he dicho, podremos demostrar la existencia de un coeficiente negativo si tenemos la suficiente suerte, pero nunca podremos demostrar que los coeficientes son todos positivos a menos que tengamos $n + 1$ ecuaciones.

Answer 4

1. Consulta si para cualquier $x>0$ que $f(x)\le0$ y $f(x+\alpha)<f(x)$ para cualquier $\alpha>0$
2. Consulta si para cualquier $x<0$ que $f(x)\ge0$ y $f(x+\alpha)>f(x)$ para cualquier $\alpha>0$

Algunos casos raros pueden colarse, pero en general esto parece bastante adecuado

Answer 5

Si conocemos la altura $h(f)$ del polinomio $$f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n$$ es decir, $$-b \le a_i \le b$$ donde $b = h(f)$ entonces una única evaluación de $f(2b + 1)$ es suficiente para determinar los coeficientes $a_i$ únicamente.

Véase

Bettina Richmond (2010) On a Perplexing Polynomial Puzzle, The College Mathematics Journal, 41:5, 400-403, DOI: 10.4169/074683410X522017

También está disponible un prepintado aquí .