Zarankiewicz's crossing-number conjecture (Turan's brick factory problem)

Turan's brick factory problem (1944) asks for the least number of crossings in a plane drawing of the complete bipartite graph $K_{m,n}$ , crossings counted as points with edges drawn as simple arcs. Zarankiewicz (1954/55) gave a drawing with $\lfloor\frac m2\rfloor\lfloor\frac{m-1}2\rfloor\lfloor\frac n2\rfloor\lfloor\frac{n-1}2\rfloor$ crossings and a proof of optimality that turned out to contain a gap, leaving the formula as a conjecture. Kleitman proved it when $\min(m,n)\le6$ , Woodall checked $K_{7,7}$ and $K_{7,9}$ , and flag algebras gave about $0.91$ of the value asymptotically. Is $\mathrm{cr}(K_{m,n})=\lfloor\frac m2\rfloor\lfloor\frac{m-1}2\rfloor\lfloor\frac n2\rfloor\lfloor\frac{n-1}2\rfloor$ for all positive $m,n$ ?

Result: Proved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Argument
Field: Topological graph theory; crossing numbers
Posed by: Paul Turan (brick factory problem, 1944, recounted in 1977); formula and flawed proof by Kazimierz Zarankiewicz (Fund. Math. 41, 1954/55)
Year posed: 1944
Years open: 82y
Solved: 2026-09-23
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Lean-checked, statement unaudited
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 55 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Claims $\mathrm{cr}(K_{m,n})=\lfloor\frac m2\rfloor\lfloor\frac{m-1}2\rfloor\lfloor\frac n2\rfloor\lfloor\frac{n-1}2\rfloor$ for all positive $m,n$ . The lower bound comes from a linear-algebra inequality $\sum_{i,j}\dim(U_i\cap V_j)\le\lfloor m^2/4\rfloor N$ for subspaces with $U_i\cap V_i=0$ , proved by interpolation, applied through signed intersections of cycles; Zarankiewicz's drawing gives the upper bound. Crossings are counted as points. It does NOT address rectilinear, pair or odd crossing numbers of $K_{m,n}$ .

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 Hodge conjecture for CM abelian varieties and the zeta zero-free region work) do not concern this family. The manuscript is credited to OpenAI with no human author named.

Verification

No independent mathematician has checked this yet. Theorem 1.1 was read against the posed problem: $\mathrm{cr}(K_{m,n})=d_md_n$ with $d_r=\lfloor r/2\rfloor\lfloor(r-1)/2\rfloor$ for all positive $m,n$ , ordinary point count, unrestricted drawings. formalization.yaml lists OAI.Zarankiewicz.mainTarget_proof (comparator BipartiteCrossing) as the main result. Its statement MainTarget says that for all $m,n>0$ some admissible drawing of $K_{m,n}$ has exactly $d_md_n$ crossing points and every admissible drawing has at least that many, with the same admissibility conditions as the complete-graph file (simple continuous arcs, finitely many proper crossings, no triple points). That is the headline claim. Permitted axioms are propext, Quot.sound and Classical.choice. Not rebuilt here. Hebbar and Mangam (2018, Int. J. Eng. Technol.) published earlier claims of both formulas, which the manuscripts cite and treat as upper-bound constructions only.

Zarankiewicz's crossing-number conjecture (Turan's brick factory problem)

What was actually shown

What the AI did

Verification

Sources

Discussion