Encontrar los coeficientes de un polinomio con consultas mínimas

Question

Considere el siguiente juego, jugado entre Alice y Bob: Alice elige un polinomio $p(x) \in \mathbb{Z}[x]$ donde los coeficientes son todos mayores o iguales a $-1$ . El objetivo de Bob es determinar el polinomio; para ello puede pedir a Alice que evalúe el polinomio en cualquier punto racional.

¿Hay algún protocolo que Bob pueda seguir para encontrar $p(x)$ (es decir, encontrar todos sus coeficientes)? Si es así, ¿cuál es el mejor límite del número de pasos necesarios?

Antecedentes: Esta es una generalización de un acertijo que escuché de Sergiu Hart. La pregunta es la misma que la anterior, pero $p(x)$ se sabe que tiene coeficientes enteros no negativos (y no sólo mayores que $-1$ ). Con esta restricción adicional, Bob puede encontrar $p(x)$ con un número sorprendentemente pequeño de consultas.

Nota adicional: Si a Bob se le permite pedir evaluaciones sobre puntos reales, en lugar de sólo racionales, es casi trivial que pueda encontrar $p(x)$ con una sola consulta (aunque podría decirse que esto es hacer trampa).

Answer 1

Comience por consultar $p(2)$ . Ahora afirmo que el coeficiente principal de $p$ es menor o igual que $M=\max(1,p(2)+1)$ . De hecho, si $p(x)=a_nx^n+a_{n-1}x^{n-1}\dots+a_0$ entonces $$p(2)\geq a_n2^n-2^{n-1}-\dots-1=a_n2^n-2^n+1>(a_n-1)2^n$$ que es al menos $a_n-1$ a menos que $a_n\leq 1$ . De ello se desprende que $a_n\leq M$ .

Ahora bien, tenga en cuenta que si $q$ es un primo que no divide el coeficiente principal de $p$ entonces el denominador de $p(1/q)$ en términos mínimos será $q^n$ donde $n=\deg p$ . Por lo tanto, dejemos que $q$ sea un primo mayor que $M$ y consulta $p(1/q)$ para determinar el grado de $p$ . Una vez que tenemos el grado de $p$ podemos determinar $p$ con $\deg p+1$ preguntas.

---

Este método se generaliza al caso de que exista cualquier límite inferior en los coeficientes de $p$ . En efecto, si los coeficientes de $p$ son todos al menos $-N$ entonces podemos consultar $p(N+1)$ para obtener de forma similar una cota superior en el coeficiente principal de $M$ (ya que los términos negativos de grado inferior no podrán alcanzar al término principal). Hace un uso crucial de poder consultar entradas racionales, y no sólo enteras. No sé si es posible hacerlo sólo con entradas enteras. Tampoco sé si es posible hacerlo con un límite (independiente de $p$ ) sobre el número de consultas.