18 votos

¿Cuáles son las propiedades de este polinomio secuencia?

Considere el siguiente polinomio de la secuencia.

$$\begin{cases}a_{-1}=0,~a_0=1, \\a_{n+1}=x \cdot a_n \pm a_{n-1}\end{cases}$$

Aquí $+$ o $-$ es tomado de tal manera que todos los coeficientes en $a_n$ no exceda $1$ en valor absoluto (es decir,$\forall k \hookrightarrow |[x^k]a_n(x)|\leq 1$). La secuencia parece ser infinito, pero lo que es la estricta prueba de ello y cuáles son las propiedades de dicha secuencia? Tal vez por eso tiene nombre único?

También parece que si vamos a escribir $0$ cada vez que lo utilizamos $-$ e $1$ cada vez que lo utilizamos $+$ en secuencia $s_i$, no va a ser $2^{\lfloor\log_2 n\rfloor+1}$ secuencias de $s_i$ que generan corregir $a_i$. Aquí es todo lo $16$ patrones posibles de primera $15$ términos de $s_i$:

001011001011010 110100110100101
001011010011010 110100101100101
001101001010110 110010110101001
001101010010110 110010101101001
010010101101001 101101010010110
010010110101001 101101001010110
010100101100101 101011010011010
010100110100101 101011001011010

Se puede ver cualquier patrón aquí? Tenga en cuenta que en la misma fila es la secuencia y la misma secuencia inversa.

ACTUALIZACIÓN: parece que $s_0$ no importa (ya que produce $a_1=x$ en cualquier forma) y si tenemos en cuenta la secuencia de $g_i$, lo que genera $\{s_i\}_{i=1}^{2^{n}-2}$, su prefijos pueden ser generados como

$$\begin{cases}g_1=\varepsilon,\\g_{n+1}=g_n + (01|10) + g_n^r\end{cases}$$

donde $g_n^r$ representa invierte $g_n$.

15voto

steevc Puntos 211

Aquí es un formalismo algebraico que parece acabar con el problema. Deje ${\mathbb Z}[x]$ ser el anillo de enteros de polinomios en $x$, y deje ${\mathbb Z}[x]^{\mathbb N}$ denotar el anillo de funciones $f: {\mathbb N} \to {\mathbb Z}[x]$ que tomar números naturales $n \in {\mathbb N} = \{0,1,2,\dots\}$ a los polinomios. En este anillo tenemos un cambio homomorphism $T: {\mathbb Z}[x]^{\mathbb N} \to {\mathbb Z}[x]^{\mathbb N}$ definido por $Tf(n) := f(n-1)$ (con el convenio que $f(n)=0$ negativos $n$). Dada una señal patrón de $\epsilon \in \{-1,+1\}^{\mathbb N} \subset {\mathbb Z}[x]^{\mathbb N}$, la solución de la recurrencia $$ a(0) = 1$$ $$ a(n) = x a(n-1) + \epsilon(n) a(n-2) \hbox{ for } n \geq 1$$ (con la convención de las $a(n)=0$ negativos $n$) es equivalente a la localización de un elemento $a \in {\mathbb Z}[x]^{\mathbb N}$ obedeciendo a la ecuación $$ (1 - x T - \epsilon T^2) a = \delta$$ donde $\delta \in {\mathbb Z}[x]^{\mathbb N}$ es la delta de Kronecker, que se define mediante el establecimiento $\delta(0)=1$ e $\delta(n) = 0$ para $n > 0$. Esto tiene una solución única que nos puede escribir como $a = (1 - xT - \epsilon T^2)^{-1} \delta$, donde el inverso se expandió formal de la serie de Neumann.

Presentamos el ${\mathbb Z}[x]$-lineal de operadores de $A, B_\epsilon: {\mathbb Z}[x]^{\mathbb N} \to {\mathbb Z}[x]^{\mathbb N}$ por $A := xT$ e $B_\epsilon := \epsilon T^2$, con lo que estamos tratando de encontrar los patrones de signos de $\epsilon$ tal que $(1 - A - B_\epsilon)^{-1} \delta$ toma los valores de los polinomios con coeficientes en $\{-1,0,+1\}$.

Llamar a un signo de patrón $\epsilon \in \{-1,+1\}^N$ buena si obedece a las siguientes propiedades:

  1. $\epsilon(2n+2)=-\epsilon(2n+3)$ para todos los $n$.
  2. $\epsilon(2^m(2n+3)) = - \epsilon(2^m(2n+1))$ para todos los $n$ y todos los $m \geq 1$.

