Interpolación de determinados coeficientes

Question

Diga $F(X) \in \mathbb{Z}[X]$ es un polinomio de grado par de grado $2n$ .

Hay que evaluar $F(X)$ en $O(n)$ puntos para interpolar y obtener todos los coeficientes de $F(X)$ .

Sin embargo digamos que necesito sólo el coeficiente de $X^{n}$ o $X^{2n}$ (el coeficiente medio o el mayor), ¿sigo teniendo que evaluar en $O(n)$ ¿puntos?

Tendrá coeficiente de $X^{t}$ igual que el coeficiente de $X^{2n-t}$ ayudar a reducir el número de puntos de $O(n)$ detectar $X^{n}$ coeficiente (coeficiente medio en el caso simétrico)?

¿Se trata de un problema bien estudiado y con buenas referencias, es decir, interpolar sólo uno o unos pocos coeficientes?

Hay una forma de hacerlo: evaluar en un primo grande y reducir mediante operaciones de módulo. Sin embargo, esto da demasiada información (es decir, puedo obtener todos los coeficientes) y cuando evalúo en un primo grande, el tamaño de la palabra se convierte en el orden de $O(n\log(nM))$ donde M es el mayor tamaño del coeficiente. Así que, en cierto modo, seguimos utilizando $O(n^{1+\epsilon})$ operaciones.

Supongo que debería haber una forma de obtener sólo información sobre el coeficiente que me interesa y reducir las operaciones a $O(n^{1-\epsilon})$ a "costa de no obtener" información sobre otros coeficientes.

Digamos que tienes un polinomio de grado impar (coeficientes pares). Evaluando en $1$ y $-1$ y sumando los resultados o restándolos, localiza la información en grupos de dos coeficientes. Mi pregunta podría ser ¿se puede localizar más? Suponiendo además que tengo $F(x) = A(x)B(x)$ donde sé $A(x)$ y $B(x)$ ¿es posible representar $A(x)$ y $B(x)$ de una manera diferente para que pueda apuntar de alguna manera el coeficiente medio de $F(x)$ sin obtener otros coeficientes?

Answer 1

Salvo trucos como evaluar a un número grande/irracional con gran precisión, dudo que puedas hacer nada. Digamos que evalúas en $2n$ sólo puntos, $x_1,\dots,x_{2n}$ (que es uno menos de los que necesitarías para saber todo sobre el polinomio). Entonces nunca sabrás si estabas trabajando con el polinomio $p(x)$ o con $p(x)+K(x-x_1)(x-x_2)\cdots(x-x_{2n})$ para algunos $K$ . Y el coeficiente principal de este último depende de $K$ .

(aunque no necesariamente el coeficiente central, si se elige el $x_i$ adecuadamente. Hmmm, quizás necesitemos un argumento más complicado para el coeficiente central. Pero este argumento definitivamente funciona para el término principal).

Answer 2

Voy a convertir mi comentario anterior en una respuesta, tal vez le aclare las cosas al OP.

Teorema: Sea $1\le m\le n$ , $m\le k\le2n$ , $a_1,\dots,a_k\in\mathbb Q$ . Entonces existen polinomios $A,B,\tilde A\in\mathbb Z[x]$ de grado $n$ tal que $AB$ y $\tilde AB$ tienen distintos $k$ coeficiente, pero $A(a_i)B(a_i)=\tilde A(a_i)B(b_i)$ para cada $i=1,\dots,m$ .

Prueba: Ponga $A=0$ , $A'=cx^r\prod_{i=1}^m(x-a_i)$ , $B=x^s$ donde $k=m+r+s$ , $r+m,s\le n$ y $c$ se elige de forma que $A'$ tiene coeficientes enteros (es decir, $c$ es múltiplo del producto de los denominadores del $a_i$ s).

Por lo tanto, si desea extraer el $k$ coeficiente por evaluación en puntos racionales, es absolutamente necesario al menos $k+1$ puntos, y por lo tanto el tiempo $\Omega(k)$ .

