An algorithm for constructing an optimal structural schedule

The article is devoted to the problem of finding an optimal schedule for a class of functionals ƒ which allows for the existence of a structural set of activities. The functionalƒ(R), where, is defined in the following way: where {_i(t)} is a structural set of functions, and the function F is defined on any finite set of arguments and satisfies the following conditions: 1)F(x)=(x); 2) F(x₁,x₂)=(x₁,x₂), F(x₁,x₂,...x₃)= (x₁, F(x₂,...,x_s)), S2; 3) and do not decrease in each of their arguments, and moreover, 3a) strictly increases with the increase of both arguments, 3b) if (x₁,x₂)>(x₁, x₂ (x₂, x₃)> (x₂,x₃), then F(x₁,x₂,x₃)>F(x₁,x₂,x₃).Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 124, pp. 5–20, 1983.     

On the quantifier complexity of Δ<Subscript> n+1</Subscript> (T)– induction

In this paper we continue the study of the theories I _n+1 (T), initiated in [7]. We focus on the quantifier complexity of these fragments and theirs (non)finite axiomatization. A characterization is obtained for the class of theories such that I _n+1 (T) is _n+2 –axiomatizable. In particular, I _n+1 (I _n+1 ) gives an axiomatization of Th _n+2 (I _n+1 ) and is not finitely axiomatizable. This fact relates the fragment I _n+1 (I _n+1 ) to induction rule for _n+1 –formulas. Our arguments, involving a construction due to R. Kaye (see [9]), provide proofs of Parsons conservativeness theorem (see [16]) and (a weak version) of a result of L.D. Beklemishev on unnested applications of induction rules for _n+2 and _n+1 formulas (see [2]).Research partially supported by grant PB96–1345 (Spanish Goverment)Mathematics Subject Classification (2000): 03F30, 03H15     

A multiple recursive non-linear congruential pseudo random number generator

On-linear multiple recursive congruential pseudo random number generator with prime modulus p is introduced. Let x, n0, be the sequence generated by a usual linear (r+1)-step recursive congruential generator with prime modulus p and denote by N(n), n0, the sequence of non-negative integers with x_N(n)0 (mod p). The non-linear generator is defined by z_nx_N(n)+1·x _N(n) ^–1 (mod p), n0, where x _N(n) ^–1 denotes the inverse element of x_N(n) in the Galois field GF(p). A condition is given which ensures that the generated sequence is purely periodic with period length p^r and all (p–1)^r r-tupels (y₁,...,y_r) with 1y₁,...,y_rp are generated once per period when r-tupels of consecutive numbers of the generated sequence are formed. For r=1 this generator coincides with the generator introduced by Eichenauer and Lehn [2].     

Necessary conditions for the existence of divisible designs

BOSE and CONNOR [2] proved that a symmetric regular divisible design with w classes of sizes g and joining numbers ₁ and ₂ must satisfy for every prime p the arithmetic condition (d₁, (–1)^sw)_p(d₂,(–l)^tg^w)_p=1, where d₁=k²–v₂, d₂= k–₁ s=(w-1)(w-2)/2, t=(v-w)(v-w-1)/2 and (*,*) is the Hilbert symbol. We show that if in addition _{1 2} and the design is fully symmetric divisible then (d₁, (–1)^s w)_p=(d₂, (–1)^tg^w)=1. Our assumption is by a result of CONNOR [5] fulfilled, if d₁ and ₁–₂ are relatively prime. Thus, we can exclude parameters not accessible to the Bose-Connor-Theorem. Our result can be derived from a theorem of RAGHAVARAO [9], and we give the precise assumptions of this theorem. We also discuss arithmetic restrictions for divisible designs which satisfy diverse other rules for the intersection numbers and generalize a result of DEMBOWSKI [6; 2.1.11].Dedicated to Professor Benz on occasion of his sixtieth birthday     

Best approximations of continuous functions by spline functions

An investigation of the approximation on [0, 1] of functionsf (x) by spline functions s(f,; x) of degree 2r-1 and of deficiency r (r>1) depending on the vector function = ₁ (x),..., _r-1(x) and interpolatingf (x) at fixed points. For the optimal choice of the vector ₀, exact estimates are obtained of the norms f(x)-s (f, ₀; x)_C[0,1] and f (x)-s (f, ₀; x)_{L[0, 1]} on the function classes H Translated from Matematicheskie Zametki, Vol. 8, No. 1, pp. 41–46, July, 1970.In conclusion we would like to thank N. P. Korneichuk for suggesting this problem and for his valuable advice.     

On the Ranked Excursion Heights of a Kiefer Process

Let (K(s,t), 0s1, t1) be a Kiefer process, i.e., a continuous two-parameter centered Gaussian process indexed by [0,1]×₊ whose covariance function is given by (K(s₁,t₁) K(s₂,t₂))=(s₁s₂-s₁s₂)t₁t₂, 0s₁, s₂1, t₁, t₂ 0. For each t>0, the process K(·,t) is a Brownian bridge on the scale of . Let M ₁ ^* (t) M ₂ ^* (t) M _j ^* (t) 0 be the ranked excursion heights of K(,t). In this paper, we study the path properties of the process tM _j ^* (t). Two laws of the iterated logarithm are established to describe the asymptotic behaviors of M _j ^* (t) as t goes to infinity.     

On Piecewise-Constant Approximation of Continuous Functions of n Variables in Integral Metrics

We consider the approximation by piecewise-constant functions for classes of functions of many variables defined by moduli of continuity of the form (₁, ..., _n ) = ₁(₁) + ... + _n ( _n ), where _i ( _i ) are ordinary moduli of continuity that depend on one variable. In the case where _i ( _i ) are convex upward, we obtain exact error estimates in the following cases: (i) in the integral metric L ₂ for (₁, ..., _n ) = ₁(₁) + ... + _n ( _n ); (ii) in the integral metric L _p (p 1) for (₁, ..., _n ) = c ₁₁ + ... + c _{n n} ; (iii) in the integral metric L _{(2, ..., 2, 2r)} (r = 2, 3, ...) for (₁, ..., _n ) = ₁(₁) + ... + _{n – 1}( _{n – 1}) + c _{n n} .     

On a generalization of the Cauchy functional equation

Summary While looking for solutions of some functional equations and systems of functional equations introduced by S. Midura and their generalizations, we came across the problem of solving the equationg(ax + by) = Ag(x) + Bg(y) + L(x, y) (1) in the class of functions mapping a non-empty subsetP of a linear spaceX over a commutative fieldK, satisfying the conditionaP + bP P, into a linear spaceY over a commutative fieldF, whereL: X × X Y is biadditive,a, b K\{0}, andA, B F\{0}. Theorem.Suppose that K is either R or C, F is of characteristic zero, there exist A ₁,A ₂,B ₁,B ₂, F\ {0}with L(ax, y) = A ₁ L(x, y), L(x, ay) = A ₂ L(x, y), L(bx, y) = B ₁ L(x, y), and L(x, by) = B ₂ L(x, y) for x, y X, and P has a non-empty convex and algebraically open subset. Then the functional equation (1)has a solution in the class of functions g: P Y iff the following two conditions hold: L(x, y) = L(y, x) for x, y X, (2)if L 0, then A ₁ =A ₂,B ₁ =B ₂,A = A ₁ ² ,and B = B ₁ ² . (3) Furthermore, if conditions (2)and (3)are valid, then a function g: P Y satisfies the equation (1)iff there exist a y ₀ Y and an additive function h: X Y such that if A + B 1, then y ₀ = 0;h(ax) = Ah(x), h(bx) =Bh(x) for x X; g(x) = h(x) + y ₀ + 1/2A ₁ ^-1 B ₁ ^-1 L(x, x)for x P.     

The Dirichlet Laplacian on Finely Open Sets

For any decreasing sequence of bounded finely open sets D_i R^N it is shown that, for every n, the nth eigenvalue _n ( D_i) of the Dirichlet laplacian A ( D_i ) on D_i converges to _n ( D ) (the nth eigenvalue of A ( D ) ), where D denotes the fine interior of D_i. Likewise, A ( D_i )^-1 A ( D )^-1 in operator norm. Similar results are obtained for increasing or just order convergent sequences ( D_i ). Furthermore, A ( D )^-1 is identified with the integral operator on L² ( D ) whose kernel is Green's function for D.     

More on P-Stable Convex Sets in Banach Spaces

We study the asymptotic behavior and limit distributions for sums S _n =b_n ^-1 _i=1 ⁿ _i,where _i, i 1, are i.i.d. random convex compact (cc) sets in a given separable Banach space B and summation is defined in a sense of Minkowski. The following results are obtained: (i) Series (LePage type) and Poisson integral representations of random stable cc sets in B are established; (ii) The invariance principle for processes S _n(t) =b_n ^-1 _i=1 ^[nt] _i, t[0, 1], and the existence of p-stable cc Levy motion are proved; (iii) In the case, where _i are segments, the limit of S _n is proved to be countable zonotope. Furthermore, if B = R ^d , the singularity of distributions of two countable zonotopes Y_{p 1}, ₁,Y_{p 2}, ₂, corresponding to values of exponents p ₁, p ₂ and spectral measures ₁, ₂, is proved if either p ₁ p ₂ or _{1 2}; (iv) Some new simple estimates of parameters of stable laws in R ^d , based on these results are suggested.     

Monomial gorenstein curves in A4 as set-theoretic complete intersections

It is shown that if the prime ideal ,, x₄], k an arbitrary field, has generic zero x_i=tⁿ _i, n_i positive integers with g.c.d. equal l, l i 4, then P(S) is a set-theoretic complete intersection if the numerical semigroup S=1,, n₄> is symmetric (i.e. if the extension of P(S) in k[[x₁,, x₄]] is a Gorenstein ideal).     

