Information Theory
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Tuesday 5 May
We study a Pareto-type notion of finite-block optimality for injective source codes, where two codes are compared through the full sequence of expected block lengths. As a concrete and fully analyzable test case, we revisit the four-symbol constrained Markov source introduced by Dalai and Leonardi in their "meaningful example” on constrained-source decodability. For each admissible nonempty string $u=x_1^m \in \mathscr{A} \subset \mathscr{X}^+$, let $$ K(u):=-\log_2 \mathbb{P}(X_1^m=u) $$ denote its information cost. We construct a canonical injective binary mapping $C:\mathscr{A} \to \{0,1\}^+$ by ordering admissible strings by increasing $K(u)$, then by length and lexicographic order, and assigning binary strings in shortlex order. For the length-$n$ block $X_1^n$ we prove $$ \mathbb{E}[|C(X_1)|]=\tfrac32, \qquad \mathbb{E}[|C(X_1^n)|]<\tfrac32\,n\quad (n\ge 2). $$ Moreover, for every fixed $$ 0<c<\frac{\sqrt2}{18\sqrt\pi} $$ we have $$ \mathbb{E}[|C(X_1^n)|]\le \tfrac32\,n-\frac{c}{\sqrt n} $$ for all sufficiently large $n$. Thus, for this source, the reversible Dalai-Leonardi code is not Pareto-optimal with respect to finite-block average length. The proof is based on an exact enumeration of admissible strings by information cost and on a shortlex gap identity implying that each cost class splits evenly between lengths $K(u)-1$ and $K(u)$. The example is simple, but it already exhibits the kind of finite-block Pareto comparison that seems natural for injective source coding under source constraints.
Rings and Algebras
Solving one-sided linear systems over symmetrized and supertropical semiring
One-sided linear systems of the form “$Ax=b$” are well-known and extensively studied over the tropical (max-plus) semiring and wide classes of related idempotent semirings. The usual approach is to first find the greatest solution to such system in polynomial time and then to solve a much harder problem of finding all minimal solutions. We develop an extension of this approach to the same systems over two well-known extensions of the tropical semiring: symmetrized and supertropical, and discuss the implications of our findings for the tropical cryptography.
Read the full abstract
Numerical Analysis
Fourier Residual Networks Achieve Spectral Accuracy for Discontinuous Functions
We present a constructive approximation framework for analyzing the expressive power of Fourier residual networks in approximating a broad class of one-dimensional functions. Our study covers both piecewise continuous functions – including those with jump discontinuities in the function and its derivatives – and fully smooth functions. We show that Fourier residual networks achieve spectral convergence without requiring periodicity or continuity, thereby overcoming key limitations of classical linear Fourier approximation and nonlinear methods, without being restricted to Barron-type function spaces. Our approach builds on classical techniques from approximation theory, including fixed-point iteration and Hermite interpolation by trigonometric polynomials. We support our theoretical results with numerical experiments based on both the constructed approximations and a randomized algorithm developed in our earlier work.
Read the full abstract
Numerical Analysis
Random test functions, $H^{-1}$ norm equivalence, and stochastic variational physics-informed neural networks
The dual norm characterisation of weak solutions of second-order linear elliptic partial differential equations is mathematically natural but computationally intractable: evaluating the $H^{-1}$ norm of the residual requires a supremum over an infinite-dimensional test space. We prove that the $H^{-1}$ norm of any functional is equivalent to its expected squared evaluation against a random test function whose probability distribution depends only on the domain. Crucially, realisations of this random test function have negative Sobolev regularity for $d \geq 2$, yet this roughness is not an obstacle: averaging over the distribution exactly recovers the correct weak topology, independently of the differential operator, and no supremum evaluation is necessary. This equivalence introduces the notion of stochastically weak solutions, which coincide with classical weak solutions, and motivates stochastic variational physics-informed neural networks (SV-PINNs): neural networks trained by minimising an empirical approximation of the stochastic norm of the PDE residual. Although instantiated here with neural networks, the underlying principle is independent of the trial space and suggests a broader paradigm for numerical methods based on stochastic rather than deterministic test spaces. The framework extends naturally to higher-order elliptic, parabolic and hyperbolic equations and to abstract operator equations on Hilbert spaces. As a proof of concept, we present numerical experiments on eight challenging second-order linear elliptic problems spanning high-frequency and multi-scale solutions, indefinite operators, variable coefficients, and non-standard domains, in which SV-PINNs consistently and significantly outperform standard PINNs, recovering solutions to within one percent relative error in hundreds of L-BFGS steps.
Read the full abstract
Numerical Analysis · Cross-listed from cs.CE
Device-Induced Thrombus Formation in Cerebral Aneurysms: Linking Patient-Specific Clot Modeling and Functional Occlusion to Virtual Angiographic Assessment
Endovascular treatment of cerebral aneurysms aims to achieve functional occlusion and isolation of the aneurysm sac from bloodflow. In clinical practice, treatment success is assessed primarily through digital subtraction angiography (DSA), which visualizes contrast-agent inflow and washout but does not directly resolve thrombus formation driving early occlusion. We present a computational framework that couples acute fibrin thrombus formation with virtual angiography, enabling early thrombus growth to be interpreted through clinically familiar DSA-like imaging. Three common treatment strategies: endovascular coiling, flow diversion, and stent-assisted coiling, are modeled under pulsatile hemodynamics and linked to simulated contrast transport. Across three representative aneurysm morphologies, the simulations demonstrate that while devices reduce inflow, residual contrast access and trapping may persist, with early thrombus formation contributing substantially to perfusion suppression and altered washout patterns. These effects are clearly reflected in the virtual angiographic imaging. The importance of vortical structures in device-induced thrombosis is highligthed in one of the cases. By seeking to align modelling and simulation tools with clinically-relevant metrics, with a particular focus on occlusion outcome, this work presents a good starting point for bridging the gap between these two paradigms.
Read the full abstract
Differential Geometry
Existence and stability of weak critical points of $r$-energy functionals
The main aim of this paper is to prove the existence of certain proper weakly $r$-harmonic ($ES-r$-harmonic) maps. We construct critical points which belong to a family of rotationally symmetric maps $\varphi_a : B^n \to \mathbb{S}^n$, where $B^n$ and $\mathbb{S}^n$ denote the Euclidean $n$-dimensional unit ball and sphere respectively. We find that the existence of solutions within this family is restricted to specific dimensions $n$. Next, we prove that our critical points are unstable. In the course of this analysis we point out some specific differences between the $r$-harmonic and the $ES-r$-harmonic cases when $r \geq 4$. Next, we analyse two variants of the problem. First, we replace the target manifold $\mathbb{S}^n$ with a rotationally symmetric ellipsoid $E^n(b)$ and establish the existence of proper weakly biharmonic maps for all $n \geq 5$, as well as proper weakly triharmonic maps for all $n \geq 7$. Finally, we study a similar problem replacing the domain $B^n$ with a suitable warped product manifold.
Read the full abstract
Probability
Kolmogorov-Smirnov distance and discrepancies versus Wasserstein distances
We establish inequalities that compare the p-Wasserstein distance to distances which are built as suprema of box measures. More precisely, when the measures are supported on $[0,1]^d$, we obtain sharp upper-bounds of the $p$-Wasserstein distance by (powers of) the (uniform) discrepancy. As an application, we retrieve the Pro\”inov Theorem. When the two distributions are supported {by the whole} $R^d$, {their} $p$-Wasserstein distance is upper bounded by the product of a (power of) their Kolmogorov-Smirnov (KS) distance with the sum of their $p$-moments. Reverse inequalities are established when one of the two distributions has a density, depending on its ${\cal L}^s$-integrability with respect to the Lebesgue measure for some $s>1$.
Read the full abstract
Logic
Free sets, thin sets and rainbows for barriers
We formulate and prove the generalizations of Friedman's free set and thin set theorems and of the rainbow Ramsey theorem to colorings of barriers. We analyze the strength of these theorems from the point of view of computability theory proving some upper and lower bounds on the complexity of solutions for computable instances and some uniform computable reductions. We obtain as corollaries some proof-theoretical results on the logical strength of the theorems, in the spirit of reverse mathematics.
Read the full abstract
Algebraic Geometry
Twisted cohomology on algebraic and analytic varieties
In this article, we study and review some aspects of twisted cohomologies on algebraic and analytic varieties. We compared such cohomologies in both the algebraic and analytic categories and defined two types of twisting parameters in the analytic setting, and also discussed algebraic twisting. Several computations are given. We have also reviewed some isomorphisms of such cohomologies for cohomologous twisting parameters. We discussed constraints on the algebraic varieties that should be assumed so that the algebraic de Rham cohomologies on the variety can be twisted.
Read the full abstract
Symplectic Geometry
Open-closed Deligne-Mumford field theories: construction
Open-closed Deligne–Mumford field theories are chain-level field theories based on moduli spaces of stable curves with boundary. We associate to a relatively spin embedded Lagrangian $L \subset (X,\omega)$ such an open-closed DMFT. It extends the Fukaya $A_\infty$ algebra to curves of arbitrarily high genus and with arbitrarily many boundary components and is unique up to homotopy. This is the first step in proving Kontsevich's conjecture that the Fukaya category determines the Gromov–Witten invariants of $X$, following a strategy delineated by Costello.
Read the full abstract
Optimization and Control
Parametrizing Convex Sets Using Sublinear Neural Networks
We propose a neural parameterization of convex sets by learning sublinear (positively homogeneous and convex) functions. Our networks implicitly represent both the support and gauge functions of a convex body. We prove a universal approximation theorem for convex sets under this parametrization. Empirically, we demonstrate the method on shape optimization and inverse design tasks, achieving accurate reconstruction of target shapes.
Read the full abstract
Number Theory
Infinitesimal characters for the completed cohomology of $\mathrm{GL}_n$ over CM fields
Let $p$ be a prime, and let $F$ be a CM field containing an imaginary quadratic field in which $p$ splits. We show that the locally analytic vectors of Hecke eigenspaces in the ($p$-adic) completed cohomology of $\mathrm{GL}_n/F$, localized at a non-Eisenstein decomposed generic maximal ideal, admit infinitesimal characters determined by the Sen operators of the corresponding Galois representations, thus confirming a conjecture of Dospinescu-Paškūnas-Schraen in this case.
Read the full abstract
History and Overview of Mathematics
Spherical trigonometry before the modern era:The treatise of Nasir al-Din al-Tusi
This is an overview of Nasir al-Din al-Tusi's Treatise of the quadrilateral, an invaluable 13th century document on spherical geometry which was translated into French in 1891. The title we are using here is the one given by the translator (Alexandre Carathéodory). A title which is closer to the original Arabic is ”Disclosing the secrets of the secant figure.” The term ”secant figure”, to which the title refers, is the so-called ”complete (spherical) quadrilateral”, that is, the figure that underlies what we call today Menelaus' Theorem. This theorem gives a formula that was extensively used by astronomers in their computations and the establishment of their tables since the first century AD, notably by Ptolemy, in the absence of the spherical trigonometric formulae that were discovered later. Nasir's treatise contains much more than Menelaus' theorem, since we find there a complete system of spherical trigonometric formulae, with complete proofs. The treatise includes at the same time invaluable historical information on the discovery of the trigonometric formulae by the Arab mathematicians of the Middle-Ages and the transformation of the field of spherical trigonometry that this discovery led to. The final version of this paper will appear in the book Spherical geometry in the eighteenth century, I: Euler, Lagrange and Lambert, edited by Renzo Caddeo and Athanase Papadopoulos, Springer, 2026.
Read the full abstract
Representation Theory
Growth rates of indecomposable summands in tensor powers of representations of quivers
Tensor products of quiver representations have been extensively studied; typical examples include the pointwise tensor product and the tensor product induced by the coalgebra structure of path algebras. In this paper, we investigate the growth rates of the number of indecomposable direct summands in tensor powers of quiver representations with respect to these two typical tensor products.
Read the full abstract
Information Theory · Cross-listed from cs.LG
A Hierarchical Sampling Framework for bounding the Generalization Error of Federated Learning
We study expected generalization bounds for the Hierarchical Federated Learning (HFL) setup using Wasserstein distance. We introduce a generalized framework in which data is sampled hierarchically, and we model it with a multi-layered tree structure that induces dependencies among the clients' datasets. We derive generalization bounds in terms of Wasserstein distance under the Lipschitz assumption on the loss function, by applying a supersample construction that allows us to measure the sensitivity of the algorithm to the change of a single node in the sampling tree. By leveraging the FL structure, we recover and strictly imply existing state-of-the-art conditional mutual information (CMI) bounds in the case of bounded losses. We also show that our bound can be applied together with Differential Privacy assumptions, to recover generalization bounds based on algorithmic privacy. To assess the tightness of our bounds, we study the Gaussian Location Model (GLM) and show that we recover the actual asymptotic rate of the generalization error.
Read the full abstract
Algebraic Topology
Weighted algebraic topology, II (Real valued metrics)
Extending the `metric spaces' of Lawvere, we study `real metrics', with values in the extended real line. Formally, this ordered set is a symmetric monoidal closed category, and our structures are enriched categories on the latter. Concretely, the present goal is measuring `profits' and `losses' of a process, in any sense - possibly related to energy, or a variable in any science. In particular, linear real metrics derive from a potential function. This article is Part II in a series devoted to `weighted algebraic topology' - an enriched version of directed algebraic topology, where paths are measured. Part III will introduce a finer framework, more adequate to `quotient spaces' (as the spheres) and better related to topology.
Read the full abstract
Optimization and Control
Quantitative Convergence of Proximal Splitting Iterations in Uniformly Convex Metric Spaces
We provide sufficient conditions for quantitative convergence of the iterates of proximal splitting algorithms for minimizing a sum of functions on a metric space. The theory does not assume that the functions have common minima, nor does it require vanishing proximal parameters or step sizes. Our results are stated for general $p$-uniformly convex spaces with curvature bounded above, and a corollary specializes the main theorem to Hadamard spaces, where many assumptions for the more general setting can be dropped. The theory is demonstrated with computation of Fréchet means in the space of SPD matrices with the affine invariant metric (a Hadamard space) and the sphere with the usual geodesic metric (a CAT($\kappa$) metric space).
Read the full abstract
Combinatorics
Signed sumsets and restricted signed sumsets in groups and fields
Let $A = \{a_1, \ldots, a_k\}$ be a nonempty finite subset of an additive abelian group $G$. For a nonnegative integer $h$, the \emph{$h$-fold signed sumset} of $A$, denoted by $h_{\pm} A$, is defined by $$ h_{\pm} A = \Biggl\{\sum_{i = 1}^{k} \lambda_i a_i : \lambda_i \in \{-h, \ldots, h\}, \ \sum_{i = 1}^{k} |\lambda_i| = h \Biggr\}, $$ and the \emph{restricted $h$-fold signed sumset}, denoted by $h_{\pm}^\wedge A$, is defined by $$ h_{\pm}^\wedge A = \Biggl\{\sum_{i = 1}^{k} \lambda_i a_i : \lambda_i \in \{-1, 0, 1\}, \ \sum_{i = 1}^{k} |\lambda_i| = h \Biggr\}. $$ We study direct and inverse problems for these signed sumsets, namely determining extremal bounds for their sizes and characterizing the structure of sets $A$ attaining these bounds. While such problems have been extensively studied and resolved in the additive group of integers, comparatively little is known in general abelian groups, especially for restricted signed sumsets. In this paper, we investigate the signed sumset $h_{\pm} A$ in arbitrary (not necessarily finite) abelian groups under the condition $A \cap (-A) \neq \varnothing$. We further analyze both $h_{\pm} A$ and $h_{\pm}^\wedge A$ when $A \cap (-A)$ has a prescribed size. These results are extended to generalized signed sumsets $H_{\pm} A = \bigcup_{h \in H} h_{\pm} A$, where $H$ is a finite set of nonnegative integers, with particular attention to $[0,h]_{\pm} A$. Furthermore, using the polynomial method, we establish nontrivial lower bounds for $|h_{\pm}^\wedge A|$ in arbitrary fields. In addition, for $h = 2, 3, 4$, we derive lower bounds for $|h_{\pm} A|$ in arbitrary fields under the condition $A \cap (-A) = \varnothing$.
Read the full abstract
Analysis of PDEs
Stability of de Sitter Space and Expansion at the Conformal Boundary
Using an approach similar to arXiv:2409.15460, we give a new proof of the nonlinear stability of de Sitter space as a solution to the Einstein vacuum equations with positive cosmological constant in $n+1$ dimensions, with $n\geq3$. Using the gauge freedom of the equations, we are able to prove a precise expansion of the perturbed spacetime at the conformal boundary. In $n=$ odd spatial dimensions, the conformally rescaled metric is smooth up to the future conformal boundary and in $n=$ even spatial dimensions it is smooth if and only if the obstruction tensor of the boundary metric vanishes; if not, then the conformally rescaled metric is log smooth at the boundary. These results also hold for asymptotically de Sitter spaces. Using the results of Fefferman and Graham (1985, Conformal invariants), arXiv:0710.0919, arXiv:1705.09674 and arXiv:2311.02739, the structure of our expansion allows us to establish a 1-1 correspondence between solutions to the Einstein vacuum equations close to de Sitter space and scattering data prescribed on the conformal boundary in general dimension.
Read the full abstract
Combinatorics
Helmholzian spectra of graphs: basic properties
The Helmholtzian matrix of a graph $G=(V(G),E(G))$ is a graph-theoretic analogue of the vector Laplacian (or Helmholtz operator) [S. Li, L. Lu, J.F. Wang, A graph discretization of vector Laplacian, 379 (2026) 446–460]. Motivated by the applications of graph Helmholtzian in simplicial networks, we will investiagte its basic spectral properties. As the first graph matrix indexed by edge set, we find that Helmholtzian matrix is positive semi-definite and its non-negativity correlates with the odd cycles in $G$ and the orientation on $E(G)$, while its irreducibility relates to the signed graphs with loops. We show that the eigenvalues of Helmholtzian matrix are independent of the orientation and further investigate the eigenvalue interlacing under edge additions. One of striking findings is that the non-zero eigenvalues of the Laplacian matrix are those of Helmholtzian matrix of every graph. All these discoveries reveal that the Helmholtzian spectrum of $G$ balances and bridges the oriented graphs, weighted graphs and signed graphs as well as their adjacency or Laplacian spectra.
Read the full abstract
Combinatorics
Polynomials from tilings of rectangles
We study tilings of rectangular boards using unit squares together with a single type of big tile shaped as a Ferrers diagram. We derive generating functions for these tilings, prove real-rootedness and interlacing properties of associated independence polynomials, and establish connections with several sequences in the OEIS. Our results touch on tilings involving L-shaped polyominoes, fault-free tilings, and cylindric variants. We prove that tiling polynomials for two-column Ferrers shapes are real-rooted and form interlacing sequences.
Read the full abstract
Combinatorics
Criteria on forbidden subgraphs in the complements for positive Lin–Lu–Yau curvature
We investigate forbidden subgraph conditions in the complement of a graph that guarantee positive Lin–Lu–Yau curvature. In particular, we prove that every graph whose complement contains no $4$-cycles has positive Lin–Lu–Yau curvature, with the only exception of the $4$-vertex path. We further prove that, for any integer $t\ge2$, every graph on at least $\max\{t^2-2t+2, 8t\}$ vertices whose complement contains no $K_{2,t}$ has positive curvature. In addition, this lower bound on the number of vertices is optimal for $t\geq 10$. Finally, we construct examples showing that, in general, the forbidden subgraphs in these results cannot be replaced by cycles of length other than $4$ or by complete bipartite graphs $K_{s,t}$ with $s> 2$ and $t> 2$.
Read the full abstract
Mathematical Physics · Cross-listed from physics.optics
Anisotropy in Fourier space optical memory effect correlations
We investigate anisotropy in Fourier-domain speckle correlations associated with the optical memory effect in disordered scattering media. Within a single scattering framework, we show that while the conventional memory effect constrains transverse wavevector shifts, the correlation strength also depends non-trivially on differences in the axial wavevector components. Our theory is supported by numerical simulations of a three-dimensional, single scattering medium, which show excellent agreement with theory. We extend the analysis to pseudo-correlations, demonstrating that analogous anisotropic behavior arises in the conjugate memory effect. Our results highlight the often neglected role of axial disorder in scattered field correlations.
Read the full abstract
Classical Analysis and ODEs
A novel asymptotic technique for integrals involving the Hankel contour and the Bleistein asymptotic formula
Several important functions, including the gamma function, as well as several infinite sums, admit integral representations involving the Hankel contour. In addition, the large $t$ asymptotic analysis of several recently derived identities satisfied by the Riemann zeta function requires computing the asymptotic form of certain integrals which also involve the Hankel contour; these integrals depend on a real parameter, $\alpha$. A rigorous asymptotic technique is presented here for computing such integrals to all orders. For certain values of $\alpha$, the relevant formula, in addition to an asymptotic series of explicit terms, also contains a specific integral. It is shown that, remarkably, the leading order of this integral can be written in the form of the leading order of the Bleistein integral. The latter integral arises in the implementation of the classical steepest descent method in the case that the stationary point coincides with one of the boundary points of the integral under consideration.
Read the full abstract
Commutative Algebra · Cross-listed from cs.SC
Asymptotic properties of random monomial ideals
This paper focuses on asymptotic properties of random monomial ideals through a statistical viewpoint. It extends the study of redundancy in monomial ideals by analyzing the poset density of the LCM-lattice. We explore how this density behaves across random algebraic models and structured networks. Experimental data reveal that the LCM-lattice exhibits sharp threshold behavior rather than changing smoothly. We observe a strong negative correlation between the number of generators and LCM-lattice density, abruptly separating three distinct regimes: a low-density Taylor-like regime, a high-density redundant regime, and a narrow transition window. We show that increasing the generator degree causes this density drop to occur at lower probability thresholds. We conclude by conjecturing that for equigenerated squarefree ideals, the LCM-lattice density undergoes a sharp phase transition, analogous to the emergence of giant components in hypergraphs. This suggests that the classical, ideal-by-ideal role of the LCM-lattice as a combinatorial invariant also admits a statistical/asymptotic counterpart: in natural random families, redundancy and resolution-complexity indicators concentrate into distinct typical regimes separated by a narrow transition window.
Read the full abstract
Representation Theory
Revising Auslander-Gruson-Jensen duality
For a ring $A$ there is a well-known duality between definable subcategories of right $A$-modules and definable subcategories of left $A$ modules. This is a consequence of Auslander-Gruson-Jensen duality $\rm mod\text{-}(mod\text{-}A)\rightarrow mod\text{-}(mod\text{-}A^{op})$. The existence of this duality arises from the fact that $\rm mod\text{-}(mod\text{-}A)$ is the free abelian category over the pre-additive category $A$ with a single object. In this note, first, we give a simple description of the free abelian category. This description clarifies Auslender-Gruson-Jensen duality and also the duality between definable subcategories of right $A$-modules and those of left $A$-modules.
Read the full abstract
Algebraic Topology
Higher categories of bordisms with geometric structures
We introduce a system of axioms that uniquely defines an (infinity,d)-category of bordisms equipped with geometric data. The underlying manifolds of these bordisms may be smooth, complex, super, or formal smooth manifolds, as well as any class of manifolds satisfying conditions specified in this paper. We develop a general notion of a field on a manifold, encompassing structures such as Riemannian metrics, principal bundles with connection, conformal structures, and traditional tangential structures. Using this framework, we construct a symmetric monoidal (infinity,d)-category of bordisms with prescribed underlying manifolds and fields, and prove that it satisfies our axioms.
Read the full abstract
Group Theory
On the base size of a finite group on its action on the lattice of subgroups
Given a finite group $R$, we investigate the base size of the action of the automorphism group of $R$ on the lattice of subgroups of $R$. Our main result shows that this base size is $1$ if and only if $R$ is cyclic. Our motivation arises from a conjecture of Babai on the problem of representing groups as automorphism groups of lattices with a bounded number of orbits.
Read the full abstract
Optimization and Control
Promoting Fair Online Resource Allocation with Indivisible Units
Allocating scarce, indivisible resources to diverse groups under uncertainty is a central challenge in operations research, where efficiency-focused methods often underserve marginalized populations. We study the Fair Online Resource Allocation with Indivisible Units (FORA-IU) problem, in which an unpredictable sequence of demands must be served from a strictly fixed inventory, and ask what fairness guarantees are achievable under different distributional and structural assumptions. We adopt a fairness criterion based on the expected filling ratio (FE-FR-beta), which balances each group's expected allocation against its expected demand and priority weight. We design online policies that calibrate acceptance probabilities to the remaining budget, analyze both arbitrary time-varying and stationary arrivals, introduce the Random Cyclic Blocks (RCB) algorithm tailored to the stationary case, and study the effect of restricting policies to all-or-nothing allocations. For arbitrary time-varying arrivals, our policy achieves the optimal universal fairness guarantee of 1/(1+R_beta), where R_beta denotes the priority-weighted system load. For time-invariant arrivals, RCB achieves the exact finite-horizon guarantee [1-(1-R_beta/T)^T]/R_beta, which is at least (1-e^{-R_beta})/R_beta and is also tight. We further show that all-or-nothing allocation policies cannot match these guarantees. These findings demonstrate that distributional stationarity strictly improves the fairness frontier, and that partial fulfillment is a necessary condition for attaining optimal fairness in online indivisible resource allocation.
Read the full abstract
Number Theory
Behaviour of Certain Crystalline Representations modulo $2$
We compute the explicit form of the semisimplified reduction modulo $2$ of the $2$-adic crystalline Galois representations $V_{k,a_2}$ at small slopes in $(0,1]$, using the compatibility of $2$-adic and mod-$2$ local Langlands correspondence. We find parameters $\alpha'(k,a_{2})$ and $\alpha(k,a_{2})$, which play a crucial role in determining the reduction of $V_{k,a_{2}}$ for slopes in the range $(0,1)$ and slope $1$ respectively.