De hecho, cualquier algoritmo de extracción del $k$ coeficiente de $AB$ necesita tiempo $\Omega(k)$ . La razón es que el coeficiente es igual a $\sum_{i\le k}A_iB_{k-i}$ y por lo tanto depende en $2k+2$ de los números de entrada en el sentido de que cambiar cualquiera de ellos puede cambiar el resultado. De hecho siempre cambiar el resultado a menos que el coeficiente de coincidencia en el producto sea $0$ por lo que, incluso en el mejor de los casos, tendremos que leer al menos uno de los siguientes documentos $A_i$ o $B_{k-i}$ para cada $i$ para fijar el resultado, es decir, necesitamos utilizar al menos $k+1$ de los números de entrada, y por lo tanto necesitamos tiempo al menos $k+1$ . No hay forma de evitarlo.

Teniendo en cuenta este hecho, probablemente sea mejor atenerse a la evaluación directa de la fórmula $\sum_{i=0}^kA_iB_{k-i}$ que calcula el resultado utilizando $k+1$ multiplicaciones y $k$ adiciones. Dado que necesita al menos $k$ más o menos utilizando cualquier otro método, éste es prácticamente óptimo y, además, es sencillo y fácil de aplicar.

Los métodos más sofisticados (como la evaluación y la interpolación) sólo son útiles si necesita extraer muchos coeficientes del polinomio, porque ahorran algunos cálculos repetidos. No te servirán de nada si sólo necesitas un coeficiente.

Answer 3

Si hay coeficientes iguales para $x^{2n-t}$ y $x^t$ para todos $0 \le t \lt n$ entonces tenemos $n+1$ coeficientes desconocidos por lo que $n+1$ puntos es suficiente. Por supuesto, esto sigue siendo $O(n).$ Entonces el c oeficiente superior es $y(0)$ pero eso no es divertido. Me centraré en el coeficiente medio.

• Para el caso cuadrático $y=ax^2+bx+a$ tenemos $y(i)=bi.$

• Para $y=ax^4+bx^3+cx^2+bx+a$ tenemos $y(I)=2a+c$ y $y(0)=a.$

• para $y=ax^6+bx^5+cx^4+dx^3+cx^2+bx+a$ basta con tener $y$ en $i$ y en $\frac{\pm1+\sqrt{3}i}{2}$

Esto sugiere una reducción de $n+1$ a $n$ puntos. Esto no es utilizar el hecho de que los coeficientes son números enteros.

Para el caso $2n=4$ allí los valores $u=\sqrt{-2+\sqrt{-5}},v=-\sqrt{-2-\sqrt{-5}}$ escriba a $v^4+1=-(u^4+1)$ , $v^3+v=-(u^3+u)$ pero $v^2 \ne -u^2$ así se puede encontrar $c$ junto con una determinada combinación lineal de $a,b$ pero no $a$ o $b.$

Una pregunta útil podría ser "tenemos un polinomio de grado $2n$ con coeficientes enteros (simétricos). ¿Cuántas evaluaciones de la función se necesitan para decidir si el coeficiente medio es $0$ ¿o no?"

No sé si considera razonables las aportaciones complejas. Me imagino que uno podría ser capaz de utilizar un campo finito apropiado en su lugar.

Parece que otra pregunta es algo así como: "Supongamos que $a_1,a_2,\cdots,a_k$ son valores tales que $f(a_i)=0$ donde $f$ tiene grado $2n$ . ¿Qué condiciones $n,k$ los coeficientes y el $a_i$ son tales que $f$ está obligado a ser el polinomio cero (o a que el grado de un determinado coeficiente sea cero)" Las condiciones pueden ser límites de tamaño. Esto está relacionado con la cuestión de cuán pocas evaluaciones determinan el coeficiente o coeficientes sin tener en cuenta cuánto trabajo cuesta extraerlos.

Answer 4

¿Tiene una estimación del tamaño del mayor coeficiente? Para unos pocos primos de tamaño moderado $p$ calcula $(p^{2n} F(1/p))\ {\rm mod}\ p$ que le da el coeficiente de $X^{2n}$ mod $p$ entonces usa el Resto Chino.

Answer 5

Si tienes un límite en los coeficientes, entonces ciertamente puedes obtener el coeficiente de grado más alto evaluando en un punto (cuéntalos), ya que sólo estás tratando de evaluar el límite de $P(X)/X^N,$ donde $N$ es el grado, y sabes que la respuesta es un número entero. Si no tienes ese límite, dudo que puedas hacer algo mejor que lo obvio (donde "lo obvio" podría ser "evaluar el polinomio en las raíces de la unidad y hacer la transformada inversa de Fourier", o "evaluarlo en números enteros pequeños y hacer la interpolación de Lagrange").