Том 93, № 3 (2016)

Symmetric random matrices are considered whose upper triangular entries are independent identically distributed random variables with zero mean, unit variance, and a finite moment of order 4 + δ, δ > 0. It is shown that the distances between the Stieltjes transforms of the empirical spectral distribution function and the semicircle law are of order lnn/nv, where v is the distance to the real axis in the complex plane. Applications concerning the convergence rate in probability to the semicircle law, localization of eigenvalues, and delocalization of eigenvectors are discussed.

New inequalities relating Sobolev and Kantorovich norms for functions on Riemannian manifolds satisfying certain curvature conditions are obtained.

The boundary values of conformal mappings of plane finitely connected domains are studied. A complete description of the boundary values of such mappings in terms of the moduli (extremal lengths) of pairs of boundary components of domains is obtained in the case where the number of boundary components is not larger than three.

A family of distance graphs whose structure is close to that of Kneser graphs is studied. New lower and upper bounds for the chromatic numbers of such graphs are obtained, and relations between these numbers are considered. The structure of certain important independent sets of the family of graphs under consideration is described, and the cardinalities of these sets are explicitly calculated.

A new quality measure for compressed sensing matrices is considered and its non-trivial lower bound is obtained which depends on the matrix sizes only. A relation of the new estimate to the standard restricted isometry property is established. The tightness of the new result is discussed as well as some its consequences related to the known results in compressed sensing theory.

The notions of the distance and multidistance embeddability of a graph in ℝ^d are natural generalizations of the notion of a distance graph in ℝ^d. Results on the complexity of the computational problem of verifying distance graph embeddability are briefly surveyed, and new progress in solving this and related problems is described.

The complexity status of several discrete optimization problems concerning the search for a subset of a finite set of Euclidean points (vectors) is analyzed. In the considered problems, the aim is to minimize objective functions depending either only on the norm of the sum of the elements from the subset or on this norm and the cardinality of the subset. It is proved that, if the dimension of the space is part of the input, then all analyzed problems are strongly NP-hard and, if the space dimension is fixed, then these problems are NP-hard even for dimension 2 (on a plane). It is shown that, if the coordinates of the input points are integer, then all the problems can be solved in pseudopolynomial time in the case of a fixed space dimension.

It is proved that integrals of Abel differential equations can be used in the explicit construction of Bäcklund transformations in mechanics.

Consider a periodic sequence over a finite alphabet, say ..ababab.... This sequence can be specified by prohibiting the subwords aa and bb. In the paper, the maximum period of a word that can be defined by using k restrictions is determined. A sharp exponential bound is obtained: the period of a word determined by k restrictions cannot exceed the kth Fibonacci number. Thus, the period colength is estimated. The problem is studied in the context of Gröbner bases, namely, the growth of a Gröbner basis of an ideal (the cogrowth of an algebra). The proof uses the technique of Rauzy graphs.

A general theorem on the purity of invariant field extensions is proved. Using it, a criterion of rational triangulability of connected solvable affine algebraic subgroups of the Cremona groups is obtained. This criterion is applied for proving the existence of rationally nontriangulable subgroups of the above form and for proving their stable rational triangulability. The latter property answers in the affirmative Bass’ Triangulability Problem in the stable range. A general construction of all rationally triangulable connected solvable affine algebraic subgroups of the Cremona groups is obtained. As an application, a classification of all rationally triangulable connected one-dimensional unipotent affine algebraic subgroups of the Cremona groups up to conjugacy is given.

The resolvent approach to the Fourier method is used to examine the behavior of the formal solution to the mixed problem for an inhomogeneous wave equation with a summable potential. A classical solution is obtained under minimum conditions imposed on the initial function. It is shown that, in the case of square summable initial and driving functions, the series sum of the formal solution is a weak solution of the mixed problem.

We give a description of metric properties of measurable mappings of domains on Riemannian manifolds inducing isomorphisms of Sobolev spaces by the composition rule. We prove that any such mapping can be redefined on a set of measure zero to be quasi-isometric, when the exponent of summability is different from the dimension of a Riemannian manifold or to coincide with a quasi-conformal mapping otherwise.

We find the asymptotics of the counting function of elements of an additive arithmetical semigroup for the case of an exponential counting function of prime generators, which has a natural interpretation in terms of Bose statistics as well as in the problem of counting the number of Gaussian packets on decorated graphs.

A new approach to solving discrete Lyapunov matrix algebraic equations is based on methods for spectral decomposition of their solutions. Assuming that all eigenvalues of the matrices on the left-hand side of the equation lie inside the unit disk, it is shown that the matrix of the solution to the equation can be calculated as a finite sum of matrix bilinear quadratic forms made up by products of Faddeev matrices obtained by decomposing the resolvents of the matrices of the Lyapunov equation. For a linear autonomous stochastic discrete dynamic system, analytical expressions are obtained for the decomposition of the asymptotic variance matrix of system’s states.