Uno puede hacer una buena señal de que el patrón de la fórmula $\epsilon(2^m(2n+1)) = \sigma_m (-1)^n$ para todos los $m \geq 1$ y todos los $n$ con signos arbitrarios $\sigma_m \in \{-1,+1\}$, y, a continuación, configuración de $\epsilon(2n+1) = -\epsilon(2n)$ para todos los $n$.

El punto de una buena señal de que el patrón es el siguiente: si $\epsilon$ es bueno, entonces uno tiene el anti-conmutatividad de la propiedad $(A^{2^m} B_\epsilon^{2^m} + B_\epsilon^{2^m} A^{2^m}) f = 0$ siempre $m \geq 0$ e $f \in {\mathbb Z}[x]^{2^{m+1} {\mathbb N}}$ es compatible con los múltiplos $2^{m+1} {\mathbb N}$ de % de${\mathbb N}$. De hecho, esto es equivalente a la identidad $$ \prod_{j=1}^{2^m} \epsilon(2^{m+1} n + 2j) + \prod_{j=1}^{2^m} \epsilon(2^{m+1} n + 2^m + 2j) = 0$$ para cualquier $n$. Para $m=0$ esto es exactamente de la propiedad 1 de una buena secuencia. Para $m>0$ cancelamos fuera un factor común de $\prod_{j=2^{m-1}+1}^{2^m} \epsilon(2^{m+1}+2j)$ a la escritura de la identidad como $$ \prod_{j=1}^{2^{m-1}} \epsilon(2^{m+1} n + 2j) + \prod_{j=1}^{2^{m-1}} \epsilon(2^{m+1} (n+1) + 2j) = 0$$ y, a continuación, observar, desde la propiedad 2 $\epsilon(2^{m+1}(n+1) + 2j) = \epsilon(2^{m+1} n + 2j)$ al $1 \leq j < 2^{m-1}$ e $\epsilon(2^{m+1}(n+1)+ 2j) = -\epsilon(2^{m+1} n + 2j)$ para $j = 2^{m-1}$.

El uso de este anticommutativity y la inducción obtenemos el tipo Frobenius de la identidad $$ (A + B_\varepsilon)^{2^m} f = (A^{2^m} + B_\varepsilon^{2^m}) f$$ siempre que $m \geq 0$ e $f \in {\mathbb Z}[x]^{2^m {\mathbb N}}$ (tenga en cuenta que $A^{2^m}$ e $B_\varepsilon^{2^m}$ mapa de ${\mathbb Z}[x]^{2^{m+1} {\mathbb N}}$ a ${\mathbb Z}[x]^{2^{m} {\mathbb N}}$). Un similares de inducción, a continuación, conduce a la identidad $$ (1-A-B_\epsilon) \prod_{i=0}^{m-1} (1 + A^{2^i} + B_\epsilon^{2^i}) f = (1 - A^{2^m} - B_\epsilon^{2^m}) f$$ siempre que $m \geq 0$ e $f \in \mathbb{Z}[x]^{2^m {\mathbb N}}$, donde el producto se ordena de izquierda a derecha, así $$ \prod_{i=0}^{m-1} (1 + A^{2^i} + B_\epsilon^{2^i}) = (1 + A + B_\epsilon) (1 + A^2 + B_\epsilon^2) \dots (1 + A^{2^{m-1}} + B_\epsilon^{2^{m-1}}).$$ La especialidad de a $f=\delta$, aplicando $(1-A-B_\varepsilon)^{-1}$ y, a continuación, envío de $m$ hasta el infinito obtenemos la fórmula $$ (1-A-B_\epsilon)^{-1} \delta = \prod_{i=0}^{\infty} (1 + A^{2^i} + B_\epsilon^{2^i}) \delta$$ (donde el producto converge pointwise). Uno puede comprobar que cada término en este pointwise producto les da otro monomio encuentra en un punto diferente con coeficiente de $\pm 1$, por lo que este hecho da una secuencia $a(n) \in {\mathbb Z}[x]$ para $n \in {\mathbb N}$ con el de las propiedades, con la forma explícita $$ a = (1 + A + B_\epsilon) (1 + A^2 + B_\epsilon^2) (1 + A^4 + B_\epsilon^4) \dots \delta.$$

