The Busemann-Petty problem in hyperbolic and spherical spaces

The Busemann-Petty problem asks whether origin-symmetric convex bodies in Rⁿ with smaller central hyperplane sections necessarily have smaller n-dimensional volume. It is known that the answer to this problem is affirmative if n?4 and negative if n?5. We study this problem in hyperbolic and spherical spaces.     

Comparison of volumes of convex bodies in real, complex, and quaternionic spaces

The classical Busemann-Petty problem (1956) asks, whether origin-symmetric convex bodies in Rn with smaller hyperplane central sections necessarily have smaller volumes. It is known, that the answer is affirmative if n?4 and negative if n>4. The same question can be asked when volumes of hyperplane sections are replaced by other comparison functions having geometric meaning. We give unified analysis of this circle of problems in real, complex, and quaternionic n-dimensional spaces. All cases are treated simultaneously. In particular, we show that the Busemann-Petty problem in the quaternionic n-dimensional space has an affirmative answer if and only if n=2. The method relies on the properties of cosine transforms on the unit sphere. We discuss possible generalizations.     

Cycles in bipartite tournaments

It is shown that if an oriented complete bipartite graph has a directed cycle of length 2n, then it has directed cycles of all smaller even lengths unless n is even and the 2n-cycle induces one special digraph.     

Short cycles of Poncelet’s conics

Main results of this paper are the following:1. A closed N-gon interscribed between two conics exists if and only if a specially constructed polygon with a smaller number of sides (n) is closed. To verify the closure of this n-gon, we need to find a periodic solution of a dynamical system of order n. The proof is based on the connection of Poncelet’s curves and matrices that admit unitary bordering [4,9,10,16]. Application of this criterion makes sense when n?N, in particular when n≈log₂N (see Table 4 where n=m₁). So for example we may say that a polygon with 2049 sides interscribed between two circles is closed if and only if some specially constructed 11-gon is closed.2. A closed N-gon interscribed between two confocal ellipses (the billiard case) exists if and only if an N-gon interscribed between two special nested circles is closed.     

The Busemann-Petty problem via spherical harmonics

The Busemann-Petty problem asks whether symmetric convex bodies in with smaller central hyperplane sections necessarily have smaller n-dimensional volume. The solution has recently been completed, and the answer is affirmative if n?4 and negative if n?5. In this article we present a short proof of the affirmative result and its generalization using the Funk-Hecke formula for spherical harmonics.     

Extreme positive operators on minimal and almost minimal cones

Fiedler and Pták called a cone minimal if it is n-dimensional and has n+1 extremal rays. We call a cone almost minimal if it is n-dimensional and has n+2 extremal rays. Duality properties stemming from the use of Gale pairs lead to a general technique for identifying the extreme cone-preserving (positive) operators between polyhedral cones. This technique is most effective for cones with dimension not much smaller than the number of their extreme rays. In particular, the Fiedler-Pták characterization of extreme positive operators between minimal cones is extended to the following cases: (i) operators from a minimal cone to an arbitrary polyhedral cone, (ii) operators from an almost minimal cone to a minimal cone.     

Assignment and scheduling in parallel matrix factorization

We consider the problem of factoring a dense n×n matrix on a network consisting of P MIMD processors, with no shared memory, when the network is smaller than the number of elements in the matrix (P<n²). The specific example analyzed is a computational network that arises in computing the LU, QR, or Cholesky factorizations. We prove that if the nodes of the network are evenly distributed among processors and if computations are scheduled by a round-robin or a least-recently-executed scheduling algorithm, then optimal order of speedup is achieved. However, such speedup is not necessarily achieved for other scheduling algorithms or if the computation for the nodes is inappropriately split across processors, and we give examples of these phenomena. Lower bounds on execution time for the algorithm are established for two important node-assignment strategies.     

Latin squares and superqueens

Let L be a Latin square of order n with entries from {0, 1,…, n ? 1}. In addition, L is said to have the (n, k) property if, in each right or left wrap around diagonal, the number of cells with entries smaller than k is exactly k. It is established that a necessary and sufficient condition for the existence of Latin squares having the (n, k) property is that of (2|n ? 2| k) and (3|n ? 3| k). Also, these Latin squares are related to a problem of placing nonattacking queens on a toroidal chessboard.     

The standard factorization of Lyndon words: an average point of view

A non-empty word w is a Lyndon word if and only if it is strictly smaller for the lexicographical order than any of its proper suffixes. Such a word w is either a letter or admits a standard factorization uv where v is its smallest proper suffix. For any Lyndon word v, we show that the set of Lyndon words having v as right factor of the standard factorization is regular and compute explicitly the associated generating function. Next, considering the Lyndon words of length n over a two-letter alphabet, we establish that, for the uniform distribution, the average length of the right factor v of the standard factorization is asymptotically 3n/4.     

Numerical enclosure for each eigenvalue in generalized eigenvalue problem

