Stability preservation theorems

The basic result of the paper is the main theorem worded as follows. Let {ie155-01} be a valued field such that {ie155-02} has characteristic p > 0 and let {ie155-03} be an extension of valued fields satisfying the following conditions: (i) there exists a set {ie155-04} for which {ie155-05} is a separating transcendence basis for a field {ie155-06} over F_R; (ii) Γ _R is p-pure in {ie155-07}, i.e., {ie155-08} does not contain elements of order p; (iii) there exists a set B₁ ⊂ F₀^× such that the family {ie155-09} is linearly independent in the elementary p-group {ie155-10}; (iv) F₀ is algebraic over F(B₀ ⋃ B₁). Then the property of being stable for {ie155-11} implies being stable for {ie155-12}. Supported by the Council for Grants (under RF President) and State Aid of Leading Scientific Schools (grant NSh-344.2008.1) and by RFBR (grant No. 08-01-00442-a). __________ Translated from Algebra i Logika, Vol. 47, No. 3, pp. 269–287, May–June, 2008.     

EXISTENCE OF PERIODIC SOLUTIONS OF SYSTEM OF DIFFERENCE EQUATIONS

This paper studies the nonautonomous nonlinear system of difference equationsΔx(n)=A(n)x(n)+f(n,x(n)),n∈Z,(*) where x(n)∈R~N,A(n)=(a_(ij)(n))N×N is an N×N matrix,with a-(ij)∈C(R,R) for i,j= 1,2,3,...,N,and f=(f_1,f_2,...,f_N)~T∈C(R×R~N,R~N),satisfying A(t+ω)=A(t),f(t+ω,z)=f(t,z) for any t∈R,(t,z)∈R×R~N andωis a positive integer.Sufficient conditions for the existence ofω-periodic solutions to equations (*) are obtained.     

Derivation of prime rings of positive characteristic

Let L be a finite-dimensional differential Lie algebra acting on a prime ring R and let the inner part {ie49-1} of L be quasi-Frobenius. Then a constant ring R^L is prime iff {ie49-2} is a differentially simple ring. A ring of constants is semiprime iff {ie49-3} is a direct sum of differentially simple rings, and the prime dimension of a constant ring is equal to the number of differentially simple summands {ie49-4}. The Galois closure of L is obtained from L by adding all the inner derivations of a symmetric Martindale quotient ring which agree with elements from {ie49-5}. Supported by RFFR grant No. 93-01-16171 and by ISF grant RPS000-RPS300. Translated fromAlgebra i Logika, Vol. 35, No. 1, pp. 88–104, January–February, 1996.     

New axiomatizations for logics with generalized quantifiers

We give a complete axiomatization for admissible fragments ofL {ie257-1}(Q). This axiomatization implies syntactically Gregory’s characterization ofL {ie257-2} sentences with no uncountable models ([5]). This is then extended to stationary logic. To obtain these results, we employ Ressayre’s methods ([16], [17]) augmented with an application of game sentences. In section 4 we prove a result emphasizing the naturalness of Gregory’s result. Research supported by a grant from the National Research Council of Canada.     

The arithmetical hierarchy of nilpotent torsion-free groups

Previously, N. Khisamiev proved that all {ie172-1} Abelian torsion-free groups are {ie172-2}. We prove that for the class of nilpotent torsion-free groups, the situation is different: even the quotient group F of a {ie172-3} nilpotent group of class 2 by its periodic part may fail to have a {ie172-4}. Translated fromAlgebra i Logika, Vol. 35, No. 3, pp. 308–313, May–June, 1996.     

Generating combinations in parallel

A parallel algorithm for generating all combinations ofm out ofn items in lexicographic order is presented. The algorithm usesm processors and runs inO(nCm) time. The cost of the algorithm, which is the parallel running time multiplied by the number of processors used, is optimal to within a constant multiplicative factor in view of the (ncm*m) lower bound on the number of operations required to solve this problem using a sequential computer.This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grant NSERC-A3336.     

Periodic groups saturated by finite simple groups <Emphasis Type="Italic">U</Emphasis><Subscript>3</Subscript>(2<Superscript>m</Superscript>)

Let {ie166-01} be a set of finite groups. A group G is said to be saturated by the groups in {ie166-02} if every finite subgroup of G is contained in a subgroup isomorphic to a member of {ie166-03}. It is proved that a periodic group G saturated by groups in a set {U₃(2^m) | m = 1, 2, …} is isomorphic to U₃(Q) for some locally finite field Q of characteristic 2; in particular, G is locally finite. __________ Translated from Algebra i Logika, Vol. 47, No. 3, pp. 288–306, May–June, 2008.     

On the product of the distances of a point from the vertices of a polytope

Letx ₁,...,x _m be points in the solid unit sphere ofE _n and letx belong to the convex hull ofx ₁,...,x _m. Then . This implies that all such products are bounded by (2/m) ^m (m −1) ^m−1. Bounds are also given for other normed linear spaces. As an application a bound is obtained for |p(z ₀)| where andp′(z ₀)=0.     

Nilpotent groups admitting an almost regular automorphism of order four

