Research

A new upper bound for Hurwitz's sum-of-squares problem

Open since 1898, Hurwitz's question saw its exponent drop below two only in 2024, to 1.62. We bring it down to 1.414 using an idea from mathematical physics.

By Eurekist · 8 November 2026 · Algebra, complexity theory

The short version

The question
Multiply a sum of n squares by another sum of n squares. How many squares does it take to write the answer? Expanding everything gives n2. This has been an open question for more than 120 years.
The result
The best known count drops from about n1.62 to about n1.414. The exponent is √2, which is also below the 1.5 that an open problem of Pavel Hrubeš was aiming for. This holds over fields that contain √−1 or have odd characteristic.
The idea
The proof borrows from mathematical physics. Give each variable a label. Pairs of labels can pass through a much smaller middle space, and an identity from vertex algebra, the mathematics of the free boson, guarantees that nothing is lost.
Why it matters
Upper bounds here decide how much room is left for a known route to exponential circuit lower bounds. The same construction also gives circuits of size O(n1.985) over every field. If the note is correct, this answers a question Hrubeš asked about characteristic two.
How we checked it
The identity was checked exactly on small cases, and the scripts are public. The growth rate rests on the proofs in the note.
The limits
It does not help SAT, and it only matters at enormous sizes.

1. The question

How many squares does it take to multiply two sums of squares? After more than 120 years, nobody knows.

In May 1748 Leonhard Euler wrote to Christian Goldbach about sums of four squares. Multiply two such sums together and the result is again a sum of four squares. The version for two squares was already very old:

(a2+b2)(c2+d2)=(ac−bd)2+(ad+bc)2

Around 1818 Carl Ferdinand Degen found a version for eight squares. In 1898 Adolf Hurwitz proved that the list stops there. With the same number of squares in all three places, a formula like this exists only for one, two, four and eight.

That leaves a counting question. If more squares are allowed on the right, how many do you need? Write σ(n) for the smallest number that works for two sums of n squares, where each new square is the square of a combination of the products xi yj.

Expanding every product gives σ(n) ≤ n2. The best known bound stayed near that, at about n2/log n, until Hrubeš brought the exponent below two in 2024 with O(n1.62). This post goes well below that, to n√2+o(1). The deduction is short, and the key ingredient comes from an unexpected place: an identity from vertex algebra that was built for a SAT algorithm.

Figure 1. The exponent c in σ(n) ≤ nc, drawn to scale. Hrubeš's Problem 1 asks for a construction that would give 1.5. The bound here is already lower, by a different route.

Computer scientists care because of a 2011 paper by Hrubeš, Avi Wigderson and Amir Yehudayoff. They showed that proving σ(n) grows at least as fast as n1+ε, for any fixed ε > 0, would give exponential lower bounds for non-commutative arithmetic circuits, a model of computation in which xy and yx are different.

So each upper bound on σ(n) limits how much room that approach has. The range from 1 to √2 is still open, so the approach survives, with less room than before.

We were not looking for this result. We had been trying to improve the time bounds for counting solutions to k-SAT in recent papers from OpenAI and Anthropic,1 and we did not succeed. While working through Anthropic's paper, we saw that an identity in its Appendix B, used there to build crossing gadgets, gives a better bound on this old problem than any we could find in print.

2. A puzzle with four corners

The proof replaces squares with a simpler puzzle: test the two diagonals of a rectangle using only pieces that read its sides.

Put four labels at the corners of a rectangle, going around in the order x, y, v, u. We want a function that equals 1 when both diagonals match, meaning x = v and y = u, and 0 otherwise. We write it T = [x = v][y = u].

We must build T by adding up simple pieces, and each piece can only read two opposite sides. A row function reads the top and the bottom. A column function reads the left and the right. Neither can read a diagonal.

xyvu

Target[x = v][y = u]

xyvu

Row functiona(x, y) b(u, v)

xyvu

Column functionc(x, u) e(y, v)

Figure 2. The target compares labels across the diagonals. Each allowed piece reads two opposite sides and nothing else.

The puzzle is to use as few pieces as possible. Call the smallest number P(n, m), when x and v take n values and y and u take m values.2 With one kind of piece alone you need nm pieces, which is where the easy n2 comes from. All the savings come from mixing the two kinds.

A solution to the puzzle gives a formula for squares. Each piece turns into a product of two bilinear forms, and a product can be rewritten as two or three squares. So a bound on P gives the same bound on σ, up to a factor of two or three.

How a solution becomes a formula

Multiply T by xx yy xv yu (the variable x with index x, and so on) and sum over all labels, treating the variables as commuting. The left side becomes the product of the two sums of squares. A row or column function becomes a product ff′ of two bilinear forms. When the characteristic is not two,

ff′=(f+f′2)2−(f−f′2)2

If √−1 is in the field, the minus sign costs nothing and each product becomes two squares. In odd characteristic, −1 is a sum of two squares in the prime field, so each product becomes three squares. More generally, if −1 is a sum of r squares in the field, then r + 1 squares per product are enough.

3. Where the square root of two comes from

