On semidefinite-representable sets over valued fields

Corentin Cornou, Simone Naldi, Tristan Vaccon

Abstract

Polyhedra and spectrahedra over the real numbers, or more generally their images under linear maps, are respectively the feasible sets of linear and semidefinite programming, and form the family of semidefinite-representable sets. This paper studies analogues of these sets, as well as the associated optimization problems, when the data are taken over a valued field $K$. For $K$-polyhedra and linear programming over $K$ we present an algorithm based on the computation of Smith normal forms. We prove that fundamental properties of semidefinite-representable sets extend to the valued setting. In particular, we exhibit examples of non-polyhedral $K$-spectrahedra, as well as sets that are semidefinite-representable over $K$ but are not $K$-spectrahedra.

TL;DR

This paper extends the geometric foundations of optimization—specifically polyhedra and spectrahedra—from the real numbers to the setting of valued fields (such as $p$-adic numbers). The authors introduce a novel algorithm for solving linear programs over these fields using Smith Normal Forms and prove that while some classical properties carry over, new geometric distinctions arise between spectrahedra and their linear projections.

What Problem Does This Paper Address?

In classical optimization, we usually work over the real numbers ($\mathbb{R}$). Linear Programming (LP) deals with polyhedra (shapes defined by linear inequalities), while Semidefinite Programming (SDP) deals with spectrahedra (shapes defined by linear matrix inequalities).

However, there is growing interest in "non-Archimedean" geometry—settings where distance is measured differently, such as in number theory ($p$-adic fields) or computer science (formal power series). This paper asks: What do these fundamental optimization shapes look like over a valued field $K$, and can we still solve optimization problems effectively?

Specifically, the authors investigate whether polyhedra over valued fields are closed under linear maps (the "Direct Image" problem) and how to distinguish between spectrahedra and their projections (semidefinite-representable sets), a distinction that is notoriously subtle in the real case.

Methods

The authors employ a mix of algebraic geometry and matrix analysis:

  • Smith Normal Form (SNF): This is the "secret sauce" of the paper. By using SNF, the authors can decompose complex linear systems into a diagonal form. This allows them to handle valuation inequalities much more easily than standard Gaussian elimination would allow.
  • Valuation Theory: They define "positive semidefiniteness" in a non-Archimedean sense: a matrix is PSD if all its eigenvalues have a non-negative valuation in an algebraic closure.
  • Newton Polygons: To check if a matrix is PSD without actually calculating eigenvalues, the authors use Newton polygons to relate the valuations of a polynomial's roots to the valuations of its coefficients.
  • Algorithmic Reduction: The proposed SOLVELPval algorithm reduces a general linear program over a valued field into a "diagonal" version that can be solved by simply inspecting the valuations of the input data.
The canonical matrix form used in the algebraic reduction of linear systems over valued fields.

Key Insights and Ideas

  • Polyhedra are "Rounder" than you think: In the real world, polyhedra have sharp corners and flat faces. Over a valued field, the authors show that polyhedra are essentially unions of balls or polydiscs. This is because the "metric" in valued fields (like the $p$-adic metric) behaves very differently from Euclidean distance.
  • The PSD-Integrality Link: A major "aha moment" is Theorem 5.2, which proves that a matrix is positive semidefinite if and only if its characteristic polynomial has coefficients in the valuation ring $O_K$. This turns a difficult eigenvalue problem into a simple check of coefficient valuations.
  • The Helton-Nie Property Analogue: The authors explore the boundary between spectrahedra and their shadows (projections). They prove that "annuli" (sets defined by a range of valuations, like $a \leq \text{val}(x) \leq b$) are semidefinite-representable but—under certain conditions—cannot be spectrahedra. This provides a concrete way to separate these two classes of sets in the valued setting.

Key Results

  • Direct Image Theorem: The authors prove that the image of a polyhedron under an affine map is always another polyhedron. This confirms that the "polyhedral" property is robust in valued fields. The hierarchy of these direct images is central to understanding the geometry of these sets.
  • LP Algorithm: They provide Algorithm 1 (SOLVELPval), which solves linear programs over valued fields. Unlike the Simplex method which moves between vertices, this algorithm uses algebraic matrix decompositions (SNF) to find feasible points or prove unboundedness.
  • Characterization of Annuli: They demonstrate that polyannuli (products of annuli) are "spectrahedral shadows." This is significant because it shows that the class of semidefinite-representable sets is strictly larger than the class of spectrahedra in this setting.
Hierarchy of Direct Image (DI) set classes established in the paper.

Limitations and Future Work

  • Assumption of Completeness: The authors assume the valued field is discrete and complete (like $\mathbb{Q}_p$). While many results might generalize, the proofs currently rely on these properties for simplicity.
  • SDP Complexity: While the paper provides a clear algorithm for Linear Programming, a general, efficient algorithm for Semidefinite Programming over valued fields remains an open challenge.
  • Tropical Connections: The paper touches on tropical geometry (which can be viewed as a "limit" of valued fields), but a deeper integration between these exact algebraic methods and tropical combinatorial methods is suggested as a path for future research.

Summary updated

Abstract

Polyhedra and spectrahedra over the real numbers, or more generally their images under linear maps, are respectively the feasible sets of linear and semidefinite programming, and form the family of semidefinite-representable sets. This paper studies analogues of these sets, as well as the associated optimization problems, when the data are taken over a valued field $K$. For $K$-polyhedra and linear programming over $K$ we present an algorithm based on the computation of Smith normal forms. We prove that fundamental properties of semidefinite-representable sets extend to the valued setting. In particular, we exhibit examples of non-polyhedral $K$-spectrahedra, as well as sets that are semidefinite-representable over $K$ but are not $K$-spectrahedra.
BibTeX
@misc{cornou2026semidefinite,
  author = {Corentin Cornou and Simone Naldi and Tristan Vaccon},
  title = {{On semidefinite-representable sets over valued fields}},
  year = {2026},
  eprint = {2602.09702},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.09702},
}
Figure