CS Paper Radar

Projective blowups: a formal and multicentered proof

A. Mayeux

cs.LO math.AG ·submitted 2026-08-13 07:43 UTC · v2
theory

Abstract

We give a machine-checked proof, in Lean 4, of the universal property of multi- centered blowups: given a finite family Z of closed subschemes of a scheme X, presented on each chart by ideals, there is a scheme BlZ X over X, terminal among X-schemes on which every member of the family becomes an effective Cartier divisor. To the best of our knowledge this is the first formalisation of blowups, single- or multicentered, in any theorem prover. The proof is organised around the universal property of the multicentered dilatation of a ring. The comparison isomorphisms on overlaps, the cocycle identity, and the independence of the chosen presentation are obtained from the uniqueness part of this universal property. We give the exact theorem statement as formalized, the proof architecture, and the main new mathematical ingredients, together with the corresponding Lean code.

Closest papers

Nearest neighbours by meaning across the whole index.

Dilatations of categories, via their lean formalization

cs.LO math.CT ·2026-08-10 ·Arnaud Mayeux
similarity 0.57
Abstract

Given a category $\calC$ and a center, that is a collection of pairs $(d_i, N_i)$ consisting of a morphism $d_i$ and a sieve $N_i$ over its codomain, the dilatation of $\calC$ is a new category $\calC'$ in which every $n \in N_i$ factors, uniquely and functorially, through $d_i$. This paper presents the theory of dilatations of categories through a full formalization of the construction and its main theorems in the Lean~4 proof assistant, on top of the Mathlib library. An appendix collects a systematic dictionary between the mathematical statements and the Lean declarations that formalize them.

0.04

Boxicity and Threshold Dimension of Zero Divisor Graphs

cs.DM math.COmath.AC ·2026-08-27 ·Marco Caoduro, Meike Neuwohner
similarity 0.52
Abstract · 25 pages 5 figures

The zero divisor graph $Γ(R)$ of a finite commutative ring $R$ has as vertices the non-zero zero divisors of $R$, with an edge between two elements exactly when their product is zero. We determine the boxicity and threshold dimension of $Γ(R)$ for two classes of finite commutative rings: reduced rings and quotients of principal ideal domains. Our proofs use a new combinatorial gadget, the integral covering graph, that captures the structure shared by both ring families and generalizes the disjointness graph on subsets of $[n]$, where two subsets are adjacent if and only if they are disjoint. In doing so, we answer two questions recently posed by L.~Sunil Chandran and Suraj Kumar Sahoo in Boxicity of Zero Divisor Graphs, Discrete Applied Mathematics 391 (2026).

0.40

Hull variation of algebraic geometry codes under divisor twists

cs.IT ·2026-11-18 ·Erik Mendoza, Sihem Mesnager, Luciane Quoos
theory similarity 0.52
Abstract

The hull $\mathrm{Hull}(\mathcal{C})=\mathcal{C}\cap\mathcal{C}^{\perp}$ of a linear code $\mathcal{C}\subseteq\mathbb{F}_q^n$ interpolates between linear complementary dual (LCD) codes, with trivial hull, and self-dual codes. Its dimension is preserved by coordinate permutations but not by scalings $\mathcal{C}\mapsto\mathbf{x}\cdot\mathcal{C}$, $\mathbf{x}\in(\mathbb{F}_q^*)^n$. This governs the complexity of Sendrier's support-splitting algorithm and decides whether an equivalence class contains LCD codes. We study this hull-variation problem, formalised by Chen, for algebraic geometry codes $\mathcal{C}(D,G)$ over a function field $\mathcal{F}/\mathbb{F}_q$ of genus $g>0$, where scalings are twists of $G$ by principal divisors; as a natural relaxation, we allow twists $G\mapsto G+L$ by arbitrary divisors. Writing $\mathcal{C}(D,G)^{\perp}=\mathcal{C}(D,H)$, with $H=D-G+W$, $W$ canonical, a twist acts by $(G,H)\mapsto(G+L,H-L)$. Whenever $\gcd(G+L,H-L)$ is non-special, the hull dimensions of $\mathcal{C}(D,G+L)$ and $\mathcal{C}(D,G)$ differ by exactly $\frac12(\mathrm{deg}|G-H|-\mathrm{deg}|G-H+2L|)$. For a genuine scaling, $L=-(z)$, this variation is bounded by $2[\mathcal{F}:\mathbb{F}_q(z)]$. Under the same hypothesis, we obtain an upper bound on the hull dimension depending only on $D$ and $W$, and characterise exactly when it is attained by a scaling of it. These bounds shed new light on Chen's maximal hull dimension; explicit scalings on Kummer extensions show that the first is sharp. We construct explicit twists that raise, respectively lower, the hull dimension by prescribed amounts, one unit at a time, and apply them to two classical families. Starting from known LCD codes, we reach every hull dimension in an explicit range; starting from a self-dual code ($q$ even) or a code of maximal hull dimension ($q$ odd), we descend to $0$, yielding LCD codes of various dimensions.

0.15

Promise Systems of Equations over Magmas with Identity and over Algebras in Congruence Modular Varieties

cs.CC ·2026-09-03 ·Nick Jamesson
similarity 0.51
Abstract

