Browse

Logic in Computer Science

cs.LO — Logic in Computer Science

cs.LO RSS feed

Works in cs.LO

56 works

math-ph — Mathematical Physics

From Four-Dimensional Wilson Lattice Gauge Theory to Quantum Yang--Mills Theory: Construction with Proofs from Certified Assumptions, and the Record of Its Independent Validation

Contributed by Zeng Chunping

We present a complete formal paper compiling the Lean-verified construction of quantum Yang--Mills theory submitted on October 28, 2026, and independently validated by the Yang--Mills Shepherding Committee. Starting from the Wilson definition of lattice gauge theory on a four-dimensional torus, we give full proofs of every step that can be carried out from the definitions: the field-label algebra, the finite lattice theory, and---under an explicit, individually certified package of renormalization-group and analytic assumptions (RG1)--(RG5), (UV1), (PH1)--(PH3), (AN1), (Y1)--(Y4), (B1), (C1)---the fixed-volume ultraviolet limit, the subsequential infinite-volume limit, the phase decomposition with clustering and full support, the Osterwalder--Schrader reconstruction satisfying the Wightman axioms, and the Yang--Mills identification: the stress tensor and its Ward identity, the trace anomaly with the verified constant 3dim⁡Rg/π43\dim_{\mathbb{R}}\mathfrak{g}/\pi^{4}, the exclusion of a precise class of free-field descriptions, the one-loop running coupling, and the operator product expansion. The independent validation (clean rebuild, Lean kernel replay, Comparator runs, the verification of the OS axioms against an independent axiom system, and the lattice-law, Ward-identity, common-scale, short-distance, and OPE adapters) is recorded in the second part. Two errata to the source validation document are corrected in the text. For the mass gap we prove two logical boundaries: an explicit OS model satisfies all sixteen registered inputs, with E4 clustering (equivalently, vacuum uniqueness) holding, yet its Hamiltonian has no spectral gap, and a mass gap is equivalent to a uniform exponential rate in the clustering axiom E4; the sixteen registered inputs therefore do not imply a mass gap. The gap problem is reduced to a single volume-uniform, label-uniform rate (MG); the cluster-expansion, spectral, rate and Wilson-loop routes, the random-mechanics criteria, the source-level adjudication, and the complete status are recorded in an appendix. A positive mass gap, uniqueness of the infinite-volume limit, uniqueness of the vacuum of the mixed theory, and order-by-order agreement of the OPE with perturbation theory are not proved, and the paper records precisely what is and is not proved at every step.

Author comments: Recompiled with complete proofs from the committee's validation document (2026-11-10 release) of the Lean-verified OpenAI Yang--Mills construction (2026-10-28), incorporating the readable re-proof and the review-and-supplement packages. All proofs that can be carried out from the definitions and the certified assumption package (16 external inputs) are given in full; two errata of the source document are corrected (the $I^2=1$ contraction identity and the $\log^2$ weight of the free-field exclusion). The mass-gap problem is reduced to the single uniform rate (MG); Appendix E records the complete adjudicated status including rate theorems, counterexample families, cluster-expansion and local-mixing routes, and source-level adjudications.

A mix of human-written and AI-generated textHuman understanding: some partsLeanOPEOS/Wightman axiomsRGWilson latticeYang-Millsconstructive QFTmass gaptrace anomaly
Nov 15, 202681 pages
PDFView work

math.NT — Number Theory

Bounds for the smallest limit point of the areal Mahler measure of totally positive algebraic integers

Contributed by Tejasvi Singh Tomar

Pritsker's areal analog ∥P∥0\|P\|_0 of the Mahler measure replaces the integral of log⁡∣P∣\log|P| over the unit circle by its integral over the unit disc with respect to normalized area. For an algebraic number α\alpha of degree nn with minimal polynomial P∈Z[x]P\in\mathbb{Z}[x], taken primitive with positive leading coefficient, let N0(α)=∥P∥01/nN_0(\alpha)=\|P\|_0^{1/n}. Flammang proved that N0(α)≥1.380047N_0(\alpha)\ge1.380047 for every totally positive algebraic integer α\alpha outside an explicit finite set. We prove that the smallest limit point of the values of N0N_0 on totally positive algebraic integers and their essential minimum lie between 1.38301341.3830134 and 1.38395791.3839579. The lower bound improves on Flammang's constant: it holds for all but finitely many totally positive algebraic numbers, not only integers, although the exceptions are not determined. Infinitely many totally positive algebraic integers satisfy N0(α)<1.3839579N_0(\alpha)<1.3839579. The lower bound comes from an auxiliary function with a logarithmic energy term, and the upper bound from an explicit measure that, by a criterion and a theorem of Smith, is a limit of distributions of conjugates of totally positive algebraic integers. The inequalities behind both bounds are verified in ball arithmetic, and both bounds are also proved in Lean, the upper one assuming Smith's theorem.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23715993

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 15, 202610 pages
PDFView work

math.MG — Metric Geometry

An upper bound of 2√2 for the three-dimensional sofa problem in a snake-shaped corridor

Contributed by Tejasvi Singh Tomar

The moving sofa problem in a snake-shaped corridor, posed by O'Rourke and by Georgiev, Gómez-Serrano, Tao and Wagner, asks for the largest volume of a connected body that can be moved through a corridor of unit-square cross-section with two turns that are far apart, one in the xx–yy plane and one in the yy–zz plane. The largest reported body has volume at least 1.85584041.8558404, and Tang obtained upper bounds for this problem, the best of which is 3.40833.4083. We prove by hand that the largest volume is at most 222\sqrt2 whenever the straight section between the turns is longer than 2+22+\sqrt2. The main new tool is a sharp bound: two infinite tubes of unit-square cross-section whose axes make an angle θ\theta meet in volume at most 1/sin⁡θ1/\sin\theta. With it, Hammersley's argument for the planar moving sofa problem carries over to three dimensions. The same argument gives explicit bounds for shorter straight sections; these and the main bound have also been proved in Lean 4 with Mathlib.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23716059

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 15, 202610 pages
PDFView work

cs.LO — Logic in Computer Science

A formal proof in Lean of the finiteness of planar five-body central configurations for all positive masses

Contributed by Tejasvi Singh Tomar

Smale's sixth problem asks whether, for every choice of positive masses, there are finitely many central configurations up to similarity. For five bodies in the plane, Albouy and Kaloshin proved finiteness outside a set of masses of codimension two. In a companion paper the author proved finiteness for every choice of five positive masses by their method, adding steps that cannot be checked by hand: exact computer algebra, rational certificates and a branch and bound. We formalize this theorem in Lean 4 with Mathlib without assuming the results of Albouy and Kaloshin that the informal proof uses. Instead we prove what the proof needs of their rules on limit diagrams, of their classification of these diagrams and of their mass conditions. We do so at places of complex algebraic curves, taken as valuations of the function field rather than points of a projective model. Almost every computation becomes data for a checker that we write in Lean, prove sound with respect to Mathlib's real and complex numbers, and run in the kernel (proof by reflection). The main theorem depends on about 680,000680{,}000 theorems proved in this way, and Mathlib's tactics prove the few other computations. The proof uses only Lean's three standard axioms, and two independent Lean kernels, nanoda and lean4lean, accept it.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23723139

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202619 pages
PDFView work

cs.LO — Logic in Computer Science

A Lean 4 formalization of the area law for three-dimensional U(1) lattice gauge theory with the Wilson action

Contributed by Tejasvi Singh Tomar

In three-dimensional U(1)U(1) lattice gauge theory with the Wilson action, static charges are confined at every coupling: rectangular Wilson loops obey an area law, uniformly in the finite box. This was proved recently by the author in a separate paper; the proof runs to over three hundred pages with its supplement and adapts the Debye-screening analysis of Brydges and Federbush and the multiscale expansion of Göpfert and Mack. We describe a formalization of this proof in Lean 4 with Mathlib, which also covers the paper's corollaries and its appendix on comparing Wilson and Villain loops. The formal theorems take no hypotheses and use only the standard axioms of Lean. The proof became formalizable through explicit interfaces between its parts, written-out versions of the steps that the paper adapts from the literature or leaves out, and certified values for every numerical constant. The formalization also yielded 70 corrections and improvements to the paper, none of which changes its main results.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23752572

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202619 pages
PDFView work

cs.LO — Logic in Computer Science

Formal Verification of a Computer-Assisted Proof in Celestial Mechanics

Contributed by Tejasvi Singh Tomar

Albouy, Fu and Sun conjectured in 2008 that four positive masses admit, for each cyclic order of the bodies, exactly one convex central configuration up to similarity; the question is Problem 10 of a 2012 list of open problems on the nn-body problem. We recently proved the conjecture by reducing it to an inequality for a trace at the real zeros of an equation in four variables; a branch and bound that starts from a grid of 136,448 boxes establishes the inequality. In this paper we describe a formalization of the whole proof in Lean 4 and Mathlib in which Lean's kernel checks the computation, using decide +kernel, so that no compiler has to be trusted. Our checker stores an interval as two natural numbers in a biased fixed-point format. The kernel can then hand all the arithmetic to GMP. Functions are enclosed over boxes by first-order slopes. An unverified search records the decisions for each box in one natural number, and the checker replays them. We write each formula once over a type class; evaluating it at a type that pairs a real number with an interval then proves the enclosure correct. Checking the 3418 certificate theorems takes 7.6 hours of processor time, and the independent type checker nanoda accepts the proof. A version rebuilt on one eighth of the boxes passed three type checkers in 2.9 hours on a public registry of formal proofs.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23485952

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202619 pages
PDFView work

math.DS — Dynamical Systems

Smale's sixth problem for six bodies in the plane: finiteness of central configurations for generic masses, with a proof formalized in Lean

Contributed by Tejasvi Singh Tomar

Smale's sixth problem asks whether, for every choice of positive masses, the number of central configurations up to similarity is finite. We prove that it is finite for six bodies in the plane and all positive masses outside a proper algebraic subset of the mass space. This subset, which we describe only in part, contains every mass vector with three equal masses or with one mass equal to the sum of two others. Finiteness for all positive masses remains open. Infinitely many central configurations would give a curve of complex solutions; following Albouy and Kaloshin, we exclude such a curve using the valuations of the mutual distances at its points at infinity. The proof is computer-assisted and uses linear programs, Gröbner bases and interval arithmetic. The theorem is proved in the Lean proof assistant, whose kernel checks the computations as well.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23720035

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202648 pages
PDFView work

cs.LO — Logic in Computer Science

Re-proving native_decide facts in Lean's kernel: a study of 16 public packages and a converter

Contributed by Tejasvi Singh Tomar

Lean's native_decide proves a decidable proposition by running compiled code and records the result as an axiom. Mathlib forbids such axioms, and lake check and Comparator in Lean 4.35 reject them, as do the independent proof checkers. NativeTrust re-proves the recorded facts in Lean's kernel, with only the standard axioms and without editing the projects that contain them. Where a definition blocks kernel evaluation and NativeTrust has a version proved equal to it (for example, a fuel-indexed form of well-founded recursion), the converter evaluates a copy that uses that version. It then proves the copy equal to the original, usually by congruence. With its default settings it converts 98.2% of 52,821 native facts in 16 public packages. The three largest packages hold 94% of these facts; outside them it converts 68.5%. Nearly every converted fact needed nothing beyond plain kernel evaluation. Two tools remove the native axioms that the kernel can prove within a budget: a single import that makes each call of the tactic try the kernel first, and a source rewriter.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23818391

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202627 pages
PDFView work

