On the optimal switching level for an M/G/1 queueing system

A cost function is studied for an M/G/1 queueing model for which the service rate of the virtual waiting time process U_t for U_t<K differs from that for U_t > K. The costs considered are costs for maintaining the service rate, costs for switching the service rate and costs proportional to the inventory U_t. The relevant cost factors for the system operating below level K differ from those when U_t > K. The cost function which is considered only for the stationary situation of the U_t-process expresses the average cost per unit time. The problem is to find that K for which the cost function reaches a minimum. Criteria for the possibly optimal cases are found; they have an interesting intuitive interpretation, and require the knowledge of only the first moment of the service time distribution.     

On equivalence of moduli of smoothness of polynomials in ,

It is well known that for functions , 1p∞. For general functions fL_p, it does not hold for 0<p<1, and its inverse is not true for any p in general. It has been shown in the literature, however, that for certain classes of functions the inverse is true, and the terms in the inequalities are all equivalent. Recently, Zhou and Zhou proved the equivalence for polynomials with p=∞. Using a technique by Ditzian, Hristov and Ivanov, we give a simpler proof to their result and extend it to the L_p space for 0<p∞. We then show its analogues for the Ditzian–Totik modulus of smoothness and the weighted Ditzian–Totik modulus of smoothness for polynomials with .     

Upper bounds for the formula size of symmetric Boolean functions

We prove that the complexity of the implementation of the counting function of n Boolean variables by binary formulas is at most n ^3.03, and it is at most n ^4.47 for DeMorgan formulas. Hence, the same bounds are valid for the formula size of any threshold symmetric function of n variables, particularly, for the majority function. The following bounds are proved for the formula size of any symmetric Boolean function of n variables: n ^3.04 for binary formulas and n ^4.48 for DeMorgan ones. The proof is based on the modular arithmetic.     

Hypercontractivity for log-subharmonic functions

We prove strong hypercontractivity (SHC) inequalities for logarithmically subharmonic functions on Rn and different classes of measures: Gaussian measures on Rn, symmetric Bernoulli and symmetric uniform probability measures on R, as well as their convolutions. Surprisingly, a slightly weaker strong hypercontractivity property holds for any symmetric measure on R. A log-Sobolev inequality (LSI) is deduced from the (SHC) for compactly supported measures on Rn, still for log-subharmonic functions. An analogous (LSI) is proved for Gaussian measures on Rn and for other measures for which we know the (SHC) holds. Our log-Sobolev inequality holds in the log-subharmonic category with a constant smaller than the one for Gaussian measure in the classical context.     

Exact travelling wave solutions of the generalized Bretherton equation

We search for exact travelling wave solutions of the generalized Bretherton equation for integer, greater than one, values of the exponent m of the nonlinear term by two methods: the truncated Painlevé expansion method and an algebraic method. We find periodic solutions for m=2 and m=5, to add to those already known for m=3; in all three cases these solutions exist for finite intervals of the wave velocity. We also find a “kink” shaped solitary wave for m=5 and a family of elementary unbounded solutions for arbitrary m.     

The steiner ratio conjecture is true for five points

The long-standing conjecture of Gilbert and Pollak states that for any set of n given points in the Euclidean plane, the ratio of the length of a Steiner minimal tree and the length of a minimal (spanning) tree is at least $\text{3}\text{2}$. This conjecture was shown to be true for n = 3 by Gilbert and Pollak, and for n = 4 by Pollak. Recently, Du, Yao and Hwang used a different approach to give a shorter proof for n = 4. In this paper we continue this approach to prove the conjecture for n = 5. Such results for small n are useful in obtaining bounds for the ratio of the two lengths in the general case.     

Representations of Central Matrix-Valued Carathéodory Functions in Both Nondegenerate and Degenerate Cases

We derive left and right quotient representations for central q × q matrix-valued Carathéodory functions. Moreover, we obtain recurrent formulas for the matrix polynomials involved in the quotient representations. These formulas are the starting point for getting recurrent formulas for those matrix polynomials which occur in the Arov-Krein resolvent matrix for the nondegenerate matricial Carathéodory problem.     

Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots

