Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic

It was proved that the complexity of square root computation in the Galois field GF(3^s), s = 2^kr, is equal to O(M(2^k)M(r)k + M(r) log₂r) + 2^kkr^1+o(1), where M (n) is the complexity of multiplication of polynomials of degree n over fields of characteristics 3. The complexity of multiplication and division in the field GF(3^s) is equal to O(M(2^k)M(r)) and O(M(2^k)M(r)) + r^1+o(1), respectively. If the basis in the field GF(3^r) is determined by an irreducible binomial over GF(3) or is an optimal normal basis, then the summands 2^kkr^1+o(1) and r^1+o(1) can be omitted. For M(n) one may take n log₂nψ(n) where ψ(n) grows slower than any iteration of the logarithm. If k grow and r is fixed, than all the estimates presented here have the form O_r (M (s) log ₂s) = s (log ₂s)²ψ(s).     

The program iteration method in a game problem of guidance

Let a sequence of d-dimensional vectors n _k = (n _k ¹ , n _k ² ,..., n _k ^d ) with positive integer coordinates satisfy the condition n _k ^j = α _j m _k +O(1), k ∈ ?, 1 ≤ j ≤ d, where α ₁ > 0,..., α _d > 0 and {m _k } _k=1 ^∞ is an increasing sequence of positive integers. Under some conditions on a function φ: [0,+∞) → [0,+∞), it is proved that, if the sequence of Fourier sums \({S_{{m_k}}}\) (g, x) converges almost everywhere for any function g ∈ φ(L)([0, 2π)), then, for any d ∈ ? and f ∈ φ(L)(ln⁺ L) ^d?1([0, 2π) ^d ), the sequence \({S_{{n_k}}}\) (f, x) of rectangular partial sums of the multiple trigonometric Fourier series of the function f and the corresponding sequences of partial sums of all conjugate series converge almost everywhere.     

Centralizers of generalized skew derivations on multilinear polynomials

Let R be a prime ring of characteristic different from 2, let Q be the right Martindale quotient ring of R, and let C be the extended centroid of R. Suppose that G is a nonzero generalized skew derivation of R and f(x ₁,..., x _n ) is a noncentral multilinear polynomial over C with n noncommuting variables. Let f(R) = {f(r ₁,..., r _n ): r _i ∈ R} be the set of all evaluations of f(x ₁,..., x _n ) in R, while A = {[G (f(r ₁,..., r _n )), f(r ₁,..., r _n )]: r _i ∈ R}, and let C _R (A) be the centralizer of A in R; i.e., C _R (A) = {a ∈ R: [a, x] = 0, ? _x ∈ A }. We prove that if A ≠ (0), then C _R (A) = Z(R).     

Equicontinuity of maps on a dendrite with finite branch points

Let(T, d) be a dendrite with finite branch points and f be a continuous map from T to T. Denote byω(x,f) and P(f) the ω-limit set of x under f and the set of periodic points of,respectively. Write Ω(x,f) = {y| there exist a sequence of points x_k E T and a sequence of positive integers n_1 n_2 … such that lim_(k→∞)x_k=x and lim_(k→∞)f~(n_k)(x_k) =y}. In this paper, we show that the following statements are equivalent:(1) f is equicontinuous.(2) ω(x, f) = Ω(x,f) for any x∈T.(3) ∩_(n=1)~∞f~n(T) = P(f),and ω(x,f)is a periodic orbit for every x ∈ T and map h : x→ω(x,f)(x ET)is continuous.(4) Ω(x,f) is a periodic orbit for any x∈T.     

Equiconvergence of expansions in multiple Fourier series and in fourier integrals with “lacunary sequences of partial sums”

We investigate the equiconvergence on T^N = [?π, π)^N of expansions in multiple trigonometric Fourier series and in the Fourier integrals of functions f ∈ L_p(T^N) and g ∈ L_p(R^N), p > 1, N ≥ 3, g(x) = f(x) on T^N, in the case where the “partial sums” of these expansions, i.e., S_n(x; f) and J_α(x; g), respectively, have “numbers” n ∈ Z^N and α ∈ R^N (n_j = [α_j], j = 1,..., N, [t] is the integral part of t ∈ R¹) containing N ? 1 components which are elements of “lacunary sequences.”     