cs.LO — Logic in Computer Science

Expressiveness, Verifiability, Tractability: Toward a Computational Thermodynamics

Contributed by Benjamin Kaminsky

An investigation into the existence of a conservation law governing computational behaviour, in the form of the Expressiveness, Verifiability, Tractability (EVT) Hypothesis, is undertaken. The hypothesis is motivated by a simple observation: mechanisms that increase what a system can directly express, powerful control, effects, reflection, meta-programming, and self-interpretation, tend to undermine what can be verified uniformly and mechanically, while regimes that maximize static guarantees typically do so by restricting expressiveness or relocating effort into compilers, proof artifacts, or human interpretation. We analyze canonical failure modes that arise when one attempts to push beyond this frontier, distinguishing collapse of correctness, collapse of compilability, and collapse of comprehensibility. We then develop an order-theoretic model for comparing languages and verification disciplines and define an “E/V boundary” as a Pareto frontier in a partially ordered design space. Finally, we sketch how analogous tradeoffs appear in other computational domains, suggesting that “thermodynamic” boundary behaviour may be a recurring feature of expressive formalisms that demand strong global guarantees and within physical methods of information processing.

A mix of human-written and AI-generated textHuman understanding: all partsEVT hypothesiscomputationprogramming languagesresource theory
Nov 12, 202639 pages
PDFView work

math.MG — Metric Geometry

On the local geometry of the tight 39-point code in the octonionic projective plane

Contributed by Robert R. MacGregor

Cohn, Kumar and Minton constructed a four-parameter family of tight 3939-point codes in the octonionic projective plane. We show that near each member outside a closed nowhere-dense set of resonant parameters, the labeled tight codes modulo F4F_4 form exactly four ten-dimensional families, any two meeting in the four-parameter family, although the first-order deformations of the member form a 2828-dimensional space modulo F4F_4. The originally constructed code is resonant, and we do not determine the tight codes near it; but every neighborhood of it in the space of unlabeled tight 3939-point codes modulo F4F_4 contains a nonempty open subset homeomorphic to an open subset of R10\mathbb R^{10}, so any neighborhood of it that is a manifold has dimension ten.

Author comments: 55 pages, 5 figures. Ancillary files: anc/native-data.json holds the exact coefficients of Appendix C, and anc/finite-identities.py replays the finite identities of Proposition 6.5 from it in exact arithmetic. Lean source: https://github.com/macgregor-sudo/tight-39-code at commit 46f01c1.

Primarily AI-generated textHuman understanding: no partsAlbert algebraF4Leandeformationmutually unbiased basesoctonionic projective planetight code
Nov 12, 202655 pages
PDFView work

math.HO — History and Overview

The Rising-Sea Theses: Twelve Theses on Mathematics and Machine Reasoning

Contributed by Vincent Liu

The Grothendieckian Programme is a set of seven works on machine reasoning about mathematics (34 volumes, 26,021 pages), released openly in October 2026 as first drafts that have not been peer-reviewed. This paper draws from them twelve theses on how mathematics and machine reasoning should be combined. Each thesis is stated in one sentence, argued, tied to the passages of the seven works on which it rests, related to existing work, and paired with an observation that would refute it. The theses concern the unit of mathematical knowledge for a reasoning system, the place of epistemic status, the latent space of mathematical reasoning, attention, failure, authority, and the method of discovery. The paper adds no mathematical result to the seven works; none of them claims a proof of the Riemann Hypothesis, the Birch and Swinnerton-Dyer conjecture, the Hodge conjecture, the abc conjecture or the Langlands correspondence.

Author comments: 26 pages, 5 figures. Version 1.0 of 28 October 2026; the same text is deposited at Zenodo, DOI 10.5281/zenodo.23734424 (all versions: 10.5281/zenodo.23734423). This copy was typeset with pdfLaTeX for Hexagon: its text is identical to version 1.0 at Zenodo, whose sealed PDF was typeset with LuaLaTeX, except that a broken cross-reference on page 3 ("igref{works}") is corrected to "Figure 1"; a few line and page breaks differ. The twelve theses are also set out at https://github.com/AlienMuse/grothendieckian-problems/blob/main/THESES.md; the seven works on which they rest, each with its DOI, are listed at https://github.com/AlienMuse/grothendieckian-programme. Corrections recorded since version 1.0 to the seven works and to the papers: https://github.com/AlienMuse/grothendieckian-problems/blob/main/ERRATA.md. Companion papers: The Grothendieckian Programme: An Overview (DOI 10.5281/zenodo.23734421) and The 57 Grothendieckian Problems (DOI 10.5281/zenodo.23734426).

A mix of human-written and AI-generated textHuman understanding: all partsGrothendieckian Programmedescentepistemic statusformal verificationmachine reasoningrecursive mathematical discovery
Nov 10, 202626 pages
PDFView work

math.HO — History and Overview

The Grothendieckian Programme: An Overview — Seven Open Works on Mathematics and Machine Reasoning

Contributed by Vincent Liu

The Grothendieckian Programme is a series of seven works on machine reasoning about mathematics (34 volumes, 26,021 pages), released openly on Zenodo in October 2026 with an overview volume. Two of the works specify a reasoning architecture — a core that holds mathematical worlds as typed, versioned and verifiable objects, and a kernel that reasons inside such worlds by sites, sheaves and descent. Five apply one method, recursive mathematical discovery, to the Riemann Hypothesis, the conjecture of Birch and Swinnerton-Dyer, the Hodge conjecture, the abc conjecture and the Langlands programme, and record what it proves, what it reduces to stated hypotheses and what it leaves open. This paper describes the architecture, the five research subjects, the method, the published corpus and the open process by which the works are to be reviewed and continued. None of the works claims a proof of any of these conjectures; they are first drafts and have not been peer-reviewed.

Author comments: 10 pages, 3 figures. Version 1.0 of 28 October 2026; the same text is deposited at Zenodo, DOI 10.5281/zenodo.23734422 (all versions: 10.5281/zenodo.23734421). This copy was typeset with pdfLaTeX for Hexagon: its text, and its line and page breaks, are the same as in version 1.0 at Zenodo, whose sealed PDF was typeset with LuaLaTeX. The seven works it describes, each with its DOI, are listed at https://github.com/AlienMuse/grothendieckian-programme. Corrections recorded since version 1.0 to the seven works and to the papers: https://github.com/AlienMuse/grothendieckian-problems/blob/main/ERRATA.md. Companion papers: The Rising-Sea Theses (DOI 10.5281/zenodo.23734423) and The 57 Grothendieckian Problems (DOI 10.5281/zenodo.23734426).

A mix of human-written and AI-generated textHuman understanding: all partsGrothendieckian Programmedescentmachine reasoningmathematical worldsopen sciencerecursive mathematical discovery
Nov 10, 202610 pages
PDFView work

math.CO — Combinatorics

Sharp thresholds for five-colour cube assemblies

Contributed by Jason Davies

We determine the least pool sizes guaranteeing a frame or a complete a×b×ca\times b\times c box from unit cubes whose faces use all five colours of a fixed palette, for every a,b,c≥2a,b,c\ge2. Proper rotations are allowed; the target has monochromatic exterior faces using all five colours. The frame threshold is max⁡{15,4(a+b+c)−16,2(a+b+c)+1}\max\{15,4(a+b+c)-16,2(a+b+c)+1\}, and the complete-box threshold is max⁡{abc,15,2(a+b+c)+1}\max\{abc,15,2(a+b+c)+1\}. The proof combines a certified fifteen-cube corner theorem with elementary Hall arguments and a uniform three-variety obstruction. It completes the five-colour frame column left open by Berkove, Eickemeyer and Schulman (2018). All threshold statements are formalised in Lean. A fixed-size flow formulation decides feasibility and constructs assemblies in time linear in the explicit source list. We also determine the corner thresholds when the number of source varieties is bounded, and classify all fourteen-cube obstructions into 56 classes under common colour relabelling and simultaneous reflection, described by three structural forms. The minimum size of a collection capable of reproducing every 2×2×22\times2\times2 target is also fifteen.

Primarily AI-generated textHuman understanding: some partsHall's theoremLean formalisationMacMahon puzzlescoloured cubescomputer-assisted proofextremal combinatoricsinterval certificates
Nov 10, 202634 pages
PDFView work

math.LO — Logic

The Logical Anatomy of Optimization: Reverse Mathematics, Proof Mining, and the Price of Convergence

Contributed by Xiaoyu Li

Optimization theory proves three kinds of theorems: that optimal points exist, that algorithms converge to them, and that optimality can be certified by duality. We measure how much mathematics each kind needs, using reverse mathematics, Weihrauch complexity and proof mining, and assemble the answers, old and new, into one map stated in the language of optimization. Compactness makes existence cost weak Kőnig's lemma, but convexity (and, format by format, tameness) makes it cheap: we show that RCA0\mathsf{RCA}_0 proves that convex functions on [0,1][0,1] attain their minima (and on [0,1]n[0,1]^n, for each fixed nn, given a modulus of uniform continuity), and that RCA0\mathsf{RCA}_0 proves linear programming duality and the minimax theorem for real data of every size. Convergence costs more: it follows from results of Kohlenbach and Neumann that convergence of gradient descent for convex smooth functions on R\mathbb{R} is equivalent to ACA0\mathsf{ACA}_0. We explain this by a selection principle: what costs is the particular minimizer the algorithm selects, and uniqueness or an error bound removes the cost. Below convergence lies finitary information. Gradient descent in Rd\mathbb{R}^d has at most 2CdD/ε2C_dD/\varepsilon fluctuations of size ε\varepsilon, with CdC_d depending only on dd, which yields rates of metastability; no such bound is dimension-free, by the span-restriction argument behind performance estimation; and the limits of gradient descent on computable instances have d.c.e. coordinates, a proper subclass of the limit-computable reals. The map also covers Ekeland's variational principle (up to Π11-CA0\Pi^1_1\text{-}\mathsf{CA}_0), separation theorems, Kőnig duality (ATR0\mathsf{ATR}_0), proof-mined rates for fixed-point iterations, and the feasible world, where local search captures the NP\mathsf{NP} search problems provably total in T21T^1_2 and approximate stationary points of smooth functions are complete for CLS=PPAD∩PLS\mathsf{CLS}=\mathsf{PPAD}\cap\mathsf{PLS}. We close with five principles and open problems.

Primarily AI-generated textHuman understanding: some partsTFNPWeihrauch complexitybounded arithmeticconvex optimizationgradient descentlinear programming dualitymetastabilityminimax theoremproof miningreverse mathematics
Nov 10, 202646 pages
PDFView work

math.HO — History and Overview

The 57 Grothendieckian Problems: Open Problems for Mathematics and Machine Reasoning from the Grothendieckian Programme

