The hexagonal versus the square lattice

We establish Schmutz Schaller's conjecture that the hexagonal lattice is `better' than the square lattice. Schmutz Schaller (Bulletin of the AMS 35 (1998), p. 201), motivated by considerations from hyperbolic geometry, conjectured that in dimensions 2 to 8 the best known lattice sphere packings have `maximal lengths' and goes on to write: "In dimension 2 the conjecture means in particular that the hexagonal lattice is `better' than the square lattice. More precisely, let 0<h_1<h_2<... be the positive integers, listed in ascending order, which can be written as h_i=x^2+3y^2 for integers x and y. Let 0<q_1<q_2<... be the positive integers, listed in ascending order, which can be written as q_i=x^2+y^2 for integers x and y. Then the conjecture is that q_i<=h_i for i=1,2,3,..." Our proof requires computational prime number theory in combination with methods from a preprint of the first author (to appear in Math. Comp.), arXiv:math.NT/0112100.