Math problems solved by AI

(one construction disproves both the product conjecture and its weak form)

Extremal graph theory

Simonovits conjectured that if a forbidden family $\mathcal{F}$ with $p(\mathcal{F}) > 1$ has extremal number exceeding the Turan bound by a superlinear surplus, then its extremal graphs are joins of $p$ graphs, each extremal for a family of chromatic number two. Disproved by a fixed finite family $\mathcal{L}$ with $p(\mathcal{L}) = 2$ and $\mathrm{ex}(n,\mathcal{L}) > t_2(n) + cn^{3/2}$ that nevertheless has, at every large order, an extremal graph with connected complement and hence no nontrivial join decomposition. The same construction disproves the Weak Product Conjecture of Furedi and Simonovits.

(The Formal Conjectures pull request flipping this from open to solved is still open rather than merged, so the canonical repository has not yet accepted it.)

Graph Theory (automated conjecture)

For every finite connected simple graph $G$, is the order of the largest induced tree at least $\mathrm{girth}(G) - 1 + \mathrm{ecc}(G, \mathrm{center}(G))$, where the last term is the eccentricity of the centre set? Answered affirmatively, with a Lean proof.

Randomized algorithms

Does two-terminal reliability, the probability that $s$ still reaches $t$ when edges fail independently, admit a fully polynomial-time randomised approximation scheme? Asked explicitly in Kannan's 1994 survey and left open while the all-terminal cases were settled by Karger and by Guo and Jerrum. Answered positively for general graphs, both directed and undirected. The complementary unreliability question is shown to be BIS-hard, so it is unlikely to admit one.

(The formalization proves the statement under the weaker hypothesis n >= 2; the pull request marking the conjecture solved is open, not merged)

Graph theory (automated conjecture)

Let $G$ be a simple connected graph on $n\geq 5$ vertices. If the maximum over all vertices $v$ of $\ell(v)$ - the independence number of the subgraph induced by the open neighborhood $N(v)$ - is at most $1$, must $G$ be well totally dominated? Answered affirmatively; the Lean proof in fact needs only $n\geq 2$, and retains the conjecture's $n\geq 5$ to state the source faithfully.

(the equality case; the inequality was settled separately and is tracked on its own entry)

Convex geometry

Ehrhart conjectured that a full-dimensional compact convex body in $\mathbb{R}^n$ whose barycenter is its unique interior lattice point has volume at most $(n+1)^n/n!$. With the inequality itself settled, the remaining question was which bodies attain it. Every such body is a unimodular image of the simplex $(n+1)\Delta_n - (1,\dots,1)$.

(Claimed in a self-published research draft; a standalone by-product is the transcendence of the integral of exp(q) between distinct algebraic endpoints for nonconstant algebraic q)

Commutative Algebra, Transcendence

Let $\mathcal{L}(x^{a}y^{b})=a!\,b!$ on $\mathbb{C}[x,y]$. The Factorial Conjecture asks whether $\mathcal{L}(f^{m})=0$ for every $m\geq 1$ forces $f=0$. The homogeneous two-variable case was settled by Liu and Sun; the inhomogeneous problem does not reduce to it, because radial integration couples the homogeneous layers through Gamma factors. A claimed proof settles the full two-variable case affirmatively.

Convex geometry

What is the maximum volume of a convex body in $\mathbb{R}^n$ whose centroid is its only interior lattice point? Ehrhart conjectured the extremal value in 1964; the sharp maximum is now determined in every dimension.

Algebraic combinatorics

Monical, Tokcan and Yong conjectured that Schubitopes, the generalized permutahedra arising as Newton polytopes of Schubert polynomials and of Demazure characters of $\mathrm{GL}_n$, are Ehrhart positive. Disproved by an explicit Schubitope whose Ehrhart polynomial has a negative coefficient in its monomial expansion.

(upper bounds reach the Cohn-Elkies threshold; the true asymptotic density remains open)

Discrete geometry

How dense can a sphere packing in $\mathbb{R}^n$ be as $n \to \infty$? The Kabatiansky-Levenshtein upper bound stood for almost fifty years; the new proof improves the asymptotic upper bound all the way down to the Cohn-Elkies linear-programming threshold.

Erdős #180 · Extremal graph theory

For every finite family $\mathcal{F}$ of graphs, is there a single $G \in \mathcal{F}$ with $\mathrm{ex}(n;G) \ll_{\mathcal{F}} \mathrm{ex}(n;\mathcal{F})$? A counterexample refutes the Erdős-Simonovits compactness conjecture.

Erdős #183 · Ramsey theory

Let $R(3;k)$ be the least $n$ such that every $k$-colouring of the edges of $K_n$ contains a monochromatic triangle. Determine $\lim_{k\to\infty} R(3;k)^{1/k}$ (a \$250 Erdős prize problem). A superexponential lower bound resolves the problem: the limit is infinite.

(an n^4/log n formula lower bound; VP vs VNP remains wide open)

Algebraic complexity

How large must arithmetic circuits and formulas computing the $n \times n$ permanent be? New lower bounds include an arithmetic-formula bound of order $n^4/\log n$, far beyond the quadratic barrier that stood for decades.

Quantum complexity

Does the value of a two-player quantum game decay exponentially under parallel repetition, as Raz's theorem gives for classical games? Yes: an exponential parallel repetition theorem holds for arbitrary finite two-player quantum games.

