An improved algorithm for finding saddlepoints of two-person zero-sum games

It is well-known that one can sort (order)n real numbers in at mostF ₀(n) =nl – 2 ^l + 1 steps (comparisons), wherel = [log₂ n]. We snow how to find the strict saddlepoint or prove its absence in anm byn matrix,m n, in at mostF ₀(m)+F ₀(m+1)+n+m – 3 + (n–m) [log₂(m+1)] steps.     

Existenzaussagen für gewisse Zweipunkt-Randwertaufgaben

Zusammenfassung Für Randwertaufgaben der Form–u–l ₀ ...u–l ₀ ...u=f(x, u) mitl ₀R,lR,f definiert und stetig auf {a<-x<-b, |u|<} wird eine Existenzaussage gewonnen, fallsf inu linear durch die aufeinanderfolgenden Eigenwerte der zugehörigen linearen Aufgabe beschränkt ist. Zum Beweis betrachtet man die äquivalente Hammersteinsche Integralgleichung mit nichtsymmetrischem Kern. Mit Hilfe des Schauderschen Fixpunktsatzes erhält man für diese Integralgleichung Existenzaussagen, welche Ergebnisse von Dolph verallgemeinern.

---

Summary This note contains an existence theorem for a two-point boundary value problem of the form–u–l ₀ u–l ₀ u=f(x, u) wherel ₀R,l ₀R,f defined and continuous on {a<-xb, |u|<} iff is linear bounded inu by the successive eigenvalues of the corresponding linear problem. To prove this result we consider the equivalent Hammerstein integral equation with non-symmetric kernel. Schauders fixpoint principle supplies existence theorems for integral equations of this type which generalize results of Dolph in some sense.

     

Control of stochastic distributed-parameter systems

A scheme is proposed for the feedback control of distributed-parameter systems with unknown boundary and volume disturbances and observation errors. The scheme consists of employing a nonlinear filter in the control loop such that the controller uses the optimal estimates of the state of the system. A theoretical comparison of feedback proportional control of a styrene polymerization reactor with and without filtering is presented. It is indicated how an approximate filter can be constructed, greatly reducing the amount of computing required.Notation a(t) l-vector noisy dynamic input to system - A(t, a) l-vector function - A frequency factor for first-order rate law (5.68×10⁶ sec^–1) - b distance to the centerline between two coil banks in the reactor (4.7 cm) - B k-vector function defining the control action - c(, ) concentration of styrene monomer, molel ^–1 - C _p heat capacity (0.43 cal · g^–1 · K^–1) - C _ij constants in approximate filter, Eqs. (49)–(52) - E activation energy (20330 cal · mole^–1) - expectation operator - f(t,...) n-vector function - g ₀,g ₁(t,...) n-vector functions - h(t, u) m-vector function relating observations to states - H(t) function defined in Eq. (36) - k dimensionality of control vectorv(x, t) - k _i constants in approximate filter, Eqs. (49)–(52) - K dimensionless proportional gain - l dimensionality of dynamic inputa(t) - m dimensionality of observation vectory(t) - n dimensionality of state vectoru(x, t) - P ^(vv)(x, s, t) n×n matrix governed by Eq. (9) - P ^(va)(x, t) n×l matrix governed by Eq. (10) - P ^(aa)(t) l×l matrix governed by Eq. (11) - q _i (t) diagonal elements ofm×m matrixQ(x, s, t) - Q(x, s, t) m×m weighting matrix - R universal gas constant (1.987 cal · mole^–1 · K^–1) - R(x, s, t) n×n weighting matrix - R _i (t) n×n weighting matrix - s dimensionless spatial variable - S(x, s, t) matrix defined in Eq. (11) - t dimensionless time variable - T(, ) temperature, K - u(x, t) n-dimensional state vector - u _c (t) wall temperature - u _d desired value ofu ₁(1,t) - u _c * reference control value ofu _c - u _c ^max maximum value ofu _c - u _c ^min minimum value of _c - v(x, t) k-dimensional control vector - W(t) l×l weighting matrix - x dimensionless spatial variable - y(t) m-dimensional observation vector - _i constants in approximate filter, Eqs. (49)–(52) - dimensionless parameter defined in Eq. (29) - H heat of reaction (17500 cal · mole^–1) - dimensionless activation energy, defined in Eq. (29) - (x) Dirac delta function - (x, t) m-dimensional observation noise - thermal conductivity (0.43×10^–3 cal · cm^–1 · sec^–1 · K^–1) - density (1 g · cm^–3) - time, sec - dimensionless parameter defined in Eq. (29) - spatial variable, cm - * reference value - ^ estimated value     

