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 offer Alice a co-authorship. Alice declines thinking that
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.
The 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.

Range Avoidance

Let \(f\) be a function mapping binary strings of length \(m\) to strings of length \(n\) with \(n>m\). Since there are more strings of length \(n\) than \(m\), \(f\) is not onto. Can you find a string not in the range? This is known as the range avoidance problems, or AVOID for short 

Let's do an example. Consider \(f\) that outputs an undirected graph on \(n\) nodes and takes as input:

• \(n\)
• A set \(S\) of \(k\) vertices \(v_1,\ldots,v_k\)
• For each \(i\) and \(j\), \(i<j\), where at least one of \(i\) and \(j\) are not in \(S\), whether or not there is an edge between \(i\) and \(j\).
• A bit \(b\)

If \(b=1\) output the graph \(G\) which consists of the given edges plus a clique on \(S\). If \(b=0\) the same but an independent set on \(S\).

For an appropriate choice of \(k\), about \(2 \log n\), the output of \(f\) is longer than the input. Any graph not in the range is a Ramsey graph, i.e., no clique or independent set of size \(k\).

You can use AVOID to capture other probabilistic method constructions, high time-bounded Kolmogorov strings, Boolean functions with high circuit complexity, two-source extractors, rigid matrices, error-correcting codes and more.

AVOID started as the problem 1-Empty in a paper by Robert Kleinberg, Oliver Korten, Daniel Mitropolsky and Christos Papadimitriou as an example of a total function problem higher up the polynomial-time hierarchy as verifying that a string not in the range is a co-NP question. Korten made the connection to probabilistic constructions. Hanlin Ren, Rahul Santhanam and Zhikun Wang popularized the problem and gave AVOID its current name. I learned about AVOID talking about the problem with Rahul and his students during my time at Oxford.

You can solve AVOID randomly using an NP oracle, at least half the strings are not in the range, and you can check that a string is not in the range in co-NP. Whether you can solve AVOID deterministically with an NP oracle remains open. Korten showed that that problem is equivalent to circuit lower bounds for E^NP. 

Surendra Ghentiyala, Zeyong Li and Noah Stephens-Davidowitz show that any decision problem that reduces to AVOID sits in AM ∩ co-AM which strongly suggests AVOID is not NP-hard.

See Korten's BEATCS survey for much more on the AVOID problem.

Scott Aaronson wins Trevisan Award? Prize? Medal? Statue?

 1) Congratulations to Scott Aaronson for winning the first Trevisan Award.

The Trevisan Award is in memory of Luca Trevisan and recognizes expository work in Theoretical Computer Science. It is given out by the ACM. The ACM announcement of Scott's award is here. Scott blogged about winning it here.

2) When preparing this blog post, I googled Trevisan Award. The first hit I got was this. That site says the award was for significant research. Hmmm. My first thought was Scott has, in fact, done significant research. Perhaps I misunderstood the award. I shared these thoughts with Lance who pointed out I was at the wrong website:

Scott won the Trevisan AWARD.

There is also a Trevisan PRIZE. This was the first hit I got when I googled Trevisan Award. 

There is not yet a Trevisan MEDAL. Give it time.

 
4) I then realized I did not actually know the difference between an award, a prize, and a medal.

a) What are all the ways to honor someone in academia?

b) How do they differ?

5) I asked our future AI overlords:

In academia there are PRIZES, AWARDS, MEDALS. Other ways to honor people in other fields are Ribbons and Trophies. Are there other ways to honor people? How do they differ?

Chatty gave me 10 pages of interesting material that appeared correct, which is about the best one can hope for. See here. In case you are thinking tl;dr, here is a short version focused on academia, with some of my own thought mixed in.  

a) Awards: General Recognition of excellence. May or may not involve competition (that's a tautology). I aspire to win the Montgomery Burns Award for Outstanding Achievement in the Field of Excellence.

b) Prizes: Usually competitive. Often recognizes a specific breakthrough.

c) Medals: Prestige and ceremony. Often accompanied by an actual medal.

d) Fellowships: Recognizes a substantial body of work.

e) Named lectures: Prestige plus airfare.

f) Named professorships: Prestige plus discretionary funds.

g) Election to academies: Peer validation with nice stationary.

h) Honorary degrees. A way to get a celebrity speaker at a graduation.

i) Statues. The only academic one I know of is The Slide Rule Statue, see here. 