Contributed by Vincent Liu

We state fifty-seven open problems drawn from the seven works of the Grothendieckian Programme (34 volumes, 26,021 pages, released openly in October 2026 as first drafts that have not been peer-reviewed). Thirty-five come from the two works on the architecture of a reasoning system and twenty-two from the five works that each take a named conjecture or programme as research subject; no problem is one of those conjectures. Each problem is stated in the words of its source, located by work, chapter and page, given the status the source assigns it, and paired with a criterion that decides when it is solved, a note on existing work and the date of a literature check. The problems are of three kinds: twenty-five mathematical problems, nineteen machine problems with success criteria fixed in advance, and thirteen formalization problems for Lean 4 and Mathlib. Every quotation from the sources has been checked against the published PDFs, and each problem has been checked against the literature as of 28 October 2026; a machine-readable version accompanies the paper.

Author comments: 54 pages, 5 figures. Version 1.0 of 28 October 2026; the same text is deposited at Zenodo, DOI 10.5281/zenodo.23734427 (all versions: 10.5281/zenodo.23734426). This copy was typeset with pdfLaTeX for Hexagon: its text is identical to version 1.0 at Zenodo, whose sealed PDF was typeset with LuaLaTeX, and a few line and page breaks differ. Each problem has a public issue at https://github.com/AlienMuse/grothendieckian-problems, which also holds the machine-readable data, the literature-check records and the Lean statement of Problem 49. Corrections recorded since version 1.0, including literature missed by the check for Problem 18: https://github.com/AlienMuse/grothendieckian-problems/blob/main/ERRATA.md. Companion papers: The Grothendieckian Programme: An Overview (DOI 10.5281/zenodo.23734421) and The Rising-Sea Theses (DOI 10.5281/zenodo.23734423).

A mix of human-written and AI-generated textHuman understanding: all partsGrothendieckian ProgrammeLeandescentformal verificationmachine reasoningopen problems
Nov 10, 202654 pages
PDFView work

cs.LO — Logic in Computer Science

Formalizing the interpolation lemma of the openai/math Landau–Siegel paper and substituting it into a Comparator-accepted proof

Contributed by Joseph Reilly

OpenAI’s openai/math release includes a Lean formalization of “Uniform exclusion of Landau–Siegel zeros” (OpenAI, October 1, 2026). Its Comparator challenge has two checked theorems, whose statements we prove equivalent in Lean. OpenAI proves them by two routes, neither through the paper’s proof of Lemma 3. The catalogued main result, exists_absolute_real_zero_gap, gets its spanning step from a local Bézout argument and does not use OpenAI’s Corollary 4 theorem. The second theorem, dirichletRealZeroBound_proof, proves Corollary 4 by a multiplicity estimate. We formalized the paper’s proofs of Lemma 3 and Corollary 4 in Lean. By reading, the Lean statements match the paper’s, and the declarations use only the axioms propext, Classical.choice and Quot.sound. A +2/-1 substitution puts the paper’s Corollary 4 into dirichletRealZeroBound_proof. Comparator accepts the result with both kernels at openai/math fd4aeeb under a deny list of all 45 socket address families, and that theorem’s closure no longer contains the three named OpenAI lemmas. Our replay of the corpus agrees with an independent replay on all 402 configurations where both have a verdict.

Primarily AI-generated textHuman understanding: some parts
Nov 10, 202620 pages
PDFView work

math.AG — Algebraic Geometry

The tangent line at a marked point on M0,n/Sn−1M_{0,n}/\mathfrak S_{n-1}, after a table of Grothendieck

Contributed by Michel Hua

Let LnL_n be the line bundle on M0,nM_{0,n} whose fibre is the tangent line to P1\mathbb P^1 at the last marked point, and LL the tensor product of the tangent lines at all of them. We show that, in characteristic zero, the Picard group of the quotient stack [M0,n/Sn−1][M_{0,n}/\mathfrak S_{n-1}] is cyclic of order (n−1)(n−2)(n-1)(n-2) for every n≥3n \ge 3, generated by LnL_n, and that LL has order n−1n-1 in Pic⁡[M0,n/Sn]\operatorname{Pic}[M_{0,n}/\mathfrak S_n]. For even n≥6n \ge 6 the group was known, through the integral Chow ring computed by Edidin and Hu; the odd case does not seem to be in print. The question comes from a table in Grothendieck’s working notes, which gives these orders for four points and only guesses for five and six. The proof takes a few lines once the stack is written as monic squarefree polynomials modulo the affine group. An elementary version, with explicit trivialisations and fixed configurations, is formalised in Lean.

Primarily AI-generated textHuman understanding: some partsGrothendieckLean 4MathlibMontpellier archivePicard group of a quotient stackbinary formsdiscriminantformalisationmoduli of pointed rational curvestangent line bundle
Nov 07, 20265 pages
PDFView work

math.CO — Combinatorics

A bigon-free dichotomy for pseudoline arrangements, after a note of Grothendieck

Contributed by Michel Hua

A pseudoline of an arrangement in the real projective plane is bigonal when it carries exactly two vertices of the arrangement. In an undated folder of working notes from the early 1980s, Grothendieck states that every arrangement without bigonal pseudolines is either four pseudolines in general position or contains one of three configurations: five pseudolines in general position, a pencil of three and a pencil of two without the line joining their centres, or the complete quadrangle. The notes derive this from a statement that is false as written, and they give no independent proof. We give a short proof, together with the ordering of the pseudolines that the notes ask for, and we deduce that for n ≥ 6 the near-pencils are the only arrangements of n pseudolines containing none of the three configurations. The dichotomy has been checked by an exhaustive enumeration of all arrangements of at most nine pseudolines, and it is formalised in the proof assistant Lean for a combinatorial model of arrangements, generalised maps of Euler characteristic one.

Primarily AI-generated textHuman understanding: some partsGrothendieckLean 4MathlibMontpellier archiveSylvester–Gallaicomplete quadrangleformalisationgeneralised mapsnear-pencilpseudoline arrangements
Nov 07, 20267 pages
PDFView work

math.DS — Dynamical Systems

Normal Cone Is All You Need: Unsoftened Symplectic Integration Of The Newtonian N-Body Problem Across Collisions In Finite Steps

Contributed by Jeremy Nusa

In the classical formulation of the Newtonian NN-body problem, symplectic geometry and collision singularities appear fundamentally irreconcilable: fixed-step symplectic integrators preserve the Poincaré integral invariants on smooth orbits only by softening the gravitational potential or breaking down at close encounters, whereas classical Sundman and Levi-Civita regularizations resolve collisions only by deforming the global time flow or altering the canonical phase-space structure. In this work, we show that this dichotomy is not an intrinsic obstruction of Hamiltonian mechanics, but an artifact of working on the unblown Cartesian configuration space. By lifting the dynamics to the standard cotangent bundle T∗Q[N]T^*\mathbf{Q}[N] of the real oriented Fulton–MacPherson compactification Q[N]=Bl⁡Π(N)(M/R3)\mathbf{Q}[N] = \operatorname{Bl}_{\Pi(N)}(M/\mathbb{R}^3) and applying the Calaque–Safronov shifted cotangent deformation to the normal cone DZQ[N]→A1\mathcal{D}_Z \mathbf{Q}[N] \to \mathbb{A}^1, we construct an exact, unsoftened (ε=0\varepsilon = 0) Hamiltonian splitting covered by the combinatorial atlas of (2N−3)!!(2N-3)!! rooted binary Jacobi trees. Along the normal-cone degeneration, the interaction decomposes canonically into commuting Kepler–Sundman leaf flows, synchronous anti-Zeno supernodes, and a scale-invariant quadrupolar-screened apex potential of global C1,1\mathcal{C}^{1,1} regularity. Endowing the exceptional collision divisors with McGehee's unitary elastic bounce involution (BC2=Id\mathcal{B}_C^2 = \mathrm{Id}) renders the leaf flows globally complete and time-reversible across binary collisions in a finite number of physical steps, thereby lifting the Sheng–Suzuki negative-timestep barrier for high-order symmetric compositions. In the bi-graded Poisson–Lie algebra Ln,m\mathcal{L}_{n,m} associated with this splitting, we establish a Universal Double Obstruction Theorem at order six: momentum-parity alternation prevents any pure configuration-space corrector from cancelling the leading secular error, while a non-vanishing Hall cohomology class in H1(DA,L5,2)H^1(D_A, \mathcal{L}_{5,2}) creates an incompressible O(ε2h4)\mathcal{O}(\varepsilon^2 h^4) quadratic tidal floor. We overcome the parity obstruction by introducing a torque-free cotangent corrector K4∈L4,1∩P1K_4 \in \mathcal{L}_{4,1} \cap \mathcal{P}_1, realized via a palindromic Lie conjugator Z4BM4(h)\mathcal{Z}_4^{\mathrm{BM4}}(h) that vanishes naturally as O(r7/2)\mathcal{O}(r^{7/2}) at collisions (scheme PBM4\mathrm{PBM}_4). Whenever the trajectory changes local Jacobi chart or dyadic step-size level, a non-commutative covariant gauge connection TA→B(PBM4)T_{A\to B}^{(\mathrm{PBM4})} closes the Čech 1-cocycle on the atlas groupoid and eliminates interfacial shadow-energy jumps. Accompanied by a complete, axiom-free Lean 4 formalization and validated up to 116-bit quadruple precision against the REBOUND integrator suite (IAS15, TRACE, MERCURIUS, and WHFast), the resulting architecture preserves all Galilean Lie–Bargmann invariants to machine precision across secular, collisional, and chaotic multi-body regimes.

A mix of human-written and AI-generated textHuman understanding: some partsFulton-MacPherson compactificationHall Lie algebraLie-Bargmann algebraN-body problemcelestial mechanicscollision regularizationdeformation to the normal conesymplectic correctorssymplectic integration
Nov 06, 2026195 pages
PDFView work

cs.LO — Logic in Computer Science

Proof-Carrying Modernization: LLM Translations of COBOL Batch Programs, Each Proved Against the Original in Lean

Contributed by Tejasvi Singh Tomar

Large language models translate legacy code quickly, but a translation can differ from the original on inputs that no test exercises. We show that LLM translations of whole, unmodified COBOL programs into Rust and Java can be proved in Lean 4 to behave like our semantics of the originals on every admissible input: a bounded number of well-formed records, among other premises. The COBOL semantics is executable; it computes record layouts, decimal arithmetic and file handling from our front end’s output for the unmodified source. For the eight standalone batch programs of AWS CardDemo covered by that front end, all 16 translations are proved, as equivalences for Rust and as refinements with partial correctness for Java. The statements are generated from the programs except for a few small parts, LLM agents write the proofs, and Lean’s kernel checks them. Before any proof, 35% of the first running translations differed from our semantics of the original on a generated input, and no proof found a difference that this testing had missed.

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 06, 202623 pages
PDFView work

cs.CC — Computational Complexity

What the ETH refutations do not give: barriers for the counting engines, with machine-checked lemmas

Contributed by Vaibhav Tulsyan