We study the computational complexity of solving promise systems of equations over finite algebras. Given two algebras $\mathbf{A}$ and $\mathbf{B}$ with a homomorphism from $\mathbf{A}$ to $\mathbf{B}$, the promise system of equations problem is to determine if an input system of equations has a solution in $\mathbf{A}$ or not even in $\mathbf{B}$. We generalize the results of Larrauri, Mottet, and Živný [ACM ToCL'26] to obtain a $\mathbf{P}-\mathbf{NP}$-hard dichotomy result for promise systems of equations over a class of algebras which contains all monoids, and a dichotomy result for promise systems of equations over algebras in a congruence modular variety. We then consider the metaproblem for promise systems of equations over algebras in a congruence modular variety: given finite algebras $\mathbf{A}$ and $\mathbf{B}$ such that $\mathbf{A}$ is in a congruence modular variety, we show there is a quasi-polynomial time algorithm for determining whether or not the associated promise system of equations problem is in $\mathbf{P}$.

0.19

Approximate Polynomial Satisfiability and Integral Closure Membership in the Counting Hierarchy

cs.CC ·2026-10-30 ·Sanyam Agarwal, Archit Hari, Anurag Pandey, Himanshu Shukla
theory similarity 0.51
Abstract · Made some minor changes

Andrews, Garg, and Schost (FOCS~2026) recently, in a breakthrough result, placed Hilbert's Nullstellensatz (HN) in the Counting Hierarchy ($\CH$) using constant-depth circuits for multivariate resultants. While HN deals with exact polynomial satisfiability, Guo, Saxena, and Sinhababu (CCC~2018; Theory of Computing~2019) introduced approximate polynomial satisfiability (APS) as a natural approximative analogue of polynomial system satisfiability. They proved its $\mathsf{NP}$-hardness and a $\PSPACE$ upper bound, and used APS to construct hitting sets for $\overline{\mathsf{VP}}$ in polynomial space, substantially narrowing the GCT chasm in geometric complexity theory. We place APS in the Counting Hierarchy for rational polynomials given by arithmetic circuits. Our proof combines Noether normalization with a geometric restriction on how points in the image of a polynomial map approach the origin, reducing APS to a test on multivariate resultants which allows solvability in $\CH$. It complements the independent and concurrent proofs of Balaji, Shirmohammadi, Tavenas, and Worrell, and Andrews, Garg, Oliveira, and Schost. Moreover, we also place integral closure membership testing in the Counting Hierarchy. Here, the question is whether a given polynomial $f$ is integral over $\C[f_1,\ldots,f_m]$. Our approach uses a global annihilator criterion and an effective degree bound to reduce non-integrality to APS in polynomial time. In fact, we show that the reduction holds both ways, and Integral Closure Membership Testing is equivalent to APS under polynomial-time reductions.

0.17

Testing epimorphism onto the bicyclic monoid is $\mathsf{NP}$-complete

cs.LO math.GR ·2026-10-06 ·Luka Carroll, Murray Elder
theoryunusual similarity 0.49
Abstract · 17 pages, 1 figure. Comment about OpenAI result added

We prove that deciding whether there is a surjective homomorphism from an arbitrary finitely presented inverse monoid onto the bicyclic monoid is $\mathsf{NP}$-complete. As part of the proof, we show that an extension of existential Presburger arithmetic which involves greatest common divisors on $n$ arguments is in $\mathsf{NP}$, extending a recent result of Défossez, Haase, Mansutti, and Pérez (SODA 2024).

0.29

Optimal and minimal $p$-ary linear codes from generalized order ideals of hierarchical posets

cs.IT math.CO ·2026-09-27 ·Rumi Melih Pelen
similarity 0.49
Abstract · 13 pages, no figures. Ancillary files contain a Python script verifying the formulas and computational examples

Hyun, Kim, Wu and Yue constructed optimal and minimal binary linear codes from order ideals of hierarchical posets with two levels. Two different generalizations of the underlying antichain (simplicial complex) setting to odd characteristic are known: down-sets of $\mathbb{F}_p^n$ under the componentwise order, and support-closed subsets of $\mathbb{F}_q^m$. No generalization of the poset setting itself has appeared. We introduce generalized order ideals of a poset of order $p-1$, obtained by attaching multiplicities in ${0,\dots,p-1}$ to the elements of a poset, and study the two natural notions of order ideal that arise for hierarchical posets with two levels. Whenever the ideal meets the upper level, the resulting defining sets are neither down-sets nor support-closed. We determine the weight distributions of the associated complement codes, exhibit a family of Griesmer codes in which the upper element carries an arbitrary multiplicity, and, via the characteristic function of a generalized order ideal, obtain an infinite family of minimal $p$-ary codes of length $p^n-1$ and dimension $n+1$ violating the Ashikhmin--Barg condition.

0.21

Graded Intersection Types

cs.LO cs.PL ·2026-11-12 ·Rémy Cerda, Ugo Dal Lago
similarity 0.49
Abstract

We introduce graded intersection types, in which arrow domains are multisets of types with coefficients in a semiring. Boolean and natural number grades recover idempotent and non-idempotent intersection types. We give algebraic conditions on the semiring for subject reduction and expansion in finite systems and in locally finite systems with guarded infinite types. We construct a lifting to multisets of grades corresponding, in this general setting, to lifting the idempotent system to the non-idempotent one. We recall the main existing operational characterisations from the literature, and show some general extensions.

0.34