CS Paper Radar

Rational polynomial solvability reduces to stratifiability of semilinear sets

Michaël Cadilhac

cs.FL cs.LO ·submitted 2026-10-20 01:47 UTC · v1

Abstract

A semilinear set is stratifiable if it is a finite union of linear sets whose periods have at most two nonzero coordinates, with no two periods in one component connecting alternating pairs of coordinates. We give a computable many-one reduction from the existence of a rational zero of an integer polynomial to deciding stratifiability. After the classical reduction to quadratic systems, we reduce rational solvability of these systems to a problem we call finite separation by Cartesian products of rational linear forms. Its input consists of rational subspaces $D_1,\ldots,D_k\le\mathbb Q^r\times\mathbb Q^r$. A separator is a map $(\boldsymbol x,\boldsymbol y)\mapsto(u(\boldsymbol x),v(\boldsymbol y))$, where $u,v\colon\mathbb Q^r\to\mathbb Q$ are nonzero rational linear forms. The problem asks whether finitely many separators suffice so that every pair outside $\bigcup_iD_i$ receives, from some separator, a value attained at no pair in that union. We then reduce this problem to stratifiability. Ginsburg and Spanier's characterization of letter-bounded context-free languages} also induces a reduction from rational polynomial solvability to context-freeness of letter-bounded languages specified by semilinear exponent sets. An OpenAI preprint claims undecidability of rational polynomial solvability; if correct, our result settles the decidability of general stratifiability, a problem open since 1966.

Comment
13 pages plus 10 pages of appendix

Closest papers

Nearest neighbours by meaning across the whole index.

Approximate Polynomial Satisfiability is in the Counting Hierarchy

cs.CC ·2026-09-30 ·Nikhil Balaji, Mahsa Shirmohammadi, Sébastien Tavenas, James Worrell
theory similarity 0.59
Abstract

The Approximate polynomial satisfiability problem (APS), introduced by Guo, Saxena, and Sinhababu (CCC 2018), asks whether the zero vector lies in the Zariski closure of the image of a given polynomial map. Specifically, for a field $k$ with algebraic closure~$K$, the problem asks whether $\boldsymbol 0 \in\overline{\boldsymbol f(K^n)}$ for a polynomial map $\boldsymbol f=(f_1,\ldots,f_m)$ with $f_i\in k[X_1,\ldots,X_n]$. APS is a natural topological analogue of Hilbert's Nullstellensatz, namely the question of whether a given system of polynomial equations has a common zero. APS captures several problems in algebraic complexity, including border rank, hitting sets for border classes, and null-cone membership; it is known to be NP-hard and in PSPACE. We show that APS lies in the Counting Hierarchy (CH) over both the rationals and finite fields, substantially improving the known PSPACE upper bound. Our proof builds on a recent breakthrough due to Andrews, Garg, and Schost (FOCS 2026) on deciding Hilbert's Nullstellensatz in CH. As a corollary, our result improves the complexity of certifying hitting sets for border classes from PSPACE to CH. We also give a polynomial-time reduction of Hilbert's Nullstellensatz to APS, valid in any characteristic. In characteristic zero, we give a reduction of APS to the decision problem for the existential theory of real closed fields. Overall, our results place approximate polynomial satisfiability closer in complexity to exact polynomial feasibility and as a byproduct give improved complexity bounds for several problems arising in approximative complexity.

0.53

Controllability of polynomial systems is undecidable and not recursively enumerable

cs.CC math.OCeess.SY ·2026-10-19 ·Jun Liu, Ivan O. Shevchenko
theory similarity 0.56
Abstract

Sontag conjectured in 1988 that global controllability of polynomial control systems with rational coefficients is undecidable, but that the controllable systems form a recursively enumerable set. We prove the first part of the conjecture and disprove the second. For every homogeneous polynomial vector field $F$ of odd degree with rational coefficients, we construct an explicit polynomial control system $Σ_F$, with one more state than $F$, that is globally controllable if and only if the origin is \emph{not} globally asymptotically stable for $\dot x=F(x)$. By a recent result, the homogeneous polynomial vector fields with a globally asymptotically stable origin form a set that is recursively enumerable but not decidable. Consequently, global controllability of polynomial systems is undecidable, and the controllable polynomial systems are not recursively enumerable. The same conclusions hold for systems of the form $\dotξ=f(ξ)+Bu$ with a polynomial drift and a constant input matrix.

0.27

Regular Separability for Bidirected VASS

cs.FL ·2026-11-02 ·Łukasz Orlikowski, Georg Zetzsche
similarity 0.56
Abstract

The regular separability problem asks, given two languages, whether there exists a regular language that contains one of them and is disjoint from the other. We study regular separability for bidirected VASS. We first show that the problem remains Ackermann-complete when the input consists of two languages recognised by bidrected VASS. To find a subclass of VASS in which the problem has lower complexity we define alphabetically bidirected VASS as ones where bidirectedness is also visible in the input letters. Our main result establishes that regular separability for alphabetically bidirected VASS is EXPSPACE-complete. The key to this result is that, in this setting, regular separability coincides with disjointness. As a first ingredient in this equivalence, we also show that for alphabetically bidirected Z-VASS, regular separability and disjointness are equivalent. Consequently, regular separability for these systems is in polynomial-time. In fact, it is log-space inter-reducible with non-solvability of integer linear Diophantine equation systems. Finally, we observe that the picture changes dramatically in the presence of a zero test, namely, we show that regular separability for alphabetically bidirected one-counter automata is undecidable.

