Peer Revenue Returns subject to peer review

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

Mathematics

math Watch Mathematics (sign in to use)

Thursday 19 March

Combinatorics

The red-blue-yellow matching problem

We consider the red-blue-yellow matching problem: given two natural numbers $k_R$, $k_B$ and a graph $G$ whose edges are colored red, blue or yellow, the goal is to find a matching of $G$ that contains exactly $k_R$ red edges and exactly $k_B$ blue edges, and is of maximum cardinality subject to these constraints. This is a natural generalization of the well known red-blue matching problem, whose complexity status is unknown: although a randomized polynomial-time algorithm exists, a deterministic algorithm has remained elusive for nearly four decades. The best known deterministic approach to the red-blue matching problem, due to Yuster (2012), gives an additive approximation. In this paper, we show a similar result for the red-blue-yellow matching problem, giving a polynomial-time deterministic algorithm that, under natural assumptions, finds a matching satisfying the color requirements almost exactly and has cardinality within 3 of the optimal solution. Our algorithm is a mix of classic linear programming techniques and ad hoc existence results on restricted classes of graphs such as paths and cycles. As a key ingredient, we prove a curious topological property of plane curves, which is a strengthened version of a result by Grandoni and Zenklusen (2010) in the related context of budgeted matchings.
Read the full abstract

Commutative Algebra

Simis and packing properties of Alexander dual of connected ideals

In this article, we investigate when the ordinary and symbolic powers of the Alexander dual of connected ideals of graphs coincide, and provide a complete classification of all such graphs. Furthermore, we prove Conforti–Cornuèjols conjecture for this class of ideals.

Probability

Invariance principles for rough walks in random conductances

We establish annealed and quenched invariance principles for random walks in random conductances lifted to the p-variation rough path topology, allowing for degenerate environments and long-range jumps. Our proof is based on a unified structural strategy where pathwise convergence is viewed as a natural upgrade of the classical theory. This approach decouples the martingale lift from terms involving the integrals with respect to the corrector and the quadratic covariations. In the quenched regime, we show that the existence of a stationary potential for the corrector with $2+\epsilon$ moments is sufficient to ensure the vanishing of the corrector in $p$-variation for any $p>2$. This input, combined with our structural framework, provides a direct and modular pathway to rough path convergence. We further provide a transfer lemma to construct this potential from spatial moment bounds. While presently verified in the literature primarily for nearest-neighbor settings, our formulation isolates the exact analytic input required for pathwise convergence in more general environments.
Read the full abstract

All authors Johannes Bäumler, Noam Berger, Tal Orenshtein, Martin Slowik

Optimization and Control

Second-Order Conditions for Infinite-Horizon Semilinear Parabolic Control Problems without Tikhonov Regularization

We consider semilinear parabolic optimal control problems subject to Neumann boundary conditions, control constraints, and an infinite time horizon. The control constraints are pointwise in time, but they can be pointwise or integral in the space variable. Crucially, the optimal control problem does not include a Tikhonov regularization in the cost functional, which provides a major difficulty in the extension of the classical finite-horizon theory to infinite-horizon optimal control problems. As a consequence of our findings, we establish a sufficient second-order optimality condition and prove that local optimal states of the finite-horizon problems approximate local optimal states to the infinite-horizon problem as the horizon tends to infinity.
Read the full abstract

Analysis of PDEs

Neumann problem with a discontinuous nonlinearity

This study is devoted to proving the existence of weak solutions for a nonlinear elliptic problem with Neumann-type boundary data. The problem is driven by a discontinuous power nonlinearity and a nonsmooth prescribed data. Additionally, we aim to derive an estimate that proves the well-posedness of the problem. This estimate serves as an evidence for the uniqueness of the existing solution when the boundary term is “smooth".
Read the full abstract

Optimization and Control

Scheduling Ground-Based Telescope Observations with Uncertain Nights

