Logic
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Tuesday 10 March
We study the continuous reducibility of isomorphism relations in the space of regresive functions in $\kappa^\kappa$. We show for inaccessible $\kappa$, that if $\mathcal{T}$ is a theory with less than $\kappa$ non-isomorphic models of size $\kappa$ and $\mathcal T'$ is unstable or superstable non-classifiable, then the isomorphism of models of $\mathcal{T}$ is continuous reducible to the isomorphism of models of $\mathcal{T}'$.
Analysis of PDEs
Backward problem for a degenerate viscous Hamilton-Jacobi equation: stability and numerical identification
This work is devoted to the analysis of the backward problem for a viscous Hamilton-Jacobi equation with degenerate diffusion and a general Hamiltonian that is not necessarily quadratic. First, we focus on linear degenerate parabolic equations in the nondivergence setting. We prove the conditional stability of the backward problem using Carleman estimates. Then, by a linearization technique, we prove similar results for the nonlinear viscous Hamilton-Jacobi equation. Regarding numerical identification, we first investigate the linear degenerate equation with noisy data using the adjoint state method, combined with a Conjugate Gradient algorithm, to solve the associated minimization problem. Finally, the numerical identification for the nonlinear viscous Hamilton-Jacobi equation is investigated by the Van Cittert iteration. Numerical tests are presented to show the performance of the proposed algorithms.
Read the full abstract
Optimization and Control
Dirichlet control problems with energy regularization governed by non-coercive elliptic equations
The present study investigates a linear-quadratic Dirichlet control problem governed by a non-coercive elliptic equation posed on a possibly non-convex polygonal domain. Tikhonov regularization is carried out in an energy seminorm. The regularity of the solutions is established in appropriate weighted Sobolev spaces, and the finite element discretization of the problem is analyzed. In order to recover the optimal rate of convergence in polygonal non-convex domains, graded meshes are required. In addressing this particular problem, it is also necessary to introduce a discrete projection in the sense of $H^{1/2}(\Gamma)$ to deal with the non-homogeneous boundary condition. A thorough examination of the approximation properties of the discrete controls reveals that the discrete problems are strongly convex uniformly with respect to the discretization parameter. All these ingredients lead to optimal error estimates. Practical computational considerations and numerical examples are discussed at the end of the paper.
Read the full abstract
Probability
Uniform Lorden-type bounds for overshoot moments for standard exponential families: small drift and an exponential correction
We study the overshoot \(R_b=S_{\tau(b)}-b\) of a random walk with independent identically distributed increments from a standardised one-parameter exponential family, with primary emphasis on the small-drift regime \(\theta\downarrow0\). Unlike the classical renewal-process setting with nonnegative increments, we allow sign-changing increments and assume only a positive drift \(\mu_\theta>0\). For each \(k\in\mathbb N\) we obtain Lorden-type moment bounds, uniform in the barrier \(b\), for \(\E_\theta[R_b^k]\) with an explicit remainder term decaying exponentially in \(b\). The proof reduces the problem to the renewal process of strict ascending ladder heights and combines a simple bound for the limiting overshoot moments with a uniform exponential estimate for the rate of convergence of the distribution functions of \(R_b\) to the limiting random variable \(R_\infty\) as \(b\to\infty\), uniformly in \(\theta\in[0,\theta^\ast]\). As a consequence, the classical constant \((k+2)/(k+1)\) arising in residual-life bounds improves to \(C_k=1\) for sufficiently large \(b\) at fixed \(\theta\), and also uniformly over all \(b\ge0\) in the small-drift regime. Counterexamples are provided showing that the stronger inequality with \(k\mu_\theta\) in the denominator cannot hold uniformly in \((b,\theta)\). Finally, the exponential CDF estimate is interpreted in terms of optimal transport: we obtain exponential convergence in the metric \(W_1\), a quantile coupling with \(\E|\widetilde R_b-\widetilde R_\infty|=O(e^{-rb})\), error bounds for Lipschitz functionals and a total-variation bound for smoothed distributions.
Read the full abstract
Algebraic Topology
The homotopy type of the moment-angle complex associated to the complex of injective words
Topological methods have emerged as valuable tools for analyzing the structural properties of directed graphs, particularly connectome data in computational neuroscience. This paper investigates the construction of topological spaces from combinatorial data of directed graphs using the polyhedral product functor, with particular emphasis on understanding their homotopy type, which is also of independent interest in topology and combinatorics. Specifically, we compute the homotopy type of the moment-angle complex over the face poset of the complex of injective words. This reveals a tight connection between homotopy and combinatorics: its homotopy type is determined by the $h$-vector of complexes of injective words. We also construct an associated homotopy fibration of polyhedral products associated to ordered simplicial complexes, which in a way generalizes the analogous homotopy fibration for polyhedral products over abstract simplicial complexes.
Read the full abstract
Probability
Uniform Concentration for $\alpha$-subexponential Random Operators
Random matrices acting on structured sets play a fundamental role in high-dimensional geometry, compressed sensing, and randomized algorithms. Existing results primarily focus on subgaussian models, when random matrices act as near-isometries on sets with optimal tail behavior. Nevertheless, very often in applications we deal with distributions with heavy tails that are not subgaussian but have at least exponential-type tails. In this work, we study random matrices A whose rows (or columns) have $\alpha$-subexponential tail distributions with $\alpha \in (0,2]$. So subgaussian and sub-exponential models are included in as special cases. We establish concentration type inequality for $Ax$, where x belongs to the bounded subsets of $\mathbb{R}^n$, showing that their geometric distortion is governed by Talagrand's functional of the set and depends on the tail parameter $\alpha$. Our results extend the known optimal inequalities in the subgaussian regime ($\alpha=2$), and provide new guarantees for heavier-tailed, yet exponentially integrable, random matrices. These findings extend the theory of random matrices beyond the subgaussian framework. Moreover, they yield near-isometric embedding results applicable to dimension reduction and allow us to make robust high-dimensional inference under non-Gaussian measurements.
Read the full abstract
Optimization and Control
An Integer Linear Programming Model for the Evolomino Puzzle
Evolomino is a pencil-and-paper logic puzzle published by the Japanese company Nikoli, renowned for culture-independent puzzles such as Sudoku, Kakuro, and Slitherlink. Its name reflects the core mechanic: the polyomino-like blocks drawn by the player must gradually "evolve" according to the directions indicated by arrows pre-printed on a rectangular grid. In this paper, we formalize the rules of Evolomino as an integer linear programming (ILP) model, encoding block evolution, connectivity, and consistency requirements through linear constraints. Furthermore, we introduce an algorithm for generating random Evolomino instances, utilizing this ILP framework to ensure solution uniqueness. Computational experiments on a custom benchmark dataset demonstrate that a state-of-the-art CP-SAT solver successfully handles puzzle instances of up to $10 \times 10$ within one second and up to $18 \times 18$ within one minute.
Read the full abstract
Algebraic Geometry
Semi-rigid stable sheaves: a criterion and examples
Inspired by Mukai's work on K3 surfaces, we introduce and study a notion of semi-rigidity for stable sheaves on smooth polarised varieties, designed to capture the existence of stable deformations of direct sums. We show that semi-rigidity is detected by the absence of decomposable elements in the kernel of the Yoneda pairing. We apply the resulting criterion to line bundles on smooth projective varieties and to line bundles supported on smooth Lagrangian subvarieties of hyper-Kähler manifolds.
Read the full abstract
Combinatorics · Cross-listed from cs.DM
Some polynomial classes for the acyclic orientation with parity constraint problem
We study the problem of finding an acyclic orientation of an undirected graph with constrained in-degree parities specified by a subset T of vertices. An orientation is called T -odd if a vertex v has odd in-degree if and only if v P T . While the unconstrained parity orientation problem is polynomial (Chevalier et al. (1983)), imposing acyclicity makes it more challenging, and its complexity remains an open question. Szegedy and Szegedy ( 2006) proposed a randomized polynomial-time algorithm for this problem, but it is not known whether it belongs to co-NP. Furthermore, Gravier et al. (2025) showed the problem becomes NP-complete on partially directed graphs, even when restricted to planar cubic graphs. We identify three necessary conditions for the existence of acyclic T -odd orientation: a global parity condition P, and two conditions S and S ensuring the existence of potential sources and sinks. Following the work of Frank and Kiraly (2002), we define graph classes containing the graphs for which a given subset of the necessary conditions P, S and S is also sufficient for the existence of an acyclic T -odd orientation. We establish the inclusion relationships between these classes. We complete the study of these classes by a characterization of the solvable instances for Cartesian products of paths and cycles. The proofs of these results are all constructive, so that acyclic T -odd orientations can be built in polynomial time whenever they exist. We use these families, along with cliques, to demonstrate the strictness of the class inclusions in our hierarchy.
Read the full abstract
Optimization and Control
Fairness in Robust Unit Commitment Problem Considering Suppression of Renewable Energy
Power company operators make power generation plans one day in advance, in what is known as the Unit Commitment (UC) problem. UC is exposed to uncertainties, such as unknown electricity load and disturbances caused by renewable energy sources, especially PVs. In previous research, we proposed the Renewable Energy Robust Optimization Problem (RE-RP), which solves these uncertainties by considering suppression. In this paper, we propose a new model called RE-RP with fairness (RE-RPfair), which aims to achieve fair allocation among PVs allocation. This model is an expansion of the original RE-RP, and we prove its effectiveness through simulation. To measure the degree of fairness, we use the Gini Index, which is well-known in social science.
Read the full abstract
Optimization and Control
Mollified Christoffel-Darboux Kernels and Density Recovery on Varieties
We introduce mollified Christoffel-Darboux (CD) kernels on varieties, a systematic regularization of the classical CD kernel associated with a probability measure on a compact domain. The main motivations are twofold: first, to sharpen the classical on/off-support dichotomy of the CD polynomial by replacing linear growth on the support by a uniform bound; second, to obtain consistent and quantitatively controlled recovery of densities from moment data, without the need to know the equilibrium measure of the underlying domain. Our contributions are the following: (i) We introduce families of mollifiers on algebraic varieties. For each measure and degree on such a variety we define a mollified CD kernel, which can be computed from the moments of the underlying measure by linear algebra. (ii) We prove, by elementary arguments, that an improved dichotomy property holds: on the interior of the support the mollified CD polynomial is uniformly bounded in the degree, while outside the support it grows exponentially with the degree. (iii) Assuming Sobolev regularity of the density with respect to a reference measure, we derive explicit convergence rates for density recovery for measures in Euclidean space via mollified CD kernel. (iv) On the unit sphere, we show that suitably chosen algebraic mollifiers, constructed from zonal polynomials, lead to kernels with improved rates, building on classical constructive approximation results.
Read the full abstract
Differential Geometry
Nonlinear Lebesgue spaces: Curves and geometry
This paper is the second in a series by the author and collaborators devoted to the study of geometric and analytic properties of nonlinear Lebesgue spaces, that is, L^p spaces of mappings taking values in arbitrary metric spaces. The present article formalizes the pointwise description of their geometric properties—their length structure, bounds on their Alexandrov curvature as well as the definition of a velocity for absolutely continuous curves despite the lack of differential structure. To obtain this pointwise description, we first prove a nonlinear analogue of the Fubini–Lebesgue theorem, which yields an identification of L^p curves in nonlinear Lebesgue spaces with mappings taking values in the space of L^p curves. This identification of L^p curves then enables a similar identification for absolutely continuous curves, from which the pointwise description of the geometric properties of nonlinear Lebesgue spaces follows.
Read the full abstract
Dynamical Systems
Rigidity of the dynamics of ${{\rm Aut}}({\mathsf{F}}_n)$ on representations into a compact group
Let $G$ be a compact Lie group. Let ${\mathsf{F}}_n$ be the free group of rank $n$. We describe the orbits of ${\mathsf{Aut}}(\mathsf{F}_n)$ on ${\mathsf{Hom}}(\mathsf{F}_n;G)$ when $n$ is sufficiently large. The dynamics stabilizes: orbit closures and invariant probability measures are algebraic, as in Ratner's theorems.
Read the full abstract
Numerical Analysis
Exponential Convergence of $hp$-FEM for the Integral Fractional Laplacian on cuboids
For the Dirichlet integral fractional Laplacian, we prove root exponential convergence of tensor-product $hp$-finite element approximations on $(0,1)^3$, for forcing $f$ that is analytic in $[0,1]^3$. Exploiting analytic regularity estimates in weighted Sobolev spaces, we prove for $hp$-GLL interpolation approximations with $N$ degrees of freedom the energy norm error bound $\lesssim \exp(-b\sqrt[6]{N})$. Tensor product mesh families which are geometrically refined towards all sides of $(0,1)^3$ are used. Numerical experiments with $hp$-Galerkin FEM confirm the bound.
Read the full abstract
Optimization and Control
Faster Stochastic ADMM for Nonsmooth Composite Convex Optimization in Hilbert Space
In this paper, a stochastic alternating direction method of multipliers (ADMM) is proposed for a class of nonsmooth composite and stochastic convex optimization problems in Hilbert space, motivated by optimization problems constrained by partial differential equation (PDE) with random coefficients. We prove the strong convergence of the proposed ADMM algorithm in the strongly convex case, and show the faster nonergodic convergence rates in terms of functional values and feasibility violation for both strongly convex and general convex cases. We demonstrate the application of the proposed method to solve certain model problems, along with its associated probability bound of large deviation. Some preliminary numerical results illustrate the efficiency of our method.
Read the full abstract
Dynamical Systems
Multiplier rigidity for complex Hénon maps
We investigate the multiplier rigidity problem for polynomial automorphisms of $\mathbf{C}^2$. A first result states that a complex Hénon map of given degree is determined up to finitely many choices by its multiplier spectrum, or more generally by the unstable multipliers of its saddle periodic points. This is the counterpart in this setting of a classical result of McMullen for one-dimensional rational maps. For compositions of Hénon maps, the same rigidity holds provided the multi-degree and the multi-Jacobian are fixed. As in McMullen's theorem, this follows from the nonexistence of stable algebraic families in the corresponding parameter space. This in turn relies on precise asymptotic bounds for the Lyapunov exponents of the maximal entropy measure along diverging families.
Read the full abstract
Number Theory
On autoduality of Drinfeld modules and Drinfeld modular forms
Let $\mathbb{F}_q$ be the field of $q$ elements and let $A=\mathbb{F}_q[t]$ be the polynomial ring over $\mathbb{F}_q$. Let $\mathfrak{n}\in A\setminus \mathbb{F}_q$ be a monic polynomial with a prime factor of degree prime to $q-1$. Let $\Delta$ be a subgroup of $(A/(\mathfrak{n}))^\times$ such that the map $\Delta\to (A/(\mathfrak{n}))^\times/\mathbb{F}_q^\times$ is bijective. Let $S$ be a scheme over $A[1/\mathfrak{n}]$ and let $R$ be an $A[1/\mathfrak{n}]$-algebra which is an excellent regular domain. In this paper, we show that any Drinfeld module $E$ of rank two over $S$ admitting a $\Gamma_1^\Delta(\mathfrak{n})$-structure is isomorphic to its Taguchi dual $E^D$. As an application, for the Hodge bundle $\bar{\omega}$ on the Drinfeld modular curve $X$ of level $\Gamma_1^\Delta(\mathfrak{n})$ over $R$, we give a dual Kodaira–Spencer isomorphism of the form $\bar{\omega}^{\otimes 2}\simeq \Omega^1_{X/R}(2\mathrm{Cusps})$, in contrast with the usual one in the Drinfeld case in which $E^D$ is involved.
Read the full abstract
Dynamical Systems
Spectral rigidity among ellipses, Bialy's conjecture and local extrema of Mather's beta function
In this paper we prove Bialy's conjecture which states that if the Mather beta functions of two ellipses coincide at two nonzero rotation numbers then the ellipses coincide. We also show that the same conclusion holds when only one rotation number is prescribed, provided the two ellipses have the same perimeter. Finally we discuss consequences for local extremizers of Mathers beta function building on a recent result of Baranzini, Bialy and Sorrentino.
Read the full abstract
Information Theory
Scientific Rigor and Human Warmth: Remembering Vladimir Sidorenko (1949-2025)
During the Foundations of Future Communication Systems (FFCS) conference in Braunschweig, a dedicated memorial session was held in honor of Dr. Vladimir (Volodya) Sidorenko (1949-2025). The session, chaired by Minglai Cai, brought together colleagues, collaborators, and former students to commemorate his scientific achievements and his exceptional human qualities. This report summarizes the biographical tribute, the personal recollections shared by speakers, and the broader impact of Volodya's work in coding theory, cryptography, telecommunications, and quantum error correction. Beyond his more than 150 publications and substantial technical contributions, the session highlighted his intellectual rigor, mentorship, humor, generosity, and lasting influence on the international research community.
Read the full abstract
Category Theory
A Critical Pair Enumeration Algorithm for String Diagram Rewriting
Critical pair analysis provides a convenient and computable criterion of confluence, which is a fundamental property in rewriting theory, for a wide variety of rewriting systems. Bonchi et al. showed validity of critical pair analysis for rewriting on string diagrams in symmetric monoidal categories. This work aims at automation of critical pair analysis for string diagram rewriting, and develops an algorithm that implements the core part of critical pair analysis. The algorithm enumerates all critical pairs of a given left-connected string diagram rewriting system, and it can be realised by concrete manipulation of hypergraphs. We prove correctness and exhaustiveness of the algorithm, for string diagrams in symmetric monoidal categories without a Frobenius structure.
Read the full abstract
Category Theory
Composable Uncertainty in Symmetric Monoidal Categories for Design Problems
Applied category theory often studies symmetric monoidal categories (SMCs) whose morphisms represent open systems. These structures naturally accommodate complex wiring patterns, leveraging (co)monoidal structures for splitting and merging wires, or compact closed structures for feedback. A key example is the compact closed SMC of design problems (DP), which enables a compositional approach to co-design in engineering. However, in practice, the systems of interest may not be fully known. Recently, Markov categories have emerged as a powerful framework for modeling uncertain processes. In this work, we demonstrate how to integrate this perspective into the study of open systems while preserving consistency with the underlying SMC structure. To this end, we employ the change-of-base construction for enriched categories, replacing the morphisms of a symmetric monoidal V-category C with parametric maps A to C(X,Y) in a Markov category induced by a symmetric monoidal monad. This results in a symmetric monoidal 2-category N*C with the same objects as C and reparametrization 2-cells. By choosing different monads, we capture various types of uncertainty. The category underlying C embeds into N*C via a strict symmetric monoidal functor, allowing (co)monoidal and compact closed structures to be transferred. Applied to DP, this construction leads to categories of practical relevance, such as parametrized design problems for optimization, and parametrized distributions of design problems for decision theory and Bayesian learning.
Read the full abstract
Optimization and Control
Convex Duality Made Difficult
The study of convex functions - in particular, of their optimization (really minimization) is one of the most important fields of applied mathematics. Convexity seems to be one of those incredibly well-chosen hypotheses which is just specific enough to admit a wealth of theorems, just general enough to produce a nontrivial theory (and a large amount of important examples). Convex optimization, possibly because it has an "analytical" rather than "algebraic" feel, has not been very thoroughly studied by applied category theorists. The one notable exception is [4], which studies the decomposition of optimization problems by categorical means. This paper takes a different approach, attempting to define a category with optimization problems as the objects, and to prove theorems about optimization by categorical means. As an illustration, we show how to use our methods to rederive some existing results: A minimax-type theorem, Theorem 5.5, and the fact that for convex functions, (f*)*=f (where f* is the Legendre dual), Proposition 6.6.
Read the full abstract
Logic
A Model Companion for Abelian Lattice-Ordered Groups with a Valuation
An abelian lattice-ordered group, or abelian $\ell$-group, is an abelian group equipped with a compatible lattice ordering. In this paper, we introduce two multi-sorted extensions of abelian lattice-ordered groups inspired by the zero-set maps for continuous functions into R. We demonstrate that this expansion is equivalent to equipping G with a spectral subspace X of $\ell$-Spec(G), along with the map sending $a \in G$ to $V(a \wedge 0) \cap X$. Using a classical partial quantifier elimination result originally due to Fuxing Shen and Volker Weispfenning, we show that one of these expansions admits a model companion, which is complete and has quantifier elimination in a small language expansion.
Read the full abstract
Analysis of PDEs
Rigidity of balls in the solid mean value property for polyharmonic functions
We show that balls are the only open bounded domains for which the mean value formula for polyharmonic functions holds. We do so by adapting an argument of Ü. Kuran for harmonic functions. Also, we provide a quantitative version of the same result.
Algebraic Topology
On the topological complexity of non-simply connected spaces
Topological complexity is a numerical homotopy invariant that measures the instability of motion planning in a space. To study the topological complexity of non-simply connected spaces, Costa and Farber introduced a cohomology class whose nilpotency gives a lower bound of topological complexity. Farber and Mescher constructed a spectral sequence that evaluates this nilpotency without direct computation. We extend these results with respect to a group homomorphism. As an application, we determine the topological complexity of some 3-manifolds with nonabelian fundamental group.
Read the full abstract
Algebraic Topology
Szczarba's twisted shuffle and equivariant path homology of directed graphs
To a marked simplicial set one can associate its path chain complex, and define its homology to be the homology of this complex, inspired by path homology theories for directed graphs, quivers, and marked categories. Given a marked simplicial set with a simplicial group action preserving the markings and degenerate 1-simplices, together with a twisting function, we define a marked twisted Cartesian product using the box product. Classically, Szczarba's twisted shuffle provides a quasi-isomorphism between the chain complex of a twisted Cartesian product and the corresponding twisted tensor product. In this paper, we prove that in the marked setting, this map restricts to a chain isomorphism on path chain complexes. As an application, for directed graphs with group actions, we obtain a natural Borel construction as a special case of marked twisted Cartesian products. Equivariant path homology is defined as the homology of this construction and is computed by an explicit twisted tensor product.
Read the full abstract
Operator Algebras
On quantum symmetries of graphs
Let $G$ be a simple finite graph, and let $\mathcal U_G$ be the related quantum graph. We study the game algebra $C(\mathrm{Qut}(\mathcal U_G))$ of quantum automorphism of $\mathcal U_G$. Moreover, we prove that for any graph $G$ with $|V(G)|\geq 3$, the quantum graph $\mathcal U_G$ admits nonlocal symmetry, meaning that there exists a perfect quantum no-signaling correlation
Read the full abstract
Symplectic Geometry
The completion of the set of Lagrangians and applications to dynamics – Based on lectures by C. Viterbo
The goal of these lectures is to introduce the completion of the set of Lagrangian submanifolds of a symplectic manifold with respect to the spectral metric first introduced by V. Humilière and recently revisited by C. Viterbo. We establish a number of basic properties of this completion, in particular through the notion of $\gamma$-support, which we develop as a refinement of Humilière's original concept. We then present an application of these notions to conformally symplectic dynamics, generalizing the notion of Birkhoff attractor as defined and studied by G.D. Birkhoff, M. Charpentier, and more recently P. Le Calvez. Finally, we briefly mention several other applications of the Humilière completion and highlight many open questions. These are notes elaborated from the lectures with the same title given by C. Viterbo at the CIME School ”Symplectic Dynamics and Topology” held in Cetraro (CS), Italy, from 16th to 20th June 2025.
Read the full abstract
Classical Analysis and ODEs
The maximal operator on variable Lebesgue spaces: an ${\mathcal A}_{\infty}$-characterization
In this paper we obtain a new boundedness criterion for the maximal operator $M$ on variable exponent spaces $L^{p(\cdot)}$. It is formulated in terms of the variable exponent analogue of the well known weighted $A_{\infty}$ condition.
Dynamical Systems · Cross-listed from eess.SY
Amplitude-Dependent Bode Diagrams via Scaled Relative Graphs
Scaled Relative Graphs (SRGs) provide an intuitive graphical frequency-domain method for the analysis of Nonlinear (NL) systems, generalizing the Nyquist diagram. In this paper, we develop a method for computing $L_2$-gain bounds for Lur'e systems over bounded frequency and amplitude ranges. We do this by restricting the input space of the SRG both in frequency and energy content, and using methods from Sobolev theory. The resulting gain bounds over restricted sets of inputs are less conservative than bounds computed over the entire $L_2$, and yield three-dimensional NL generalization of the Bode diagram, plotting $L_2$-gain as function of both input frequency and energy content. In the zero-energy limit, the Linear Time-Invariant (LTI) Bode diagram is recovered, and at the infinite-energy zero-frequency limit, we recover the $L_2$-gain. The effectiveness of our method is demonstrated on an example that resembles Phase-Locked Loop dynamics.