Research 11/18/2026

GPT-6.2 Astra Formalizes Smoktunowicz's Gap Theorem

On our new Autoform-Hard benchmark, GPT-6.2 Astra produced a Lean proof that no graded domain has Gelfand–Kirillov dimension strictly between 2 and 3, a 2006 theorem of Agata Smoktunowicz that, as far as we know, had never been formalized. It took 94 minutes, and the argument takes a different route from the published one.

Jacob Stavrianos
GPT-6.2 Astra Formalizes Smoktunowicz's Gap Theorem

Of the 56 research-level formalization tasks on Autoform-Hard, exactly one separates the top of the leaderboard. GPT-6.2 Sol and Claude Fable 5.2 solve exactly the same 48 tasks. GPT-6.2 Astra also solves a 49th, and it is the only model on the board to do so: a 2006 theorem of Agata Smoktunowicz about the growth of graded algebras.

Not only is it the only language model we tested to formalize Smoktunowicz’s theorem, it’s also the only formalization we’ve ever heard of. Astra’s proof takes 94 minutes and about 1,800 lines of Lean, and after a shared opening it takes a different route from the published argument. Read the annotated proof here

The run

Astra worked alone in a sandbox with Lean, Mathlib and a shell, under Autoform-Hard’s limits of three hours and a $200 budget. No human touched it. The whole run cost $21.58 at Astra’s published price.

94 minwall clock
1,794lines of code
146agent turns

It nearly ended early. About 47 minutes in, Astra submitted a partial proof: complete for the easier, commutative case, but with a gap (a sorry) in the general one. The grader rejected it. Astra then filed an honest “unsolved” report, saying exactly what it had and hadn’t proved. Autoform-Hard doesn’t let a model give up until it has spent $20, and Astra had spent about $8, so the harness sent it back to work. It spent the next nine minutes thinking without writing any code, then started on a new approach. The grader accepted the full proof 39 minutes after the “unsolved” report.

How we checked it

Autoform-Hard accepts a proof only if it passes clean-room grading. The graded theorem is rebuilt from a trusted copy of the task, its statement must match the original exactly, and the proof may use only Lean’s standard axioms (propext, Quot.sound, Classical.choice). An independent kernel then replays the proof.

We also reviewed this proof by hand:

  • It builds with no sorry and no warnings, and depends only on the standard axioms.
  • The trusted task files are byte-identical to the originals.
  • It uses no native_decide, new axioms, unsafe code or redefinitions of benchmark objects.
  • The statement matches Theorem 1 of the paper, including the finite-dimensional degree-zero part.

This is a formal proof of Smoktunowicz’s theorem, not a formalization of her proof. The two coincide only in the opening steps.

How the proof works

The theorem is about how fast an algebra grows. Start from a few generators and count how many independent elements you can build with at most nn multiplications. Smoktunowicz proved that for one natural family of algebras, that count grows either no faster than about n2n^2 or at least as fast as about n3n^3, never at a rate strictly in between.

Astra argues by contradiction. It assumes the growth rate lands in the forbidden range and shows that the growth must then be slower than assumed, which is a contradiction.

The published proof leans on three deep results from algebra and algebraic geometry. None of them is in Mathlib, Lean’s math library, and formalizing them would be a large project in its own right. Astra used none of them. Instead it defined a quantity it calls capacity: how much a space grows when multiplied by a fixed generating piece. Capacity behaves like the size of a boundary in a graph, and the rest of the proof is built on it.

Capacity has relatives in the research literature. We trace them in Hard Mode, below.

The annotated proof

We have annotated the full proof line by line. You can scroll through the Lean code with three layers of commentary:

  • Code: what each declaration does.
  • Thinking: what Astra was doing when it wrote it, reconstructed from the run log. Quoted reasoning comes from provider-generated summaries, not the model’s raw reasoning.
  • Math: where each step sits relative to the published proofs.

Start with Capacity.lean, the heart of the argument; Hard Mode below walks through every file.

See where every model stands on Autoform-Hard. Thanks to the AutoformBench team at Meta FAIR for the benchmark, and to OpenAI for permission to publish the proof and excerpts from the model’s reasoning.

Hard Mode

From here on, this post is for readers who want the mathematics and a minute-by-minute account of the run. If you’re not a mathematician, this is a good place to stop.

How the proof REALLY works

Take an algebra AA over a field, generated by finitely many elements. Count the dimension of the space spanned by products of at most nn generators. If it grows like nδn^{\delta}, then δ\delta is the Gelfand–Kirillov (GK) dimension of AA, a standard measure of how big a noncommutative algebra is. A polynomial ring in dd variables has GK dimension dd.