The observation of celestial objects is a fundamental activity in astronomy. Ground-based and space telescopes are used to gather electromagnetic radiation from space, allowing astronomers to study a wide range of celestial objects and phenomena, such as stars, planets, galaxies, and black holes. The European Southern Observatory (ESO) charges each night 83 kEUR (Milli et al. 2019), so the schedules of the telescopes are really important in order to optimize every second. Ground-based telescopes are affected by meteorological conditions, such as clouds, wind, and atmospheric turbulence. Accurate scheduling of observations in the presence of such uncertainties can significantly improve the efficiency of telescopes use and support from automated tools is highly desirable. In this paper, we study a mathematical approach for scheduling ground-based telescope observations under an uncertain number of clear nights due to uncertain weather and atmospheric conditions. The model considers multiple targets, uncertain number of nights, and various observing constraints. We demonstrate the viability and effectiveness of an approach based on stochastic optimization and reactive strategy comparing it against other methods.
Read the full abstract

All authors Thomas Rahab Lacroix, Pierre Lemaire, Anne-Marie Lagrange, Julien Milli, Nadia Brauner

Numerical Analysis

Reconstructions of Single Pixel X-Ray Transforms with Applications in Nuclear-Disarmament Verification

In nuclear arms control and disarmament processes, it is crucial to determine whether an object is a nuclear weapon or not without revealing sensitive information about it. At the MIT: Laboratory for Nuclear Security and Policy, such a nuclear verification method was developed, showcasing a transmission-based approach [1]. This method's essential part rests on a mathematical operation, the Single-Pixel X-Ray Transform: a cone of X-rays transmits an object and the remaining intensity is measured with a single-pixel detector. This transformation and the recovery of objects from dimensionless single-pixel measurements more generally has only been analyzed to a limited extent. In this work, we investigate some of the Single Pixel X-Ray Transform's mathematical properties. More specifically, we show that the Single Pixel X-ray transform is non-linear, continuous, Fréchet-differentiable and convex. We also introduce a method of reconstructing an object based only on a finite number of dimensionless, noisy Single Pixel X-Ray Transform measurement values. This method is based on Douglas-Rachford splitting and uses total variation denoising. We present an implementation for this method, focusing on rotational symmetric objects, as they allow the use of a one-dimensional direct total variation denoising algorithm [2].
Read the full abstract

Optimization and Control

Non-linear in-band interference cancellation on base of conjugate gradients method

This paper investigates one possible solution to the problem of self-interference cancellation (SIC) arising in the design of in-band full-duplex (IBFD) communication systems. Self-interference cancellation is performed in the digital domain using multilayer nonlinear models adapted via gradient-based optimization. The presence of local minima and saddle points during the adaptation of multilayer models limits the direct use of second-order methods due to the indefiniteness of the hessian matrix. The mixed Newton method can address the saddle-point issue; however, it requires significant computational resources. In this work, a conjugate gradient (CG) method constructed on the base of the mixed Newton method (MNM) is proposed. The method exploits information from mixed second-order derivatives of the loss function without explicit computation the full hessian matrix. As a result, the proposed approach achieves a higher convergence rate than first-order methods while requiring significantly lower computational resources than conventional second-order methods when adapting multilayer nonlinear self-interference cancellers in full-duplex communication systems.
Read the full abstract

Commutative Algebra

Bass numbers of local cohomology modules at the first and last non-vanishing levels

Let $R $ be a commutative Noetherian ring, $\mathfrak{a}$ be an ideal of $R$ and $M$ be a finitely generated $R$-module. In this paper, we study the Bass numbers $\{\mu^i(\mathfrak{p}, H^j_{\mathfrak{a}}(M))\} $ of local cohomology modules with respect to an ideal $\mathfrak{p}\in Spec(R)$ in each of the following cases: $i\in \{ 0, 1, 2\}$ and $j= grade_{\mathfrak{a}}(M),$ $R$ is regular and $i\in\{ ht(\mathfrak{p}), ht(\mathfrak{p})- 1\}$ and $j= cd_{\mathfrak{a}}(M)$, the cohomological dimension of $M$ with respect to $\mathfrak{a}$.
Read the full abstract

Mathematical Physics · Cross-listed from cond-mat.stat-mech

Thermal relaxation asymmetry persists under inertial effects

