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

Question

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?

Answer 1

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}