On likelihood ratio ordering of parallel systems with exponential components

Let T(λ₁,...,λ _n ) be the lifetime of a parallel system consisting of exponential components with hazard rates λ₁,...,λ _n , respectively. For systems with only two components, Dykstra et. al. (1997) showed that if (λ₁, λ₂) majorizes (γ₁, γ₂), then, T(λ₁, λ₂) is larger than T(γ₁, γ₂) in likelihood ratio order. In this paper, we extend this theorem to general parallel systems. We introduce a new partial order, the so-called d-larger order, and show that if (λ₁,...,λ _n ) is d-larger than (γ₁,...,γ _n ), then T(λ₁,...,λ _n ) is larger than T(γ₁,...,γ _n ) in likelihood ratio order.     

Lower bounds for polynomials of many variables

A polynomial P(ξ) = P(ξ₁,..., ξ _n ) is said to be almost hypoelliptic if all its derivatives D ^ν P(ξ) can be estimated from above by P(ξ) (see [16]). By a theorem of Seidenberg-Tarski it follows that for each polynomial P(ξ) satisfying the condition P(ξ) > 0 for all ξ ∈ R ⁿ , there exist numbers σ > 0 and T ∈ R¹ such that P(ξ) ≥ σ(1 + |ξ|) ^T for all ξ ∈ R ⁿ . The greatest of numbers T satisfying this condition, denoted by ST(P), is called Seidenberg-Tarski number of polynomial P. It is known that if, in addition, P ∈ I _n , that is, |P(ξ)| → ∞ as |ξ| → ∞, then T = T(P) > 0. In this paper, for a class of almost hypoelliptic polynomials of n (≥ 2) variables we find a sufficient condition for ST(P) ≥ 1. Moreover, in the case n = 2, we prove that ST(P) ≥ 1 for any almost hypoelliptic polynomial P ∈ I₂.     

Inequalities between best polynomial approximations and some smoothness characteristics in the space <Emphasis Type="Italic">L</Emphasis> <Subscript>2</Subscript> and widths of classes of functions

We obtain exact constants in Jackson-type inequalities for smoothness characteristics Λ_k(f), k ∈ N, defined by averaging the kth-order finite differences of functions f ∈ L₂. On the basis of this, for differentiable functions in the classes L₂^r, r ∈ N, we refine the constants in Jackson-type inequalities containing the kth-order modulus of continuity ω_k. For classes of functions defined by their smoothness characteristics Λ_k(f) and majorants Φ satisfying a number of conditions, we calculate the exact values of certain n-widths.     

A new characterization of symmetric group by NSE

Let G be a group and ω(G) be the set of element orders of G. Let k ∈ ω(G) and m _k (G) be the number of elements of order k in G. Let nse(G) = {m _k (G): k ∈ ω(G)}. Assume r is a prime number and let G be a group such that nse(G) = nse(S _r ), where S _r is the symmetric group of degree r. In this paper we prove that G ? S _r , if r divides the order of G and r ² does not divide it. To get the conclusion we make use of some well-known results on the prime graphs of finite simple groups and their components.     

Regularized traces of singular differential operators with canonical boundary conditions

A self-adjoint differential operator \(\mathbb{L}\) of order 2m is considered in L ₂[0,∞) with the classic boundary conditions \(y^{(k_1 )} (0) = y^{(k_2 )} (0) = y^{(k_3 )} (0) = \ldots = y^{(k_m )} (0) = 0\), where 0 ≤ k ₁ < k ₂ < ... < k _m ≤ 2m ? 1 and {k _s } _s=1 ^m ∪ {2m ? 1 ? k _s } _s=1 ^m = {0, 1, 2, ..., 2m ? 1}. The operator \(\mathbb{L}\) is perturbed by the operator of multiplication by a real measurable bounded function q(x) with a compact support: \(\mathbb{P}\) f(x) = q(x)f(x), f ∈ L ₂[0,∞). The regularized trace of the operator \(\mathbb{L} + \mathbb{P}\) is calculated.     

