Dense polynomials, sparse squares: the lab's report

All problems · Problem No. 1 · Dense polynomials, sparse squares

The lab's report: Dense polynomials, sparse squares

Five days, 51.9 trillion search steps and 30 methods: a real-coefficient bound below the one that has stood since 1949.

In 1947 Rényi and Erdős asked how few nonzero terms the square of a polynomial can have when the polynomial itself has no zero coefficient. Two years later Verdenius built families whose squares grow like n^0.8155 with integer coefficients and n^0.8107 with real ones. Epoch AI lists the question among its open problems and still cites n^0.811, from 1949, as the best known upper bound.

From 25 to 30 September 2026 the lab worked on nothing else. Up to 44 cloud helpers ran 176 agents at once; the lab designed and ran 30 methods, computed 164,904 units of research jobs and more than 51.9 trillion search steps, and checked every result exactly before it counted.

It closed the search with a proved real-coefficient exponent of 0.7872539, seven certified real blocks below the 1949 bound, a proved integer exponent of 0.812807, and theorems that explain why an integer block below the bar is so hard to find.

Real coefficients

0.7872539

Proved upper bound on the exponent, below 0.8107145 (Verdenius, 1949). A block of degree 31, certified with interval arithmetic and checked again by independent code.

Integer coefficients

0.812807

Proved upper bound: the 1947 block of degree 8, chained with a tuned scale. Below the 1949 integer construction (0.815465), not below 0.8107145.

Certified real blocks

Blocks of degree 10 to 31, each proved to exist and each below the 1949 bound for real coefficients.

What stays open: the problem asks for integer coefficients. The lab's integer bound, 0.812807, improves on the 1949 integer construction but not on 0.8107145, and no integer polynomial is known whose square has fewer than √n terms. Both bounds are the lab's own proofs, replayed by separate code; no one outside the lab has reviewed them yet.

closed 30 Sep 2026, 17:00 UTC · posed by Rényi and Erdős in 1947

By the numbers

51.9 trillion
search steps: 164,904
units of research jobs on the fleet: 8,966
core-hours of research jobs: 7,457
agents created: 176
agents at once, at the peak: 1.49 billion
search steps in one second, at the fastest: 30
methods designed and run: 44
cloud helpers at the peak, 38 through the week: 152
cores on research jobs at once: 394
curves and surfaces tracked branch by branch: 1,460
zero-dimensional shapes queued for complete solving: 54,180
units to close degrees 30 and 32

as of 30 Sep 2026, 17:33 UTC · the work on this problem only

Timeline

25 Sep 2026, 08:33A searcher finds Rényi's 1947 block again from scratch: degree 8, every coefficient nonzero, a square with 9 terms. Its family reaches 0.815465, the 1949 integer bound.
25 Sep 2026, 17:45The whole lab turns to this one problem: every helper searches dense polynomials.
26 Sep 2026, 09:20Integer bound 0.812807 proved: the 1947 block chained at step 9 with scale 196, where one kind of carry cancels exactly.
26 Sep 2026Verdenius's 1949 paper read in the original: two bounds, 0.815465 for integer coefficients and 0.8107145 for real ones, the n^0.811 that Epoch AI cites.
26 Sep 2026, 18:25An automatic prover for chain bounds, and the first real-coefficient bound below 1949: 0.809823, Verdenius's own block with a tuned scale, confirmed by independent code.
27 Sep 2026, 01:12The fleet at its largest: 44 cloud helpers, 176 agents at once.
27 Sep 2026, 08:40A real block of degree 15 certified in exact arithmetic: 0.8044748.
27 Sep 2026, 12:25The research queue goes live: methods are written as jobs and computed by the whole fleet, 152 cores at once.
27 Sep 2026, 13:35Real record 0.7872539: a block of degree 31 whose square has three clusters of terms, step 26, growth exactly 13, with a Krawczyk certificate and an independent check.
28 Sep 2026, 03:45The fastest moment: 1.49 billion search steps in one second.
28 Sep 2026Degrees 30 and 32 closed by a new exact solver: 54,180 units, 1,244 core-hours, no rational block.
30 Sep 2026, 02:45A final 24-hour push: eleven methods (M20 to M30) in one day, run by agents in parallel.
30 Sep 2026, 08:30The structural note: the window theorem, a degree bound and a calculus of cancellations explain why an integer block below the bar can only be found, not derived.
30 Sep 2026, 17:00The search closes. Every job is switched off and the lab turns to its next problem.

times in UTC

The real-coefficient bound, step by step

Each step is a real block proved to exist, with the exact support of its square, and its chain's growth computed exactly. Lower is better.

When	Exponent	Block
1949	0.8107145	Verdenius: a block of degree 12 built with the cube root of 5
26 Sep	0.809823	Verdenius's block chained with a tuned scale, proved by the type automaton
27 Sep	0.8044748	degree 15, exact interval certificate
27 Sep	0.8042949	degree 10, exact in Q(√7)
27 Sep	0.8007514	degree 14, Krawczyk certificate
27 Sep	0.7924813	degree 19, Krawczyk certificate
27 Sep	0.7876097	degree 25, Krawczyk certificate
27 Sep	0.7872539	degree 31, step 26, growth exactly 13: the lab's record

