Polinomios de la misión Voyager. Demostrar que para cualquier $p(x)$ $|p(x)(1+x+x^3+x^4+x^6)|+|p(x)(1+x^3+x^4+x^5+x^6)|\geq10$ , donde $|\cdot|$ número de monumentos

Question

Tarea especial de la NASA para las mejores mentes de la MSE (bromeando:).

Consideremos dos polinomas sobre $F_2$

$$ f(x)=1+x+x^3+x^4+x^6,\qquad g(x)=1+x^3+x^4+x^5+x^6 $$

Prueba o refutar que para cualquier polinomio $p(x) \in F_2[x]\setminus\{0\}$ $$ |pf|+|pg|\ge 10,$$ donde $|\cdot|$ es el número de monos no nulos.

Observación 1: Está claro que el límite es agudo - toma $p(x)=1$ obtenemos $|f|+|g|=10$

Observación 2: Ver esta discusión para la motivación, la historia, etc.

Observación 3: Esta pregunta es más bien para divertirse, creo que es bastante agradable ya que es "todo el mundo puede entender", pero demuestra los problemas reales en la teoría de los códigos convolucionales, por lo que podría ser utilizado como ejercicio en la enseñanza, que es por eso que me gustaría compartirlo. Me temo que no existe una solución bonita - hay que considerar muchos casos... Lo que sería realmente grande para encontrar alguna solución "basada en la idea y corto" a este rompecabezas, pero puede ser que no hay tal ... (Alguna solución (probablemente no agradable) debe estar en algún lugar en la literatura sobre los códigos convolucionales).

P.D.

Todo lo bueno en cuestión es de Jyrki Lahtonen, todo lo malo de mí.

P.S.P.S.

El sentido de la pregunta es: demostrar que cierto código de corrección de errores es "bueno".

Piensa en los coeficientes de $p(x)$ como bits de información que desea transmitir. Codificador envía $p(x)$ para emparejar $(pf, pg)$ por lo que se añaden bits de redundancia antes de la transmisión. Si la igualdad es verdadera significa que el código es capaz de corregir $4$ errores ( $4+4<10$ ).

Los chismes dicen que este código ha sido utilizado en la misión Voyager para transmitir estas bonitas fotos . Gracias a "draks" por el enlace a las fotos.

Answer 1

Mis disculpas por aportar lo contrario de la solución "basada en ideas y breve" que pedías: Una búsqueda informática muestra que, como usted sospechaba, $|pf| + |pg| \ge 10$ para todo lo que no sea cero $p\in\mathbb F_2[x]$ .

Supongamos que $p\in\mathbb F_2[x]$ es un contraejemplo. Entonces podemos dividir por la menor potencia de $x$ y todavía tenemos un contraejemplo, así que sin pérdida de generalidad podemos suponer que $p$ tiene un término constante (lo que implica que tanto $pf$ y $pg$ tienen un término constante). Entonces podemos buscar en el árbol de decisión de coeficientes de potencias crecientes; cada decisión sobre un coeficiente determina los correspondientes coeficientes de los productos, que no se ven influidos por decisiones posteriores sobre coeficientes de potencias superiores. Así, al buscar en el árbol de decisión primero en profundidad, podemos llevar la cuenta del número de coeficientes distintos de cero que ya no cambiarán, y abandonar una rama en cuanto llegue a $10$ .

El árbol de búsqueda sólo tiene $1065$ hojas, a una profundidad máxima de $23$ . El código se puede probar un poco sustituyendo $10$ por $11$ lo que hace que descienda indefinidamente por el árbol con $p=1$ .