Simple minimum coverings ofK n with copies ofK 4 −e

Summary AK ₄–e design of ordern is a pair (S, B), whereB is an edge-disjoint decomposition ofK _n (the complete undirected graph onn vertices) with vertex setS, into copies ofK ₄–e, the graph on four vertices with five edges. It is well-known [1] thatK ₄–e designs of ordern exist for alln 0 or 1 (mod 5),n 6, and that if (S, B) is aK ₄–e design of ordern then |B| =n(n – 1)/10.Asimple covering ofK _n with copies ofK ₄–e is a pair (S, C) whereS is the vertex set ofK _n andC is a collection of edge-disjoint copies ofK ₄–e which partitionE(K_n)P, for some . Asimple minimum covering ofK _n (SMCK _n) with copies ofK ₄–e is a simple covering whereP consists of as few edges as possible. The collection of edgesP is called thepadding. Thus aK ₄–e design of ordern isSMCK _n with empty padding.We show that forn 3 or 8 (mod 10),n 8, the padding ofSMCK _n consists of two edges and that forn 2, 4, 7 or 9 (mod 10),n 9, the padding consists of four edges. In each case, the padding may be any of the simple graphs with two or four edges respectively. The smaller cases need separate treatment:SMCK ₅ has four possible paddings of five edges each,SMCK ₄ has two possible paddings of four edges each andSMCK ₇ has eight possible paddings of four edges each.The recursive arguments depend on two essential ingredients. One is aK ₄–e design of ordern with ahole of sizek. This is a triple (S, H, B) whereB is an edge-disjoint collection of copies ofK ₄–e which partition the edge set ofK _n\K_k, whereS is the vertex set ofK _n, and is the vertex set ofK _k. The other essential is acommutative quasigroup with holes. Here we letX be a set of size 2n 6, and letX = {x ₁, x₂, ..., x_n} be a partition ofX into 2-element subsets, calledholes of size two. Then a commutative quasigroup with holesX is a commutative quasigroup (X, ) such that for each holex _i X, (x_i, ) is a subquasigroup. Such quasigroups exist for every even order 2n 6 [4].     

A characterization of the generalized twisted field planes of characteristic ≥5

Let be a non-Desarguesian semifield plane of orderp ⁿ, p a prime number 5 andn3, and let denote the group induced by the autotopism groupG of on the line at infinity. We prove that is a generalized twisted field plane if, and only if, has an element of order (p ^k–1)((p ⁿ–1)/(p ^m–1)), for some integersk andm, wherek | m, m | n, andm.This work was supported in part by NSF grants RII-9014056, component IV of the EPSCoR of Puerto Rico grant and ARO grant for Cornell MSI     

On improved regularity of weak solutions of some degenerate,Anisotropic elliptic systems

Summary We consider a (possibly) vector-valued function u: R^N, Rⁿ, minimizing the integral , 2-2/(n*1)<p<2, whereD _i u=u/x _i or some more general functional retaining the same behaviour, we prove higher integrability for Du: D₁ u,..., D_n–1 u L^p/(p-1) and D_nu L²; this result allows us to get existence of second weak derivatives: D(D₁ u),...,D(D_n–1u)L² and D(D_n u) L _p.This work has been supported by MURST and GNAFA-CNR.     