Relaxation phenomena far from thermal equilibrium feature a rich phenomenology, including the thermal relaxation asymmetry. The latter states that heating occurs faster than cooling in overdamped harmonic systems quantified in terms of excess free energy and entropy production. Upon isolating the relevant relaxational contribution to the entropy production, we here algebraically prove the asymmetry in thermal relaxation in phase space in the entire range from overdamped dynamics to underdamped dynamics. We show that for the same setup as for overdamped dynamics (i.e., motion in harmonic potentials, also known as Ornstein-Uhlenbeck dynamics), even in the more general case of phase-space relaxation, i.e., underdamped dynamics, far-from-equilibrium heating is faster than cooling. The coupling of positions and velocities emerging in this generalization further underscores, in a striking manner, the intricate dynamics of such thermal relaxation processes that do not pass through local equilibria. Investigating the overdamped limit, our generalized approach reveals, interestingly, that an excess free energy contribution from the velocity degrees of freedom does not trivially vanish in the overdamped limit, but is instead affected by the precise interpretation of temperature quenches in overdamped systems.
Read the full abstract

Optimization and Control · Cross-listed from cs.DS

Resource-Constrained Joint Replenishment via Power-of-$m^{1/k}$ Policies

The continuous-time joint replenishment problem has long served as a foundational inventory management model. Even though its unconstrained setting has seen recent algorithmic advances, the incorporation of resource constraints into this domain precludes the application of newly discovered synchronization techniques. Such constraints arise in a broad spectrum of practical environments where resource consumption is bounded as an aggregate rate over time. However, for nearly four decades, the prevailing approximation guarantee for resource-constrained joint replenishment has remained $\frac{ 1 }{ \ln 2 } \approx 1.4427$, achieved via classical power-of-$2$ policies. In this paper, we circumvent these structural policy restrictions by devising generalized rounding frameworks, demonstrating that a well-known convex relaxation is much tighter than previously established. In particular, we expand our analytical scope to encompass fractional base expansion factors, randomized shifting, and staggered interleaved grids. Through this multifaceted methodology, we present a sequence of gradually improving performance guarantees. First, by proposing a best-of-two framework that exploits structural asymmetries between deterministic power-of-$m^{1/k}$ policies, we surpass the classical barrier to obtain a $1.3776$-approximation. Second, by injecting a random shift into the logarithmic grid domain and formulating a factor-revealing linear program to optimize a dual-policy approach, we attain a $1.2512$-approximation. Finally, by superimposing a secondary offset grid to subdivide rounding intervals and suppress holding cost inflation, we utilize interleaved policies to arrive at our ultimate approximation ratio of $\frac{5}{6\ln 2} \approx 1.2023$, which is proven to be best-possible for the class of interleaved power-of-$m^{1/k}$ policies.
Read the full abstract

Combinatorics

More Shattering News

An ordered variant of the well-known set theory concept of shattering was introduced by Anstee, Rónyai, and Sali. In this paper, we prove several new results related to order shattering. Given a family $\mathcal F$ of subsets of $[n]$, we show that $\mathrm{osh}(\mathcal F)$, the family of all sets order shattered by $\mathcal F$, coincides with $T(\mathcal F)$, the family obtained from $\mathcal F$ by the down-shift operation. We then give a full characterization of all sets that can be order shattered by some $\ell$-Sperner family. Finally, we completely determine $\mathrm{osh}\left(\binom{[n]}{a}\cup\binom{[n]}{b}\right)$.
Read the full abstract

Optimization and Control

A mathematical framework for time-delay reservoir computing analysis

Reservoir computing is a well-established approach for processing data with a much lower complexity compared to traditional neural networks. Despite two decades of experimental progress, the core properties of reservoir computing (namely separation, robustness, and fading memory) still lack rigorous mathematical foundations. This paper addresses this gap by providing a control-theoretic framework for the analysis of time-delay-based reservoir computers. We introduce formal definitions of the separation property and fading memory in terms of functional norms, and establish their connection to well-known stability notions for time-delay systems as incremental input-to-state stability. For a class of linear reservoirs, we derive an explicit lower bound for the separation distance via Fourier analysis, offering a computable criterion for reservoir design. Numerical results on the NARMA10 benchmark and continuous-time system prediction validate the approach with a minimal digital implementation.
Read the full abstract