An algorithm for enclosing all eigenvalues in generalized eigenvalue problem Ax=λBx is proposed. This algorithm is applicable even if A∈C^n×n is not Hermitian and/or B∈C^n×n is not Hermitian positive definite, and supplies nerror bounds while the algorithm previously developed by the author supplies a single error bound. It is proved that the error bounds obtained by the proposed algorithm are equal or smaller than that by the previous algorithm. Computational cost for the proposed algorithm is similar to that for the previous algorithm. Numerical results show the property of the proposed algorithm.     

Hyperbolic manifolds,amalgamated products and critical exponents

We give a new proof of a result due to Y. Shalom: if the fundamental group of a compact real hyperbolic manifold of dimn is a free product of its subgroups A and B over the amalgamated subgroup C, then the critical exponent of C is not smaller than n?2. The proof, which is geometric, allows one to treat the equality case and an extension to variable curvature. To cite this article: G. Besson et al., C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Hermitian pencils with a cubic minimal polynomial

Let A be an n × n complex matrix and write A = H + iK, where H and K are Hermitian matrices. We show that if the minimal polynomial of the pencil xH + yK has degree 3, then there is a unitary matrix U such that U^-1AU is block diagonal with blocks of size 3 × 3 or smaller. This is a special case of a conjecture made by Kippenhahn in 1951.     

(n,d)-Injective covers,n-coherent rings,and (n,d)-rings

It is known that a ring R is left Noetherian if and only if every left R-module has an injective (pre)cover. We show that (1) if R is a right n-coherent ring, then every right R-module has an (n, d)-injective (pre)cover; (2) if R is a ring such that every (n, 0)-injective right R-module is n-pure extending, and if every right R-module has an (n, 0)-injective cover, then R is right n-coherent. As applications of these results, we give some characterizations of (n, d)-rings, von Neumann regular rings and semisimple rings.     

A matrix of permanents

If A is a matrix of order n×(n?2), n?3, denote by ā the n×n matrix whose (i,j)th entry is zero if i=j, and if i≠j, is the permanent of the submatrix of A obtained by deleting its ith and jth rows. It is shown that if A is a nonnegative n×(n?2) matrix, then ā is nonsingular if and only if A has no zero submatrix of n?1 lines. This is used to give precise consequences of the occurrence of equality in Alexandroff's inequality.     

On the modular sumset partition problem

A sequence m₁≥m₂≥?≥m_k of k positive integers isn-realizable if there is a partition X₁,X₂,…,X_k of the integer interval [1,n] such that the sum of the elements in X_i is m_i for each i=1,2,…,k. We consider the modular version of the problem and, by using the polynomial method by Alon (1999) [2], we prove that all sequences in Z/pZ of length k≤(p−1)/2 are realizable for any prime p≥3. The bound on k is best possible. An extension of this result is applied to give two results of p-realizable sequences in the integers. The first one is an extension, for n a prime, of the best known sufficient condition for n-realizability. The second one shows that, for n≥(4k)³, an n-feasible sequence of length k isn-realizable if and only if it does not contain forbidden subsequences of elements smaller than n, a natural obstruction forn-realizability.     

A joint similarity problem for n-tuples of operators on vector-valued Bergman spaces

We investigate n-tuples of commuting Foias-Williams/Peller type operators acting on vector-valued weighted Bergman spaces. We prove that a commuting n-tuple of such operators is jointly (completely) polynomially bounded if and only if it is similar to an n-tuple of contractions, if and only if each of the n operators is polynomially bounded.     

Real eigenvalues of nonnegative matrices which commute with a symmetric matrix involution

It is well known that if P is a nonnegative matrix, then its spectral radius is an eigenvalue of P (Perron-Frobenius theorem). In this paper it is shown that if P is an n × n nonnegative matrix and it commutes with a nonnegative symmetric involution when n=4m+3, then (1) P has at least two real eigenvalues if n=4m or 4m + 2, (2) P has at least one real eigenvalue if n=4m+1, and (3) P has at least three real eigenvalues if n=4m+3, where m is a nonnegative integer and n ? 1. Examples are given to show that these results are the best possible, and nonnegative symmetric involutions are classified.     

On divisors of binomial coefficients,I

It is a well-known conjecture that (_n²ⁿ) is never squarefree if n > 4. It is shown that (_n²ⁿ) is not squarefree if n > n₀.     

On extremal k-outconnected graphs

Let G be a minimally k-connected graph with n nodes and m edges. Mader proved that if n?3k-2 then m?k(n-k), and for n?3k-1 an equality is possible if, and only if, G is the complete bipartite graph K_k,n-k. Cai proved that if n?3k-2 then m?⌊(n+k)²/8⌋, and listed the cases when this bound is tight.In this paper we prove a more general theorem, which implies similar results for minimally k-outconnected graphs; a graph is called k-outconnected from r if it contains k internally disjoint paths from r to every other node.     

Existence of weakly pandiagonal orthogonal Latin squares

A weakly pandiagonal Latin square of order n over the number set {0, 1, . . . , n-1} is a Latin square having the property that the sum of the n numbers in each of 2n diagonals is the same. In this paper, we shall prove that a pair of orthogonal weakly pandiagonal Latin squares of order n exists if and only if n ≡ 0, 1, 3 (mod 4) and n≠3.