The Müntz-Szasz problem

A condition is obtained on the placement of point _n (in some sense, the final point) with which completeness of the system of functionsexp (– _n x), Re_n>0, in spaces L^p, 1p<2. is equivalent to divergence of the series re_n(1+¦_n¦²)^–1.Translated from Matematicheskie Zametki, Vol. 23, No. 1, pp. 91–103, January, 1978.Deceased.     

On Generalized Hermite–Fejér Interpolation of Lagrange Type on the Chebyshev Nodes

For fC[−1, 1], let H_m, n(f, x) denote the (0, 1, …,anbsp;m) Hermite–Fejér (HF) interpolation polynomial of f based on the Chebyshev nodes. That is, H_m, n(f, x) is the polynomial of least degree which interpolates f(x) and has its first m derivatives vanish at each of the zeros of the nth Chebyshev polynomial of the first kind. In this paper a precise pointwise estimate for the approximation error |H_2m, n(f, x)−f(x)| is developed, and an equiconvergence result for Lagrange and (0, 1, …, 2m) HF interpolation on the Chebyshev nodes is obtained. This equiconvergence result is then used to show that a rational interpolatory process, obtained by combining the divergent Lagrange and (0, 1, …, 2m) HF interpolation methods on the Chebyshev nodes, is convergent for all fC[−1, 1].     

Truncation error bounds for limit-periodic continued fractionsK(a n /1) with lima n =0

Summary Truncation error bounds are developed for continued fractionsK(a _n /1) where |a _n |1/4 for alln sufficiently large. The bounds are particularly suited (some are shown to be best) for the limit-periodic case when lima _n =0. Among the principal results is the following: If |a _n |/n ^p for alln sufficiently large (with constants >0,p>0), then |f–f _m |C[D/(m+2)] ^p(m+2) for allm sufficiently large (for some constantsC>0,D>0). Heref denotes the limit (assumed finite) ofK(a _n /1) andf _m denotes itsmth approximant. Applications are given for continued fraction expansions of ratios of Kummer functions₁ F ₁ and of ratios of hypergeometric functions₀ F ₁. It is shown thatp=1 for₁ F ₁ andp=2 for₀ F ₁, wherep is the parameter determining the rate of convergence. Numerical examples indicate that the error bounds are indeed sharp.Research supported in part by the National Science Foundation under Grant MCS-8202230 and DMS-8401717     

Second Jackson Inequality in a Sign-Preserving Approximation of Periodic Functions

We consider a 2-periodic function f continuous on and changing its sign at 2s points y _i [–, ). For this function, we prove the existence of a trigonometric polynomial T _n of degree n that changes its sign at the same points y _i and is such that the deviation |f(x) – T _n(x)| satisfies the second Jackson inequality.     

A Variation of an Extremal Theorem Due to Woodall

We consider a variation of an extremal theorem due to Woodall [12, or 1, Chapter 3] as follows: Determine the smallest even integer (₃C₁,n), such that every n-term graphic sequence = (d₁, d₂,..., d_n) with term sum () = d₁ + d₂ + ... + d_n (₃C₁,n) has a realization G containing a cycle of length r for each r = 3,4,...,l. In this paper, the values of (₃C_l,n) are determined for l = 2m – 1,n 3m – 4 and for l = 2m,n 5m – 7, where m 4.AMS Mathematics subject classification (1991) 05C35Project supported by the National Natural Science Foundation of China (Grant No. 19971086) and the Doctoral Program Foundation of National Education Department of China     

Interpolating them-th power ofx at the zeros of then-th Chebyshev-polynomial yields an almost best Chebyshev-approximation

