On factoring polynomials whose only coefficients are 0 and 1.

87 Views Asked by At

I say a polynomial $P\left(z\right)=\sum_{n=0}^{d}a_{n}z^{n}$ is digital if for each $n$, $a_{n}\in\left\{ 0,1\right\}$.

Let $\alpha$ be a positive integer $\geq2$, and let $P\left(z\right)$ be a non-zero digital polynomial of degree $d$, where $d\leq\alpha-1$. Supposing that $P\left(z\right)$ and $1-z^{\alpha}$ are not co-prime, let: $$\frac{N\left(z\right)}{D\left(z\right)}$$ denote the irreducible form of the rational function: $$\frac{P\left(z\right)}{1-z^{\alpha}}$$ where both $N\left(z\right)$ and $D\left(z\right)$ are monic polynomials.

Is it necessarily true that $N\left(z\right)$ will be a digital polynomial, and that $D\left(z\right)=1-z^{\beta}$, where $\beta$ is some divisor of $\alpha$?

1

There are 1 best solutions below

2
On BEST ANSWER

The rational function $\, P(z)/(1-z^\alpha) \,$ is the generating function of a sequence of numbers each of which is $0$ or $1$. By construction, the sequence has a period of $\,\alpha.\,$ Let its minimal period be $\,\beta.\,$ Then $\,\beta\,$ must divide $\,\alpha\,$ because the minimal period divides all periods. The generating function is now $\, Q(z)/(1-z^\beta) \,$ where $\, Q(z) \,$ is the generating function polynomial of the repeating part of the sequence and hence is digital just as $\,P(z)\,$ was.