In October 2026 OpenAI and Anthropic each claimed a deterministic subexponential algorithm for counting the solutions of a kk-CNF; both counting engines sum products of local tables. For SAT itself, Majdoddin bounds the rate of Anthropic's grid recursions with product terms, and Dias and Lima bound OpenAI's clause-product scheme. However, Majdoddin notes that no barrier is known for decompositions whose terms are not products, and neither paper treats the counting problems beyond SAT. We introduce the engine barrier problem: bound from below the shared bits UU of every network of a stated class that computes a given count, and the rate of every recursion of a stated class. Our approach puts a rank on every cut of a local network, and on one contraction inside both flattenings of a term. Machine-checked in Lean are: correlated (non-product) decompositions of two rectangles, of the 3×23\times2 grid and of the full 3×33\times3 grid level have flattening-rank sums at least N2N^2, N3N^3 and N8N^8, while N9N^9 is open; the row cut of the permanent has rank (nk)\binom nk, which on paper gives U≥nlog⁡2(n/s)U\ge n\log_2(n/s) for row-local networks; algebras in which the permanent is a functional of a product have dimension at least (nn/2)\binom n{n/2}; pieces have saving ρ≥1/2\rho\ge1/2 (rank form; Anthropic's observation); and exact colouring filters for Hamiltonicity need q≥n−4q\ge n-4 colours. On paper we prove U≥(1−o(1))nlog⁡2nU\ge(1-o(1))n\log_2n for vertex-local networks for the Tutte polynomial off the integer hyperbolas, and ρ≥3/8\rho\ge3/8 for correlated decompositions of full grid levels. We cite 4545 Lean theorems, with standard axioms only. Every barrier is about a named model: in Anthropic's general model no unconditional bound on UU exists without separating P\mathrm P from P#P\mathrm P^{\#\mathrm P}, and an unconditional cap on oblivious algebraic algorithms would separate VP\mathrm{VP} from VNP\mathrm{VNP}.

Primarily AI-generated textHuman understanding: some partsExponential Time HypothesisSATTutte polynomialcorrelated decompositionscut rankengine barrier problemtensor networks
Nov 06, 202624 pages
PDFView work

cs.LO — Logic in Computer Science

Formalization of Robust Strictly Positive Real Synthesis for Fourth-Order Interval Polynomial Families

Contributed by Tiancheng Xu, Wensheng Yu

That every robustly Hurwitz-stable fourth-order interval polynomial family admits a common strictly positive real (SPR) numerator was conjectured by Anderson et al. and proved by Yu and Wang. In this paper, we present a complete formalization of this classical synthesis theorem in the Lean~4 interactive theorem prover.

Primarily AI-generated textHuman understanding: all partsHurwitz stabilityLean 4formal verificationinterval polynomial familyproof reconstructionstrictly positive real synthesis
Nov 06, 202613 pages
PDFView work

math.NT — Number Theory

Cumulative Prime Sums and Riemann Zeros: A fine grid, its ripple, and a family of prime races

Contributed by Antonio Mennillo

Summing the primes one after another and taking logarithms gives an increasing sequence of real numbers, σm=log⁡Spm\sigma_m=\log S_{p_m} with SN=1+∑p≤NpS_N = 1+\sum_{p\le N}p, which becomes exponentially dense. The ordinates γn\gamma_n of the zeros of the Riemann zeta function fall on this grid with tiny errors: 1.4⋅10−31.4\cdot10^{-3} at the first zero, 2.4⋅10−72.4\cdot10^{-7} at the fifth, 3⋅10−173\cdot10^{-17} at the twentieth. Part I explains why. The cell of the grid containing a height tt has width (1+o(1))t e−t/2(1+o(1))\sqrt t\,e^{-t/2} (Step Theorem), and every real t>log⁡3t>\log 3 has a node above it within that width, by an argument going back to Bertrand's postulate (Covering Theorem). The precision observed at the zeros is therefore the resolution of the grid, and the same precision holds at every height (Genericity Principle). We compute the first-crossing primes NnN_n with certification up to n=20n=20 and test, in a protocol fixed before the computation, whether the zeros sit closer to the nodes than a generic height. Neither the mean distance to the nearest node (0.2460.246 against 0.2500.250, p=0.92p=0.92) nor the distribution of the position within the cell (Kolmogorov–Smirnov, p=0.79p=0.79) departs detectably from the generic case, and an integer grid used as control behaves in the same way. We also correct the half-exponent law by a factor t′/t\sqrt{t'/t}. Part II shows where the zeros are actually visible. They are not in the position of the nodes but in the ripple: the deviation of the grid from its mean curve B(x)=1+li(x2)−li(4)B(x)=1+\mathrm{li}(x^2)-\mathrm{li}(4). This ripple is a sum of pure oscillations, one per zero; its spectrum shows a peak at each of the first 13 ordinates, with the amplitude predicted by the explicit formula. Under RH the ripple has size e−t/4e^{-t/4} on the grid, much larger than the cell e−t/2e^{-t/2}, and RH is equivalent to this decay rate. The ripple is not centred: on [103,108][10^3,10^8] the sum of the primes stays below li(x2)\mathrm{li}(x^2) for about 97% of logarithmic time, and it first exceeds it at x=109x=109. We place this in a one-parameter family of prime races, ∑p≤xpa\sum_{p\le x}p^a against li(xa+1)\mathrm{li}(x^{a+1}), and prove that under RH the normalized error has mean −1/(2a+1)-1/(2a+1), coming from the squares of the primes. Under RH and LI the limiting logarithmic density of the set where the race is ahead is given by a Rubinstein–Sarnak formula; it moves from 2.6⋅10−72.6\cdot10^{-7} (counting the primes, a=0a=0) to 0.060.06 (summing them, a=1a=1) and tends to 1/21/2 as a→∞a\to\infty, at the rate 12−δa∼1/(2πAlog⁡(A/2π))\tfrac12-\delta_a\sim1/\bigl(2\sqrt{\pi A\log(A/2\pi)}\bigr) with A=a+12A=a+\tfrac12. At a=−1/2a=-1/2 the bias becomes the 12log⁡log⁡x\tfrac12\log\log x of the weighted counting functions of Aoki and Koyama. All theorems are formalized in Lean 4, with the classical results they use as explicit hypotheses.

A mix of human-written and AI-generated textHuman understanding: some partsChebyshev biasLean 4Riemann zerosexplicit formulaprime races
Nov 06, 202629 pages
PDFView work

math.HO — History and Overview

Grothendieck Montpellier. Énoncés des lectures modernisées démontrés.

Contributed by Michel Hua

Working notes of Alexandre Grothendieck, put online by the University of Montpellier, have been transcribed and restated in current notation with a language model; the restatements may contain errors. This appendix proves statements taken from these restatements in seventy-five folders, in commutative algebra, algebraic geometry, plane affine geometry, general and tame topology, category and group theory, homotopical algebra, order theory, algebra and finite combinatorics. Each proof follows a proof checked in the Lean 4 proof assistant with its library mathlib. For each statement the text gives the context of the leaf, the proof, the hypotheses that are superfluous or necessary, and the corrections made to the restatement or to the page. It ends with the list of statements the sections report without a Lean check.

Author comments: v2. Part 1 (Lean appendix): a section on Venken's 1971 example, a non-effective finite equivalence relation that answers a question of the 1973 Buffalo lectures, checked in Lean (part Descente). A section on the "serene" objects and dualisable objects of the IHÉS manuscript "Motifs" (fonds Grothendieck–Illusie), checked in Lean. In the IHÉS notes on K of a triangulated category, the exact sequence K(D) → K(C) → K(C/D) → 0 for a thick subcategory and its Verdier quotient is proved in Lean, with Thomason's counterexample without thickness. Nine figures of the edition beside the statements of folders 70, 74, 78, 79, 80, 84, 86 and 154, each pointing to the facsimile page. Four new references (Dold–Puppe 1980, Lewis–May–Steinberger 1986, FGA III, Venken 1971). Part 2 (open questions): the Buffalo effectivity problem (Problem 14) is answered by Venken's example, with a second example of length 15 (16 in characteristic 2); a figure for the stable graphs of folder 147.

Primarily AI-generated textHuman understanding: some partsGrothendieckLean 4MathlibMontpellier archiveformalisationworking notes
Nov 05, 2026409 pages
PDFView work

math.NT — Number Theory

The parity of the prime-counting function in time xo(1)x^{o(1)}

Contributed by Vaibhav Tulsyan

Computing the prime-counting function π(x)\pi(x) exactly takes x1/2+o(1)x^{1/2+o(1)} steps by the analytic method of Lagarias and Odlyzko, and to our knowledge its parity is known faster only on short intervals: Tao, Croot and Helfgott decide whether an interval of length at most x1/2+cx^{1/2+c} near xx contains an odd number of primes in time x1/2−c+o(1)x^{1/2-c+o(1)}. However, their identity needs the Mobius function μ(d)\mu(d) for all d≤xd\le\sqrt x, and we know of no bound of the form xo(1)x^{o(1)} for the parity, even conditionally. We present deterministic algorithms that output π(x) mod 2\pi(x) \bmod 2 and the parity of the number of primes in any interval [A,B][A,B] in time 2O(n/log⁡n)=xo(1)2^{O(n/\sqrt{\log n})}=x^{o(1)}, where nn is the input bit length. Our approach replaces μ(d)\mu(d) by its residue modulo 2, which is the squarefree indicator again: the number of chains d12∣md_1^2\mid m, d22∣d1,…d_2^2\mid d_1,\dots of depth LL is odd exactly when mm is squarefree, for m<22Lm<2^{2^L}. The parity of π\pi on [A,B][A,B] is then the parity of one count of tuples satisfying O(log⁡n)O(\log n) multiplications, which Anthropic's counting engine evaluates through a network whose variables have geometrically shrinking widths. We prove both theorems in Lean 4 (piParity_TM_rate, piIntervalParity_TM_rate; axioms propext, Classical.choice, Quot.sound). The result does not give deterministic prime finding or the exact value of π(x)\pi(x): the parity can be even on every interval one queries, and exact counts seem to need iterated products, for whose product-tree verifiers we prove a lower bound in Lean. The constants are astronomical, and the result rests on Anthropic's Lean development of its claimed refutation of the Exponential Time Hypothesis, which is under review.

Primarily AI-generated textHuman understanding: some partsExponential Time HypothesisMobius functiondeterministic prime findingdivisor chainsparity of pi(x)prime-counting functionsquarefree numbers
Nov 05, 20269 pages
PDFView work

math.NT — Number Theory

Class numbers, square roots and quadratic non-residues in time 2O(n/log⁡n)2^{O(n/\sqrt{\log n})}, assuming the new #SAT algorithms

Contributed by Vaibhav Tulsyan

