Markov decision processes with exponentially representable discounting

We generalize the geometric discount of finite discounted cost Markov Decision Processes to “exponentially representable”discount functions, prove existence of optimal policies which are stationary from some time N onward, and provide an algorithm for their computation. Outside this class, optimal “N-stationary” policies in general do not exist.     

Crossed modules as homotopy normal maps

In this note we consider crossed modules of groups (N→G, G→Aut(N)), as a homotopy version of the inclusion N⊂G of a normal subgroup. Our main observation is a characterization of the underlying map N→G of a crossed module in terms of a simplicial group structure on the associated bar construction. This approach allows for “natural” generalizations to other monoidal categories, in particular we consider briefly what we call “normal maps” between simplicial groups.     

Stacked polytopes and tight triangulations of manifolds

Tightness of a triangulated manifold is a topological condition, roughly meaning that any simplex-wise linear embedding of the triangulation into Euclidean space is “as convex as possible”. It can thus be understood as a generalization of the concept of convexity. In even dimensions, super-neighborliness is known to be a purely combinatorial condition which implies the tightness of a triangulation. Here, we present other sufficient and purely combinatorial conditions which can be applied to the odd-dimensional case as well. One of the conditions is that all vertex links are stacked spheres, which implies that the triangulation is in Walkup?s class K(d). We show that in any dimension d?4, tight-neighborly triangulations as defined by Lutz, Sulanke and Swartz are tight. Furthermore, triangulations with k-stacked vertex links and the centrally symmetric case are discussed.     

Shape sensitivity for the Laplace-Beltrami operator with singularities

This paper considers shape sensitivity analysis for the Laplace-Beltrami operator formulated on a two-dimensional manifold with a fracture. We characterize the shape gradient of a functional as a bounded measure on the manifold and decompose it into a “distributed gradient” supported on the manifold, plus a singular part that we derive as the limit of a “jump” through the crack and Dirac measures at the crack extremities. The important point is that we introduce a technique that is not dimension dependent, and makes no use of classical arguments such as the maximum principle or continuation uniqueness. The technique makes use of a family of envelopes surrounding the fracture which enable us to relax certain terms and to overcome the lack of regularity resulting from the presence of the fracture. We use the min-max differentiation in order to avoid taking the derivative of the state equation and to manage the crack's singularities. Therefore, we write the functional in a min-max formulation on a space which takes into account the hidden boundary regularity established by the tangential extractor method.     

On some hereditary properties of Riemannian g-natural metrics on tangent bundles of Riemannian manifolds

It is well known that if the tangent bundle TM of a Riemannian manifold (M,g) is endowed with the Sasaki metric gs, then the flatness property on TM is inherited by the base manifold [Kowalski, J. Reine Angew. Math. 250 (1971) 124-129]. This motivates us to the general question if the flatness and also other simple geometrical properties remain “hereditary” if we replace gs by the most general Riemannian “g-natural metric” on TM (see [Kowalski and Sekizawa, Bull. Tokyo Gakugei Univ. (4) 40 (1988) 1-29; Abbassi and Sarih, Arch. Math. (Brno), submitted for publication]). In this direction, we prove that if (TM,G) is flat, or locally symmetric, or of constant sectional curvature, or of constant scalar curvature, or an Einstein manifold, respectively, then (M,g) possesses the same property, respectively. We also give explicit examples of g-natural metrics of arbitrary constant scalar curvature on TM.     

Differential conformal superalgebras and their forms

We introduce the formalism of differential conformal superalgebras, which we show leads to the “correct” automorphism group functor and accompanying descent theory in the conformal setting. As an application, we classify forms of N=2 and N=4 conformal superalgebras by means of Galois cohomology.     

Ideal Turaev-Viro invariants

Turaev-Viro invariants are defined via state sum polynomials associated to a special spine or a triangulation of a compact 3-manifold. By evaluation of the state sum at any solution of the so-called Biedenharn-Elliott equations, one obtains a homeomorphism invariant of the manifold (“numerical Turaev-Viro invariant”). The Biedenharn-Elliott equations define a polynomial ideal. The key observation of this paper is that the coset of the state sum polynomial with respect to that ideal is a homeomorphism invariant of the manifold (“ideal Turaev-Viro invariant”), stronger than the numerical Turaev-Viro invariants. Using computer algebra, we obtain computational results on several examples of ideal Turaev-Viro invariants, for all closed orientable irreducible manifolds of complexity at most 9.     

Almost disjoint large subsets of semigroups

There are several notions of largeness in a semigroup S that originated in topological dynamics. Among these are thick, central, syndetic and piecewise syndetic. Of these, central sets are especially interesting because they are partition regular and are guaranteed to contain substantial combinatorial structure. It is known that in (N,+) any central set may be partitioned into infinitely many pairwise disjoint central sets. We extend this result to a large class of semigroups (including (N,+)) by showing that if S is a semigroup in this class which has cardinality κ then any central set can be partitioned into κ many pairwise disjoint central sets. We also show that for this same class of semigroups, if there exists a collection of μ almost disjoint subsets of any member S, then any central subset of S contains a collection of μ almost disjoint central sets. The same statement applies if “central” is replaced by “thick”; and in the case that the semigroup is left cancellative, “central” may be replaced by “piecewise syndetic”. The situation with respect to syndetic sets is much more restrictive. For example, there does not exist an uncountable collection of almost disjoint syndetic subsets of N. We investigate the extent to which syndetic sets can be split into disjoint syndetic sets.     

