PiecewiseL-splines

Leta=x ₀<x ₁<...<x _N =b be a partition of the interval [a, b] and letL be a normalm-th order linear differential operator. The purpose of this note is to point out that spline functions in one variable need not be excluded to piecewise fits of functions belonging to the null spaceN(L ^* L) on each closed subinterval [x _i,x _i+1], 0in-1 but may be extended to piecewise fits of functions belonging toN(L _i ^* L _i) on each subinterval [x _i,x _i+1] provided theL _i's are selected from a uniformly bounded family of normal linear differential operators. Furthermore when theL _i's are so selected one obtains the usual integral relations and error estimates obtained for splines [2, 8 and 9] including the extended error estimates obtained by Swartz and Varga [10].     

Identification of parameters by the distribution of the maximum random variable: The general multivariate normal case

Summary LetX ₁,X ₂, ...,X _r ber independentn-dimensional random vectors each with a non-singular normal distribution with zero means and positive partial correlations. Suppose thatX _i =(X _i1 , ...,X _in ) and the random vectorY=(Y ₁, ...,Y _n ), their maximum, is defined byY _j =max{X _ij :1ir}. LetW be another randomn-vector which is the maximum of another such family of independentn-vectorsZ ₁,Z ₂, ...,Z _s . It is then shown in this paper that the distributions of theZ _i 's are simply a rearrangement of those of theZ _j 's (and of course,r=s), whenever their maximaY andW have the same distribution. This problem was initially studied by Anderson and Ghurye [2] in the univariate and bivariate cases and motivated by a supply-demand problem in econometrics.     

Compactness of the congruence group of measurable functions in several variables

We solve a problem, which appears in functional analysis and geometry, on the group of symmetries of functions of several arguments. Let be a measurable function defined on the product of finitely many standard probability spaces (X_i, , μ_i), 1 ≤ i ≤ n, that takes values in any standard Borel space Z. We consider the Borel group of all n-tuples (g₁, ..., g_n) of measure preserving automorphisms of the respective spaces (X_i, , μ_i) such that f(g₁ x ₁, ..., g_nx_n) = f(x₁, ..., x_n) almost everywhere and prove that this group is compact, provided that its “trivial” symmetries are factored out. As a consequence, we are able to characterize all groups that result in such a way. This problem appears with the question of classifying measurable functions in several variables, which was solved by the first author but is interesting in itself. Bibliography: 5 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 334, 2006, pp. 57–67.     

Sumsets in difference sets

We study some properties of sets of differences of dense sets in ℤ² and ℤ³ and their interplay with Bohr neighbourhoods in ℤ. We obtain, inter alia, the following results.

An ODE-based approach to nonlinearly constrained minimax problems

We consider the following problem: Choosex ₁, ...,x _n to wherem ₁,m ₂,m ₃ are integers with 0m ₁m ₂m ₃, thef _i are given real numbers, and theg _i are given smooth functions. Constraints of the formg _i (x ₁, ...,x _n )=0 can also be handled without problem. Each iteration of our algorithm involves approximately solving a certain non-linear system of first-order ordinary differential equations to get a search direction for a line search and using a Newton-like approach to correct back into the feasible region when necessary. The algorithm and our Fortran implementation of it will be discussed along with some examples. Our experience to date has been that the program is more robust than any of the library routines we have tried, although it generally requires more computer time. We have found this program to be an extremely useful tool in diverse areas, including polymer rheology, computer vision, and computation of convexity-preserving rational splines.     

On a problem of spencer

LetX ₁, ...,X _n be events in a probability space. Let ϱ_i be the probabilityX _i occurs. Let ϱ be the probability that none of theX _i occur. LetG be a graph on [n] so that for 1 ≦i≦n X _i is independent of ≈X _j ‖(i, j)∉G≈. Letf(d) be the sup of thosex such that if ϱ₁, ..., ϱ _n ≦x andG has maximum degree ≦d then ϱ>0. We showf(1)=1/2,f(d)=(d−1) ^d−1 d ^−d ford≧2. Hence df(d)=1/e. This answers a question posed by Spencer in [2]. We also find a sharp bound for ϱ in terms of the ϱ _i andG.     

An Erdös-Ko-Rado theorem for the subcubes of a cube