This paper addresses cyclic scheduling of a no-wait robotic cell with multiple robots. In contrast to many previous studies, we consider r-degree cyclic (r > 1) schedules, in which r identical parts with constant processing times enter and leave the cell in each cycle. We propose an algorithm to find the minimal number of robots for all feasible r-degree cycle times for a given r (r > 1). Consequently, the optimal r-degree cycle time for any given number of robots for this given r can be obtained with the algorithm. To develop the algorithm, we first show that if the entering times of r parts, relative to the start of a cycle, and the cycle time are fixed, minimizing the number of robots for the corresponding r-degree schedule can be transformed into an assignment problem. We then demonstrate that the cost matrix for the assignment problem changes only at some special values of the cycle time and the part entering times, and identify all special values for them. We solve our problem by enumerating all possible cost matrices for the assignment problem, which is subsequently accomplished by enumerating intervals for the cycle time and linear functions of the part entering times due to the identification of the special values. The algorithm developed is shown to be polynomial in the number of machines for a fixed r, but exponential if r is arbitrary.     

Hypoelliptic heat kernel inequalities on the Heisenberg group

We study the existence of “L^p-type” gradient estimates for the heat kernel of the natural hypoelliptic “Laplacian” on the real three-dimensional Heisenberg Lie group. Using Malliavin calculus methods, we verify that these estimates hold in the case p>1. The gradient estimate for p=2 implies a corresponding Poincaré inequality for the heat kernel. The gradient estimate for p=1 is still open; if proved, this estimate would imply a logarithmic Sobolev inequality for the heat kernel.     

Hypercontractivity, Nash inequalities and subordination for classes of nonlinear semigroups

A suitable notion of hypercontractivity for a nonlinear semigroup {T _t } is shown to imply Nash-type inequalities for its generator H, provided a subhomogeneity property holds for the energy functional (u,Hu). We use this fact to prove that, for semigroups generated by operators of p-Laplacian-type, hypercontractivity implies ultracontractivity. Then we introduce the notion of subordinated nonlinear semigroups when the corresponding Bernstein function is f(x)=x ^α , and write an explicit formula for the associated generator. It is shown that hypercontractivity still holds for the subordinated semigroup and, hence, that Nash-type inequalities hold as well for the subordinated generator.     

The Atiyah-Jones conjecture for rational surfaces

We show that if the Atiyah-Jones conjecture holds for a surface X, then it also holds for the blow-up of X at a point. Since the conjecture is known to hold for P² and for ruled surfaces, it follows that the conjecture is true for all rational surfaces.     

Minimum cutsets for an element of a boolean lattice

An informative new proof is given for the theorem of Nowakowski that determines for all n and k the minimum size of a cutset for an element A with |A|=k of the Boolean algebra B _n of all subsets of {1,...,n}, ordered by inclusion. An inequality is obtained for cutsets for A that is reminiscent of Lubell's inequality for antichains in B _n. A new result that is provided by this approach is a list of all minimum cutsets for A.Research supported in part by NSF Grant DMS 87-01475.Research supported in part by NSF Grant DMS 86-06225 and Air Force OSR-86-0076.     

Genus polynomials and crosscap‐number polynomials for ring‐like graphs

An H‐linear graph is obtained by transforming a collection of copies of a fixed graph H into a chain. An H‐ring‐like graph is formed by binding the two end‐copies of H in such a chain to each other. Genus polynomials have been calculated for bindings of several kinds. In this paper, we substantially generalize the rules for constructing sequences of H‐ring‐like graphs from sequences of H‐linear graphs, and we give a general method for obtaining a recursion for the genus polynomials of the graphs in a sequence of ring‐like graphs. We use Chebyshev polynomials to obtain explicit formulas for the genus polynomials of several such sequences. We also give methods for obtaining recursions for partial genus polynomials and for crosscap‐number polynomials of a bar‐ring of a sequence of disjoint graphs.     

Torus quotients of homogeneous spaces — minimal dimensional Schubert varieties admitting semi-stable points

In this paper, for any simple, simply connected algebraic group G of type B,C or D and for any maximal parabolic subgroup P of G, we describe all minimal dimensional Schubert varieties in G/P admitting semistable points for the action of a maximal torus T with respect to an ample line bundle on G/P. We also describe, for any semi-simple simply connected algebraic group G and for any Borel subgroup B of G, all Coxeter elements τ for which the Schubert variety X(τ) admits a semistable point for the action of the torus T with respect to a non-trivial line bundle on G/B.     

Intermutation

