A Mathematica package for q-holonomic sequences and power series

We describe a Mathematica package for dealing with q-holonomic sequences and power series. The package is intended as a q-analogue of the Maple package gfun and the Mathematica package GeneratingFunctions. It provides commands for addition, multiplication, and substitution of these objects, for converting between various representations (q-differential equations, q-recurrence equations, q-shift equations), for computing sequence terms and power series coefficients, and for guessing recurrence equations given initial terms of a sequence. C. Koutschan partially supported by the Austrian Science Foundation (FWF) grants SFB F1305.     

Limit Property for Regular and Weak Generalized Convolution

We denote by ? \((\mathcal{P_{+}})\) the set of all probability measures defined on the Borel subsets of the real line (the positive half-line [0,∞)). K. Urbanik defined the generalized convolution as a commutative and associative ?₊-valued binary operation ? on ? ₊ ² which is continuous in each variable separately. This convolution is distributive with respect to convex combinations and scale changes T _a (a>0) with δ ₀ as the unit element. The key axiom of a generalized convolution is the following: there exist norming constants c _n and a measure ν other than δ ₀ such that \(T_{c_{n}}\delta_{1}^{\bullet n}\to\nu\).In Sect. 2 we discuss basic properties of the generalized convolution on ? which hold for the convolutions without the key axiom. This rather technical discussion is important for the weak generalized convolution where the key axiom is not a natural assumption. In Sect. 4 we show that if the weak generalized convolution defined by a weakly stable measure μ has this property, then μ is a factor of strictly stable distribution.     

Dense Fast Random Projections and Lean Walsh Transforms

Random projection methods give distributions over k×d matrices such that if a matrix Ψ (chosen according to the distribution) is applied to a finite set of vectors x _i ∈ℝ ^d the resulting vectors Ψx _i ∈ℝ ^k approximately preserve the original metric with constant probability. First, we show that any matrix (composed with a random ±1 diagonal matrix) is a good random projector for a subset of vectors in ℝ ^d . Second, we describe a family of tensor product matrices which we term Lean Walsh. We show that using Lean Walsh matrices as random projections outperforms, in terms of running time, the best known current result (due to Matousek) under comparable assumptions.     

Some Inequalities Related to Transience and Recurrence of Markov Processes and Their Applications

For an irreducible symmetric Markov process on a (not necessarily compact) state space associated with a symmetric Dirichlet form, we give Poincaré-type inequalities. As an application of the inequalities, we consider a time-inhomogeneous diffusion process obtained by a time-dependent drift transformation from a diffusion process and give general conditions for the transience or recurrence of some sets. As a particular case, the diffusion process appearing in the theory of simulated annealing is considered.     

Cone-constrained eigenvalue problems: theory and algorithms

Equilibria in mechanics or in transportation models are not always expressed through a system of equations, but sometimes they are characterized by means of complementarity conditions involving a convex cone. This work deals with the analysis of cone-constrained eigenvalue problems. We discuss some theoretical issues like, for instance, the estimation of the maximal number of eigenvalues in a cone-constrained problem. Special attention is paid to the Paretian case. As a short addition to the theoretical part, we introduce and study two algorithms for solving numerically such type of eigenvalue problems.     

Two cancellative commutative congruences and group diagrams

Remmers (Adv. Math. 36:283–296, 1980) uses group diagrams in the Euclidean plane to demonstrate how equality in a semigroup S “mirrors” that inside the group G sharing the same presentation with S, when S satisfies Adyan’s condition—no cycles in the left/right graphs of the semigroup’s presentation. Goldstein and Teymouri (Semigroup Forum 47:299–304, 1993) introduce a conjugacy equivalence relation for semigroups S. By closely examining the geometry of annular group diagrams in the plane, they show how their equivalence relation mirrors conjugacy inside G, for S satisfying Adyan’s. In this article we introduce two cancellative commutative congruences. Following their leads, we examine the geometry of group diagrams on closed surfaces of higher genera to demonstrate how these congruences mirror equality inside two naturally associated Abelian quotient groups G/[G,G] and G/G ², respectively. In these instances we can drop Adyan’s condition.     