Academia has many ways to honor people. Apparently the hard part is keeping track of which noun goes with which person.

The real award was the friends we cited along the way.

 

Prediction Markets Redux

For those very long-time readers this blog extensively covered prediction markets from 2006 to 2008. In a prediction market, you have a future event, such as the winner of an election, and a market that pays off one dollar if that event happens and nothing if it doesn't. The price of this market corresponds to a predicted probability that the event will happen. 

I worked with David Pennock and Yiling Chen to create an interactive map that colored every state based on how likely it was to go Democratic or Republican for both the presidential, gubernatorial and Senate races.

This all ended when Intrade, the source of the data that we used, went out of business after its CEO died climbing Mount Everest and may have embezzled money from the company.

In 2016 prediction markets went out of favor after badly predicting against Brexit once and Trump twice. 

But what's old becomes new again. Prediction markets are back with a bang, with Kalshi and Polymarket providing real money markets open to U.S. citizens, something we didn't legally have, except for very low stakes, twenty years ago.

Prediction markets play two distinct roles:

1. As a betting system so people can put their "money where their mouth is" based on their beliefs.
2. As an information aggregation system, to use the wisdom of the crowds to predict future events.

Sometimes these roles conflict with each other. With real money comes real greed and we've seen some recent issues of insider trading, most notably a US soldier who used classified knowledge about the then upcoming raid in Venezuela to net $400K on Polymarket. 

Insider trading will likely lead to better predictions, but those who have bet on that market might feel cheated. In the short run, insider trading might be a good thing, but in the long run, if we scare away participants because they're afraid others who have more information will take advantage of them, then we have fewer people in the market making it harder to draw upon the wisdom of the crowds. 

Another challenge for prediction markets is determining how the market pays off. You need to come up with a very specific definition of what it means for the market to pay off, but strange circumstances can lead to unexpected results. Back in 2006 North Korea launched a test missile outside the country but the market for that event paid off zero because the U.S. Department of Defense never verified that the missile actually left North Korean airspace. 

The market I like to see is factoring the RSA numbers by a given date. Very easy to verify. Some people might buy such a security, expecting quantum computing to be factoring numbers soon. And then I can make some money by betting against it. 

Searches Are Weird! No they're not! Bad coding style?

In David Marcus's guest post on good coding style (see here)  he reviewed a book from 1986 called  "Professional Pascal."

I wondered if it was still in print and could be bought:

1) I went to Amazon and searched all products for Professional Pascal. I got this, which is not that book.

2) I then restricted to books, and I got the same, though later on the page I got a relevant book, here.

3) I then searched for Professional Pascal on Google, and got the Amazon site for the book here.

David thought this was weird. I did not. As I put it:

A computer does something which makes no sense. This is common, hence it's not weird.

Why did the search from outside of Amazon do better than the search inside of Amazon?

Speculation

1) Search is just a really hard problem.

2) The coders at Amazon did not use good coding style. They should read the book. If they can find it. 

When do we know someone has died

As the blog of record in computational complexity, we like to bring attention to those in the community who have left us. When we learn of someone in our field who has died, Bill and I will talk to each other and decide whether we should do a social media post or a full blog post, and who should write it, Bill, me, or someone else. In fact, if I call Bill, he'll often answer the phone with "who died?"

We also remember those who passed away during the year in our end-of-year post.

One challenge is how we actually know when somebody has died. Consider Michael Rabin. His death was announced on Wikipedia based on the following announcement in Haaretz, an Israeli newspaper.

Haaretz Obit (Translated by Google)

That's a pretty simple obituary for a very famous computer scientist. Rabin is a common name in Israel, and there easily could have been another professor named Michael Rabin somewhere in the country. Every mention of Michael Rabin's death that I saw was just citing the Wikipedia article, nothing from Tal Rabin or some other source that cited the family.

By the time Bill put up the first Rabin post on April 22, we figured that had our Michael Rabin not died, someone would have come forward about it. 

Tony Hoare is a different story, where our blog was one of the first to break the news. I heard from two separate people that they had heard from the family that he had passed away. It helped that I was in Oxford at the time, where Hoare spent much of his career.

And too often a theoretical computer scientist passes away but the news never reaches us and we don't remember them. It's always sad when someone passes, but it is a good opportunity to remember how they helped shape our field. But we need your help to know when someone has passed away. So if you know someone in our community has passed away, please let us know, and how you know, so that we can know we know.