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).     

Elliptic function of level 4

The article is devoted to the theory of elliptic functions of level n. An elliptic function of level n determines a Hirzebruch genus called an elliptic genus of level n. Elliptic functions of level n are also of interest because they are solutions of the Hirzebruch functional equations. The elliptic function of level 2 is the Jacobi elliptic sine function, which determines the famous Ochanine–Witten genus. It is the exponential of the universal formal group of the form F(u, v) = (u² ? v²)/(uB(v) ? vB(u)), B(0) = 1. The elliptic function of level 3 is the exponential of the universal formal group of the form F(u, v) = (u²A(v) ? v²A(u))/(uA(v)² ? vA(u)²), A(0) = 1, A″(0) = 0. In the present study we show that the elliptic function of level 4 is the exponential of the universal formal group of the form F(u, v) = (u²A(v) ? v²A(u))/(uB(v) ? vB(u)), where A(0) = B(0) = 1 and for B′(0) = A″(0) = 0, A′(0) = A₁, and B″(0) = 2B₂ the following relation holds: (2B(u) + 3A₁u)² = 4A(u)³ ? (3A₁² ? 8B₂)u²A(u)². To prove this result, we express the elliptic function of level 4 in terms of the Weierstrass elliptic functions.     

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.”     

New Applications of the <Emphasis Type="Italic">p</Emphasis>-Adic Nevanlinna Theory

Let IK be an algebraically closed field of characteristic 0 complete for an ultrametric absolute value. Following results obtained in complex analysis, here we examine problems of uniqueness for meromorphic functions having finitely many poles, sharing points or a pair of sets (C.M. or I.M.) defined either in the whole field IK or in an open disk, or in the complement of an open disk. Following previous works in C, we consider functions fⁿ(x)f^m(ax + b), gⁿ(x)g^m(ax + b) with |a| = 1 and n ≠ m, sharing a rational function and we show that f/g is a n + m-th root of 1 whenever n + m ≥ 5. Next, given a small function w, if n, m ∈ IN are such that |n ? m|_∞ ≥ 5, then fⁿ(x)f^m(ax + b) ? w has infinitely many zeros. Finally, we examine branched values for meromorphic functions fⁿ(x)f^m(ax + b).     

Riesz transform characterization of Hardy spaces associated with Schrödinger operators with compactly supported potentials

Let L=?Δ+V be a Schrödinger operator on ? ^d , d≥3. We assume that V is a nonnegative, compactly supported potential that belongs to L ^p (? ^d ), for some p>d /2. Let K _t be the semigroup generated by ?L. We say that an L ¹(? ^d )-function f belongs to the Hardy space \(H^{1}_{L}\) associated with L if sup?_t>0|K _t f| belongs to L ¹(? ^d ). We prove that \(f\in H^{1}_{L}\) if and only if R _j f∈L ¹(? ^d ) for j=1,…,d, where R _j =(?/? x _j )L ^?1/2 are the Riesz transforms associated with L.     

Nonlinear trigonometric approximations of multivariate function classes

Order-sharp estimates are established for the best N-term approximations of functions from Nikol’skii–Besov type classes B_pq^sm(T^k) with respect to the multiple trigonometric system T^(k) in the metric of L_r(T^k) for a number of relations between the parameters s, p, q, r, and m (s = (s₁,..., s_n) ∈ R₊ⁿ, 1 ≤ p, q, r ≤ ∞, m = (m₁,..., m_n) ∈ Nⁿ, k = m₁ +... + m_n). Constructive methods of nonlinear trigonometric approximation—variants of the so-called greedy algorithms—are used in the proofs of upper estimates.     

Heat Kernels for Isotropic-Like Markov Generators on Ultrametric Spaces: a Survey

Let (X, d) be a locally compact separable ultrametric space. Let D be the set of all locally constant functions having compact support. Given a measure m and a symmetric function J(x, y) we consider the linear operator L^Jf(x) = ∫(f(x) ? f(y)) J(x, y)dm(y) defined on the set D. When J(x, y) is isotropic and satisfies certain conditions, the operator (?L^J, D) acts in L²(X,m), is essentially self-adjoint and extends as a self-adjoint Markov generator, its Markov semigroup admits a continuous heat kernel p^J (t, x, y). When J(x, y) is not isotropic but uniformly in x, y is comparable to isotropic function J(x, y) as above the operator (?L^J, D) extends in L²(X,m) as a self-adjointMarkov generator, its Markov semigroup admits a continuous heat kernel p^J(t, x, y), and the function p^J(t, x, y) is uniformly comparable in t, x, y to the function p^J(t, x, y), the heat kernel related to the operator (?L^J,D).     

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.     

Estimates for Sobolev norms of triangular mappings

