Mathoverflow 339137

Why do polynomials with coefficients 0,1 like to have only factors with 0,1 coefficients?

Reference: mathoverflow/339137 asked by user Sil

def Mathoverflow339137.IsZeroOne (P : Polynomial ℝ) : Prop

The predicate that all coefficients of a polynomial are either zero or one. P.coeffs is the finite set of all nonzero coefficients of the polynomial P. So IsZeroOne P means that every nonzero coefficient of P is equal to 1. Note that zero coefficients are not included in P.coeffs.

Equations

• Mathoverflow339137.IsZeroOne P = (P.coeffs ⊆ {1})

theorem Mathoverflow339137.mathoverflow_339137 (P Q R : Polynomial ℝ) (hP : P.Monic) (hQ : Q.Monic) (hp : ∀ c ∈ P.coeffs, 0 ≤ c) (hq : ∀ c ∈ Q.coeffs, 0 ≤ c) (h : R = P * Q) (hR : IsZeroOne R) : IsZeroOne P ∧ IsZeroOne Q

Let $P(x), Q(x) ∈ ℝ[x]$ be two monic polynomials with non-negative coefficients. If $R(x) = P(x)Q(x)$ is a $0,1$ polynomial (coefficients only from $\{0,1\}$), then $P(x)$ and $Q(x)$ are also $0, 1$ polynomials.

theorem Mathoverflow339137.mathoverflow_339137_probabilistic : (∀ (P Q R : Polynomial ℝ), P.Monic → Q.Monic → (∀ c ∈ P.coeffs, 0 ≤ c) → (∀ c ∈ Q.coeffs, 0 ≤ c) → R = P * Q → IsZeroOne R → IsZeroOne P ∧ IsZeroOne Q) ↔ (True ↔ ∀ (X Y : PMF ℤ), X.support.Finite ∧ Y.support.Finite ∧ Green28.IsUniformOnSupport (Green28.indepSum X Y) → Green28.IsUniformOnSupport X ∧ Green28.IsUniformOnSupport Y)

Green's Open Problem 28 is the probabilistic reformulation of Mathoverflow 339137.

Suppose that $X, Y$ are two finitely-supported independent random variables taking integer values, and such that $X + Y$ is uniformly distributed on its range. Are $X$ and $Y$ themselves uniformly distributed on their ranges?

Mathematically, this equivalence is established via Probability Generating Functions (PGFs), shifting the support to $\mathbb{N}$, and appropriately scaling the coefficients.