On the Growth Factor of Random Matrices
https://arxiv.org/abs/2610.06785
Gaussian elimination is the oldest and most popular method for solving a linear system. Its numerical stability for a given matrix is controlled by the growth factor, a measure of how large entries can become during elimination. In this work, we prove a number of new results regarding the growth factor of random matrices. First, we provide tight estimates for the growth factor of a matrix preconditioned by a Haar orthogonal matrix without pivoting and characterize the asymptotic distribution of the growth factor of Gaussian matrices without pivoting. Second, and most notably, we prove that the growth factor of an \( n \times n \) Gaussian matrix under partial pivoting is rarely much larger than \( \sqrt{n} \), resolving an old conjecture of Nick Trefethen. The same techniques used to prove this conjecture also provide an improved smoothed analysis of the growth factor under partial pivoting.
Navier-Stokes lost in translation: Why Lean verification of AI autoformalisation does not guarantee correct natural language proofs
Alexander Bastounis, Fabian Circelli, Anders C. Hansen
https://arxiv.org/abs/2610.08144
Autoformalisation is increasingly used to verify mathematical texts, including those generated by AI, as in OpenAI’s announced proof of blow-up of solutions to the Navier-Stokes equations. In this process, an AI system translates the text from a natural language (NL) into a formal language such as Lean. Once this translation is done, the argument expressed in the formal language can easily be mechanically verified. The purpose of this article is to demonstrate why this process may offer no confidence in the original NL argument, owing to the various difficulties in performing the translation semantically faithfully. In particular, we highlight that the problem of resolving ambiguities in mathematical NL text, which is necessary in order to provide semantically faithful translation, is arbitrarily high up in the Solvability Complexity Index (SCI) hierarchy/arithmetical hierarchy (the SCI\( = \infty \)). Hence, informally, providing semantically faithful AI autoformalisation is harder than any computational problem including the Halting problem (which has SCI\( = 1 \)). To demonstrate the effect of this result we provide several examples of AI mistranslations of NL statements and proofs into Lean in practice, resulting in mismatches between NL proofs and their Lean `verifications’. These include OpenAI’s announced Navier-Stokes proof. In particular, we show that the formalised Lean proof does not correspond to the NL proof of blow-up of solutions to the Navier-Stokes equations.
Tight Bounds for Tusnády’s Problem in the Plane
Zhewei Wei（魏哲巍）
https://arxiv.org/abs/2610.08130
We show that the worst-case combinatorial discrepancy of n points in the plane with respect to axis-parallel rectangles is \( \Theta(\log^{3/2}n) \). The known bounds were \( \Omega(\log n) \) and \( O(\log^{3/2}n) \); we prove the matching lower bound. It holds for random point sets: for every \( A>0 \), there is a constant \( c_A>0 \) such that, with probability at least \( 1-e^{-An} \), every coloring of n independent uniform points in the unit square has an anchored rectangle with imbalance at least \( c_A(\log_2n)^{3/2} \).
The proof is surprisingly simple and elementary. It reveals one coordinate digit by digit. With overwhelming probability over the points, the conditional gains of an oscillation potential add up to \( \Omega(\log^{3/2}n) \) over \( \Theta(\log n) \) digits. Bounded differences control the fluctuations well enough for a union bound over all colorings.
Positive Sectional Curvature on All Smooth 7-spheres
Yang-Hui He, Ziran Liu, Shing-Tung Yau
We construct a smooth Riemannian metric with strictly positive sectional curvature on every smooth homotopy seven-sphere. For each smooth structure, we construct positively curved metrics on two seven-dimensional disks whose induced boundary metrics agree under the prescribed attaching map. Under this identification, a gluing theorem then yields the required smooth metric on the closed manifold. The construction applies to all 28 oriented diffeomorphism classes.