Random Logistic Maps. I

Let {C _i} ₀ be a sequence of independent and identically distributed random variables with vales in [0, 4]. Let {X _n} ₀ be a sequence of random variables with values in [0, 1] defined recursively by X _n+1=C _n+1 X _n(1–X _n). It is shown here that: (i) E ln C ₁<0X _n0 w.p.1. (ii) E ln C ₁=0X _n0 in probability (iii) E ln C ₁>0, E |ln(4–C ₁)| such that (0, 1)=1 and is invariant for {X _n}. (iv) If there exits an invariant probability measure such that {0}=0, then E ln C ₁>0 and – ln(1–x) (dx)=E ln C ₁. (v) E ln C ₁>0, E |ln(4–C ₁)|< and {X _n} is Harris irreducible implies that the probability distribution of X _n converges in the Cesaro sense to a unique probability distribution on (0, 1) for all X ₀0.     

Asymptotic behavior of the dwell time distribution for a random walk on a positive semi-axis

Let ₁, ₂, ... be a sequence of independent identically distributed random variables with zero means. We consider the functional _n = _k=o ⁿ (S _k ) where S₁=0, S_k= _i=1 ^k _i (k1) and(x)=1 for x0,(x) = 0 for x<0. It is readily seen that _n is the time spent by the random walk S_n, n0, on the positive semi-axis after n steps. For the simplest walk the asymptotics of the distribution P (_n = k) for n and k, as well as for k = O(n) and k/n<1, was studied in [1]. In this paper we obtain the asymptotic expansions in powers of n^–1 of the probabilities P(h_n = nx) and P(nx_{1 n} nx₂) for 0<₁, x = k/n ₂<1, 0<₁x₁2₂<1.Translated from Matematicheskie Zametki, Vol. 15, No. 4, pp. 613–620, April, 1974.The author wishes to thank B. A. Rogozin for valuable discussions in the course of his work.     

