¿Para qué $(n,k)$ existe un polinomio $p(x) \in F_2[x]$ tal que $\deg(p)=k$ y $p$ divide a $x^n-1$?
Motivación: si existe $p(x)$, entonces el ideal generado por $p(x)$ es un "código corrector de errores cíclico". Parece que no existe para todos los $n,k$, pero MatLab genera algunos polinomios para códigos cíclicos para todos los $n,k$ que he intentado. Así que algo está mal en mi comprensión.
La pregunta probablemente sea elemental, lo siento.
Una versión de este problema ha sido estudiada muy, muy recientemente por Lola Thompson (arXiv) en su tesis de doctorado.
Un valor de $n$ para el cual $x^n-1$ admite divisores (sobre $\mathbb Q$) de todos los grados $k\le n$ se llama $\phi$-práctico. Según trabajos anteriores de Thompson, estos son tan comunes como los números primos: el número de números $\phi$-prácticos hasta $x$ tiene un orden de magnitud de $x/\log x$.
Entonces, para la mayoría de los $n$, hay algún $k \le n$ tal que $x^n-1$ no tiene un divisor de grado $k$. Por supuesto, trabajando sobre $\mathbb F_2[x]$, hay más divisores disponibles. Empíricamente, esto no parece cambiar las cosas en más de un factor constante (hay tablas de conteos para $\mathbb F_2$, $\mathbb F_3$, $\mathbb F_5$ en el preimpreso mencionado anteriormente). Sin embargo, una prueba de densidad cero solo se conoce bajo la hipótesis de GRH.
Thompson y Pollack tienen un resultado condicional (también en GRH) para el problema inverso: para un $k \ge 3$ fijo, el número de $n \le x$ para los cuales $x^n-1$ tiene un divisor de grado $k$ sobre $\mathbb F_2$ es $\ll x/(\log k)^{2/35}$. Así que para $k$ muy grande hay un poco menos de pares $(n,k)$ con la propiedad dada.
Para responder a la pregunta, necesitamos saber algo sobre la factorización de $x^n-1$. Comencemos escribiendo $n=2^\ell m$ con $m$ impar. Entonces $$ (x^n-1)=(x^m+1)^{2^\ell}, $$ y el problema se reduce al caso de un exponente impar.
He dado la respuesta a eso de manera diferente aquí, y la respuesta es que el grado de los factores de $x^m+1$ están en correspondencia 1-1 con los tamaños de los coset cíclicos $2$ módulo $m$. El coset ($2$-) cíclico módulo $m$ de un número entero $a$ consiste en las clases residuales de $2^ja,j=0,1,\ldots$. Si $g$ es una raíz primitiva de la unidad de orden $m$, entonces el coset cíclico $[a]$ de $a$ corresponde al factor $$ f_a(x)=\prod_{j\in [a]}(x-g^j), $$ que claramente es un factor de $x^m-1$ sobre $\mathbb{F}_2[g]$, pero en realidad tiene coeficientes en $\mathbb{F}_2$, porque sus ceros son todos conjugados bajo potencias del automorfismo de Frobenius.
Como ejemplo, consideremos $n=31$. Aquí hay un único coset cíclico de tamaño $1$ concretamente $[0]$ correspondiente al factor obvio $x+1$. Los otros cosets cíclicos tienen todos 5 elementos, por lo que $x^{31}+1$ es un producto de un factor lineal y seis polinomios quínticos irreducibles. Por lo tanto, todos sus factores tienen grados congruentes con cero o uno módulo 5, y todos esos valores ($\le 31$) ocurren.
No sé cómo Matlab lo maneja. Los ingenieros tienen la costumbre de acortar códigos cíclicos, porque puedes usar el polinomio generador incluso si acortas el código al final. Obviamente destruirás la ciclicidad si haces eso. De todos modos, tienes razón. Los códigos cíclicos no existen para todas las combinaciones de $n$ y $k$.
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.
