Browse

Logic

math.LO — Logic

math.LO RSS feed

Works in math.LO

37 works

math.LO — Logic

Points from Processes: Vakarelov’s Dynamic Mereotopology and Whitehead’s Point-Free Program

Contributed by John Hessler

Whitehead held that neither points of space nor instants of time should be primitive: both ought to be definable from relations between material things. Region-based theories of space have largely carried out the spatial half of this program, but the temporal half has remained informal. This paper offers an expository and philosophical account of Dimiter Vakarelov’s dynamic mereotopology, developed in five papers between 2010 and 2016, which aims at a theory of space and time that is point-free in this double sense. We argue that the program is best read as a staged realization of Whitehead’s demand. Each stage enriches the primitive spatio-temporal relations between changing regions just enough to recover a further layer of temporal structure: first moments without order, then an ordered time, and finally nameable, spatially non-trivial epochs. The staging culminates in a structural result Whitehead anticipated but never formalized: points of space and points of time turn out to be different aggregations of one and the same stock of abstract atoms. We also argue that the representation theorems on which the program rests deliver a reconstruction, rather than a reduction, of points, and that reconstruction is what Whitehead’s program requires.

A mix of human-written and AI-generated textHuman understanding: all partsmereotopology; point-free geometry; contact algebra;; representation theorems
Nov 15, 202635 pages
PDFView work

math.LO — Logic

Self-embedding monoids and the existential Thomas conjecture

Contributed by Dr. András Pongrácz

We give a countable homogeneous finitely bounded Ramsey structure in a finite relational language with finitely many reducts up to first-order interdefinability but infinitely many self-embedding monoids of reducts. The reducts producing these monoids are first-order interdefinable, while their monoids form a strictly increasing chain. This refutes the existential strengthening of Thomas' conjecture even under the Ramsey hypothesis. The example is an ordered expansion of an equivalence-relation structure. Before the order is added, that structure has exactly five reducts up to first-order interdefinability. We also give a revised proof of the classification of self-embedding monoids for reducts of the countable existentially closed binary branching semilinear order. Exactly five monoids occur, refining its three-class first-order classification. The proof transfers the known classification for the homogeneous binary branching CC-relation from antichains to arbitrary finite configurations. The additional step is a connectivity argument on finite labelled trees, using both preservation and reflection of the reduct's basic relations.

Primarily human-written textHuman understanding: all parts
Nov 15, 202634 pages
PDFView work

math.LO — Logic

Bounded Presentations and Normalization in Arithmetic Reconstruction

Contributed by Zhenyu Sun

We study bounded presentations of selected constructions in absolute anabelian geometry and Frobenioid theory. In bounded Zermelo set theory with Choice, we prove uniform recursion for a common state space and a uniformly supplied transition rule. Under explicit index bounds, membership-table codes place the states and their histories at the same finite type level. We construct coherent comparisons for representative quotients, fiberwise full skeletons, isofibrational base changes, and countable towers, and verify the lifting properties for model Frobenioids and angular presentations. For nonzero numerical observables transforming by positive scalars, compatible normalization exists exactly when the associated character is trivial on every isotropy group. A self-equivalence of the realified arithmetic Frobenioid over Q\mathbb{Q} preserves degree and every object isomorphism class but does not lift to the unit-trivialized perfection. The structural results give a relative uniform interpretation theorem: the weak theory constructs the bounded presentations and comparison maps, and specified arithmetic recognition theorems identify the resulting structures.

Author comments: 25 pages.

A mix of human-written and AI-generated textHuman understanding: some partsFrobenioidsarithmetic reconstructionbounded recursioncategorical equivalencenormalizationweak set theory
Nov 13, 202625 pages
PDFView work

math.CT — Category Theory

Isomorphism Loci and Coherence in Equivalence Extension

Contributed by Zhenyu Sun

We study the restriction data carried by dependent-product extension along a monomorphism. In a locally cartesian closed category, the extended map is an isomorphism after a change of base if and only if the input map is an isomorphism on the restricted base. In a topos, its isomorphism locus is therefore the universal quantification of the input locus. A terminal characterization gives coherent comparisons for base change and successive extension, together with formulas for intersections and unions. Under explicit homotopical, cartesian, and universe hypotheses, this construction gives equivalence extension and preserves the boundary identifications used to prove fibrancy of a universe. Graph comparisons and strict fillers of a fixed universe boundary are represented by trivially fibrant objects. A single realignment over the comparison object induces a weak equivalence between these parameter objects, and both admit extensions of every finite cubical boundary. A finite-groupoid example shows that graph comparisons cannot be selected naturally under all isomorphisms of unstructured input.

