# Can every number be written as a small sum of sums of squares?

In a practice for a programming competition, one problem asked us to find the smallest number of pyramids which can be built using exactly $n$ blocks, where pyramids have either $k\times k, (k-1)\times (k-1),\ldots,1\times 1$ blocks on each level or $2k\times 2k, 2(k-1)\times 2(k-1),\ldots,2\times 2$ blocks on each level. Note that the first type of pyramid has $$\sum\limits_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}$$ blocks while the second has $$\sum\limits_{i=1}^k (2i)^2 = \frac23 k(k+1)(2k+1).$$ Equivalently, we want to write $n$ as a sum of numbers of this form, using as few as possible. The official solution to this problem had an exponential runtime in the minimal number of pyramids, but noted that this was not problematic as the minimal number of pyramids is always at most $6$. I see no obvious reason for this, or even an obvious reason why the minimal number of pyramids should be bounded. Can someone provide a proof?

-
This and this might be of interest. – dtldarek Feb 25 '13 at 10:54
There is no "obvious reason" as Waring-like results are usually difficult. In addition to "Waring's problem" you might also want to search for the Hardy-Littlewood "circle method" if you want to learn how to prove these kinds of results. – Noah Snyder Apr 11 '13 at 1:12
@NoahSnyder I've heard of the circle method, but was hoping for a more elementary argument here. If answering this requires a several-year digression in my mathematical study into analytic number theory, I probably won't bother. – Alex Becker Apr 11 '13 at 4:47
This looks heavily related to Pollock's 1850-conjecture (mathworld.wolfram.com/PollocksConjecture.html): every positive integer can be written as the sum of at most 5 tetrahedral numbers; every positive integer can be written as the sum of at most 7 octahedral numbers. – Jack D'Aurizio Dec 26 '13 at 14:18
With the greedy approach (every time I subtract from $n$ the biggest number of the form $\frac{1}{4}\binom{2a}{3}$ or $\binom{2b}{3}$ that is $\leq n$) the first numbers that require six terms are $43,69,84,104,119,133,153,168,178,\ldots$. The first numbers that require seven terms are $183,263,328,354,\ldots$. The first numbers that require eight terms are $1002,1423,1723,1968,2292,\ldots$. The first numbers that require nine terms are $11418, 12482, 14687, 16182, 17208,\ldots$. – Jack D'Aurizio Dec 26 '13 at 14:52

This concerns showing the minimal number of pyramaids is bounded. I don't know the effective value of the bound, as it depends on a theorem of Hua which implies that every sufficiently large integer is the sum of nine or ten cubes of primes.

Let $s(n)=n(n+1)(2n+1)$ which is $6$ times the number of blocks of a type $1$ pyramid. Then we have the identity $$s(n+1)+22s(n)+s(n-1)=6(2n+1)^3. \tag{1}$$ Now supposing we have a given large number $M,$ we write $M=6k+r$ with $0 \le r <6$. The result of Hua then says we can write $k$ as a sum of nine or ten cubes of primes. If $2$ is one of the primes we can get the $6*2^3$ using a bounded number of pyramids. The other primes are odd cubes $p^3$ and each $6p^3$ can each be obtained by a bounded number of pyramaids using $(1)$. The remainder $r$ only needs finitely many more.

EDIT: I noticed that $(1)$ may be divided by $6$ and then gives the same relation between the numbers $t(n)=n(n+1)(2n+1)/6$ which are the counts for the type 1 pyramids. Then there is no need for writing $M=6k+r$ and one can apply Hua's result directly. Since the coefficient $22=5\cdot 4 +2$ each $t(n+1)+22t(n)+t(n-1)$ really introduces only nine pyramids, which then brings the count down a bit more. But this is not much better since a bound of say $81$ for sufficiently large $M$ is so much larger than the likely bound of $6$.

The site which I found discussing the Hua result is a paper by Koichi Kawada. The Hua result is from 1938. Kawada paper

UPDATE