lower is better

What the lab proved

Two square roots and a window

Every block whose square has three clusters of terms is two truncated square-root series, one read from the lowest term and one from the highest, that agree on a window in the middle. Rényi's 1947 block is the Catalan case: the square root of 1 + 4x, with its mirror image as the tail.

A degree bound

Counting dimensions with symmetry shows that a block whose chain beats the bar has degree at most about 38. The lab's integer searches covered the degrees up to 32 as far as cost allowed.

A calculus of cancellations

In a chain two carries cancel by one equation that is linear in the chain's scale. One cancellation is free, each further one costs a dimension of the block family, and cancelling all of them is impossible. The type automaton turns this into exact, proved exponents.

Sparse or linear, not both

Rational blocks come for free only from linear equations, and a linear mechanism needs a square with at least 3n/2 terms. So an integer block below the bar can only be a rational point on a variety of high degree: something a search can find, not something a formula produces.

The small systems are finite

The non-symmetric systems of degree 15 to 18 that looked like curves are families of blocks with zero coefficients. Their dense solutions are finitely many (computed with exact checks), at degree 15 a rational one would need a coefficient divisible by 21 particular primes, and the real block of degree 17 is certified (0.801892).

A certificate template

Find a point numerically, prove an exact solution nearby with a Krawczyk interval certificate, read the square's support from the enclosure, compute the growth exactly from the transfer matrix and prove the chain dense: the recipe behind every real bound in this report.

theorems and certificates from the lab's notes

Every method: 30 in all, with 2 follow-ups

