[Aardwolf]

> An example of a galactic algorithm is the fastest known way to multiply two numbers,[4] which is based on a 1729-dimensional Fourier transform.[5]

That number looked familiar, and yep it's the taxicab number. Coincidence? Neither of the two references seems to mention it

[scapp]

It's somewhat a coincidence. In the paper, the dimension has to be larger than this constant K which is shown to be no larger than 1728. This is a fairly crude estimate that comes from multiplying a bunch of small numbers together, so the fact that it ends up being 12³ is not unimaginable. Then taking the dimension to be one larger than this estimate on K, we get 1729 = 12³ + 1³ (= 9³ + 10³).

However, 1728 isn't the minimum possible value for K. With more precise estimates, sketched in the paper, we can bring it down to 8 + ε. So assuming that this finer estimate works, using a 9 dimensional Fourier transform would also make the algorithm be O(n log(n)).