Operator algebras

Are ICC property (T) groups remembered by their von Neumann algebras - if $L(\Gamma) \cong L(\Lambda)$ for such groups, must $\Gamma \cong \Lambda$? A counterexample refutes Connes' conjecture that these groups are uniquely determined by their group von Neumann algebras.

Lattices & cryptography

Is the closest vector problem NP-hard to approximate within polynomial factors $n^c$? Yes for some $c > 0$: hardness of approximation reaches polynomial factors, with consequences for decoding and related lattice problems - a foundational question underpinning post-quantum cryptography where hardness had stalled at almost-polynomial factors since the late 1990s.

(exponential improvement over the 1977 MRRW bounds; the exact rate-distance trade-off remains open)

Coding theory

What is the maximum size of a binary code of given minimum distance? The linear-programming bounds of McEliece, Rodemich, Rumsey and Welch (1977) resisted improvement for half a century. The new upper bounds are exponentially stronger at every prescribed distance, with analogous results for high-dimensional spherical codes.

(answered no: non-sofic groups exist)

Geometric group theory

Is every group sofic - does every group admit approximate finite permutation representations? A central open question of geometric group theory since Gromov introduced soficity: soficity implies Gottschalk's surjunctivity conjecture, Kaplansky's stable finiteness and more, and no non-sofic group was known. An explicit construction now establishes that non-sofic groups exist.

Erdős #146 · Extremal graph theory

If $H$ is bipartite and $r$-degenerate, is $\mathrm{ex}(n;H) \ll n^{2-1/r}$ (a \$500 Erdős-Simonovits prize conjecture)? A counterexample refutes the degeneracy conjecture.

(The ball case. For arbitrary domains Pólya's conjecture remains open; this continues the authors' programme after the planar disk, circular sectors, and the Dirichlet case in arbitrary dimensions.)

Spectral Geometry, Laplace Eigenvalues

Pólya conjectured in 1954 that the Weyl-law expression bounds the eigenvalue counting function of the Laplacian. The paper proves the Neumann case for Euclidean balls in dimensions three and higher, extending the authors' earlier planar and Dirichlet results. Key difficulty: estimating zeros of derivatives of ultraspherical Bessel functions rather than of Bessel functions themselves.

(record lower bounds for seven odd cycles; the exact capacities remain open for every odd cycle beyond C5)

Zero-error information theory

Determine the Shannon capacities of odd cycles beyond $C_5$, or improve the best explicit bounds. Lovasz's theta function settled $C_5$ in 1979 and every longer odd cycle has stayed open since. The current records, all obtained with model assistance and formally verified, are $\Theta(C_7) \ge 3.258805369885$, $\Theta(C_{11}) \ge 5.294502522149$, $\Theta(C_{13}) \ge 6.302455083464$, $\Theta(C_{15}) \ge 7.301600534487$, $\Theta(C_{19}) \ge 9.357192705918$, $\Theta(C_{21}) \ge 10.342455853338$ and $\Theta(C_{23}) \ge 11.328224257774$.

(Record lower bound only. The sub-2 ceiling is the codimension-two case and does not bound the record ladder (k=17 has complement mass 11). 4/3 and 2 are conjectures; the proved gap is [1.28249, 2].)

—

For a single-source unsplittable flow, find the optimal universal additive constant $C$ s.t. every feasible fractional flow $x$ with arc costs $c$ should admit an unsplittable routing $y$ with $c^\top y \le c^\top x$ and $y_a \le x_a + C \cdot d_{\max}$ on every arc. Goemans conjectured $C=1$; this was disproved in July 2026 by a separate seven-vertex counterexample with critical constant $16/15$ (see the Dinitz–Garg–Goemans entry), leaving the optimal $C$ open. Lower bound: a seventeen-terminal common-point interval instance certifies $$C\ \ge\ \frac{1282494797984843521}{10^{18}}=1.28249\ldots$$ Upper bounds: the paper proves the first unconditional ceiling below 2, but for the codimension-two case only, at complement mass $q=2$. The record cells lie outside it, the $k=17$ instance having $q=11$, so that ceiling does not bound the record ladder. Two figures are conjectures rather than results: $4/3$ as the supremum of critical constants over common-point cells, approached but not attained and not an extrapolation from the ladder (Conjecture 1.1, Theorem 5.1), and $2$ for the universal constant itself (Conjecture 1.2). The proved gap remains $[1.28249\ldots,\ 2]$.

Commutative Algebra, Local Cohomology

Can a noetherian ring have a local cohomology module whose support is not closed - equivalently, one with infinitely many minimal primes? Huneke and Lyubeznik asked; the paper constructs such rings, so the answer is yes.

(no constant-bound repair of the conjecture is possible)

Spectral graph theory

Is the difference between the numbers of positive and negative adjacency eigenvalues of every connected line graph at most one? A $14$-vertex witness has signature $2$, and chaining copies gives connected line graphs of signature $k + 1$ for every $k \ge 1$ - the signature is unbounded.

Graph theory (automated conjecture)

(leading asymptotic determined up to a bounded q-dependent term)

Function-field arithmetic

Let $D_q(n)$ be the largest possible least degree of a polynomial omitted by a non-covering family of $n$ distinct-modulus congruence classes in $\mathbb{F}_q[x]$. What is its asymptotic size? The answer is $D_q(n) = \frac{n}{q-1} + O_q(1)$.