Two-sided estimates for essential height in Shirshov’s Height Theorem

The paper is focused on two-sided estimates for the essential height in Shirshov??s Height Theorem. The concepts of the selective height and strong n-divisibility directly related to the height and n-divisibility are introduced. We prove lower and upper bounds for the selective height over nonstrongly n-divisible words of length 2. For any n and sufficiently large l these bounds differ at most twice. The case of words of length 3 is also studied. The case of words of length 2 can be generalized to the proof of an upper exponential estimate in Shirshov??s Height Theorem. The proof uses the idea of V.N. Latyshev related to the application of Dilworth??s theorem to the study of non n-divisible words.     

Piecewise periodicity structure estimates in Shirshov’s height theorem

The Gelfand-Kirillov dimension of l-generated general matrices is equal to (l ? 1)n ² + 1. Due to the Amitzur-Levitsky theorem, the minimal degree of the identity of this algebra is 2n. That is why the essential height of A being an l-generated PI-algebra of degree n over every set of words is greater than (l ? 1)n ²/4 + 1. In this paper we prove that if A has a finite Gelfand-Kirillov dimension, then the number of lexicographically comparable subwords with the period (n ? 1) in each monoid of A is not greater than (l ? 2)(n ? 1). The case of subwords with the period 2 can be generalized to the proof of Shirshov’s height theorem.     

On graphs with equal edge connectivity and minimum degree

The note contains some conditions on a graph implying that the edge connectivity is equal to the minimum degree. One of these conditions is that if d₁?d₂???d_n is the degree sequence then ∑^l_l?1(d₁+d_n?1)>In?1 for $\text{1 ? l? min {}\text{n}\text{2?1}\text{, d}{}_{\mathrm{n}}\text{}}$.     

Binary Segmentation for Multivariate Polynomials

This paper develops a fast method of binary segmentation for multivariate integer polynomials and applies it to polynomial multiplication, pseudodivision, resultant and gcd calculations. In the univariate case, binary segmentation yields the fastest known method for multiplication of integer polynomials, even slightly faster than fast Fourier transform methods (however, the underlying fast integer multiplication method is based on fast Fourier transforms). Fischer and Paterson ("SIAM-AMS Proceedings, 1974," pp. 113-125) seem to be the first authors who suggest binary segmentation for polynomials with coefficients in {0, 1}. Schönhage (J. Complexity1 (1985), 118-137), as well as Bini and Pan (J. Complexity2 (1986), 179-203) have applied the binary segmentation to univariate polynomial division and gcd calculation. In the multivariate case, well- known methods are the iterated application of univariate binary segmentation and Kronecker′s map. Our method of binary segmentation to the contrary is based on a one-step algebra homomorphism mapping multivariate polynomials directly into integers. More precisely, the variables x₁, . . . , x_n of a multivariate polynomial are substituted by integers 2^ν₁, . . . , 2^ν_n, where ν₁ < · · · < ν_n are chosen as small as possible. If n is the number of variables, d bounds the total degrees, and l bounds the bit lengths of the input, we achieve the bit complexities O(ψ((2d)ⁿ (n log d + l))) for multivariate multiplication, O(d ψ(d²ⁿ(n log d + l))) for multivariate pseudo-division (provided n = O(d log d)), and O(d ψ((2d²)ⁿ (n log d + l))) for multivariate subresultant chain calculation. Here ψ(l) = l log l log log l denotes the complexity of integer multiplication.     

Global Hölder estimates for optimal transportation

We generalize the well-known result due to Caffarelli concerning Lipschitz estimates for the optimal transportation T of logarithmically concave probability measures. Suppose that T: ? ^d → ? ^d is the optimal transportation mapping µ = e ^?V dx to ν = e ^?W dx. Suppose that the second difference-differential V is estimated from above by a power function and that the modulus of convexity W is estimated from below by the function A _q |x|^1+q , q ≥ 1. We prove that, under these assumptions, the mapping T is globally Hölder with the Hölder constant independent of the dimension. In addition, we study the optimal mapping T of a measure µ to Lebesgue measure on a convex bounded set K ? ? ^d . We obtain estimates of the Lipschitz constant of the mapping T in terms of d, diam(K), and DV, D ² V.     

