Distribution of Eigenvalues of Highly Palindromic Toeplitz Matrices

Consider the ensemble of real symmetric Toeplitz matrices whose entries are i.i.d. random variables chosen from a fixed probability distribution p of mean 0, variance 1, and finite higher moments. Previous work (Bryc et al., Ann. Probab. 34(1):1–38, 2006; Hammond and Miller, J. Theor. Probab. 18(3):537–566, 2005) showed that the spectral measures (the density of normalized eigenvalues) converge almost surely to a universal distribution almost that of the Gaussian, independent of p. The deficit from the Gaussian distribution is due to obstructions to solutions of Diophantine equations and can be removed (see Massey et al., J. Theor. Probab. 20(3):637–662, 2007) by making the first row palindromic. In this paper we study the case where there is more than one palindrome in the first row of real symmetric Toeplitz matrices. Using the method of moments and an analysis of the resulting Diophantine equations, we show that the spectral measures converge almost surely to a universal distribution. Assuming a conjecture on the resulting Diophantine sums (which is supported by numerics and some theoretical arguments), we prove that the limiting distribution has a fatter tail than any previously seen limiting spectral measure.     

Orbital stability of spherical galactic models

We consider the three dimensional gravitational Vlasov Poisson system which is a canonical model in astrophysics to describe the dynamics of galactic clusters. A well known conjecture (Binney, Tremaine in Galactic Dynamics, Princeton University Press, Princeton, 1987) is the stability of spherical models which are nonincreasing radially symmetric steady states solutions. This conjecture was proved at the linear level by several authors in the continuation of the breakthrough work by Antonov (Sov. Astron. 4:859–867, 1961). In the previous work (Lemou et al. in A new variational approach to the stability of gravitational systems, submitted, 2011), we derived the stability of anisotropic models under spherically symmetric perturbations using fundamental monotonicity properties of the Hamiltonian under suitable generalized symmetric rearrangements first observed in the physics literature (Lynden-Bell in Mon. Not. R. Astron. Soc. 144:189–217, 1969; Gardner in Phys. Fluids 6:839–840, 1963; Wiechen et al. in Mon. Not. R. Astron. Soc. 223:623–646, 1988; Aly in Mon. Not. R. Astron. Soc. 241:15, 1989). In this work, we show how this approach combined with a new generalized Antonov type coercivity property implies the orbital stability of spherical models under general perturbations.     

A note on meromorphic functions that share a set with their derivatives

In this paper, we study a problem of meromorphic functions that share an arbitrary set having three elements with their derivatives. A uniqueness result is derived which is an improvement of some related theorems given by Fang and Zalcman (J. Math. Anal. Appl. 280 (2003), 273–283) and Chang, Fang, and Zalcman (Arch. Math. 89 (2007), 561–569). As an application, we generalize the famous Brück conjecture with the idea of sharing a set.     

Concavity of the conditional mean sojourn time in the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/1 processor-sharing queue with batch arrivals

Avrachenkov et al. (Queueing Syst. 50:459–480, [2005]) conjectured that in an M/G/1 processor-sharing queue with batch arrivals, the conditional mean sojourn time is concave. In this paper, we show that this conjecture is generally not true. This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2006-312-C00470).     

Time-dependent properties of symmetric queues

We settle a conjecture of Kella et al. (J. Appl. Probab. 42:223–234, 2005): the distribution of the number of jobs in the system of a symmetric M/G/1 queue at a fixed time is independent of the service discipline if the system starts empty. Our derivations are based on a time-reversal argument for regenerative processes and a connection with a clearing model.     

A note on spectrum analysis of augmentation block Schur complement preconditioners

In this note, as a generalization of the preconditioner presented by Greif et al. (SIAM J Matrix Anal Appl 27:779–792, 2006), we consider a set of augmentation block Schur complement preconditioners for solving saddle point systems whose coefficient matrices have singular (1,1) blocks. The spectral properties of the preconditioned matrices are analyzed and an optimal preconditioner is derived.     

The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic

