VibeMathedMath problems solved with AI
Sign in

A uniform bound of three on generalized star height (the generalized star-height problem)

A generalized regular expression over a finite alphabet Σ\Sigma is built from 00, 11 and letters by union, concatenation, complement in Σ∗\Sigma^* and Kleene star; its height is the nesting depth of stars, and h(L)h(L) is the least height of an expression for a regular language LL. Without complement, star height is unbounded (Eggan; Dejean-Schutzenberger). With complement, height zero is exactly the star-free languages (Schutzenberger), height at most one was known for languages recognized by abelian groups, nilpotent groups of class two and some semigroups (Pin-Straubing-Therien, Bourne-Ruskuc), and no language of generalized height above one is known. Straubing distinguishes two questions: does one height bound serve for all regular languages, and does height one always suffice? Is there a uniform bound on generalized star height, and is it one?

Result
Proved(see note)
Status
Partial result
AI contribution
AI-discovered
Method
Argument
Field
Automata and formal languages; regular expressions
Posed by
The generalized star-height problem, as named by Pin, Straubing and Therien (1992); the uniform-boundedness form distinguished by Straubing (LATIN 2002, p. 537)
Year posed
—
Years open
—
Solved
2026-09-25
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
30 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Claims Theorem 1.1: for every finite alphabet Σ\Sigma and every regular L⊆Σ∗L\subseteq\Sigma^*, h(L)≤3h(L)\le3, using expressions over Σ\Sigma itself with complement in Σ∗\Sigma^*. Companions prove the weaker bounds 13 and 4 by different constructions. It does NOT exhibit any language of generalized star height greater than one, does not decide whether height one always suffices, gives no algorithm for computing h(L)h(L), and bounds neither expression size nor running time.

What the AI did

The release README says the manuscripts were produced by an unreleased internal OpenAI model, the vast majority by one fixed procedure using on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier results produced by the models. Its named exceptions to that procedure (the zeta zero-free region work, whose Re(s) > 11/12 write-up was human edited, and the Hodge conjecture for CM abelian varieties) do not concern this family. All three manuscripts of the family (bounds 13, 4 and 3, all dated 25 September 2026) are credited to OpenAI with no human author named; each states that it gives its own complete proof by a different construction.

Verification

No independent mathematician has checked this yet. Theorem 1.1 of the principal manuscript (h(L)≤3h(L)\le3 for every regular LL over every finite alphabet, complement in the same free monoid) was read against the problem: it answers uniform boundedness and leaves open whether height one suffices, as the paper says. The Lean challenge ComparatorChallenges/GeneralizedStarHeight.json (theorem OAI.GeneralizedStarHeight.main, solution module OAI.Computability.StarHeight.Main, present at the pinned commit) is not in the formalization catalogue formalization.yaml; it was found through lean/docs/134.md. Its statement was read here: an inductive expression type with zero, one, letters, union, concatenation, complement and star, height as defined in the paper, and for a finite alphabet every regular language (Mathlib's IsRegular) is the language of some expression of height at most three. That is the headline claim. Permitted axioms are propext, Quot.sound and Classical.choice. Not rebuilt here.

Sources

Changelog1 change

Discussion