High school deconvolution


One of my favorite formulas is the factorization of 1-x^n:

1 - x^n = (1 - x)(1 + x + x^2 + \dots + x^{n-1}).

This is a fairly ubiquitous formula that most people would have seen in high school, perhaps in various guises. A common special case is (1-x)(1+x) = 1- x^2, which is itself a special case of the “sum of squares” formula (a-b)(a+b) = a^2 - b^2.

The irreducible factors of 1 + x + x^2 + \dots + x^{n-1} are the cyclotomic polynomials which have many interesting links to number theory.

In other areas, substituting something nice for x leads to interesting formulas/results. When x is some prime power p^e (usually written q), the quantity

\frac{1-q^n}{1-q} = 1 + q + \dots + q^{n-1}

is the q-analog of n. The reason for the name is that as we let q \to 1, we get

\lim_{q \to 1} \frac{1-q^n}{1-q} = n.

This observation forms the starting point of the study of combinatorial q-analogs. Toggling between q=1 and q=p^e allows one to view sets as vector spaces over the “field” of 1 element.

However, I won’t be writing about that today. Instead, this post is about a curious connection between that simple formula above and deconvolution.

Continue reading