DRMacIver's Notebook

Can you throw money at the Collatz Conjecture?

Can you throw money at the Collatz Conjecture?

Published
2021-07-30

Warning: Inside baseball, very much a set of notes rather than a coherent point.

For context, the Collatz conjecture is the following:

For any given natural number \(n\), if \(n\) is even, move to \(\frac{n}{2}\), otherwise move to \(3n + 1\). The Collatz conjecture is that no matter which \(n\) we start with, we will eventually reach \(1\).

There is, as far as I know, no particular reason to care about the Collatz conjecture except that it’s interesting and that we don’t know how to solve it.

I claimed on Twitter that you could probably solve the Collatz conjecture in a decade, given $1 billion of funding. Ben Gunby disagrees.

I don’t think we disagreed a lot. My estimate was something like “this would probably work”, and I think his is something like “this probably wouldn’t work”. As far as I can tell neither of us thinks the other’s position is ridiculous, we’ve just got moderately different views on the problem. That being said, having written all of this up, I’ve concluded that he’s right and I’m wrong, because I had significantly underestimated how hard the Collatz conjecture is.

I think the following is a fair summary of his argument that this is likely to be very hard:

  1. We are likely quite far away from techniques that would allow us to tackle the Collatz conjecture.
  2. If this is the case, there is likely a long dependency chain in which we have to develop tools to develop tools to develop tools etc.
  3. If this is the case, this likely passes through many fields unrelated to the Collatz conjecture.
  4. $1 billion is a lot but it’s not enough to literally bend the whole of mathematical research to your whims.

To look at this from another perspective, one can think of this in terms of two questions:

  1. How many direct mathematician-years of work do we need to solve the Collatz conjecture? i.e. if you add up all the mathematician-years of work spent on the proof and things it depends on, what do you get?
  2. How many mathematician-years of work do we realistically need to do in order to actually achieve that? This would be the same if you could just linearly proceed from A to B, but if you depend on unrelated fields you need to take into account work done in equally plausible unrelated fields that you couldn’t have known in advance.
  3. How much of that work is intrinsically sequential? e.g. if we decided that it will take 1000 mathematician-years, can we do that in 10 years with 100 mathematicians or are you going to have to do a full 1000 years of work with one mathematician building on the results of another, etc?

(“mathematician-years” of course depends on how good the mathematicians in question are. I guess I’m assuming reasonably top end mathematicians)

I think Ben and my intuitions on these differ as follows:

  1. His estimate of the number of mathematician-years required is much higher than mine initially was.
  2. I think you probably can cut out a lot of the unrelated work with a bit of work on focusing people.
  3. I believe this is more parallelisable than he does.

On further reading up on the difficulty of the literature I think that he is right and I am wrong about the first one, and I’ve significantly underestimated how hard the Collatz conjecture is. In particular “The Ultimate Challenge” by Lagarias has a good survey that made me realise I’d underestimated the problem. Terence Tao made good progress on the problem in 2019 and this good progress established a substantially weaker result than the full conjecture.

For comparison, I think reasonable estimates for how many mathematician years went into solving Fermat’s Last Theorem are somewhere in the region of 1000 to 10,000 mathmatician years, taking 1900 as the starting point (Most of the work on it that got real traction happened in the 20th century, I think). If on average 100 mathematicians were working on it full time at any given point of that century, that gets us to 10,000. If it’s only 10, that’s 1,000.

Is that realistic? I don’t know. I could also make a convincing argument that it was less than that (e.g. a lot of the last stretch was Wiles working on his own for 7 years, followed by Wiles and Taylor finishing it off…). But lets say 10,000 mathematicians years is about how much FLT took. It’s a nice round number.

Is the Collatz conjecture about as hard as FLT starting from 1900? I don’t know. Based on my reading since Ben and my initial disagremeent… yeah, probably. Possibly even harder. We’ve got a number of partial results and angles of attack on it, but certainly nothing resembling a convincing story. It might be that it’s actually amenable to some easy attack, but I don’t think we’ve got any reason to expect that to be the case, and people who have studied it more than me seem to think it’s probably too hard for us right now.

Suppose now that we could just turn money into mathematician-years. A high end mathematician salary seems to be about $100k. Because we want the best, and also need support staff and infrastructure, lets double that and say that one mathematician year costs us $200k. $1 billion now gets us 5,000 mathematician years.

So, based on these (admittedly somewhat pessimistic) estimates, even if we could make a perfect beeline for the Collatz conjecture, if it’s about as hard starting from now as Fermat’s Last Theorem was starting from 1900, we should not expect to be able to solve it with a mere billion dollars.

This is before we even get to the harder questions to quantify. What if exploring all the dead ends means we actually need 100,000 mathematician years?

Also, what happens with the dependencies problem? Can we, realistically, do even those 10,000 mathematician-years in 10 years even if we had infinite amounts of money to throw at it?

I don’t have a good handle on this but think the answer is a resounding “Maybe”. If we again use Fermat’s Last Theorem as a benchmark it doesn’t seem unreasonable to me to think that we could do this - that’s only one order of magnitude reduction, and I think if we had the relevant parties in a room together and were able to more aggressively speed up the collaboration, offer them support, etc. I don’t think this is ridiculous. Wiles worked on FLT for 7 years on his own, and I wouldn’t be surprised if he could have done that in half with a collaborator to discuss things with.

This is all speculative though, I genuinely don’t know, and I don’t have any way to know. The polymath project gives me some hope that hard mathematical problems are parallelisable, but as far as I know it’s never been tried on anything nearly this hard.

So, in conclusion, Ben is probably right. You probably can’t solve this is in a decade with $1 billion.

I do think you could probably make meaningful progress on the Collatz conjecture, up to and including solving it, with a mere $1 billion, but I think if I were to do that it would look more like trying to build resources and community around it in the broader mathematical community.

For example, for this sort of price tag one could fund:

An alternative approach would be to just hire Terence Tao and Jeffrey Lagarias, and any dozen or so other mathematicians they care to name, and let them go wild on the problem. I doubt it would work, but it might produce something interesting.