This paper proves coherence results for categories with a natural transformation called intermutation made of arrows from (A ∧ B) ∨ (C ∧ D) to (A ∨ C) ∧ (B ∨ D), for ∧ and ∨ being two biendofunctors. Intermutation occurs in iterated, or n-fold, monoidal categories, which were introduced in connection with n-fold loop spaces, and for which a related, but different, coherence result was obtained previously by Balteanu, Fiedorowicz, Schw?nzl and Vogt. The results of the present paper strengthen up to a point this previous result, and show that two-fold loop spaces arise in the manner envisaged by these authors out of categories of a more general kind, which are not two-fold monoidal in their sense. In particular, some categories with finite products and coproducts are such. Coherence in Mac Lane’s “all diagrams commute” sense is proved here first for categories where for ∧ and ∨ one assumes only intermutation, and next for categories where one also assumes natural associativity isomorphisms. Coherence in the sense of coherence for symmetric monoidal categories is proved when one assumes moreover natural commutativity isomorphisms for ∧ and ∨. A restricted coherence result, involving a proviso of the kind found in coherence for symmetric monoidal closed categories, is proved in the presence of two nonisomorphic unit objects. The coherence conditions for intermutation and for the unit objects are derived from a unifying principle, which roughly speaking is about preservation of structures involving one endofunctor by another endofunctor, up to a natural transformation that is not an isomorphism. This is related to weakening the notion of monoidal functor. A similar, but less symmetric, justification for intermutation was envisaged in connection with iterated monoidal categories. Unlike the assumptions previously introduced for two-fold monoidal categories, the assumptions for the unit objects of the categories of this paper, which are more general, allow an interpretation in logic.     

Anomalous behaviour for the random corrections to the cumulants of random walks in fluctuating random media

The Central Limit Theorem for a model of discrete-time random walks on the lattice ℤ^ν in a fluctuating random environment was proved for almost-all realizations of the space-time nvironment, for all ν > 1 in [BMP1] and for all ν≥ 1 in [BBMP]. In [BMP1] it was proved that the random correction to the average of the random walk for ν≥ 3 is finite. In the present paper we consider the cases ν = 1,2 and prove the Central Limit Theorem as T→∞ for the random correction to the first two cumulants. The rescaling factor for theaverage is for ν = 1 and (ln T), for ν=2; for the covariance it is , ν = 1,2. Received: 25 November 1999 / Revised version: 7 June 2000 / Published online: 15 February 2001     

The Galerkin scheme for Lavrentiev’sm-times iterated method to solve linear accretive Volterra integral equations of the first kind

In this paper, for the numerical solution of linear accretive Volterra integral equations of the first kind in Hilbert spaces we consider the Galerkin scheme for Lavrentiev’sm-times iterated method, i.e., for each parameter choice for Lavrentiev’sm-times iterated method the arisingm stabilized equations are discretized by the Galerkin scheme. An associated discrepancy principle as parameter choice strategy for this finite-dimensional version of Lavrentiev’sm-times iterated method is proposed, and corresponding convergence results are provided.     

Arithmetic properties of similitude theta lifts from orthogonal to symplectic groups

Adapting the work of Kudla and Millson we obtain a lifting of cuspidal cohomology classes for the symmetric space associated to GO(V) for an indefinite rational quadratic space V of even dimension to holomorphic Siegel modular forms on GSp _n (A). For n =  2 we prove the Thom Lemma for hyperbolic 3-space, which together with results of Kudla and Millson imply an interpretation of the Fourier coefficients of the theta lift as period integrals of the cohomology class over certain cycles, and relates those over infinite geodesics to L-values of cusp forms for GL₂ over imaginary quadratic fields. This allows us to prove, for almost all primes p, the p-integrality of the lift for a particular choice of Schwartz function. We further calculate the Hecke eigenvalues (including for some “bad” places) for this choice in the case of V of signature (3,1).     

Distribution of Wilks' likelihood-ratio criterion in the complex case

Summary The null distribution of Wilks' likelihood ratio criterian, Λ, in the complex case, is obtained, and explicit expressions for the same are given forp=2 and 3, wherep is the number of variables. It is shown that unlike the real case the distributions derived have closed form representation for allp and for allf ₂, the hypothesis degree of freedom. Tables of correction factors for converting chi-square percentiles to exact percentiles of a logarithmic function of Λ are provided for fourteen (p, f ₂) pairs. Tables for an additional thirteen pairs can be obtained from those tabulated by interchangingp andf ₂. This research was supported (in part) by the National Science Foundation under Grant Number GU-15-34. Reproduction in whole or in part is permitted for any purpose of the United States Government.     

Some applications of Montgomery's sieve

Artin has conjectured that every positive integer not a perfect square is a primitive root for some odd prime. A new estimate is obtained for the number of integers in the interval [M + 1, M + N] which are not primitive roots for any odd prime, improving on a theorem of Gallagher.Erd?s has conjectured that 7, 15, 21, 45, 75, and 105 are the only values of the positive integer n for which n ? 2^k is prime for every k with 1 ≤ k ≤ log₂n. An estimate is proved for the number of such n ≤ N.