An improvement of the five halves theorem of J. Boardman

Let (M ^m , T) be a smooth involution on a closed smooth m-dimensional manifold and F = ∪ _j=0 ⁿ F ^j (n ≤ m) its fixed point set, where F ^j denotes the union of those components of F having dimension j. The famous Five Halves Theorem of J. Boardman, announced in 1967, establishes that, if F is nonbounding, then m ≤ 5/2n. In this paper we obtain an improvement of the Five Halves Theorem when the top dimensional component of F, F ⁿ , is nonbounding. Specifically, let ω = (i ₁, i ₂, …, i _r ) be a non-dyadic partition of n and s _ω (x ₁, x ₂, …, x _n ) the smallest symmetric polynomial over Z ₂ on degree one variables x ₁, x ₂, …, x _n containing the monomial \(x_1^{i_1 } x_2^{i_2 } \cdots x_r^{i_r }\). Write s _ω (F ⁿ ) ∈ H ⁿ (F ⁿ , Z ₂) for the usual cohomology class corresponding to s _ω (x ₁, x ₂, …, x _n ), and denote by ?(F ⁿ ) the minimum length of a nondyadic partition ω with s _ω (F ⁿ ) ≠ 0 (here, the length of ω = (i ₁, i ₂, …, i _r ) is r). We will prove that, if (M ^m , T) is an involution for which the top dimensional component of the fixed point set, F ⁿ , is nonbounding, then m ≤ 2n + ?(F ⁿ ); roughly speaking, the bound for m depends on the degree of decomposability of the top dimensional component of the fixed point set. Further, we will give examples to show that this bound is best possible.     

Characterizations of symmetrized polydisc

Let Γ_n, n ≥ 2, denote the symmetrized polydisc in ?ⁿ, and Γ₁ be the closed unit disc in ?. We provide some characterizations of elements in Γ_n. In particular, an element (s₁,..., s_n?1, p) ∈ ?ⁿ is in Γ_n if and only if \({s_j} = {\beta _j} + \overline {{\beta _{n - j}}}p\), j = 1,..., n ? 1, for some (β₁,..., β_n?1) ∈ Γ_n?1, and |p| ≤ 1.     

Some variations on Tverberg’s theorem

Define T(d, r) = (d + 1)(r - 1) + 1. A well known theorem of Tverberg states that if n ≥ T(d, r), then one can partition any set of n points in R^d into r pairwise disjoint subsets whose convex hulls have a common point. The numbers T(d, r) are known as Tverberg numbers. Reay added another parameter k (2 ≤ k ≤ r) and asked: what is the smallest number n, such that every set of n points in R^d admits an r-partition, in such a way that each k of the convex hulls of the r parts meet. Call this number T(d, r, k). Reay conjectured that T(d, r, k) = T(d, r) for all d, r and k. In this paper we prove Reay’s conjecture in the following cases: when k ≥ [d+3/2], and also when d < rk/r-k - 1. The conjecture also holds for the specific values d = 3, r = 4, k = 2 and d = 5, r = 3, k = 2.     

On the pronormality of subgroups of odd index in finite simple symplectic groups

A subgroup H of a group G is pronormal if the subgroups H and H ^g are conjugate in 〈H,H ^g 〉 for every g ∈ G. It was conjectured in [1] that a subgroup of a finite simple group having odd index is always pronormal. Recently the authors [2] verified this conjecture for all finite simple groups other than PSL _n (q), PSU _n (q), E ₆(q), ² E ₆(q), where in all cases q is odd and n is not a power of 2, and P Sp_2n (q), where q ≡ ±3 (mod 8). However in [3] the authors proved that when q ≡ ±3 (mod 8) and n ≡ 0 (mod 3), the simple symplectic group P Sp²ⁿ (q) has a nonpronormal subgroup of odd index, thereby refuted the conjecture on pronormality of subgroups of odd index in finite simple groups.The natural extension of this conjecture is the problem of classifying finite nonabelian simple groups in which every subgroup of odd index is pronormal. In this paper we continue to study this problem for the simple symplectic groups P Sp_2n (q) with q ≡ ±3 (mod 8) (if the last condition is not satisfied, then subgroups of odd index are pronormal). We prove that whenever n is not of the form 2 ^m or 2 ^m (2^2k +1), this group has a nonpronormal subgroup of odd index. If n = 2 ^m , then we show that all subgroups of P Sp_2n (q) of odd index are pronormal. The question of pronormality of subgroups of odd index in P Sp_2n (q) is still open when n = 2 ^m (2^2k + 1) and q ≡ ±3 (mod 8).     