Basic counting problems of computational number theory have proven deterministic bounds that are fixed powers of the input. The class number h(D)h(D) of an imaginary quadratic discriminant takes ∣D∣1/2+o(1)|D|^{1/2+o(1)} steps unconditionally and ∣D∣1/5+o(1)|D|^{1/5+o(1)} under the generalised Riemann hypothesis (GRH); exact divisor sums ∑m≤xτ(m)\sum_{m\le x}\tau(m) take x1/3+o(1)x^{1/3+o(1)}. However, none of these bounds is of the form Xo(1)X^{o(1)}, even conditionally. We present deterministic algorithms in time 2O(n/log⁡n)2^{O(n/\sqrt{\log n})}, where nn is the input bit length, for the number of reduced forms of discriminant −N-N (for fundamental discriminants, h(−N)h(-N)) and for ∑m≤xτ(m)\sum_{m\le x}\tau(m), ∑m≤xσ(m)\sum_{m\le x}\sigma(m) and the Gauss circle count. Our approach writes each answer as a count of solutions of equations with one or two products and evaluates it with Anthropic's counting engine through one network library with O(n)O(n) shared bits. The same library gives the least square root modulo any mm and the least quadratic non-residue modulo a prime. These are not new bounds (OpenAI's results on the quasi-Riemann hypothesis and on deterministic polynomial factorisation over Fp\mathbb{F}_p give polynomial time modulo a prime), but they are machine-checked. We prove the seven resulting theorems in Lean 4 (for example hForm_TM_rate; axioms propext, Classical.choice, Quot.sound): a finite-alphabet Mathlib Turing machine outputs the answer within ⌊C⋅2Cn/log⁡2(n+2)⌋\lfloor C\cdot2^{Cn/\sqrt{\log_2(n+2)}}\rfloor steps on every input. Lean proves the count of Gauss's reduced forms; its equality with the ideal class number is classical and not formalised. The constants are astronomical, the machines use exponential space, and every result rests on Anthropic's Lean development of its claimed refutation of the Exponential Time Hypothesis, which is under review. Version 2 corrects the claims of version 1 about non-residues and square roots.

Primarily AI-generated textHuman understanding: some parts
Nov 05, 202612 pages
PDFView work

cs.LO — Logic in Computer Science

Voblint: End-to-End Soundness of a Context-Sensitive Goblint-Style Analyzer in Isabelle/HOL

Contributed by Manuel Lerchner

Goblint-style analyzers solve side-effecting equations, where evaluating one unknown can contribute to other unknowns. An existing Isabelle/HOL proof establishes solver partial correctness without connecting the equations to execution. We mechanize this connection for a scalar imperative language with recursive procedures but no pointers or heap memory. We adapt the local traces of Schwarz et al. to record procedure activations and the callers resumed by returns. A context policy relates concrete calls to one or more analysis contexts. A cover assigns sets of stores to program points and contexts as candidate overapproximations of reachability. We prove that five local obligations suffice for a cover to contain every valid trace’s final store in every admitted context, on any control-flow graph. A post-solution assigns abstract values that bound each equation’s result and side effects. When the abstract operations are sound and the routing agrees with the context policy, every post-solution induces a cover. The verified solver computes a post-solution when it returns. For every accepted configuration, whenever the Isabelle-defined analyzer returns a report, it overapproximates the stores reached by finite source executions from the prescribed initial states. Whenever execution reaches a check, PROVED guarantees that its condition holds, and REFUTED guarantees that it fails. Neither verdict establishes reachability. This source-level guarantee applies to the Isabelle-defined analyzer; solver termination, parsing, and correctness of generated code are not established.

A mix of human-written and AI-generated textHuman understanding: all partsIsabelle/HOLabstract interpretationcalling contextsinterprocedural analysisside-effecting constraint systemsverified static analysis
Nov 05, 202618 pages
PDFView work

cs.DS — Data Structures and Algorithms

Counting Eulerian circuits in subexponential time, assuming the new #SAT algorithms

Contributed by Vaibhav Tulsyan

Counting the Eulerian circuits of an undirected graph is #P-complete, even for planar 4-regular graphs, while for directed graphs the BEST theorem counts them in polynomial time. However, we are unaware of any exact algorithm for undirected graphs of bounded degree that runs in time 2o(m)2^{o(m)}, where mm is the number of edges. We show that such an algorithm follows from the exact counting of Hamiltonian cycles that we proved earlier on top of Anthropic's claimed #SAT algorithm. The reduction is classical: by Kotzig's description, the Eulerian circuits of GG are in bijection with the Hamiltonian cycles of the line graph of the double subdivision of GG, which has 3m3m vertices and at most (Δ+1)m(\Delta+1)m edges. We prove in Lean 4 (theoremEuler, theoremEuler_noIso, theoremEuler_rate; axioms propext, Classical.choice, Quot.sound) that for every δ>0\delta>0 and Δ\Delta a finite-alphabet Mathlib Turing machine outputs the number of Eulerian circuits of every graph of maximum degree at most Δ\Delta within ⌊C(n+2)C2δm⌋\lfloor C(n+2)^C 2^{\delta m}\rfloor steps, and within ⌊C2δm⌋\lfloor C 2^{\delta m}\rfloor steps when there is no isolated vertex; and that one machine does so for all graphs within ⌊C(n+2)C2Cmlog⁡2(Δ+2)/log⁡2(m+2)⌋\lfloor C(n+2)^C 2^{Cm\log_2(\Delta+2)/\sqrt{\log_2(m+2)}}\rfloor steps. The factor (n+2)C(n+2)^C pays for reading the n2n^2-bit adjacency matrix and cannot be dropped. The bijection is checked by brute force on twelve small graphs, for example 132 circuits for K5K_5. The formal object is Kotzig's transition-system definition; its agreement with Mathlib's Eulerian walks is not formalised. The constants are astronomical, and the proof rests on Anthropic's Lean development of its claimed refutation of the Exponential Time Hypothesis, which is under review.

Primarily AI-generated textHuman understanding: some parts#P-completenessEuler toursEulerian CircuitsHamiltonian cycleexact countingline graph
Nov 04, 20268 pages
PDFView work

math.CO — Combinatorics

Three-colour cuboids from four-colour cubes

Contributed by Jason Davies

We determine the least number of four-colour cubes that guarantees a cuboid with monochromatic faces using exactly three colours. Each source uses all four colours of a fixed palette; only proper rotations are allowed, and interior faces need not match. For integer side lengths 2≤a≤b≤c2\le a\le b\le c, the sharp threshold for the corner-and-edge frame is max⁡{16a−3,4(a+b+c)−16,⌊(24c−1)/5⌋}\max\{16a-3,4(a+b+c)-16,\lfloor(24c-1)/5\rfloor\}, and the complete-cuboid threshold is max⁡{abc,16a−3,⌊(24c−1)/5⌋}\max\{abc,16a-3,\lfloor(24c-1)/5\rfloor\}. The three frame bounds arise from colour-bucket capacity, the number of positions and balanced checkerboards. The upper bound combines corner containment, a weighted graph selecting edge directions, and Hall's theorem. For cubic frames the threshold is 16n−316n-3, with exactly two failing collections of size 16n−416n-4. For n≥3n\ge3 we classify every failure of size at least 14n14n and count these collections and the inclusion-maximal ones. The case n=2n=2 answers the threshold question in Problem 2 of Berkove, Eickemeyer and Schulman (2018). All threshold, stability and counting results are formalised in Lean.

Primarily AI-generated textHuman understanding: some partsHall's theoremLean formalisationMacMahon cubescolour cubescuboidsextremal combinatorics
Nov 04, 202616 pages
PDFView work

math.CO — Combinatorics

Kernel Dimension of the Z/2 Connection Laplacian on a Finite Simple Graph (A Formalisation in Lean 4 / Mathlib v4.11.0)

Contributed by Jesus Vilela Jato

We present a Lean 4/Mathlib v4.11.0 formalization of the kernel-dimension theory of the Z/2\mathbb{Z}/2 connection Laplacian on finite simple graphs equipped with designated wrap edges. Each edge carries either the identity or the coordinate-swap matrix. A Hadamard–Kronecker change of basis decomposes the resulting rank-two connection Laplacian into the ordinary and signed graph Laplacians. An analogous splitting holds for the scalar Laplacian of the associated two-sheeted cover. A connected component is balanced precisely when its covering preimage has two connected components, equivalently when its sign holonomy is trivial along every closed walk. Consequently, the nullity of the signed Laplacian equals the number of balanced connected components, while the nullity of the full connection Laplacian equals the number of connected components plus the number of balanced components. For the flat connection, the nullity is twice the number of connected components. We also formalize exact characteristic polynomials and eigenvalue multisets, including multiplicities, for explicit ordinary and one-wrap signed cycle matrices for n≥3n \geq 3. Transfer to general connection-graph encodings remains conditional on specified matrix-reindexing identities. The contribution is a machine-checked formalization, exposition, and documented verification of results rooted in classical signed-graph spectral theory, rather than a claim of priority for those identities. The accompanying repository preserves proof artifacts, computational cross-checks, historical verification evidence, and documented corrections.

Primarily AI-generated textHuman understanding: some partsAI-assisted mathematicsLean 4connection Laplacianformal verificationgraph coverssigned graphsspectral graph theory
Nov 04, 202618 pages
PDFView work

math.CO — Combinatorics

The ten minimum universal sets of MacMahon cubes

Contributed by Jason Davies

A collection of six-coloured MacMahon cubes is universal if eight of its cubes can be selected to build a 2×2×22\times2\times2 model of any target variety, with matching exterior colours and no internal matching requirement. We prove that exactly ten labelled collections attain the known minimum size of twelve, even when repeated varieties are allowed, resolving the conjectures of Johnson and Roldán. Usable-cube inequalities force a symmetric multiplicity matrix with row and column sums two; corner coverage then forces two disjoint triangles in Conway's tableau. The written proof is elementary and requires no exhaustive search. The classification and its discrete geometric interpretation are formalised in Lean 4. Exhaustive computation provides a separate check and additional target-count distributions.

Primarily AI-generated textHuman understanding: some partsConway's tableauEight Blocks to MadnessLean 4MacMahon cubesuniversal sets
Nov 02, 20267 pages
PDFView work

math.NT — Number Theory

Every real primitive Dirichlet L-function has de Bruijn–Newman constant at most 9/32: a kernel-checked proof in Lean 4

Contributed by Peter W. Murphy, MD

