Pregunta acerca de los polinomios con coeficientes en Z

Question

Vamos $f = a_0 + a_1 x + \ldots + a_n x^n$ ($f \ne 0$), donde $a_i \in \{-1, 0, 1\}$. Deje $p(f)$ ser el número más grande tal que $f(x)$ es divisible por $y$ para cualquier entero $x$ cualquier $1 \leq y \leq p(f)$. Deje $g(n)=max_f\; p(f)$. Es cierto que $g(n) = o(n)$? ¿Cuál es la mejor parte superior o el límite inferior de $g(n)$ puede ser derivada?

Para mi aplicación sería genial para demostrar que $g(n) = o(n)$ con el fin de obtener algo no trivial, o $g(n) = o(n^{2/5})$ con el fin de mejorar el mejor resultado conocido. ¿Crees que es real?

UPD es una obvia consecuencia del postulado de Bertrand Schwartz y–Zippel lema que $g(n) \leq 2n$. El uso de fuerza bruta tengo los siguientes valores:

$g(10) = 7$, $f = x^{10} + x^8 - x^4 - x^2$.

$g(15) = 10$, $f = x^{15} + x^{13} + x^{12} + x^{11} + x^{10} - x^7 - x^6 - x^5 - x^4 - x^3$.

$g(17) = 10$, $f = x^{16} + x^{15} + x^{14} + x^{13} + x^{12} + x^{11} - x^8 - x^7 - x^6 - x^5 - x^4 - x^3$.

Answer 1

Voy a probar el límite superior $g(n) = O(n^{1/2+o(1)})$, que es esencialmente mejor posible si Kevin Costello las heurísticas son correctos.

Supongamos que $q$ es una de las principales con el $q > n^{1/2}+1$. La reducción de la $f(x)$ modulo $x^{q-1}-1$ $\mathbb{Z}[x]$ equivale a reducir los exponentes modulo $q-1$, por lo que el resultado es un polinomio $h(x)$ de grado menor que $q-1$ cuyos coeficientes son en la mayoría de las $n/(q-1) + 1$ (que es menos de $q$) en valor absoluto. Por otro lado, si $q \le p(f)$, $f(x) \bmod q$ es divisible por $x^q-x$ y, por tanto, también por $x^{q-1}-1$, lo $h(x) \bmod q$ debe $0$; esto sólo es posible si $h(x)=0$$\mathbb{Z}[x]$, lo que implica que $f(x)$ se desvanece en el $\phi(q-1)$ primitiva $(q-1)$-th raíces de la unidad. Desde $f(x)$ tiene más de $n$ complejo ceros, obtenemos $\sum_{n^{1/2}+1 < q \le p(f)} \phi(q-1) \le n$ (la suma de rangos de números primos $q$ en el intervalo). El primer número y teorema Teorema de de 327 en Hardy y Wright (que establece que $\phi(m)/m^{1-\delta} \to \infty$ cualquier $\delta>0$), esto es una contradicción para suficientemente grande $n$ si $p(f)>n^{1/2+\epsilon}$ fijos $\epsilon>0$.

EDIT: La más precisa enlazado $\phi(m) \ge (e^{-\gamma} - o(1)) m/\log \log m$ dada por el Teorema de 328 en Hardy y Wright lleva a la $g(n) \le (e^{\gamma}/2 + o(1)) n^{1/2} \log n \log \log n$.

Answer 2

El punto de esta respuesta es señalar que Kevin Costello de la heurística puede ser rigurosa. Para cualquier positivos $\epsilon$ si $y=O(n^{1/2-\epsilon})$, entonces un polinomio existe un gran $n$.

Lema: Vamos a $G$ ser un número finito de abelian grupo y dejar $g_1$, $g_2$, ..., $g_n$ elementos de $G$. Si $2^n > |G|$, entonces existen enteros $\epsilon_i \in \{ -1, 0, 1 \}$, no todos cero, tales que $\sum \epsilon_i g_i =0$.

Prueba: Considerar el $2^n$ sumas $\sum a_i g_i$$a_i \in \{ 0, 1 \}$. Por el principio del palomar, dos de ellas son iguales. Restando ellos, obtenemos la supuesta relación. QED

Ahora, considere el grupo abelian $$G:=\bigoplus_{k=1}^y (\mathbb{Z}/k)^{\oplus k}.$$ Deje $g_i$ a ser el elemento de $G$ cuyas $k$-ésima componente es $(0^i, 1^i, 2^i, 3^i, \ldots, (k-1)^i)$, para $i=0$, $1$, ..., $n$. El orden de $G$$\exp( \sum k \log k) = \exp( O(y^2 \log y))$. Por lo tanto, si $y=O(n^{1/2-\epsilon})$, $2^{n+1} > |G|$ y el lema nos dice que hay $\epsilon_i$ tal que $\sum \epsilon_i g_i=0$. A continuación, $\sum \epsilon_i x^i$ es la necesaria polinomio.

Hay una gran cantidad de holgura en este argumento, pero Bjorn argumento muestra que no podemos mejorar el exponente de $n$ apretándolo.