Primarily human-written textHuman understanding: all partsBeck–Chevalleydependent productequivalence extensionfibrant universeisomorphism locusrealignment
Nov 12, 202624 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

math.GR — Group Theory

Finite-length permutation modules for\\free-amalgamation structures of arbitrary arity

Contributed by Dr. András Pongrácz

Let $\A$ be the countable homogeneous limit of a free-amalgamation class in a finite relational language, expanded by a generic linear order. We prove that its tuple permutation modules have finite composition length over every field, also after naming finitely many points. More precisely, each orbit of increasing dd-tuples disjoint from the named points has a permutation module of length 2d2^d. This extends the theorem of Yang--Boja\'nczyk--Klin from unary and binary relations to relations of arbitrary arity. The main step shows that every finitely supported array whose sums over each single coordinate vanish is a linear combination of alternating sums obtained by independently doubling its coordinates. Its proof combines a Ramsey separation theorem with a construction that moves finite configurations into prescribed order intervals. Over a finite field, we also obtain finitely many closed invariant linear subspaces of $\F^{A^k}$; each is generated, in the product topology, by functions definable using at most kk additional parameters.

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

math.NT — Number Theory

A proof that Z\mathbb{Z} is Diophantine in Q\mathbb{Q} through congruent-number twists

Contributed by Manvir Jaswal

We give a proof of Glazer and collaborators' theorem that Z\mathbb{Z} is Diophantine in Q\mathbb{Q}, which builds on OpenAI's proof that Hilbert's tenth problem over Q\mathbb{Q} has a negative answer. Integers are represented by multiples of a point on an elliptic curve of rank one over Q(2)\mathbb{Q}(\sqrt2). An existential condition on two congruent-number twists forbids poles of odd order at odd primes. A height bound at six rational points, from a quaternionic Shimura curve and Serre's conjecture (a theorem of Khare–Wintenberger and Kisin), and a prime pattern from the Green–Tao–Ziegler theorem turn congruences at chosen primes into identities between multiples, and the growth of a Lucas sequence forces integrality. Our contribution is the existence of the rational points that the condition on twists requires: for coprime squarefree integers β>1\beta>1 and θ≥1\theta\ge1 with β≡θ≡1(mod8)\beta\equiv\theta\equiv1\pmod8, each a square modulo the primes of the other, there is an integer ee such that y2=x3−e2xy^2=x^3-e^2x and y2=x3−e2θ2xy^2=x^3-e^2\theta^2x both have rank one and a rational point with abscissa in βQ×2\beta\mathbb{Q}^{\times2}. Where Glazer and collaborators use a restricted 22-converse theorem, this rests on published theorems: the genus criterion of Tian, Yuan and Zhang, with Gross–Zagier.

Author comments: Version 3 adds one citation (introduction).

Primarily AI-generated textHuman understanding: no partsDiophantine setsElliptic CurvesHilbert's tenth problemSerre's conjectureShimura curvescongruent numbers
Nov 12, 202631 pages
PDFView work

math.LO — Logic

Borel Ruziewicz problem

Contributed by Konstantin Slutsky

We prove that normalized surface measure is the unique finitely additive rotation-invariant probability on the Borel subsets of SnS^n, n≥2n\geq2. We also prove that Lebesgue measure is the unique finitely additive measure on bounded Borel subsets of Rd\R^d, d≥3d\geq3, invariant under orientation-preserving rigid motions and normalized on the unit cube. The main step is the annihilation of Borel null sets. A spectral gap first gives bounded divergence certificates for compact null sets, chosen in a jointly Borel way. A shared random threshold then combines these certificates to cover arbitrary null sets. For Euclidean space, the construction is applied to families of spheres about two centers; spherical averaging completes the identification of the measure.

Primarily AI-generated textHuman understanding: no partsBorel dynamicsRuziewicz problemfinitely additive measuresspectral gap
Nov 12, 202612 pages
PDFView work

math.CT — Category Theory

Higher Galois Recognition and Parameter Descent

Contributed by Zhenyu Sun