LetX={x ₁,x ₂,..., _n }I=[–1, 1] and . ForfC ₁(I) definef* byf–p _f =f*, wherep _f denotes the interpolation-polynomial off with respect toX. We state some properties of the operatorf f*. In particular, we treat the case whereX consists of the zeros of the Chebyshev polynomialT _n (x) and obtain x ^m –p _x ^m8eE _n–1(x ^m ), whereE _n–1(f) denotes the sup-norm distance fromf to the polynomials of degree less thann. Finally we state a lower estimate forE _n (f) that omits theassumptionf ⁽ⁿ⁺¹⁾>0 in a similar estimate of Meinardus.     

Equally-weighted formulas for numerical differentiation

Equally-weighted formulas for numerical differentiation at a fixed pointx=a, which may be chosen to be 0 without loss in generality, are derived for (1) whereR _2n =0 whenf(x) is any (2n)^th degree polynomial. Equation (1) is equivalent to (2) ,r=1,2,..., 2n. By choosingf(x)=1/(z–x),x _i fori=1,..., n andx _i fori=n+1,..., 2n are shown to be roots ofg _n (z) andh _n (z) respectively, satisfying (3) . It is convenient to normalize withk=(m–1)!. LetP _s (z) denotez ^s · numerator of the (s+1)^th diagonal member of the Padé table fore ^x , frx=1/z, that numerator being a constant factor times the general Laguerre polynomialL _s ^–2s–1 (x), and letP _s (X _i )=0, i=1, ...,s. Then for anym, solutions to (1) are had, for2n=2ms, forx _i , i=1, ...,ms, andx _i , i=ms+1,..., 2ms, equal to all them ^th rootsX _i ^1/m and (–X _i )^1/m respectively, and they give {(2s+1)m–1}^th degree accuracy. For2sm2n(2s+1)m–1, these (2sm)-point solutions are proven to be the only ones giving (2n)^th degree accuracy. Thex _i 's in (1) always include complex values, except whenm=1, 2n=2. For2sm<2n(2s+1)m–1,g _n (z) andh _n (z) are (n–sm)-parameter families of polynomials whose roots include those ofg _ms (z) andh _ms (z) respectively, and whose remainingn–ms roots are the same forg _n (z) andh _n (z). Form>1, and either 2n<2m or(2s+1)m–1<2n<(2s+2)m, it is proven that there are no non-trivial solutions to (1), real or complex. Form=1(1)6, tables ofx _i are given to 15D, fori=1(1)2n, where 2n=2ms ands=1(1) [12/m], so that they are sufficient for attaining at least 24^th degree accuracy in (1).Presented at the Twelfth International Congress of Mathematicians, Stockholm, Sweden, August 15–22, 1962.General Dynamics/Astronautics. A Division of General Dynamics Corporation.     

Two combinatorial problems on posets

Bialostocki proposed the following problem: Let nk2 be integers such that k|n. Let p(n, k) denote the least positive integer having the property that for every poset P, |P|p(n, k) and every Z _k -coloring f: P Z _k there exists either a chain or an antichain A, |A|=n and _aA f(a) 0 (modk). Estimate p(n, k). We prove that there exists a constant c(k), depends only on k, such that (n+k–2)²–c(k) p(n, k) (n+k–2)²+1. Another problem considered here is a 2-dimensional form of the monotone sequence theorem of Erdös and Szekeres. We prove that there exists a least positive integer f(n) such that every integral square matrix A of order f(n) contains a square submatrix B of order n, with all rows monotone sequences in the same direction and all columns monotone sequences in the same direction (direction means increasing or decreasing).     

On sets of integers with prescribed gaps

For a fixed setI of positive integers we consider the set of paths (p _o,...,p _k ) of arbitrary length satisfyingp _l –p _l–1I forl=2,...,k andp ₀=1,p _k =n. Equipping it with the uniform distribution, the random path lengthT _n is studied. Asymptotic expansions of the moments ofT _n are derived and its asymptotic normality is proved. The step lengthsp _l –p _l–1 are seen to follow asymptotically a restricted geometrical distribution. Analogous results are given for the free boundary case in which the values ofp ₀ andp _k are not specified. In the special caseI={m+1,m+2,...} (for some fixed m) we derive the exact distribution of a random m-gap subset of {1,...,n} and exhibit some connections to the theory of representations of natural numbers. A simple mechanism for generating a randomm-gap subset is also presented.     