There are far fewer partitions of 2h than pairs of partitions of h. That gap is the whole saving.

The labels are partitions, the ways of writing a whole number as a sum. For example, 3 + 1 + 1 is one of the seven partitions of five. Write p(h) for the number of partitions of h. Hardy and Ramanujan showed in 1918 that ln p(h) grows like a constant times √h.

Use the partitions of h as labels, so there are N = p(h) labels and N2 pairs. The new formula sends each pair through a middle space whose states are partitions of numbers up to 2h. Because of the square root, doubling h only multiplies ln p by √2. So the middle space has about N√2 states, far fewer than N2. Figure 3 lets you try it.

Labels, N190,569,292
Middle states3,972,999,029,388
Pairs of labels, N2about 2⁵⁵
limit, N√2

Middle states = N to the power 1.522

Figure 3. Move the slider to change h. Bar lengths are logarithms, so the pairs bar is always twice the labels bar. The middle bar shrinks toward the line at √2 ≈ 1.414, and it gets there slowly. Middle states are counted here as p(2h). The full count is in Table 1.

You would expect this squeeze to lose information. The identity in Anthropic's Appendix B is what prevents that. It splits T into blocks, one for each integer s, and each block can be run in two orders, shown in Figure 4.

One order makes the block a sum of row functions. The other makes it a sum of column functions. Each state of the middle space gives one piece, so we pick the order with the smaller middle space. The blocks then add up to exactly T.

Row order. The middle state σ has weight at most 2h + s.

y operator for xreads x and y σ operator for vreads u and v u

Column order. The middle state σ has weight at most 2h − s.

y operator for vreads y and v σ operator for xreads x and u u
Figure 4. The same block run in two orders, with all labels at size h. Using the row order for negative s and the column order for positive s keeps every middle state at weight 2h or below.

The result, allowing different numbers of values n and m, is this, over every field:

lnP(n,m)≤(1+o(1))ln2n+ln2m

For n = m it gives P(n, n) ≤ n√2+o(1).3

The precise statement

Take polynomials in variables t1, t2, … with tk of weight k, so that the monomials of weight E are the partitions of E. This space carries the Heisenberg vertex algebra, which physicists know as the free boson. Each polynomial a gives operators a[r] that raise weight by r. For b of weight h, Appendix B of Anthropic's paper defines

Qs(a,b)=∑i=02h(−1)ia⟨i⟩[s−h+i]b[h−s−i]

and proves three facts (Lemma 9):

  1. Qs(a, b) does not change if the two families of operators are applied in the opposite order. This is an explicit form of locality.
  2. On states of weight E, Qs(a, b) = 0 when |s| > E + h.
  3. The sum of Qs(a, b) over all s multiplies every state by a single number.

The same appendix chooses a polynomial ax for each partition x of h. With b = tv, the number in fact 3 is then 0 unless x = v, and a known nonzero number zv when x = v.

Let x, v be partitions of h and y, u partitions of E. Apply Qs(ax, tv) to ty, read the coefficient of tu, and divide by zv. By fact 3, the results As add up to T. By fact 1, each As has both forms in Figure 4, with middle weight at most E + h + s or E + h − s. So

P(p(h),p(E))≤(2E+2h+1)S(E+h)

where S(E) = p(0) + … + p(E). If n = p(h) and m = p(E), then ln n ≈ c√h and ln m ≈ c√E, and c√E + h = √ln2 n + ln2 m. The square root in the theorem is the Pythagorean formula applied to √h and √E.

4. The same identity modulo a prime

Modulo a prime, some labels break. Removing them leaves fewer labels and the same exponent.

All the operators have integer entries, so the identity holds modulo any prime p. The problem is the number z at the end of the test. For some labels it is divisible by p, and then the test reads 0 = 0 and tells us nothing.

The fix is to remove those labels: any partition with a part divisible by p, or with a part repeated p or more times. In characteristic two, that leaves the partitions into distinct odd parts. For 16 that is only five labels, out of 231 partitions. What remains is the simple Heisenberg vertex algebra in prime characteristic studied by Haisheng Li and Qiang Mu, so the operators still work.

With fewer labels, the bound takes longer to start working. But the logarithm of the count still grows like a constant times √E, and the constant cancels out of the exponent.4 Only the square root matters, so the exponent is √2 in every characteristic.

The algebra

For a partition ν with mk parts equal to k, the number in the test is

zν=∏kkmkmk!

Let I be the ideal generated by all tk with p dividing k and all powers tkp. All the operators preserve I, so they act on the quotient, whose basis is the set of labels above. On those labels zν is not zero. The constant in the count is π√2/3 (1 − 1/p).

5. Circuits and characteristic two

The puzzle also gives smaller circuits, including in characteristic two, where squares say nothing.

The polynomial at the center of the 2011 approach is IDn = ∑ xi yj xi yj, in variables that do not commute. Written out, it takes about n2 multiplications. Hrubeš showed size O(n1.96) when the characteristic is not two, and asked whether anything below n2 is possible in characteristic two.

