Dirichlet’s proof of the three-square theorem: An algorithmic perspective

Abstract:

The Gauss–Legendre three-square theorem asserts that the positive integers $n$ expressible as a sum of three integer squares are precisely those not of the form $4^k(8m+7)$ for any nonnegative integers $k,m$. In 1850, Dirichlet gave a beautifully simple proof of this result using only basic facts about ternary quadratic forms. We explain how to turn Dirichlet’s proof into an algorithm; if one assumes the Extended Riemann Hypothesis (ERH), there is a random algorithm for expressing $n=x^2+y^2+z^2$, where the expected number of bit operations is $O((\lg n)^2 (\lg \lg n)^{-1} \cdot M(\lg n))$. Here, $M(r)$ stands in for the bit complexity of multiplying two $r$-bit integers. A random algorithm for this problem of similar complexity was proposed by Rabin and Shallit in 1986; however, their analysis depended on both the ERH and on certain conjectures of Hardy–Littlewood type.