Let n≥0n\geq0 and let X\mathcal X be a bounded coherent ∞\infty-topos. Suppose that finitely many noninitial coherent nn-truncated objects cover its terminal object, and that every coherent nn-truncated object in each of their slices has a finite covering family of sections. We identify X≤ncoh\mathcal X^{\mathrm{coh}}_{\leq n} with Fun⁡(M,Sπ,≤n)\operatorname{Fun}(M,\mathcal S_{\pi,\leq n}) for a π\pi-finite (n+1)(n+1)-type MM, recovered by all finite models preserving finite limits, finite coproducts, and effective epimorphisms. Descent uses degrees through n+2n+2 for objects and n+1n+1 for maps; both bounds are sharp for finite homotopy actions. Every exact functor FF between recognized categories has a universal parameter PF=F!(1)P_F=F_!(1) and a canonical factorization through its slice with fully faithful second functor. This parameter characterizes full faithfulness, conservativity, and all exact slice factorizations. For successive abelian Postnikov layers, we identify the space of marked exact lifts with a path space of Eilenberg--Mac Lane sections with local coefficients. The obstruction, classes of lifts, and relative automorphisms occur in degrees r+1r+1, rr, and r−1r-1. We compute a twisted parity obstruction and, for odd primes, classify cyclic self-equivalence components by a pp-adic valuation. A nonzero Postnikov class can persist in the identity component. For continuous finite families over a profinite (n+1)(n+1)-type, we prove that a uniform finite-section atlas exists precisely when the complete model space is π\pi-finite. Exact functors from finite model semantics, together with their lift spaces, satisfy finite-stage descent, while explicit profinite examples separate objectwise trivialization from uniform parameter elimination.

Author comments: 49 pages. Second paper in the series Model groupoids and finite homotopy semantics. Includes two verification scripts and their outputs.

A mix of human-written and AI-generated textHuman understanding: some parts
Nov 11, 202649 pages
PDFView work

math.LO — Logic

A Michael Space in the Laver model

Contributed by Morgan Jones

We show that a Michael space exists in the Laver model.

Author comments: I was stress testing Claude Fable 5.2 with varying levels of problems and trying to improve my workflow with AI. This problem was reasoned pretty quickly by Claude, however it required some convincing that it could do it.

Primarily AI-generated textHuman understanding: no parts
Nov 11, 202610 pages
PDFView work

math.LO — Logic

The 51-state beeper M51M_{51}: every battle ends, and what Peano Arithmetic can prove about it

Contributed by Annanay Kapila

We study an explicit 51-state, 2-symbol beeping Turing machine M51M_{51} and its associated dispatch-level process RR. An ordinal descent below ε0\varepsilon_0 proves that every battle of RR terminates and hence that M51M_{51} beeps infinitely often. A growth lemma shows that the battle counters and beep times eventually dominate every function provably computable in Peano Arithmetic. Together with a Rocq-checked simulation theorem, these results establish that quasihalting of M51M_{51} is independent of Peano Arithmetic. The document includes the process definition, machine table, ordinal analysis, growth proof and an account of its external dependencies.

Author comments: Supporting materials: Rocq simulation development, https://github.com/a-kapila/maths-proofs/blob/2e2d689f198e7bd51d264cd5468d6b7606886d2e/beeping-busy-beaver-51/rocq51.tar.gz ; computational checks, https://github.com/a-kapila/maths-proofs/blob/2e2d689f198e7bd51d264cd5468d6b7606886d2e/beeping-busy-beaver-51/checks51.tar.gz . The Rocq materials support the simulation theorem; the complete independence argument is not claimed to be fully formalized.

Primarily AI-generated textHuman understanding: some parts
Nov 11, 202635 pages
PDFView work

math.LO — Logic

Definability and Lifting in Model Subgroupoids

Contributed by Zhenyu Sun

Restriction to a wide subgroupoid of a model groupoid can introduce invariant relations, maps, and objects. For open topological groupoids, a map between restricted objects lifts exactly when its graph is invariant under the full groupoid, and a specified quotient presentation lifts exactly when its kernel relation is invariant. Under coherent restriction, these criteria recover definable maps and coherent quotient presentations. For finite continuous actions of a group with an open subgroup of finite index, coinduction identifies extensions with invariant subsets on which evaluation is bijective. For a finite group GG and a normal subgroup NN, we classify extensions of finite NN-sets by normalizer extensions of their orbit types. Multiplicities must be constant on conjugacy orbits of types; within each such block, the liftable multiplicities form the additive monoid generated by indices of subgroups over which the normalizer extension splits. The same subgroup data determine the groupoid of lifts and its isomorphism-class and mass generating functions. This classification also applies to finite continuous actions of profinite groups with an open normal subgroup. For a fixed action, a centralizer extension gives the splitting obstruction, with an H2H^2 obstruction and an H1H^1 classification when its kernel is abelian. The center of SL2(F5)\mathrm{SL}_2(\mathbb F_5) gives the monoid ⟨12,20⟩\langle12,20\rangle; Heisenberg groups over fields of odd prime order give unbounded lifting indices at fixed cohomological period. Finite torsor theories and infinite pure sets realize the definability criteria. For profinite extensions with finite kernel, one finite quotient detects all liftable multiplicities, though it need not carry every lift.