An increasing triangular mapping T on the n-dimensional cube Θ = [0, 1] ⁿ transforming a measure μ to a measure ν is considered, where μ and ν are absolutely continuous Borel probability measures having densities ρ _μ and ρ _ν . It is shown that if there exist positive constants ? and M such that ? < ρ _ν < M, ? < ρ _ν < M, there exist numbers α, β > 1 such that p = αβ(n ? 1)^?1 (α + β)^?1 > 1 and ρ _μ ∈ W ^1,α (Θ), ρ _ν ∈ W ^1,β ) (Θ), where W ^1,q denotes a Sobolev class, then the mapping T belongs to the class W ^1,p (Θ).     

Stability of Cubic and Quartic Functional Equations in Non-Archimedean Spaces

We prove generalized Hyers-Ulam–Rassias stability of the cubic functional equation f(kx+y)+f(kx?y)=k[f(x+y)+f(x?y)]+2(k ³?k)f(x) for all \(k\in \Bbb{N}\) and the quartic functional equation f(kx+y)+f(kx?y)=k ²[f(x+y)+f(x?y)]+2k ²(k ²?1)f(x)?2(k ²?1)f(y) for all \(k\in \Bbb{N}\) in non-Archimedean normed spaces.     

Boolean Lattices: Ramsey Properties and Embeddings

A subposet Q ^′ of a poset Q is a copy of a poset P if there is a bijection f between elements of P and Q ^′ such that x ≤ y in P iff f(x) ≤ f(y) in Q. For posets P, P ^′, let the poset Ramsey number R(P, P ^′) be the smallest N such that no matter how the elements of the Boolean lattice Q _N are colored red and blue, there is a copy of P with all red elements or a copy of P ^′ with all blue elements. We provide some general bounds on R(P, P ^′) and focus on the situation when P and P ^′ are both Boolean lattices. In addition, we give asymptotically tight bounds for the number of copies of Q _n in Q _N and for a multicolor version of a poset Ramsey number.     

When does the zero-one <Emphasis Type="Italic">k</Emphasis>-law fail?

The limit probabilities of the first-order properties of a random graph in the Erd?s–Rényi model G(n, n^?α), α ∈ (0, 1), are studied. A random graph G(n, n^?α) is said to obey the zero-one k-law if, given any property expressed by a formula of quantifier depth at most k, the probability of this property tends to either 0 or 1. As is known, for α = 1? 1/(2^k?1 + a/b), where a > 2^k?1, the zero-one k-law holds. Moreover, this law does not hold for b = 1 and a ≤ 2^k?1 ? 2. It is proved that the k-law also fails for b > 1 and a ≤ 2^k?1 ? (b + 1)².     

Optimal Embeddings of Bessel-Potential-Type Spaces into Generalized Hölder Spaces Involving <Emphasis Type="Italic">k</Emphasis>-Modulus of Smoothness

We establish necessary and sufficient conditions for embeddings of Bessel potential spaces H ^σ X(IR ⁿ ) with order of smoothness σ?∈?(0, n), modelled upon rearrangement invariant Banach function spaces X(IR ⁿ ), into generalized Hölder spaces (involving k-modulus of smoothness). We apply our results to the case when X(IR ⁿ ) is the Lorentz-Karamata space \(L_{p,q;b}({{\rm I\kern-.17em R}}^n)\). In particular, we are able to characterize optimal embeddings of Bessel potential spaces \(H^{\sigma}L_{p,q;b}({{\rm I\kern-.17em R}}^n)\) into generalized Hölder spaces. Applications cover both superlimiting and limiting cases. We also show that our results yield new and sharp embeddings of Sobolev-Orlicz spaces W ^k?+?1 L ^n/k(logL) ^α (IR ⁿ ) and W ^k L ^n/k(logL) ^α (IR ⁿ ) into generalized Hölder spaces.     

Relative widths of Sobolev classes in the uniform and integral metrics

Let W_p^r be the Sobolev class consisting of 2π-periodic functions f such that ‖f^(r)‖_p ≤ 1. We consider the relative widths d_n(W_p^r, MW_p^r, L_p), which characterize the best approximation of the class W_p^r in the space L_p by linear subspaces for which (in contrast to Kolmogorov widths) it is additionally required that the approximating functions g should lie in MW_p^r, i.e., ‖g^(r)‖_p ≤ M. We establish estimates for the relative widths in the cases of p = 1 and p = ∞; it follows from these estimates that for almost optimal (with error at most Cn^?r, where C is an absolute constant) approximations of the class W_p^r by linear 2n-dimensional spaces, the norms of the rth derivatives of some approximating functions are not less than cln min(n, r) for large n and r.     

Series by Haar system with monotone coefficients

