11
$\begingroup$

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?

$\endgroup$
5
  • 6
    $\begingroup$ 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. $\endgroup$ Aug 20, 2020 at 17:14
  • $\begingroup$ @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? $\endgroup$ Aug 20, 2020 at 17:31
  • 3
    $\begingroup$ @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. $\endgroup$ Aug 20, 2020 at 17:39
  • $\begingroup$ @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$. $\endgroup$
    – KConrad
    Aug 22, 2020 at 14:59
  • $\begingroup$ @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. $\endgroup$ Aug 22, 2020 at 15:17

1 Answer 1

20
$\begingroup$

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}

$\endgroup$
2
  • 2
    $\begingroup$ A much faster computer, or a much better algorithm. $\endgroup$ Aug 21, 2020 at 0:24
  • 2
    $\begingroup$ @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. $\endgroup$ Aug 21, 2020 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.