On convergence subsystems of orthonormal systems

It is proved that for any sequence {R _k} _k=1 of real numbers satisfyingR _kk (k1) andR _k=o(k log₂ k),k, there exists an orthonormal system {n _k(x)} _n=1 ,x (0;1), such that none of its subsystems {n _k(x)} _k=1 withn _kR_k (k1) is a convergence subsystem.     

Eine Klasse nicht einbettbarer reeller Laguerre-Ebenen

Replace in the parabolic model of the classical Laguerre-Plane the parabolas y=a(x–b)²+c, a0, by the curves y=af(x–b)+c with f(x)= if x0, and f(x)=(–x)^r ₂ if x<0. For each pair r₁, r₂>1 we obtain again a Laguerre-Plane (r₁,r₂).(r₁,r₂) can be embedded only if r₁=r₂=2.     

Residues of higher order and holomorphic vector fields

LetX ₁ andX ₂ be two holomorphic vector fields on a manifoldV with complex dimensionp. Assume that they have the same singular set . For all , it is known (after Chern-Bott) that each of the vector fields defines a residual characteristic classC ₁(V,X ₁)(resp.C ₁(V,X ₂)) inH ^2p (V, V-), which is a lift of the usual characteristic classC ₁ (V) of the tangent bundle. The differenceC ₁ (V,X ₂)-C ₁ (V,X ₁) belongs then to the image of in the exact sequence. In fact, there exists a canonical liftC ₁ (V,X ₁,X ₂) of this difference inH ^2p–1(V-): we will call itthe residual class of order 2 (associated toI, X ₁ andX ₂). This class is localized near the points whereX ₁ andX ₂ are colinear: we will explain this precisely in terms of Grothendieck residues. The formula that we obtain can be interpreted as a generalization of the purely algebraic identity, obtained from the general one as a byproduct: where ( ₁, , _p) and ( ₁,, _p ) denote two families of non-zero complex numbers, such that all denominators in this formula do not vanish. (This identity corresponds in fact to the case whereX ₁ andX ₂ are non-degenerate at the same isolated singular point.)If the _i 's (1ip) depend now differentiably (resp. holomorphically) on a real (resp. complex) parametert then, denoting by the derivative with respect tot, and assuming all numbers lying in a denominator not to be 0, we can deduce from the above identity the following derivation formula:     

