Why an AI breakthrough on a simple number puzzle matters

For about 30 years, computer scientists used a simple number puzzle as a benchmark for what computers could do efficiently. They had a clever solution. They suspected that a whole category of better solutions was impossible.

An October 2026 research paper by Josh Alman and Virginia Vassilevska Williams gives a method that crosses that supposed limit. According to its authors, the central algorithm, the recipe of steps a computer follows, was discovered by Claude, an AI model from Anthropic.

The improvement is tiny. It won’t make your laptop noticeably faster. But it changes a long-standing answer to “what is possible?” And the result comes with mathematical arguments that others can inspect, rather than a model’s assurance that it found something clever.

You can understand why this is surprising by working through the puzzle yourself. All you need to start is addition.

The puzzle: can three numbers add up to zero?

Take this list:

4, -5, 6, 1, -8, 3, -2

Choose three entries. Do they add up to zero?

• 4 + 6 + (-8) = 2. No.
• 6 + (-8) + (-2) = -4. No.
• 4 + (-5) + 1 = 0. Yes.

That’s 3SUM (yes, this really is the name). Given a list of numbers, decide whether any three entries add up to zero. You can use each position in the list once; if the same value appears twice, those are two separate entries.

Finding one matching group settles the question. Finding every matching group is a different job, potentially requiring much more work. Here we’re asking whether an answer exists, and showing one when it does.

Seven numbers are manageable. A million numbers make the method you choose matter enormously.

The obvious method: try every group of three

Start with the first number. Pair it with the second, then try every remaining number as the third. Next, keep the first number but change the second and try again. Continue until you’ve tested every group, or found an answer.

If no group adds to zero, you have to check them all. With 1,000 numbers, there are about 166 million possible groups. With a million numbers, there are about 167 quadrillion.

Suppose, purely for illustration, a computer could check a billion groups per second. The smaller list would take a fraction of a second. The larger one would take roughly five years.

That’s why a simple puzzle becomes a serious computing problem. Each individual addition is easy. There are far too many groups to add up.

def three_sum_naive(nums):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    return nums[i], nums[j], nums[k]
    return None

What “n cubed” tells us

Computer scientists need a way to describe that explosion without assuming a particular computer. They look at how the work grows when the list gets bigger.

Let n mean the number of entries. The expression n³, pronounced “n cubed,” means n × n × n. Checking groups of three has roughly that pattern: each choice of a first number creates choices of a second and a third.

Double the size of the list, and each of those three sets of choices roughly doubles. The work grows by 2 × 2 × 2: eight times. Requiring different positions and ignoring the order of a group reduces the count, but doesn’t change this growth pattern as the list gets large.

This matters when buying a faster computer looks like the answer. A computer twice as fast would help, but the next doubling of the list would bring eight times the work. A better method can change that relationship.

A better method: put the numbers in order

Sort the list from smallest to largest:

-8, -5, -2, 1, 3, 4, 6

Now choose one number. We’ll use -5, which means the other two must add up to 5.

Put a finger on the smallest remaining number to its right, -2, and another on the largest, 6. In the diagram, these are labeled L and R for left and right; a is the number we’re keeping fixed, -5.

1. -5 + (-2) + 6 = -1. Too small. Move the left finger right, from -2 to 1, to increase the sum.
2. -5 + 1 + 6 = 2. Too big. Move the right finger left, from 6 to 4, to decrease the sum.
3. -5 + 1 + 4 = 0. Found one.

The clever part is knowing those moves can’t skip a valid answer for the fixed number.

In the first step, -2 was already paired with the largest available number, 6, and the total was still too small. Pairing -2 with anything smaller can’t help. We can rule out -2 entirely for this choice of -5.

In the second step, 6 was paired with the smallest number still under consideration, 1, and the total was too big. Any larger partner would make it worse. We can rule out 6.

Each unsuccessful step eliminates one remaining entry. The two fingers move inward until they find an answer or meet. If they meet, we try a different fixed number and repeat. To search the entire list, we start with the first fixed number and work through the possible choices; -5 was our worked example.

