¿Los coeficientes de un producto de polinomios mónicos son $0$ y $1$; si los coeficientes de los polinomios son no negativos, también deben ser $0$ y $1$?

Question

He estado atrapado con esta pregunta por... bastante tiempo. Las implicaciones se mencionan después de mi pregunta.

¿Es cierto que si dos polinomios reales $P(x), Q(x)$, tienen su producto igual a un polinomio de 0-1 (por ejemplo, $1+x+x^5+x^{42}$), y se asume que sus coeficientes son no negativos, y ambos son mónicos, entonces estos coeficientes también son 0's y 1's?

Puedo demostrarlo cuando el producto es un polinomio recíproco (un caso de libro es $1+x+x^2+x^3+\cdots+x^n$), pero no logro eliminar esta condición.

Advertencia de que puede existir factores con coeficientes negativos, la suposición es que tanto $P, Q$ no los tienen.

Esto explicaría por qué la Programación Lineal en los campos reales parece encontrar siempre factorizaciones de 0-1 en algunos problemas de teselado en dim. 1 (sé que esto ha sido recientemente desmentido en dimensiones superiores). Esto es un acontecimiento muy gratificante pero sería bueno entender por qué o al menos probarlo...

Answer 1

Esto seguiría de una proposición combinatoria (que propongo pero quizás sea obviamente falsa, todavía no he pensado mucho, pero si $ P (t) $ tiene grado $ \leq 6 $ lo verifiqué). Esto se puede comprobar si es verdadero o falso en cualquier situación dada.

La pregunta es si existe o no tal situación.

Doy una definición primero

1. Un subconjunto $ X $ de $ \mathbb N \times \mathbb N $ ($ \mathbb N $ los números naturales) se dice independiente si el mapa de suma de $ X $ a $ \mathbb N $ es inyectivo,
2. fuertemente dependiente si la partición dada por + en $ X $ (las contraimágenes) tiene todas las partes con al menos 2 elementos,
3. Dos conjuntos $ A, B \subset \mathbb N $ son independientes si $ A \times B $ es independiente.

La pregunta es si hay dos conjuntos finitos $ A, B \subset \mathbb N $ ambos conteniendo 0, con $ h, k $ los máximos respectivos, que se descomponen como $ A = A_0 \cup A_1, \ B = B_0 \cup B_1 $ uniones disjuntas con $ 0, h \in A_0 $ y $ 0, k \in B_0 $.

1. Con $ A_0, B_0 $ independientes
2. $X:= A_1 \times B \cup A \times B_1 $ no vacío y fuertemente dependiente
3. ¿La imagen $ C_0 $ de la suma aplicada a $ A_0 \times B_0 $ es disjunta de la imagen $ C_1 $ de la suma aplicada a $ A_1 \times B \cup A \times B_1 $? En particular $ A_0 \times B_0 $ es disjunta de $ A_1 \times B \cup A \times B_1 $.

El enlace es este. Sea $ A $ el soporte de $ P (t) $, $ B $ el soporte de $ Q (t) $ y $ C $ el soporte de $ R (t)= P (t) Q (t) $, entonces $C=A+B$. Sea $ A_0 $ el subconjunto donde los coeficientes son iguales a 1, del mismo modo $ B_0 $ y $ A_1, B_1 $ los complementos (donde los coeficientes son diferentes de cero y $<1$). Luego $ C $ se descompone en $ C_0 \cup C_1 $ donde $ C_0 $ es la contribución de los términos en $ A_0, B_0 $ y estos conjuntos satisfacen las propiedades previas.

Entonces supongamos que hay un ejemplo con $C_1\neq\emptyset$, la esperanza es llegar a una contradicción. Empezamos construyendo tal ejemplo eligiendo primero el mínimo $i\in A_1$. Nota, si $ i = \min (A_1) $ entonces $ i = \min (A_1) = \min (B_1) $. De hecho, entonces $ i = i + 0 \in C_1 $ y debe haber otro par $ (a, b) \mid a + b = i, b \neq 0 $. Si $ b entonces lo mismo sucede por inducción. Por dualidad $h- \max (A_1) = k-\max(B_1) $

_

Otra observación, el problema puede ser dualizado.

Si $ R (t) = P (t) Q (t) $ con $ P (t), Q (t) $ de grados $ h, k $ tenemos $$ t ^ {h + k} R (1 / t) = t ^ {h} P (1 / t) t ^ {k} Q (1 / t) $$ esto implica que uno siempre puede reducir al caso $ i = \min (A_1) $ con $ 1 \leq i . Entonces, por ejemplo, si $h=6 ($h=k$ no es posible) solo tenemos dos casos para analizar $i=1,2$ ($i=3$ está excluido ya que 3+3=6).

¡El argumento se parece a algún tipo de Sudoku!

$i=3$ no es posible ya que $6=3+3$.

Si $i=2$ debemos tener $(2,0), (0,2)\in +^{-1}(2)\in X$. Entonces $(2,2)\in X:= A_1 \times B \cup A \times B_1 $ y $+^{-1}(4)$ debe tener al menos otro elemento fuera de $(0,4), (1,3),(3,1),(4,0)$ pero $(0,4), (4,0)$ en $X$ pueden ser excluidos de lo contrario $6=2+4\in A_1$. Digamos que $3\in A_1$ entonces $1\in B_0, 3\notin B, 5\notin A$ luego $(3,2)\in X$ y luego debe haber $(0,5)\in X$. \begin{equation}\label{pp} \begin{matrix} A:&0&\emptyset &2&3&\emptyset& \emptyset&6\\ B :&0&1&2&\emptyset &\emptyset &5&\emptyset\end{matrix} \end{equation} Ahora claramente la solución dual tiene $i=3$ que no es posible.

_

Answer 2

Observación:

Supongamos que $P(x)Q(x) = M(x)$, donde $M$ es un polinomio $0-1$ y $P$, $Q$ son polinomios con coeficientes no negativos como en tu pregunta. Define la siguiente propiedad de este producto:

Propiedad 1: Para cada término ($x^n$ por ejemplo) en $M$, existe un par único de términos en $P$ y $Q$ que multiplican de manera única para formar este término.

En primer lugar, parece que la conjetura es fácil de probar con la suposición de que la propiedad 1 se cumple.

En segundo lugar, si la conjetura _es_cierta (por lo que $P$ y $Q$ son necesariamente ambos 0-1) entonces la propiedad 1 debe cumplirse para el producto (es decir, para cada producto).

Answer 3

(No es una respuesta, pero es demasiado largo para un comentario.)

Aquí tienes un buen problema de probabilidad.

Supongamos que tenemos dos dados de seis caras, con caras numeradas $1,\dots,6$. Pero estos no son dados justos, están ponderados. Es decir, la probabilidad de los resultados $1,\dots,6$ para el primer dado son algunos números no negativos $a_1,\dots,a_6$, respectivamente, y para el segundo dado $b_1,\dots,b_6$. ¿Podemos arreglar estos pesos de alguna manera para que, cuando se lancen los dos dados, todos los resultados $2,\dots,12$ para la suma sean igualmente probables?

Respuesta: no. Probablemente puedas encontrar una solución en línea.

Algebraicamente, significa:
El polinomio $\sum_{j=0}^{10} x^j$ no puede factorizarse como $(a_1+a_2x+\cdots+a_6x^5)(b_1 +b_2x+\cdots+b_6x^5)$ con todos los coeficientes no negativos.