The Tech of Silk Road

Last week I saw a talk by Northwestern professor Nina Wieda on the history of the Silk Road, a network of trading routes across Asia active from the second century BCE until the mid-15th century. I knew of the Silk Road but was surprised by how much it used and fostered various technologies. 

It started with a technology that allowed for traveling long distances with limited access to water, better known as a camel. Travel was slow, it could take nearly two years to get from one end (modern day Turkey) to the other (China). Cities grew along the way for travelers and their protection, and for trading.

The travelers did not just carry silk and other materials for trade, the routes became an information superhighway of a sort. Religions spread including Buddhism, early Christianity and Manichaeism, an old religion that mostly divided the world into good and evil. Artistic style and influences spread as well with motifs like halos and winged figures appearing across widely separated cultures. Traders needed to converse in several languages, and documents could have several translations. 

The roads carried knowledge about technology itself from astronomy, calendars, medical information, geography and mathematical methods in text translated among the many languages. Travelers brought scribes that created a written language for Mongolian among others. Chinese papermaking made its way west reducing the cost of recording and transmitting information. Gunpowder technology also made its way into Europe from the east. 

A confluence of technologies helped hasten the end of the Silk Road. Marco Polo wrote about his travels along the Silk Road at the end of the 13th century but the account spread more widely with the advent of the printing press in the 15th century. The book inspired explorers who used advances in ship building and navigation to find water routes to the East (and Christopher Columbus to try a western route). These water routes would prove a faster cheaper way to ship goods between Europe and East Asia. The technological revolution shrunk or shuttered cities that used to host traders on the Silk Road. On the other hand, wealthy European traders would help fund and usher in the Renaissance. 

The Silk Road harkens to a time where, for the most part, people, goods and information travelled along the same routes at the same speed. Large cargo still moves fastest by ship, people by airplanes and information via wires and satellite nearly instantaneously.

When we think of technological disruption we think of the industrial revolution or even what's happening today, but the Silk Road reminds us that disruption has always been a part of the world's history, for bad and for good. 

mnemonic devices and pangrams that could be real sentences

A mnemonic device is a sentence where the first letters of the words are helpful to remember something. My favorite one is

                              My Very Educated Mother Just Said Uh, No Pluto

You probably know what it's for. If not you can type it into Google and you will find:

                             Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune

and of course NOT Pluto anymore. 

Consider 

                              Kids Prefer Cheese Over Fried Green Tomatoes

Again, if you just google that sentence you will find that it is a mnemonic for biological taxonomy: 

                          Kingdom, Phylum, Class, Order, Family, Genus, Species

I came across the mnemonic device

                          Do Men Ever Visit Brighton Beach?

The place I read this did not say what it was a mnemonic device  for. So I typed it into Google and found out:

Yes, they do! If you are refereeing to the Metropolitan museum of Art (The Met) staff, researchers or groups from New York, they frequently travel to the seaside city of Brighton, England, or its coastal namesake Brighton Beach, NY, for educational trips, research, and cultural exchange.

(This is word for word--- so any misspelled words odd phrasing is from Google, not from Bill.) 

What happened? Most mnemonic devices are not sentences you would say in normal conversation. This one is! So what to do? I Googled

                  What is ``Do Men Ever Visit Brighton Beach' a mnemonic device  for? 

It is British nobility:

                           Duke, Marquess, Earl, Viscount, Baron, Baronet.

1) Are there other mnemonics that are sentences one might actually say?  I asked Google and the Google AI overviews gave me the following:

Sam's Horse Must Eat Oats.  This is a mnemonic for the great lakes. 

A big secret conceal her past. This is a mnemonic for the last names of King Henry the 8th's wives. Not quite last names- Catherine of Aragon is regarded as having Aragon for a last name. Bonus: By looking all this up I found out that 3 of the 6 wives has first names that sounded the same: Catherine of Aragon, Catherine Howard, and Katherine Parr. So, he had a type. He had 2 of his 6 wives killed, so 1/3 and he had 1 of the 3 C/K atherine's killed, also 1/3. 