Percentage Points of the Largest Among Student's T Random Variable

Let us consider k( 2) independent random variables U₁, . . . ,U_k where U_i is distributed as the Student's t random variable with a degree of freedom m_i, i=1, . . . ,k. Here, m₁, . . . ,m_k are arbitrary positive integers. We denote m=(m₁, . . . ,m_k) and U_k:k=max {U₁, . . . ,U_k}, the largest Student's t random variable. Having fixed 0< <1, let a a(k,) and h_m h_m (k,) be two positive numbers for which we can claim that (i) ^k(a)–^k(–a)=1–, and (ii) P{–h_m U_k:k h_m}=1–. Then, we proceed to derive a Cornish–Fisher expansion (Theorem 3.1) of the percentage point h_m. This expansion involves a as well as expressions such as _i=1 ^k m_i ^–1, _i=1 ^km_i ^–2, and _i=1 ^k m_i ^–3. The corresponding approximation of h_m is shown to be remarkably accurate even when k or m₁, . . . ,m_k are not very large.     

Necessary and sufficient conditions for the convergence of integrated and mean-integratedr-th order error of histogram density estimates

Suppose thatX _l ,..., X _n are samples drawn from a population with density functionf andf _n (x)=f _n (x;X _l ,..., X _n is an estimate off(x), Denote bym _nr =|f _n (x)–f(n)| ^r dx andM _nr =E(m _nr) the Integratedr-th Order Error and Mean Integratedr-th Order Error off _n for somer1 (whenr=2,they are the familiar and widely studied ISE and MISE), In this paper the same necessary and sufficient condition for and a.s. is obtained whenf _n (x) is the ordinary histogram estimator.The Project supported by National Natural Science Foundation of China.     

On weak convergence of functionals of stochastic processes with continuously differentiable paths

We obtain a criterion for weak convergence of a sequence of stochastic processes _n(t), t [0, 1],n N, _n(t) R ^m in the spaceC _m ^k [0, 1] of continuously differentiable functions. We consider several examples of weakly convergent sequences of stochastic processes inC _m ^k [0, 1] and several integer functionals defined on these random variables.Translated fromTeoriya Sluchainykh Protsessov, Vol. 15, pp. 85–90, 1987.     

Kernels of sequences of complex numbers and their regular transformations

It is proved that , where U(a, r) is the ball of radius r with center at the pointa, is the smallest closed convex set containing the kernel of any sequence {y_n} obtained from the sequence {x_n} by means of a regular transformation (c_nk) satisfying the condition , where x, x_n, c_nk (n, k=1, 2,...) are complex numbers.Traslated from Matematicheskie Zametki, Vol. 22, No. 6, pp. 815–823, December, 1977.     

Some examples of random walks on free products of discrete groups

Summary We consider the random walk (X_n) associated with a probability p on a free product of discrete groups. Knowledge of the resolvent (or Green's function) of p yields theorems about the asymptotic behaviour of the n-step transition probabilities p^*n(x)=P(X_n= x¦ X₀=e) as n. Woess [15], Cartwright and Soardi [3] and others have shown that under quite general conditions there is behaviour of the type p^*n(x)C_x^– n n^– 3/2. Here we show on the other hand that if G is a free product of m copies ofZ ^r and if (X_n) is the « average » of the classical nearest neighbour random walk on each of the factorsZ ^r, then while it satisfies an « n^–3/2 — law » for r small relative to m, it switches to an n^– r/2 -law for large r. Using the same techniques, we give examples of irreducible probabilities (of infinite support) on the free groupZ ^*m which satisfyn ^– for .