We establish the inverse conjecture for the Gowers norm over finite fields, which asserts (roughly speaking) that if a bounded function f : V ? \mathbbC{f : V \rightarrow \mathbb{C}} on a finite-dimensional vector space V over a finite field \mathbbF{\mathbb{F}} has large Gowers uniformity norm ||f||_U^s+1(V){{\parallel{f}\parallel_{U^{s+1}(V)}}} , then there exists a (non-classical) polynomial P: V ? \mathbbT{P: V \rightarrow \mathbb{T}} of degree at most s such that f correlates with the phase e(P) = e ^2πiP . This conjecture had already been established in the “high characteristic case”, when the characteristic of \mathbbF{\mathbb{F}} is at least as large as s. Our proof relies on the weak form of the inverse conjecture established earlier by the authors and Bergelson [3], together with new results on the structure and equidistribution of non-classical polynomials, in the spirit of the work of Green and the first author [22] and of Kaufman and Lovett [28].     

Fixed-point-free elements in <Emphasis Type="Italic">p</Emphasis>-groups

In this paper we prove that there exists no function F(m, p) (where the first argument is an integer and the second a prime) such that, if G is a finite permutation p-group with m orbits, each of size at least p ^F(m,p), then G contains a fixed-point-free element. In particular, this gives an answer to a conjecture of Peter Cameron; see [4], [6].     

The critical exponent conjecture for powers of doubly nonnegative matrices

Doubly nonnegative matrices arise naturally in many setting including Markov random fields (positively banded graphical models) and in the convergence analysis of Markov chains. In this short note, we settle a recent conjecture by C.R. Johnson et al. [Charles R. Johnson, Brian Lins, Olivia Walch, The critical exponent for continuous conventional powers of doubly nonnegative matrices, Linear Algebra Appl. 435 (9) (2011) 2175–2182] by proving that the critical exponent beyond which all continuous conventional powers of n-by-n   doubly nonnegative matrices are doubly nonnegative is exactly n−2$n-2$. We show that the conjecture follows immediately by applying a general characterization from the literature. We prove a stronger form of the conjecture by classifying all powers preserving doubly nonnegative matrices, and proceed to generalize the conjecture for broad classes of functions. We also provide different approaches for settling the original conjecture.     

Serre’s modularity conjecture (II)

This paper is the first part of a work which proves Serre’s modularity conjecture. We first prove the cases p 1 2p\not=2 and odd conductor, and p=2 and weight 2, see Theorem 1.2, modulo Theorems 4.1 and 5.1. Theorems 4.1 and 5.1 are proven in the second part, see Khare and Wintenberger (Invent. Math., doi:, 2009). We then reduce the general case to a modularity statement for 2-adic lifts of modular mod 2 representations. This statement is now a theorem of Kisin (Invent. Math., doi:, 2009).     

Random Block Matrices and Matrix Orthogonal Polynomials

In this paper we consider random block matrices, which generalize the general beta ensembles recently investigated by Dumitriu and Edelmann (J. Math. Phys. 43:5830–5847, 2002; Ann. Inst. Poincaré Probab. Stat. 41:1083–1099, 2005). We demonstrate that the eigenvalues of these random matrices can be uniformly approximated by roots of matrix orthogonal polynomials which were investigated independently from the random matrix literature. As a consequence, we derive the asymptotic spectral distribution of these matrices. The limit distribution has a density which can be represented as the trace of an integral of densities of matrix measures corresponding to the Chebyshev matrix polynomials of the first kind. Our results establish a new relation between the theory of random block matrices and the field of matrix orthogonal polynomials, which have not been explored so far in the literature.     

An inductive approach to Coxeter arrangements and Solomon’s descent algebra

In our recent paper (Douglass et al. (2011)), we claimed that both the group algebra of a finite Coxeter group W as well as the Orlik–Solomon algebra of W can be decomposed into a sum of induced one-dimensional representations of centralizers, one for each conjugacy class of elements of W, and gave a uniform proof of this claim for symmetric groups. In this note, we outline an inductive approach to our conjecture. As an application of this method, we prove the inductive version of the conjecture for finite Coxeter groups of rank up to 2.     

Turyn type Williamson matrices up to order 99