A degree sum condition for graphs to be prism hamiltonian

Win, in 1975, and Jackson and Wormald, in 1990, found the best sufficient conditions on the degree sum of a graph to guarantee the properties of “having a k-tree” and “having a k-walk”, respectively. The property of “being prism hamiltonian” is an intermediate property between “having a 2-tree” and “having a 2-walk”. Thus, it is natural to ask what is the best degree sum condition for graphs to be prism hamiltonian. As an answer to this problem, in this paper, we show that a connected graph G of order n with σ₃(G)≥n is prism hamiltonian. The degree sum condition “σ₃(G)≥n” is best possible.     

Tau-functions,Grassmannians and rank one conditions

In integrable systems, specifically the KP hierarchy, there are functions known as “tau-functions”, closely related to the Schur polynomials in terms of which they are often written. Although they are generally viewed as the solutions to a collection of nonlinear PDEs, in this note they will equivalently be characterized by a quadratic difference equation. Sato's theorem associates tau-functions to the points of a Grassmann manifold. To make that amazing theorem clear to non-experts, we will first show an analogous (but easily understood) example of a linear ODE and its solution from a flow on the xy-plane. In each case the solution is created via a flow generated by a certain linear operator. The question we pose is this: “What other operators could have been used to generate solutions in the same way?” Although the answer is well known in the ODE case, the question in the nonlinear case is the main result of our new paper. We will state the result and discuss its relationship to the “trend” of writing tau-functions in terms of matrices satisfying certain rank one conditions. The elucidation of a geometric interpretation of the Hirota bilinear difference equation (HBDE) is a key feature of the proof and will be briefly described.     

Second variation and Legendrian stabilities of minimal Legendrian submanifolds in Sasakian manifolds

First, we derive a new second variation formula which holds for minimal Legendrian submanifolds in Sasakian manifolds. Using this, we prove that any minimal Legendrian submanifold in an η-Einstein Sasakian manifold with “nonpositive” η-Ricci constant is stable. Next we introduce the notion of the Legendrian stability of minimal Legendrian submanifolds in Sasakian manifolds. Using our second variation formula, we find a general criterion for the Legendrian stability of minimal Legendrian submanifolds in η-Einstein Sasakian manifolds with “positive” η-Ricci constant.     

Modified Whittle estimation of multilateral models on a lattice

In the estimation of parametric models for stationary spatial or spatio-temporal data on a d-dimensional lattice, for d?2, the achievement of asymptotic efficiency under Gaussianity, and asymptotic normality more generally, with standard convergence rate, faces two obstacles. One is the “edge effect”, which worsens with increasing d. The other is the possible difficulty of computing a continuous-frequency form of Whittle estimate or a time domain Gaussian maximum likelihood estimate, due mainly to the Jacobian term. This is especially a problem in “multilateral” models, which are naturally expressed in terms of lagged values in both directions for one or more of the d dimensions. An extension of the discrete-frequency Whittle estimate from the time series literature deals conveniently with the computational problem, but when subjected to a standard device for avoiding the edge effect has disastrous asymptotic performance, along with finite sample numerical drawbacks, the objective function lacking a minimum-distance interpretation and losing any global convexity properties. We overcome these problems by first optimizing a standard, guaranteed non-negative, discrete-frequency, Whittle function, without edge-effect correction, providing an estimate with a slow convergence rate, then improving this by a sequence of computationally convenient approximate Newton iterations using a modified, almost-unbiased periodogram, the desired asymptotic properties being achieved after finitely many steps. The asymptotic regime allows increase in both directions of all d dimensions, with the central limit theorem established after re-ordering as a triangular array. However our work offers something new for “unilateral” models also. When the data are non-Gaussian, asymptotic variances of all parameter estimates may be affected, and we propose consistent, non-negative definite estimates of the asymptotic variance matrix.     

The Oshima-Sekiguchi and Liouville theorems on Heintze groups

Let L be an elliptic operator on a Riemannian manifold M. A function F annihilated by L is said to be L-harmonic. F is said to have moderate growth if and only if F grows at most exponentially in the Riemannian distance. If M is a rank-one symmetric space and L is the Laplace-Beltrami operator for M, the Oshima-Sekiguchi theorem [T. Oshima, J. Sekiguchi, Eigenspaces of invariant differential operators on an affine symmetric space, Invent. Math. 57 (1980) 1-81] states that a L-harmonic function F has moderate growth if and only if F is the Poisson integral of a distribution on the Furstenberg boundary. In this work we prove that this result generalizes to a very large class of homogeneous Riemannian manifolds of negative curvature. We also (i) prove a Liouville type theorem that characterizes the “polynomial-like” harmonic functions which vanish on the boundary in terms of their growth properties, (ii) describe all “polynomial-like” harmonic functions, and (iii) give asymptotic expansions for the Poisson kernel. One consequence of this work is that every Schwartz distribution on the boundary is the boundary value for a L-harmonic function F which is uniquely determined modulo “polynomial-like” harmonic functions.     