We consider locally nilpotent periodic groups admitting an almost regular automorphism of order 4. The following are results are proved: (1) If a locally nilpotent periodic group G admits an automorphism ϕ of order 4 having exactly m<∞ fixed points, then (a) the subgroup {ie176-1} contains a subgroup of m-bounded index in {ie176-2} which is nilpotent of m-bounded class, and (b) the group G contains a subgroup V of m-bounded index such that the subgroup {ie176-3} is nilpotent of m-bounded class (Theorem 1); (2) If a locally nilpotent periodic group G admits an automorphism ϕ of order 4 having exactly m<∞ fixed points, then it contains a subgroup V of m-bounded index such that, for some m-bounded number f(m), the subgroup {ie176-4}, generated by all f(m) th powers of elements in {ie176-5} is nilpotent of class ≤3 (Theorem 2). Supported by RFFR grant No. 94-01-00048 and by ISF grant NQ7000. Translated fromAlgebra i Logika, Vol. 35, No. 3, pp. 314–333, May–June, 1996.     

Linear and nonlinear methods of relief approximation

In this paper, we compare the effectiveness of free (nonlinear) relief approximation, equidistant relief approximation, and polynomial approximation {ie129-01}, and {ie129-02} of an individual function ?(x) in the metric {ie129-03}, where {ie129-04} is the unit ball |x| ≤ 1 in the plane ?². The notation we use is the following: {fx129-01}. Here {ie129-05} is the set of all N-term linear combinations of functions of the plane-wave type {fx129-02} with arbitrary profiles W _j (x), x ∈ ?¹ and transmission directions {θ _j } ₁ ^N ; {ie129-06} is the subset of {ie129-07} associated with N equidistant directions; {fx129-03} denotes the subspace of algebraic polynomials of degree less than or equal to N ? 1 in two real variables. Obviously, the inequalities {ie129-08} hold.We state the following model problem. What are the functions which satisfy the relation {ie129-09}, i.e., where the nonlinear approximation {ie129-10} is more effective than a linear one? This effect has been proved for harmonic functions, namely, for any ε > 0 there exists c _ε > 0 such that if Δ?(x) = 0, |x| < 1, and ? ∈ {ie129-11}, then {fx129-04}. On the other hand, {ie129-12}. Thus, {ie129-13} has an “almost squared effectiveness” of {ie129-14} for ? = ?_harm. However, this ultra-high order of approximation is obtained via a collapse of wave vectors.On the other hand, the nonlinearity of {ie129-15} which corresponds to the freedom of choice of wave vectors does not much improve the order of approximation, for instance, for all the radial functions. If {ie129-16}, then {ie129-17} and {ie129-18}.The technique we use is the Fourier-Chebyshev analysis (which is related to the inverse Radon transform on {ie129-19}) and a duality between the relief approximation problem and the optimization of quadrature formulas in the sense of Kolmogorov-Nikolskii [14] for trigonometric polynomial classes.     

On exposed functions in Bernstein spaces

For σ > 0, the Bernstein space {ie427-01} consists of those L ¹(ℝ) functions whose Fourier transforms are supported by [−σ, σ]. Since {ie427-02} is separable and dual to some Banach space, the closed unit ball {ie427-03} of {ie427-04} has sufficiently large sets of both exposed and strongly exposed points: {ie427-05} coincides with the closed convex hull of its strongly exposed points. We investigate some properties of exposed points, construct several examples, and obtain as corollaries relations between the sets of exposed, strongly exposed, weak* exposed, and weak* strongly exposed points of {ie427-06}.     

Estimates for the real taylor coefficients in one function class

Considering the class {ie48-01} of analytic functions {ie48-02} in the unit disk with a _m,n ε ℝ and the nonvanishing nth divided difference [F(z);z ₀, ⋯, z _n ] for all z ₀, ℝ, z _n ∈ E we establish that {ie48-03}, where {ie48-04}. If n is an odd number then {ie48-05}.     

A fixed-parameter-tractable algorithm for set packing

1. IntroductionIt is a useful and challenging task to find efficient algorithms for many computationalhard problems. Recently, the research on Fixed-Parameter nactable Theory arouses muchinterest. FOr example, different fixed- p ax amet er- t rac t ab le- algori t hms for many well- knowndecisio11 pruble11ls illc1udi11g 3-dimellsio11al IIlatchiIlg: a11d vertex--cover Problen1 have beenPrese11ted in [1 8]. Jia11er Chen, DoIlald K. FYiesen al1d Weijia Jia proPosed a coll1pletelynew appro…     

A fast and simple algorithm for the computation of Legendre coefficients