Maxima and Minima of the Hosoya Index and the Merrifield-Simmons Index

The Hosoya index and the Merrifield-Simmons index are typical examples of graph invariants used in mathematical chemistry for quantifying relevant details of molecular structure. In recent years, quite a lot of work has been done on the extremal problem for these two indices, i.e., the problem of determining the graphs within certain prescribed classes that maximize or minimize the index value. This survey collects and classifies these results, and also provides some useful auxiliary results, tools and techniques that are frequently used in the study of this type of problem.     

Symmetric functions,codes of partitions and the KP hierarchy

We consider an operator of Bernstein for symmetric functions and give an explicit formula for its action on an arbitrary Schur function. This formula is given in a remarkably simple form when written in terms of some notation based on the code of a partition. As an application, we give a new and very simple proof of a classical result for the KP hierarchy, which involves the Plücker relations for Schur function coefficients in a τ-function for the hierarchy. This proof is especially compact because we are able to restate the Plücker relations in a form that is symmetrical in terms of partition code notation.     

Martingale Approximation and Optimality of Some Conditions for the Central Limit Theorem

Let (X _i ) be a stationary and ergodic Markov chain with kernel Q and f an L ² function on its state space. If Q is a normal operator and f=(I?Q)^1/2 g (which is equivalent to the convergence of \(\sum_{n=1}^{\infty}\frac{\sum_{k=0}^{n-1}Q^{k}f}{n^{3/2}}\) in L ²), we have the central limit theorem [cf. (Derriennic and Lin in C.R. Acad. Sci. Paris, Sér. I 323:1053–1057, 1996; Gordin and Lif?ic in Third Vilnius conference on probability and statistics, vol. 1, pp. 147–148, 1981)]. Without assuming normality of Q, the CLT is implied by the convergence of \(\sum_{n=1}^{\infty}\frac{\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}}{n^{3/2}}\), in particular by \(\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}=o(\sqrt{n}/\log^{q}n)\), q>1 by Maxwell and Woodroofe (Ann. Probab. 28:713–724, 2000) and Wu and Woodroofe (Ann. Probab. 32:1674–1690, 2004), respectively. We show that if Q is not normal and f∈(I?Q)^1/2 L ², or if the conditions of Maxwell and Woodroofe or of Wu and Woodroofe are weakened to \(\sum_{n=1}^{\infty}c_{n}\frac{\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}}{n^{3/2}}<\infty\) for some sequence c _n ↘0, or by \(\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}=O(\sqrt{n}/\log n)\), the CLT need not hold.     

A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing

The three-dimensional bin packing problem consists of packing a set of boxes into the minimum number of bins. In this paper we propose a new GRASP algorithm for solving three-dimensional bin packing problems which can also be directly applied to the two-dimensional case. The constructive phase is based on a maximal-space heuristic developed for the container loading problem. In the improvement phase, several new moves are designed and combined in a VND structure. The resulting hybrid GRASP/VND algorithm is simple and quite fast and the extensive computational results on test instances from the literature show that the quality of the solutions is equal to or better than that obtained by the best existing heuristic procedures.     

On the Wave Equation Associated to the Hermite and the Twisted Laplacian

The dispersive properties of the wave equation u _tt +Au=0 are considered, where A is either the Hermite operator −Δ+|x|² or the twisted Laplacian −(∇ _x −iy)²/2−(∇ _y +ix)²/2. In both cases we prove optimal L ¹−L ^∞ dispersive estimates. More generally, we give some partial results concerning the flows exp (itL ^ν ) associated to fractional powers of the twisted Laplacian for 0<ν<1.     

Suitability and managerial implications of a Master Surgical Scheduling approach