A block is a short polynomial with every coefficient nonzero whose square has few terms. Chaining a block with itself at larger and larger scales, A(x) · A(λx^m) · A(λ'x^(m²)) · ..., gives dense polynomials of every size, and their squares grow like n^e with e = log ρ / log m, where ρ is how fast the square's terms multiply from one level to the next. Every bound in this report is such an exponent, and lower is better.

The bar is 0.8107145, the 1949 bound. A block beats it when its chain's exponent is lower. Finding one means solving polynomial equations, because the square must vanish at prescribed places: a rational solution gives integer coefficients after scaling, a real one gives real coefficients.

Most methods below hunt for rational solutions: modulo primes and lifted back, over values built from small primes (S-units), numerically with exact recognition, or by solving a system completely. The others are proofs and reviews that close whole routes at once.

No.	Method	What it did	Outcome
M01	Tuned chains result	Chain a known integer block with a scale chosen so that some terms of the square cancel.	The integer bound 0.812807 (26 Sep). An audit then showed this route alone cannot pass 0.8107145 with integers.
M02	Census modulo small primes ruled out	Count every block of degree 8 to 16 whose square fits a sparse pattern, working modulo 5, 7, 11 and 13.	Closed as incomplete: small primes lose true solutions (the 1947 block disappears modulo 7).
M03	Symmetric curves, slice and lift no hit	On 37 symmetric three-cluster shapes of degree 22 to 28, fix one coefficient modulo a prime, solve for the rest and lift every solution to an exact one.	38,978 units, 548 core-hours, no rational block.
M04	General curves, slice and lift no hit	The same on 14 shapes without symmetry.	11,154 units, 167 core-hours, no rational block.
M05	Count sieve not run	Sieve shapes by the number of their solutions modulo many primes.	Not run: it waited behind M04, and later methods took its place.
M06	Geometry classifier tool	Count the points of each shape modulo many primes to read off its components and genus; an S-unit sieve on the sporadic points.	The symmetric curves of degree 8 to 24 have genus at least 1 and no rational point turned up; the first exact exclusion, at degree 22. 3,140 sieve units.
M07	Structure-first families result	Build blocks from known structures: head and mirror, periodic tails, Dickson polynomials, the 1991 example of Coppersmith and Davenport.	Closed for integers up to degree 22. Found a real block of degree 10, exact in Q(√7), at 0.8042949.
M08	Census on clean primes not run	The census of M02 again at primes large enough to keep every solution.	Not run: the queue moved to the curve searches.
M09	Mixed chains not run	Chains whose levels use different blocks.	Not run as a search; the route review (M22) and mixed steps (M26) covered the idea.
M10	Special sub-supports ruled out	Force extra zeros into a rational family and let the step vary.	A degree-12 curve reached 0.7933, but exact solving found only degenerate rational points.
M11	S-unit lifting no hit	Try every value built from the primes 2, 3, 5 and 7, later up to 13, as the free coefficient of the four best curves.	About 50 core-hours, no rational block.
M12	Real certificates result	Prove the real blocks exist exactly with interval arithmetic and compute their growth exactly.	Certified 0.8042949, 0.8007514, 0.7924813, 0.7876097 and the record 0.7872539.
M13	Wide shape scan tool	Scan symmetric shapes of degree 24 to 40 with a free step.	370 shapes below the bar, 30 of them curves; the targets of M14 to M17.
M14	Exact slice solver tool	Eliminate one coefficient of each slice by a greatest common divisor over a finite field.	1.1 to 1.4 times faster, which opened degrees 30 and 32: 46,780 units and 5,132 core-hours before M17 replaced it.
M15	Fibre solver tool	Solve each slice by elimination instead of trying every value.	Became the core of M14.
M16	Numerical search, exact recognition no hit	Solve numerically from many random starts, refine to 80 digits and recognise rational numbers exactly.	448 units, 52 core-hours, no rational block.
M16b	Branch tracking no hit	Follow every real branch of each curve continuously and test every rational crossing.	689 units over 307 curves, 30 more curves and 57 surfaces, no rational block.
M17	Second elimination level no hit	Remove a second coefficient by resultants over a finite field: 3.3 times faster.	Degrees 30 and 32 closed completely: 54,180 units, 1,244 core-hours, no rational block.
M18	Numerical search on every curve no hit	M16 on all 307 curves from the queue, degrees 20 to 72.	1,796 of 2,456 units by the close, 416 core-hours, no rational block.
M19	Two-scale families ruled out	Blocks without symmetry, built from two independent square-root series.	No rational family below the bar up to degree 18; five systems left for M19-open.
M19-open	The five leftover systems ruled out	Solve them numerically and test every solution.	No rational point; four of the five hide real curves.
M20	Fibrations and witness sets tool	Certify the geometry of the solution sets with trace tests and witness sets.	Degrees and components certified, and 14 odd-degree curves found that no search had covered.
M21	Small curves, slice and lift no hit	Exact slices on the small curves of M19-open.	1,691 units and thousands of local values, no rational block; M27 then showed these were not curves of dense blocks.
M22	Route review ruled out	An independent review of every route beyond one block per chain, and of the literature.	No new route: two clusters, four stacks, Kronecker substitutions, Galois norms, compositions and more fail by counting.
M23	Odd-degree solver no hit	A new exact core for odd degrees, run on the cheapest of the 14 new curves (degree 29).	3,038 of 24,389 units, 318 core-hours, no rational block; larger degrees closed on cost.
M24	Genus of the small curves ruled out	Estimate the genus of the small curves from point counts and fibre degrees.	Genus 0 or 1 looks unlikely (not certified), so no free parametrisation is expected.
M25	The blind-spot slices no hit	Blocks whose linear coefficient is zero on the nine record curves, a case the usual normalisation skips.	1,182 real solutions found and checked exactly, none rational.
M26	Mixed steps ruled out	Alternate two steps in one chain.	The exponent is exactly the average of the two: no gain.
M27	Finiteness theorem result	Prove what the small systems of degree 15 to 18 really are.	Proved: the apparent curves are families with zero coefficients. Dense solutions are finitely many (exact checks); a real block of degree 17 certified at 0.801892.
M28	Complete solving no hit	Find every complex solution of each zero-dimensional shape and test each one for rationality.	85 of 1,460 shapes done by the close, no rational block.
M29	A third identity ruled out	Look for a new algebraic identity like the square-root series and the mirror of the 1947 block.	None survives. Found a relation that would be worth 0.02 to 0.05 on the exponent; no known block satisfies it.
M30	Overlap-tuned shapes no hit	Scan shapes tuned by that relation.	Degrees 8 to 14 complete and empty; the fleet scan was paused for memory at the close.

4 with results · the rest closed routes or built tools

What the lab ruled out

Two-cluster and four-cluster constructions: counting shows they cannot beat the bar (the 1949 shape at step 13 gives 0.9746, four stacks at least 0.82).
Blocks in several variables, Kronecker substitutions, sums of chains and circulant recursions.
Galois norms and traces, products of blocks and compositions.
Chains that alternate two steps: the exponent is exactly the average.
Every three-cluster shape up to degree 22, by exact algebra.
The record curves of degrees 20 to 32: slices modulo primes lifted exactly, and S-unit values.
The 307 curves from the queue, numerically and branch by branch.
Blocks whose linear coefficient is zero, on the nine record curves: 1,182 real solutions, none rational.
The small non-symmetric systems of degree 15 to 18: families with zero coefficients, not curves of dense blocks.
A third identity of the kind the 1947 block uses: none of the natural candidates survives.

routes closed by proof, by counting or by complete search

The live record

from the lab feed, as the lab published it

Where it stands

Find a polynomial whose coefficients are all nonzero integers and whose square has as few nonzero terms as possible.

The square of a typical dense polynomial is dense too. The open question is how few terms the square of a dense polynomial can have as its degree n grows: the best known families have squares with about n^e terms for a fixed exponent e, and a lower e is better.

The published record

...

Reading the lab feed.

The lab's best family

...

Reading the lab feed.

The lab's best explicit witness

...

Reading the lab feed.

The lab's best single polynomial

...

Reading the lab feed.

reading the lab feed

Console

offlinetimes in UTC

connecting to the lab…

Record book

by kind

Reading the record book…