Factorisation and roots of infinite polynomial

Question

Recently, I’ve learned about generating functions. From my understanding you basically represent each “option” with a polynomial, and the resulting polynomials multiplied would give coefficients related to the number of ways you can choose some objects.

So here, I’m trying to apply the same thing to binary numbers! Using $x^{2^n}+1$ to represent 2^n in binary and multiplying first 3 terms of it i.e. $(x+1)(x^2+1)(x^4+1)=\sum_{i=0}^7x^i$ I can show that 0-7 has unique representation in binary!

However, I would like to prove this for all natural numbers. Simple, simply multiply $\Pi_{i=0}^\infty (x^{2^i}+1) $ what I would get would be $1+x+x^2+...$. Ayyy! $\frac{1}{1-x}$! I quickly write down

Some might see the problem here, but we said that $\frac{1}{1-x}=\Pi_{i=0}^\infty x^{2^i}+1$. The problem here is that (I GIVE UP PHONE LATEX) LHS has no roots while RHS has infinitely many roots i.e. x=1, x^2=-1, ...

$$\frac{1}{1-x}=\Pi_{i=0}^\infty x^{2^i}+1 $$

question: why do they not match in terms of roots, even though they “clearly is the same”?

Also I believe you can do the same “factorisation” in different “base”. Is the factorisation even valid? It’s not unique though...

Gareth

Sorry it’s hard to type and format latex on phone

Answer 1

They are not the same. $\frac{1}{1 - x} = \sum_{i = 0}^\infty x^i$ only when $|x| < 1$. All the roots of the infinite polynomial occur when this condition is not satisfied. In fact, $|r| = 1$ for all roots $r$.

You can do this factorization in any base if you include as the exponents all multiples of the powers of the base up to $b - 1$. So for base three, the product would be $\prod_{i = 0}^\infty (1 + x^{3^i}+x^{2 \cdot 3^i})$

Answer 2

We want to show that $$\frac{1}{1-x} = (1+x)(1+x^2)(1+x^4)(1+x^8)\cdots $$ An equivalent statement is $$1 = (1-x)(1+x)(1+x^2)(1+x^4)(1+x^8)\cdots \tag{*}$$ Now notice that $$\begin{align} (1-x)(1+x)(1+x^2)(1+x^4)(1+x^8)\cdots &= (1-x^2)(1+x^2)(1+x^4)(1+x^8)\cdots \\ &= (1-x^4)(1+x^4)(1+x^8)\cdots \\ &= (1-x^8)(1+x^8) \cdots \\ & \vdots \end{align}$$ from which we conclude that the infinite product is equal to $1$, proving $(*)$.

In working with generating functions, we often do not worry about questions of convergence of series; rather, we regard the series as formal objects subject to certain rules. This is OK so long as we do not attempt to actually evaluate the series, but if we do evaluate the series then questions of convergence apply. So it would be incorrect to attempt to evaluate the infinite product $(*)$ at $x=i$, for example, because the product does not converge there.