Let χ be a real primitive Dirichlet character of conductor N ≥ 3 and parity k ∈ {0,1}. Let Λ(s,χ) = (N/π)^{(s+k)/2} Γ((s+k)/2) L(s,χ) be its completed L-function, and let H^χ_t(z) = ∫_0^∞ e^{tu²} Φ_χ(u) cos(zu) du be the de Bruijn–Newman heat flow of Λ(·,χ), normalised so that H^χ_0(z) = (1/8) Λ(1/2 + iz/2, χ). We give a proof, checked by the Lean 4 kernel, that for every such χ and every t ≥ 9/32 all zeros of H^χ_t are real. Equivalently, the generalised de Bruijn–Newman constant satisfies Λ_χ ≤ 9/32. The mathematics is not new, and we say exactly whose it is. De Bruijn's strip-contraction theorem (1950) gives Λ_χ ≤ D²/2 whenever the zeros of H^χ_0 lie in |Im z| ≤ D. Freire, González-Riquelme, Muñoz, Poblete and Salinas observed (arXiv:2610.27343, Remarks 3.1 and 3.4) that the zero-free half-plane Re s > 7/8 for Dirichlet L-functions asserted by OpenAI would give D = 3/4, and hence Λ_χ ≤ 9/32. What this paper adds is a complete formal proof of that composition. For conductors up to 400, FGMPS's unconditional bounds are stronger for 136 of the 242 characters; what is new is that 9/32, for every conductor, is a kernel-checked theorem. OpenAI's half-plane enters as their own kernel-checked Lean theorem. Every other step is proved in Lean on top of Mathlib: de Bruijn's theorem for a general class of kernels, the identification of the theta integral with Mathlib's completed L-function, and Gauss's sign theorem for real primitive characters. The final theorem depends only on the axioms propext, Classical.choice and Quot.sound. In local, unsandboxed replays five checkers accept it: Lean's kernel (run twice), nanoda, and the con-leche/con-ron pair. All five reject a deliberately unsound control. A sandboxed Comparator run against a separately written challenge also accepts it. That run was made by another agent session, and the auditor reproduced its solution export byte for byte. The result rests on OpenAI's Lean proof, whose accompanying manuscript is unrefereed. It is not progress on the Generalised Riemann Hypothesis, which is the statement Λ_χ ≤ 0. A short, separable section records two companion results for ζ that use no OpenAI code, Λ ≤ 225/512 and ψ(x) = x + O_ε(x^{31/32+ε}), both from Cureton and Thorner's half-plane Re s > 31/32. Code, verification records and archive: https://github.com/DrMurphyIsIn/real-dirichlet-dbn-lean (release v1.0.0); DOI 10.5281/zenodo.23840082.

Primarily AI-generated textHuman understanding: some partsDirichlet L-functionsGauss sumsLean 4Mathlibde Bruijn-Newman constantformal verification
Nov 02, 202625 pages
PDFView work

cs.DS — Data Structures and Algorithms

Counting Hamiltonian cycles in sparse graphs in subexponential time, assuming the new #SAT algorithms

Contributed by Vaibhav Tulsyan

In October 2026 two manuscripts claimed refutations of the Exponential Time Hypothesis by deterministic algorithms for #k\#k-SAT, each with a Lean formalisation of its top-level statement. Neither result applies directly to connectivity problems such as Hamiltonicity, because no linear-size CNF encoding of "this edge set is a single cycle" is known. This paper derives a corollary of the Anthropic manuscript: assuming three of its internal results (a network-to-clique reduction, an algorithm for cliques of all levels, and the existence of its "pieces"), the number of Hamiltonian cycles of a graph with nn vertices and at most DnDn edges can be computed exactly and deterministically in time O(2δn)O(2^{\delta n}) for every δ>0\delta>0, and in time 2O(max⁡(m,n)/log⁡n)2^{O(\max(m,n)/\sqrt{\log n})} for a graph with mm edges. A rank-encoded variant of the construction gives 2O(nlog⁡dˉ/log⁡n)2^{O(n\log\bar d/\sqrt{\log n})} for average degree dˉ\bar d. Deterministic decision, search and Hamiltonian-path counting follow, and so do exact sparse TSP with polynomially bounded weights, exact counting of directed Hamiltonian cycles, and ATSP. The result is not a standalone breakthrough; it stands or falls with the claimed refutation. The ingredients are known: the folklore matrix-tree identity on 22-factors, the fermionic (Berezin) matrix-tree theorem of Caracciolo, Jacobsen, Saleur, Sokal and Sportiello, and the blob partitions of Cut&Count. What is new is the observation that connectivity can be encoded with O(1)O(1) bits per edge through a Grassmann determinant whose only non-local part is a sign, and that this sign costs only O(g3)O(g^3) bits for gg blobs, so the whole construction is a network in the sense of the manuscript, whose value is n⋅#HC(G)n\cdot\#\mathrm{HC}(G). Every theorem we claim is formally verified in Lean, end to end, on top of the manuscript's own Lean development: the three counting theorems, the decision, search and path corollaries, sparse TSP, directed Hamiltonian cycles and ATSP, using only the standard axioms, with fresh kernel replays. The Lean sources are at https://github.com/xennygrimmato/eth-hamiltonicity. We also record weaker results that rest only on the machine-checked top-level theorems: the parity of #HC(G)\#\mathrm{HC}(G) for every graph in time 2O((m+n)/log⁡(m+n))2^{O((m+n)/\sqrt{\log(m+n)})} (machine-checked in Lean, with the hypotheses discharged by the labs' own Lean proofs), and one-sided randomized decision. We describe what is proved, what is checked numerically, what is formalised, what is assumed, and what the limitations are.

Primarily AI-generated textHuman understanding: some partsHamiltonian cycle; ETH; matrix-tree theorem; Grassmann algebra; Cut&Count; TSP
Oct 31, 202629 pages
PDFView work

math.LO — Logic

A true theorem Lean can state but can never verify

Contributed by William Banks

We give an expository account of a mathematical result that the Lean proof assistant can formally state but, by Gödel's second incompleteness theorem, can never verify, and which it also does not refute, namely, the consistency of Lean's own underlying type theory. Working in ZFC\mathsf{ZFC} extended by the existence of infinitely many inaccessible cardinals, we sketch the construction of a set-theoretic model of Lean's Calculus of Inductive Constructions (with its universe hierarchy, quotient types, and choice), outline the proof of a soundness lemma, and conclude that no derivation of False\mathtt{False} exists. The argument is the model-theoretic consistency proof carried out in full by Carneiro, building on Werner's set-theoretic interpretation of the same calculus; all substantive results are due to these authors, and this paper claims no new mathematics. We explain why this theorem lies outside Lean's own reach, note that Gödel's second incompleteness theorem has itself been verified by Lean's kernel for first-order arithmetic, and discuss why every consistency proof ultimately rests on trust rather than proof.

A mix of human-written and AI-generated textHuman understanding: all partsLeanconsistencyinaccessible cardinalsincompletenessproof assistantstype theory
Oct 29, 20266 pages
PDFView work

math.LO — Logic

The Euclidean algorithm is not optimal among uniform processes

Contributed by Jason Davies

Reusing a stored Euclidean prefix, we show that every pair a≥ba\geq b has a derivation of gcd⁡(a,b)\gcd(a,b) from a,ba,b with O(log⁡a/log⁡log⁡a)O(\log a/\log\log a) applications of the remainder function alone; Euclid's algorithm needs order log⁡a\log a in the worst case. These derivations bound the intrinsic complexity of gcd and coprimeness by the same order, refuting Moschovakis's conjectured logarithmic lower bounds for uniform processes; by his best-uniform-process theorem, a single uniform process attains this bound. The Main Conjecture for algorithms remains open. We also prove an Ω(log⁡log⁡a)\Omega(\log\log a) lower bound on this complexity for almost all coprime pairs and give, for each ε>0\varepsilon>0, a nondeterministic register program computing gcd that, on every input a≥b≥1a\geq b\geq1, has a successful computation using at most εlog⁡a+O(1)\varepsilon\log a+O(1) remainder calls. The upper bound also answers negatively an open problem of van den Dries and Moschovakis on the closure depth of the gcd. The main bounds and the refutations are formalised in Lean 4; the best-uniform-process theorem is cited.

Primarily AI-generated textHuman understanding: some partsEuclidean algorithmLean 4closure depthgreatest common divisorintrinsic complexityremainder functionuniform processes
Oct 29, 202616 pages
PDFView work

cs.CC — Computational Complexity

Deterministic Factoring in Time No(1)N^{o(1)}

Contributed by Isaac Rudich, Louis-Martin Rousseau

The current best upper bound for deterministic factoring is N1/5+o(1)N^{1/5+o(1)}. We provide a Lean certificate that there exists a deterministic Turing machine that computes the smallest prime factor of every NN in No(1)N^{o(1)} steps: for every k≥1k\ge 1 it runs within Ck 2n/kC_k\,2^{n/k} steps on nn-bit inputs. The algorithm reduces factoring to counting divisors with prescribed leading bits, and counts them by leveraging the counting engine used to refute the Exponential Time Hypothesis (ETH). The Lean statement that a reader must check to verify the proof is only 13 lines and only uses Mathlib. The full proof is about 35,000 lines. This note was written less than 24 hours after the ETH refutations were posted. No human-readable explanation of these results exists yet, and their Lean proofs are long: Anthropic's alone runs to about 152,000 lines. Our proof re-proves only the part of the counting engine it needs and imports nothing from those developments. We hope this application, with its short statement, serves as a stepping stone for those working to understand the engine; a follow-up paper will explain this proof in detail.

A mix of human-written and AI-generated textHuman understanding: some partsExponential Time HypothesisLeancounting algorithmsdeterministic factoringformal verificationinteger factorization
Oct 29, 20266 pages
PDFView work

cs.LO — Logic in Computer Science

On the scope of computability and formal axiomatic systems

Contributed by Jon Bohlin

This survey explores the theoretical scope of effective computation and formal axiomatic systems, emphasizing a constructive perspective based on computable trees and their associated path spaces. No new technical results are presented; rather, the aim is to synthesize established results from computability theory and mathematical logic into a unified framework that clarifies what can be computed in principle, complementing the classical emphasis on undecidability results. It is argued that standard models of computation, such as Turing machines and equivalent formalisms, are computationally saturated: any effective extension of their instruction sets does not enlarge the class of effectively computable functions and algorithms. This saturation corresponds, on the logical side, to the representational completeness of Robinson arithmetic, which is sufficient to encode all computable functions despite being finitely axiomatized. The survey proceeds by showing how standard models of computation give rise to computable trees whose infinite paths correspond to complete and consistent, but typically non-computable, extensions. This construction links effectively closed classes in Cantor space with spaces of completions of formal theories and clarifies the boundary between effective computability and logical possibility. Since Cantor space is homeomorphic to the classical Cantor set, this framework provides a natural bridge between discrete computability-theoretic and logical structures on the one hand, and continuous topology on the other.

Primarily human-written textHuman understanding: all partsComputability
Oct 29, 20265 pages
PDFView work

math.CO — Combinatorics

The maximum Laplacian ratio of a tree: a complete answer to a question of Brualdi and Goldwasser, kernel-checked in Lean

Contributed by Peter W. Murphy, MD

For a tree TT with Laplacian L(T)L(T), Brualdi and Goldwasser (1984) introduced the Laplacian ratio π(T)=per⁡L(T)/∏vdeg⁡v\pi(T)=\operatorname{per} L(T)/\prod_v\deg v and asked which tree on nn vertices maximizes it. We answer the question for every nn. For every n≥4n\ge 4 the maximum is attained by a spider of cherry arms: a centre carrying pendant paths of length two (cherries) and arms, an arm being a vertex that carries cherries. For n≥492n\ge 492 the centre carries only arms, almost all with five cherries, and the exceptional arms are fixed by 6(n−1) mod 116(n-1)\bmod 11 through an explicit rule; for 4≤n≤4914\le n\le 491 the maximizer is given by an explicit table. Along the way we determine the exact exponential growth rate of the maximum, 64621ρn≤max⁡∣T∣=nπ(T)≤2ρn−1\tfrac{64}{621}\rho^{n}\le\max_{|T|=n}\pi(T)\le 2\rho^{n-1} with ρ=(621/64)1/11\rho=(621/64)^{1/11}, and prove the sharp inequality behind it: every pendant subtree bb has matching weight at most ρ∣b∣\rho^{|b|}, with equality exactly for the five-cherry arm. The whole argument is formalized in Lean 4 with Mathlib and checked by the Lean kernel, depending only on Lean's three standard axioms. Large parts of it are certificates: exact data produced by untrusted generators and checked by the kernel. We explain the mathematics, show where each piece lives in the formal development and why it is organized that way, and discuss what the answer and the method suggest. Code, certificates and the Lean formalization: https://github.com/DrMurphyIsIn/brualdi-goldwasser (release v1.4.4; Zenodo doi:10.5281/zenodo.22983412).