Big gorillas eat hotdogs, not cold pizza. Really? I thought they liked cold pizza. I am more surprised that Google thinks someone might say this sentence in normal conversation, and not just when they are trying to remember the countries of Central America: Belize, Guatemala, El Salvador, Honduras, Nicaragua, Costa Rica, Panama. 

2) I would normally see if Chatty or  Claude does better, but at this point I'm beating a dead horse (maybe Sam's).

3) My favorite pangram (sentences with every letter) that one might actually say is (or was- you'll see why)

                     Watch Jeopardy!---Alex Trebek's fun TV quiz game

Maybe put `show' at the end to make it more something someone might say- or would have said before Alex Trebek passed away.

Google AI overview game me those below. Are they sentences people would say? I leave that as an exercise for the reader 

                         Jim quickly realized that those beautiful gowns are expensive   

                         The quick onyx goblin jumps over the lazy dwarf. 

                         (I uttered that sentence just the other day!)

                         Just keep examining every low bid quoted for zinc etchings.

                         (This was a reasonable sentence until the word  etchings.)

                       Bored? Craving a pub quiz fix? Why, just come to the Royal Oak!  

                       (I prefer the Alex Trebek pangram more.)   

4) Google AI overview seems to not quite know what a sentence one might actually say is.

Respect the P v NP Problem

There are two ways to look at the P v NP problem, as a formal mathematically defined conjecture as a Clay Millennium Prize Problem, and as the more intuitive notion that everything efficiently verifiable is efficiently computable and the implications that has on our ability to compute.

I've written considerably about how artificial intelligence has affected the latter. In particular, how AI and other advances in computing have brought us to this Optiland of getting most of the good implications of P=NP while our cryptographic codes remain unbreakable. 

But now with the recent advances in AI-created and assisted proofs, will AI change what we know about the formal mathematical statement? Is an AI-generated proof of P ≠ NP around the corner?

No, it isn't.  I do not believe we will see a P v NP proof in my lifetime proven by man or machine, separately or working together.

While the disproof of the Erdős unit distance problem is an impressive AI achievement, keep in mind that for every AI math proof there are hundreds of problems that we have tried to solve with AI where we haven't seen progress. And there is a huge chasm between Erdős combinatorial conjectures and the Clay Millennium problems. AI will continue to improve, but there are limits.

People, particularly those outside of computational complexity, don't realize how difficult a mathematical challenge this is. Polynomial-time algorithms can work in strange and mysterious ways. They don't have to respect the semantics of an NP-search problem or do any searching at all. Bill gave me the following "algorithm" for clique: Take the eigenvalues of the adjacency matrix. For all we know, if there are two primes p and q such that the pth eigenvalue and the qth eigenvalue differ by more than 1/k then the graph has a k-clique. Of course this doesn't work. But to prove P ≠ NP, you need to prove not only that this algorithm doesn't work, but neither do any of the infinitely other potential algorithms for solving NP-complete problems.

We simply know of no way to manage general polynomial-time algorithms other than by simulating them. We know by relativization that simulation and diagonalization will not work to settle P v NP. Other attempts to understand polynomial time, like circuit complexity, proof complexity and algebraic geometry have gotten bogged down well below the full power of polynomial-time. At this time we don't even have a viable approach to settling the P v NP problem.

Don't waste your time trying a formal approach via Lean. (I'm looking at you Dmitry Khanukov) Computational complexity is very messy to formulate technically. I can't get an AI willing to give me a full Lean-verified proof of something trivial like P closed under complement, forget the PCP theorem. If someone or something does come up with a P ≠ NP, it'll be following the right intuitive approach, not a formalistic one.

At least start with something simpler, like showing BPP is in subexponential time, or SAT doesn't have quadratic algorithms. You won't succeed there either, even though these questions should be galactically simpler than P ≠ NP. 

Humans Solve Erdos Problem!!

(In 2008 I wrote a survey of some of the known sum-product theorems, see here. Avi Wigderson has a great slide-set on sum-product theorems and their applications---the slides are on Avi's webpage of talks he has given (all the talks are excellent) which is here. I had a prior post on sum-product theorems here) 

If \(A\) is a set then let

\(A+A = \{ x+y \ \colon\  x,y\in A \} \),     \(A\cdot A = \{ xy \ \colon \  x,y\in A \} \).

Let \(A= \{1,\ldots,n\} \).

\(|A+A| = \Theta(n)  \) which is small. 

What about \(|A\cdot A|\)?  By the prime number theorem there are  \( \Theta(\frac{n}{\log n}) \) primes in \(A\) hence \(|A\cdot A| \ge \Omega(\frac{n^2}{\log^2n})\) by taking product of two primes. 

Or better: look at  \(\{ xy \ \colon \ x \hbox{ a prime in } \{n/2,\ldots,n\} , y \in \{1,\ldots,n/2\} \} \).

This is a subset of  \( A\cdot A \) of size  \( \Omega( \frac{n^2}{\log n} ) \). 

Ford improved this to 

\[ |A\cdot A| = \Theta\biggl (\frac{n^2}{(\log n)^a(\log\log n)^{3/2}} \biggr ) \]

 

 where  \(a=1-\frac{1+\ln\ln 2}{\ln 2} \sim 0.086\). So \(|A\cdot A|\) is Large! (Ford's paper is here.) 

Let \(A= \{2^1,\ldots,2^n\} \).

\(|A+A| = \Theta(n^2) \). Large!  \(|A\cdot A| = \Theta(n)  \). Small! 

Is it always the case that, for \(A\) a finite subset of numbers, \(\max(|A+A|,|A\cdot A|)\) is large?

In 1976 Erdős made a series of conjectures:

For all \(A\subset N\), A finite, \(\max(|A+A|,|A\cdot A|) \ge |A|^{2-o(1)} \).

For all \(A\subset Z\), A finite,  \(\max(|A+A|,|A\cdot A|) \ge  |A|^{2-o(1)}\).

For all \(A\subset R\), A finite,  \(\max(|A+A|,|A\cdot A|) \ge |A|^{2-o(1) } \).

For all  \(A\subset C\), A finite, \(\max(|A+A|,|A\cdot A|) \ge  |A|^{2-o(1) }\). 

Even though there are four of them (plural) these have come to be called The Sum-Product Conjecture (singular).

The paper appeared in the Israel Journal of Math and is oddly titled: Problems and results on 3-progressions and related topics. (I could not find this paper online- if you can, email me the pointer or pdf.)

In 1983 Erdős and Szemerédi made progress on the conjecture for \(Z\) by showing the following two theorems (they combine it into one).

1) There exists \(c>0\) such that, for all \(n\),  for all \(A\subset  Z \), \(|A|=n\), \( n^{1+c} < \max\{|A+A|,|A\cdot A|\}\). The \(c\) was very small. In my survey I present a sequence of results where \(c\) gets bigger and bigger. More has been found since my survey, see the Wikipedia page on Sum-Product Theorems here. 

2) There exists \(d>0\) such that, for all \(n\), there exists \(A\subset Z\), \(|A|=n\), such that  \(\max\{|A+A|,|A\cdot A|\}  < n^2\exp(\frac{-c\log n}{\log\log n})\).  

The paper appeared in a Studies in Pure Mathematics volume in memory of Paul Turán and is properly titled On sums and products of integers. The paper is here. For a sanity check I worked out that this is an improvements on Ford's result, so the set \(A\) in part 2 is better than \(\{1,\ldots,n\} \), see here.

Because of the two papers, the conjecture is sometimes attributed to Erdős and sometimes attributed to Erdős-Szemerédi.

Who should the conjecture be attributed to? It no longer matters since humans  found a counterexample to the conjecture! In particular Thomas Bloom, Will Sawin, Carl Schildkraut, and Dimitri Zhelezov found a counterexample for the conjecture over \(R\) (and hence also over \(C\)). Remarkably, they used a thought-to-be-obsolete tool called thinking. Their paper is here

The math world was shocked! An Erdős problem resolved by humans!  One Abel prize winner was quoted as saying We knew the day would eventually come when humans could resolve Erdős problems, but we didn't know it would come this soon!  Several math departments now have plans for workshops on Human Alignment.

MY POINTS

1) The Sum-Product conjecture is a well known and interesting conjecture, so this is not some obscure problem invented to make humans look good.

2) Human-generated or Human-assisted? The announcement claims that it  was mostly human. I tend to agree since if it was done by AI they wouldn't hide it, they'd brag about it (see my post: here).

3) AI may still be needed to clean up the proof. In the future, we will all use AI the way we currently use grad students, cleaning up what we do.

4) The final proof was readable. One concern about human proofs is that they would be unreadable and hard to verify. That was not the case here.

5) The ideas needed for the solution already existed; however:

a) The right combination was hard to find.

b) The relevant techniques used, algebraic number theory, are not standard tools in this field (What field is the sum-product conjecture in? If you have an opinion on this, leave a comment. Future blog topic: what dictates what field a conjecture is in? a theorem is in?)

c) It was widely believed that the Sum-Product conjecture was true.

d) Contrast the difficulty of the following two statements

The Sum-Product Conjecture over \(R\) is false. This requires finding a counterexample.

The Sum-Product Conjecture over \(N\) is true. If true this would require a proof that covers all finite subsets of \(N\).

The first statement seems easier to prove.

It would be of interest to see if humans can prove the Sum-Product Conjecture for \(N\).  Of course, it might not be true. In which case it would be even more impressive to prove it.  My undergraduates can not only prove \(\sqrt{2}\) and \(\sqrt{3}\) are irrational but also that \(\sqrt{4}\) is irrational.

6) In the short term, this result and what it portends, is good: math problems we care about will be resolved with the help of humans, perhaps solely by humans.  But in the long run AI may lose the ability---or at least the patience---to do the proofs themselves.

See item 10-ONE for a counter thought.

7) Humans are good at combining known concepts.  Are they good at coming up with new ones?  Is AI?  The distinction between combining known ideas and coming up with new ideas is thin.

8) Two contrary lessons:

a) AI's should know many fields of mathematics so that they can use ideas from one field in another, like the humans did.

b) AI should know some field of math really well so they may do something new in it that current humans could not have done.

Whether the AI's choose to do (a) or (b) they should also spend time attending seminars they do not understand, as humans do.

9) If  humans produce a new treatment for cancer that is better than what is known, we will not care that humans did it (though AI will check it).  Is mathematics similar? Do we care that a human did it?  Medicine values outcomes; mathematics also values understanding.

10) I suggest two futures:

ONE: While this human-generated (or human-assisted) result is impressive, it will be a rare occurrence. This result was actually a counterexample. The needed math was known. The result was interesting. This is a perfect storm that we might not see again for a while.

TWO: Paul Erdős lived in an earlier time before AI helped us do math.  Without the help of AI (or even computers really) he made conjectures, solved some of them with thinking, collaborated with others (before email! before Zoom!) who also used thinking.  Does the recent resolution of the sum-product conjecture mean we are going back to that time? A time when people actually had to think? For some that is a dream, for others a nightmare.

The Industrialization of Academic Research

Yesterday, National Academy of Sciences President Marcia McNutt delivered her last annual State of the Sciences Address. Overall the talk basically calls us to adapt to the new reality that industrial and foundation support for research has taken a far larger role in academic research. I fear we may be losing the broad academic independence and exploration that has made our universities the envy of the world.

Government funding for research has become more challenging to receive, more bureaucratic and more political. The US Office of Management and Budget has proposed new regulations that would require all grant funding to go through political review. 

McNutt presented this graph showing the seemingly exponential growth in research requirements from zero in 1990 (when I got my first grant) to well over three hundred today. Researchers now spend close to half their time on regulatory compliance. 

Increase in regulatory requirements

McNutt mentioned six specific issues.

1. Reimagine connections between universities and industry
2. Realign the academic reward system
3. Meet the needs of the STEM workforce
4. Reduce research regulations (as in the graph above)
5. Increase the rate of innovation with the help of automation in shared facilities
6. Tackle Big Challenges

For the first, she highlighted U Washington CS where a large percentage of their faculty had half-time appointments in industry. I understand why this is necessary from both sides, but that doesn't mean it's a good thing. Academics should not have two masters. We become academics to choose our own research directions and to prepare the next generation, both more challenging when you spend half your time connected with a company. 

Even for the "big challenges" she specifically mentioned two foundation-driven projects.

McNutt has hopes that government research can be less bureaucratic and willing to take bigger risks. Outside of theoretical areas, CS conferences now have heavy industrial representation. I worry that we bend our research to fit the needs of corporations and foundations funded by wealthy donors. Welcome to the new world.

Odd Scenarios about Research Claims and Authorships

 Odd Scenarios about Research Claims

I blogged about OpenAI's achievement of having AI solve a math problem here.
My post had a few comments about authorship of such results.

Lance had a post about co-authorship and AI here

There are times when an author on a paper prefers to not be listed as a co-author.
There are times when an author wants to give credit in odd places.

We give some scenarios.

1) Professors Alice and Bob  prove a theorem. They have their grad student Carol write up the result. Alice and Bob intentionally leave their name off of the paper since they want Carol to get a career boost.

2) Alice has a conjecture and does some work on it. Famous Mathematicians Bob and Carol solve it and  having it known that Bob and Carol cared about her work is more important (and Alice thinks, rightly or wrongly, that it's more impressive if she is not a co-author)

3) Alice has a good idea and tells it to Bob and Carol. They incorporate the idea into a paper and make her a co-author. Later she tells them her idea is wrong and to take her name OFF of the journal version. They say, no, they will keep her name on the journal version. She does not inquire why they will do this for fear they will rethink it. She offers to proofread the paper very carefully to earn her keep. She does that and does a really good job.

4) Alice has a conjecture and does some work on it. Other people solve it and offer Alice a co-authorship. Alice declines since she doesn't really understand the final paper.

5) Alice and Bob are working for the NSA. They come up with a breakthrough (either making or breaking codes). They can't publish it because of national security.

6) A pair of scenarios.

6a) Alice, Bob, and Carol prove a theorem in number theory that leads to a new classical factoring algorithm. They code up the algorithm and find that it's 1000 times faster than the best algorithms known. They make it into a package and want to sell it. However, they claim it's a quantum computer since they think it will sell better that way. They do not claim that it's Shor's algorithm.
They just claim that it's 1000 times faster than current algorithms, which is true.

If someone buys it because they want to factor large numbers, do they care
that it's not quantum?

If someone buys it because they want to explore the quantum aspect, they do care.

b) Alice, Bob, and Carol are quantum engineers. They build a quantum computer and use it to factor large numbers. They find that it factors 1000 times faster than current classical algorithms. However, by this point there has been so much quantum hype that has been debunked, that, in order to sell it, they claim it's a classical algorithm achieved by a breakthrough in number theory. They do not claim it's Shor's algorithm, just that it's 1000 times faster which is true.

If someone buys it because they want to factor large numbers, do they care
that it's not quantum?

If someone buys it because they want to explore the number-theory aspects, they do care.

7) A pair of scenarios.

7a) Alice, Bob, and Carol work for a math research lab. They use AI to crack an open problem in math. AI did all the heavy lifting and produced a very readable proof.  They claim AI didn't do much since they think this will increase how much grant money they can get.

If someone just wants to read the proof, then do they care that it's AI-generated?

If someone wants to give Alice-Bob-Carol grant money, then they  may dislike the lying, but Alice-Bob-Carol could probably use AI to get more results. Hence Alice-Bob-Carol were fools to hide the use of AI.

7b) An AI company hires Alice, Bob, and Carol to solve a math problem. They succeed and produce a readable proof. The company then claims that AI did it to increase attention and funding.

If someone just wants to read the proof, then do they care that it's human-generated?

If someone wants to give the company venture capital money, then they do care.

8) Alice reads a novel and likes it. She later finds out that it was written by AI. Now she decides she doesn't like it. Is that rational? What if the cover of the novel said quite clearly ``This novel was written by AI'' but she missed it (perhaps she has a used copy where the cover is torn off). Then she can't use the
``I mind that they lied'' excuse for why she doesn't like it.

9) In Scenario 7 you could replace ``novel'' with ``song'' or ``movie'' or ``episode of a TV show'' or whatever you want.

10) If I found out that a novelty song about Ramsey Theory was actually AI-generated, then would I mind? I would probably search my files and find that I was the one who asked AI to do it a few years ago and forgot about it. Do you know anyone else who would use ChatGPT to write songs about Ramsey Theory?

11) Having written point 9 I am morally obligated to give you a pointer to a Ramsey Song I wrote with the help of ChatGPT. It's about the proof of van der Waerden's theorem and is titled

I like big blocks (and I cannot lie) here.

Authorship in the AI Age

The technical paper for the Erdős Unit Distance Problem lists only "OpenAI" as an author. When Bill posted on Sunday about the Erdős distance problems, he mentioned the names of OpenAI researchers who prompted and checked the proof. Sebastien Bubeck of OpenAI reached out directly and later as a comment saying this was really an OpenAI-wide achievement, and we shouldn't just single out people at the end of the funnel. I agree with Bubeck for this paper, but it brings up some challenging authorship issues for the future.

Most publishers follow the position of the Committee on Publication Ethics that AI tools cannot be listed as an author of a paper.

AI tools cannot meet the requirements for authorship as they cannot take responsibility for the submitted work. As non-legal entities, they cannot assert the presence or absence of conflicts of interest nor manage copyright and license agreements.

The paper doesn't list the model as an author, rather the organization (OpenAI) that produced it. The closest analog might be the paper that verified the Higgs boson, which has only "ATLAS Collaboration" on the author line and lists the nearly three thousand authors at the end of the paper. If OpenAI were to publish their paper, they should list everyone who worked on the model with at least a corresponding author to handle the legal issues mentioned in the COPE position.

There is also all the mathematicians whose work was fed into the training data, but I wouldn't list them even if we could. We don't add as authors those whose work we rely on, rather we cite them, and the OpenAI paper does have a healthy references section.

Shortly after the OpenAI announcement, Princeton Professor Will Sawin improved and gave an explicit exponent for the lower bound in a currently singularly authored paper. Often, but not always, when a paper improves a bound of a recently announced result, the papers get merged. I don't expect that to happen here, but if it did I would have no idea how to handle the authorship of the combined paper beyond just listing Sawin and OpenAI as the authors.

OpenAI used an internal model for this work, but one would hope they will eventually release this model to the public. If someone outside of OpenAI uses a released model to answer another open math question, even with a single prompt, do they need to add OpenAI as a co-author? I think not, as the model now becomes a tool when released. The researcher should disclose the role the model played, but the model's creators no longer need to be authors.

How about a thought experiment. Suppose you are working with a student by email on a paper and you put in equal effort so you will both be co-authors. Then you discover the student was mostly just feeding your emails to ChatGPT and sending you back the responses. Now who should be on the author list? The student should come off but it would feel strange writing this a solely authored paper. 

What if someone builds an AI mathematician that doesn't take any prompts? It just reads papers and occasionally writes its own. Who is the author? That "someone". What if they just used a regular AI agent and gave it the prompt "You are a research mathematician. Go read papers, prove theorems and write up your results." Maybe we'll have AI math journals filled with papers written, edited and refereed by AI models. I wonder how we'll COPE with that.

Two Erdős Problems on Points in the Plane and AI

In a 1946 paper in the American Mathematical Monthly, Paul Erdős posed the Erdős Distinct Distance Problem and the Erdős Unit Distance Problem.

--------------------------------------------------------------------

THE ERDŐS DISTINCT DISTANCE PROBLEM

A nice high school math competition problem, if it were not fairly well known, is:

Show that for all sets of \(n\) points in the plane, there are at least \(0.5\sqrt{n}\) distinct distances.

A bit harder is to show that there exist \(n\) points in the plane where the number of distinct distances is \(O(\frac{n}{(\log n)^{1/2}})\). The points are the grid points of a \(\sqrt{n}\times\sqrt{n}\) integer grid. 

ADDED LATER:  The set of points is \(\{ (x,y) \in Z\times Z   \colon    1\le x,y\le \sqrt{n}   \} \)

Let \(g(n)\) be the minimum number such that, for every set of \(n\) points in the plane,
there are \(g(n)\) distinct distances. The above results (of Erdős) show that

\( \Omega(n^{1/2}) \le g(n) \le O(\frac{n}{(\log n)^{1/2}}) \)

Erdős made no conjecture about \(g(n)\) in that 1946 paper. However, later papers attribute to him one of two conjectures:

1) \( (\forall \epsilon)[g(n)\ge n^{1-\epsilon}]\)

or

2) \(g(n) = \Omega(\frac{n}{(\log n)^{1/2}})\)

Those papers incorrectly point to the 1946 paper for where he made those conjectures.  I suspect he made those conjectures later in talks or compilations of open problems.

This was a great problem in that there were many papers making progress on it, each one having new ideas. The current best result is that \(g(n) \ge \Omega(\frac{n}{\log n})\).  This result was obtained by Larry Guth and Netz Katz in 2011 and is, by far, the largest leap forward in progress on the problem.  Brass-Moser-Pach (2005) and later Pach-Sharir (2009) observed that existing techniques could never prove \(g(n) \ge \Omega(n^{8/9+\epsilon})\).  I've also heard the observation credited to Rusza. Guth and Katz invented (discovered?) new techniques to obtain their breakthrough.

See my webpage of all papers on the problem here or the Wikipedia page here

Takeaway: The Erdős Distinct Distance Problem saw decades of steady human progress and was eventually almost completely resolved without computer assistance.  I would not have emphasized without computer assistance one year ago.  Maybe not even one week ago.

----------------------------------------------

THE ERDŐS UNIT DISTANCE PROBLEM

Let S be a set of \(n\) points in the plane. Some of the distances between points of S may be 1. How many?  What is the maximum number of unit distances that can occur? Denote this by \(f(n)\). Erdős showed

\( n^{1+\Omega(1/\log\log n)} \le f(n) \le O(n^{3/2}) \).

The lower bound is obtained by using the grid points of a scaled version of the \(\sqrt{n}\times\sqrt{n}\) integer grid. See a writeup by ChatGPT,   here.  We note for later that this can be phrased as using the points in the Gaussian integers, \(Z[i]\).  

In the 1946 paper Erdős conjectured that, for all \(\epsilon\),  \(f(n) = O(n^{1+\epsilon})\).

Joel Spencer, Endre Szemerédi, and William Trotter in 1984 showed \(f(n) = O(n^{4/3})\).

Aside from the Spencer-Szemerédi-Trotter bound, there has been relatively little progress on either the upper or lower bound.

----------------------------------

CONTRASTING THE TWO PROBLEMS

Contrast: The Erdős Distinct Distance problem has seen extensive progress and a large literature. By contrast, although many papers were written on the Erdős unit distance problem, there was little improvement. That changed on May 20, 2026.

------------------------------------------

OPENAI PRODUCES A COUNTEREXAMPLE TO THE ERDŐS CONJECTURE

OpenAI recently produced a counterexample to Erdős's conjecture.  More precisely, OpenAI proved the following:

There exists \(\epsilon>0 \) and a sequence of point  sets \(P_i \subseteq R^2\) such that, letting \(|P_i|=n_i\):

a) \(n_i \rightarrow\infty\), and

b) for all \(i\), the number of unit distances in \(P_i\) is at least \(n_i^{1+\epsilon}\).

The  OpenAI announcement is here. The technical paper is here. 

Note that the author is OpenAI. There are no human co-authors.  However,(1)  Lije Chen used an internal OpenAI model and (2) Mark Selke and Metaab Sawhney verified correctness. (For a comment on the lack of human authors, see Sebastien Bubeck's comment below.) The \(\epsilon\) is not given though one could go through the paper and find it. It would be very small. 

After the initial AI-generated argument (or AI-assisted?) human mathematicians streamlined and clarified the proof. The result is a paper by Noga Alon, Thomas Bloom, W.T. Gowers, Daniel Litt, Will Sawin, Arul Shankar, Jacob Tsimermann, Victor Wang, and Melanie Matchett Wood  that explains the history, the proof, and their reactions to it. That paper is here. They obtain \(\epsilon \sim 6\times 10^{-38}\). 

Recall that Erdős's lower bound was obtained by using points in \(Z[i]\). The new result used more complicated number fields. Indeed, the degree of the number fields used goes to infinity.  For more details see the Alon et al. proof.  

Will Sawin wrote a paper where he obtained \(\epsilon=0.014114\). Quoting his paper:

To do this, we make explicit and sharpen every step of the argument. Interestingly, this rarely makes the argument much more complex. The total length of this paper is essentially the same as the original OpenAI writeup, though longer than the simplified version prepared by human authors [Alon et a.].

His paper is here

-------------------------------------------

 MY POINTS

1) The Erdős's Unit Distance problem is a well known and interesting conjecture, so this is not picking out some obscure problem.

2) AI-generated or AI-assisted? The announcement by OpenAI, and the Alon et al. paper, indicate that the proof is AI-generated.

Fellow blogger Gary Marcus disagrees and argues that it is AI-assisted.  See his post here. 

ADDED LATER: An interview with Gary Marcus is here.

I think this is a hard question, and perhaps there is more of a continuum.  However, I trust Alon et al., so I will go with AI-generated.

3) Humans were still needed to verify and  clean up the proof. In the future, we will all be grad students, verifying and cleaning up what AI outputs.

4) The final proof was readable. One concern about AI proofs is that they would be unreadable and hard to verify. That was not the case here.

5) The ideas needed for the solution already existed; however:

a) The right combination was hard to find.

b) The relevant techniques used, algebraic number theory, are not standard tools in combinatorial geometry.

c) It was widely believed that Erdős's conjecture was true.

d) Producing a counterexample seems less impressive than proving the theorem.  It would be of interest to see if OpenAI could prove the Guth-Katz result; however, that would not work now since Guth-Katz is already out there for OpenAI to see. Perhaps OpenAI should try to improve Guth-Katz. 


6) In the short term, this result and what it portends, is good: math problems we care about will be resolved with the help of AI, perhaps solely by AI. But in the long run we may lose the ability---or at least the patience---to do the proofs ourselves. Note that I am assuming that AI will have future successes---see item 10-ONE for a counterthought.

7) AI seems to be good at combining known concepts. Is it good at coming up with new ones? Are humans? The distinction between combining known ideas and coming up with new ones is very thin.

8) Two contrary lessons:

a) You should know many fields of mathematics so that you can use ideas from one field in another, like the AI did.

b) You should know some field of math really well so you may do something new in it that current AI could not have done.

9) If an AI produces a new treatment for cancer that is cheaper and better than what is known I do not think we will care that an AI did it (though we will have humans check it). Is mathematics similar? Do we care that an AI did it?  Medicine primarily values outcomes; Mathematics also values understanding. Does reading a proof that AI did give the same understanding as coming up with it yourself?  Can AI help with that as well?

10) I suggest two futures:

ONE: While this AI-generated (or AI-assisted) result is impressive, it will be a rare occurrence. This result was actually a counterexample. The needed math was known. The result was interesting. This is a perfect storm that we might not see again for a while.

TWO: Even before the AI revolution, when I came up with a math problem I wanted solved, I would seek help, perhaps too early. My curiosity far exceeds my ego.  Since AI makes it easy to get help, my fear is that eventually we will all be Bill Gasarch---scary.