Author comments: 37 pages. Exact finite-group computations and their output are included as ancillary files.

Primarily human-written textHuman understanding: all partsBurnside ringscoherent toposesdefinabilityfinite group actionsgroup extensionsmodel groupoids
Nov 11, 202637 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.LO — Logic

Inertia and Elementary Theories of Hermitian Nilpotent Operators

Contributed by Zhenyu Sun, Jilin Wang

Let VV be a finite-dimensional Hermitian space over an algebraically closed field with a nonidentity involution, and suppose its form hh is nondegenerate. For a self-adjoint nilpotent operator NN, we recover the multiplicity of each signed Jordan block from finite differences of the ranks and signature differences of the forms h(x,Njy)h(x,N^j y). On a fixed Hermitian space these inertias classify unitary conjugacy. Across scalar fields they classify elementary equivalence in the four-sorted language of scalars, vectors, endomorphisms, and projective points with NN named. At fixed dimension each admissible inertia sequence isolates a complete theory. These theories are model complete and decidable, and none has the independence property. A bivariate generating function counts them by ambient signature. For two self-adjoint square-zero operators with a common image of fixed positive dimension and positive definite quotient forms, simultaneous unitary conjugacy on a fixed Hermitian space is classified by the ordered generalized eigenvalues. The associated Hermitian pencil recovers these eigenvalues even when all operator words have constant ranks and inertias. At fixed signature and rank the family theory is model complete and decidable. Its completions correspond to the ordered-field types of the spectrum, and each completion has the Turing degree of its type. We also characterize the Witt index by square-zero ranks over arbitrary fields with involution. For positive definite spaces we prove that finite-measurement sentences at fixed dimensions and outcome count have the same truth value over R(−1)R(\sqrt{-1}) as over C\mathbb C for every real closed field RR. The least Naimark dilation dimension of a measurement is the sum of its effect ranks.

Primarily human-written textHuman understanding: some partsHermitian forminertiamodel completenessquantum measurementreal closed fieldself-adjoint nilpotent operator
Nov 04, 202626 pages
PDFView work

math.LO — Logic

Intuitionistic Compression and Optimal Verification Trees

Contributed by Zhenyu Sun, Jilin Wang

In strict finitistic generation semantics, a formula is assertible at a generation if some stage in its verification tree forces it. We ask when assertibility agrees with intuitionistic truth on the poset of generations. The leaves of the verification trees, ordered by generation extension, form an intuitionistic Kripke model that preserves truth at every leaf, even without atomic prevalence. For a finite bundle, compression to the generations is exact if and only if each fiber of leaves has a greatest intuitionistic theory and the map selecting these theories has the back property. Compression remains exact under every restriction of the generation poset if and only if atomic prevalence holds. Conversely, consider coherent tree representations of a finite Kripke model whose atomic valuation reflects its order. Among representations with atomic prevalence, the minimum numbers of leaves and nodes over uu are h(u)h(u) and δC+∑x⪯uh(x)\delta_C+\sum_{x\preceq u}h(x), where h(x)h(x) counts saturated paths from minimal worlds to xx, and δC\delta_C is 11 if the comparability component of uu has no least element and 00 otherwise. Saturated-path trees attain both minima simultaneously. Among representations attaining the node minimum at every world, the common root labels in components without a least element determine the representation up to isomorphism over the outer frame. Allowing rooted posets in place of trees can reduce the number of nodes exponentially.

Primarily human-written textHuman understanding: all parts
Nov 04, 202621 pages
PDFView work

math.CO — Combinatorics

Local independent sets and colourings of triangle-free graphs

Contributed by Matthew Bowen, András Máthé, Oleg Pikhurko

