Paper deep dive
Global Convergence of Multiplicative Updates for the Matrix Mechanism: A Collaborative Proof with Gemini 3
Keith Rush
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/23/2026, 12:05:08 PM
Summary
This paper proves the global convergence of a multiplicative update iteration for a regularized nuclear norm objective function, which arises in the context of the matrix mechanism for private machine learning. The author demonstrates that the iteration satisfies a monotonic ascent property, ensuring convergence to a unique global optimizer, and highlights the collaborative role of the AI model Gemini 3 in identifying the key variational characterization required for the proof.
Entities (5)
Relation Signals (3)
Keith Rush → collaboratedwith → Gemini 3
confidence 100% · The bulk of this proof was provided by Gemini 3... Gemini 3 also sketched the initial version of this note.
Gemini 3 → contributedto → Global Convergence of Multiplicative Updates for the Matrix Mechanism
confidence 100% · Gemini 3 made me aware of the representation Lemma 1, and sketched the major steps of this proof.
Majorization-Minimization → usedtoprove → Global Convergence of Multiplicative Updates for the Matrix Mechanism
confidence 95% · we employ the Majorization-Minimization (MM) principle by constructing a variational surrogate function
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We analyze a fixed-point iteration $v \leftarrow \phi(v)$ arising in the optimization of a regularized nuclear norm objective involving the Hadamard product structure, posed in~\cite{denisov} in the context of an optimization problem over the space of algorithms in private machine learning. We prove that the iteration $v^{(k+1)} = \text{diag}((D_{v^{(k)}}^{1/2} M D_{v^{(k)}}^{1/2})^{1/2})$ converges monotonically to the unique global optimizer of the potential function $J(v) = 2 \text{Tr}((D_v^{1/2} M D_v^{1/2})^{1/2}) - \sum v_i$, closing a problem left open there. The bulk of this proof was provided by Gemini 3, subject to some corrections and interventions. Gemini 3 also sketched the initial version of this note. Thus, it represents as much a commentary on the practical use of AI in mathematics as it represents the closure of a small gap in the literature. As such, we include a small narrative description of the prompting process, and some resulting principles for working with AI to prove mathematics.
Tags
Links
- Source: https://arxiv.org/abs/2603.19465v1
- Canonical: https://arxiv.org/abs/2603.19465v1
Trouble viewing inline? Open PDF directly →
Full Text
37,299 characters extracted from source content.
Expand or collapse full text
Global Convergence of Multiplicative Updates for the Matrix Mechanism: A Collaborative Proof with Gemini 3. Keith Rush Google DeepMind Abstract We analyze a fixed-point iteration v←ϕ(v)v←φ(v) arising in the optimization of a regularized nuclear norm objective involving the Hadamard product structure, posed in [DMR+22] in the context of an optimization problem over the space of algorithms in private machine learning. We prove that the iteration v(k+1)=diag((Dv(k)1/2MDv(k)1/2)1/2)v^(k+1)=diag((D_v^(k)^1/2MD_v^(k)^1/2)^1/2) converges monotonically to the unique global optimizer of the potential function J(v)=2Tr((Dv1/2MDv1/2)1/2)−∑viJ(v)=2Tr((D_v^1/2MD_v^1/2)^1/2)-Σ v_i, closing a problem left open there. The bulk of this proof was provided by Gemini 3, subject to some corrections and interventions. Gemini 3 also sketched the initial version of this note. Thus, it represents as much a commentary on the practical use of AI in mathematics as it represents the closure of a small gap in the literature. As such, we include a small narrative description of the prompting process, and some resulting principles for working with AI to prove mathematics. 1 The Problem and its Brief History We consider the problem of finding the fixed point v∗∈ℝ++Nv^* _++^N satisfying the equation: v∗=diag((Dv∗1/2MDv∗1/2)1/2)v^*=diag ( (D_v^*^1/2MD_v^*^1/2 )^1/2 ) (1) where M∈ℝN×NM ^N× N is a symmetric positive definite matrix (M≻0M 0), and Dv=diag(v)D_v=diag(v). This fixed-point equation arises naturally as the stationarity condition (∇J(v)=0∇ J(v)=0) for the potential function J:ℝ++N→ℝJ:R_++^N : J(v)=2Tr((Dv1/2MDv1/2)1/2)−∑i=1NviJ(v)=2Tr ( (D_v^1/2MD_v^1/2 )^1/2 )- _i=1^Nv_i (2) To our knowledge, the first occurrence of this potential can be found in [DMR+22], where it arose in the context of designing matrix factorizations that are in some sense optimal for the matrix mechanism [LMH+15] under a specific notion of error. [DMR+22] was able to show that iterating the mapping Eq.˜1 converged locally, and provided empirical evidence that this fixed-point iteration converged extremely rapidly, outpacing pure gradient-based approaches, but global convergence of these iterates was left open. The followup papers in the series of [DMR+22] (see the literature review in [PUC+25]) generally moved away from the unconstrained optimization problem that yields the potential Eq.˜2, in order to impose structural constraints on matrices which address practical concerns like runtime efficiency and ability to prove privacy amplification results. The specification of the BLT class [DMP+24] providing the ability to compute near-optimal factorizations with complexity independent of matrix size rendered the convergence of the iterates of Eq.˜1 even more academic. Still, I always viewed it as unsatisfactory that we were unable to prove global convergence despite reasonably serious attempts by reasonably serious mathematicians. This global convergence always had the feel to me of something which was just an issue of putting together the right tools, which probably all existed. I therefore kept it in my back pocket, and tested it repeatedly on new versions of various AI models as they were released. Given my affiliation, most of these attempts used Gemini. With a few iterations, Gemini 3 was able to identify the crucial piece that we had missed: a variational characterization of the nuclear norm that allows the problem to be diagonalized. This diagonalization of our crucial object essentially required the ability to call certain linear algebra to hand that neither myself nor my collaborators demonstrated, but it was not exactly revolutionary. This is not unreasonable – mathematics is quite large, and not every mathematician can recall every inequality or characterization of an object under study, particularly if this object is far from their main field. We hope that this note can serve as a small example of utilization of AI in mathematics, echoing several that have appeared elsewhere in the literature, and also represent the closure of a problem that had always nagged me. We study the convergence of the parameter-free multiplicative update rule: v(k+1)=ϕ(v(k))=diag((Dv(k)1/2MDv(k)1/2)1/2)v^(k+1)=φ(v^(k))=diag ( (D_v^(k)^1/2MD_v^(k)^1/2 )^1/2 ) (3) Our main contribution is a proof that this iteration satisfies the monotonic ascent property J(v(k+1))≥J(v(k))J(v^(k+1))≥ J(v^(k)), ensuring global convergence to the unique maximum. We also include discussion of the experience of working interactively with natural-language AI models to produce nontrivial mathematics. 2 Theoretical Analysis 2.1 Basic Properties The result here depends critically on a representation of the first term in our potential as the nuclear norm of a matrix, and a particular variational characterization for this norm. Definition 1 (Nuclear Norm). For any real matrix A, define the nuclear norm ‖A‖∗\|A\|_* as: ‖A‖∗=Tr((A⊤A)1/2)\|A\|_*=Tr((A A)^1/2) We will collect the properties of the nuclear norm that we need before we begin. Lemma 1. For any real A, the nuclear norm can be characterized in the following manner: ‖A‖∗=supU∈(N)Tr(U⊤A)\|A\|_*= _U (N)Tr(U A) where (N)U(N) is the set of unitary matrices. The supremum is attained when U is the unitary factor from the polar decomposition of A (see Section 7.4 of [HJ90]). Proof. We recall the polar factorization of A, the representation A=UPA=UP where P=(A⊤A)1/2P=(A A)^1/2 and U is unitary. (Since A is real, U is in fact orthogonal). Therefore U⊤A=PU A=P, and: ‖A‖∗=Tr((A⊤A)1/2)=Tr(P)=Tr(U⊤A).\|A\|_*=Tr ((A A)^1/2 )=Tr(P)=Tr(U A). This shows that ‖A‖∗≥supU∈(N)Tr(U⊤A)\|A\|_*≥ _U (N)Tr(U A). The reverse inequality follows from the Von Neumann trace inequality; for O unitary, its singular values are of absolute value 1, and therefore |Tr(O⊤A)|≤∑|ωiαi|=∑|αi|=Tr((A⊤A)1/2)|Tr(O A)|≤Σ| _i _i|=Σ| _i|=Tr ((A A)^1/2 ) ∎ Lemma 2 (Strict Concavity). For a symmetric positive definite matrix M≻0M 0, the potential function J(v)=2Tr((Dv1/2MDv1/2)1/2)−∑i=1NviJ(v)=2Tr ( (D_v^1/2MD_v^1/2 )^1/2 )- _i=1^Nv_i is strictly concave on the positive orthant ℝ++NR_++^N. Proof. For any matrices A and B, ABAB and BABA share the same non-zero eigenvalues (this is [HJ90], Theorem 1.3.22). Let A=Dv1/2M1/2A=D_v^1/2M^1/2 and B=M1/2Dv1/2B=M^1/2D_v^1/2. As ABAB and BABA share eigenvalues, the trace of their square roots is identical: Tr((Dv1/2MDv1/2)1/2)=Tr((M1/2DvM1/2)1/2)Tr ((D_v^1/2MD_v^1/2)^1/2 )=Tr ((M^1/2D_vM^1/2)^1/2 ) Since the mapping v↦M1/2DvM1/2v M^1/2D_vM^1/2 is linear in v and injective, Lieb’s concavity theorem ([LIE73]) combined with concavity for a composition of an injective linear map with a concave map finish the proof. ∎ Lemma 3 (Coercivity). The potential function J(v)J(v) is coercive on ℝ+NR_+^N in the sense that J(v)→−∞J(v)→-∞ as ‖v‖1→∞ v _1→∞. Proof. Let A=Dv1/2MDv1/2A=D_v^1/2MD_v^1/2. Note that Tr(A1/2)Tr(A^1/2) is the nuclear norm of Dv1/2M1/2D_v^1/2M^1/2. By the relationship between the nuclear norm and the Frobenius norm, Tr(A1/2)≤NTr(A)Tr(A^1/2)≤ NTr(A). We have: Tr(A)=Tr(Dv1/2MDv1/2)=Tr(MDv)=∑i=1NMiivi≤maxi(Mii)‖v‖1Tr(A)=Tr(D_v^1/2MD_v^1/2)=Tr(MD_v)= _i=1^NM_iv_i≤ _i(M_i) v _1 Thus, J(v)≤2Nmaxi(Mii)‖v‖1−‖v‖1J(v)≤ 2 N _i(M_i) v _1- v _1. As ‖v‖1→∞ v _1→∞, the linear term dominates the square-root term, hence J(v)→−∞J(v)→-∞. This, combined with strict concavity and the fact that J(v)J(v) is bounded at the boundary ∂ℝ+N _+^N, ensures the existence of a unique maximizer v∗∈ℝ++Nv^* _++^N. ∎ Lemma 4 (Positive Invariance). If v(k)∈ℝ++Nv^(k) _++^N and M≻0M 0, then v(k+1)=ϕ(v(k))∈ℝ++Nv^(k+1)=φ(v^(k)) _++^N. Proof. Let X=Dv(k)1/2MDv(k)1/2X=D_v^(k)^1/2MD_v^(k)^1/2. Since v(k)>0v^(k)>0 element-wise, Dv(k)1/2D_v^(k)^1/2 is a non-singular diagonal matrix. Because M≻0M 0, the congruence transformation X is also symmetric positive definite (X≻0X 0). The unique positive definite square root X1/2X^1/2 is also strictly positive definite. Since the diagonal entries of any strictly positive definite matrix are strictly positive, vi(k+1)=[X1/2]ii>0v^(k+1)_i=[X^1/2]_i>0 for all i. ∎ Counterintuitive as it may seem given its triviality, we will begin by analyzing the scalar case. Surprisingly, using the nuclear norm representation above, we will be able to, in effect, reduce to it. 2.2 The Scalar Case (N=1N=1) To build intuition, we first analyze the scalar case where M=1M=1 and Dv=xD_v=x. The potential simplifies to J(x)=2x−xJ(x)=2 x-x. The update rule is xnew=x_new= x. Let ΔJ=J(xnew)−J(x) J=J(x_new)-J(x). Substituting xnew=x1/2x_new=x^1/2: ΔJ J =(2x1/4−x1/2)−(2x1/2−x) =(2x^1/4-x^1/2)-(2x^1/2-x) =2x1/4−3x1/2+x =2x^1/4-3x^1/2+x To analyze the sign of ΔJ J, we perform a change of variables x=z4x=z^4 (with z>0z>0). This transforms the expression into a polynomial in z: ΔJ(z)=z4−3z2+2z J(z)=z^4-3z^2+2z (4) By inspecting the root at z=1z=1 (the fixed point), we can factorize the polynomial: ΔJ(z)=z(z−1)2(z+2) J(z)=z(z-1)^2(z+2) (5) Since z>0z>0, we have z>0z>0, (z−1)2≥0(z-1)^2≥ 0, and (z+2)>0(z+2)>0. Thus, ΔJ≥0 J≥ 0, with equality if and only if z=1z=1 (x=1x=1). This factorization confirms unconditional monotonicity for the scalar case. 2.3 The Matrix Case Theorem 1. For positive-definite M, the algorithm defined by iterating the map ϕφ, ϕ(v)=diag((Dv1/2MDv1/2)1/2),φ(v)=diag ( (D_v^1/2MD_v^1/2 )^1/2 ), (6) converges to the unique fixed point of ϕφ for any initialization in ℝ++nR^n_++. Proof. In the general matrix case, DvD_v and M do not commute. Consequently, we cannot apply the scalar polynomial factorization directly to the eigenvalues. Note that the fixed point of ϕφ is exactly the maximizer of the potential Eq.˜2. To prove convergence of the iterates of ϕφ, we employ the Majorization-Minimization (M) principle by constructing a variational surrogate function: we will show that this surrogate function lower bounds the potential J, and iterating ϕφ makes strict progress on this surrogate function every step, and thus that the iterates make monotonic progress on the potential. Elementary analysis allows us to conclude that the iterates indeed converge to v∗v^*: given coercivity, since we stay away from the boundary (IE, no vi→0v_i→ 0 under this iteration, as can be shown simply), we can extract a subsequence which converges to a limit point, but this could be nothing but a fixed point. And monotonic ascent tells us that we cannot leave a neighborhood once we have entered it. Alternatively, we may invoke Zangwill’s theorem [ZAN69] to conclude. Thus we proceed with the M framework. 2.3.1 Step 1: Construction of the Minorizer (Surrogate Function) Let A(v)=M1/2Dv1/2A(v)=M^1/2D_v^1/2. By Lemma˜1, the first term of our potential is: 2Tr((Dv1/2MDv1/2)1/2)=2‖M1/2Dv1/2‖∗=supU∈(N)2Tr(U⊤M1/2Dv1/2)2Tr ((D_v^1/2MD_v^1/2)^1/2 )=2\|M^1/2D_v^1/2\|_*= _U (N)2Tr (U M^1/2D_v^1/2 ) (7) Let v(k)v^(k) be the current iterate. Define the matrix Ak=M1/2Dv(k)1/2A_k=M^1/2D_v^(k)^1/2. We compute the polar decomposition Ak=UkPkA_k=U_kP_k, where Pk=(Ak⊤Ak)1/2P_k=(A_k A_k)^1/2 is positive semidefinite and UkU_k is unitary. Note that strictly UkU_k aligns the singular vectors; implicitly this solves the variational problem supUTr(U⊤Ak) _UTr(U A_k). We define the surrogate function G(v;v(k))G(v;v^(k)) by fixing the unitary UkU_k: G(v;v(k))=2Tr(Uk⊤M1/2Dv1/2)−∑i=1NviG(v;v^(k))=2Tr (U_k M^1/2D_v^1/2 )- _i=1^Nv_i (8) Properties of the Surrogate: 1. Lower Bound: By the variational definition of the nuclear norm, J(v)≥G(v;v(k))J(v)≥ G(v;v^(k)) for all v. 2. Tightness (Value Match): At v=v(k)v=v^(k), the optimal unitary for the variational form is precisely UkU_k. Thus, J(v(k))=G(v(k);v(k))J(v^(k))=G(v^(k);v^(k)). 3. Tangency (Gradient Match): We verify that the surrogate shares the same first-order behavior as the objective at v(k)v^(k). The gradient of the original potential J(v)J(v) is: ∇J(v)=diag((Dv1/2MDv1/2)1/2)⊘v−∇ J(v)=diag ((D_v^1/2MD_v^1/2)^1/2 ) v-1 (9) At v(k)v^(k), note that (Dv(k)1/2MDv(k)1/2)1/2=(Ak⊤Ak)1/2=Pk(D_v^(k)^1/2MD_v^(k)^1/2)^1/2=(A_k A_k)^1/2=P_k. Using the polar decomposition Pk=Uk⊤AkP_k=U_k A_k: ∇J(v(k))=diag(Uk⊤Ak)⊘v(k)−∇ J(v^(k))=diag(U_k A_k) v^(k)-1 (10) Now, consider the gradient of the surrogate G(v;v(k))G(v;v^(k)). The trace term is linear in Dv1/2D_v^1/2: 2Tr(Uk⊤M1/2Dv1/2)=2∑i[Uk⊤M1/2]iivi2Tr(U_k M^1/2D_v^1/2)=2 _i[U_k M^1/2]_i v_i (11) The gradient with respect to viv_i is: ∂G∂vi=[Uk⊤M1/2]iivi−1 ∂ G∂ v_i= [U_k M^1/2]_i v_i-1 (12) Evaluating at v(k)v^(k), we substitute [Uk⊤M1/2]ii[U_k M^1/2]_i back into matrix form. Note that, as Ak=M1/2Dv(k)1/2A_k=M^1/2D_v^(k)^1/2, we have diag(Uk⊤Ak)i=[Uk⊤M1/2]iivi(k)diag(U_k A_k)_i=[U_k M^1/2]_i v_i^(k). Thus: ∇G(v(k);v(k))=diag(Uk⊤Ak)v(k)⊙v(k)−=∇J(v(k))∇ G(v^(k);v^(k))= diag(U_k A_k) v^(k) v^(k)-1=∇ J(v^(k)) (13) This confirms v(k)v^(k) is a valid touch-point for Majorization-Minimization. 2.3.2 Step 2: Monotonic Ascent via the Surrogate To prove monotonic ascent, we analyze the behavior of the surrogate function constructed in the previous step. Recall that the surrogate, constructed by freezing the unitary UkU_k from the polar decomposition of M1/2Dv(k)1/2M^1/2D_v^(k)^1/2, is given by: G(v;v(k))=∑i=1N(2civi−vi)G(v;v^(k))= _i=1^N (2c_i v_i-v_i ) (14) where the coefficients are ci=[Uk⊤M1/2]iic_i= [U_k M^1/2 ]_i. The Surrogate Maximizer vs. The Algorithm Update. The global maximizer of this separable surrogate, denoted voptv^opt, is found by setting the derivative to zero: ∂G∂vi=civi−1=0⟹viopt=ci2 ∂ G∂ v_i= c_i v_i-1=0 v_i^opt=c_i^2 (15) However, we must verify how this relates to our actual fixed-point update ϕ(v(k))φ(v^(k)). The gradient of the true potential J(v)J(v) at v(k)v^(k) is given by ∇J(v)=ϕ(v)⊘v−∇ J(v)=φ(v) v-1. The gradient of the surrogate G(v)G(v) at v(k)v^(k) is ∇G(v)=c⊘v−∇ G(v)=c v-1. By the tangency condition above, ∇J(v(k))=∇G(v(k);v(k))∇ J(v^(k))=∇ G(v^(k);v^(k)). Equating the terms reveals the explicit form of the update in terms of the surrogate coefficients: ϕ(v(k))ivi(k)=civi(k)⟹vi(k+1)=civi(k) φ(v^(k))_iv^(k)_i= c_i v^(k)_i v^(k+1)_i=c_i v^(k)_i (16) Substituting ci=vioptc_i= v_i^opt, we observe that the algorithm update is the element-wise geometric mean of the current iterate and the surrogate’s optimum: vi(k+1)=vi(k)⋅vioptv^(k+1)_i= v^(k)_i· v_i^opt (17) Proof of Ascent. Since the algorithm does not jump strictly to the maximizer voptv^opt but instead takes a damped step, we must show that this step still increases the surrogate value. Let ΔG=G(v(k+1))−G(v(k)) G=G(v^(k+1))-G(v^(k)). Since the terms separate, we analyze the scalar contribution for a single index i (omitting the subscript for brevity). Let v be the current value and c be the coefficient. The update is vnew=cv_new=c v. ΔGscalar G_scalar =(2cvnew−vnew)−(2cv−v) = (2c v_new-v_new )- (2c v-v ) =(2ccv−cv)−2cv+v = (2c c v-c v )-2c v+v =2c3/2v1/4−3cv1/2+v =2c^3/2v^1/4-3cv^1/2+v And we see the relation to the scalar case above. Again we substitute variables. Let v=c2z4v=c^2z^4 (for z>0z>0). This implies v1/2=cz2v^1/2=cz^2 and v1/4=c1/2zv^1/4=c^1/2z. ΔGscalar G_scalar =2c3/2(c1/2z)−3c(cz2)+c2z4 =2c^3/2(c^1/2z)-3c(cz^2)+c^2z^4 =c2(2z−3z2+z4) =c^2 (2z-3z^2+z^4 ) We must factorize the polynomial P(z)=z4−3z2+2zP(z)=z^4-3z^2+2z. But note, we already did this, in the scalar case. Thus, referring to Eq.˜4, we have ΔGscalar=c2⋅z⋅(z−1)2⋅(z+2) G_scalar=c^2· z·(z-1)^2·(z+2) (18) Since c,z>0c,z>0 (where c>0c>0 relies on positive-definiteness of M) and (z−1)2≥0(z-1)^2≥ 0, we have ΔG≥0 G≥ 0 unconditionally. Combining these results yields the ascent inequality chain: J(v(k+1))≥G(v(k+1);v(k))≥G(v(k);v(k))=J(v(k))J(v^(k+1))≥ G(v^(k+1);v^(k))≥ G(v^(k);v^(k))=J(v^(k)) (19) This confirms that the update rule guarantees monotonic ascent of the objective function, with strict increase whenever v(k)v^(k) is not a fixed point (as, by Eq.˜16, z=1z=1 again corresponds to the fixed point). ∎ Remark: This same proof can show linear (exponential) convergence to the objective. But this was already shown asymptotically (IE, close to the fixed point) by [DMR+22], and convergence rates are typically formulated asymptotically. 3 Conclusion I don’t consider the result shown here to be particularly noteworthy; I view it as the closure of a small problem that appeared in one of my past papers. It was something of a shame to me that we did not prove global convergence initially, despite spending a nontrivial amount of time searching for a surrogate function to fit in the M framework (and some reasonably heavy analysis by Sergey Denisov which showed ϕφ was a local contraction around its fixed point). The key fact we were missing was the representation Lemma˜1, which, as we saw above, allowed us to effectively diagonalize the problem. The effectiveness of a potential method of “diagonalizing the problem” was quite clear to us; but like most ex-mathematicians working in industry, I would be hard-pressed to recall every matrix equation I have ever seen. I have a deep an abiding love for mathematics; I entered computing because I believed that it would be a significant source of problems and approaches for the mathematics of the 21st century, in roughly the way physics was for so many years. I remember seeing Jordan Ellenberg at the 2025 joint mathematics meetings, and discussing with him my fear that advances in AI would be used primarily for companionship chatbots rather than progress in fundamental mathematics and science. He rightly pointed out to me the slightly strange priorities my comment implied: that I would rather prove more theorems than bring some comfort to lonely people around the world! I initially did this work in December of 2025; since then, several other examples of work of this flavor have appeared ([KNU26, OPE26, GLS+26, BEM+26]). I am happy to see that greater minds than my own have found utility in the current models in a roughly similar way to me. I decided to write up this note, rather than simply let sit the fact that I was able to close a not-entirely-trivial problem primarily through prompting of an AI model, in the hope that I might be able to play some small part in bringing the communities of pure mathematics and AI closer in these, the early days of our journey together. 4 Acknowledgments Gemini 3 made me aware of the representation Lemma˜1, and sketched the major steps of this proof. I filled in some details and fixed some argumentation (including some subtle gaps), but I consider this proof to have been effectively fully generated by Gemini 3. Moreover, Gemini 3 wrote a significant amount of this note; after some rounds of edits, it is difficult to say exactly how much, but its contribution was substantial. I owe a debt to Abhradeep Thakurta and Brendan McMahan, with whom I worked on formulating the problem that eventually led here. Certainly also our other co-authors on that first paper, Adam Smith and my advisor, Sergey Denisov. Finally, thank you to my wife Breanne Lynch, who has provided me with unfailing support, even if I can’t quite articulate why I need to be typing away at odd hours. References [BEM+26] J. Bryan, B. Elek, F. Manners, G. Salafatinos, and R. Vakil (2026-01) The motivic class of the space of genus 0 maps to the flag variety. arXiv preprint arXiv:2601.07222. Note: In collaboration with the Google DeepMind Blueshift team, including Adam Brown and Vinay Ramasesh External Links: 2601.07222, Link Cited by: §3. [DMR+22] S. Denisov, H. B. McMahan, J. Rush, A. Smith, and A. Guha Thakurta (2022) Improved differential privacy for sgd via optimal private linear operators on adaptive streams. In Advances in Neural Information Processing Systems, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.), Vol. 35, p. 5910–5924. External Links: Link Cited by: Appendix A, Appendix A, §1, §1, §2.3.2. [DMP+24] K. D. Dvijotham, H. B. McMahan, K. Pillutla, T. Steinke, and A. Thakurta (2024-10) Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy . In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), Vol. , Los Alamitos, CA, USA, p. 2306–2317. External Links: ISSN , Document, Link Cited by: §1. [GUE12] F. E. Guerra-Pujol (2012) Gödel’s loophole. SSRN Electronic Journal. External Links: Document, Link Cited by: Appendix A. [GLS+26] A. Guevara, A. Lupsasca, D. Skinner, A. Strominger, and K. Weil (2026-02) Single-minus gluon tree amplitudes are nonzero. arXiv preprint arXiv:2602.12176. Note: On behalf of OpenAI External Links: 2602.12176, Link Cited by: §3. [HJ90] R. A. Horn and C. R. Johnson (1990) Matrix analysis. Cambridge University Press. External Links: ISBN 0521386322, Link Cited by: §2.1, Lemma 1. [KNU26] D. E. Knuth (2026-02) Claude’s cycles. Stanford University, Computer Science Department. Note: Unpublication available at https://w-cs-faculty.stanford.edu/˜knuth/papers/claude-cycles.pdfRevised March 16, 2026 Cited by: §3. [LMH+15] C. Li, G. Miklau, M. Hay, A. McGregor, and V. Rastogi (2015) The matrix mechanism: optimizing linear counting queries under differential privacy. VLDB J. 24 (6), p. 757–781. External Links: Link, Document Cited by: §1. [LIE73] E. H. Lieb (1973) Convex trace functions and the wigner-yanase-dyson conjecture. Advances in Mathematics 11 (3), p. 267–288. External Links: ISSN 0001-8708, Document, Link Cited by: §2.1. [OPE26] OpenAI (2026-02) Our first proof submissions. Note: OpenAI BlogPublished February 20, 2026 External Links: Link Cited by: §3. [PUC+25] K. Pillutla, J. Upadhyay, C. A. Choquette-Choo, K. Dvijotham, A. Ganesh, M. Henzinger, J. Katz, R. McKenna, H. B. McMahan, K. Rush, T. Steinke, and A. Thakurta (2025) Correlated noise mechanisms for differentially private learning. External Links: 2506.08201, Link Cited by: §1. [ZAN69] W.I. Zangwill (1969) Nonlinear programming: a unified approach. Prentice-Hall international series in management, Prentice-Hall. External Links: ISBN 9780136235798, LCCN 69010606, Link Cited by: §2.3. Appendix A A User’s Journey Given my background, I am relatively uniquely positioned to effectively interact with current AI systems and produce effective mathematics. At present, it is a nontrivial procedure, and it is not entirely surprising that, with a different mental model of contemporary AI systems, interactions may go nowhere useful. In this section, I will attempt to extract the relevant aspects of my experience resulting in the proof above, and highlight some of the ways the process could have gone wrong. First, it must be stated that the models that currently exist are generally incredibly credulous. Mathematics is a process which requires surfacing all relevant reasoning steps. As much as formal methods indicate that we may be somewhat deceiving ourselves about the tightness of our reasoning, mathematics is, in my experience, the domain with the highest bar of reasoning in human activity. Thus, keeping in mind the view of LLMs as a “steerable probability distribution over all human text” (which is probably correct to first order), it is no surprise that models will tend, from the mathematician’s perspective, to leap to conclusions. These leaps, like our leaps, are often incorrect. Currently, models don’t demonstrate significant ability to spot their own gaps and critique their own leaps, though I expect this to change in the near future. This leads to the first pattern of effective use that I have found: Principle 1: Push hard on gaps. Models will often leap over the requirements of strict reasoning. Mathematicians know this is common practice in human interaction, and we must work quite hard to achieve the state of mind that allows for precise reasoning. Mathematicians, then, are often excellent (though far from perfect!) at “sniffing out” logical gaps. (In an infamous story, the great logician Kurt Gödel was said to have found an “internal contradiction” in the US Constitution which permits the US to legally convert itself from a republic to a dictatorship [GUE12]. Luckily the judge administering the citizenship examination to Gödel declined to pursue the matter.) Interacting with an AI with the goal of proving mathematics often stretches this logical-gap-sniffing capacity to the limit – there are so many! I will give one example that I found in the log of my interaction with Gemini that resulted in this note. After I pointed to [DMR+22] and asked for a proof of the convergence of iterates of ϕφ, Gemini responded with: Gemini: … Scalar Analogy: Consider the 1D case J(x)=2ax−xJ(x)=2 ax-x. The iteration is xnew=ax_new= ax. Let u=(x/a)1/4u=(x/a)^1/4. The gain ΔJ=J(xnew)−J(x) J=J(x_new)-J(x) factors as: ΔJ∝u(u−1)2(u+2) J u(u-1)^2(u+2) This is strictly positive for all u≠1u≠ 1. The matrix case satisfies a similar inequality. Clearly, this is insufficient. (Though, as we have seen above, indeed correct). Thus I asked: Keith: It seems like the crux of your argument is step 3, particularly, "the matrix case satisfies a similar inequality". please cut no corners and carefully show step 3. then: is step 3 a well-known fact? if so, please give a reference. Unfortunately, even to this I was left with a “matrix case satisfies a similar inequality” response. Gemini even admitted it could not prove this to me, and suggested I try numerics. At this point I opened a new chat, pasting in the argument Gemini gave me as context, asking: Keith: It seems like the crux of the argument to follow is step 3, particularly, "the matrix case satisfies a similar inequality". please cut no corners and carefully show step 3. then: is step 3 a well-known fact? if so, please give a reference. Here we finally, in hindsight, started to get closer. But much reasoning remained suppressed: Gemini: … Summary: The scalar proof (z(z−1)2(z+2)≥0z(z-1)^2(z+2)≥ 0) provides the intuition. The matrix case holds because the Trace acts on the singular values, and the non-commutativity terms are handled by the unitary invariance of the Nuclear Norm, effectively "diagonalizing" the problem into the scalar case at the optimal alignment. By now we see implicit references to the proof above, but it was quite difficult in the moment to disambiguate a correct hand-waving around unitary invariance from a pure hallucination. Keith: so, you haven’t given me a proof, right? Please try harder. This sequence of interactions yielded the representation of the nuclear norm we have in this note, and the basic outline of an M argument. With a few more iterations and fixing a few more gaps (initially, Gemini claimed that the iterations of ϕφ jumped directly to the maximum of the surrogate; upon my attempt to rewrite the logic, I discovered this was incorrect), we had the result you see above. But the interaction above contained a crucial easy-to-miss step, which can serve as our second principle: Principle 2: Beware of your context. Transformer-based LLMs typically attend to their context (in this case, the chat history) on every turn. This means that ideas present in the context can in some sense “pollute” new outputs, even if you are hoping to steer the model away from these ideas. Remember, an LLM is in “just” a steerable distribution over text, with the context serving as the conditioning variables for the generation process. Thus, the model is generating for you text that is likely to follow the context, presumably modulated by some posttraining to steer it towards free-flowing interactions. (I do not work in posttraining, so I do not have intimate familiarity with such details). But for this reason, things in the context can be very hard to make the model ignore. If it has responded to you with an answer you don’t like multiple times, you may be better off manually curating the context by starting a new chat, and feeding in your summary of the things you want the model to know, filtering out the things you wish for it to avoid. One aspect of this interaction which I suppressed above was the generation of colab snippets to check that we could not generate counterexamples to the claimed monotonic ascent. The validity of these snippets (plus my recollection that this was empirically true during the writing of [DMR+22]) served as a critical grounding in continuing to push the model towards a proof. Here Gemini was reasonably inventive, numerically attempting to minimize the gain in the vector v. Gemini generated the colab to follow, which I then altered slightly while running, to ensure the claimed ascent was not simply a low-dimensional phenomenon. ⬇ 1import numpy as np 2from scipy.linalg import eigh 3from scipy.optimize import minimize 4import matplotlib.pyplot as plt 5 6def get_sym_sqrt(A): 7 vals, vecs = eigh(A) 8 # Numerical stability: Clip small eigenvalues 9 vals = np.maximum(vals, 1e-14) 10 return vecs @ np.diag(np.sqrt(vals)) @ vecs.T 11 12def potential_J(v, M): 13 v_sqrt = np.sqrt(v) 14 D_sqrt = np.diag(v_sqrt) 15 Inner = D_sqrt @ M @ D_sqrt 16 17 # Tr(A^1/2) is sum(sqrt(eigenvalues(A))) 18 vals = np.linalg.eigvalsh(Inner) 19 vals = np.maximum(vals, 1e-14) 20 21 return 2 * np.sum(np.sqrt(vals)) - np.sum(v) 22 23def phi_map(v, M): 24 v_sqrt = np.sqrt(v) 25 D_sqrt = np.diag(v_sqrt) 26 Inner = D_sqrt @ M @ D_sqrt 27 S = get_sym_sqrt(Inner) 28 return np.diag(S) 29 30def run_adversarial_search(N=3): 31 32 # Parameterize M = L L^T (to ensure PD) and v = exp(u) (to ensure v > 0) 33 # Params: [u (size N), L_flat (size N*N)] 34 35 def pack(v, L): 36 return np.concatenate([np.log(v), L.flatten()]) 37 38 def unpack(params): 39 u = params[:N] 40 L_flat = params[N:] 41 v = np.exp(u) 42 L = L_flat.reshape(N, N) 43 M = L @ L.T + 1e-5 * np.eye(N) 44 return v, M 45 46 def objective(params): 47 v, M = unpack(params) 48 v_next = phi_map(v, M) 49 50 # We want to minimize gain 51 gain = potential_J(v_next, M) - potential_J(v, M) 52 return gain 53 54 # Initial random guess 55 A_init = np.random.randn(N, N) 56 v_init = np.random.rand(N) + 0.1 57 x0 = pack(v_init, A_init) 58 59 # Run Optimization (L-BFGS-B handles smooth unconstrained problems well) 60 res = minimize(objective, x0, method=’L-BFGS-B’,tol=1e-9) 61 62 min_gain = res.fun 63 64 if min_gain < -1e-8: 65 raise ValueError(min_gain) 66 else: 67 pass 68 69# Run the search 70 71# Test on a few dimensions 72run_adversarial_search(N=2) 73run_adversarial_search(N=3) 74run_adversarial_search(N=5) This colab verification pattern I have found useful in several other mathematics-heavy contexts when working with AI models; e.g., if the model claims to prove convexity of a certain function, the quickest route to falsifying this claim is often to simply ask the model to generate a code snippet which tests this claim numerically. This leads to our third and final principle: Principle 3: Ask for empirical verification of theory. If this test fails, it is often enough to feed this evidence back to the model to encourage it to revise its approach. Given the tendency of models to either hallucinate or suppress reasoning steps, quick empirical verification of claimed theoretical statements has saved me much time in the past. I have hope that other mathematicians and scientists can save themselves time and frustration, and achieve a fair sense of what the current models are capable of, by following and expanding on these three principles. Appendix B On the subtleties of checking correctness In an earlier version of this note, before posting publicly, there was an incorrect “proof” of Lemma˜2 which slipped past me. It is reproduced below. “Proof”. Let Ψ(v)=Dv1/2MDv1/2 (v)=D_v^1/2MD_v^1/2 and note that Ψ(v)=(vv⊤)⊙M (v)=( v v ) M. Since the square root function is strictly concave on ℝ++R_++, the map v↦vv⊤v v v is strictly operator concave. Because M≻0M 0, the Schur Product Theorem implies that Ψ(v) (v) is also strictly operator concave. Finally, since the trace-square-root functional X↦Tr(X1/2)X (X^1/2) is operator monotone and strictly concave on the positive definite cone, the composition J(v)J(v) is strictly concave. The linear term −∑vi-Σ v_i has a zero Hessian, thus the strict concavity of the first term yields ∇2J(v)≺0∇^2J(v) 0 for all v∈ℝ++Nv _++^N. ∎ The fundamental flow with this argument is in the claim that v↦vv⊤v v v is operator concave. A simple example choosing v=(1,4)v=(1,4) and w=(4,1)w=(4,1) is enough to contradict this claim. However, I did not spot it. Almost certainly I had asked for some kind of numerical verification of the claim of Lemma˜2, similar to the snippet above, and this led me to be a bit too trusting in the details of the argument. Later on, I caught a subtle mismatch between the definition of A used in Section˜2.3.1 and that which corresponds to the actual literal potential function. (The model used Dv1/2M1/2D_v^1/2M^1/2 instead of M1/2Dv1/2M^1/2D_v^1/2). Technically this was only a missed logical step, and not incorrect, because of the equivalence of the eigenvalues of ABAB and BABA as noted in the (new) proof of Lemma˜2, but it resulted in some strange gymnastics (e.g. the use of the left polar factorization instead of the more traditional right polar factorization). I rewrote the argument in the current form you find it, which I find much more straightforward. In some ways, each of these is an effective illustration of our principle 1 above. But it also highlights a real difficulty in using AI to accelerate mathematics in this way, at least, without coupling with formal methods. On the other hand, it is a belief of mine (shared by at least one other mathematician I know) that every math paper has gaps; the only question that counts is whether or not those gaps matter. Neither of these gaps matter. And indeed, once Gemini presented me with the variational characterization of the nuclear norm Lemma˜1, I knew the problem was solved, and the rest was details. Time will tell, I think, whether the ease of producing a gap with AI-assisted mathematics will proliferate their relative occurrence, and whether the human checking will be overwhelmed by the volume of argumentation and its apparent simplicity, or whether this is a phantom concern that will either be solved by better models or improved ways of working.