# Drawing Blanks

Premature Optimization is a Prerequisite for Success

## What did Euler know?

I heard a legend that I refuse to believe. It goes like this:

Euler studied irreducible factorizations of polynomials $x^n - 1$. He noticed that all coefficients that appear in the factors are 1, –1 and 0. E.g. $x^{15}-1=(x-1)(x^2+x+1)(x^4+x^3+x^2+x+1)(x^8-x^7+x^5-x^4+x^3-x+1)$. He attempted to prove that that’s always the case, but he couldn’t. He computed all factorizations up to $x^{100}-1$ and he didn’t see any coefficients other than 1, –1 and 0.

He died convinced that this property always holds. But it doesn’t. Had he factorized $x^{105}-1$, he would see some 2s too.

Did Euler know that the factors are cyclotomic polynomials? Maybe not. Even if he noticed that, he probably wouldn’t be able to prove it. Even if he believed that, he wouldn’t be able to derive any general properties of the coefficients.

But if he really computed all those factorizations up to the power 100, how come he didn’t notice any patterns? I bet he did! He must have come up with some clever methods of computations, and he couldn’t miss the fact that the structure of the factorization of the polynomial depends on the prime factorization of the power. Then why would he stop at 100? Why not check 3*5*7 = 105 ?

Ok, let’s assume the legend is true. Then I’m curious if Euler would really think that the property is true or would consider it an open conjecture? We know that Euler didn’t care much about formal foundations. He died before Cauchy was born, so he never got a chance to put his work on a formal ground. Laplace, on the other hand (according to another legend), did recheck all his work after he learned about Cauchy’s formalism. (I mentioned Laplace here; I think he was at least as brilliant as Euler).