Information Theory · Cross-listed from quant-ph
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Thursday 14 May
The performance of quantum resource manipulation protocols, including key examples such as distillation of quantum entanglement, is measured in terms of the rate at which desired target states can be produced from a given noisy state. However, to achieve optimal rates, known protocols require precise tailoring to the quantum state in question, demanding a perfect knowledge of the input and allowing no errors in its preparation. Here we show that distillation of quantum resources in the framework of resource non-generating operations can be performed universally: optimal rates of distillation can be achieved with no knowledge of the input state whatsoever, certifying the robustness of quantum resource distillation. The findings apply in particular to the purification of quantum entanglement under non-entangling maps, where the optimal rates are governed by the regularised relative entropy of entanglement. Our result relies on an extension of the generalised quantum Stein's lemma in quantum hypothesis testing to a composite setting where the null hypothesis is no longer a fixed quantum state, but is rather composed of i.i.d. copies of an unknown state. The solution of this asymptotic problem is made possible through new developments in one-shot quantum information and a refinement of the blurring technique from [Lami, arXiv:2408.06410].
Logic
Modal group theory: homomorphisms
I investigate modal group theory for arbitrary homomorphisms. Possibility is interpreted by the existence of a group homomorphism out of the given group, so the semantics is governed by the possibility of collapse: elements may be identified, parameters may be killed, and new relations may hold in the target. I show that the modal language nevertheless expresses cyclic subgroup membership, subgroup generation by a fixed finite tuple, cyclicity, finite generation by a fixed number of elements, and torsion. I use these definability results to interpret arithmetic, and prove that, as sets of Goedel numbers, the homomorphic modal theory of finitely presented groups is computably isomorphic to true arithmetic. I also analyze propositional modal validities: sentential validities are exactly S5, the trivial group has exact parameter-validities S5, and uniformly prime-indivisible groups have exact parameter-validities S4.2.
Read the full abstract
Probability · Cross-listed from cs.CY
Due Process on Hold: A Queueing Framework for Improving Access in SNAP
The U.S. social safety net delivers essential services at mass scale, but access burdens persist, as congested contact or call centers serve as a primary mode of application completion and assistance. In Holmes v. Knodell, Missouri's SNAP call centers were so congested that nearly half of all application denials were procedural, caused by applicants' inability to complete required interviews, rather than underlying ineligibility. The judge ruled these system failures led to a violation of procedural due process. We propose a performance evaluation framework based on queueing models from operations research and management to assess and improve access in such systems. Operational access failures of call centers are distinct from prior automation failures in benefits provision. Emergent arbitrariness arises from interactions between system dynamics and access demand, rather than from an explicit algorithmic rule, making diagnosis and repair inherently system-level. We develop a queueing model that incorporates phenomena that distinguish social services from standard service domains, redials and abandonment, through which backlogs generate endogenous congestion. Standard queueing guidance from Erlang-A that does not address endogenous congestion fundamentally understaffs, which could lead to persistent shortfalls in practice. Using a fluid approximation, we derive steady-state performance metrics to analytically characterize the impacts of bundled staffing and service delivery changes. We fit model parameters to call-center data disclosed in court documents. Our queueing model can support ex-ante evaluation and design of access systems, inform policy levers for improving access, and provide evidence about whether applicants are afforded a meaningful opportunity to be served at scale.
Read the full abstract
Dynamical Systems · Cross-listed from eess.SY
On the Nonexistence of Continuous Immersions for Discrete-time Systems
Understanding when linear immersions of nonlinear dynamical systems exist is important since such immersions allow us to leverage the rich tools of linear system theory to analyze nonlinear dynamics. Recently, Liu et al. (2023) showed that continuous-time dynamical systems that admit countably many but more than one omega-limit sets cannot be immersed into finite dimensional linear systems with a one-to-one and continuous mapping. In this paper, we extend these results to discrete-time dynamics and show that similar obstructions exist also in discrete time. We further consider a generalization involving alpha-limit sets. Several examples are provided to demonstrate the results.
Read the full abstract
Logic
Avoiding logical strength in real analysis
In reverse mathematics, real numbers are traditionally represented by Cauchy sequences with a given rate of convergence. We work without rates and speak of slow Cauchy sequences. It turns out that almost all one-dimensional real analysis from the reverse mathematics book by Simpson can then be developed in theories that are conservative over $\mathsf{RCA}_0$. Specifically, we obtain clusters of equivalences with the infinite pigeonhole principle and the strong cohesive principle. The second cluster includes results like the Bolzano-Weierstrass and Arzelà-Ascoli theorems, which are traditionally associated with the stronger axiom of arithmetical comprehension, but also the Heine-Borel theorem, which is normally separated from these principles. This suggests two things: In elementary analysis, one can avoid logical strength to an extent that the traditional picture seems to forbid. And the division of the so-called reverse mathematics zoo into analytical and combinatorial principles may be less rigid than previously assumed.
Read the full abstract
Analysis of PDEs
Asymptotically Self-Similar Blowup for 3D Incompressible Euler with $C^{1, 1/3-}$ Velocity I: $C^{\infty}$ 1D Limiting Profiles
We consider a one-parameter family of 1D models for the 3D axisymmetric incompressible Euler equation with $C^{\alpha}$ vorticity and without swirl near the symmetry axis. For $\alpha = \frac13$, we impose a crucial normalization and construct a $C^{\infty}$ self-similar blowup profile with unbounded 1D stream function and infinite spatial blowup rate, using a fixed-point argument around a numerically constructed approximate profile. For $\alpha < \frac13$ sufficiently close to $\frac13$, we perturb the $\frac13$-profile and analytically construct exact smooth 1D profiles with bounded stream function and finite spatial blowup rate. In the companion work~\cite{chen2026eulerII}, for any $\alpha \in (0,\frac13)$, we lift these 1D blowup profiles to construct exact $C^{1,\alpha}$ self-similar blowup profiles for 3D Euler, and build on them to prove sharp asymptotically self-similar blowup for 3D axisymmetric Euler without swirl from $C_c^\alpha$ initial vorticity and $C^{1,\alpha} \cap L^2$ initial velocity.
Read the full abstract
Mathematical Physics
Noether symmetries and conservation laws of a class of time-dependent multidimensional nonlinear wave equations
Conservation laws of a class of time-dependent damped nonlinear multidimensional wave equations are derived by Noether's theorem. For arbitrary nonzero damping coefficient and nonlinear interaction term, its infinitesimal variational symmetries span a Euclidean algebra $\euclid(n)$ of space translations and rotations. They produce conservation of linear and angular momentums. For some specific forms of these two terms symmetry algebra is enlarged to a subalgebra of the conformal algebra $\conf(1,n)$ and in this case more interesting conservation laws are found.
Read the full abstract
Combinatorics
Improved Ramsey bounds for generalized Schur equations
We show that for $m, r \in \mathbb{N}$ and $N > (2m+1)^r (r!)^{1/m}$, every $r$-coloring of the integers in the interval $[N]$ contains a monochromatic solution to the equation \[ x_1 + \dots + \dots x_{m+1} = y_1 + \dots + y_m. \] This generalizes and improves recent results of Koścuiszko. We also show that if $N \geq 2^{r}$, then every $r$-coloring of the integers in $[N]$ must always determine a monochromatic solution to the above equation for some $m \geq 1$. The latter estimate is optimal.
Read the full abstract
History and Overview of Mathematics · Cross-listed from cs.LO
Guises and Perspectives: An Intentional and Hyperintensional Sketch
This paper develops a formal logic for guises based on the work of Héctor-Neri Castañeda, who understood relations from an internalist viewpoint, following Leibniz. We introduce a syntax, model theory, and proof theory for an intensional logic in which guises (taken as bundles of properties equipped with intention) serve as primary semantic objects. The system integrates (i) a Leibnizian containment semantics for singular truths, (ii) an intentional operator that captures internal relations among guises, and (iii) a modal layer for possibility and necessity modeled as maximally consistent closures. We establish core metatheoretic results (e.i. soundness and canonical-model completeness sketches) and analyze hyperintensional phenomena such as substitution failure in intentional contexts, quasi-indexicality, and de se reference. We compare the framework to classical intensional semantics (Montague), property theory (Bealer), hyperintensional logics (Fine), situation semantics (Barwise and Perry), and to the Leibniz program for a calculus of concepts. The result is a selfcontained formal framework that demonstrates that relations are not external causal links but intentional internal structures encoded in the guises through which agents and objects are conceived: i.e., they are perspectives.
Read the full abstract
Combinatorics
New Bounds for Integer Flows and Verma Modules, via Denormalized Lorentzian Laurent Series
The theory of log concave polynomials has recently been developed to study objects and problems in combinatorics and other subfields in mathematics. Particular classes of log concave polynomials called Lorentzian polynomials and denormalized and dually Lorentzian polynomials have been used to prove log concavity statements for various combinatorial sequences. This includes the strongest form of Mason's log concavity conjecture on the independent sets of matroids and the log concavity of sequences of Kostka numbers. In this paper, we develop an analogous class of power series called denormalized Lorentzian (DL) Laurent series. This class is the natural generalization of DL polynomials to homogeneous power series with the benefit of capturing a number of combinatorial generating series including the Kostant partition function for integer flows of directed graphs. We then analyze specific DL Laurent series to obtain new bounds for integral flows on general directed acyclic graphs and new bounds for the dimensions of weight spaces of parabolic $\mathfrak{sl}_{n+1}(\mathbb{C})$ Verma modules.
Read the full abstract
Information Theory · Cross-listed from eess.SP
Deep Mixture of Experts Network for Resource Optimization in Aerial-Terrestrial CF-mMIMO Systems under URLLC
As a critical component of sixth-generation (6G) wireless networks, ultra-reliable and low-latency communication (URLLC) is expected to support real-time and reliable information exchange in low-altitude environments. However, achieving URLLC often incurs significant resource overhead, including increased bandwidth consumption, higher transmit power, and denser access point (AP) deployment, which pose significant challenges to both spectral efficiency (SE) and energy efficiency (EE). Besides, existing iterative optimization algorithms are computationally intensive and struggle to meet the latency requirements of URLLC. To address these challenges, we propose a hybrid aerial-terrestrial cell-free massive MIMO (CF-mMIMO) network to support diverse services, along with a channel prediction network and a deep mixture of experts (MoE) network for uplink optimization. First, we design a channel prediction network (CP-Net) to mitigate channel aging caused by high-mobility user equipment (UE). CP-Net employs three Transformer-based sub-networks for aged channel state information (CSI) prediction, while a channel quality-aware loss function is introduced to improve the prediction accuracy of weak links. Based on the predicted CSI, we develop a deep MoE network (MoE-Net) for power allocation comprising three expert models targeting different objectives. Then, we introduce a weighted gating network (WT-Net) to learn an efficient adaptive combination of expert outputs. The proposed framework better captures heterogeneous UE requirements and improves communication performance under URLLC constraints. Numerical results demonstrate the effectiveness of the proposed method.
Read the full abstract
Analysis of PDEs
Asymptotically Self-Similar Blowup for 3D Incompressible Euler with $C^{1, 1/3-}$ Velocity II: 3D Profiles, Blowup, and Limiting behavior
For any $\alpha \in (0,1/3)$, we construct exact $C^{\alpha}$ self-similar blowup profiles for the vorticity of the 3D incompressible Euler equation without swirl, and build on them to prove asymptotically self-similar blowup from $C_c^\alpha$ initial vorticity and $C^{1,\alpha}\cap L^2$ initial velocity. Moreover, we provide a complete characterization of the limiting behavior of the $C^{\alpha}$ vorticity profiles and the associated blowup solutions as $\alpha\to(1/3)^-$. Specifically, as $\alpha \to(1/3)^-$, the spatial blowup rate $\mathsf{c}_{\mathsf{x},\alpha}$ diverges to $\infty$, while the $C^{\alpha}$ vorticity profile $\Omega_{*,\alpha}^{\theta}$ asymptotically factorizes and converges strongly in a weighted $L^\infty$ norm to a nonzero constant multiple of $r^{1/3}\bar W_{1/3}(z)$, where $\bar W_{1/3}$ is a $C^\infty$ 1D blowup profile. Our construction is inspired by the Hou–Zhang blowup scenario. Using a fixed-point argument, we lift the $C^\infty$ blowup profiles for a 1D model constructed in the companion work [11] to exact 3D blowup profiles. To overcome the lack of $r$-directional decay in the approximate profile and capture the anisotropic structure, we develop a family of anisotropic weighted estimates and introduce a crucial integration-by-parts method along trajectories that exploits the equation twice. We then develop a finite codimension stability argument in a low-regularity setting to prove stability of the 3D profiles and establish asymptotically self-similar blowup. This blowup result is sharp in view of the global regularity theory for axisymmetric Euler without swirl with $ C_c^{\alpha}$ initial vorticity for all $\alpha \geq 1/3$. To the best of our knowledge, our results provide the first example in which a singularity from a 1D nonlocal fluid model is lifted to construct blowup for incompressible fluid equations in $\mathbb{R}^2$ or $\mathbb{R}^3$.
Read the full abstract
Logic · Cross-listed from cs.LO
Constructive higher sheaf models with applications to synthetic mathematics
There have recently been several developments in synthetic mathematics using extensions of dependent type theory with univalence and higher inductive types: simplicial homotopy type theory, synthetic algebraic geometry and synthetic Stone duality. We provide a foundation of higher sheaf models of type theory in a constructive metatheory and, in particular, build constructive models of these formal systems.
Read the full abstract
Combinatorics
An excluded minor theorem for the 6-wheel
For each integer $n \geq 3$, the wheel graph $W_n$ is defined as the graph obtained by connecting a single vertex to all vertices of a cycle of length $n$. In particular, $W_6$ can be uniquely obtained from the Petersen graph by contracting three edges incident to a common vertex. Gubser provided a characterization of all 3-connected planar $W_6$-minor-free graphs. In this paper, we complete the characterization of $W_6$-minor-free graphs by determining the 3-connected nonplanar cases.
Read the full abstract
Number Theory
Real geometric transcendence for the Gamma function
We show that the $x$-axis is the only real algebraic curve in $\mathbb R^2$ whose image via the Gamma function is contained in an algebraic curve. Our proof employs an elegant base-change argument due to Tamiozzo (2023) to deduce the result from the corresponding complex geometric transcendence result of Eterović, Padgett and Zhao (2025). As an application, we use the complex and real geometric transcendence results to study analogues of the Manin–Mumford conjecture for the Gamma function.
Read the full abstract
Mathematical Physics · Cross-listed from quant-ph
New approaches to almost i.i.d. information theory
Independent and identically distributed (i.i.d.) states are ubiquitous in quantum information theory. However, in a practical setting, the i.i.d. assumption is too stringent, and possibly not realistic. A physically more compelling class of 'almost i.i.d.' sources was recently proposed by [Mazzola/Sutter/Renner, arXiv:2603.15792]. In this paper, we introduce two alternative definitions of almost i.i.d. states, based on the normalised quantum Wasserstein distance and on the idea of looking at the average $k$-body marginal. We explore some basic properties of these notions and prove a strict hierarchical relation among them, with Mazzola et al.'s notion being the strictest, the one based on $k$-body marginals the loosest, and the one based on the quantum Wasserstein distance in between. Strict separation is established by means of explicit examples.
Read the full abstract
Information Theory · Cross-listed from cs.LG
Proposal and study of statistical features for string similarity computation and classification
Adaptations of features commonly applied in the field of visual computing, co-occurrence matrix (COM) and run-length matrix (RLM), are proposed for the similarity computation of strings in general (words, phrases, codes and texts). The proposed features are not sensitive to language related information. These are purely statistical and can be used in any context with any language or grammatical structure. Other statistical measures that are commonly employed in the field such as longest common subsequence, maximal consecutive longest common subsequence, mutual information and edit distances are evaluated and compared. In the first synthetic set of experiments, the COM and RLM features outperform the remaining state-of-the-art statistical features. In 3 out of 4 cases, the RLM and COM features were statistically more significant than the second best group based on distances (P-value < 0.001). When it comes to a real text plagiarism dataset, the RLM features obtained the best results.
Read the full abstract
Number Theory
Solutions for Hecke Sum Questions of Banerjee and Bringmann
We previously conjectured a Hecke-type identity for a series arising from two-color partitions. Banerjee and Bringmann proved the conjecture using modular methods and asked for a direct proof using Bailey pairs. They also suggested investigating the odd part of the series. We answer both questions by applying Bailey's transform to a Bailey pair of Andrews and a conjugate Bailey pair of Lovejoy. Our main theorem gives formulas for the even and odd parts of a series $P_a(q)$ depending on a parameter $a$. The specialization $a=1$ gives the conjectured formula and a companion formula for the odd part.
Read the full abstract
Combinatorics
Uniform Turán densities of $k$-uniform hypergraphs
For $k\ge 3$, the $(k-2)$-uniform Turán density $\pi_{k-2}(F)$ of a $k$-graph $F$ is the supremum of $d$ for which there are arbitrarily large $F$-free $k$-graphs that are uniformly $d$-dense with respect to the $k$-vertex cliques of every $(k-2)$-graph on the same vertex set. We develop a palette framework for this density. For every family $\mathcal F$ of $k$-graphs, we prove that $\pi_{k-2}(\mathcal F)$ equals the corresponding palette Turán density. We further establish palette classification tools for the existence of $k$-graphs satisfying prescribed palette colorability constraints. Those together allow us to reduce exact density computations to a palette-homomorphism framework without relying on the hypergraph regularity method. As applications, for all $k\ge 3$ and $r\ge 2$, we establish the following values \[ \frac{r-1}{r},\quad \frac{(r-1)^2}{r^2},\quad \frac{r-1}{2r},\quad \frac{(k-1)^k}{k^k},\quad \frac{4(k-2)^{k-2}}{k^k},\quad \frac{4(k-2)^{k-2}}{3k^k} \] as $(k-2)$-uniform Turán densities of single $k$-graphs. Finally, for every $k\ge3$, we show that there exist $k$-graphs $F_1,F_2$ such that \[ \pi_{k-2}(\{F_1,F_2\})< \min\{\pi_{k-2}(F_1),\pi_{k-2}(F_2)\}, \] which provides the first examples of non-principal families for this density.
Read the full abstract
Geometric Topology
Mazur manifolds and symplectic structures
We use the Heegaard Floer homology cobordism maps to obstruct the existence of a symplectic structure on the Akbulut-Kirby Mazur manifolds whose boundary is a Brieskorn sphere $Y$ among $\Sigma(2,3,13),$ $\Sigma(2,5,7)$ and $\Sigma(3,4,5)$. Furthermore, we describe how they imply the existence of exotic pairs of simply connected 4-manifolds, with definite intersection form, whose boundary is a Brieskorn sphere bounding a Mazur manifold.
Read the full abstract
Analysis of PDEs
An inverse problem for inhomogeneous Signorini obstacle
This paper investigates the inverse problem of determining a general Signorini obstacle using boundary measurements. We demonstrate that both the shape of the obstacle and the obstacle function can be uniquely determined from solution measurements taken on an arbitrary open subset of the boundary. This result applies to both the scalar and elasticity versions of the Signorini problem.
Read the full abstract
Numerical Analysis
Homotopy continuation of viscoelastic waveguide dispersion curves: from intra-manifold tracking to inter-manifold transport
Conventional mode tracking operates in the dark: it traces dispersion branches on the non-Hermitian eigenvalue manifold using only local continuity, unaware of the global Riemann-sheet topology. When exceptional points (EPs) lie close to the real frequency axis, the eigenvector similarity that local trackers rely on degrades, and mode tracking becomes unreliable, failing silently. This paper replaces blind intra-manifold tracking with inter-manifold transport. A material attenuation parameter s in [0,1] continuously maps the target lossy problem to an auxiliary lossless one whose Hermitian eigenvalue problem yields a well-posed anchor manifold on which each dispersion branch possesses a globally unique and continuous identity. These identities are defined once on the elastic anchor and then transported to the viscoelastic target via predictor-corrector homotopy continuation; as long as the path avoids all EPs, branch identity is preserved throughout the transport. For any mode pair whose EPs have not crossed the real frequency axis (Type I), the transported identities are inherited automatically. In contrast, when an EP crosses the real axis and becomes Type II, the topology differs from the elastic anchor and a label swap is required. The framework is validated on symmetric and unsymmetric laminates, with most cases at loss factors of 0.003 to 0.02; for all Type I pairs in these cases the identities are inherited without alteration. For a challenging unsymmetric laminate at 0.05, several EP pairs have become Type II, yet the homotopy transport still produces numerically accurate solutions. Two diagnostic signatures–an extremely sharp imaginary-part crossing and a marked discrepancy between spectral group velocity and energy flux velocity–identify where the underlying EP topology demands a label swap.
Read the full abstract
Statistics Theory · Cross-listed from stat.ML
Average Gradient Outer Product in kernel regression provably recovers the central subspace for multi-index models
We study a prototypical situation when a learned predictor can discover useful low-dimensional structure in data, while using fewer samples than are needed for accurate prediction. Specifically, we consider the problem of recovering a multi-index polynomial $f^*(x)=h(Ux)$, with $U\in\mathbb{R}^{r\times d}$ and $r\ll d$, from finitely many data/label pairs. Importantly, the target function depends on input $x$ only through the projection onto an unknown $r$-dimensional central subspace. The algorithm we analyze is appealingly simple: fit kernel ridge regression (KRR) to the data and compute the Average Gradient Outer Product (AGOP) from the fitted predictor. Our main results show that under reasonable assumptions the top $r$-dimensional eigenspace of AGOP provably recovers the central subspace, even in regimes when the prediction error remains large. Specifically, if the target function $f^*$ has degree $p^*$, it is known that $n\asymp d^{p^*}$ samples are necessary for KRR to achieve accurate prediction. In contrast, we show that if a low degree $p$ component of $f^*$ already carries all relevant directions for prediction, subspace recovery occurs in the much lower sample regime $n\asymp d^{p+\delta}$ for any $\delta\in(0,1)$. Our results thus demonstrate a separation between prediction and representation, and provide an explanation for why iterative kernel methods such as Recursive Feature Machines (RFM) can be sample-efficient in practice.
Read the full abstract
Rings and Algebras
Non-crystallographic systems of integers over composition algebras
In this work we revisit classical systems of integers inside the real normed division algebras from the point of view of finite norm shells and root systems. Building on the icosian framework of Moody–Patera and on the integral root-system viewpoint of Chen–Moody–Patera and of Johnson, we isolate the precise axiomatic ingredients of the non-crystallographic analogue: an order over the golden ring \(\Zphi\) together with a distinguished finite root shell whose Cartan coefficients lie in \(\Zphi\). We show that the usual Gaussian, Eisenstein, Hamilton, Hurwitz and Coxeter–Dickson examples are recovered by separating the order, its units, and its distinguished finite shells; once the lattice requirement is replaced by a finite root-shell requirement, the golden integer ring becomes the natural coefficient ring for the non-crystallographic cases \(H_2\) and \(H_4\). We then construct a weak golden octonion order by Cayley–Dickson doubling of the icosian ring; the resulting free rank-\(8\) \(\Zphi\)-order has a \(240\)-element finite shell of type \(H_4\oplus H_4\) and its multiplication is genuinely octonionic. Finally, we prove (i) that this weak double is self-dual with respect to the polar norm pairing, hence has no strict norm-integral overorder, and (ii) that the first trace-integral discriminant tower over it contains no octonion-stable nonzero isotropic gluing.
Read the full abstract
Analysis of PDEs
On the Necessity of Logarithmic Estimates for Hypoellipticity
This paper is focused on necessary conditions for hypoellipticity of an operator $L$ of the form $L=L_1(x)+g(x)L_2(y)$, where the operator $L_1$ is either elliptic or parabolic, $L_2$ is degenerately elliptic and $g(x)$ may itself vanish adding further degeneracy. First, we establish a logarithmic criterion: if the operator $L$ above is hypoelliptic and $L_1$ has a family of spectral solutions we define in the paper, then the remaining part $L_2$ must gain a power of a logarithm of a derivative. Such a property can be thought of as a restriction on degeneracy of the operator $L_2$. We then use this criterion to examine degenerate elliptic and parabolic operators closing gaps between sufficiency and necessity that have been open since 1980s in three and higher dimensions.
Read the full abstract
Number Theory
On Vu's restricted box estimate in Waring's problem
In 2000, Vu proved that the number of solutions of $x_1^k + \cdots + x_s^k = N$ in an arbitrary box satisfies the expected Hardy–Littlewood upper bound with a power-saving error term, for $s \geq O(8^k k^3)$. We show that one may take $s\geq k^2 - k + O(\sqrt{k})$.
Probability
The critical activation density in graph bootstrap percolation
In graph bootstrap percolation, edges of an Erdős-Rényi random graph ${\mathcal G}_{n,p}$ are initially active, and activation spreads to other edges of $K_n$ via the combinatorics of a fixed graph $H$: an edge becomes active whenever it is the unique inactive edge in a copy of $H$. The process $H$-percolates if all edges of $K_n$ are eventually activated. While classical cases such as $H=K_3$ (connectivity) and $H=K_4$ (related to $2$-neighbor bootstrap percolation) have been studied extensively, general graphs $H$ can exhibit wildly different behaviors. In this work, we determine the critical $H$-percolation threshold $p_c(n,H)$ for every graph $H$, fully resolving a longstanding open question of Balogh, Bollobás, and Morris. The location of $p_c(n,H)$ is governed by a new, universal parameter $\rho(H)$, which measures the maximal efficiency of witness graphs that activate an edge. To achieve this, we introduce a novel framework based on the unfolding and refolding of witness graphs. While previous works were restricted to specific families of $H$, our approach provides a unified strategy for all $H$. Inspired by algebraic topology, we lift witness graphs to covering graphs and algorithmically embed folded versions into ${\mathcal G}_{n,p}$ via a sequence of extensions. Crucially, this allows us to incorporate highly efficient witness graphs of unbounded size, which are potentially far larger than ${\mathcal G}_{n,p}$ itself. Beyond resolving $p_c(n,H)$, our framework recovers and strengthens several existing bounds in the literature. Finally, we initiate the study of the universal density parameter $\rho(H)$ and pose central open questions regarding its computability and its exact correspondence with the sharpness of the $H$-percolation threshold.
Read the full abstract
Combinatorics
The Rényi entropy of the order of a random permutation
We study the distribution of the order of a random permutation of $[n]$ through the lens of Rényi entropy. In particular, we obtain an asymptotic for the Rényi $q$-entropy of the order in the full range $1 \leq q \leq \infty$. For $q > 1$, our results are quantitatively optimal and reveal a tight connection between the asymptotic behaviour of the Rényi $q$-entropy and arithmetic properties of $n$. Of particular interest are the cases $q = \infty$ and $q = 2$, which correspond to the maximum probability of achieving a particular order and the probability that two independent random permutations have equal orders, respectively. In the former case, we show that the probability in question is asymptotic to $1/n$ and additionally characterise the maximiser for sufficiently large $n$. In the latter case, we determine a minimal and maximal order for the probability as a function of $n$, of respective forms $c/n^2$ and $\log^*n/n^2$. Our results provide an essentially complete answer to a set of questions raised by Acan, Burnette, Eberhard, Schmutz and Thomas, some of which go back to work of Erdős and Turán from the 1960s.
Read the full abstract
Combinatorics
Complete simplicial fans, Stanley–Reisner rings, and equivariant h-polynomials
We derive a graded character formula for the action of any finite group on the Artinian reduction of the Stanley–Reisner ring of any complete simplicial fan, which is given by an equivariant version of the classical h-polynomial. This gives the graded character formula for the representation of the group on the cohomology of the associated toric variety when the fan is rational. As an application, we use a navel tool, which we called hybrid fan, to compute the Poincaré polynomial of the invariants of the Artinian reduction of the Stanley–Reisner ring of any complete simplicial fan under a finite reflection group action. This implies that the Poincaré polynomial of the quotient of a compact toric orbifold by any finite reflection group is equal to the Poincaré polynomial of the compact toric orbifold associated to the hybrid fan.
Read the full abstract
Logic
Quasi-Polish spaces and spaces of filters in second-order arithmetic
The class of quasi-Polish spaces admits several equivalent representations, including UF spaces, NP spaces, $\mathbf{\Pi}_2^0$ subspaces of $\mathcal{P}(\mathbb{N})$, and sober spaces of countably presented frames. In this paper, we formalize these structures within second-order arithmetic and conduct a systematic reverse mathematical analysis of the transitions between them.