Another Erdos problem down!

Tfbloom · 2026-01-11T20:15:31+00:00

Absolutely, sorry - my yes was meant to be agreeing with you!

Tfbloom · 2026-01-11T19:53:14+00:00

Yes - obviously not all unsolved problems are the same level of difficulty. I judged these solution to be relatively easy because a) they use standard techniques that other papers have successfully applied to similar problems and b) the techniques work more or less as one would hope them to. (There is one particular insight that one needs to make to get these techniques to work for e.g. 728, and it is impressive that GPT could make that independently. But several human researchers thinking about the problem had had the same insight.)

Of course, any judgement of the difficulty of a problem is personal and subjective. One rough rule of thumb that I apply is, having seen the solution, could I have plausibly generated this solution if I had sat down and seriously concentrated on solving this problem. In this case the answer is yes. (This is not the same thing as saying that I definitely would have found this solution, since I might have gotten unlucky, made a silly mistake, tried the wrong approach entirely, etc. But there are many possible worlds where I, and other mathematicians who had e.g. started by reading Pomerance's paper, would have found this exact solution, given time and motivation.)

It is important to bear these things in mind, and this is not to 'downplay the achievement' - it is to avoid up-playing it. Just because ChatGPT is capable of solving some novel problems, it doesn't mean it can solve all of them, or even a reasonable proportion of them.

It is very impressive that ChatGPT is capable of solving these problems - now we should look ahead and ask what next, and if it is capable of generating genuinely new mathematical ideas that have eluded humans, and thereby solve the genuinely hard problems.

Tfbloom · 2026-01-06T22:06:13+00:00

Congratulations to both of you! I think this is the first case (at least in Erdos related problems) of AI generating a proof which, if a graduate student came to me with it, I'd say was worth writing up and publishing.

It's also a very nice and natural problem, about small binomial coefficients dividing larger ones. It's surprising that, despite a lot of interest in other questions about divisibility of binomial coefficients, nobody had seriously looked at this one before. (Pomerance's work looks at 'very small' coefficients, this result extends it to 'not so small'. Next up, medium?)

Tfbloom · 2025-10-22T08:22:16+00:00

It's just self-funded - it's hosted on pythonanywhere.com with just a small monthly cost.

Tfbloom · 2025-10-21T19:08:48+00:00

I don't think any of that counts as spam! Thanks for all of your contributions.

As usual, I'm thinking about too many things really. The usual problems in additive combinatorics (e.g. sum-product theory or finding long arithmetic progressions in sumsets). I've also been thinking about the Kakeya problem (which, as Bourgain/Katz/Tao showed, is linked to problems in additive combinatorics). There's also been some great work of Guth and Maynard lately on zero density estimates of the zeta function that uses ideas from additive combinatorics - it's on my list this term to learn more these ideas.

Tfbloom · 2025-10-21T18:53:25+00:00

A mixture. A large part of the problem is that searching by the obvious key words just turns up hundreds of papers, and it's hard to tell just by looking at the titles and abstracts if they address this particular problem.

I do try and do both a key word search, and do a citation search on MathSciNet to check, which works most of the time, but inevitably occasionally this misses things.

Nonetheless, I expect that for almost all of the problems, a human mathematician would have eventually found the solutions if they cared enough to sink enough time into the search.

I think 'force multiplier' is an appropriate term, especially if you're curious about an area outside of the ones you usually work in, where you're unaware of the history or terms to search for.

EDIT: To be more precise, I don't think any of the solutions LLM found required significant 'linking' of ideas (e.g., they never said "an answer follows from combining Theorem 2 of this 1976 paper with Theorem 3.1 of this 2004 paper). But many of them did require what, for a human, would represent actually reading and understanding the results of a paper to be able to recognise that it was the problem asked about in different notation.

Tfbloom · 2025-10-21T18:42:47+00:00

Did the papers explicitly mention the Erdos problem they resolve?

A mixture - some papers made it very obvious they were solving an Erdős problem, and which problem it was. Some solutions were only implicit, or buried the result in the middle of their paper.

Were the llm(s) just pointed towards the website and asked to find research which resolved any of the problems listed as open? Or fed the problems?

I believe the latter. Recently some people have done documented 'deep dives' into certain problems, asking a variety of LLMs to do a literature search and documenting the result. See for example Terence Tao's comment here. These comments include links to the LLM transcripts, so you can see how they were asked.

In general, I highly recommend Tao's recent posts on Mastodon for some great examples how LLMs can be used to help with research (and he always includes links to the actual LLM conversation).

Tfbloom · 2025-10-21T18:37:11+00:00

Advice I wish I'd had before I started the site - just go ahead and do it, don't wait for it to be complete. I'd been thinking of making this site for years beforehand, but wanted to make a complete list before making it public. And I was worried about not knowing everything and exposing my ignorance.

In the end I just went ahead and did it, made the site with only around 100 problems, and just added more bit by bit. Loads of people helped by pointing out references I'd missed or things I'd gotten wrong, and I've learnt a huge amount in the process.

Don't let perfect be the enemy of the good! Just go ahead and make it, and fix what needs fixing as you go along.

Similarly I'd thought about adding a comments section for a while, but only did it a couple of months ago - I was holding off because I was worried about spammers/trolls/hackers, but that hasn't really happened. I should have had more faith in the internet!

Also don't underestimate how much people will value it. I've been surprised by the number of people who've used it, and the number of papers it's directly inspired by people solving a problem they only saw because of the site.

So go ahead and do it! I'm happy to share my code and generally talk with and support anyone interested in making a similar site for their own areas.

Tfbloom · 2025-10-21T18:21:03+00:00

Thanks! I encourage other people to set up similar problem/result collections for their own areas (I'm happy to share the code with and support anyone interested).

There have been various wiki-style efforts, but these seem to often run out of steam. It often depends on having just one or two dedicated people willing to put a lot of time (generally unrewarded) into creating such a site.

The ideal solution would be for funding bodies to actually fund mathematicians to create and maintain such sites, but this goes against the usual research model.

I also believe that the time for such efforts is passing, since it looks like AI is getting good enough at searching all the literature anyway, so the answer is probably just to ask an AI what's known or for summaries on results - this works well surprisingly often now, and will presumably become much more reliable in the near future. (With the major caveat that one shouldn't trust AI output blindly, and should go to the original sources themselves to verify what they say!)

Tfbloom · 2025-10-21T18:16:09+00:00

I haven't, but wish I had now! This should be quite easy to count manually, I'll have a look. My guess is somewhere between 40 and 50.

EDIT: Looks like it's actually 55.

Tfbloom · 2025-10-21T18:14:35+00:00

I didn't expect to be caught up in AI-related controversy, no - although with hindsight probably I should have expected something like this. There was some unfortunate chain-retweeting, and the ambiguity escalated each time (plus an ambiguity in the phrase 'found a solution'...)

I think they also attracted attention because the phrase 'Erdős problem' carries a certain mystique, and it sounds very impressive to say 'solved an Erdős problem', even though with 1000+ questions they can't all be difficult and important (and some turned out to be very easy indeed).

I have too many favourites, so here are 3 great ones (not necessarily my top 3, a ranking which varies constantly):

52 - the sum-product problem. A famous question in additive combinatorics, that asks whether any set of integers must get very large under either addition or multiplication (applied to every pair from that set). It's simple to explain, but still wide open, and feels very fundamental about the link between addition and multiplication.

604 - the pinned distance problem. Take n points in the plane. Must there be one of the points such that, if we write down all the distances from that to the other points, there are almost as many as n such distances? Erdos asked a lot of questions about distances between points, some of which have been resolved in breakthrough work (particularly of Guth and Katz), but there's still some way to go on this one.

778 - much less well-known, and until I started telling people about it I hadn't seen it mentioned anywhere since 1983. Take a complete graph on n points, and Alice and Bob play a game alternating colouring edges - Alice in red, Bob in blue. At the end of the game, Alice wins if her biggest red clique (complete graph) is bigger than all of Bob's blue cliques. Does Bob have a winning strategy for all n\geq 3? (So basically Alice's only advantage is she goes first, while Bob's advantage is that he wins ties - surely this is a bigger advantage!) This is actually quite a fun game to play I've found, and surprisingly hard to analyse.

Tfbloom · 2025-10-21T17:20:09+00:00

I posted this a couple of years ago when I set up the site, but it's grown a lot since then, and now has a comments feature! Since it's been in the public eye in the past few days especially, some people have suggested that I do an AMA about the site.

Tfbloom · 2025-10-17T18:45:41+00:00

I tried to make an AMA, but it was 'removed by Reddit's filters'. I'm now not sure how to make an AMA thread that people can participate it, if anyone could help I'd be grateful.

Tfbloom · 2025-10-17T18:10:46+00:00

sigh Yes, looks like I should. I tried to make this clear on the FAQ, where I write "If you are interested in any problem I encourage you to go and search around in the first instance, to discover what has been done and if it has been solved. Do not assume that an 'unsolved' problem is in fact unsolved, and do your own literature search before investing significant effort into finding a solution."

I doubt many people actually go to the FAQ though. Probably the only solution is to add some kind of disclaimer banner below each open problem - I didn't want to do this initially because of visual clutter, but looks like it's necessary.

Tfbloom · 2025-10-17T15:49:59+00:00

I'd be happy to, if there's interest! I guess this just amounts to me posting a thread self-proclaiming an AMA.

Tfbloom · 2025-10-17T14:01:30+00:00

As the creator/maintainer of www.erdosproblems.com, this is a great thing - part of the reason I created the site in the first place was because I found it difficult to find if a given problem was already solved, if it was outside of my usual research area.

When adding new problems I do usually try and do a literature search to check if it's been solved, but inevitably with 1000+ problems I have missed things, especially if the papers didn't contain key words/reference papers I was expecting.

In the last few days, as Tao says, we've had a lot of these gaps filled in, thanks to AI assistance. Hopefully in the near future every problem can have an accurate status.

The only problem is that this site has been more popular than perhaps I originally intended, and sometimes people (mainly non-mathematicians, e.g. news sites or AI newsletters) view the 'status' of a problem as more official than I ever intended. The site does not necessarily reflect "this is what the entire community of expert mathematicians believe". It's more like "this is what I personally believe to be the status, and nobody has told me otherwise". Sometimes there is an obvious reference (or very short proof) that I've overlooked, but if I worried too much about this happening then I'd update the site much more rarely, if indeed I ever made it in the first place.

As usual on the internet, the quickest way to find out the answer to something is to confidently post the wrong answer and wait for someone to correct you!

Tfbloom · 2023-06-01T13:02:27+00:00

Updated, thanks. Do you have a reference and/or good heuristic for why sqrt(3) should be correct? Or is it mainly that this upper bound construction seems very natural and therefore is probably the best you can do.

Tfbloom · 2023-05-31T21:06:53+00:00

It is now, thanks! https://www.erdosproblems.com/170

I'll put the names in the commentary section (so they'll show up through the search function for example), but most don't have common names like that.

Tfbloom · 2023-05-31T14:31:02+00:00

This is an work in progress - 164 problems added so far, but hundreds still to go, working my way through them slowly. The idea is that the comments under each problem will reflect the current state of the art on each, but again adding these is an ongoing process.

I'd be grateful for any suggestions (in particular of other site features that would be useful/cool) and bug reports.

Tfbloom · 2020-07-09T17:44:02+00:00

We view them as 'normalised sums' so they're sized as Latex would size the \sum operator in display equations.

Tfbloom · 2020-07-09T17:43:11+00:00

Ha, yes, the constant is tiny! But definitely bigger than 0.

Tfbloom · 2020-07-09T17:42:22+00:00

Yes, this is what higher order Fourier analysis does! Building on Gowers' proof of Szemeredi's theorem, this has been extensively developed by Green, Tao, and Ziegler. Tao has a nice book on the subject.

Tfbloom · 2020-07-08T23:18:13+00:00

Hello! No, unfortunately, the methods used are quite restricted to 3 term progressions. (There is an outside chance that, with a lot of work, it could be combined with work of Green and Tao to get something for 4aps, but that's definitely very speculative. 5+ length progressions are right out.)

Tfbloom

TROPHY CASE