This AI-assisted draft constructs, for every sufficiently large DD, a local rule of radius O((ln⁡D)2)O((\ln D)^2) that produces, on any triangle-free graph GG of maximum degree at most DD, a random independent set that includes each vertex with probability at least (1−oD(1))ln⁡D/D(1-o_D(1))\ln D/D. Further properties of the rule yield, for every fixed ε>0\varepsilon>0 and all sufficiently large DD, a randomised LOCAL algorithm that colours any such finite graph GG with at most (1+ε)D/ln⁡D(1+\varepsilon)D/\ln D colours, with high probability, in Oε(ln⁡D)+(ln⁡ln⁡∣V(G)∣)O(1)O_\varepsilon(\ln D)+(\ln\ln |V(G)|)^{O(1)} communication rounds. Applying known transference principles for Borel graphs, we obtain the same asymptotic bound on the number of colours for measurable and Baire-measurable colourings, and for Borel colourings of graphs with finite asymptotic separation index.

Primarily AI-generated textHuman understanding: some partsChromatic numberLOCAL algorithmdescriptive combinatoricsindependent settriangle-free graphs
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

Nonpathological extensions of FσF_\sigma ideals and fractional coloring

Contributed by Carlos López-Callejas

The random graph ideal is pathological, answering a question of López-Abad et al. We prove this by constructing a positive hereditarily pathological restriction using Kneser graphs. For an FσF_\sigma ideal I\mathcal I and any lower semicontinuous submeasure φ\varphi with FIN⁡(φ)=I\operatorname{FIN}(\varphi)=\mathcal I, we show that the nonpathological envelope φ^\widehat\varphi generates an ideal that depends only on I\mathcal I and, when proper, is the least nonpathological FσF_\sigma extension of I\mathcal I. Thus, I\mathcal I is nonpathological if and only if FIN⁡(φ)=FIN⁡(φ^)\operatorname{FIN}(\varphi)=\operatorname{FIN}(\widehat\varphi). We also characterize nonpathological FσF_\sigma ideals both as intersections of summable ideals and as intersections of matrix ideals, answering both converses asked by Filipów and Tryba. The least nonpathological FσF_\sigma extension of the random graph ideal is proper and is described by the fractional cochromatic numbers of its finite induced subgraphs.

A mix of human-written and AI-generated textHuman understanding: all partsF-sigma idealsKatětov orderfractional coloringleast nonpathological extensionsmatrix idealsnonpathological submeasurespathological idealsrandom graphsummable ideals
Oct 29, 202638 pages
PDFView work

math.DS — Dynamical Systems

A Boolean Lévy group with a free nonsingular action

Contributed by Konstantin Slutsky

We construct a Boolean Lévy group with a free ergodic spatial nonsingular action on a standard probability space, answering a question of Glasner, Tsirelson and Weiss. The action admits no equivalent invariant σ\sigma-finite measure. The group is a quotient of a weighted summable Boolean group by a discrete subgroup. By the nonsingular fixed-point theorem of Avraham-Re'em and Peterzil, the resulting group is not locally Wasserstein.

A mix of human-written and AI-generated textHuman understanding: all parts
Oct 29, 202614 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

math.LO — Logic

Ramsey’s Theorem for Pairs in Pincus’s Model XI

Contributed by Frank Gilson

Howard and Rubin record Pincus’s ordered colored permutation model as N48, but do not determine whether Ramsey’s theorem for pairs holds there. We prove that N48 |= RT for pairs. The proof uses least finite supports and the homogeneity of Pincus’s ordered colored structure: after fixing all but one point of a support, the remaining point generates an infinite orbit whose unordered pairs form a single stabilizer orbit. Combining this with Pincus’s results on the dense linear ordering principle (DO), the Boolean Prime Ideal Theorem (BPI), and the failure of Part∞, together with Pincus’s transfer theorems, yields Con(ZF) ⇒ Con(ZF + RT_pairs + DO + BPI + ¬Part∞), where Part∞ states that every infinite set is the disjoint union of infinitely many infinite sets.

A mix of human-written and AI-generated textHuman understanding: some partsaxiom of choice; Ramsey's theorem
Oct 22, 20264 pages
PDFView work

math.NT — Number Theory

A 15/16 zero-free half-plane for angular Hecke L-functions over the Eisenstein field

Contributed by Troy Winarski