All authors Anh-Tuan Clabaut, Jean Auriol, Islam Boussaada, Guilherme Mazanti

Algebraic Topology

Cohomology of dilute Temperley–Lieb algebras

Dilute Temperley–Lieb algebras are variants of Temperley–Lieb algebras arising in statistical mechanics in the study of solvable lattice models. In this paper we prove that the (co)homology of dilute Temperley–Lieb algebras vanishes in all positive degrees.

Optimization and Control

Stabilization of Integral Difference Equations by Solving a Corona Problem

This paper proposes a stabilizing state-feedback control law for vector-valued state systems with a scalar control input, governed by a general class of integral difference equations that incorporate both pointwise and distributed input delays. The proposed controller is expressed through integral operators acting on the state and input histories over a finite time horizon. Closed-loop stability is established by characterizing the controller kernels as solutions to a convolution equation arising from a Corona problem. The existence of such solutions is ensured under a suitable spectral stabilizability condition, and a least-square procedure is implemented to find them numerically. The approach extends existing IDE stabilization results to more general settings, allowing for arbitrary numbers of pointwise delays affecting both the state and input, without requiring commensurability assumptions.
Read the full abstract

Dynamical Systems · Cross-listed from eess.SY

Assessing performance tradeoffs in hierarchical organizations using a diffusive coupling model

We study a continuous-time dynamical system of nodes diffusively coupled over a hierarchical network to examine the efficiency and performance tradeoffs that organizations, teams, and command and control units face while achieving coordination and sharing information across layers. Specifically, after defining a network structure that captures real-world features of hierarchical organizations, we use linear systems theory and perturbation theory to characterize the rate of convergence to a consensus state, and how effectively information can propagate through the network, depending on the breadth of the organization and the strength of inter-layer communication. Interestingly, our analytical insights highlight a fundamental performance tradeoff. Namely, networks that favor fast coordination will have decreased ability to share information that is generated in the lower layers of the organization and is to be passed up the hierarchy. Numerical results validate and extend our theoretical results.
Read the full abstract

Probability

Pareto points in growing dimensions

We consider $n$ independent random points uniformly distributed in the $d_n$-dimensional unit cube and study Pareto points, that is, points that do not coordinatewise dominate any other point. We identify the critical growth rate of $d_n$ at which a phase transition occurs: below this threshold, the number of non-Pareto points diverges in probability, whereas above it there are asymptotically no such points. At criticality, the number of non-Pareto points converges in distribution to a Poisson random variable. We further describe their asymptotic spatial distribution in terms of convergence of random point measures. We also investigate points that dominate exactly $r$ other points and establish analogous phase transitions. For $r=1$, the critical dimension is the same as for non-Pareto points, whereas for every fixed $r\geq 2$ it is different, but, surprisingly, common to all such $r$.
Read the full abstract

General Mathematics

Local Morphology of the Partition Graph

For a fixed integer $n$, let $G_n$ be the graph whose vertices are the partitions of $n$, with adjacency defined by a single elementary transfer of a cell in the Ferrers diagram. In a previous paper, the clique complex $K_n = \mathrm{Cl}(G_n)$ was studied from a global homotopy-theoretic point of view. This paper studies instead the local combinatorics of the graph $G_n$ itself. For a partition $\lambda=(s_1^{m_1},\dots,s_t^{m_t})$, where $s_1>\dots>s_t>0$, we describe the admissible transfers from $\lambda$ in terms of its block structure. This yields a bipartite graph $B(\lambda)$ obtained from $K_{t,t+1}$ by deleting two explicitly determined families of edges, corresponding to singleton support blocks and unit support gaps. We prove that the graph induced on the neighborhood of $\lambda$ in $G_n$ is isomorphic to the line graph $L(B(\lambda))$. As consequences, we obtain an explicit formula for the degree of $\lambda$, a classification of all cliques through $\lambda$, and a formula for the maximal dimension of a simplex of $K_n$ containing $\lambda$. These local invariants are shown to depend only on an ordered binary datum associated with the support of $\lambda$. The results provide a local structural description of the partition graph and a combinatorial language for the study of larger-scale features of $G_n$.
Read the full abstract

