# What is the roadblock in the discovery of new taxicab numbers?

The $$n$$-th taxicab number, denoted $$\text{Ta}(n)$$, is the smallest integer that can be expressed as a sum of two positive integer cubes in $$n$$ different distinct ways.

$$\text{Ta}(1) = 2 = 1^3 + 1^3$$ is trivial, and the infamous $$\text{Ta}(2) = 1729$$ was known as early as the 17th century, much before the well-known Hardy-Ramanujan story.

$$\text{Ta}(3)$$ was found by John Leech in 1957. After no further discoveries for three decades, the quest for more taxicab numbers seems to have gained traction around the same time computer-assisted proofs became more widespread. Rosenstiel, Dardis and Rosenstiel found $$\text{Ta}(4)$$ in 1989; Dardis found $$\text{Ta}(5)$$ in 1994 and this was later confirmed by Wilson in 1999; and finally Calude et al. announced $$\text{Ta}(6)$$ in 2003 which was later verified by Hollerbach in 2008.

The best information we have regarding other taxicab numbers are the upper bounds for $$\text{Ta}(7)$$ through $$\text{Ta}(12)$$ provided by Boyer in 2006-2008. There seems to have been a relatively rapid succession in the discovery of taxicab numbers from early 1990s until mid-2000s. One would imagine, the quality of the computational tools we have access to nowadays would only have accelerated the search -- but the quest seems to be silent since Boyer's upper bounds. Why is this?

• One reason might be the following: by a theorem of Silverman, if there exists a binary cubic form $F$ with integer coefficients and an infinite sequence $\{h_n\}$ such that the number of primitive solutions to the Thue equation $F(x,y) = h_n$ increases as a function of $n$, then there exist elliptic curves over $\mathbb{Q}$ of arbitrarily large rank. This was widely believed until relatively recently, when heuristics due to a large number of authors indicate that rank of elliptic curves over $\mathbb{Q}$ might in fact be bounded. Aug 20, 2020 at 17:14
• @StanleyYaoXiao Interesting comment, I find it very surprising that the ranks might be bounded. What are these heuristics more precisely, do you have some reference? Aug 20, 2020 at 17:31
• @AntoineLabelle One of the papers with rank bound heuristics is A heuristic for boundedness of ranks of elliptic curves Jennifer Park, Bjorn Poonen, John Voight, Melanie Matchett Wood arxiv.org/abs/1602.01431 If they're correct, then that old theorem of mine that Stanley mentioned would imply that there is an absolute bound for the number of primitive solutions to $x^3+y^3=m$, where primitive means $\gcd(x,y)=1$. Note that the taxicab numbers do not impose this gcd restriction. Aug 20, 2020 at 17:39
• @JoeSilverman do you mean there would be an absolute upper bound on the number of primitive integral solutions $(x,y)$ to $x^3 + y^3 = m$ only for cubefree $m$, or is there a way to bootstrap that to an absolute upper bound allowing general $m$? Your papers on the topic focus on cubefree $m$. Aug 22, 2020 at 14:59
• @KConrad If you allow iimprimitive solutions, i.e., with $\gcd(x,y)>1$, then you can get as many solutions as you want by clearing denominators from a bunch of rational solutions. The original idea of doing this is due to Chowla. I quantified it to some extent in the paper: Integer points on curves of genus 1, J. London Math. Soc. 28 (1983), 1-7. OTOH, if we restrict to primitive solutions, then maybe we can get a uniform bound for the number of solutions in terms of the rank, even if $m$ is not cube-free. The key is to exploit the canonical height lower bound. Aug 22, 2020 at 15:17

There are a few issues here.

(1) It is relatively easy to show that Ta($$n$$) exists, for example by using a point of infinite order on an elliptic curve $$x^3+y^3=mz^3$$ to show that there is at least one number with $$n$$ distinct representations. However, the number tends to be divisible by a large cube, or alternatively, the $$(x,y)$$ pairs tend to have large $$\gcd(x,y)$$.

(2) So let's define $$\operatorname{Ta}^*(n)$$ to be the smallest that can be expressed as a sum of two relatively prime positive integer cubes in $$n$$ different distinct ways. Then $$\operatorname{Ta}^*(2)=1729$$,$$\operatorname{Ta}^*(3)=15170835645$$ (Vojta), $$\operatorname{Ta}^*(4)=1801049058342701083$$ (Gascoigne, Moore, independently), and there is some reason to believe that $$\operatorname{Ta}^*(5)$$ doesn't exist. (Or in any case, at some point $$\operatorname{Ta}^*(n)$$ doesn't exist.)

(3) To get back to your question, the size of $$\operatorname{Ta}(n)$$ probably (maybe?) grows exponentially with $$n$$. And increased computer power, even with Moore's law, has a hard time keeping up with a problem whose computational complexity grows exponentially. So for example, if increasing from $$n$$ to $$n+1$$ makes the taxicab search space grow by a factor of 100, and if it took 2 years of computer time to find $$T(n)$$, it's going to require a much faster computer to compute $$T(n+1)$$.

It looks as if $$\operatorname{Ta}(n)$$ may be growing superexponentially in $$n$$, although of course there isn't a lot of data, and the values for $$7\le n\le 12$$ are upper bounds. But the last line of this table is suggestive. $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline \dfrac{\log\operatorname{Ta}(n)}{n} &3.73 & 6.10 & 7.39 & 7.69 & 8.59 & 9.34 & 9.99 & 10.52 & 11.25 & 12.03 & 13.02 \\ \hline \dfrac{\log\operatorname{Ta}(n)}{n\ln(n)} & 5.38 & 5.55 & 5.33 & 4.78 & 4.79 & 4.80 & 4.80 & 4.79 & 4.89 & 5.02 & 5.24 \\ \hline \end{array}$$

• A much faster computer, or a much better algorithm. Aug 21, 2020 at 0:24
• @GerryMyerson Sure, I didn't think I needed to say that explicitly, but you're right, the other way to make a breakthrough is to find an algortihm that's more efficient, as happened with factorization speedup by replacing the quadratic sieve with the number field sieve. Aug 21, 2020 at 0:27