Squares cannot help there, because in characteristic two the product of the two sums of squares is already a single square. The puzzle can still be used directly. Each row or column function turns into a small piece of a circuit, and no step divides by two. What remains is to compute many bilinear forms at once, which Hrubeš's Lemma 24 does with matrix multiplication.

Size of IDnUsesHolds over
O(n1.96), Hrubeš 2024Fast rectangular matrix multiplicationCharacteristic not two
O(n1.985), this noteStrassen's algorithm onlyEvery field
O(n1.859), this noteω(1, 3, 1) < 4.1989, from Vassilevska Williams, Xu, Xu and ZhouAny field where that bound holds

The same bounds extend to the non-commutative elementary symmetric polynomials.5

6. How we checked it

Exact computer checks on small cases, and a search of the literature.

The identity
check_pieces.py works in exact arithmetic. It tests that both orders agree, that the blocks add up to T entry by entry, and that the size bounds hold. We ran it over the integers up to h = 6, over F3 up to h = 10, and over F2 up to h = 16.
The pieces
check_explicit.py builds every row and column function and checks their sum, including labels of different sizes. Largest cases: (5, 3) and (4, 4) over the integers, (12, 8) over F2, (6, 6) over F3, (6, 3) over F5, (5, 5) over F7.
The literature
As of 8 November 2026 we searched ECCC, arXiv and the web, and found no earlier statement of these bounds. A December 2025 paper by Rossman and Zhu still cites n1.62 as the best known bound over the complex numbers.
Limits of the checks
Small cases cannot confirm the growth-rate steps or the circuit parameters, which rest on the proofs in the note. Nothing in the note is formalized. Anthropic's repository lists Lemmas 9 and 10 as formalized in Lean 4. We did not build or check those files.

The scripts use only the Python standard library. A literature search can miss things.

7. Limitations

  • The bounds only matter at enormous sizes. The exponent passes 2 near N = 216 and Hrubeš's 1.62 near N = 268 (Table 1). In characteristic two, a rough estimate puts the point where the Strassen circuit beats n2 at log2 n in the thousands. Nobody will write these formulas out.
  • Nothing over the real numbers. Turning products into squares needs −1 to be a sum of squares, which fails over the real and rational numbers. This may be more than a limit of the method. Zhang and Zhu showed this year that the problem can depend on the field, with a formula of type [12, 12, 18] that exists over the complex numbers but not over the real numbers.
  • The best circuit bound is conditional. Laser-method bounds are generally understood to hold over every field, but we did not find this stated for the specific bound behind 1.859. The bound 1.985 does not depend on it.
  • The central identity is not ours. In characteristic zero it is in Appendix B of Anthropic's paper, and the quotient in prime characteristic is due to Li and Mu. Our part is the short deduction, the form with n ≠ m, the crossing identity in prime characteristic, and the circuit bounds.
  • No lower bound and no progress on SAT. n√2 is still superlinear, so the route of the 2011 paper remains open. None of this improves the running time for 3-SAT or k-SAT.
hN = p(h)Exponent of the full countExponent of p(2h) alone
1025.42.6391.723
40215.22.0201.574
160236.61.7391.502
640281.51.5941.464
2,5002170.91.5161.443
10,0002354.01.4711.430
Table 1. The bound as a power of N in characteristic zero, using exact partition numbers. The full count takes the cheaper order for each block. The limit of both columns is √2 ≈ 1.414.

8. Open questions

  • What is the true exponent? It could be anywhere from 1 to √2. Proving any exponent above 1 would give the circuit lower bound of the 2011 paper.
  • Can a different algebra beat √2? The same construction should work for other vertex algebras. We scanned several families numerically, including Virasoro minimal models, symplectic fermions, free fermions and the Deligne series, and none went below √2. The closest was free fermions at about 1.42. This is a hint and not a theorem, since we have not proved the general construction.
  • Is there anything over the real numbers? A subquadratic bound there would need a different idea.

If you find an error or an earlier source, please write to max@eurekist.com. We will correct this post and record the change here.

Author

This post and the note were written by Eurekist.

Credits

The central identity comes from Anthropic's 3-SAT paper. The reductions to circuits follow Hrubeš, and the algebra in prime characteristic is due to Li and Mu.

Footnotes

  1. The target was the bound 2O(n/√log n) at bounded clause density and 2Ok(n loglog n/√log n) in general. We found no improvement. ↩︎
  2. For the rational numbers and n = m, this is the quantity P(N) in Appendix G of Anthropic's paper, which already links crossings to Hurwitz's problem. That appendix records O(N11/6) from a different lemma and cites O(N1.62). It is also the rank in Naslund's Problem 12, the width of IDn in the 2011 paper, and the PT-rank of Rossman and Zhu. ↩︎
  3. The o(1) depends only on the characteristic of the field. In characteristic zero, the bound is O(n√2 (ln n)5). ↩︎
  4. This follows from the generating function of the labels and Kohlbecker's Tauberian theorem. See Lemma 5 in the note. ↩︎
  5. For fixed k ≥ 4, the polynomial Sk,n has size O(nk−4+c), with c the exponent from the table. Optimizing the split over real parameters brings 1.859 down to about 1.854. ↩︎

References