Amazing stuff! This is only the beginning!
"OpenAI released solutions to ten open problems in mathematics and theoretical computer science, generated by Astra, an internal unreleased model.
The problems span sphere packing, coding theory, group theory, and quantum complexity—each vetted by formal proofs in Lean.
Generating all ten solutions cost roughly $2,000 in compute at current API rates. The results include a disproof of Connes’s rigidity conjecture, new bounds on sphere-packing density, and a construction proving the existence of non-sofic groups. OpenAI framed the release carefully, noting that humans prepared the manuscripts but the mathematical arguments came from the system, a deliberate stance on authorship and attribution as AI systems edge into research collaboration."
From the abstract:
"We present a collection of results obtained by an internal OpenAI model, spanning mathematics and theoretical computer science:
1. High-dimensional sphere packing. The asymptotic strength of the Cohn–Elkies linear program is determined exactly. This gives an improved general packing bound in high dimensions and settles the corresponding Fourier sign-uncertainty problem asymptotically.
2. Binary and spherical codes. Classical upper bounds for fixed-distance binary and spherical codes are improved by exponential factors for all parameters. The spherical construction also recovers the sphere-packing exponent of Chapter 1.
3. Non-sofic groups. An explicit non-sofic group is constructed, resolving the question of whether every countable group admits finite permutation approximations. The argument uses property-(T) expanders and the binary Leavitt algebra.
4. Connes’s rigidity conjecture. Infinitely many pairwise nonisomorphic property-(T) groups are constructed with the same group von Neumann algebra, disproving Connes’s conjecture and answering a related finite-to-one question of Popa.
5. Arithmetic circuit complexity. For the permanent, division-free circuits require Ω(n2 log log n) gates, while formulas require Ω(n 4/ log n) leaves.
6. Quantum parallel repetition. Exponential parallel repetition is proved for every finite two-player entangled game, extending the classical repetition principle beyond previously treated special classes of quantum games.
7. Closest vector problem. A direct reduction from 3SAT gives n
1/400-factor hardness for the Euclidean closest vector problem, with related consequences for binary decoding and other lattice norms.
8. Ehrhart’s volume conjecture. The sharp bound (n + 1)n/n! is proved in every dimension for convex bodies whose barycenter is their only interior lattice point. 9. Multicolor Ramsey numbers. A superexponential lower bound proves Rk(3) = kΘ(k).
10. Compactness and degeneracy. Separate bipartite graph constructions disprove two conjectures in extremal graph theory: the compactness conjecture of Erdős and Simonovits and a degeneracy conjecture of Erdős."
Ten Advances in Mathematics and Theoretical Computer Science (open access, not peer reviewed, 249 pages)
No comments:
Post a Comment