LetP be that partially ordered set whose elements are vectors x=(x ₁, ...,x _n ) withx _i ε {0, ...,k} (i=1, ...,n) and in which the order is given byx≦y iffx _i =y _i orx _i =0 for alli. LetN _i (P)={x εP : |{j:x _j ≠ 0}|=i}. A subsetF ofP is called an Erdös-Ko-Rado family, if for allx, y εF it holdsx ≮y, x ≯ y, and there exists az εN ₁(P) such thatz≦x andz≦y. Let ? be the set of all vectorsf=(f ₀, ...,f _n ) for which there is an Erdös-Ko-Rado familyF inP such that |N _i (P) ∩F|=f _i (i=0, ...,n) and let 〈?〉 be its convex closure in the (n+1)-dimensional Euclidean space. It is proved that fork≧2 (0, ..., 0) and \(\left( {0,...,0,\overbrace {i - component}^{\left( {\begin{array}{*{20}c} {n - 1} \\ {i - 1} \\ \end{array} } \right)}k^{i - 1} ,0,...,0} \right)\) (i=1, ...,n) are the vertices of 〈?〉.     

A scaling technique for finding the weighted analytic center of a polytope

Let a bounded full dimensional polytope be defined by the systemAx b whereA is anm × n matrix. Leta _i denote theith row of the matrixA, and define theweighted analytic center of the polytope to be the point that minimizes the strictly convex barrier function – _i=1 ^m w _i ln(a _i ^T x –b _i ). The proper selection of weightsw _i can make any desired point in the interior of the polytope become the weighted analytic center. As a result, the weighted analytic center has applications in both linear and general convex programming. For simplicity we assume that the weights are positive integers.If some of thew _i 's are much larger than others, then Newton's method for minimizing the resulting barrier function is very unstable and can be very slow. Previous methods for finding the weighted analytic center relied upon a rather direct application of Newton's method potentially resulting in very slow global convergence. We present a method for finding the weighted analytic center that is based on the scaling technique of Edmonds and Karp and is an enhancement of Newton's method. The scaling algorithm runs in iterations, wherem is the number of constraints defining the polytope andW is the largest weight given on any constraint. Each iteration involves taking a step in the Newton direction and its complexity is dominated by the time needed to solve a system of linear equations.Supported by the Campus Research Board, University of Illinois at Urbana-Champaign.Supported by the National Science Foundation under Grants CCR-9057481 and CCR-9007195.     

An Erdo&#x030B;s–Ko–Rado Theorem for Direct Products

Letn_i, k_ibe positive integers,i=1, ..., d,satisfyingn_i≥2k_i.LetX₁, ..., X_dbe pairwise disjoint sets with |X_i| =n_i.Letbe the family of those (k₁+···+k_d)-element sets which have exactlyk_ielements inX_i, i=1,..., d.It is shown that if⊂is an intersecting family then ||/||≤max_ik_i/n_i,and this is best possible. The proof is algebraic, although in thed=2 case a combinatorial argument is presented as well.     

Fractional dimension of partial orders

Given a partially ordered setP=(X, ), a collection of linear extensions {L ₁,L ₂,...,L _r } is arealizer if, for every incomparable pair of elementsx andy, we havex<y in someL _i (andy<x in someL _j ). For a positive integerk, we call a multiset {L ₁,L ₂,...,L _t } ak-fold realizer if for every incomparable pairx andy we havex<y in at leastk of theL _i 's. Lett(k) be the size of a smallestk-fold realizer ofP; we define thefractional dimension ofP, denoted fdim(P), to be the limit oft(k)/k ask. We prove various results about the fractional dimension of a poset.Research supported in part by the Office of Naval Research.     

Optimal pairs of score vectors for positional scoring rules

Letw=(w ₁,,w _m ) andv=(v ₁,,v _m-1 ) be nonincreasing real vectors withw ₁>w _m andv ₁>v _m-1 . With respect to a lista ₁,,a _n of linear orders on a setA ofm3 elements, thew-score ofaA is the sum overi from 1 tom ofw _i times the number of orders in the list that ranka inith place; thev-score ofaA{b} is defined in a similar manner after a designated elementb is removed from everya _j .We are concerned with pairs (w, v) which maximize the probability that anaA with the greatestw-score also has the greatestv-score inA{b} whenb is randomly selected fromA{a}. Our model assumes that linear ordersa _j onA are independently selected according to the uniform distribution over them linear orders onA. It considers the limit probabilityP _m (w, v) forn that the element inA with the greatestw-score also has the greatestv-score inA{b}.It is shown thatP _m (m,v) takes on its maximum value if and only if bothw andv are linear, so thatw _i –w _i+1=w _i+1–w _i+2 forim–2, andv _i –v _i+1 =v _i+1 –v _i+2 forim–3. This general result for allm3 supplements related results for linear score vectors obtained previously form{3,4}.     

A general Hobby-Rice Theorem and cake cutting

LetX be a Borel subset of a separable Banach spaceE. Letμ be a non-atomic,σ-finite, Borel measure onX. LetG ⊆L ₁ (X, Σ,μ) bem-dimensional. Theorem:There is an l ∈ E* and real numbers −∞=x ₀<x ₁<x ₂<…<x _n<x _n+1=∞with n≤m, such that for all g ∈ G,      

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.     

