For a variety of pattern-avoiding classes, we describe the limiting distribution for the number of fixed points for involutions chosen uniformly at random from that class. In particular we consider monotone patterns of arbitrary length as well as all patterns of length 3. For monotone patterns we utilize the connection with standard Young tableaux with at most k rows and involutions avoiding a monotone pattern of length k. For every pattern of length 3 we give the bivariate generating function with respect to fixed points for the involutions that avoid that pattern, and where applicable apply tools from analytic combinatorics to extract information about the limiting distribution from the generating function. Many well-known distributions appear.
The catenary degree is an invariant that measures the distance between factorizations of elements within an atomic monoid. In this paper, we classify which finite subsets of Z≥0 occur as the set of catenary degrees of a numerical monoid (i.e., a co-finite, additive submonoid of Z≥0). In particular, we show that, with one exception, every finite subset of Z≥0 that can possibly occur as the set of catenary degrees of some atomic monoid is actually achieved by a numerical monoid.
We investigate the position that foundational theories should be modelled on ordinary computability, with axioms and theorems presented as sequents of Σ formulas. We define a proof from such a theory to be a finite sequence of Σ formulas, with an axiom of the theory applied at each step. We obtain a complete system of logical axioms for this style of proof. In such a proof, free variables are not implicitly universally quantified, but rather behave like parameters, so each formula may be computationally verified, notionally in an infinitary setting, and literally in a finitary one. We show that such a foundational theory may establish the semantic properties of the Σ truth predicate, and may additionally establish that the truth of the assumption of any of its axioms implies the truth of the conclusion, but nevertheless that theory may be strong enough to formalize standard foundational theories in both the finitary and infinitary settings. We also show that the Σ truth predicate may be extended to intuitionistic sentences in a way that respects the connectives permitted in Σ formulas, by appealing to the constructive properties of intuitionstic deduction. Finally, we propose two completeness principles for the universe of pure sets, and show that they are equivalent.
We consider quantum information tasks in an operator algebraic setting, where we consider normal states on von Neumann algebras. In particular, we consider subfactors N⊂M, that is, unital inclusions of von Neumann algebras with trivial center. One can ask the following question: given a normal state ω on M, how much can one learn by only doing measurements from N? We argue how the Jones index [M:N] can be used to give a quantitative answer to this, showing how the rich theory of subfactors can be used in a quantum information context. As an example we discuss how the Jones index can be used in the context of wiretap channels. Subfactors also occur naturally in physics. Here we discuss two examples: rational conformal field theories and Kitaev's toric code on the plane, a prototypical example of a topologically ordered model. There we can directly relate aspects of the general setting to physical properties such as the quantum dimension of the excitations. In the example of the toric code we also show how we can calculate the index via an approximation with finite dimensional systems. This explicit construction sheds more light on the connection between topological order and the Jones index.
Assume we are given a sum of linear measurements of s different rank-r matrices of the form y=∑sk=1Ak(Xk). When and under which conditions is it possible to extract (demix) the individual matrices Xk from the single measurement vector y? And can we do the demixing numerically efficiently? We present two computationally efficient algorithms based on hard thresholding to solve this low rank demixing problem. We prove that under suitable conditions these algorithms are guaranteed to converge to the correct solution at a linear rate. We discuss applications in connection with quantum tomography and the Internet-of-Things. Numerical simulations demonstrate empirically the performance of the proposed algorithms.
We extend the theory of relative trisections of smooth, compact, oriented 4-manifolds with connected boundary given by Gay and Kirby to include 4-manifolds with an arbitrary number of boundary components. Additionally, we provide sufficient conditions under which relatively trisected 4-manifolds can be glued to one another along diffeomorphic boundary components so as to induce a trisected manifold. These two results allow us to define a category Tri whose objects are smooth, closed, oriented 3-manifolds equipped with open book decompositions, and morphisms are relatively trisected cobordisms. Additionally, we extend the Hopf stabilization of open book decompositions to a relative stabilization of relative trisections.
We study the family of spin-S quantum spin chains with a nearest neighbor interaction given by the negative of the singlet projection operator. Using a random loop representation of the partition function in the limit of zero temperature and standard techniques of classical statistical mechanics, we prove dimerization for all sufficiently large values of S.
Consider the following partial “sorting algorithm” on permutations: take the first entry of the permutation in one-line notation and insert it into the position of its own value. Continue until the first entry is 1. This process imposes a forest structure on the set of all permutations of size n, where the roots are the permutations starting with 1 and the leaves are derangements. Viewing the process in the opposite direction towards the leaves, one picks a fixed point and moves it to the beginning. Despite its simplicity, this “fixed point forest” exhibits a rich structure. In this paper, we consider the fixed point forest in the limit n → ∞ and show using Stein’s method that at a random permutation the local structure weakly converges to a tree defined in terms of independent Poisson point processes. We also show that the distribution of the length of the longest path from a random permutation to a leaf converges to the geometric distribution with mean e − 1, and the length of the shortest path converges to the Poisson distribution with mean 1. In addition, the higher moments are bounded and hence the expectations converge as well.
We initiate the study of general neighborhood growth dynamics on two dimensional Hamming graphs. The decision to add a point is made by counting the currently occupied points on the horizontal and the vertical line through it, and checking whether the pair of counts lies outside a fixed Young diagram. We focus on two related extremal quantities. The first is the size of the smallest set that eventually occupies the entire plane. The second is the minimum of an energy-entropy functional that comes from the scaling of the probability of eventual full occupation versus the density of the initial product measure within a rectangle. We demonstrate the existence of this scaling and study these quantities for large Young diagrams.
Classical Spanier-Whitehead duality was introduced for the stable homotopy category of finite CW complexes. Here we provide a comprehensive treatment of a noncommutative version, termed Spanier-Whitehead $K$-duality, which is defined on the category of $C^*$-algebras whose $K$-theory is finitely generated and that satisfy the UCT with morphisms the $KK$-groups. We explore what happens when these assumptions are relaxed in various ways. In particular, we consider the relationship between Paschke duality and Spanier-Whitehead $K$-duality.