Isomorphism of one-place functors Ext

Let be an associative ring with identity. One considers the category of left (unitary) -modules m and also the contravariant and the covariant functors Ext ¹ ( ,A) and Ext ¹ (A, ): M_z M. One proves the following results: (1) If the homomorphism of -modules A B induces an isomorphism Ext ¹ ( ,A)Ext ¹ ( ,B), then there exist injective -modules J₁ and J₂ such that AJ₁BJ₂. (2) Every functorial morphism Ext ¹ ( ,A)Ext ¹ ( ,B) induces a certain homomorphism of -modules AB. One also obtains a dual result.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 112, pp. 71–74, 1981.     

Integral representation of linear operators

In this paper we obtain necessary and sufficient conditions in order that a linear operator, acting in spaces of measurable functions, should admit an integral representation. We give here the fundamental results. Let (T_i, _i) (i=1,2) be spaces of finite measure, and let (T,) be the product of these spaces. Let E be an ideal in the space S(T₁, ₁) of measurable functions (i.e., from |e₁||e₂|, e₁ S (T₁, ₁), e₂E it follows that e₁E). THEOREM 2. Let U be a linear operator from E into S(T₂, ₂). The following statements are equivalent: 1) there exists a-measurable kernel K(t,S) such that (Ue)(S)=K(t,S) e(t)d(t) (eE); 2) if 0e_nE (n=1,2,...) and e_n0 in measure, then (Ue_n)(S) 0 ₂ a.e. THEOREM 3. Assume that the function (t,S) is such that for any eE and for s a.e., the ₂-measurable function Y(S)=(t,S)e(t)d ₁(t) is defined. Then there exists a-measurable function K(t,S) such that for any eE we have (t,S)e(t)d ₁(t)=K(t,S)e(t)d ₁(t) ₁a.e.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 47, pp. 5–14, 1974.     

Cross-monotone subsequences

Two finite real sequences (a ₁,...,a _k ) and (b ₁,...,b _k ) are cross-monotone if each is nondecreasing anda _i+1–a _i b _i+1–b _i for alli. A sequence (₁,..., _n ) of nondecreasing reals is in class CM(k) if it has disjointk-term subsequences that are cross-monotone. The paper shows thatf(k), the smallestn such that every nondecreasing (₁,..., _n ) is in CM(k), is bounded between aboutk ²/4 andk ₂/2. It also shows thatg(k), the smallestn for which all (₁,..., _n ) are in CM(k)and eithera _k b ₁ orb _k a ₁, equalsk(k–1)+2, and thath(k), the smallestn for which all (₁,..., _n ) are in CM(_k)and eithera ₁b ₁...a _k b _k orb ₁a ₁...b _k a _k , equals 2(k–1)²+2.The results forf andg rely on new theorems for regular patterns in (0, 1)-matrices that are of interest in their own right. An example is: Every upper-triangulark ²×k ² (0, 1)-matrix has eitherk 1's in consecutive columns, each below its predecessor, ork 0's in consecutive rows, each to the right of its predecessor, and the same conclusion is false whenk ² is replaced byk ²–1.