In 2008 Holzmann et al. introduced a new algorithm to search for symmetric circulant Williamson matrices. We adapted the algorithm for Turyn type Williamson matrices. For each order up to 99 where Turyn type Williamson matrices exist our computer search found, up to equivalence, exactly one such matrix.     

The Limiting Spectra of Girko’s Block-Matrix

To analyze the limiting spectral distribution of some random block-matrices, Girko (Random Oper. Stoch. Equ. 8(2), 189–194, 2000) uses a system of canonical equations from (An Introduction to Statistical Analysis of Random Arrays. VSP, Utrecht, 1998). In this paper, we use the method of moments to give an integral form for the almost sure limiting spectral distribution of such matrices.     

Throughput maximization for two station tandem systems: a proof of the Andradóttir–Ayhan conjecture

We study a tandem queueing network with two stations, M heterogeneous flexible servers, and a finite intermediate buffer. The objective is to dynamically assign the servers to the stations in order to maximize the throughput of the system. The form of the optimal policy for M≤3 was derived in two previous papers. In one of those papers, Andradóttir and Ayhan (Operations Research 53:516–531, 2005) provide a conjecture on the form of the optimal policy for M≥4. We prove their conjecture in this paper, showing that the optimal policy is defined by monotone thresholds and the ratios of the service rates among the servers. For M>1, we also prove that the optimal policy always uses the entire intermediate buffer.     

Numerical aspects of computing the Moore-Penrose inverse of full column rank matrices

This paper presents a comparison of certain direct algorithms for computing the Moore-Penrose inverse, for matrices of full column rank, from the point of view of numerical stability. It is proved that the algorithm using Householder QR decomposition, implemented in floating point arithmetic, is forward stable but only conditionally mixed forward-backward stable. A similar result holds also for the Classical Gram-Schmidt algorithm with reorthogonalization (CGS2). This algorithm was developed and analyzed by Abdelmalek (BIT, 11(4):354–367, 1971) and its detailed error analysis was given in Giraud et al. (Numer. Math. 101(1):87–100, 2005).     

Asymmetry of Convex Polytopes and Vertex Index of Symmetric Convex Bodies

In (Gluskin, Litvak in Geom. Dedicate 90:45–48, [2002]) it was shown that a polytope with few vertices is far from being symmetric in the Banach–Mazur distance. More precisely, it was shown that Banach–Mazur distance between such a polytope and any symmetric convex body is large. In this note we introduce a new, averaging-type parameter to measure the asymmetry of polytopes. It turns out that, surprisingly, this new parameter is still very large, in fact it satisfies the same lower bound as the Banach–Mazur distance. In a sense it shows the following phenomenon: if a convex polytope with small number of vertices is as close to a symmetric body as it can be, then most of its vertices are as bad as the worst one. We apply our results to provide a lower estimate on the vertex index of a symmetric convex body, which was recently introduced in (Bezdek, Litvak in Adv. Math. 215:626–641, [2007]). Furthermore, we give the affirmative answer to a conjecture by Bezdek (Period. Math. Hung. 53:59–69, [2006]) on the quantitative illumination problem.     

Simply connected projective manifolds in characteristic p>0 have no nontrivial stratified bundles

We show that simply connected projective manifolds in characteristic p>0 have no nontrivial stratified bundles. This gives a positive answer to a conjecture by D. Gieseker (Ann. Sc. Norm. Super. Pisa, 4 Sér. 2(1):1–31, 1975). The proof uses Hrushovski’s theorem on periodic points.     

New subclasses of block H-matrices with applications to parallel decomposition-type relaxation methods

The parallel decomposition-type relaxation methods for solving large sparse systems of linear equations on SIMD multiprocessor systems have been proposed in [3] and [2]. In case when the coefficient matrix of the linear system is a block -matrix, sufficient conditions for the convergence of methods given in [2], [3] have been further improved in [5] and [4]. From the practical point of view, the convergence area obtained there is not always suitable for computation, so we propose new, easily computable ones, for some special subclasses of block -matrices. Furthermore, this approach improves the already known convergence area for the class of block strictly diagonally dominant (SDD) matrices.