That’s the saving: ordering the numbers lets us discard whole sets of combinations without testing each one.

Why that turns five years into minutes

For each fixed number, the fingers can move at most about as many times as there are entries. There are at most that many choices of fixed number, too.

Using n again, that’s at most about n × n steps: n², or “n squared.” Doubling the list now means roughly four times the work, rather than eight. Sorting has a cost, but its growth is slower than n², so the repeated searches determine the growth of the whole method.

For a million entries, this method needs at most about half a trillion finger-position checks, plus sorting. At our hypothetical billion checks per second, that’s about eight minutes, compared with five years of checking every group.

Those are illustrations, not timings of real software. Different checks can take different amounts of time, and the sorting still has to happen. The point is the enormous advantage of avoiding work as the list grows.

def three_sum_sorted(nums):
    nums = sorted(nums)
    n = len(nums)
    for i in range(n - 2):
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total == 0:
                return nums[i], nums[lo], nums[hi]
            if total < 0:
                lo += 1   # need a bigger sum
            else:
                hi -= 1   # need a smaller sum
    return None

The limit researchers thought they had reached

The move from n³ to n² is dramatic. The next question is whether you can improve the growth pattern again.

For decades, researchers found refinements that shaved work off the n² method. But they couldn’t get an algorithm for general inputs with a growth bound of n raised to any fixed power below 2, under the computing rules discussed below. Even 1.9999 would count. That precise belief became known as the 3SUM hypothesis.

A hypothesis is an assumption researchers investigate, not a proven law. Still, this one became useful enough that other results depended on it.

Researchers had ways to translate other problems into 3SUM, or related problems, while preserving useful speed relationships. A translation like that is called a reduction. If solving a geometry problem much faster would also let you solve 3SUM much faster, believing 3SUM was hard gave you a reason to expect the geometry problem was hard, too.

That made 3SUM a benchmark well beyond a number puzzle. A whole body of research mapped these connections. An improvement could travel along some of the same connections and help solve other problems.

The precise scope: the integer hypothesis concerns whole numbers whose sizes are bounded by a fixed power of the list length, on a theoretical computer where an operation on a suitably sized chunk of bits counts as one step. It doesn’t cover arbitrarily enormous numbers at no extra cost. Researchers also study a separate model that allows exact operations on real numbers. These rules matter when comparing results; the example Python programs are illustrations, not implementations of the new theorem.

What changed, and why a tiny difference counts

In their October 5 paper, Josh Alman and Virginia Vassilevska Williams give an algorithm for integer 3SUM with a growth bound of n^1.9992.

The notation means “n raised to the power 1.9992.” It’s just below n², exactly the kind of improvement the hypothesis said couldn’t exist.

You may also see O(n^1.9992). The O notation expresses an upper bound on how the work grows for sufficiently large inputs, leaving out constant multipliers and smaller terms. It isn’t a stopwatch reading.

Look at the last two rows. Almost identical. So why does anyone care?

Because the hypothesis ruled out every fixed exponent below 2, however close to 2. A method with 1.9992 crosses that line. It establishes that the supposed barrier wasn’t an unavoidable feature of the problem.

The distinction is between showing a method that grows more slowly in theory and delivering faster software today. At a billion numbers, the difference between these two powers alone is under 2%. Getting a factor of two from that difference would require about 10^376 numbers: a 1 followed by 376 zeroes. Real implementations also have overheads that the growth bound leaves out. The paper doesn’t establish a useful speedup for your application.

The mathematical change reaches beyond 3SUM. The same technique improves all-pairs shortest paths, the task of finding the shortest route between every pair of places in a network. Its classic growth pattern is n³, where n counts the places. The paper lowers that exponent below 3 for the general integer-weighted setting it studies, crossing another long-standing hypothetical barrier.

This article explains the October 5 result, not a claim to today’s best exponent. An October 12 follow-on preprint reports further improvements. Both are research preprints; appearing on arXiv doesn’t establish independent peer review.

