Tail asymptotics of the waiting time and the busy period for the {{\varvec{M/G/1/K}}} queues with subexponential service times

We study the asymptotic behavior of the tail probabilities of the waiting time and the busy period for the $M/G/1/K$ queues with subexponential service times under three different service disciplines: FCFS, LCFS, and ROS. Under the FCFS discipline, the result on the waiting time is proved for the more general $GI/G/1/K$ queue with subexponential service times and lighter interarrival times. Using the well-known Laplace–Stieltjes transform (LST) expressions for the probability distribution of the busy period of the $M/G/1/K$ queue, we decompose the busy period into a sum of a random number of independent random variables. The result is used to obtain the tail asymptotics for the waiting time distributions under the LCFS and ROS disciplines.     

Counting nonsingular matrices with primitive row vectors

We give an asymptotic expression for the number of nonsingular integer $n\times n$ -matrices with primitive row vectors, determinant $k$ , and Euclidean matrix norm less than $T$ , as $T\rightarrow \infty $ . We also investigate the density of matrices with primitive rows in the space of matrices with determinant $k$ , and determine its asymptotics for large $k$ .     

On adding a variable to a Frobenius manifold and generalizations

Let $\pi :V\rightarrow M$ be a (real or holomorphic) vector bundle whose base has an almost Frobenius structure $(\circ _{M},e_{M},g_{M})$ and typical fiber has the structure of a Frobenius algebra $(\circ _{V},e_{V},g_{V})$ . Using a connection $D$ on the bundle $\pi : V{\,\rightarrow \,}M$ and a morphism $\alpha :V\rightarrow TM$ , we construct an almost Frobenius structure $(\circ , e_{V},g)$ on the manifold $V$ and we study when it is Frobenius. In particular, we describe all (real) positive definite Frobenius structures on $V$ obtained in this way, when $M$ is a semisimple Frobenius manifold with non-vanishing rotation coefficients. In the holomorphic setting, we add a real structure $k_{M}$ on $M$ and a real structure $k_{V}$ on the bundle $\pi : V \rightarrow M$ . Using $k_{M}$ , $k_{V}$ and $D$ we define a real structure $k$ on the manifold $V$ . We study when $k$ , together with an almost Frobenius structure $(\circ , e_{V}, g) $ , satisfies the tt*- equations. Along the way, we prove various properties of adding variables to a Frobenius manifold, in connection with Legendre transformations and $tt^{*}$ -geometry.     

Free subalgebras of division algebras over uncountable fields

We study the existence of free subalgebras in division algebras, and prove the following general result: if $A$ is a noetherian domain which is countably generated over an uncountable algebraically closed field $k$ of characteristic $0$ , then either the quotient division algebra of $A$ contains a free algebra on two generators, or it is left algebraic over every maximal subfield. As an application, we prove that if $k$ is an uncountable algebraically closed field and $A$ is a finitely generated $k$ -algebra that is a domain of GK-dimension strictly less than $3$ , then either $A$ satisfies a polynomial identity, or the quotient division algebra of $A$ contains a free $k$ -algebra on two generators.     

Elliptic equations with jumping nonlinearities involving high eigenvalues

We present some multiplicity results concerning semilinear elliptic Dirichlet problems with jumping nonlinearities where the jumping condition involves a set of high eigenvalues not including the first one. Using a variational method we show that the number of solutions may be arbitrarily large provided the number of jumped eigenvalues is large enough. Indeed, we prove that for every positive integer $k$ there exists a positive integer $n(k)$ such that, if the number of jumped eigenvalues is greater than $n(k),$ then the problem has at least a solution which presents $k$ peaks. Moreover, we describe the asymptotic behaviour of the solutions as the number of jumped eigenvalues tends to infinity; in particular, we analyse some concentration phenomena of the peaks (near points or suitable manifolds), we describe the asymptotic profile of the rescaled peaks, etc $\ldots $      

Existence of immersed spheres minimizing curvature functionals in compact 3-manifolds

We study curvature functionals for immersed 2-spheres in a compact, three-dimensional Riemannian manifold $M$ . Under the assumption that the sectional curvature $K^M$ is strictly positive, we prove the existence of a smooth immersion $f:{\mathbb {S}}^2 \rightarrow M$ minimizing the $L^2$ integral of the second fundamental form. Assuming instead that $K^M \le 2$ and that there is some point $\overline{x} \in M$ with scalar curvature $R^M(\overline{x}) > 6$ , we obtain a smooth minimizer $f:{\mathbb {S}}^2 \rightarrow M$ for the functional $\int \frac{1}{4}|H|^2+1$ , where $H$ is the mean curvature.     

Highly Incident Configurations with Chiral Symmetry

A geometric $k$ -configuration is a collection of points and straight lines in the plane so that $k$ points lie on each line and $k$ lines pass through this point. We introduce a new construction method for constructing $k$ -configurations with non-trivial dihedral or chiral (i.e., purely rotational) symmetry, for any $k \ge 3$ ; the configurations produced have $2^{k-2}$ symmetry classes of points and lines. The construction method produces the only known infinite class of symmetric geometric 7-configurations, the second known infinite class of symmetric geometric 6-configurations, and the only known 6-configurations with chiral symmetry.     