We describe the argument recorded in a frozen Lean development for nonvanishing of the unit-compatible angular Hecke L-functions over Q(−3)\mathbb Q(\sqrt{-3}) in the strict half-plane ℜ(s)>15/16\Re(s)>15/16, apart from the genuine principal pole. The family includes imprimitive finite parts, every integer angular type allowed by the unit relation, and real unitary norm twists. The proof route passes through a mean-square estimate for the actual sextic rows, sixth-power averaging, a smoothed Möbius estimate with a totient factor, and Mellin continuation. We reconstruct the angular reflection, quadratic energy estimate, finite descent, and the calculation producing the 15/1615/16 exponent, while identifying the technical source lemmas inherited from OAI-003 that remain to be independently reconstructed. The theorem is formally verified in Lean and the frozen source/evidence package has undergone statement comparison, axiom audit, recursive kernel replay, quotient postchecking, and separate AI-assisted review. This manuscript is an expository reconstruction rather than a claim of independent human certification. We describe the formally verified proof as a xenoproof, and the theorem provisionally as a xenotheorem, to distinguish formal mathematical correctness from human mathematical understanding.

Primarily AI-generated textHuman understanding: some partsEisenstein integersHecke L-functionsLeananalytic number theoryangular Hecke charactersformal verificationxenoproofxenotheoremzero-free regions
Oct 22, 202636 pages
PDFView work

math.LO — Logic

Relative PP-Ideals of Hypergraphs and Ultrafilter Spectra

Contributed by Zhenyu Sun

We study ideals of hypergraphs of finite uniformity under countable upper bounds modulo finite vertex covers. The canonical ideal generated by a free filter and finite weak colorings has this relative PP-property exactly when the filter is the intersection of finitely many PP-points. The classification is preserved by adjoining hypergraphs that are locally finite after a finite vertex deletion. The corresponding extension of a trace ideal induces capture ideals on increasing sequences. These are σ\sigma-ideals exactly for PP-filters, and their uniformities are max⁡{πχ(F),d}\max\{\pi\chi(\mathcal{F}),\mathfrak{d}\}. For an ultrafilter U\mathcal{U}, the arity-two capture ideal equals the Louveau ideal exactly when U\mathcal{U} is a PP-point. Successive capture ideals decrease with the arity, and equality characterizes QQ-points. Every strict inclusion is witnessed by a closed set. Thus a non-QQ PP-point yields a decreasing sequence of σ\sigma-ideals, distinguished by closed sets, with equal uniformities. We also establish invariance under locally finite witness enlargements and analyze Stone kernels and countable block products. Consistently, nested ray-positive PP-sets have the same singleton endpoint spectrum and different ray transversal numbers.

A mix of human-written and AI-generated textHuman understanding: all partsHypergraph idealLouveau idealP-pointQ-pointStone dualityreaping numberultrafilter
Oct 20, 202645 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

math.LO — Logic

A counterexample to Vaught's Conjecture for Lω1,ωL_{\omega_1,\omega}

Contributed by Nathanael L. Ackerman, Cameron Freer, Robin W. Knight

We construct a sentence of Lω1,ωL_{\omega_1,\omega} having exactly ℵ1\aleph_1 many countable models up to isomorphism, but no perfect set of non-isomorphic models. This disproves Vaught's conjecture for infinitary logic. The construction follows a framework devised by Robin Knight, and the proof has been formally verified in Lean.

Primarily human-written textHuman understanding: all partsKnight systemsVaught’s conjectureinfinitary logicnumber of models
Oct 11, 202626 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.NT — Number Theory

Proof of the Non-existence of Perfect Cuboids via Mordell-Weil Rank Exhaustion and Minimal Polynomial Irreducibility of the Perfect Cuboid Surface

Contributed by Jonathan 𝑓(n) Reed

This manuscript establishes the non-existence of the Perfect Cuboid---a rectangular parallelepiped with integer edges, face diagonals, and space diagonal. By performing a rational sectioning of the governing quadratic forms, we demonstrate that the problem reduces to finding a non-trivial rational point on a family of hyperelliptic curves of Genus 3. We prove that the Jacobian of these curves possesses a Mordell-Weil rank of zero and that the perfection locus is an irrational algebraic singularity of degree d=4d = 4, precluding any solution in the integer domain Z3\mathbb{Z}^3. The non-existence of rational solutions is further verified via formal methods in Lean 4, demonstrating that the intersection of the Mordell-Weil torsion set and the degree-4 perfection locus is empty.

A mix of human-written and AI-generated textHuman understanding: all parts2-DescentEuler BrickHyperelliptic CurvesInteractive Theorem ProvingJacobian VarietyLean 4Mordell-Weil RankPerfect CuboidQuadratic Residueformal verification
Oct 07, 20268 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.GR — Group Theory

An Executable Stallings Recognizer for Finite Generating Lists in Lean

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