How does the new method work?

It goes beyond moving two fingers along a sorted list. Here’s the outline of the connection, rather than a substitute for the proof.

First, known translations turn the problems into questions about graphs: networks of dots joined by lines. A triangle is three dots with a line connecting every pair. The transformed question asks about triangles in a specially structured network.

Next, those connections can be represented using matrices, rectangular tables of numbers. Multiplying two such tables is a standard way of combining information about connections through intermediate dots.

The new algorithm computes a selected set of answers from a multiplication involving “thin” tables, where one dimension is much smaller than the others. It adapts existing algebraic methods to avoid calculations that aren’t needed for those answers, and proves that enough work can be avoided to lower the exponent.

The translations then carry that saving back to 3SUM and shortest paths. That’s why one discovery can affect several problems. Connections previously used to explain why improvement was difficult also provide routes for spreading an improvement once it exists.

The highlighted squares are the answers we need from the table multiplication. Simply choosing fewer answers isn’t the whole discovery; the new method reuses calculations across those answers. The proof establishes that this reuse saves enough work to lower the exponent. The network and tables above are schematic, not the actual conversion of our seven-number example.

Additional technical scope: the integer 3SUM method is deterministic, with a guaranteed growth bound rather than a bound averaged over random choices. The paper also gives an always-correct randomized method for real-number 3SUM, with expected growth O(n^1.998) in its exact-arithmetic model. Its integer shortest-path result is O(n^2.9995) for directed networks with polynomially bounded integer edge weights and no negative cycles, meaning no loop whose total cost is below zero. Those restrictions are part of the result.

What the AI actually contributed

According to the paper’s methodology account, an Anthropic employee asked an internal research model to check and improve mathematical constructions in cryptography. Those constructions depended on a related problem being hard to solve.

The model found a method showing the problem could be solved faster than assumed. It first handled typical inputs, then extended the idea to cover even the hardest inputs. That second step matters: being fast on friendly examples wouldn’t overturn an assumption about the worst case.

The authors report that the discovery session used 16 million output tokens, the pieces of text the model generates, with no human input during that session after its initial task. This was a substantial research run. It doesn’t mean the whole project happened without people.

Anthropic shared the algorithm with the authors in September 2026. They worked to understand, simplify, strengthen and extend it, connect the results to prior research, and write the paper. They credit Claude with discovering the algorithm and take responsibility for the publication.

That’s what makes the AI claim striking. The credited contribution is a new method addressing a long-standing research barrier. It goes beyond reproducing a familiar solution to a puzzle. The discovery account comes from the paper’s authors; a mathematical proof can establish the method’s properties, but can’t establish who or what originated it.

Why checking the result matters as much as finding it

An AI can produce a confident explanation that is wrong. A proposed algorithm needs an argument that it always gives the right answer and that its amount of work really has the claimed bound.

The authors report that, after the paper was written, Anthropic used a research model to formalize its main integer results in Lean, a proof assistant. Lean requires proofs to be expressed as precise logical steps that software can check against formal definitions.

The public formalization gives others an artifact they can inspect and check. That’s stronger evidence than a plausible paragraph from a chatbot. It still requires care: the formal definitions must match the intended mathematical claim, and the formalization covers the main integer results, not every version of the theorem or the story of its discovery. We haven’t independently rebuilt that proof project for this article.

Researchers had studied this puzzle for decades and suspected that this kind of improvement was impossible. The authors credit AI with finding the method that crossed that barrier. They’ve made their arguments and the formalization available for others to check.

That gives us something specific to examine when judging claims about AI research. What did the method change, and does the evidence hold up? Here, the change is a small exponent with a large implication: the limit researchers had relied on can be beaten.

Sources

• Alman and Vassilevska Williams, October 5 preprint, including the introduction, algorithm overview and acknowledgments/methodology.
• Public Lean formalization, as described in the paper; not independently rebuilt for this article.
• Majdoddin, October 12 follow-on preprint, cited to distinguish the original discovery from subsequent reported bounds.