There is a result of R. D. James which implies one can get all sufficiently large integers as a sum of nine of the type 1 pyramidal numbers, above called $t(n)$. This is a much better bound than that implied by the sum of cubes consequences worked out above, though it still only applies for sufficiently large integers. If anyone wants to check the correspondence, it is that $t(x)$ matches the polynomial $P(x)$ of James' paper provided $a=2,\ b=c=1.$

Jame's paper is on JSTOR, with the following link. One gets a preview page, which contains enough to see the result, and it seems one can read on line for free if one gets a JSTOR account. The link:

http://www.jstor.org/discover/10.2307/2370934?uid=3739832&uid=2129&uid=2&uid=70&uid=4&uid=3739256&sid=21104342222973

-
Very interesting. After more than a year, I'd given up on this being solved. This bound is very large (even for sufficiently large numbers), but seems to me this method is highly suboptimal, since not the only property of primes we use is that they are odd or $2$. – Alex Becker Apr 6 '14 at 19:21
@AlexBecker Yes it is a way large bound. I don't even know how large since I didn't go through the Hua result to see what bound on the number is needed to guarantee 9 or 10 cubes, and then there's the largeness coming from using (1) [the 22s(n) can be gotten from 11 type 2 pyramids I think...] – coffeemath Apr 6 '14 at 19:41
@AlexBecker It may be you aren't looking at this any more, however I found a paper which brings the total down to nine of the type 1 pyramids, for sufficdiently large integers. This is now included in my answer below in the "UPDATE" section at the end. – coffeemath Jun 20 '14 at 19:50

Not quite an answer, but a start: It's easy to show there are infinitely many integers n which require at least four pyramids: The number of blocks in a pyramid is always 0 (modulo 5), 1 (modulo 5) or 4 (modulo 5). Actually, one in five numbers is 1 (modulo 5), one in five is 4 (modulo 5) and 3 in 5 are 0 (modulo 5). To get a sum that is 2 (modulo 5), we need to add 0 + 1 + 1 (modulo 5) or 4 + 4 + 4 (modulo 5).

k(k+1)(2k+1)/6 is about k^3/3, so there are about (3n)^(1/3) of those less than n. k(k+1)(2k+1)*2/3 is about 4k^3/3, so about (3n/4)^(1/3) of those are less than n. The total number of values < n is about 2.351 n^(1/3). About 0.47 n^(1/3) are 1 (modulo 5), about 0.47 n^(1/3) are 4 (modulo 5), about 1.41 n^(1/3) are 0 modulo 5.

There are about (0.47 * 0.47 * 1.41 / 2)n sums of the form 0 + 1 + 1 (modulo 5), and about (0.47 * 0.47 * 0.47 / 6)n sums of the form 4 + 4 + 4 (modulo 5). This adds up to about 0.173n sums equal to 2 (modulo 5); many of these are > n, so the number of sums less than n are fewer than that. But there are 0.2 numbers <= n that are 2 modulo 5, so many of these cannot be the sums of three pyramids.

I checked that up to n = 1 billion, about 69% of all numbers are the sum of at most three pyramids. The same is true for n = 100 million, so that percentage of numbers needing four pyramids seems quite constant. All numbers up to 1 billion are the sum of four pyramids with the exceptions n = 108, n = 247 and n = 1007 which need 5.

Some more statistics: Of the numbers from 1 to 1 billion,

69.58% are the sum of three pyramids
89.48% are the sum of three pyramids and the number 1
97.47% are the sum of three pyramids and the number 1 or 4
98.78% are the sum of three pyramids and the number 1, 4 or 5
99.36% are the sum of three pyramids and the number 1, 4, 5 or 20
99.77% are the sum of three pyramids and the number 1, 4, 5, 20 or 14
All but the three mentioned above are the sum of three pyramids, and a pyramid up to 650.


This makes it quite unlikely that any numbers other than 108, 247 and 1007 would require more than four pyramids, but doesn't help one bit proving it.

-