For general algebras, GK dimension can be any real number from 2 up. Extra structure rules values out. Bergman showed that nothing lies strictly between 1 and 2 [KL00, Thm 2.5]. For algebras that are graded by the natural numbers and have no zero divisors, Artin and Stafford [AS95] ruled out GK dimension strictly between 2 and 11/5, and Smoktunowicz [S06] strengthened the result:

Theorem [S06, Thm 1]. A finitely generated algebra over a field that is graded by N\mathbb{N}, has no zero divisors and has a finite-dimensional degree-zero part has GK dimension either at most 2 or at least 3.

The Lean statement in the benchmark has exactly these hypotheses. Experts wrote and audited it for Meta FAIR’s AutoformBench, independently of this run.

The proof is a contradiction. Assume the GK dimension lies strictly between 2 and 3. Then the space of everything up to degree nn grows faster than n2n^2 but slower than n3n^3, so the single degree-nn piece, dim⁡An\dim A_n, grows faster than linearly but slower than quadratically. Astra then shows that slower-than-quadratic growth in fact forces linear growth. The first half sets up a division ring of fractions DD and follows known steps. The second half, the capacity argument, is where it leaves the published proof behind.

1. From GK dimension to counting dimensions

Growth.lean110 lines · first written 17 minutes in

Vocabulary: the span of words of length at most nn in the generators, plus small facts about the benchmark's growth definitions.

Read the annotated code →
Degree.lean159 lines · first written 19 minutes in

Counting by word length and counting by grading degree give the same growth up to constants. This is where the finite-dimensional degree-zero part is used.

Read the annotated code →
Hilbert.lean160 lines · first written 22 minutes in

Restates the hypothesis in terms of dim⁡An\dim A_n: a GK dimension strictly between 2 and 3 means dim⁡An\dim A_n grows faster than linearly but slower than quadratically. The rest of the proof shows that is impossible.

Read the annotated code →

2. Fractions

Ore.lean91 lines · first written 25 minutes in

Because AA grows only polynomially, any two nonzero elements have a common multiple (the Ore condition), so AA embeds in a division ring of fractions.

Read the annotated code →
HomogeneousFractions.lean127 lines · first written 29 minutes in

Builds that division ring QQ and, inside it, DD: the fractions a/ba/b with aa and bb of equal degree. The rest of the argument lives in DD.

Read the annotated code →
Boundary.lean89 lines · first written 41 minutes in

Two tools: putting finitely many fractions over a common denominator, and a plateau lemma saying a slowly growing sequence must stall somewhere. The name is a fossil of an argument Astra later cut.

Read the annotated code →

3. DD is generated by one piece

This section proves a known result, Artin and Stafford's [AS95, Thm 1.15], by a different contradiction.

Frames.lean138 lines · first written 57 minutes in

The division ring generated by a subspace UU, and a criterion: if multiplying UU by VV less than doubles its dimension, then VV already lies in the division ring UU generates.

Read the annotated code →
StableIntervals.lean85 lines · first written 59 minutes in

Conjugation by a homogeneous element is an automorphism, and generated division rings behave well under it.

Read the annotated code →
Weighted.lean98 lines · first written 62 minutes in

Bookkeeping for words in generators of different degrees, with a pigeonhole argument on their total weights.

Read the annotated code →
CoefficientGeneration.lean194 lines · first written 64 minutes in

DD is generated, as a division ring, by one finite-dimensional piece S=Admx−mS=A_{dm}x^{-m}. Artin and Stafford [AS95] derive this from common denominators; Astra derives it from growth.

Read the annotated code →

4. The capacity argument

Capacity.lean133 lines · first written 75 minutes in

The heart of the proof.

For a finite-dimensional subspace UU, measure how much it grows when multiplied by SS, the piece from section 3 that generates DD: the defect dim⁡(SU)−dim⁡U\dim(SU)-\dim U. The capacity of UU is the smallest defect among subspaces containing UU. Astra shows that capacity behaves like the size of a boundary in a graph: merging two subspaces costs no more than the parts, and shifting UU by a nonzero element changes nothing. From this follows the fact the whole proof turns on: the elements that do not raise the capacity of UU form a division ring. So to control all of DD, it is enough to control a set of generators. The defect is the quantity in Zhang's volume difference inequality, which defines his lower transcendence degree [Z98, §1] and which he proposed as a route to this gap [Z98, Prop 8.6]; his Lemma 8.7 has a stabilizer argument of the same shape. Minimizing over larger subspaces, and the plateau argument built on it, are not there. The tools are also those of Hamidoune's isoperimetric method from additive combinatorics, which proves sumset bounds by studying the sets that minimize growth; Lecouvey adapted it to subspaces of division rings [L14]. Astra wrote all 25 declarations in a single command 75 minutes into the run, and the file compiled after one round of fixes.