The view-obstruction problem for 3-dimensional spheres

LetC be ann-dimensional sphere with diameter 1 and center at the origin inE ⁿ . The view-obstruction problem forn-dimensional spheres is to determine a constant ν(n) to be the lower bound of those α for which any half-lineL, given byx _i =a _i t (i=1,2,...,n) where parametert≥0 anda _i (i=1,2,...,n) are positive real numbers, intersects

Inequalities for ordered sums

Summary Letx _i =y _i +z _i ,i=1, ...n, and writex ₍₁₎≦...≦x _(n) , with corresponding notation for the orderedy _i andz _i . It is shown, for example, that ,r=1, ...n. Inequalities are also obtained for convex (or concave) functions of thex _(i) . The results lead immediately to bounds for the expected values of order statistics in nonstandard situations in terms of simpler expectations. A small numerical example illustrates the method. Research supported by U.S. Army Research Office.     

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.     

The generalized order complementarity problem

Given an ordered Banach Space (E,K) andm functionsf ₁,f ₂,...,f _m:EE, the generalized order complementarity problem associated with {f _i} andK is to findx ₀K such thatf _i(x ₀)K,i=1,...,m, and (x ₀,f ₁(x ₀),...,f _m(x ₀))=0. The problem is shown to be equivalent to several fixed-point problems and equivalent to the order complementarity problem studied by Borwein and Dempster and by Isac. Existence and uniqueness of solutions and least-element theory are shown in the spacesC(, ) andL _p(, ). For general locally convex spaces, least-element theory is derived, existence is proved, and an algorithm for computing a solution is presented. Applications to the mixed lubrication theory of fluid mechanics are described.     

A basic family of iteration functions for polynomial root finding and its characterizations

Let p(x) be a polynomial of degree n?2 with coefficients in a subfield K of the complex numbers. For each natural number m?2, let L_m(x) be the m×m lower triangular matrix whose diagonal entries are p(x) and for each j=1,…,m−1, its jth subdiagonal entries are . For i=1,2, let L_m^i)(x) be the matrix obtained from L_m(x) by deleting its first i rows and its last i columns. L₁⁽¹⁾(x)≡1. Then, the function B_m(x)=x−p(x) defines a fixed-point iteration function having mth order convergence rate for simple roots of p(x). For m=2 and 3, B_m(x) coincides with Newton's and Halley's, respectively. The function B_m(x) is a member of S(m,m+n−2), where for any M?m, S(m,M) is the set of all rational iteration functions g(x) ∈ K(x) such that for all roots θ of p(x), then g(x)=θ+∑_i=m^Mγ_i(x)(θ−x)ⁱ, with γ_i(x) ∈ K(x) and well-defined at any simple root θ. Given g ∈ S(m,M), and a simple root θ of p(x), gⁱ(θ)=0, i=1, …, m−1 and the asymptotic constant of convergence of the corresponding fixed-point iteration is . For B_m(x) we obtain . If all roots of p(x) are simple, B_m(x) is the unique member of S(m,m + n − 2). By making use of the identity , we arrive at two recursive formulas for constructing iteration functions within the S(m,M) family. In particular, the family of B_m(x) can be generated using one of these formulas. Moreover, the other formula gives a simple scheme for constructing a family of iteration functions credited to Euler as well as Schröder, whose mth order member belongs to S(m,mn), m>2. The iteration functions within S(m,M) can be extended to any arbitrary smooth function f, with the uniform replacement of p^(j) with f^(j) in g as well as in γ_m(θ).     

Bivariate Bonferroni inequalities

Summary LetA ₁,A ₂, ,A _m ,C ₁,C ₂, ,C _n be events on a given probability speace. LetV _m andU _n , respectively, be the numbers among theA _i 's andC _j 's which occur.Upper and lower bounds ofP(V _m 1, U _n 1) are obtained by means of the bivariate binomial moments. These extend recent univariate optimal Bonferroni-type inequalities.     

Comparison theorems forL-monosplines of minimal norm

Summary LetLM _N be the set of allL-monosplines withN free knots, prescribed by a pair (x;E) of pointsx = {x _i } ₁ ⁿ ,a <x ₁ < ... <x _n <b and an incidence matrixE = (e _ij ) _i=1 ⁿ , _r-1 ^j=0 with Denote byLM _N ^O the subset ofLM _N consisting of theL-monosplines withN simple knots (n=N). We prove that theL-monosplines of minimalL _p-norms inLM _N belong toLM _N ^O .The results are reformulated as comparison theorems for quadrature formulae.