Differential Geometry

On the Killing property of the defining vector field for an almost Yamabe soliton

In this paper, we first investigate almost Yamabe solitons on compact Riemannian manifolds without boundary of dimension greater than or equal to two. We provide some sufficient conditions for which the defining conformal vector field associated to a compact almost Yamabe soliton is a Killing vector field. We then study almost Yamabe solitons on complete, non-compact Riemannian manifolds. We prove the Killing property of the defining conformal vector field associated to a complete, non-compact almost Yamabe soliton under certain conditions when the dimension is strictly greater than two.
Read the full abstract

Mathematical Physics

The Lee-Yang property of isotropic vector ferromagnets and lattice fields

The Lee-Yang property of a given spin model means that its partition function has purely imaginary zeros as a function of an external magnetic field. A similar property is also used in the theory of quantum anharmonic crystals and quantum lattice fields. A number of powerful analytic methods of the mathematical theory of such models employ this property. Its suitable generalization is used in the theory of models of isotropic $D$-dimensional spins (rotors) or $D$-component quantum lattice fields. So far, the (generalized) Lee-Yang property has been established only for two-dimensional isotropic models. In this work, we prove that isotropic spin and field models living on $\mathds{Z}$ have this property for all even $D$.
Read the full abstract

Combinatorics

$t$-tone colorings of outerplanar and Halin graphs

A $t$-tone $k$-coloring of a graph $G$ assigns a set of $t$ distinct colors from $\{1, \dots, k\}$ to each vertex so that vertices at distance $d$ share fewer than $d$ common colors. The $t$-tone chromatic number of $G$ is the minimum $k$ such that $G$ has a $t$-tone $k$-coloring. This paper investigates the $t$-tone coloring of two specific subclasses of planar graphs: subcubic outerplanar graphs and Halin graphs. We provide a complete characterization of the $2$-tone chromatic number for subcubic outerplanar graphs and establish a sharp upper bound for their $3$-tone chromatic number. We then turn to Halin graphs and prove that every cubic Halin graph of order $n \ge 6$ is $2$-tone $7$-colorable. Moreover, we derive an upper bound on the $2$-tone chromatic number for Halin graphs with arbitrary maximum degree.
Read the full abstract

Mathematical Physics · Cross-listed from quant-ph

Schrödinger Bridges via the Hacking of Bayesian Priors in Classical and Quantum Regimes

Bayes' rule is widely regarded as the canonical prescription for belief updating. We show, however, that one can arbitrarily preserve pre-specified beliefs while appearing to perform Bayesian updates via "prior hacking": engineering a reference prior distribution such that, for a fixed channel and evidence, the update matches a chosen target distribution. We prove that this is generically possible in both classical and quantum settings whenever Bayesian inversions are well-defined (with the Petz recovery map as the quantum analogue to Bayes' rule), and provide constructive algorithms for doing so. We further establish a duality between prior hacking and Schrödinger bridge problems (a key object in statistical physics with applications in generative modelling), yielding in the quantum setting a unique, inference-consistent selection among candidate bridges. This formally establishes the Bayes-like updating that Schrödinger bridges are performing with respect to the process as opposed to the reference prior, both in classical and quantum settings.
Read the full abstract

Dynamical Systems

A Julia-Fatou Theory via Random Systems with Complete Connections

We develop a Julia-Fatou theory for random dynamical systems of continuous self-maps on compact metric spaces driven by random systems with complete connections (RSCCs). To each index, we assign either a family of continuous self-maps or a probability measure supported on such a family. Together with these assigned objects, a random index sequence gives rise to a random dynamical system on the compact metric space. Although the index process need not be a finite-order Markov chain, the recursively updated state process is a time-homogeneous Markov chain. For each state, we decompose the compact metric space into the Julia and Fatou sets. We also define the corresponding kernel Julia set and Julia sets along admissible paths. We further study the averaged dynamics on the product of the compact metric space and the state space and prove Cooperation Principle I. Under suitable assumptions, emptiness of the kernel Julia set at every state implies equicontinuity of the iterates of the adjoint transition operator on the whole space of probability measures. Moreover, for every initial state and finite Borel measure, the Julia set has measure zero along almost every admissible path. This extends previous results for graph-directed Markov systems with finitely many vertices and edges. We also identify a phenomenon specific to RSCCs, namely emptiness jumps of kernel Julia sets along admissible state trajectories. Such a jump may cause the kernel-emptiness hypothesis, which is used as a sufficient condition in Cooperation Principle I, to fail. We provide several conditions excluding these jumps. Examples motivated by mechanisms such as reinforcement illustrate both the jump phenomenon and the applicability of Cooperation Principle I to state-dependent selection rules.
Read the full abstract

