Sum-of-Three-Cubes Problem Solved for ‘Stubborn’ Number 33
quantamagazine.org
quantamagazine.org
which is a followup from the 2015 episode https://www.youtube.com/watch?v=wymmCdLdPvM when the 33 problem was unsolved.
The announcement elicited this Mathoverflow discussion about "mic drop" moments in mathematics: https://mathoverflow.net/questions/325105/what-are-some-note...
Andrew Booker's paper about 33 [1].
It's quite funny how Numberphile inspired these searches.
[0] https://arxiv.org/abs/1604.07746
[1] https://people.maths.bris.ac.uk/~maarb/papers/cubesv1.pdf
(8,866,128,975,287,528)³ +
(–8,778,405,442,862,239)³ +
(–2,736,111,468,807,040)³ = 33
696950821015779435648178972565490929714876221952 -
676467453392982277424361019810585360331722557919 -
20483367622797158223817952754905569383153664000 = 33Interesting that Lewis Carroll also makes references to 42.
[1] https://en.wikipedia.org/wiki/42_(number)#The_Hitchhiker's_G...
(from his Foreword to Vorlesungen über Zahlentheorie (Lectures on Number Theory) (1927).)
He might be very disappointed that number theory underpins modern cryptography.
Curious how we are able to prove that and with certainty say this is a rule?
The sums of three of these, mod 9, are 0, 1, 2, 3, -1, -2, -3 or 0, 1, 2, 3, 6, 7, 8, so the sum of 3 cubes can not be 4 or 5 mod 9.
In irb or python interpreter copy and paste
8866128975287528**3+(-8778405442862239)**3+(-2736111468807040)**3
Unknown. From the article:
'A major result would be to prove the conjecture that k = x³ + y³ + z³ has infinitely many solutions for every whole number k, except those k that have a remainder of 4 or 5 after being divided by 9.'
8866128975287528n**3n+(-8778405442862239n)**3n+(-2736111468807040n)**3n
"A major result would be to prove the conjecture that k = x³ + y³ + z³ has infinitely many solutions for every whole number k, except those k that have a remainder of 4 or 5 after being divided by 9."
If I command-space on OSX and put this into the search bar (which accepts math), I get exactly 30,000,000,000,000.
I know this is just a coincidence, but it's a rather poetic one.
https://en.wikipedia.org/wiki/Phrases_from_The_Hitchhiker%27...
You would certainly hope so, since every value a computer works with is integral.
* given a computer program that prints integers, there is a Diophantine equation whose integer solutions are precisely the set of integers printed by that program,
* given any computer program, one can represent it by a Diophantine problem: one can write down a polynomial equation such that it has integer solutions if and only if the program halts.
For example, because we can write down a computer program to print the prime numbers, there exists a certain (explicitly known) polynomial whose integer values are precisely the prime numbers. And as we can write down a program which halts only if (say) the Riemann hypothesis is true, we can write down a Diophantine equation which has integer solutions only if the Riemann hypothesis is true.
(What you're saying about being able to represent every value a computer can represent would be true for say linear or quadratic equations too, but those are not rich enough to simulate all of computation.)
Essentially, you can build a computer out of diophantine equations.
You can read more at https://en.wikipedia.org/w/index.php?title=Hilbert%27s_tenth... and good expositions by Poonen at http://www-math.mit.edu/~poonen/papers/sample_beamer.pdf (talk slides) or http://www.ams.org/notices/200803/tx080300344p.pdf (article).
True, but this is a strange comparison to make. Calling an equation "linear" or "quadratic" is a statement about the kinds of computation involved in the equation. Calling an equation "Diophantine" is a statement about the kinds of solutions to that equation that you, the author/reader, consider acceptable. These are not comparable concepts.
I understood the claim "Diophantine equations are sufficient to represent a computer" to contrast with e.g. "Real-valued equations are sufficient to represent a computer". It's true that real numbers have more power (vaguely defined) than integers do, so I can see why this comparison might be drawn in the first place. But since computers can't use real numbers, I still don't find it surprising that integers are sufficient.
> A computer does more than store values: it also performs computation.
Yes, but this is not a way in which computers differ from equations. And there are no restrictions on the types of computation you can invoke in an equation, whereas computers are e.g. restricted to computing computable numbers.
> And “they’re rich enough to simulate computers” refers to the celebrated (and surely surprising!) theorem...
The proof of the incompleteness theorem involves showing that integers, by themselves, are rich enough to represent any arbitrary mathematical statement. Why would it be surprising that adding structure on top of the integers lets you keep the expressive power you already had? "x = k", for some constant k that encodes your chosen meaning, is a perfectly valid Diophantine equation, and we already know that we can represent arbitrary mathematical statements using only equations of that form. The additional forms allowed by extending ourselves to arbitrary equations won't take anything away from that.
Similarly for quadratic equations — you still get sets that are easily parametrized. Something like this is what motivated Hilbert to ask the question in the first place. Nothing so far would have suggested that if you go up to higher-degree polynomials, you should eventually be able to obtain any computable (i.e. recursively enumerable) set as the set of integer solutions to some polynomial equation. Yet that's the case.
The contrast was never with real numbers, so mentioning real numbers is neither here nor there. (Though I understand how one can get that impression, if one thinks that what is being highlighted is “Diophantine solutions” in the sense of “integer solutions” as opposed to “real solutions” or whatever.) The surprising fact being highlighted by the number-theorist in the quote (and one of the highlights of 20th-century mathematics) is that the structure “the set of integer solutions to a polynomial equation” is rich enough to encode all possible computation — i.e. polynomials are not as “simple” as one may think. (Please take a look at those links if you haven't; it's really beautiful and super surprising that a program can be encoded as the set of integer roots of an integer polynomial.)
So...did he just brute force it?
EDIT: Should've read further down. Looks like, yes:
>But usually, solutions are “nontrivial.” In these cases, the trio of cubed integers — like (114,844,365)³ + (110,902,301)³ + (–142,254,840)³, which equals 26 — looks more like a lottery ticket than anything with predictable structure. For now, the only way for number theorists to discover such solutions is to play the mathematical “lottery” over and over, using the brute force of computer-assisted search to try different combinations of cubed integers, and hope for a “win.”
https://www.geeksforgeeks.org/find-triplets-array-whose-sum-...
I haven't looked at the algorithm, but a linear search probably can be GPGPU computed in parallel. A Vega64 is around $400 and runs 16384 threads on 4096 physical shaders at roughly 1.2GHz.
The main issue is if whatever data-structures used for this search will actually fit inside the microscopic amount of memory that is available to each shader.
They are not using GPUs and from the paper it looks like they haven't thought about it. I think a GPU cluster would be a speedup, but big number multiplication is relatively slow on GPUs, so maybe not as big speedup as with other algorithms.
Its probably cheaper and easier to just port your code to Amazon cloud or Google Cloud for a month, rather than to port your code to a GPU.
Honestly, the more and more I look into this, it seems like GPUs are the ideal computational platform for this problem. We're talking about a simple equation, with numbers that fit inside the 64-bit integer space (less than 10^19). GPUs can calculate that somewhat easily (The compiler probably turns 64-bit multiplies into 4x32-bit multiplies + adds, but that's still low in memory usage...)
I'm not sure if one GPU would be enough to compute everything. But we're talking about 512-cpu cores at 1-month of computing. A GPU probably can solve it within 6 months.
I'm talking about replicating the work done on "33" by the way, not on 42. If 10^19 is sufficient for a search space, then 64-bit ints can be used.
------------
It won't be an easy port btw. The three variables are written as x^2 - 2xy + y^2 == (33 - z^3) / d, where d = (x+y).
The Numberphile video said that "d" is brute-force searched, because there are very few values of "z" that would satisfy the above formula. So every shader probably can brute-force d on its own in a GPU.
Overall, seems pretty efficient to run this on a GPU. Very little memory, everything probably fits in GPU-register space.
But still, worth a try if you have one, and don't forget SHOW HN once you have luck ;)
Its a (nearly) linear brute-force search. Every thread is going to run "guess d", and then calculate "(33 - z^3) / d = x^2 -2xy + y^2".
All values must be integer, so (33 - z^3) / d must be an integer value. Which means the selected value "d" must be a factor of (33 - z^3). So "z" is going to be a small search space. I would expect that similar "d" values would have similar amounts of "z" values that satisfy this solution, so thread divergence doesn't seem to be a major issue.
That's about as uniform as it gets. Its a guess-and-check search, very much akin to cryptocoin mining. It seems like the GPU is the best architecture to the algorithm.
The biggest number will fit inside of 53 bits, 54 if you include the sign bit. Which means all of the values fit inside of 64-bits (including the sign bit). The cubes will fit within 192-bits.
If this truly were a "big number" problem, then brute-force wouldn't be a valid methodology!
That's why I call it big-number calculation: manual carry/overflow handling, larger-than-register size operands, tedious indexing/bug prone if coding from scratch, ... but of course you can still argue that it is not "big."
Or maybe now GPGPUs have big integer support? The last time I did actual GPU computing was CUDA 7 I guess, using cublas in daily basis so never ever been familiar with integer computation in GPU.
Its not a general big-integer implementation which can be arbitrarily sized. Since you know all results fit inside of 192 bits, and that all operands are less than 64-bits, you can easily code for this special case.
192-bit x 64-bit is way easier to debug and test than 192-bit x 192-bit. Its probably the bulk of your work, but I don't foresee any major complication here. Its just grade-school arithmetic.
struct cube{
long long val[3];
}
cube multiply(cube x, long long y){
cube toReturn;
toReturn.val[0] = x.val[0] * y;
toReturn.val[1] = x.val[1] * y + __umul64hi(x.val[0] * y);
toReturn.val[2] = x.val[2] * y + __umul64hi(x.val[1] * y);
return toReturn;
}
Without any if-statements, the GPU can calculate the above across different threads without any divergence. You can likely optimize this further with MAD instructions, but the above would be a good "first step" towards this problem.
As I said earlier: this wouldn't be an "easy" port, but it would be possible, and it would likely be very efficient. I'm not going to think through all the edge cases, but the bulk of the algorithm seems very easy to do efficiently on the GPU architecture to me.
And again, I'm not saying GPU-porting is easy. I'm just saying its possible, and likely is the most cost-effective use of hardware. Whether or not it is worth the programmer time is a separate question of course. But I don't see anything that's stopping a GPU from efficiently computing THIS problem, especially if its restricted to 192-bit as the biggest number in the whole algorithm (worst-case 64-bit cubed).
I've tried to port other algorithms to the GPU and it didn't work. But THIS sum-of-three cubes problem looks like an easier job than most algorithms to me.
Fair enough. Also thanks for the demonstration, it updates my understanding.
But still at some moment in the future, we may need a general big-number algorithms for calculation due to the inevitable expansion of search space. There is no guarantee that unsolved k's, says 100 < k < 200, can be found in min(|x|,|y|,|z|) <= 192 bit.
> But THIS sum-of-three cubes problem looks like an easier job than most algorithms to me.
Good luck and I'm looking forwards to any updates.
You can see it here: https://youtu.be/ASoz_NuIvP0?t=393
Rewind a couple of minutes if you want the explanation.
1 core year = 12 core months
23 core years = 276 core months
(x + y)(x^2 - xy + x^2) = 42 - z^3
d = x + y
x^2 - xy + x^2 = (42 - z^3)/d
I can't think of anything snappy, though. "Clever brute force" is the best I've got, and it's a mouthful. I tried looking for antonyms for "brute," the options aren't great. Well-bred? Polished? Humanitarian?
I think "refined force" is a solid option. Selective works well but might be too literal since "select" is a common algorithm verb.
"Judicious force" is my favorite and "prudent force" comes second.