Math problems solved by AI

(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.

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.

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.

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.

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.

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.

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.

(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.

(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.

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.

(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.

(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.

(Record lower bound plus class-restricted ceilings; the existence and exact value of a finite universal constant remain open)

—

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: we present a seventeen-terminal common-point interval instance that certifies $$C\ \ge\ \frac{1282494797984843521}{10^{18}}=1.28249\ldots$$ Upper bounds: we prove the first unconditional upper bound below 2 for a nontrivial family of extremal cells, representing the class as a weighted two-permutation prefix system. We also prove additional structural results on the limits of techniques used for the lower bound. The ceilings apply to the common-point / two-order class from which the lower bounds are drawn, not to the universal constant $C$ itself.

Graph theory (automated conjecture)

(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.

(Infinite family of counterexamples; mathematical argument internally checked, with external verification and novelty review pending.)

Graph theory

Every finite connected simple graph G satisfies $$\alpha(G)\ge r(G)+\ln(\rho(G)),$$ where $\alpha(G)$ is the independence number, $r(G)$ is the radius, and $\rho(G)$ is the minimum number of pairwise vertex-disjoint paths whose vertices cover $V(G)$.

(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)$.

Spectral graph theory

Does every nontrivial finite simple graph have noninteger Sombor energy? If $\rho_1,\ldots,\rho_n$ are the eigenvalues of the Sombor matrix of a graph $G$, its Sombor energy is $$E_{\mathrm{SO}}(G)=\sum_{i=1}^{n}|\rho_i|.$$ The conjecture asserted that $E_{\mathrm{SO}}(G)\notin\mathbb Z$ for every nontrivial graph. A connected graph on nine vertices is exhibited with $E_{\mathrm{SO}}(G)=64$, disproving the conjecture.

(four record lower bounds; 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. New independent sets in strong graph powers give $\Theta(C_7) > 3.258020$, $\Theta(C_{11}) > 5.289773$, $\Theta(C_{13}) > 6.300109$ and $\Theta(C_{15}) > 7.301399$.

Spectral theory

Let $\mu$ be a probability measure on the unit circle with Verblunsky coefficients $\alpha$. Lukic conjectured that a weighted entropy condition with finitely many critical points is equivalent to a decomposition of $\alpha$ into components localized at those points. A counterexample with two critical points of multiplicity three refutes it: the sequence satisfies the decomposition conditions while the corresponding weighted entropy is $-\infty$.

Erdős #106 · Discrete Geometry, Packing

If $f(n)$ is the maximum total side length of $n$ interior-disjoint squares packed in the unit square, is $f(k^2 + 1) = k$? An exact rational configuration packs $17$ squares with total side length greater than $4$, refuting the identity at $k = 4$.

Quantum information

Is the irreversibility of entanglement manipulation robust in the strong-converse sense - a strict separation between the exponential strong-converse distillable entanglement and the entanglement cost, as conjectured by Lami and Regula? Yes: there are states for which any attempt to restore reversibility incurs an error growing exponentially in the number of copies, and the irreversibility persists even at polynomially growing error.

(New arXiv preprint with an author-provided Lean formalization; not yet peer-reviewed.)

Additive combinatorics

For every finite set $A\subset\mathbb Z$ with $|A|\ge 2$, define $$C(A)=\frac{\log\left(|A+A|/|A|\right)} {\log\left(|A-A|/|A|\right)}.$$ Determine the largest possible value of $C(A)$, equivalently the least universal exponent $c$ such that $$\frac{|A+A|}{|A|} \le \left(\frac{|A-A|}{|A|}\right)^c$$ for every such set $A$. The result proves that the supremum is exactly $2$, although no individual admissible set attains it.

Classical electrostatics

Do $n$ point charges whose electrostatic potential has only non-degenerate critical points always have at most $(n-1)^2$ of them? A configuration of five charges - three at the vertices of an equilateral triangle plus two small central charges pulled apart into a shallow bipyramid - has at least $24 > 16$ non-degenerate critical points, so the conjecture is false.