Canonical and monophonic convexities in hypergraphs

Known properties of “canonical connections” from database theory and of “closed sets” from statistics implicitly define a hypergraph convexity, here called canonical convexity (c-convexity), and provide an efficient algorithm to compute c-convex hulls. We characterize the class of hypergraphs in which c-convexity enjoys the Minkowski-Krein-Milman property. Moreover, we compare c-convexity with the natural extension to hypergraphs of monophonic convexity (or m-convexity), and prove that: (1) m-convexity is coarser than c-convexity, (2) m-convexity and c-convexity are equivalent in conformal hypergraphs, and (3) m-convex hulls can be computed in the same efficient way as c-convex hulls.     

Chiral differential operators: Formal loop group actions and associated modules

Chiral differential operators (CDOs) are closely related to string geometry and the quantum theory of 2-dimensional σ-models. This paper investigates two topics about CDOs on smooth manifolds. In the first half, we study how a Lie group action on a smooth manifold can be lifted to a “formal loop group action” on an algebra of CDOs; this turns out to be a condition on the equivariant first Pontrjagin class. The case of a principal bundle receives particular attention and gives rise to a type of vertex algebras of great interest. In the second half, we introduce a construction of modules over CDOs using the said “formal loop group actions” and semi-infinite cohomology. Intuitively, these modules should have a geometric meaning in terms of “formal loop spaces”. The first example we study leads to a new conceptual construction of an arbitrary algebra of CDOs. The other example, called the spinor module, may be useful for a geometric theory of the Witten genus.     

How strange can an attractor for a dynamical system in a 3-manifold look?

The aim of this paper is to characterise those compact subsets K of 3-manifolds M that are (stable and not necessarily global) attractors for some flow on M. We will show that it is the topology of M−K, rather than that of K, the one that plays a relevant role in this problem.A necessary and sufficient condition for a set K to be an attractor is that it must be an “almost tame” subset of M in a sense made precise under the equivalent notions of “weakly tame” and “tamely embedded up to shape”, defined in the paper. These are complemented by a further equivalent condition, “algebraic tameness”, which has the advantage of being checkable by explicit computation.A final section of the paper is devoted to a partial analysis of the same question when one replaces flows by discrete dynamical systems.     

Optimal production correction and maintenance policy for imperfect process

This study considers imperfect production processes that require production correction and maintenance. Two states of the production process are performed, namely: the type I state (out-of-control state) and the type II state (in-control state). At the beginning of the production of the each renewal cycle, the state of the process is assumed not always to be restored to “in-control”. The type I state involves the adjustment of the production mechanism, whereas the type II state does not. Production correction is either imperfect; worsening a production system, or perfect, returning it to “in-control”. After N + 1 type I states, the operating system must be maintained and returned to the beginning condition. The mean loss cost due to reproduction through production correction per the total expected cost until the N + 1 type I states are entered successively is determined. The existence of a unique and finite optimal N for an imperfect process under certain reasonable conditions is shown. A numerical example is presented.     

Eigenvalue estimates for Dirac operators with parallel characteristic torsion

Assume that the compact Riemannian spin manifold (Mn,g) admits a G-structure with characteristic connection ∇ and parallel characteristic torsion (∇T=0), and consider the Dirac operator D1/3 corresponding to the torsion T/3. This operator plays an eminent role in the investigation of such manifolds and includes as special cases Kostant's “cubic Dirac operator” and the Dolbeault operator. In this article, we describe a general method of computation for lower bounds of the eigenvalues of D1/3 by a clever deformation of the spinorial connection. In order to get explicit bounds, each geometric structure needs to be investigated separately; we do this in full generality in dimension 4 and for Sasaki manifolds in dimension 5.     

The rational canonical form via the splitting field

It is clear that a given rational canonical form can be further resolved to a Jordan canonical form with entries from the splitting field of its minimal polynomial. Conversely, with an a priori knowledge of the existence and uniqueness of the rational canonical form of a matrix with entries from a general field, one can modify its Jordan canonical form in the splitting field of its minimal polynomial to construct its rational canonical form in the original field. No author has tried this converse with the a priori existence–uniqueness condition removed. It is feared that “in many occasions when, after a result has been established for a matrix with entries in a given field, considered as a matrix with entries in a finite extension of that field, we cannot go back from the extension field to get the desired information in the original field” [I.N. Herstein, Topics in Algebra, Ginn and Company, Waltham, MA, 1964 (pp. 262–263)]. The present paper removes this a priori condition and uses a “symmetrization” to “integrate” back the Jordan canonical form of a matrix to its rational canonical form in the original field.