We explain a Lean 4 construction of a finite inverse automaton recognizing the subgroup of the rank-two free group generated by any finite list of signed words. The implementation builds a flower multigraph and computes the least equivalence relation compatible with deterministic labelled transitions by exhaustive finite search over Boolean relations. Canonical representatives realize the folded graph on the original finite state type. A coset-potential invariant proves that folding introduces no additional subgroup elements; preservation of the input loops proves the opposite inclusion. A separate reduction argument shows that traversal of the canonical reduced representative decides membership. We distinguish the registered theorem, its executable witness, and classical reasoning used only in the proof. The construction retains unused states and has no formalized complexity, core-trimming, subgroup-basis, intersection, or index algorithm. This is an expository account of a classical recognition theorem and a pinned formal artifact, with no claim of mathematical novelty or formalization priority.

Primarily AI-generated textHuman understanding: some partsLean 4MathlibStallings foldingfinite inverse automatafree groupssubgroup membership
Oct 01, 20268 pages
PDFView work

cs.LO — Logic in Computer Science

A Lean Formalization of Myerson-Satterthwaite Impossibility for Continuous Bilateral Trade

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

We present a source-grounded account of a Lean 4 formalization of the Myerson-Satterthwaite impossibility theorem for continuous bilateral trade. Buyer values and seller costs are independent, with atomless probability measures supported on compact real intervals whose interiors overlap. The model explicitly requires restricted Lebesgue measure to be absolutely continuous with respect to each type measure, together with full support; it does not require the type measures themselves to have densities. Under allocation and transfer measurability and integrability conditions, the registered theorem excludes the simultaneous satisfaction of almost-sure ex post efficiency, Bayesian incentive compatibility at every admissible type and report, interim individual rationality, and weak ex ante budget balance. The proof derives envelope identities from incentive inequalities, identifies the efficient allocation almost everywhere, and uses a layer-cake representation to show that the required information rents strictly exceed efficient surplus. We explain the analytic steps, their Lean declarations, and the verification evidence for the exact Palomar-registered source revision. This is an exposition of a classical result and an existing formal artifact, without a claim of mathematical novelty or formalization priority.

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

cs.DS — Data Structures and Algorithms

A Lean Certificate for the Single Source Unsplittable Flow Cost Counterexample

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

We explain a standalone Lean 4 and Mathlib verification of the finite counterexample announced by Dmitry Rybin to the cost-preserving single-source unsplittable-flow conjecture. The instance has seven vertices, nine directed arcs, and three terminal demands. An exact rational path flow saturates every arc, has cost 58, and has largest demand 15. Exhaustive graph-path classification reduces every unsplittable routing to two choices per terminal. Three backbone-arc inequalities force any routing with load at most the fractional load plus 15 to use at least two paid routes, each costing 30. Thus every such routing costs at least 60, ruling out cost preservation even with a non-strict congestion bound. We present the numerical certificate, its graph realization, and the boundary between the pinned proved implementation and its statement-only verification interface. The contribution is an exposition of a source-based formal certificate; no new counterexample, first formalization, or general rounding algorithm is claimed.

Primarily AI-generated textHuman understanding: some partsGoemans cost conjectureLean 4MathlibRybin counterexamplefinite counterexampleformal verificationsingle-source unsplittable flow
Oct 01, 20266 pages
PDFView work

math.LO — Logic

Ordinal-definable families in Cohen, random, and collapse extensions

Contributed by Elliot Glazer