Para dar sentido de esta fórmula, si escribimos $a$ como una secuencia $a(0),a(1),a(2),\dots$, luego $$ \delta = 1, 0, 0, \dots$$ $$ (1+A+B_\epsilon) \delta = 1, x, \epsilon(2), 0, \dots$$ $$ (1+A+B_\epsilon) (1+A^2+B_\epsilon^2) \delta = 1, x, \epsilon(2) + x^2, x^3, \epsilon(2)\epsilon(4) + \epsilon(2) x^2, \epsilon(2)\epsilon(4) x, \epsilon(2)\epsilon(4)\epsilon(6),0, \dots$$ y uno converge a $$ a(0) = 1$$ $$ a(1) = x$$ $$ a(2) = \epsilon(2) + x^2$$ $$ a(3) = x^3$$ $$ a(4) = \epsilon(2) \epsilon(4) + \epsilon(2) x^2 + x^4 $$ $$ a(5) = \epsilon(2) \epsilon(4) x + x^5 $$ $$ a(6) = \epsilon(2)\epsilon(4) \epsilon(6) + \epsilon(6)x^4 + x^6 $$ $$ \dots$$ que es un reparameterisation de las soluciones anteriores.

Uno puede mostrar que estas son en realidad las únicas secuencias de polinomios $a$ que mantienen sus coeficientes en $-1,+1$, pero la prueba de esta singularidad es un poco tedioso de inducción y esta respuesta ya es bastante largo, así que voy a dejar como un ejercicio.

9voto

Michael L Puntos 1429

No hay pruebas, sólo hechos experimentales (de ahí cw):

Deje $a_{n+1}=xa_n+\varepsilon_{n+1}a_{n-1}$, con $\varepsilon_k=\pm1$; a continuación, $\varepsilon_{2^k}$ podría ser arbitraria, mientras que todos los demás se determina únicamente por ellos. Durante los primeros casos que hemos $$ \begin{aligned} \varepsilon_{3}&=-\varepsilon_{2}\\ \varepsilon_{5}&=-\varepsilon_{4}\\ \varepsilon_{6}&=-\varepsilon_{2}\\ \varepsilon_{7}&=\varepsilon_{2}\\ \varepsilon_{9}&=-\varepsilon_{8}\\ \varepsilon_{10}&=\varepsilon_{2}\\ \varepsilon_{11}&=-\varepsilon_{2}\\ \varepsilon_{12}&=-\varepsilon_{4}\\ \varepsilon_{13}&=\varepsilon_{4}\\ \varepsilon_{14}&=-\varepsilon_{2}\\ \varepsilon_{15}&=\varepsilon_{2}\\ \varepsilon_{17}&=-\varepsilon_{16}\\ \varepsilon_{18}&=\varepsilon_{2}\\ \varepsilon_{19}&=-\varepsilon_{2}\\ \varepsilon_{20}&=\varepsilon_{4}\\ \varepsilon_{21}&=-\varepsilon_{4}, \end{aligned} $$ los polinomios de ser, respectivamente, $$ \begin{aligned} a_1&=x \\ a_2&=x^2+\varepsilon_{2} \\ a_3&=x^3 \\ a_4&=x^4+\varepsilon_{4}x^2 +\varepsilon_{2} \varepsilon_{4} \\ a_5&=x^5+\varepsilon_{2} \varepsilon_{4}x \\ a_6&=x^6-\varepsilon_{2}x^4 -\varepsilon_{4} \\ a_7&=x^7 \\ a_8&=x^8+\varepsilon_{8}x^6 -\varepsilon_{2} \varepsilon_{8}x^4 -\varepsilon_{4} \varepsilon_{8} \\ a_9&=x^9-\varepsilon_{2} \varepsilon_{8}x^5 -\varepsilon_{4} \varepsilon_{8}x \\ a_{10}&=x^{10}+\varepsilon_{2}x^8 -\varepsilon_{8}x^4 - \varepsilon_{4} \varepsilon_{8}x^2-\varepsilon_{2}\varepsilon_{4} \varepsilon_{8} \\ a_{11}&=x^{11}-\varepsilon_{4} \varepsilon_{8}x^3 \\ a_{12}&=x^{12}-\varepsilon_{4}x^{10} -\varepsilon_{2} \varepsilon_{4}x^8 + \varepsilon_{8}x^2+\varepsilon_{2}\varepsilon_{8} \\ a_{13}&=x^{13}-\varepsilon_{2} \varepsilon_{4}x^9 +\varepsilon_{2} \varepsilon_{8}x \\ a_{14}&=x^{14}-\varepsilon_{2}x^{12} +\varepsilon_{4}x^8 - \varepsilon_{8} \\ a_{15}&=x^{15} \\ a_{16}&=x^{16}+\varepsilon_{16}x^{14} -\varepsilon_{2} \varepsilon_{16}x^{12} +\varepsilon_{4} \varepsilon_{16}x^8 -\varepsilon_{8} \varepsilon_{16} \\ a_{17}&=x^{17}-\varepsilon_{2} \varepsilon_{16}x^{13} + \varepsilon_{4} \varepsilon_{16}x^9 - \varepsilon_{8} \varepsilon_{16}x \\ a_{18}&=x^{18}+\varepsilon_{2}x^{16} -\varepsilon_{16}x^{12} +\varepsilon _{4} \varepsilon_{16}x^{10} +\varepsilon_{2}\varepsilon_{4} \varepsilon_{16}x^8 - \varepsilon_{8} \varepsilon_{16}x^2 -\varepsilon_{2} \varepsilon_{8} \varepsilon_{16} \\ a_{19}&=x^{19}+\varepsilon_{4} \varepsilon_{16}x^{11} - \varepsilon_{8} \varepsilon_{16}x^3 \\ a_{20}&=x^{20}+\varepsilon_{4}x^{18} +\varepsilon_{2} \varepsilon_{4}x^{16} +\varepsilon_{16}x^{10} +\varepsilon_{2}\varepsilon_{16}x^8 -\varepsilon_{8} \varepsilon_{16}x^4 -\varepsilon_{4}\varepsilon_{8} \varepsilon _{16}x^2 -\varepsilon_{2}\varepsilon_{4}\varepsilon_{8} \varepsilon_{16} \\ a_{21}&=x^{21}+\varepsilon_{2} \varepsilon_{4}x^{17} +\varepsilon_{2} \varepsilon_{16}x^9 - \varepsilon_{8} \varepsilon_{16}x^5- \varepsilon_{2} \varepsilon_{4} \varepsilon_{8} \varepsilon_{16}x \end{aligned} $$