Equalities on the number of conjugacy classes of the Sylow p-subgroups of GL(n,q)

We denote by Gn the group of the upper unitriangular matrices over F_q, the finite field with q = p^t elements, and r(G_n) the number of conjugacy classes of G_n. In this paper, we obtain the value of r(G_n) modulo (q² -1)(q -1). We prove the following equalities     

Integral approximation of the characteristic function of an interval by trigonometric polynomials

We prove that the value E _n?1(χ _h ) _L of the best integral approximation of the characteristic function χ _h of an interval (?h, h) on the period [?π,π) by trigonometric polynomials of degree at most n ? 1 is expressed in terms of zeros of the Bernstein function cos {nt ? arccos[(2q ? (1 + q ²) cost)/(1 + q ² ? 2q cost)]}, t ∈ [0, π], q ∈ (?1,1). Here, the parameters q, h, and n are connected in a special way; in particular, q = sech ? tanh for h = π/n.     

The Erdös-Kac theorem for additive arithmetical semigroups

We show that the Erdös-Kac theorem for additive arithmetical semigroups can be proved under the condition that the counting function of elements has the asymptotics G(n) = q ⁿ (A + O(1/(lnn)^k) as n → ∞ with A > 0, q > 1, and arbitrary k ∈ ? and that P(n) = O(q ⁿ /n) for the number of prime elements of degree n. This improves a result of Zhang.     

The independent neighborhoods process

A triangle T^(r) in an r-uniform hypergraph is a set of r+1 edges such that r of them share a common (r-1)-set of vertices and the last edge contains the remaining vertex from each of the first r edges. Our main result is that the random greedy triangle-free process on n points terminates in an r-uniform hypergraph with independence number O((n log n)^1/r). As a consequence, using recent results on independent sets in hypergraphs, the Ramsey number r(T^(r),K_s^(r)) has order of magnitude s^r/ log s. This answers questions posed in [4, 10] and generalizes the celebrated results of Ajtai–Komlós–Szemerédi [1] and Kim [9] to hypergraphs.     

On low discrepancy sequences and low discrepancy ergodic transformations of the multidimensional unit cube

In this paper we describe a third class of low discrepancy sequences. Using a lattice Γ ? ? ^s , we construct Kronecker-like and van der Corput-like ergodic transformations T _1,Γ and T _2,Γ of [0, 1) ^s . We prove that for admissible lattices Γ, (T _ν,Γ ⁿ (x))_n≥0 is a low discrepancy sequence for all x ∈ [0, 1) ^s and ν ∈ {1, 2}. We also prove that for an arbitrary polyhedron P ? [0, 1) ^s , for almost all lattices Γ ∈ L _s = SL(s,?)/SL(s, ?) (in the sense of the invariant measure on L _s ), the following asymptotic formula

$\# \{ 0 \le n < N:T_{v,\Gamma }^n(x) \in P\} = NvolP + O({(\ln N)^{s + \varepsilon }}),N \to \infty$

holds with arbitrary small ? > 0, for all x ∈ [0, 1) ^s , and ν ∈ {1, 2}.

     

Linear preservers of row-dense matrices

Let M_m,n be the set of all m × n real matrices. A matrix A ∈ M_m,n is said to be row-dense if there are no zeros between two nonzero entries for every row of this matrix. We find the structure of linear functions T: M_m,n → M_m,n that preserve or strongly preserve row-dense matrices, i.e., T(A) is row-dense whenever A is row-dense or T(A) is row-dense if and only if A is row-dense, respectively. Similarly, a matrix A ∈ M_n,m is called a column-dense matrix if every column of A is a column-dense vector. At the end, the structure of linear preservers (strong linear preservers) of column-dense matrices is found.