Let χ = {χ _n } _n=0 ^∞ be the Haar system normalized in L ²(0, 1) and M = {M _s } _s=1 ^∞ be an arbitrary, increasing sequence of nonnegative integers. For any subsystem of χ of the form {φ _k } = χS = {χ _n } _n∈S , where S = S(M) = {n _k } _k=1 ^∞ = {n ∈ V[p]: p ∈ M}, V[0] = {1, 2} and V[p] = {2 ^p + 1, 2 ^p + 2, …, 2 ^p+1} for p = 1, 2, … a series of the form Σ _i=1 ^∞ a _i φ _i with a _i ↘ 0 is constructed, that is universal with respect to partial series in all classes L ^r (0, 1), r ∈ (0, 1), in the sense of a.e. convergence and in the metric ofL ^r (0, 1). The constructed series is universal in the class of all measurable, finite functions on [0, 1] in the sense of a.e. convergence. It is proved that there exists a series by Haar system with decreasing coefficients, which has the following property: for any ? > 0 there exists a measurable function µ(x), x ∈ [0, 1], such that 0 ≤ µ(x) ≤ 1 and |{x ∈ [0, 1], µ(x) ≠ = 1}| < ?, and the series is universal in the weighted space L _µ[0, 1] with respect to subseries, in the sense of convergence in the norm of L _µ[0, 1].     

On homogenization for non-self-adjoint locally periodic elliptic operators

In this note we consider the homogenization problem for a matrix locally periodic elliptic operator on R ^d of the form A ^ε = ?divA(x, x/ε)?. The function A is assumed to be Hölder continuous with exponent s ∈ [0, 1] in the “slow” variable and bounded in the “fast” variable. We construct approximations for (A ^ε ? μ)^?1, including one with a corrector, and for (?Δ) ^s/2(A ^ε ? μ)^?1 in the operator norm on L ₂(R ^d ) ⁿ . For s ≠ 0, we also give estimates of the rates of approximation.     

Distance domination of generalized de Bruijn and Kautz digraphs

Let G = (V,A) be a digraph and k ≥ 1 an integer. For u, v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G _B (n, d) and generalized Kautz digraphs G _K (n, d) are good candidates for interconnection networks. Denote Δ _k := (∑ _j=0 ^k d ^j )^?1. F. Tian and J. Xu showed that ?nΔ _k ? γ _k (G _B (n, d)) ≤?n/d ^k? and ?nΔ _k ? ≤ γ _k (G _K (n, d)) ≤ ?n/d ^k ?. In this paper, we prove that every generalized de Bruijn digraph G _B (n, d) has the distance k-domination number ?nΔ _k ? or ?nΔ _k ?+1, and the distance k-domination number of every generalized Kautz digraph G _K (n, d) bounded above by ?n/(d ^k?1+d ^k )?. Additionally, we present various sufficient conditions for γ _k (G _B (n, d)) = ?nΔ _k ? and γ _k (G _K (n, d)) = ?nΔ _k ?.     

Nikol’skii inequality between the uniform norm and <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">q</Emphasis></Subscript>-norm with jacobi weight of algebraic polynomials on an interval

We study the Nikol’skii inequality for algebraic polynomials on the interval [?1, 1] between the uniform norm and the norm of the space L _q ^(α,β) , 1 ≤ q < ∞, with the Jacobi weight ?(α,β)(x) = (1 ? x) ^α (1 + x) ^β , α ≥ β > ?1. We prove that, in the case α > β ≥ ?1/2, the polynomial with unit leading coefficient that deviates least from zero in the space L _q ^(α+1,,β) with the Jacobi weight ? ^(α+1,β)(x) = (1?x) ^α+1(1+x) ^β is the unique extremal polynomial in the Nikol’skii inequality. To prove this result, we use the generalized translation operator associated with the Jacobi weight. We describe the set of all functions at which the norm of this operator in the space L _q ^(α,β) for 1 ≤ q < ∞ and α > β ≥ ?1/2 is attained.     

On a functional equation related to derivations in prime rings

In this paper we prove the following result. Let m ≥ 1, n ≥ 1 be fixed integers and let R be a prime ring with m + n + 1 ≤ char(R) or char(R) = 0. Suppose there exists an additive nonzero mapping D : R → R satisfying the relation 2D(x ^n+m+1) = (m + n + 1)(x ^m D(x)x ⁿ + x ⁿ D(x)x ^m ) for all \({x\in R}\). In this case R is commutative and D is a derivation.     

Inversion and subspaces of a finite field

Consider two F _q -subspaces A and B of a finite field, of the same size, and let A ^?1 denote the set of inverses of the nonzero elements of A. The author proved that A ^?1 can only be contained in A if either A is a subfield, or A is the set of trace zero elements in a quadratic extension of a field. Csajbók refined this to the following quantitative statement: if A ^?1 ? B, then the bound |A ^?1∩B| ≤ 2|B|/q ? 2 holds. He also gave examples showing that his bound is sharp for |B| ≤ q ³. Our main result is a proof of the stronger bound |A ^?1 ∩ B| ≤ |B|/q · (1 + O _d (q ^?1/2)), for |B| = q ^d with d > 3. We also classify all examples with |B| ≤ q ³ which attain equality or near-equality in Csajbók’s bound.