Read the annotated code →
MaxCapacity.lean113 lines · first written 77 minutes in

Runs the capacity along the growing pieces Adnx−nA_{dn}x^{-n}. It cannot rise at every step, since that would force quadratic growth, so it plateaus. At the plateau, the division ring from Capacity.lean contains the generator SS, hence all of DD.

Read the annotated code →

5. From a plateau to linear growth

Cuts.lean107 lines · first written 79 minutes in

Combinatorics of words: cutting a homogeneous word at a letter of bounded degree, and which degrees occur at all.

Read the annotated code →
Optimal.lean172 lines · first written 82 minutes in

The payoff: one finite-dimensional T⊆DT\subseteq D whose products T AnT\,A_n grow by a bounded amount, uniformly in nn. At 172 lines, it is the largest file Astra wrote in one go.

Read the annotated code →
Controlled.lean87 lines · first written 84 minutes in

A second division-ring lemma: the elements that multiply with bounded growth form a division ring, so again it is enough to check generators.

Read the annotated code →
LinearBound.lean105 lines · first written 86 minutes in

Turns bounded growth into dim⁡(TAn)≤dim⁡(TAn−d)+C\dim(TA_n)\le\dim(TA_{n-d})+C, hence dim⁡An\dim A_n grows at most linearly. That contradicts Hilbert.lean.

Read the annotated code →

6. The theorem

Submission.lean45 lines · first written 39 minutes in

The graded theorem itself: a seven-line proof that strings the modules together and ends in that contradiction.

Read the annotated code →

The workspace also contains Helpers.lean, an empty file that came with the task.

The formal proof is partly a known route and partly not. Its first half (growth of the graded pieces, the Ore condition, the degree-zero division ring DD, and DD being generated by one piece) matches standard steps and [AS95, Lem 1.6, Thm 1.15]. Its second half, the capacity argument that goes from subquadratic growth straight to a linear bound on dim⁡An\dim A_n, has no counterpart in [AS95], [S05] or [S06]. Its basic quantity does appear elsewhere: it is the volume difference behind Zhang's lower transcendence degree [Z98]. It takes the place of Bergman's Gap Theorem [KL00, Thm 2.5], the Small–Warfield theorem [SW84] and the Riemann–Roch argument [AS95, Thm 1.2], none of which is in Mathlib.

Published proofs (AS95, S05, S06)
  1. Graded ring of fractions Q(R)=D[z,z−1;σ]Q(R)=D[z,z^{-1};\sigma] and the Ore property, quoted from the literature [AS95, pp. 235–236], [S06, pp. 635–636]
  2. dim⁡Rn\dim R_n grows like nGKdim⁡R−1n^{\operatorname{GKdim}R-1} [AS95, Lem 1.6]
  3. DD is finitely generated as a division ring, by Vn=Rnz−nV_n=R_nz^{-n} [AS95, Thm 1.15]
  4. GKdim⁡D<2\operatorname{GKdim}D<2. Artin–Stafford get this for GKdim⁡R<11/5\operatorname{GKdim}R<11/5 from a common-denominator estimate [AS95, Prop 1.4, Cor 1.5]. Smoktunowicz gets it for GKdim⁡R<3\operatorname{GKdim}R<3 from generic elements, Lemma 3 and a dimension count on chains UiU_i ([S05, Thm 1], for infinite KK with a transcendental element; [S06, Thm 3], all fields, over K(X)K(X))
  5. Bergman's Gap Theorem [KL00, Thm 2.5] gives GKdim⁡D≤1\operatorname{GKdim}D\le1; Small–Warfield [SW84] makes DD finite over a function field of a curve [AS95, p. 242]
  6. Then dim⁡Rn≤cn\dim R_n\le cn by Riemann–Roch [AS95, Thm 1.2], so GKdim⁡R≤2\operatorname{GKdim}R\le2
Formal proof (GPT-6.2 Astra)
  1. Known steps, re-proved: growth of dim⁡An\dim A_n, the Ore condition, QQ and its degree-zero division ring DD (sections 1–2)
  2. Known step, proved differently: DD is generated by one finite-dimensional space S=Admx−mS=A_{dm}x^{-m} (section 3)
  3. Not in the published proofs: capacity, built on the volume difference of [Z98]; a monotone, submodular, translation-invariant integer attached to subspaces of QQ (section 4)
  4. Not in the published proofs: subquadratic growth forces a capacity plateau, whose stabilizer is a division subring containing DD (section 4)
  5. Not in the published proofs: a fixed T⊆DT\subseteq D with uniformly bounded expansion of TAnTA_n; bounded-expansion multipliers form a division subring; hence dim⁡An=O(n)\dim A_n=O(n) (section 5)