0.26

Exact Minimum Extension Degrees for Reed Solomon Codes under Linear and Nonlinear Repair at the Cut Set Bound

cs.IT ·2026-10-25 ·Yuhan Li
theoryhot direction similarity 0.54
Abstract · 21 pages

We study the minimum extension degree required for a Reed--Solomon code to admit exact $\mathbb{F}_q$-linear repair at the cut-set bound from every prescribed set of $d$ helpers. Let $s=d-k+1$, and let $Q_s(n)$ be the minimum product of $n$ pairwise coprime integers, each at least $s$. For every prime power $q$ and all $3\le k<d<n\le2d-2$, we prove that the minimum degree over $\mathbb{F}_q$ is exactly $sQ_s(n)$. When all surviving nodes are helpers, we also characterize the admissible extension degrees and bound the number of coordinates that can attain the cut-set bound. The required achievability follows from existing construction methods; we give a short existence proof using splitting subspaces. For a family of parameters with $n>2d-2$, we obtain strictly smaller extension degrees, showing that the range restriction cannot be omitted altogether. Finally, we prove that a nonlinear repair scheme attaining the cut-set bound induces an $\mathbb{F}_p$-linear repair scheme on the same code, where $p$ is the characteristic. Consequently, the extension-degree lower bounds over the prime field remain valid without a linearity assumption.

0.51

Good rational functions up to degree six

cs.IT math.NT ·2026-11-02 ·Anuvrat Jaindungarwal, Divyesh Vaghasiya
similarity 0.54
Abstract · 14 pages, 1 table

Locally recoverable codes (LRCs) are fundamental to the architecture of modern distributed storage systems. The Tamo-Barg construction of optimal LRCs was revolutionized by the introduction of good polynomials, which group evaluation points into local recovery sets. However, polynomial constructions are constrained by their inherently large Galois groups, which limit the number of totally split rational places. Recent advances have generalized this paradigm to good rational functions, which leverage the geometry of the projective line to achieve minimal Galois groups and subsequently codes with greater length. In this paper, we complete the classification of good rational functions of degree up to $6$ in characteristic $2$. By embedding the problem into algebraic function field theory, we explicitly determine the minimal arithmetic and geometric Galois groups for these low degrees. Furthermore, we move beyond asymptotic Hasse-Weil estimates by proving that the exact number of totally split places over extension fields obeys a linear recurring sequence (LRS). This gives an efficient method for computing the exact lengths and dimensions of the corresponding optimal LRCs and, in many cases, yields parameters beyond those obtainable from good polynomials.

0.24

Polynomial Separation of a Shared Tensor Leg and Matrix Multiplication in Arbitrary Characteristic

cs.CC ·2026-10-12 ·Houxi Lü
theory similarity 0.53
Abstract

We improve the shared-leg separation construction in Proposition 3.1 of OpenAI, *An Upper Bound of $9/4$ for the Matrix Multiplication Exponent* (October 2, 2026). If $M$ tensor blocks have a common first space and independent matched sectors on their other two spaces, then $M+n-1$ copies of their matched sum degenerate to the full direct sum of the blocks, each tensored with an $n$-dimensional dot product. For $n=M$, this reduces the number of source copies from $5M$ to $2M-1$. The construction uses polynomial interpolation and truncated local substitution, with no roots of unity or factorial denominators. It works over every field containing enough distinct elements. We verify that the remaining spectral and discrete-growth arguments of the cited preprint are independent of characteristic. Over an algebraic closure, the replacement therefore gives $ω\leq9/4$ in every characteristic.

0.46

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.53
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

Construction of Regular Fat Linear Sets and Non-Representable q-Matroids

cs.IT math.CO ·2026-10-12 ·Yufei Qiu, Valentino Smaldore, Zhenpeng Wang, Corrado Zanella, Ferdinando Zullo
similarity 0.53
Abstract

Let $q$ be a prime power. An $(r, i)$-regular fat $\mathbb F_q$-linear set has exactly $r$ points of weight $i\ge2$, called fat points. All of its remaining points have weight one, and at least one such point occurs. We solve two open problems posed by three of the authors of this paper. First, we derive divisibility constraints on the point weights using the scalar stabilizer of the defining subspace. Consequently, a regular fat linear set of rank $2i$ in $\operatorname {PG}(1,q^n)$ has at most two or exactly $q + 1$ fat points. In the latter case, the fat points form an $\mathbb F_q$-subline. Second, we construct higher-dimensional regular fat linear sets whose fat points do not form an $\mathbb F_q$-subgeometry. In particular, for every $k\geq 3$ we obtain examples of rank $2k$ whose fat locus consists of an $\mathbb F_q$-subgeometry $\operatorname {PG}(k-2,q)$ in $\operatorname {PG}(k-1,q^4)$ together with one external point. This construction is then generalized further. Finally, we apply our projective-line results to $q$-matroid representability and present an infinite family of non-representable rank-two $q$-matroids arising from partial spreads.

0.25