In this mathematical tour de force, the authors prove distribution properties of greedy sums of distinct squares (GSDSs), a subject that would seem to have received scant attention in the literature. A positive integer is a GSDS if there are no duplicate summands in its representation as a sum of squares, in which each successive summand is as large as possible. For example, 30 = 52 + 22 + 12 is a GSDS; 31 = 52 + 22 + 12 + 12 is not. A facile argument suggests that the set of GSDSs has natural density of 4/9; a glance at some numbers might suggest a natural density of 1/2. The authors refute these intuitions, showing that the set has, in fact, no natural density, but that the counting function exhibits a predictable oscillation.
The authors proceed by considering the counting function A(v), defined to be one plus the number of GSDSs less than v. They devote the bulk of the work to a detailed proof that the limit, as integer k increases without bound, of A(vkx)/vkx, where vkx is my shorthand notation for 4exp(2k+x), is a continuous nonconstant function of x with period 1; or, as they put it in plain words, “A(v)/v has persistent wobbles on a log log scale.” They further show that this function is bounded below by 0.50307, and above by 0.50964.
The work is highly mathematical, with an occasional graph included for illumination. An important fallout of the proof is the derivation of recurrences for efficiently calculating A(v): the first recurrence requires O(v1/2) operations, and the second requires << v1/4 log log v. We are left with a tantalizing hint that still more efficiency is possible, but the details “appear to be complicated.”
After proving the main result, the authors examine the local distribution properties of the sequence of GSDSs, and establish a recurrence for the number of patterns of zeroes and ones of a given length that appear as subsequences of the characteristic sequence.
Readers interested in following more closely in the footsteps of the authors may download from either of their Web sites the Pascal programs they used to compute various results.