An Index Formula in Connection with Meromorphic Approximation

Let $\Phi $ be a continuous $n\times n$ matrix-valued function on the unit circle $\mathbb T $ such that the $(k-1)$ st singular value of the Hankel operator with symbol $\Phi $ is greater than the $k$ th singular value. In this case, it is well-known that $\Phi $ has a unique superoptimal meromorphic approximant $Q$ in $H^{\infty }_{(k)}$ ; that is, $Q$ has at most $k$ poles in the unit disc $\mathbb D $ (in the sense that the McMillan degree of $Q$ in $\mathbb D $ is at most $k$ ) and $Q$ minimizes the essential suprema of singular values $s_{j}\left((\Phi -Q)(\zeta )\right)\!, j\ge 0$ , with respect to the lexicographic ordering. For each $j\ge 0$ , the essential supremum of $s_{j}\left((\Phi -Q)(\zeta )\right)$ is called the $j$ th superoptimal singular value of degree $k$ of $\Phi $ . We prove that if $\Phi $ has $n$ non-zero superoptimal singular values of degree $k$ , then the Toeplitz operator $T_{\Phi -Q}$ with symbol $\Phi -Q$ is Fredholm and has index $$ \mathrm{ind}T_{\Phi -Q}=\dim \ker T_{\Phi -Q}=2k+\dim \mathcal E , $$ where $\mathcal E =\{ \xi \in \ker H_{Q}: \Vert H_{\Phi }\xi \Vert _{2}=\Vert (\Phi -Q)\xi \Vert _{2}\}$ and $H_{\Phi }$ denotes the Hankel operator with symbol $\Phi $ . This result can in fact be extended from continuous matrix-valued functions to the wider class of $k$ -admissible matrix-valued functions, i.e. essentially bounded $n\times n$ matrix-valued functions $\Phi $ on $\mathbb T $ for which the essential norm of the Hankel operator $H_{\Phi }$ is strictly less than the smallest non-zero superoptimal singular value of degree $k$ of $\Phi $ .     

Passage time from four to two blocks of opinions in the voter model and walks in the quarter plane

A random walk in $\mathbf{Z}_+^2$ spatially homogeneous in the interior, absorbed at the axes, starting from an arbitrary point $(i_0,j_0)$ and with step probabilities drawn on Fig. 1 is considered. The trivariate generating function of probabilities that the random walk hits a given point $(i,j) \in \mathbf{Z}_+^2 $ at a given time $k\ge 0$ is made explicit. Probabilities of absorption at a given time $k$ and at a given axis are found, and their precise asymptotic is derived as the time $k\rightarrow \infty $ . The equivalence of two typical ways of conditioning this random walk to never reach the axes is established. The results are also applied to the analysis of the voter model with two candidates and initially, in the population $\mathbf{Z}$ , four connected blocks of same opinions. Then, a citizen changes his mind at a rate proportional to the number of his neighbors that disagree with him. Namely, the passage from four to two blocks of opinions is studied.     

Approximation algorithms for k-partitioning problems with partition matroid constraint

The $k$ -partitioning problem with partition matroid constraint is to partition the union of $k$ given sets of size $m$ into $m$ sets such that each set contains exactly one element from each given set. With the objective of minimizing the maximum load, we present an efficient polynomial time approximation scheme (EPTAS) for the case where $k$ is a constant and a full polynomial time approximation scheme (FPTAS) for the case where $m$ is a constant; with the objective of maximizing the minimum load, we present a $\frac{1}{k-1}$ -approximation algorithm for the general case, an EPTAS for the case where $k$ is a constant; with the objective of minimizing the $l_p$ -norm of the load vector, we prove that the layered LPT algorithm (Wu and Yao in Theor Comput Sci 374:41–48, 2007) is an all-norm 2-approximation algorithm.     

Subsets of full measure in a generic submanifold in \mathbb C ^n are non-plurithin

In this paper we prove that if $I\subset M $ is a subset of measure $0$ in a $C^2$ -smooth generic submanifold $M \subset \mathbb C ^n$ , then $M \setminus I$ is non-plurithin at each point of $M$ in $\mathbb C ^n$ . This result improves a previous result of A. Edigarian and J. Wiegerinck who considered the case where $I$ is pluripolar set contained in a $C^1$ -smooth generic submanifold $M \subset \mathbb C ^n$ (Edigarian and Wiegernick in Math. Z. 266(2):393–398, 2010). The proof of our result is essentially different.     

L’espace symétrique de Drinfeld et correspondance de Langlands locale I

We give an upper bound of a Hamiltonian displacement energy of a unit disk cotangent bundle $D^*M$ in a cotangent bundle $T^*M$ , when the base manifold $M$ is an open Riemannian manifold. Our main result is that the displacement energy is not greater than $C r(M)$ , where $r(M)$ is the inner radius of $M$ , and $C$ is a dimensional constant. As an immediate application, we study symplectic embedding problems of unit disk cotangent bundles. Moreover, combined with results in symplectic geometry, our main result shows the existence of short periodic billiard trajectories and short geodesic loops.     