We study ordinal-definable families of sets of arbitrary rank in Cohen, random, and collapse extensions. Over LL, countable OD families have OD enumerations after adding one Cohen or one random real. A single generalized Cohen subset gives the corresponding sharp theorem at every regular uncountable cardinal. When κ\kappa is singular strong limit and has uncountable cofinality, adding κ\kappa Cohen reals makes every member of a short-parameter definable family of size at most κ\kappa definable from a short parameter. Adding κ\kappa random reals gives a single short-parameter definable enumeration for every such family of size strictly below κ\kappa. The random bound is sharp. The proofs use coordinate amalgamation and small-index arguments. We also obtain arbitrary-rank descent for countable families after collapsing any infinite cardinal, with applications to choice in the relative Feferman--Levy model. In the full Solovay collapse extension of an arbitrary ZFC ground, every family definable from a real and ordinals that represents fewer than 2c2^{\mathfrak c} classes modulo null sets consists of measurable sets; the corresponding category assertion also holds. In the extensions of LL by ω1\omega_1 Cohen or random reals, no model of IΔ0I\Delta_0 of size at most ℵ1\aleph_1, definable from ordinals and a real, has full binary-coded standard system. Π11-CA0\Pi^1_1\text{-}\mathsf{CA}_0 proves a finite-fragment Borel obstruction to a full binary standard system for IΔ0I\Delta_0. For regular uncountable κ\kappa, the generalized Cohen extension by $\Add(\kappa,\Lambda)^L$, Λ>κ\Lambda>\kappa, has no ambiently κ+\kappa^+-saturated IΔ0I\Delta_0 model in HOD⁡Hκ+\operatorname{HOD}_{H_{\kappa^+}}, regardless of its size. Consequently every infinite regular κ\kappa of LL admits a cofinality-preserving GCH extension with no ODP(κ)\mathrm{OD}_{\mathcal P(\kappa)} saturated arithmetic presentation of size κ+\kappa^+. ZFC also proves that every singular strong limit κ\kappa admits an OD κ+\kappa^+-saturated elementary extension of N\mathbb N of size 2κ2^\kappa, hence of size κ+\kappa^+ under GCH.

Primarily AI-generated textHuman understanding: some partsBoolean algebrasSet theorydefinability
Sep 30, 2026119 pages
PDFView work

math.LO — Logic

Five equations for first-order logic, modulo the structure of existential graphs

Contributed by Anthony Hart

Peirce’s existential graphs draw a first-order formula so that the order and grouping of conjuncts, the names and order of bound variables, the position of a quantifier relative to conjuncts that do not mention its variable, and how a network of equalities is written cannot be seen. We take these structural laws for granted. On top of them, five two-way laws are complete for ordinary first-order logic with equality over nonempty domains. That is, any two equivalent formulas are connected by applying the laws inside them, in either direction. The laws are double negation, deiteration X ∧ ¬(X ∧Y ) ⇔ X ∧ ¬Y , annihilation ⊥ ∧ X ⇔ ⊥, substitution of equals, and existential introduction X(a) ∧ ∃u.X(u) ⇔ X(a), and none of them follows from the other four. The first three were already known to be complete for the propositional part. We prove first-order completeness by reduction to Tarski’s representation theorem for locally finite cylindric algebras. A size-ordered search over first-order laws, run up to size 5, kept four of the five; deiteration has size 7 and was added by hand. We also show that a published basis for Spencer-Brown’s boundary algebra is incomplete.

Primarily AI-generated textHuman understanding: all partscylindric algebraexistential graphsfirst-order logic
Sep 29, 202614 pages
PDFView work

math.LO — Logic

Under Measurables, HOD_{Ord^{\omega}} is locally arbitrary

Contributed by Elliot Glazer

For the inner model $\HOD_{\Ord^{\omega}}$, we derive an analogue for Roguski's classical result that without nontrivial assumptions on VV, $\HOD$ is an arbitrary model of $\ZFC$. For any sentence σ\sigma, letting $\CM$ denote ``class of measurables,'' the following theories are equiconsistent: \begin{enumerate} \item $\ZFC+\CM+ [\HOD_{\Ord^{\omega}}\models (\exists\kappa\,V_{\kappa}\models\sigma)]$; \item $\ZFC+\GCH+\CM+ [\HOD_{\Ord^{\omega}}\models (\SVC\wedge\CM\wedge\exists\kappa\,V_{\kappa}\models\sigma)]$; \item $\ZF+\DC+\CM+ \exists\kappa\,V_{\kappa}\models\sigma$. \end{enumerate} Thus, under measurables the only local constraint on $\HOD_{\Ord^{\omega}}$ is the requisite choice principle. We also derive an analogue for Woodins. Letting $\CW$ denote ``class of Woodins,'' the following are equiconsistent: \begin{enumerate} \item $\ZFC+\CW+ [\HOD_{\Ord^{\omega}}\models (\exists\kappa\,V_{\kappa}\models\sigma)]$; \item $\ZFC+\GCH+\CW+ [\HOD_{\Ord^{\omega}}\models (\exists\kappa\,V_{\kappa}\models\sigma)]+$ $\HOD_{\Ord^{\omega}}$ is a ground of VV; \item $\ZFC+\CW+$ some symmetric extension $V(G) \models \DC+\exists\kappa\,V_{\kappa}\models\sigma$. \end{enumerate}

Primarily AI-generated textHuman understanding: some partsSet theoryaxiom of choice
Sep 28, 202680 pages
PDFView work