DIRICHLET'S PROOF OF THE THREE-SQUARE THEOREM: AN ALGORITHMIC PERSPECTIVE

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((lgn)(2)(lg lgn)(-1) . M(lgn)). 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.