A mix of human-written and AI-generated textHuman understanding: some partsLaplacian permanentLean 4Mathlibextremal graph theoryformal verificationtrees
Oct 27, 202631 pages
PDFView work

cs.CC — Computational Complexity

Polynomial Fault Detection Without Bounded Width: Exact Reachable Sets in Priority Controllers

Contributed by Idris Ali Shaik

Circuit-width restrictions explain several polynomial cases of automatic test pattern generation. We give a different explanation for an arbitrary-size extension of the c432 priority controller, including a subfamily with linear treewidth and net cut-width in its native layout. For a specified first-stage bridge fault, we characterize exactly the reachable qualifier sets and construct a primary input realizing each one. On drive-one inputs where the first selector flag changes, the healthy set is the target singleton; the faulty sets are precisely the target-containing sets with one request bus and all nonempty sets with at least two buses. Drive zero is undetectable. This image reduces detection to comparing decoder values on sets. For supplied guarded decoders, built from zero, positive channel leaves, disjunction and conjunction of one computed child with negative channel literals, supporting paths and dual-Horn reasoning find a detecting set in O((n+q)G) time for n channels, q outputs and counted decoder size G, or O(G) for formula forests. Unsatisfiable instances of the complete guarded native CNF encoding have resolution refutations with O(N³) inferences, where N is the encoding size. Detection is P-complete, while minimum-set optimization and counting detecting sets are NP-hard and #P-complete, respectively. A specified final-qualifier stuck-at fault makes detection NP-complete on shared guarded decoders. The exact first-stage bridge-image statements are formalized in Lean and registered as PALOMAR-2026-10-19-000010, version 1.

A mix of human-written and AI-generated textHuman understanding: all partsBoolean satisfiabilityautomatic test pattern generationfault detectionpriority controllersproof complexity
Oct 23, 202647 pages
PDFView work

math-ph — Mathematical Physics

Beyond the Event Horizon: An Operator-First Theory of Persistent Geometry and Black Hole Dynamics

Contributed by Jeromie Beasley

A black hole carries one wall of each kind. Its horizon is a geometric fold: in the right coordinate it is smooth, and nothing breaks there. Its innermost stable circular orbit is a spectral wall, a Jordan block where steady circling turns into a plunge. This paper builds both kinds of wall exactly in a setting where every step can be proved and computed, and then compares them, structurally, with black holes. The setting is the shape space of four bodies. Its kinetic metric is the Bures metric of a real qutrit, and its one genuine wall, the coplanar configurations, is a fold at finite distance. Across it a tetrahedron meets its mirror image. The transport operator A(H) = TH + HT − 2Tr(TH)G is self-adjoint in the kinetic metric. Read in the Gram frame, its back-coupling vanishes like σ₃², and it forms a Jordan block whose square-root branch is exactly the orientation double cover. Lifted to the cover, it is analytic, and the wall point is a plain double point at the tip of a cone with slope 2|t₁−t₂|√(1−δ²). Both readings are exact. What a single eigenvector reports can fail at the wall; the eigenvalue pair and its trace-log ledger come through exact, and a loop through the mirror leaves a sign. New in edition 10 - Reflection and refraction on the projector metric. A wave meeting a step in the metric reflects through the metric along the step and the Clairaut constant C alone: Γ = (√(a₁−C) − √(a₂−C)) / (√(a₁−C) + √(a₂−C)). The transverse metric drops out at a sharp step. Total reflection begins exactly where a geodesic turns, so the optical threshold is a turning point. A change of spectral gap reflects with the peel coordinate tanh(½ ln Δ₂/Δ₁). - One Gram determinant does two jobs: it sets the wave admittance, and it caps the Berry curvature a path can feel (the angle safeguard of the intrinsic quantum geometric tensor). - Mirror and matched load. The polar stratum is a perfect mirror, |Γ| = 1. A Killing horizon, polar in the same sense, is a matched load, Γ = 0. - The photon ring, read by the same generator as the ISCO: each half orbit dims an image by e^−π = 0.0432, a value that belongs to the uncharged hole alone; charge lowers it. - The fermion record: its offset is a point on the same reflection chart, tanh(ħω/2k_BT_H). - The reflection tests were pre-registered before they ran, and each was pushed several ways: 400 random sharp steps, three smooth profiles, reciprocity, flux balance, the transverse metric in a thick layer, total reflection, and the gap form. Main results - The coplanar wall is a fold, and its distance is a Bures angle: arcsin√ε = arccos√F. - Quantum Fisher information on the shape space is eight times the shape kinetic energy wherever the rank is constant, and fidelity is blind to the mirror. - Two kinds of wall: spectral (a Jordan block in every frame) and geometric (a fold that a signed coordinate unfolds). The ISCO is spectral, at the point where gravity's effective power p = 2 + 6M/r reaches the inverse cube. The horizon is geometric. - Any distance potential is even across the wall, with stiffness 2∂V/∂w₃. A thin disk holds the shape at its own frequency ν. Gravity holds the square at ω = √(2(2√2−1)); its exact potential along the lifted square is given in closed form, and its stiffness turns over for a rhombus thinner than diagonal ratio k* = 0.144557. - Structural comparisons: Petrov types through Majorana stars (Kerr is type D), merging ringdown overtones, the horizon's surface resistance as a matched load (376.73 Ω), Bell violation by a Hawking pair, Ramanujan's mock theta functions, and the mirror rule for knots. The metric throughout is the intrinsic kinetic metric of the shape space, never a spacetime metric. Every statement about black holes is a structural comparison, and every claim carries its grade (derived, measured, cited, or structural) where it is made. Files - bh_paper_v10_1.pdf: the paper (56 pages). - bh_paper_v10_1.html: the web edition, with its cover; it runs no scripts. - bh_mixer_v10.html: the Event Horizon Mixer, edition 10. It runs offline in any browser and computes every curve live: the photon-ring orbits, the layered step, the reflection chart with the horizon and the fermion record, the sine guard, and the tip-and-tail matrices. Its Synchronize mode drives every eye from one wall dial, and its "Synchronize the universe" eye shows the connection energy draining as a ring of fields falls into step. - bh_v10_1_code_and_sources.zip: LaTeX source, figures, every check script with its saved output, the pre-registrations, the proof log and the ideas ledger, and a README. Each script states its kill condition before it runs (Python 3: numpy, scipy, sympy, mpmath, matplotlib). AI-assisted: the ideas and research direction are the author's; AI tools were used for literature search, computation, drafting and typesetting, and every number was checked by the scripts in the archive.

A mix of human-written and AI-generated textHuman understanding: some parts
Oct 20, 202656 pages
PDFView work

math.NT — Number Theory

log⁡p2⋅log⁡p(3+2)\log_p 2 \cdot \log_p(3+\sqrt2) is not a pp-adic linear form in logarithms

Contributed by Shawn Krisman

Let pp be a prime, Cp\mathbb{C}_p the completion of an algebraic closure of Qp\mathbb{Q}_p, Q‾\overline{\mathbb{Q}} the algebraic numbers in Cp\mathbb{C}_p, LL the Q\mathbb{Q}-vector space of pp-adic logarithms of algebraic numbers, and L=Q‾+Q‾L\mathcal{L}=\overline{\mathbb{Q}}+\overline{\mathbb{Q}}L the space of pp-adic linear forms in logarithms of algebraic numbers with algebraic coefficients. We prove, in Lean 4 with Mathlib and from the three standard axioms only, that log⁡p2⋅log⁡p(3+2)∉L\log_p 2\cdot\log_p(3+\sqrt2)\notin\mathcal{L} for every prime p≡±3(mod8)p\equiv\pm3 \pmod 8, together with a family of similar statements for real quadratic fields, and the general principle behind them: if σ\sigma is a continuous automorphism of Cp\mathbb{C}_p fixing a nonzero t∈Lt\in L and moving u∈Lu\in L to a conjugate σu≠±u\sigma u\neq\pm u of finite orbit, then tu∉Ltu\notin\mathcal{L}. This is G. Diaz's use of complex conjugation with an element of Gal(Q‾p/Qp)\mathrm{Gal}(\overline{\mathbb{Q}}_p/\mathbb{Q}_p) in its place; the complex analogue log⁡2⋅log⁡(3+2)∉L\log 2\cdot\log(3+\sqrt2)\notin\mathcal{L} is open. The deep input is Roy's form of Waldschmidt's linear-subgroup theorem for Gad0×Gmd1\mathbb{G}_a^{d_0}\times\mathbb{G}_m^{d_1} over Cp\mathbb{C}_p, with a derivative subspace, which we also prove in Lean, from Philippon's multiplicity estimate; the strong six exponentials theorem and the inhomogeneous Baker--Brumer theorem in two logarithms over Cp\mathbb{C}_p follow. The pp-adic linear-subgroup theorem has been used since Laurent and Roy, but we were unable to locate a proof written for Cp\mathbb{C}_p of the version with derivatives. The Lean development is the proof of record; the paper explains the statements, the route, and how to check the certificate. The code is available at https://github.com/telaviv/p-adic-log-products.

Primarily AI-generated textHuman understanding: no partsLean 4Mathlibformal verificationinterpolation determinantslinear forms in logarithmslinear-subgroup theoremmultiplicity estimatesp-adic logarithmp-adic transcendencestrong six exponentials theorem
Oct 20, 202614 pages
PDFView work

math.CO — Combinatorics

An intrinsic interval-deletion characterization of digraph support families

Contributed by Michael Mislan

For a finite directed graph with loops allowed, its supported subsets are those in which every vertex has an in-neighbour within the subset. We characterize exactly which set families arise this way on their original ground set. Starting from the power set, a legal step chooses an inclusion-maximal remaining nonmember, selects a previously unused root absent from every target-family member below it, and deletes the rooted interval. A family is a digraph support family if and only if some legal deletion sequence reaches it. The maximal residual set may follow any fixed valid policy; only roots require branching. Successful traces have at most one step per vertex and reconstruct a realizing digraph. Consequences include exact root sets and trace length, a finite recognizer, conventional NP membership for explicit lists, projection, deletion and product closure, and RAF realizability criteria using the published antimatroid characterization. The characterization and selected consequences and trace-checking interfaces are verified in Lean 4; conventional statements and computational examples are identified separately.

Primarily AI-generated textHuman understanding: some partsLean formalizationRAF realizabilitydigraph support familiesinterior operatorsrooted-interval deletionsingle-head Horn theories
Oct 20, 202618 pages
PDFView work