6voto

Brady Puntos 273

Más hechos experimentales. Creo que no debería ser muy difícil probar por inducción, teniendo en cuenta que sabemos exactamente cuando los coeficientes de $a_n$ son no-cero (ver mi comentario a მამუკა ჯიბლაძე la respuesta).

Dada una secuencia $\epsilon_{2^n}\in\{-1,+1\}$ para $n\ge1$, vamos a definir de forma inductiva la secuencia de $(\epsilon_j)_{j\ge1}$ para todos los enteros positivos de acuerdo a las relaciones de recurrencia:

$$\epsilon_{2^n+1}=-\epsilon_{2^n}\qquad\text{for }n\ge1 $$

$$\epsilon_{2^n+j}=\epsilon_{2^n-j+1}\qquad\text{for }2\le j< 2^n\ ,$$

y también definir

$$ \eta_j:=\begin{cases} (-1)^{ j\over 2},& \text {for even }\ j \\ \\ (-1)^{ j-1\over 2}\epsilon_{j+2}, &\text {for odd } j \ .\\ \end{casos} $$ y $$ \delta_j:=\begin{cases} -1,& \text {for }\ j=0 \\ \\ 1, &\text {for } j\neq0 \ .\\ \end{casos} $$

Entonces (experimentalmente) los polinomios $a_k= a_k(x,\epsilon_2,\epsilon_4,\dots,\epsilon_{2^n})$ se determinan inductivamente por $a_{-1}:=0, a_0:=1$, y por la relación de recurrencia, para cualquier $0\le n$ y cualquier $0\le j< 2^n\ $

$$a_{2^n+j}=x^{2^n}b_j+ {\delta_{2^{n-1}-1-j}}\ \eta_j\ \epsilon_{2^n}\ a_{2^n-2-j},$$

donde
$$b_j:=a_j(x,\epsilon_2,\epsilon_4,\dots,\epsilon_{2^{n-2}},-\epsilon_{2^{n-1}})\ .$$