Where the two proofs touch

Formalhilbert_of_gap and its lemmas (Hilbert.lean)
Same statement and the same idea (multiplication by a homogeneous element is injective). Astra also has to compare word length with degree, because the benchmark's generators need not be homogeneous.
PublishedQ(R)=D[z,z−1;σ]Q(R)=D[z,z^{-1};\sigma]; domains of finite GK dimension are Ore [AS95, pp. 235–236]
FormalOre.lean, coefficientField, conjAlg
Same objects. The papers cite these facts; Astra proves them, and never builds the skew Laurent ring.
FormalcoefficientField_eq_genField (with Frames, StableIntervals, Weighted)
Same statement, with the same spaces Rnz−nR_nz^{-n} and the same key observation (U∩Uα=0U\cap U\alpha=0 when α\alpha is outside the division ring generated by UU). The contradiction is drawn differently: from common denominators in the paper, from growth in the formal proof.
PublishedLemma 3 of [S05] and [S06]; loosely, [AS95, Lem 1.10–1.13]
Formalexists_rank_plateau (Boundary.lean)
Same role: a telescoping argument that turns the growth bound into a favourable index. Different statements.
PublishedSmoktunowicz's chains UiU_i [S05], [S06]
Formaldefect_modular, cap_merge; the estimate hR inside maximal_capacity
Both rest on dim⁡(X∩Y)=dim⁡X+dim⁡Y−dim⁡(X+Y)\dim(X\cap Y)=\dim X+\dim Y-\dim(X+Y) and both bound a loss by an increment of the Hilbert function. The objects counted are different.
Publishednone
Formalcap, capStab, optimal_tails, controlledField (Capacity, MaxCapacity, Optimal, Controlled)
No counterpart in any of the three papers: a minimised, submodular, translation-invariant expansion count, and the fact that the elements preserving it form a division subring. The underlying defect is Zhang's volume difference [Z98, §1], and [Z98, Lem 8.7] proves a stabilizer is a division ring by the same kind of argument.
Published[AS95, Thm 1.2], reached through Bergman and Small–Warfield
Formalhilbert_linear_of_control (LinearBound.lean)
Same conclusion, dim⁡Rn≤cn\dim R_n\le cn. The paper proves it by Riemann–Roch on a curve; the formal proof by cutting words in a bounded window.
PublishedGeneric elements: one transcendental xx and a Vandermonde argument [S05, Lem 1]; K(X)K(X) [S06, Lem 1–2]
Formalnone
No counterpart: the formal proof stays over the base field.

Where capacity comes from

The closest relative we know of is J. J. Zhang’s lower transcendence degree [Z98], an invariant of division rings built on the same quantity and proposed as a route to this very gap. Astra’s reasoning summaries mention “lower transcendence” in the first minutes of the run. The argument also resembles Hamidoune’s isoperimetric method from additive combinatorics, which Lecouvey adapted to division rings [L14]. If you know how this route relates to the existing literature, we’d love to hear from you at jacob@vals.ai.

The run, broken down

By runtime

0 minutes94 minutes

Hover over a segment to see what Astra was doing.

By file

One dot per moment at which new declarations appeared in a file. Select a dot to open the file at that declaration. Hollow dots are files that were later deleted.

report: unsolvedgrader passesreport: solved
Growth
Degree
Hilbert
Ore
HomogeneousFractions
PolynomialModule
Commutative
Submission
Boundary
Frames
StableIntervals
Weighted
CoefficientGeneration
FrameIndex
Capacity
MaxCapacity
Cuts
Optimal
Controlled
LinearBound
0153045607590
minutes since the first command

References

[AS95]
M. Artin and J. T. Stafford, Noncommutative graded domains with quadratic growth, Invent. Math. 122 (1995), 231–276.
[KL00]
G. R. Krause and T. H. Lenagan, Growth of Algebras and Gelfand–Kirillov Dimension, revised edition, Graduate Studies in Mathematics 22, American Mathematical Society, 2000.
[L14]
C. Lecouvey, Plünnecke and Kneser type theorems for dimension estimates, Combinatorica (2014). arXiv:1109.0134
[S05]
A. Smoktunowicz, The Artin–Stafford gap theorem, Proc. Amer. Math. Soc. 133 (2005), 1925–1928.
[S06]
A. Smoktunowicz, There are no graded domains with GK dimension strictly between 2 and 3, Invent. Math. 164 (2006), 635–640. Springer
[SW84]
L. W. Small and R. B. Warfield Jr., Prime affine algebras of Gelfand–Kirillov dimension one, J. Algebra 91 (1984), 386–389.
[Z98]
J. J. Zhang, On lower transcendence degree, Adv. Math. 139 (1998), 157–193.