Stationary analysis of the shortest queue first service policy

We analyze the so-called shortest queue first (SQF) queueing discipline whereby a unique server addresses queues in parallel by serving at any time, the queue with the smallest workload. Considering a stationary system composed of two parallel queues and assuming Poisson arrivals and general service time distributions, we first establish the functional equations satisfied by the Laplace transforms of the workloads in each queue. We further specialize these equations to the so-called “symmetric case,” with same arrival rates and identical exponential service time distributions at each queue; we then obtain a functional equation $$\begin{aligned} M(z) = q(z) \cdot M \circ h(z) + L(z) \end{aligned}$$ for unknown function M, where given functions \(q, L\) , and \(h\) are related to one branch of a cubic polynomial equation. We study the analyticity domain of function M and express it by a series expansion involving all iterates of function \(h\) . This allows us to determine empty queue probabilities along with the tail of the workload distribution in each queue. This tail appears to be identical to that of the head-of-line preemptive priority system, which is the key feature desired for the SQF discipline.     

Integer-valued polynomials over matrices and divided differences

Let $D$ be an integrally closed domain with quotient field $K$ and $n$ a positive integer. We give a characterization of the polynomials in $K[X]$ which are integer-valued over the set of matrices $M_n(D)$ in terms of their divided differences. A necessary and sufficient condition on $f\in K[X]$ to be integer-valued over $M_n(D)$ is that, for each $k$ less than $n$ , the $k$ th divided difference of $f$ is integral-valued on every subset of the roots of any monic polynomial over $D$ of degree $n$ . If in addition $D$ has zero Jacobson radical then it is sufficient to check the above conditions on subsets of the roots of monic irreducible polynomials of degree $n$ , that is, conjugate integral elements of degree $n$ over $D$ .     

Convex optimization for the planted k-disjoint-clique problem

We consider the $k$ -disjoint-clique problem. The input is an undirected graph $G$ in which the nodes represent data items, and edges indicate a similarity between the corresponding items. The problem is to find within the graph $k$ disjoint cliques that cover the maximum number of nodes of $G$ . This problem may be understood as a general way to pose the classical ‘clustering’ problem. In clustering, one is given data items and a distance function, and one wishes to partition the data into disjoint clusters of data items, such that the items in each cluster are close to each other. Our formulation additionally allows ‘noise’ nodes to be present in the input data that are not part of any of the cliques. The $k$ -disjoint-clique problem is NP-hard, but we show that a convex relaxation can solve it in polynomial time for input instances constructed in a certain way. The input instances for which our algorithm finds the optimal solution consist of $k$ disjoint large cliques (called ‘planted cliques’) that are then obscured by noise edges inserted either at random or by an adversary, as well as additional nodes not belonging to any of the $k$ planted cliques.     

Variance asymptotics for random polytopes in smooth convex bodies

Let $K \subset \mathbb R ^d$ be a smooth convex set and let $\mathcal{P }_{\lambda }$ be a Poisson point process on $\mathbb R ^d$ of intensity ${\lambda }$ . The convex hull of $\mathcal{P }_{\lambda }\cap K$ is a random convex polytope $K_{\lambda }$ . As ${\lambda }\rightarrow \infty $ , we show that the variance of the number of $k$ -dimensional faces of $K_{\lambda }$ , when properly scaled, converges to a scalar multiple of the affine surface area of $K$ . Similar asymptotics hold for the variance of the number of $k$ -dimensional faces for the convex hull of a binomial process in $K$ .     

Polytopal Affine Semigroups with Holes Deep Inside

Given a positive integer $k$ k , we construct a lattice $3$ 3 -simplex $P$ P with the following property: The affine semigroup $Q_P$ Q P associated to $P$ P is not normal, and every element $q \in \overline{Q}_P \setminus Q_P$ q ∈ Q ¯ P ? Q P has lattice distance at least $k$ k above every facet of $Q_P$ Q P .     

Nearby motives and motivic nearby cycles

We prove that the construction of motivic nearby cycles, introduced by Jan Denef and François Loeser, is compatible with the formalism of nearby motives, developed by Joseph Ayoub. Let $k$ be an arbitrary field of characteristic zero, and let $X$ be a smooth quasi-projective $k$ -scheme. Precisely, we show that, in the Grothendieck group of constructible étale motives, the image of the nearby motive associated with a flat morphism of $k$ -schemes $f:X\rightarrow \mathbb A ^1_k$ , in the sense of Ayoub’s theory, can be identified with the image of Denef and Loeser’s motivic nearby cycles associated with $f$ . In particular, it provides a realization of the motivic Milnor fiber of $f$ in the “non-virtual” motivic world.     

Contact structures on M \times S^2

We show that if a manifold $M$ admits a contact structure, then so does $M \times S^2$ . Our proof relies on surgery theory, a theorem of Eliashberg on contact surgery and a theorem of Bourgeois showing that if $M$ admits a contact structure then so does $M \times T^2$ .