Non-simply connected copes

Let (W⁴,?W⁴) be a 4-manifold. Let f₁,f₂,…,f_k:(D²,?D²)→ (W⁴,?W⁴) be transverse immersions that have spherical duals $\text{α}{}_1\text{,α}{}_2\text{,…,α}{}_{\mathrm{k}}\text{:S}{}^2\text{→}\text{W}\text{?}$. Then there are open disjoint subsets V₁, V₂,…,V_k of W, such that for each 1?i?k, (a) ?V_i=V₁∩?W and ?V_i is an open regular neighborhood of f_i(?D²) in ?W, and (b) (V_i,?V_i,f_i(?D²)) is proper homotopy equivalent to (M, ?M, d)—a standard object in which d bounds an embedded flat disk. If we could get a homeomorphism instead of a proper homotopy equivalence, then we would be able to prove a 5-dimensional s-cobordism theorem.     

On the continuity of the map ϑ → ¦ϑ¦ from the predual of a W1-algebra

Let ?, ψ be elements in the predual of a W¹-algebra. For their absolute value parts ¦?¦, ¦ψ¦, the estimate $\text{∥¦?¦ ? ¦ψ¦∥ ? (2 ∥? + ψ∥ ∥? ? ψ∥)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ is obtained.     

Forbidding just one intersection

Following a conjecture of P. Erdös, we show that if $\text{F}$ is a family of k-subsets of and n-set no two of which intersect in exactly l elements then for k ? 2l + 2 and n sufficiently large |$\text{F}$| ? (_{k ? l ? 1}^{n ? l ? 1}) with equality holding if and only if $\text{F}$ consists of all the k-sets containing a fixed (l + 1)-set. In general we show |$\text{F}$| ? d_kn^{max;{;l,k ? l ? 1};}, where d_k is a constant depending only on k. These results are special cases of more general theorems (Theorem 2.1–2.3).     

Vertical versus horizontal Poincaré inequalities on the Heisenberg group

Let ? = 〈a, b|a[a, b] = [a, b]a ∧ b[a, b] = [a, b]b〉 be the discrete Heisenberg group, equipped with the left-invariant word metric d _W (·, ·) associated to the generating set {a, b, a ^?1, b ^?1}. Letting B _n = {x ∈ ?: d _W (x, e _?) ? n} denote the corresponding closed ball of radius n ∈ ?, and writing c = [a, b] = aba ^?1 b ^?1, we prove that if (X, ‖ · ‖X) is a Banach space whose modulus of uniform convexity has power type q ∈ [2,∞), then there exists K ∈ (0, ∞) such that every f: ? → X satisfies $$\sum\limits_{k = 1}^{{n^2}} {\sum\limits_{x \in {B_n}} {\frac{{\left\| {f(x{c^k}) - f(x)} \right\|_X^q}}{{{k^{1 + q/2}}}}} } \leqslant K\sum\limits_{x \in {B_{21n}}} {(\left\| {f(xa) - f(x)} \right\|_X^q + \left\| {f(xb) - f(x)} \right\|_X^q)} $$ . It follows that for every n ∈ ? the bi-Lipschitz distortion of every f: B _n → X is at least a constant multiple of (log n)^1/q , an asymptotically optimal estimate as n → ∞.     

The Independence Number for De Bruijn networks and Kautz networks

Let D be a directed graph; the (l,ω)-Independence Number of graph D, denoted by α_l,ω(D), is an important performance parameter for interconnection networks. De Bruijn networks and Kautz networks, denoted by B(d,n) and K(d,n) respectively, are versatile and efficient topological structures of interconnection networks. For l=1,2,…,n, this paper shows that α_l,d−1(B(d,n))=dⁿ,α_l,d−1(K(d,n))=α_l,d(K(d,n))=dⁿ+dⁿ⁻¹ if d≥3 and n≤d−2. In particular, the paper shows the exact value of the Independence Number for B(d,1) and B(d,2) for any d. For the generalized situation, the paper obtains a lower bound α_l,d−1(B(d,n))≥d² if n≥3 and d≥5.     

Differentiability points of functions in weighted Sobolev spaces

We consider weighted Sobolev spaces W _p ^l , l ∈ ?, with weighted L _p -norm of higher derivatives on an n-dimensional cube-type domain. The weight γ depends on the distance to an (n ? d)-dimensional face E of the cube. We establish the property of uniform L _p -differentiability of functions in these spaces on the face E of an appropriate dimension. This property consists in the possibility of L _p -approximation of the values of a function near E by a polynomial of degree l ? 1.     

Strong capacity-estimates for “fractional” norms

It is proved that for all fractionall the integral \(\int\limits_0^\infty {(p,\ell ) - cap(M_t )} dt^p\) is majorized by the P-th power norm of the functionu in the space ? _p ^l (Rⁿ) (here M_t={x∶¦u(x)¦?t} and (p,l)-cap(e) is the (p,l)-capacity of the compactum e?Rⁿ). Similar results are obtained for the spaces W _p ^l (Rⁿ) and the spaces of M. Riesz and Bessel potentials. One considers consequences regarding imbedding theorems of “fractional” spaces in ?_q(dμ), whereμ is a nonnegative measure in Rⁿ. One considers specially the case p=1.     

Sur les arborescences dans un graphe oriente

The main result of this paper is the following theorem: Let G = (X,E) be a digraph without loops or multiple edges, |X| ?3, and h be an integer ?1, if G contains a spanning arborescence and if d⁺_G(x)+d^?_G(x)+d^?_G(y)+d^?_G(y)? 2|X |?2h?1 for all x, y?X, x ≠ y, non adjacent in G, then G contains a spanning arborescence with ?h terminal vertices. A strengthening of Gallai-Milgram's theorem is also proved.     

N-Widths and ε-Dimensions for High-Dimensional Approximations

In this paper, we study linear trigonometric hyperbolic cross approximations, Kolmogorov n-widths d _n (W,H ^γ ), and ε-dimensions n _ε (W,H ^γ ) of periodic d-variate function classes W with anisotropic smoothness, where d may be large. We are interested in finding the accurate dependence of d _n (W,H ^γ ) and n _ε (W,H ^γ ) as a function of two variables n, d and ε, d, respectively. Recall that n, the dimension of the approximating subspace, is the main parameter in the study of convergence rates with respect to n going to infinity. However, the parameter d may seriously affect this rate when d is large. We construct linear approximations of functions from W by trigonometric polynomials with frequencies from hyperbolic crosses and prove upper bounds for the error measured in isotropic Sobolev spaces H ^γ . Furthermore, in order to show the optimality of the proposed approximation, we prove upper and lower bounds of the corresponding n-widths d _n (W,H ^γ ) and ε-dimensions n _ε (W,H ^γ ). Some of the received results imply that the curse of dimensionality can be broken in some relevant situations.     

Best quadrature formulas at equally spaced nodes

It has been known for some time that the trapezoidal rule $\text{T}{}_{\mathrm{n}}\text{f =}\text{1}\text{2}\text{f(0) + f(1) + … + f(n ? 1) +}\text{1}\text{2}\text{f(n)}$ is the best quadrature formula in the sense of Sard for the space W^1,p, all functions such that f′ ?L^p. In other words, the norm of the error functional Ef = ∝₀ⁿf(x) dx ? ∑_{k = 0}ⁿλ_kf(k) in W^1,p is uniquely minimized by the trapezoidal sum. This paper deals with quadrature formulas of the form ∑_{k = 0}ⁿ ∑_l?Jc_klf^(l)(k) where J is some subset of {0, 1,…, m ? 1}. For certain index sets J we identify the best quadrature formula for the space W^m,p, all functions such that f^(m)?L^p. As a result, we show that the Euler-Maclaurin quadrature formula

$\text{T}{}_{\mathrm{n}}\text{f +}\text{∑}\text{o<2v≤m}\text{B}{}_{\mathrm{2v}}\text{(2v)!}\text{(f (2v?1)(0) ? f (2v?1) (n))}$

is the best quadrature formula of the above form with J = {0, 1, 3,…, ?m ? 1} for the space W^m,p, providing m is an odd integer.     

Representations for the weighted Drazin inverse of a sum of matrices

Three representations for the W-weighted Drazin inverse of a matrix A?CWB have been developed under some conditions where A,B,C∈? ^m×n , and W∈? ^n×m . The results of this paper not only extend the earlier works about the Drazin inverse and group inverse, but also weaken the assumed condition of a result of the Drazin inverse to the case where Γ _d ZZ _g =ZZ _g Γ _d is substituted with C(Γ _d ZZ _g ?ZZ _g Γ _d )B=0. Numerical examples are given to illustrate some new results.     

Pointwise estimates of potentials for higher-order capacities

In a domain D=Ω\E∈ R ⁿ , we consider a nonlinear higher-order elliptic equation such that the corresponding energy space is W _p ^m (D)?W _q ¹ (D), q>mp, and estimate a solution u(x) of this equation satisfying the condition u(x)?kf(x)∈W _p ^m (D)?W _q ¹ (D), where k∈R ¹, f(x)∈ C ₀ ^∞ (Ω), and f(x)=1 for x∈F. We establish a pointwise estimate for u(x) in terms of the higher-order capacity of the set F and the distance from the point x to the set F.     

Nilpotency indices,degrees of iterations of affine triangular automorphisms,and Schubert calculus

Let f be a triangular automorphism of the affine N-space of degree d with Jacobian 1 over a \({\mathbb{Q}}\) -algebra R. We introduce a weighted nilpotency index ν(f) for f, and give a bound of deg(f ⁿ ) in terms of N, d and ν(f) for all \({n \in \mathbb{Z}}\) . When N = 2, our formula, combined with computation of the Hilbert series of certain graded algebras, yields the estimate deg(f ⁿ ) ≤ d ² ? d + 1 for all \({n \in \mathbb{Z}}\) . If n varies through all integers, this estimate turns out to be sharp and is related, somewhat unexpectedly, to the Schubert calculus on the Grassmannian G(d ? 1, 2d ? 2). Numerical computation for small degrees suggests that this estimate restricted to the inverse degree (i.e. n = ?1) is also sharp if d ≥ 3.     

The weight distribution of irreducible cyclic codes with block lengths n1((q1−1)N)

We study the weight distribution of irreducible cyclic (n, k) codeswith block lengths n = n₁((q¹ ? 1)/N), where N|q ? 1, gcd(n₁,N) = 1, and gcd(l,N) = 1. We present the weight enumerator polynomial, A(z), when k = n₁l, k = (n₁ ? 1)l, and k = 2l. We also show how to find A(z) in general by studying the generator matrix of an (n₁, m) linear code, $\text{V}{}^1{}_{\mathrm{d}}$ over GF(q^d) where d = gcd (ord_n1(q), l). Specifically we study A(z) when $\text{V}{}^1{}_{\mathrm{d}}$ is a maximum distance separable code, a maximal shiftregister code, and a semiprimitive code. We tabulate some numbers A_μ which completely determine the weight distributionof any irreducible cyclic (n₁(2¹ ? 1), k) code over GF(2) for all n₁ ? 17.     

A note on the probabilistic approach to Turán's problem

The Turán number T(n, l, k) is the smallest possible number of edges in a k-graph on n vertices such that every l-set of vertices contains an edge. Given a k-graph H = (V(H), E(H)), we let X_s(S) equal the number of edges contained in S, for any s-set S?V(H). Turán's problem is equivalent to estimating the expectation E(X_l), given that min(X_l) ≥ 1. The following lower bound on the variance of X_s is proved:

$\text{Var(X}{}_{\mathrm{s}}\text{)?mm}\text{n?2k}\text{s?k}\text{n}\text{s}{}^{\mathrm{?1}}\text{n}\text{k}{}^1$

, where m = |E(H)| and $\text{m}\text{= (}{}_{\mathrm{k}}{}^{\mathrm{n}}\text{) ? m}$. This implies the following: putting t(k, l) = lim_n→∞T(n, l, k)(_kⁿ)^?1 then t(k, l) ≥ T(s, l, k)((_k^s) ? 1)^?1, whenever s ≥ l > k ≥ 2. A connection of these results with the existence of certain t-designs is mentioned.