Optimization and Control
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Tuesday 13 October · still arriving
This paper proposes a Projection Anderson Acceleration (PAA) algorithm for variational inequality (VI) problems, where the underlying function is expressed as a finite sum of Hölder continuous functions and satisfies the $\sigma$-star strongly monotone condition that includes the star strong monotonicity with $\sigma = 1$ as a special case. In the absence of quasi-monotonicity and Lipschitz continuity, we establish the evaluation complexity of the PAA algorithm for finding an approximate solution. Specifically, for the star strongly monotone VI problems, the PAA algorithm needs at most $O (\log (\epsilon^{-1}) \epsilon^{2 (\underline{\alpha} - 1)})$ evaluations of the function and projection for finding an $\epsilon$-approximate solution, where $\underline{\alpha} \in (0, 1]$ is the smallest exponent of Hölder continuity of the component functions. We illustrate our theoretical results by numerical examples of non-quasi-monotone complementarity problems and non-monotone semilinear elliptic equations with non-Lipschitz terms.
Analysis of PDEs
Uniform Decay for Ruggeri's Relaxed Navier-Stokes-Fourier Equations
This work studies the linearization of Ruggeri's classical symmetric hyperbolic model of viscous, heat-conductive fluids about a homogeneous equilibrium. In three space dimensions, we show that perturbations in $L^1\cap L^2$ decay in $L^2$ at the rate $(1+t)^{-3/4}$, uniformly as a common parameter scaling the three relaxation times tends to zero. The estimate controls the equilibrium variables together with the appropriately weighted stresses and heat flux, and has the same decay rate as the formal Navier–Stokes–Fourier limit.
Read the full abstract
Mathematical Physics · Cross-listed from quant-ph
Beyond Gaussian Entanglement: Practical Criteria for Polynomially Excited Quantum States
Polynomial excitations consisting of creation and annihilation operators are studied. Subsystem entanglement is proven produced and preserved by such manipulations. NPT entanglement already present between any two subsystems of a general pure or mixed multipartite Gaussian state is preserved under all polynomial excitations. Nevertheless, these excitations can create NPT entanglement between initially separable subsystems, implying that the number of NPT entangled pairs cannot decrease. Polynomial excitations of a wide class of initially separable pure states are considered. For these states, the method reduces the infinite-dimensional positivity problem to a finite-dimensional one: after partial transposition, NPT entanglement is equivalent to a corresponding bilinear representation matrix not being positive semi-definite. Furthermore, using symplectic diagonalization and spectral decomposition, an explicit transformation is constructed between the Fock-space and position representations. It is applied to quadratic excitations of a three-mode mixed Gaussian state. The behavior of the NPT entanglement is tracked between subsystems as a function of a parameter $\kappa$, which tunes the non-locality of the excitation, and quantum negativity is evaluated. Under a chosen quadratic Hamiltonian, the resulting unitary time evolution maintains NPT entanglement for long intervals, interrupted only by short periods of PPT states. Finally, a closed analytical expression is derived for the covariance matrix of a general quadratic operator for an arbitrary number of degrees of freedom in phase space. Our framework directly connects mathematical foundations, theoretical modeling, and experimentally feasible implementations.
Read the full abstract
Differential Geometry
Pseudolocality and strong uniqueness for complete Ricci flows
In this paper, we prove a uniform pseudolocality theorem for smooth complete Ricci flows whose initial metrics have Ricci curvature bounded below and uniformly positive injectivity radius. No a priori curvature bound is assumed on the flow. As a consequence, we obtain strong uniqueness for smooth complete Ricci flows from a complete metric with the above geometric bounds. We also prove that every smooth complete Ricci flow from a complete Ricci-flat metric with uniformly positive injectivity radius is stationary. The same conclusion holds for any complete flat initial metric. In particular, we give an affirmative answer to Chen's question on the strong uniqueness of Ricci flow from Euclidean space in every dimension.
Read the full abstract
Group Theory
A note on the proof of nonamenability of F
The goal of this note is to provide a human written exposition of OpenAI's recent proof that Thompson's group F is nonamenable.
Analysis of PDEs
Blowup of smooth solutions to 2D quasilinear wave equations with higher-order null conditions and short pulse initial data
This paper investigates the 2D quasilinear wave equation $\displaystyle\sum_{\alpha,\beta=0}^{2}g^{\alpha\beta}(\partial\phi)\partial_{\alpha\beta}^{2}\phi=0$ with the short pulse initial data $(\phi, \partial_t\phi)|_{t=1}=(\delta^{2-\varepsilon_0}\phi_0(\frac{r-1}{\delta},\omega), \delta^{1-\varepsilon_0}\phi_1(\frac{r-1}{\delta},\omega))$, where $0<\varepsilon_0<1$ is a fixed constant and $\delta>0$ is a small parameter. In our previous work [Ding Bingbing, Xin Zhouping, Yin Huicheng, Sci. China Math., Vol. 69 (2026), No. 3, 667-736], we have established the global existence of a smooth solution $\phi$ under the $k$-th order null condition ($k\ge 2$) when the $(k+1)$-th order null condition fails, provided that $0<\varepsilon_0<\varepsilon_k^*=\frac{k}{k+1}$. As a natural continuation, the present paper demonstrates that for $\varepsilon_0\ge \varepsilon_k^*$, the smooth solution $\phi$ blows up in finite time. Consequently, the threshold $\varepsilon_0=\varepsilon_k^*$ is shown to be the critical exponent that precisely characterizes the global existence and finite-time blowup for smooth short pulse solutions to the aforementioned 2D quasilinear wave equation, under the assumption that the $k$-th order null condition holds while the $(k+1)$-th order null condition does not. A key novelty of our approach lies in deriving sharp orders of $\delta$ for almost all quantities in both energy and pointwise estimates. This is achieved by utilizing the higher-order null structure in conjunction with a new good unknown recently introduced by us and the transport equation for the difference between this good unknown and its corrector.
Read the full abstract
Probability
Strong Invariance Principle for Random Dirichlet Series
It is shown that the random prime Dirichlet series $ X(s)=\sum_{p\in \mathcal{P}}\frac{\xi_p}{p^{s+1/2}} $ can be almost surely approximated by a Brownian motion, where $ \{\xi_p\}_{p\ge 1} $ are independent and identically distributed random variables with zero mean and finite variance, and $ \mathcal{P} $ is the set of prime numbers. As a consequence, the functional law of the iterated logarithm, limit laws of the iterated logarithm, and Chung's law of the iterated logarithm for $ X(s) $ are obtained. It is also shown that the random Dirichlet series $ Y(s)=\sum_{k=2}^{\infty} \frac{(\log k)^{\alpha}}{k^{s+1/2}} $ with $ \alpha=-1/2 $ admits the same approximation as $ X(s) $, and a direct relationship between $ X(s) $ and $ Y(s) $ with $ \alpha=-1/2 $ is established. The strong invariance principle for $ Y(s) $ with $ \alpha>-1/2 $ is also obtained.
Read the full abstract
Metric Geometry
An explicit dimension-free isoperimetric plateau in the cube
We prove that, in every dimension, the relative Euclidean isoperimetric profile of the unit cube equals one whenever the prescribed volume differs from one half by at most $6.25\times10^{-12}$. The only minimizers in this interval are coordinate slabs. This answers Glaudo's question on the existence of a dimension-free central plateau. The proof combines a dimension-free local optimality estimate for slabs, established through BV slicing and a small-support estimate, with a quantitative Gaussian rigidity argument that forces the normal of an approximating half-space to be close to a coordinate direction.
Read the full abstract
Probability
Free energy of non-convex multi-species Ising spin glasses with external fields
We identify the limit free energy of mean-field multi-species spin glasses with +/-1 spins, allowing for the presence of external fields, and without assuming any convexity property of the covariance function of the Hamiltonian. The limit is given by an "uninverted" variational formula over Brownian martingales. The proof consists in first identifying the limit free energy of configurations with a fixed magnetization. Once the magnetization is fixed, we can show the convergence of the enriched free energy to the solution of a Hamilton-Jacobi equation. The magnetization constraint is also used to show the convexity of the initial condition in this equation, and this yields a variational representation of the solution, as a Hopf formula. Convex duality then turns this formula into an optimization over martingales whose initial values are the prescribed magnetizations.
Read the full abstract
Combinatorics
On the existence of $F$-irregular graphs for disconnected graphs $F$
For a given graph $F$, a graph $G$ is $F$-irregular if all its vertices have pairwise distinct $F$-degrees, where the $F$-degree of a vertex $v$ is the number of subgraphs of $G$ containing $v$ and isomorphic to $F$. While the existence of $F$-irregular graphs has been actively studied for connected graphs $F$, the case where $F$ is disconnected remains entirely unexplored. In this paper, we provide a complete solution to this problem. We prove that for every disconnected graph $F$ with $|E(F)| \ge 2$, there exist infinitely many $F$-irregular graphs. Conversely, if $|E(F)| \le 1$, we show that no non-trivial $F$-irregular graph exists.
Read the full abstract
Commutative Algebra
Waring rank of certain complete intersection forms
The complete intersection forms are the homogeneous polynomials whose annihilator ideal or the Macaulay dual, is an Artinian complete intersection ideal. In this paper, we compute the Waring rank of certain complete intersection forms. As an application, we compute the Waring rank of binomials whose annihilator is a complete intersection ideal. Further, we also compute the Waring rank of the product of binary forms in different sets of variables.
Read the full abstract
Analysis of PDEs
Frequency-dependent capacitance matrix formulation for Fabry–Pérot resonances. Part II: One-dimensional periodic media
We study Bloch resonances of one-dimensional periodic systems of high-contrast resonators beyond the subwavelength regime. An exact transfer-matrix formulation identifies the limiting wavenumbers with the union of the interior Neumann frequencies and the Dirichlet frequencies of the separating intervals. At each fixed reference wavenumber, we introduce a periodic frequency-dependent capacitance matrix whose positive eigenvalues determine all leading square-root splittings in the contrast parameter. A direct cyclic matching expansion proves the approximation, including multiple eigenvalues and small complex contrasts. A spectral exclusion result outside the limiting set yields a direct bandgap statement. At a common resonance of all intervals, we also derive uniform eigenmode approximations and distinguish the zero-frequency mode from nonzero double Bloch eigenvalues. For positive contrast, exact linear crossings are characterized by the monodromy matrix being proportional to the identity. A complete local classification is obtained for two resonators per cell and, through band folding, for fully symmetric arrays with any number of resonators per cell. We further formulate the weighted Zak phase for isolated bands and its quantization under reflection symmetry. Explicit two-resonator formulas and numerical illustrations complement the analysis.
Read the full abstract
Combinatorics
Prescribed and simultaneous failures of log-concavity in trees with perfect matchings
We construct trees with perfect matchings and independence sequences that fail log-concavity near the independence number $\alpha$. For every integer $k\geq1$, one family fails at $\alpha-k$ and has a witness of order $O(k^2\log(k+2))$. For every integer $t\geq2$, a single tree has simultaneous failures at $\alpha-1,\alpha-3,\ldots,\alpha-(2t-1)$, with a witness of order $O(t^3)$. All these trees satisfy $\alpha=N/2$, where $N$ is the number of vertices, and contradict Conjecture 4.2 of Ramos and Sun. A sufficient condition uses a fixed tree and the numbers of attached leaves. For fixed $k$ or $t$, explicit bounds give geometric decay of $a_j^2/(a_{j-1}a_{j+1})$ at these indices as the trees grow; $a_j$ counts independent $j$-sets. The proofs count independent sets by empty matching pairs. The Lean proof assistant checks formal proofs of the parameterized results and their quantitative bounds; exact 90- and 180-vertex examples illustrate the constructions.
Read the full abstract
Statistics Theory · Cross-listed from stat.ME
Multilevel Main Effects Matrix Factor Model
We propose a multilevel main effects matrix factor model (MMEFM) to extract meaningful row and column effects from groups of matrix data. As a generalization of a multilevel matrix factor model, we provide rigorous definitions of MMEFM and identifications, together with iterative algorithms for the estimators of all global and local components in the main effects and common component, including global/local main effects and core ranks, with rates of convergence spelt out. An important feature of the model is that all main effects can be nonstationary and still be consistently estimated at each time point. At the same time, our estimated global common factors are alignment independent, and hence are truly global, and can be presented and given interpretations more easily. We propose a Bootstrap procedure for detecting the existence and identifying the groups of data that are driven by the global common factors. The power of the test, together with the accuracy of various estimators, are demonstrated in extensive simulation settings. Estimation performance is also compared to other state-of-the-art methods for matrix time series by simulations and a set of U.S. equity data. All numerical works are done using the R package MMEFM, which is available at CRAN.
Read the full abstract
Dynamical Systems
Nonuniform dichotomies via time rescaling
We establish characterizations of general nonuniform dichotomies for linear nonautonomous dynamical systems in terms of nonuniform exponential dichotomies of appropriately time-rescaled systems. In discrete time, for a class of slowly growing rates, such a characterization requires an additional condition involving a suitable notion of nonuniform ordinary dichotomy, which can be omitted for invertible systems. In continuous time, we obtain a more general characterization for a large class of growth rates, without imposing this additional condition. Our approach does not rely on adapted Lyapunov norms and applies to evolution families on arbitrary Banach spaces. As applications, we show how several results concerning general nonuniform dichotomies can be derived from their counterparts for exponential dichotomies.
Read the full abstract
Optimization and Control · Cross-listed from cs.DS
A Practical Combinatorial Interior Point Method for Minimum-Cost Flow
In a recent breakthrough, Chen, Kyng, Liu, Peng, Probst Gutenberg, and Sachdeva (arXiv:2203.00671) designed the first almost-linear-time algorithm for minimum-cost flow. Their approach uses an Interior Point Method (IPM) to achieve complexity $m^{1+o(1)}\log U \log C$. However, the $m^{1+o(1)}$ factor hides intricate recursive data structures, large constants and multiple log factors. In this paper, we give an implementation following the core ideas of their IPM with practical data structures and empirically obtained decision rules. We compare our solver with the cost scaling and network simplex solvers of LEMON on the instance families of the DIMACS Flow Challenge 2.0 core benchmark. Our implementation scales competitively on five of twelve families and better on two. On grid_wide we observe close to linear scaling: $m^{1.04}$ against $m^{1.48}$ for LEMON. We read these results as first evidence that the almost-linear-time framework can be relevant in practice, discuss our insights gained during the implementation process, and motivate where future work should focus to bridge the theory-practice gap.
Read the full abstract
Analysis of PDEs
Attainment of the sharp stability constant of Beckner conformal log-Sobolev inequality
The existence of minimizer for stability of the fractional Sobolev inequality and the stability of Beckner conformal Log-Sobolev inequality (the endpoint case of fractional Sobolev inequality) have been established by König and Chen-Lu-Tang. The existence of minimizer for stability of the Log-Sobolev inequality is unsolved. In this paper, we solve this problem. For every $n\geq2$, we prove that the sharp $L^2$-stability constant of Beckner conformal log-Sobolev inequality on $\mathbb S^n$ is attained and is strictly less than $\frac{2\log2}{n}$. Moreover, the normalized stability constant of the fractional Sobolev inequality converges to the stability constant of the log-Sobolev inequality as $s\to0^+$. After Hersch normalization, every sequence of $L^{p_{s_k}}$-normalized minimizers for stability of the fractional Sobolev inequality, with $s_k\to0^+$, has a subsequence converging strongly in $L^2(\mathbb S^n)$ to an $L^2$-normalized minimizer of stability of the log-Sobolev inequality.
Read the full abstract
Algebraic Geometry
Lifting Prym Divisors on a Bielliptic Loop of Loops
Let $C$ be a bielliptic curve over an algebraically closed nonarchimedean field of odd characteristic or characteristic zero, and let $f \colon \widetilde{C} \to C$ be an étale double cover. We prove that, if $f$ specializes to a certain double cover of a loop of loops, then every Prym divisor on the loop of loops lifts to a Prym divisor of the same rank on $\widetilde{C}$. As consequences, we compute the dimension of the Prym-Brill-Noether variety $V^r (C,f)$, show that it is reduced and irreducible when the dimension is positive, and compute its cohomology class.
Read the full abstract
Number Theory
Untrodden pathways in the study of partitions with parts separated by parity
In this paper, we study a partition function with parts separated by parity from a family of partition functions introduced by Andrews in 2019. We first show that its generating function admit representation in terms of mock modular forms of weight $3/2$. We then initiate a study of smallest-part partition function analogues of partitions with parts separated by parity, which, to the best of our knowledge, has not previously been investigated in the literature. We show that the generating functions of these smallest-part partition functions are likewise expressible in terms of mock modular forms, mock Maass theta functions and Zagier's $q$-series $H(q)$, which he describes as a “half-derivative of the Dedekind eta-function". Our study also leads to new combinatorial interpretations of the coefficients of the aforementioned mock modular form, function $\sigma^*(q)$, and mock theta functions $\psi(q)$ and $A(q)$ in terms of odd Ferrers graphs. Moreover, we provide a quantum $q$-series identity involving Ramanujan's famous $\sigma(q)$ function. We also derive the leading asymptotic term of one of these partition functions, whose generating function we first express in terms of $\sigma^*(q)$.
Read the full abstract
Classical Analysis and ODEs
Endpoint power weight inequalities for spherical maximal functions
We prove sharp $L^p(|x|^\alpha)$ estimate for spherical maximal functions. We resolve the remaining open problem for the full maximal operator for $\alpha=1-d$ and $p<2$ and prove a more general result involving a local version of Assouad dimension of the underlying dilation set. We also make a case study with endpoint bounds for a model case involving convex sequences in $[1,2]$.
Read the full abstract
Probability
Critical oriented percolation enhanced along random supercritical horizontal lines
We consider the oriented site percolation model in a random environment introduced by Kesten, Sidoravicius and Vares (2022), in which the horizontal lines of the lattice are independently declared bad or good, sites being open with a probability that depends only on the type of their line. We study the boundary case where the bad lines are critical and the good ones supercritical, so that the model is critical oriented site percolation enhanced along a random set of good lines. We prove that percolation occurs for any positive density of the good lines. An arbitrarily sparse set of arbitrarily weakly enhanced lines suffices, the density of good lines and the strength of the enhancement being decoupled. The proof adapts the renormalization scheme of Archer, Hartarsky, Kolesnik, Olesker-Taylor, Schapira and Valesin (2026). We show that the edge of the process travels at a positive speed, which yields crossing estimates for tilted boxes; during runs of bad lines, we rely on the box-crossing property of Duminil-Copin, Tassion and Teixeira (2018); and the renormalized model dominates the oriented percolation with geometric defects of Hilário, Sá, Sanchis and Teixeira (2026).
Read the full abstract
Analysis of PDEs
Global well-posedness for a damped two dimensional fluid–beam system
We study the normalized surface system of an irrotational incompressible fluid of infinite depth beneath an elastic Euler–Bernoulli beam with structural damping. For every fixed damping coefficient $\gamma>0$, we establish global well-posedness for arbitrary initial data in $H^2(\R)\times\bigl(\dot H^{1/2}(\R)\cap\dot H^1(\R)\bigr)$. The main novelty is that the admissible data include finite energy initial potentials for which neither $\psi_0$ nor $u_0=\psi_0+G(\eta_0)\psi_0$ has an $L^2$ representative. We also prove the exact energy dissipation identity at the regularity of the constructed solutions. The main analytical difficulties are the possible failure of $L^2$ integrability at low frequencies and the justification of energy differentiation at the solution regularity. To handle the low-frequency difficulty, we fix the low-frequency part of the initial potential and evolving an $L^2$ remainder. Homogeneous Dirichlet–Neumann estimates and a high-frequency Fourier symmetrizer yield local well-posedness with $H^{-1}$ forcing. Continuous Fréchet differentiability of the energy in these affine coordinates, together with a chain rule on $H^1\subset L^2\subset H^{-1}$, justifies the dissipation identity. The Energy identity and coercivity provide uniform bounds that yields global continuation tharough the local theory. Iterating the local uniqueness and stability estimates gives global uniqueness within the stated affine solution class and Lipschitz dependence on bounded sets over every finite time interval.
Read the full abstract
Category Theory
Actions in varieties of non-associative algebras: a survey
This article surveys the main results on the representability of internal actions in varieties of non-associative algebras over a field. We begin by recalling the general framework of internal actions and split extensions in semi-abelian categories, before specialising to Orzech categories of interest and varieties of non-associative algebras. We discuss action representability, weak action representability, and action accessibility, with emphasis on the relationship between the latter two notions. We then describe the constructions of the universal strict general actor in Orzech categories of interest and the external weak actor in action accessible, operadic varieties of non-associative algebras over a field, as well as their role in the study of weak action representability. We also give a tensor-domain formulation of partial algebras and adapt the construction of the external weak actor to this setting. These notions are illustrated by examples arising from associative, Lie, Leibniz, Jacobi-Jordan, anti-commutative anti-associative, alternative, and $2$-nilpotent algebras. We conclude with a summary of the known results and some open questions for future research.
Read the full abstract
Classical Analysis and ODEs
Weighted Norm Inequalities for Maximal Multi-sublinear Rough Singular Integrals
We continue our study of multilinear rough homogeneous singular integrals by establishing weighted estimates for their maximal truncations. Let $m\ge2$ and let $\Omega\in L^q(\mathbb{S}^{mn-1})$, $1<q\le\infty$, have mean zero. For $1<p_1,\dots,p_m<\infty$ with $p_j\ge q'$ and $1/p=\sum_{j=1}^m1/p_j$, we prove $$\big\Vert \mathcal{L}_\Omega^*(f_1,\dots,f_m)\big\Vert_{L^p(v_{\vec{\boldsymbol{w}}})} \lesssim \Vert\Omega\Vert_{L^q(\mathbb{S}^{mn-1})} \prod_{j=1}^m\Vert f_j\Vert_{L^{p_j}(w_j)}$$ whenever $\vec{\boldsymbol{w}}=(w_1,\dots,w_m)\in A_{(p_1/q',\dots,p_m/q')}$, where $q'$ is the Hölder conjugate of $q$ and $v_{\vec{\boldsymbol{w}}}=\prod_{j=1}^m w_j^{p/p_j}$. The estimate holds under the same multiple weight condition as the corresponding principal value estimate.
Read the full abstract
Differential Geometry
A topological sphere theorem for pinched Legendrian submanifolds
Let $M^n$ be a closed simply connected Legendrian submanifold of $\mathbb S^{2n+1}$, where $n\geq5$, and let $\mathbf{B}$ and $\mathbf{H}=\operatorname{tr}\mathbf{B}$ denote its second fundamental form and mean-curvature vector. We prove that $M$ is homeomorphic to $\mathbb S^n$ if \begin{equation*} |\mathbf{B}|^2\leq \frac{(n-1)(n+2)}n+\frac{n^2+3n-2}{2n^2}|\mathbf{H}|^2-\frac{(n-1)(n-2)}{2n^2}|\mathbf{H}|\sqrt{|\mathbf{H}|^2+4n}. \end{equation*} The equality can be attained by the Calabi products, so simple connectivity cannot be omitted. For $n\geq4$, we also prove a sphere theorem under an explicit bound and the weaker assumption $b_1(M;\mathbb R)=0$. The proof combines phase-rotated Lawson–Simons variations with a systolic inequality for finite two-complexes. We also give local constructions showing that the pinching condition allows negative isotropic curvature at a point.
Read the full abstract
Optimization and Control · Cross-listed from eess.SY
On Over-Conservatism Under Low-Probability Extreme Events: A KL-Regularized Wasserstein Distributionally Robust Planning Method
The increasing penetration of renewable energy makes power systems more vulnerable to low-probability extreme events, elevating system planning to a critical role in ensuring reliability. Distributionally robust optimization (DRO) based on the Wasserstein distance is widely used to address this challenge. However, we find that the conventional Wasserstein ambiguity set tends to excessively amplify the probabilities of low-probability extreme events, leading to over-conservative investment decisions. To mitigate this over-conservatism, this paper proposes a novel ambiguity set that modifies the Wasserstein distance with a Kullback-Leibler (KL) divergence regularization term. By leveraging the KL divergence's sensitivity to relative probability changes, the proposed set effectively curbs the unrealistic magnification of low-probability events. A two-stage distributionally robust planning model built upon this new ambiguity set is developed to optimize the installed capacity of photovoltaic, wind, and energy storage. The complex model is then reformulated as an equivalent exponential cone program with strict theoretical proofs, making it computationally tractable. Numerical results on the PJM 5-bus and IEEE 118-bus systems reveal the over-conservatism of standard Wasserstein DRO under low-probability extreme events and validate the effectiveness and efficiency of the proposed planning model and solution algorithm.
Read the full abstract
Logic · Cross-listed from cs.LO
Finite-on-Top-of-Temporal CSPs in Fixed-Point Logic
We study definability in fixed-point logic with counting (FPC) for a class of constraint satisfaction problems (CSPs) that simultaneously generalises finite-domain CSPs and temporal CSPs. The templates for the CSPs are first-order expansions of the structure $([k] \times {\mathbb Q};<_1,\dots,<_k,\sim)$ where $<_i \, := \{((i,x),(i,x')) \mid x<x'\}$ and $\sim \, := \{((i,x),(i,x')) \mid i \in [k], x,x' \in {\mathbb Q}\}$, i.e., $k$ copies of $({\mathbb Q};<)$. Such a CSP is definable in FPC precisely when the template pp-constructs neither the ternary temporal relation $X$, which holds on three elements if the minimum is attained exactly twice, nor a nontrivial finite affine structure. Equivalently, the template has global polymorphisms that witness the tractability of the temporal CSPs on the copies, and that provide 3-4 weak near-unanimity operations on the set of copies of ${\mathbb Q}$. In this case, we prove that the CSP is even expressible in the less expressive logic FP$^*$, which is the restriction of FPC without counting terms (i.e., the extension of first-order logic by a fixed point operator and an ordered auxiliary number sort). Our algorithm samples finitely many values in each copy and then performs nested constraint-singleton consistency tests (which is a uniform polynomial-time algorithm for finite-domain CSPs). The correctness proof uses finite-domain CSP theory to combine consistency certificates by a single polymorphism term, fixing each variable to one copy without destroying the certificates needed for the temporal algorithm. We then use a known normal form for algebraic products to control the remaining interactions between different copies.
Read the full abstract
Dynamical Systems · Cross-listed from gr-qc
Stable manifolds of heteroclinic chains in Hořava-Lifshitz cosmology
We consider vacuum spatially homogeneous models in Hořava-Lifshitz gravity, which are expected to describe generic singularities for these modified gravity theories. These models perturb the well-known Bianchi models in general relativity (GR) by a parameter $v\in (0,1)$, in which GR occurs at $v=1/2$. We show that all periodic heteroclinic chains of Bianchi type II orbits are robust for small perturbations of GR, i.e. they exist for any $v\approx 1/2$. Moreover, we prove the existence of a stable manifold for each heteroclinic chain within a Cantor set for the supercritical case, $v\in (1/2,1)$. In particular, we discuss the heteroclinic chains of periods three and four in detail.
Read the full abstract
Number Theory
Higher rank elliptic sieve via CM endomorphisms
A theorem of Landau and Ramanujan states that almost all integers are not sums of two squares (when ordered by their absolute value). Equivalently, almost all integers are not norms from the Gaussian rationals $\mathbb{Q}(i)$. In this paper, we prove a version of this norm result for elliptic curves $E$. Let $E$ be an elliptic curve over a number field $K$ with complex multiplication, such that $K$ contains the endomorphism ring of $E$. For a fixed non-torsion point $P \in E(K)$ and an abelian extension $L/K$, we show that subject to a technical condition, the $y$-coordinate of almost all multiples of $P$ does not belong to the norm group of $L$. The proof is an adaptation of an argument of Bhakta et al. , whose main tools are elliptic divisibility sequences and a sieve technique known as the elliptic sieve. To account for the points in $E(K)$ arising from the additional endomorphisms, we apply the elliptic sieve to elliptic nets, a higher-rank generalisation of elliptic divisibility sequences. This approach demonstrates the possibility of applying the elliptic sieve to $\mathbb{Z}$–linear combination of points on elliptic curves and the usefulness of elliptic nets to counting problems on elliptic curves.
Read the full abstract
Combinatorics
Goodman-type lower bounds for odd cycles I: The dense regime
Goodman proved a lower bound on triangle counts which, in graphon language, states that every graphon of edge density $p$ has triangle density at least $2p^2-p$. Bennett, Dudek, Lidický, and Pikhurko established the corresponding bound for $C_5$, determining its minimum density at every Turán density $p=1-1/k$ with an integer $k\ge3$. We extend this bound to every odd cycle in the dense regime: for every odd integer $m\ge3$ and every graphon $W$ with edge density $p\ge2/3$, $t(C_m, W) \ge p^m-p(1-p)^{m-1}.$ For $2/3\le p<1$, equality holds precisely for balanced complete $k$-partite graphons with an integer $k\ge3$, up to graphon equivalence, and we establish qualitative stability at these densities. In the same density range, we also strengthen Kim and Lee's density-sensitive commonality inequality for odd cycles by adding the nonnegative term $t(P_{m-1},1-W)-(1-p)^{m-1}$ to the lower bound, where $P_{m-1}$ is the path with $m-1$ edges. To prove the main results, we develop a spectral excursion expansion and use Dirichlet averaging to reduce the resulting polynomial inequalities in arbitrarily many spectral variables to a one-variable problem. We prove the one-variable inequality through a uniform inequality comparing odd and even moments of shifted Gamma random variables. We also formalise the odd-cycle lower-bound theorem in Lean 4.