Geometric Topology

On the simplest simply connected rational homology $7$-spheres that are not $2$-connected

We give a complete classification of two families of simply connected $7$-manifolds: $\mathcal{G}_{3}(\mathrm{Wu})$-like manifolds and $\mathcal{G}_{3}^{p}(S^{5})$-like manifolds for odd primes $p$. The former are non-spin with $H_{2}\cong H_{4}\cong \mathbb{Z}/2$ as their only nontrivial middle homology; the latter have $H_{2}\cong H_{4}\cong \mathbb{Z}/p$ as their sole nontrivial middle homology. These manifolds attain the minimal homological complexity among simply connected rational homology $7$-spheres that are not $2$-connected. We prove that Milnor's $\lambda$-invariant gives a bijection from the oriented diffeomorphism classes of $\mathcal{G}_{3}(\mathrm{Wu})$-like manifolds onto $\mathbb{Z}/7$, and each such manifold decomposes as the connected sum of a standard $\mathcal{G}_{3}(\mathrm{Wu})$-like manifold and a homotopy $7$-sphere. Analogously, the Eells-Kuiper $\mu$-invariant yields a bijection from the oriented diffeomorphism classes of $\mathcal{G}_{3}^{p}(S^{5})$-like manifolds to $\mathbb{Z}/28$, with every manifold splitting as the connected sum of a standard $\mathcal{G}_{3}^{p}(S^{5})$-like manifold and a homotopy $7$-sphere.
Read the full abstract

Optimization and Control

A Certifying MCKP Framework for $\Gamma$-Robust Discrete Pricing

We study finite-menu portfolio pricing under a ratio margin requirement, price-admissibility constraints, and integer-budget demand uncertainty. The pricing model reduces exactly to a multiple-choice knapsack problem (MCKP), while the coupled robust constraint is equivalent to a finite family of fixed-threshold MCKPs indexed by zero and every original option deviation. For each threshold, classical upper-hull geometry yields an LP bound and a feasible one-item rounding rule whose loss is bounded by a single adjacent hull-value jump; under bounded jumps and linear objective growth, the corresponding relative bound is $O(1/n)$. An exact-arithmetic branch-and-bound construction provides either a global optimum or a valid anytime gap over the complete threshold family, and direct evaluation of the original sorted-$\Gamma$ protection term checks every returned pricing decision. The contribution is an end-to-end, pricing-specific certifying framework that connects these ingredients, states their boundary conditions, and implements the full original breakpoint family without tolerance clustering.
Read the full abstract

Symplectic Geometry

Birkhoff normal forms, Dirac brackets and symplectic reduction

Dirac brackets are widely used to study constrained Hamiltonian dynamics. In this paper we develop a Dirac-bracket approach to normal forms on momentum levels and relate it to symplectic reduction in the cases where reduction yields a (stratified) symplectic quotient. We consider a proper Hamiltonian $G$-action on a symplectic manifold $(M,\omega)$ with an equivariant momentum map $J$. We fix $\mu \in \mathfrak g^*$and work on $J^{-1}(\mu)$. For $G$-invariant Hamiltonians whose induced vector field on $J^{-1}(\mu)$ is tangent to a local $G_\mu$-slice, we show that the induced evolution on $J^{-1}(\mu)$ coincides with that defined by the Dirac bracket on a local second-class slice, and descends to the corresponding symplectic stratum of $J^{-1}(\mu)/G_\mu$. As a main application we study Birkhoff normal forms near a relative equilibrium. When the quadratic part of a symmetric Hamiltonian is tangent to a local $G_\mu$-slice, a Birkhoff normal form can be constructed entirely on the manifold $J^{-1}(\mu)$, and it descends to a Birkhoff normal form for the reduced dynamics on the corresponding stratum, even when the reduced space is singular. We show that for a class of simple mechanical systems this condition holds automatically at a relative equilibrium. We illustrate the method on the double spherical pendulum. Finally, we relate our results to Moser's constrained dynamics by identifying Moser's constrained vector field with the Dirac Hamiltonian vector field. We show that, if the reduced Hamiltonian is near-integrable on a stratum, then its pullback to the symplectic slice is near-integrable with respect to the Dirac bracket, and vice versa. In particular, this provides a practical route to KAM-type results for the constrained dynamics.
Read the full abstract