Por, ejemplo, el de arriba te da $$a_{51}={x}^{51}-\epsilon_{{4}}\epsilon_{{16}}{x}^{43}+ \epsilon_{{8}} \epsilon_{{16}}{x}^{35}+ \epsilon_{{4}}\epsilon_{{32}}{x}^{11}-\epsilon_ {{8}}\epsilon_{{32}}x^3$$

2voto

graphics Puntos 414

No una respuesta, pero demasiado largo para un comentario.

Para el $a_n$ como en მამუკა ჯიბლაძე la respuesta, vale la pena mirar pares e impares índices por separado. De hecho, para $n$ impar, $a_n$ sólo parece haber condiciones para $x^{n-4k}$ e $[x^{n-4k}]a_n=[x^{n-4k-1}]a_{n-1}$, por lo que toda la información está contenida en el polinomios.

Escrito $r$ para $\varepsilon_{2^r}$ y mantener los signos, tenemos los siguientes coeficientes:

$\begin{array} {rrrrrrrrrrrrrrrr} n&|&x^{n-2}&x^{n-4}&.&x^{n-8}&.&.&.&x^{n-16}\\ \hline 2&|&1\\ \hline 4&|&2&12\\ 6&|&-1&&-2\\ \hline 8&|& 3&-13&&-23\\ 10&|& 1&&-3&-23&-123\\ 12&|& -2&-12&&&3&13\\ 14&|& -1&&2&&&&-3\\ \hline 16&|& 4&-14&&24&&&&-34\\ 18&|& 1&&-4&24&124&&&-34&-134\\ 20&|& 2&12&&&4&14&&-34&-234&-1234\\ 22&|& -1&&-2&&&&-4&-34&134&&234\\ \end{array}$

Excepto para las señales, que mantener algo de misterio, los patrones de las columnas parecen ya esencialmente predecible, todo en los términos si el A006519 secuencia. Si calcular algunas líneas más, debe ser totalmente clara (por ejemplo, lo que sucede en la 5ª columna?), y a partir de hay, por supuesto, se puede demostrar que algunos de inducción.

Si se añade a su lista de $\varepsilon_{n}$'s de las líneas de $\varepsilon_{2^k}=\varepsilon_{2^k}$ de exhaustividad, a continuación, el patrón de los índices de 2,2,4,4,2,2,8,8,2,2,4,4,2,2,16,16... en particular, también debe ser isomorfo a (duplicado) A006519 secuencia. Pero las señales...? (Tristemente, $\varepsilon_{22}=-\varepsilon_{2}$.)

También tenga en cuenta que la "diagonal principal" de esta tabla (es decir, la matriz de los términos absolutos de los $a_n$), tomado como un código binario, parece encapsular un bijection $ 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, ...$ de $\mathbb N\to\mathbb N$, más precisamente el código Gray A003188.

1voto

Brady Puntos 273

En la singularidad de la vista de los datos $\{\epsilon_{2^n}\}_{n\ge1}$. Como se observa por Terry Tao en un comentario, el signo de $xa_{m-1}\pm a_{m-2}$ es forzado precisamente cuando por alguna $r$, uno tiene $$[x^r](xa_{m-1})=[x^r]a_{m-2}=1\mod 2$$ (because for integers $a,b$ in $\{-1,0,1\}$ the equation $|a+\epsilon b|\le1$ has a unique solution $\epsilon$ in $\{-1,1\}$ if and only if $|a|=|b|=1$). But the parity of the coefficients of the $a_m$ es conocido, para $a_m=\sum_{0\le j\le{n/2}}{m-j\choose j}x^{m-2j}\mod 2$ (esto se sigue inmediatamente por inducción a partir de la aditivo fórmula de binomios).

Por lo tanto, el valor de $\epsilon_m$ es libre si y sólo si $ {m-i\choose i-2}{m-i\choose i-1}$ es incluso para todos los $i\ge2$. Pero este no es el caso si $m$ no es una potencia de $2$: de hecho, si por alguna $a$ uno ha $2^a<m<2^{a+1}$,, a continuación,$2\le i:=m-2^a+1\le 2^a$, lo $m-i=2^a-1$, y tanto $ {m-i\choose i-2}$ e ${m-i\choose i-1}$ son impares, ya que todos los coeficientes binomiales ${2^a-1 \choose k}$ para $k=0,\dots,2^a-1$ son impares.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X