Operating room (OR) planning and scheduling is a popular and challenging subject within the operational research applied to health services research (ORAHS). However, the impact in practice is very limited. The organization and culture of a hospital and the inherent characteristics of its processes impose specific implementation issues that affect the success of planning approaches. Current tactical OR planning approaches often fail to account for these issues. Master surgical scheduling (MSS) is a promising approach for hospitals to optimize resource utilization and patient flows. We discuss the pros and cons of MSS and compare MSS with centralized and decentralized planning approaches. Finally, we address various implementation issues of MSS and discuss its suitability for hospitals with different organizational foci and culture.     

Numerical semigroups: Apéry sets and Hilbert series

Let a ₁,…,a _n be relatively prime positive integers, and let S be the semigroup consisting of all non-negative integer linear combinations of a ₁,…,a _n . In this paper, we focus our attention on AA-semigroups, that is semigroups being generated by almost arithmetic progressions. After some general considerations, we give a characterization of the symmetric AA-semigroups. We also present an efficient method to determine an Apéry set and the Hilbert series of an AA-semigroup. Dedicated to the memory of Ernst S. Selmer (1920–2006), whose calculations revealed the “Selmer group”.     

Switching Time Optimization for Bang-Bang and Singular Controls

Optimal control problems with the control variable appearing linearly are studied. A method for optimization with respect to the switching times of controls containing both bang-bang and singular arcs is presented. This method is based on the transformation of the control problem into a finite-dimensional optimization problem. Therein, first and second-order optimality conditions are thoroughly discussed. Explicit representations of first and second-order variational derivatives of the state trajectory with respect to the switching times are given. These formulas are used to prove that the second-order sufficient conditions can be verified on the basis of only first-order variational derivatives of the state trajectory. The effectiveness of the proposed method is tested with two numerical examples.     

Minimum and Surjectivity Moduli Preserving in Banach Space

Let m(T) and q(T) be respectively the minimum and the surjectivity moduli of T∈ℬ(X), where ℬ(X) denotes the algebra of all bounded linear operators on a complex Banach space X. If there exists a semi-invertible but non-invertible operator in ℬ(X) then, given a surjective unital linear map φ: ℬ(X)⟶ℬ(X), we prove that m(T)=m(φ(T)) for all T∈ℬ(X), if and only if, q(T)=q(φ(T)) for all T∈ℬ(X), if and only if, there exists a bijective isometry U∈ℬ(X) such that φ(T)=UTU ⁻¹ for all T∈ℬ(X).     

Existence of a periodic solution for continuous and discrete periodic second-order equations with variable potentials

Green’s functions for new second-order periodic differential and difference equations with variable potentials are found, then used as kernels in integral operators to guarantee the existence of a positive periodic solution to continuous and discrete second-order periodic boundary value problems with periodic coefficient functions. A new version of the Leggett-Williams fixed point theorem is employed.     

Logarithmic Estimates for Submartingales and Their Differential Subordinates

In the paper we determine, for any K>0 and α∈[0,1], the optimal constant L(K,α)∈(0,∞] for which the following holds: If X is a nonnegative submartingale and Y is α-strongly differentially subordinate to X, then

Inexact Josephy–Newton framework for generalized equations and its applications to local analysis of Newtonian methods for constrained optimization

We propose and analyze a perturbed version of the classical Josephy–Newton method for solving generalized equations. This perturbed framework is convenient to treat in a unified way standard sequential quadratic programming, its stabilized version, sequential quadratically constrained quadratic programming, and linearly constrained Lagrangian methods. For the linearly constrained Lagrangian methods, in particular, we obtain superlinear convergence under the second-order sufficient optimality condition and the strict Mangasarian–Fromovitz constraint qualification, while previous results in the literature assume (in addition to second-order sufficiency) the stronger linear independence constraint qualification as well as the strict complementarity condition. For the sequential quadratically constrained quadratic programming methods, we prove primal-dual superlinear/quadratic convergence under the same assumptions as above, which also gives a new result.