Efficient Algorithms for Decomposing Integers as Sums of Few Tetrahedral Numbers

Pollock conjectures that every natural number can be expressed as a sum of at most five tetrahedral numbers. It remains unknown whether this conjecture holds, and Watson proved that sums of at most eight tetrahedral numbers suffice to express all natural numbers. We devise two algorithms to decompose integers as sums of few tetrahedral numbers. Our first algorithm can decompose any given integer n into a sum of at most eight tetrahedral numbers in \(O(\log ^3 n/\log \log n)\) time with probability \(1-1/n^{\mathrm {\mathrm {\Omega }}(1)}\) , assuming the extended Riemann hypothesis. Our second algorithm can deterministically decompose all integers in \([1, \ell ]\) into sums of the fewest possible tetrahedral numbers in \(O(\ell )\) time using \(O(\ell ^{2/3})\) space, assuming a conjecture over the integers in \([1, \ell ]\) and the Pollock’s conjecture on tetrahedral numbers over the integers in \([1, \ell ]\) . While the conjectures for all integers are unproven, their validity for all integers in \([1, \ell ]\) can be verified in \(O(\ell )\) time. As a result of our second algorithm, we can show that the Pollock’s conjecture holds for all natural numbers up to \(4.71 \times 10^{20}\) . This significantly improves upon the previous known bound of \(3.77 \times 10^{15}\) .