Let . Buscar .

Question

Deje $S=\{p(x) \in \mathbb Z[X] :|p(x)| \leq 2^x, \forall x\in \mathbb N\}$. Encontrar $|S|$.

Esta es una pregunta de seguimiento a esto. (Gracias a @EricWofsey de una brillante respuesta.) Por favor vea el post anterior para ver su prueba ya que no quiero reproducir aquí. Estoy fraseo esto como una cuestión separada porque me quieren aceptar su respuesta. Sin embargo, no es obvio para mí que lo que es exactamente la cardinalidad de a$S$. No he encontrado ninguna polinomios con grado de $> 3$ satisfacen esta propiedad. El que le dio el problema inicial a mí no sabía la respuesta. Hay suficiente evidencia para sospechar que esto va a ser mucho más difícil. Alguien puede proporcionar alguna información? Muchas gracias.

Answer 1

Si no me he hecho de un error de cálculo: Hay exactamente 49 tales polinomios (todos los de grado a lo sumo 3). Ellos son el 23 de polinomios \begin{multline*} \{x-1,x,x+1,2 x-1,2 x,x^2-4 x+1,x^2-3 x,x^2-3 x+1,x^2-2 x-1,\\ x^2-2 x,x^2-2x+1,x^2-x-1,x^2-x,x^2-x+1,x^2-1,2 x^2-5 x+1,\\ 2 x^2-4 x,x^3-6 x^2+6 x+1,x^3-6 x^2+7x-1,x^3-6 x^2+7 x,\\ x^3-6 x^2+8 x-1,x^3-5 x^2+4 x,x^3-5 x^2+4 x+1\}, \end{multline*} sus puntos negativos, y la constante de polinomios $-1$, $0$, e $1$. No es que duro un ejercicio para confirmar que cada uno de estos polinomios satisface los unos límites adecuados, así que permítanme describir cómo me mostró que estos son los únicos candidatos para dichos polinomios.

Como Eric Wofsey mostraron, cada polinomio $p(x)\in S$ se caracteriza por la $6$-tupla $\big( (p(0), p(1), \dots, p(5) \big)$. Hay $3\times5\times9\times17\times33\times65 = 4{,}922{,}775$ tales $6$-tuplas.

Sin embargo, los valores de un polinomio $p(x)$ con coeficientes enteros tiene la propiedad de que si $i \equiv j\pmod m$, a continuación, $p(i)\equiv p(j)\pmod m$. Esta observación conduce a varias comprobaciones de coherencia que se puede hacer para eliminar la mayoría de las $6$-tuplas en la lista anterior; de hecho, sólo $537$ de ellos sobreviven estos filtros.

Para cada uno de los sobrevivientes $6$-tupla, calculamos el polinomio de interpolación de grado en la mayoría de las $5$ tomando los valores en $0,1,\dots,5$. Resulta que todos los polinomios de coeficientes en $\frac12\mathbb Z$.

Algunos de estos polinomios $p(x)$ satisfecho enlazado $|p(6)| \le 2^6$. Si no, entonces (de nuevo, con Eric Wofsey la idea) nos puede tratar de añadir múltiplos de $\frac12x(x-1)(x-2)(x-3)(x-4)(x-5)$ a $p(x)$ a minimizar su valor absoluto en $6$. (Hay un factor de $\frac12$ aquí porque en esta etapa estamos permitiendo que los coeficientes en $\frac12\mathbb Z$.) Pero para muchos de los $537$ polinomios, no hay ninguna modificación que produce un valor absoluto en $x=6$ que es en la mayoría de las $2^6$. Esto demuestra que el correspondiente $6$-tuplas no rendimiento de cualquier polinomio en $S$.

Sólo $183$ polinomios/$6$-tuplas permanecen después de esta etapa. Hacemos una prueba similar para ver si cualquier modificación de cada polinomio que satisface $|p(7)| \le 2^7$; sólo $67$ polinomios/$6$-tuplas sobrevivir. Hacemos una prueba similar para ver si cualquier modificación de cada uno de los restantes polinomio que satisface $|p(8)| \le 2^8$; sólo $49$ polinomios/$6$-tuplas sobrevivir-la $49$ candidato polinomios descrito anteriormente. (Y tratando el mismo procedimiento en $x=9$ e $x=10$ no acotar el conjunto más; y cada polinomio en el conjunto pasó a tener coeficientes no sólo en $\frac12\mathbb Z$ , pero en realidad en $\mathbb Z$.)

He utilizado Mathematica para hacer mis cálculos, y mi código es el siguiente por si ayuda a alguien verificar los cálculos. Una vez que el código fue escrito, los cálculos se tomó unos 30 segundos en mi portátil.

r[t_] := Range[-t, t]

possibleValues = Flatten[Outer[List, r@1, r@2, r@4, r@8, r@16, r@32], 5];

mc[i_, j_, m_][L_] := Mod[L[[i]] - L[[j]], m] == 0

consistentValues = Select[possibleValues,
  mc[1, 3, 2][#] && mc[1, 4, 3][#] && mc[1, 5, 4][#] && mc[1, 6, 5][#]
     && mc[2, 4, 2][#] && mc[2, 5, 3][#] && mc[2, 6, 4][#] && mc[3, 6, 3][#] &];

consistentPolynomials5 = Expand@InterpolatingPolynomial[Transpose[{Range[0,5],#}],x]
  & /@ consistentValues;

centerPolynomialAt[p_,t_] := p - Product[x-j, {j,0,t-1}] Round[p /. x->t, t!/2]/(t!)

possiblePolynomials6 = centerPolynomialAt[#, 6] & /@ consistentPolynomials5;

consistentPolynomials6 = Select[possiblePolynomials6, Abs[(# /. x -> 6)] <= 2^6 &];

possiblePolynomials7 = centerPolynomialAt[#, 7] & /@ consistentPolynomials6;

consistentPolynomials7 = Select[possiblePolynomials7, Abs[(# /. x -> 7)] <= 2^7 &];

possiblePolynomials8 = centerPolynomialAt[#, 8] & /@ consistentPolynomials7;

consistentPolynomials8 = Select[possiblePolynomials8, Abs[(# /. x -> 8)] <= 2^8 &];

consistentPolynomials8positive = Select[consistentPolynomials8,
  Last@CoefficientList[#, x] > 0 &];

SortBy[consistentPolynomials8positive, Reverse@CoefficientList[#, x] &]