Combinatorics

Constructing orientable and negative orientable sequences with asymptotically optimal period

Orientable sequences, periodic sequences in which any $n$-tuple appears at most once in either direction, were introduced in the early 1990s for use in certain position location applications; constructions and upper bounds on the period for the binary case were published by Dai et al. More recent work has focussed on $k$-ary sequences for arbitrary $k>2$; one method of construction involves negative orientable sequences, in which an $n$-tuple appears at most once in either the sequence or the negative of its reverse. In this paper we show how additional $n$-tuples can be added to one previously described approach for generating negative orientable sequences, resulting in new sequences with asymptotically optimal period. These sequences can in turn be used to generate orientable sequences, again with asymptotically optimal period.
Read the full abstract

Algebraic Geometry

The Geometry of Polycons and a Counterexample to Wachspress' Conjecture

Polycons, initially introduced by Wachspress in 1975 as a tool in finite element methods, are generalizations of polygons in that they allow conic boundary components. We are interested in the adjoint curve of a given polycon, i.e. the unique curve of minimal degree vanishing in the so-called residual arrangement. It was conjectured by Wachspress that under some regularity assumptions this curve does not vanish in the interior of its defining polycon. However, until recently the only class of polycons for which this was proven were convex polygons. We present a polycon bounded by three conics that constitutes a counterexample to Wachspress' conjecture. The origin of this counterexample reveals some beautiful geometry of polycons. Replacing one degree two boundary component of a polycon with a line produces a new polycon. We show that the adjoint of the latter is a contact curve to the adjoint of the former. This naturally leads to the consideration of symmetric linear determinantal representations of adjoints, which lets us explicitly describe the fibers of the adjoint map in the case of polycons bounded by three conics. As a corollary we prove that generically the adjoint of a polycon bounded by three conics is smooth.
Read the full abstract

Probability · Cross-listed from stat.ML

A Theoretical Comparison of No-U-Turn Sampler Variants: Necessary and Sufficient Convergence Conditions and Mixing Time Analysis under Gaussian Targets

The No-U-Turn Sampler (NUTS) is the computational workhorse of modern Bayesian software libraries, yet its qualitative and quantitative convergence guarantees were established only recently. A significant gap remains in the theoretical comparison of its two main variants: NUTS-mul and NUTS-BPS, which use multinomial sampling and biased progressive sampling, respectively, for index selection. In this paper, we address this gap in three contributions. First, we derive the first necessary conditions for geometric ergodicity for both variants. Second, we establish the first sufficient conditions for geometric ergodicity and ergodicity for NUTS-mul. Third, we obtain the first mixing time result for NUTS-BPS on a standard Gaussian distribution. Our results show that NUTS-mul and NUTS-BPS exhibit nearly identical qualitative behavior, with geometric ergodicity depending on the tail properties of the target distribution. However, they differ quantitatively in their convergence rates. More precisely, when initialized in the typical set of the canonical Gaussian measure, the mixing times of both NUTS-mul and NUTS-BPS scale as $O(d^{1/4})$ up to logarithmic factors, where $d$ denotes the dimension. Nevertheless, the associated constants are strictly smaller for NUTS-BPS.
Read the full abstract

All authors Samuel Gruffaz, Kyurae Kim, Fares Guehtar, Hadrien Duval-decaix, Pacôme Trautmann