We present an O(N log N){\mathcal{O}({N\,{\rm log}\,N})} algorithm for the calculation of the first N coefficients in an expansion of an analytic function in Legendre polynomials. In essence, the algorithm consists of an integration of a suitably weighted function along an ellipse, a task which can be accomplished with Fast Fourier Transform, followed by some post-processing. The mathematical underpinning of this algorithm is an old formula that expresses expansion coefficients [^(f)]_m{\hat{f}_m} as infinite linear combinations of derivatives. We evaluate the latter with the Cauchy theorem, thereby expressing each [^(f)]_m{\hat{f}_m} as a scaled integral of f(z)j_m(z)/z^m+1{f(z)\varphi_m(z)/z^{m+1}} along an appropriate contour, where j_m{\varphi_m} is a slowly converging hypergeometric function. Next, we transform j_m{\varphi_m} into another hypergeometric function which converges rapidly. Once we replace the latter function by its truncated Taylor expansion and choose an appropriate elliptic contour, we obtain an expression for the [^(f)]_m{\hat{f}_m}s which is amenable to rapid computation.     

Are rational combinations of\left\{ {X^{\lambda _n } } \right\},\lambda _n \geqslant 0 always dense in C[0, ∞]?always dense in C[0, ∞]?

The present paper shows that for any sequence of nonnegative numbers {λ_m} with, infinitely many distinct elements, the rational combinations of $\left\{ {X^{\lambda _n } } \right\}$ form a dense set (in the uniform norm on the positive axis) in the space of continuous fuctions f on [0,∞) with $\mathop {\lim }\limits_{x \to \infty } f\left( x \right) = f\left( 0 \right)$ . The last condition can be removed when {λ_m} has an infinity cluster point.     

多背包问题的半定松驰算法

The multiple knapsack problem denoted by MKP (B,S,rn,n) can be defined as follows. A set B of n items and a set S of rn knapsacks are given such that each item j has a profit pi and weight wj,and each knapsack i has a capacity Ci. The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks. MKP (B,S,m,n) is strongly NP-Complete and no polynomial time approximation algorithm can have an approximation ratio better than 0.5. In the last ten years,semi-definite programming has been empolyed to solve some combinatorial problems successfully. This paper firstly presents a semi-definite relaxation algorithm (MKPS) for MKP (B,S,rn,n). It is proved that MKPS have a approximation ratio better than 0. 5 for a subclass of MKP (B,S,m,n) with n≤100, m≤5 and max^nj=1{wj}/min^mi=1={Ci}≤2/3.     

An inequality relating to triple product integrals of laguerre functions

IfL _n(x) is thenth Laguerre polynomial and {ie45-1}, then we can expand the functions {ie45-2} over (0, ∞) in terms of the set {ie45-3}, i.e., {ie45-4}. In this paper we prove, an old-standing conjecture that (−1) ^tK_rt>0 for 0≦t≦r (r=0,1,…); i.e., that, in the sense defined by Trench, the set {ie45-5} is alternating with respect to the set {ie45-6}.     

Linear methods for approximation of some classes of holomorphic functions from the Bergman space

We construct a linear method {ie910-01} for the approximation (in the unit disk) of classes of holomorphic functions {ie910-02} that are the Hadamard convolutions of the unit balls of the Bergman space A _p with reproducing kernels {ie910-03}. We give conditions for ψ under which the method {ie910-04} approximates the class {ie910-05} in the metrics of the Hardy space H _s and the Bergman space A _s , 1 ≤ s ≤ p, with an error that coincides in order with the value of the best approximation by algebraic polynomials. Translated from in Ukrains'kyi Matematychnyi Zhurnal, Vol. 60, No. 6, pp. 783–795, June, 2008.     

The formula for the number of order-preserving selfmappings of a fence

LetY be a fence of sizem andr=?m?1/2?. The numberb(m) of order-preserving selfmappings ofY is equal toA _r-B_r-C_r-D_r, where, ifm is odd, $$\begin{gathered} A_r = 2(r + 1)\sum\limits_{s = 0}^r {\left( {\begin{array}{*{20}c} {r + s} \\ {2s} \\ \end{array} } \right)} 4^s , B_r = 2r\sum\limits_{s = 1}^r {\left( {\begin{array}{*{20}c} {r + s} \\ s \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {r - 1} \\ {s - 1} \\ \end{array} } \right),} \hfill \\ C_r = 4r\sum\limits_{s = 0}^{r - 1} {\left( {\begin{array}{*{20}c} {r + s} \\ s \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {r - 1} \\ s \\ \end{array} } \right), D_r = \sum\limits_{s = 0}^{r - 1} {(2s + 1)} \left( {\begin{array}{*{20}c} {r + s - 1} \\ s \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {r - 1} \\ s \\ \end{array} } \right)} \hfill \\ \end{gathered} $$ . Ifm is even, a similar formula forb(m) is true. The key trick in the proof is a one-to-one correspondence between order-preserving selfmappings ofY and pairs consisted of a partition ofY and a strictly increasing mapping of a subfence ofY toY.     

Varieties ofl-groups are finitely based

We deal with varieties of lattice-ordered groups {ie149-1} defined by the identity [xⁿ, yⁿ]=e. The structure of subdirectly indecomposable l-groups in the variety {ie149-2} is studied, and we establish that l-varieties satisfying the identity [xⁿ, yⁿ]=e and generated by a finitely generated l-group are finitely based. It is shown that l-varieties {ie149-3} with finite axiomatic rank {ie149-4} also have finite bases of identities. Translated fromAlgebra i Logika, Vol. 35, No. 3, pp. 268–287, May–June, 1996.