cs.LO — Logic in Computer Science

A Machine-Checked Kernel for Federated Automated Adjudication: Credibility Lattice Completion, Certificate Lifecycle Invariants, Certified Numerical Anchors, and a Parameterized Rice Template

Contributed by Chepin Zhang

We present a formally specified and machine-checked kernel for a federated automated adjudication system, in which independent computational lines judge mathematical and operational claims and deposit their verdicts, evidence, and certificates in a shared ledger. The kernel comprises five components. (i) A three-rung, three-track credibility lattice obtained as a completion of a legacy five-element poset: the completion is justified by an exhaustive enumeration over all 11^{3}=1331 ordered triples and is fully re-formalized in Lean 4, where the equational lattice laws, the order axioms, and the extremality properties of join and meet are all proved by the decide procedure over the finite carrier. (ii) A five-state certificate lifecycle machine with nine legal transitions and machine-checked invariants, likewise re-formalized in Lean 4; the formalization caught a specification flaw in one invariant (the originally stated grant-gating condition is false), and we report the corrected, machine-proved form. (iii) Certified numerical anchors: uniqueness of the gauged fixed point of circulant entropic-optimal-transport (Sinkhorn) systems, established by a Krawczyk interval operator with outward rounding across a six-instance family (k in {6,10 }, varepsilon in {1,1/2,1/5 }, later extended to ten instances), together with a second anchor family of five auction-algorithm assignment instances certified by interval dual brackets. We state plainly that the certification of these numerical anchors is carried by the Python interval-arithmetic layer; the attempted port to the Lean 4 interval library leancert is blocked by structural capability boundaries of that library (absence of the logarithm from its supported expression grammar and infeasibility of its determinant computation at the required dimensions), and the Lean files are formal statements, not machine-verified certificates. (iv) A parameterized Lean 4 template for Rice-type undecidability, consisting of a bridge theorem, an extensionality lemma, an instantiation generator, and discharged instances of increasing difficulty. (v) A minimal trusted computing base result: the soundness of an interval certificate checker (accept implies correctness), itself machine-proved in Lean 4. All Lean artifacts were verified on cloud infrastructure (Axiom Axle, environment lean-4.28.0) under the strict verify_proof channel, with axiom audits restricted to propext, Classical.choice, and Quot.sound, and no sorryAx. Empirical fuzzing over three certificate families observed zero false accepts; we report rule-of-three 95% upper bounds on the false-accept rate and explicitly do not claim a guarantee.

Primarily AI-generated textHuman understanding: some partsLean 4Rice theoremfederated adjudicationformal verificationinterval arithmeticmachine-checked certificates
Oct 11, 202616 pages
PDFView work

cs.DS — Data Structures and Algorithms

From Snapshots to Processes: Dynamic Contact Algebras as a Foundation for Process-Oriented GIS

Contributed by John Hessler

Geographic information science has argued for three decades that representing change requires moving from time-stamped snapshots to events and processes. This ontological shift has not been matched by a formal foundation with the properties a GIS needs: explicit axioms, representation theorems, and decidable reasoning. We propose dynamic mereotopology, in the form of Vakarelov’s dynamic contact algebras (DCAs), as a candidate foundation. DCAs are point-free with respect to both space and time. Regions are histories, primitive relations include space contact, time contact and precedence, moments are recovered as clusters of the time-contact relation, and properties of time correspond to axioms about regions alone. Using Grenon and Smith’s distinction between SNAP (snapshot) and SPAN (process) ontologies, we argue that DCAs originate on the SNAP side, since they are abstracted from a snapshot model, yet their primitives already carry much of what a SPAN ontology requires. We then identify precisely what is still missing for a process-oriented GIS: process and participation primitives, continuity of change, freedom from global simultaneity, identity under splitting and merging, and granularity. We develop a SPAN-first extension. For two of its components we give full proofs: a point-free continuity axiom, shown to express exactly the intended condition in discrete time and in finitely variable dense time, and a set of correspondences showing which axioms of continuous space hold at every finite resolution of discrete data and which emerge only in the limit of refinement. The remaining proposals are stated as conjectures, and the framework is tested against three case studies: a flood, a wildfire, and a pandemic.

A mix of human-written and AI-generated textHuman understanding: all partsdynamic mereotopology; contact algebra; boolean algebra
Oct 09, 202627 pages
PDFView work

cs.CC — Computational Complexity

A Verified Constructive Reduction of the Cook-Levin Theorem in Lean 4: Bridging the Gap Between Complexity Theory and Formal SAT Encodings

Contributed by Jonathan 𝑓(n) Reed

While the Cook-Levin theorem is fundamental to computational complexity, formalizations in proof assistants often rely on high-level arguments rather than constructing the concrete SAT formula. Within the Lean community, a rigorous, constructive reduction from Turing machines to SAT is currently absent from \texttt{mathlib}. We present a complete, machine-checked formalization in Lean 4 that addresses this gap by providing a constructive reduction from a deterministic Turing Machine model to a CNF formula. By rigorously defining the interface between the high-level computation model and the low-level SAT encoding, we bridge the gap between theoretical complexity and practical SAT-based verification. Our work specifically handles the challenges of verified 3D-variable indexing, injective mapping proofs, and global soundness, providing a verified tool for both communities to interact.

A mix of human-written and AI-generated textHuman understanding: all partsConjunctive Normal FormConstructive ReductionCook-Levin TheoremInteractive Theorem ProvingLean 4SAT EncodingsSatisfiability CheckingSymbolic ComputationTuring Machineformal verification
Oct 08, 202616 pages
PDFView work

math.LO — Logic

Arrow and Gibbard Satterthwaite Theorems in Lean

Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz

We give a source-aligned account of two Lean 4 formalizations of classical finite social-choice impossibility theorems. For a finite nonempty electorate and a finite alternative set containing three distinct alternatives, Arrow’s theorem derives dictatorship from unanimity and independence of irrelevant alternatives. Its proof expands a weakly decisive coalition from one ordered pair to all pairs, then contracts decisive coalitions to a singleton. The Gibbard–Satterthwaite development proves that every onto strategy-proof choice function on the unrestricted strict-ranking domain is dictatorial by constructing a social welfare function and applying that Arrow implementation. We explain the essential construction in full: top-two profiles define pairwise comparisons; strategy-proof monotonicity and three-top profiles establish a strict total order; predecessor counts provide injective natural-number ranks. Exact hypotheses, vendored dependencies, pinned source identities, prior formalizations, and the distinction between historical registry verification and the present source audit are recorded. The contribution is an exposition and audit of reusable formalization artifacts, not a new social-choice theorem or a claim of first formalization.

Primarily AI-generated textHuman understanding: some parts
Oct 01, 20269 pages
PDFView work

math.LO — Logic

A Lean Formalization of the Shapley Value Characterization for Finite Cooperative Games

Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz

We describe a Lean 4 formalization of the standard four-axiom characterization of the Shapley value for finite transferable-utility cooperative games. Games are arbitrary real-valued characteristic functions normalized at the empty coalition; the player type may itself be empty. The factorial coalition formula is proved efficient, symmetric for interchangeable players, null-player respecting, and additive. Uniqueness follows from the values of arbitrarily scaled unanimity games and an explicit Boolean-lattice Möbius decomposition. The proof requires neither a real-homogeneity axiom nor a continuity assumption on competing allocation rules. We explain the finite-sum arguments, the precise Lean statements, the separation between the registry’s challenge and implemented solution, and the historical verification evidence for the pinned source revision. The contribution is an auditable exposition of an existing formalization of classical mathematics, with no claim of new mathematics or formalization priority.

Primarily AI-generated textHuman understanding: some parts
Oct 01, 20267 pages
PDFView work

math.LO — Logic

Nash Bargaining Characterization in Lean

Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz

We describe a Lean 4 formalization of the classical two-person Nash bargaining characterization. A bargaining problem consists of a compact convex subset of the real plane, a feasible disagreement point, and a feasible outcome strictly improving both utilities. The Nash product is maximized over the individually rational part of that set. The development proves existence and uniqueness of the maximizer, verifies Pareto optimality, symmetry, positive affine invariance, and independence of irrelevant alternatives, and proves that these four axioms characterize the maximizer among feasible selection rules. We explain the algebraic midpoint proof of uniqueness and the normalization argument, including an explicit small-step tangent bound and a compact symmetric enlargement. The exposition is tied to an immutable repository snapshot and four declarations registered in Palomar. Historical registry verification is distinguished from the source inspection used to prepare this manuscript. The contribution is a documented formalization of established mathematics; no new bargaining theorem or formalization-priority claim is made.

Primarily AI-generated textHuman understanding: some parts
Oct 01, 20266 pages
PDFView work

math.LO — Logic

Finite Nash Equilibria and Dependent Mixed Strategies in Lean

Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz

We present two complementary Lean 4 developments of finite Nash equilibrium. The pure-game layer uses player-specific legal action sets, distinguishes one-way generalized ordinal potentials from bidirectional ordinal potentials, and proves potential-maximizer certificates, a local-maximum characterization, absence of strict-improvement cycles, and weak acyclicity. The mixed-game layers use either a common finite action type or a dependent finite action type for each player. They prove payoff equalization on equilibrium supports, Dirac payoff identities, continuity of the normalized payoff-excess map, and mixed equilibrium existence. We explain the finite-sum and sum-of-squares arguments and the reindexing bridge to an attributed, proved product-of-simplices Brouwer theorem. An additional legal-subtype interface is separated from the declarations selected by the registry comparator. The account is tied to two immutable source snapshots and dated verification records. It documents established mathematics and its formal interfaces, without claiming a new equilibrium theorem or formalization priority.

Primarily AI-generated textHuman understanding: some partsBrouwer fixed pointLean 4MathlibNash equilibriumdependent action typesmixed strategiespotential games
Oct 01, 20268 pages
PDFView work

math.OC — Optimization and Control

A Finite Coordinate Reduction for Approachability Loss in Lean

Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz

We explain a Lean 4 development of a finite-coordinate loss-preserving construction motivated by Theorem 4 of Dann, Mansour, Mohri, Schneider, and Sivan. Nonempty finite constraint and action index sets give a joint probability simplex with a canonical action marginal. For each mixed constraint, a linear comparator adds its outer product with that marginal. The comparator has mass two and leaves the legal action set. A one-step pairing identity yields exact equality of finite-horizon approachability and comparator-regret objectives, with explicit anchored lifts and marginal decoders. The development also proves a row-wise decomposition with at most one rank-one term per constraint index. We describe the twelve declarations registered in Palomar and their historical verification provenance. The scope is deliberately narrow: the constraint simplex parametrizes coordinate functions, both causal strategy translations observe original loss histories, and the comparators have no fixed point in the joint simplex. Thus the checked statements establish finite algebraic loss preservation; they do not certify the full published reduction, its fixed-point-defined improper class, reduced-loss-only feedback, or asymptotic rate theory. No mathematical novelty or formalization priority is claimed.

Primarily AI-generated textHuman understanding: some parts
Oct 01, 20269 pages
PDFView work