On a method to transform algebraic differential equations into universal equations

The paper introduces an algorithm which transforms homogeneous algebraic differential equations into universal differential equations (in the sense of L. A. Rubel) havingC ⁿ (ℝ)-solutions. By applications of the algorithm to different initial equations some new universal differential equations are found, and all the known equations due to R. J. Duffin are rediscovered with this method. Assuming weak conditions one can find Cⁿ(ℝ)-solutionsy of the differential equation close to any continuous function such that 1, with 0 ≤k ₁ <k ₂ < .... <k _s ≤n are linearly independent over the field of real algebraic numbers at the rational points q1,...,qs.     

Singular Nonlinear (n − 1,1) Conjugate Boundary Value Problems

Solutions are obtained for the boundary value problem, y ⁽ⁿ⁾ + f(x,y) = 0, y ⁽ⁱ⁾(0) = y(1) = 0, 0 i n – 2, where f(x,y) is singular at y = 0. An application is made of a fixed point theorem for operators that are decreasing with respect to a cone.     

A Comparison Theorem on Moment Inequalities Between Negatively Associated and Independent Random Variables

Let {X _i, 1in} be a negatively associated sequence, and let {X* _i , 1in} be a sequence of independent random variables such that X* _i and X _i have the same distribution for each i=1, 2,..., n. It is shown in this paper that Ef( ⁿ _i=1 X _i)Ef( ⁿ _i=1 X* _i ) for any convex function f on R ¹ and that Ef(max_1kn ⁿ _i=k X _i)Ef(max_1kn ^k _i=1 X* _i ) for any increasing convex function. Hence, most of the well-known inequalities, such as the Rosenthal maximal inequality and the Kolmogorov exponential inequality, remain true for negatively associated random variables. In particular, the comparison theorem on moment inequalities between negatively associated and independent random variables extends the Hoeffding inequality on the probability bounds for the sum of a random sample without replacement from a finite population.     

Remarks on osculating linear spaces to projective varieties

Let X P^N be an integral n-dimensional variety and m(X, P, i) (resp. m(X, i)), 1 i N - n + 1, the Hermite invariants of X measuring the osculating behaviour of X at P (resp. at its general point). Here we prove m(X, x) + m(X, y) m(X, x + y) and m(X, P, x) + m(X, y) m(X, P, x + y) for all integers x, y such that x + y N - n + 1, the case n = 1 being known (M. Homma, A. Garcia and E. Esteves).*Partially supported by MIUR and GNSAGA of INdAM (Italy).     

An estimate for the region of regularity of solutions of certain nonlinear differential inequalities

In the diskx ²+y ²R ² of thex, y-plane we consider the differential inequalityz _xxz_yy–z _xy ² –(1+z _x ^/2 +z _y ^/2 )^k, where the constants >0 andk>1. In the case =1 andk=2 this inequality means that the surfacez(x, y) has Gaussian curvatureK1. Efimov has shown that in this case the radius of the disk has an upper bound. In the present article we establish an analogous upper bound for the radiusR of the disk in which the functionz(x, y) satisfies the differential inequality above.Translated from Ukrainskií Geometricheskií Sbornik, Issue 28, 1985, pp. 19–21.     

On vector space partitions and uniformly resolvable designs

Let V _n (q) denote a vector space of dimension n over the field with q elements. A set of subspaces of V _n (q) is a partition of V _n (q) if every nonzero vector in V _n (q) is contained in exactly one subspace in . A uniformly resolvable design is a pairwise balanced design whose blocks can be resolved in such a way that all blocks in a given parallel class have the same size. A partition of V _n (q) containing a _i subspaces of dimension n _i for 1 ≤ i ≤ k induces a uniformly resolvable design on q ⁿ points with a _i parallel classes with block size , 1 ≤ i ≤ k, and also corresponds to a factorization of the complete graph into -factors, 1 ≤ i ≤ k. We present some sufficient and some necessary conditions for the existence of certain vector space partitions. For the partitions that are shown to exist, we give the corresponding uniformly resolvable designs. We also show that there exist uniformly resolvable designs on q ⁿ points where corresponding partitions of V _n (q) do not exist. A. D. Blinco—Part of this research was done while the author was visiting Illinois State University.     

Isoperimetric inequalities,isometric actions and the higher Newman numbers

M will be a compact connected n-dimensional Riemannian manifold. If M contains a closed connected k-dimensional, 2 k < n, minimal immersed submanifold of M, we define the kth isoperimetric number of M, Ñ _k (M), as the infimum of the volumes of all such submanifolds. We obtain a number of interesting estimates for Ñ _k (M), for both general and special manifolds, which appear to be new.Next we turn to isometric actions and a 1931 theorem of M. H. A. Newman involving the size of orbits of group actions on manifolds. We introduce the higher Newman numbers N _k (M), 1 k n. Roughly speaking, if M admits isometric actions of compact connected Lie groups with k-dimensional principal orbits, N _k (M) is defined as the infimum over all such actions of the maximum volume of all maximal dimensional orbits. We observe that N _k (M) Ñ _k (M), 2 k < n, provided N _k (M) is defined; hence our prior estimates for the isoperimetric numbers of M apply directly to the higher Newman numbers.As a best possible candidate we conjecture that N _k (M) vol S ^k (i(M)/), 1 k n, where i(M) denotes the radius of injectivity of M and S ^k (i(M)/) denotes the standard k-sphere of radius i(M)/. We verify the conjecture for various special cases. We conclude the paper by studying Newman's theorem for compact connected Lie groups with invariant metrics and obtaining a lower bound for the size of small subgroups.     

The roots of <Emphasis Type="Italic">σ</Emphasis>-polynomials

Let G be a connected graph. We denote by σ(G,x) and δ(G) respectively the σ-polynomial and the edge-density of G, where . If σ(G,x) has at least an unreal root, then G is said to be a σ-unreal graph. Let δ(n) be the minimum edgedensity over all n vertices graphs with σ-unreal roots. In this paper, by using the theory of adjoint polynomials, a negative answer to a problem posed by Brenti et al. is given and the following results are obtained: For any positive integer a and rational number 0≤c≤1, there exists at least a graph sequence {G _i}_1≤i≤a such that G _i is σ-unreal and δ(G _i)→c as n→∞ for all 1 ≤i≤a, and moreover, δ(n)→0 as n→∞. Supported by the National Natural Science Foundation of China (10061003) and the Science Foundation of the State Education Ministry of China.     

The asymptotic properties of the multichannel autoregressive spectral estimates

If we fit a-vector stationary time series using observationsx(1), ...,x(T) with AR models , then the spectral densityf() of {x(t)} can be estimated byf _k ^(T) ()=(2)^– A _k ^(T) (e ^–)^–1 _k ^(T) A _k ^(T) (e ^–i)^–, where are estimates of the variance matrix of(t), the residuals of the best linear prediction. By extending some results for the scalar case, this paper treats the asymptotic properties of the estimates in the multichannel case.     

Rational, Log Canonical, Du Bois Singularities: On the Conjectures of Kollár and Steenbrink

Let X be a proper complex variety with Du Bois singularities. Then H(X, ⁱ) H ⁱ(X, _X) is surjective for all i. This property makes this class of singularities behave well with regard to Kodaira type vanishing theorems. Steenbrink conjectured that rational singularities are Du Bois and Kollér conjectured that log canonical singularities are Du Bois. Kollér also conjectured that under some reasonable extra conditions Du Bois singularities are log canonical. In this article Steenbrink's conjecture is proved in its full generality, Kollér's first conjecture is proved under some extra conditions and Kollér's second conjecture is proved under a set of reasonable conditions, and shown that these conditions cannot be relaxed.     

Directed packings with block size 5 and even ν

Let andk be positive integers. A transitively orderedk-tuple (a ₁,a ₂,...,a _k) is defined to be the set {(a _i, a_j) 1i<jk} consisting ofk(k–1)/2 ordered pairs. A directed packing with parameters ,k and index =1, denoted byDP(k, 1; ), is a pair (X, A) whereX is a -set (of points) andA is a collection of transitively orderedk-tuples ofX (called blocks) such that every ordered pair of distinct points ofX occurs in at most one block ofA. The greatest number of blocks required in aDP(k, 1; ) is called packing number and denoted byDD(k, 1; ). It is shown in this paper that for all even integers , where [x] is the floor ofx.     

Linear Extensions of Semiorders: II

Let M _n (k) denote the family of posets on n points with k ordered pairs that maximize the number of linear extensions among all such posets. Fishburn and Trotter [2] prove that every poset in M _n (k) is a semiorder and identifies all semiorders in M _n (k) for k n. The present paper specifies M _n (k) for all k 2 n – 3.     

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.     

Maintaining the minimal distance of a point set in polylogarithmic time

A dynamic data structure is given that maintains the minimal distance in a set ofn points ink-dimensional space inO((logn) ^k log logn) amortized time per update. The size of the data structure is bounded byO(n(logn) ^k ). Distances are measured in the MinkowskiL _t -metric, where 1 t . This is the first dynamic data structure that maintains the minimal distance in polylogarithmic time for fully on-line updates.This work was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).     

An Algorithm for Computing the Best Convex Contrast Curve of Two Bivariate Samples

Abstract

Let (x ₁, y ₁),…, (x _n, y _n) be a sample of points in , consisting of two subsamples (x ₁, y ₁),…, (x _n1, y _n1) and (x _n1+1, y _n1+1),…, (x _n, y _n), where n = n ₁ + n ₂. We consider the problem of separating the two subsamples by a convex contrast curve k…that is, a real-valued convex function x → k(x). For given curve k we consider the relative frequency p ₁ of points of the first sample above the graph of k similarly p ₂. The goal is to choose k such that the difference in relative frequency p ₁ – p ₂ becomes maximal. This maximal value can be regarded as a generalized one-sided Kolmogorov-Smirnov test statistic , where p ₁(A) = (1/n ₁)#{i ≤ n ₁ : (xi, y _i) ∈ A}, p ₂(A) = (1/n ₂#{n ₁ + 1 ≤ i ≤ n : (x _i, y _i) ∈ A} and is the class of all epigraphs {(x y) : k(x) ≤ y} of convex functions k. The standard Kolmogorov-Smirnov test statistic corresponds to the class consisting of all sets —that is, epigraphs of constant functions. Test statistics of this form arise in nonparametric analysis of covariance where the regression function is assumed to be convex. In this article we give a recursive relation and an algorithm based on it to compute the value KS and an optimal convex contrast curve in O(n ³) steps. The convexity assumptions on the sets of and on the nonparametric regression function are interrelated; this is explained in the large sample situation where n ₁ Λ n ₂ → + ∞.     

Evaluation of infinite series involving special products and their algebraic characterization

The aim of the paper is the investigation of special infinite series of the form

Coin flipping from a cosmic source: On error correction of truly random bits

We study a problem related to coin flipping, coding theory, and noise sensitivity. Consider a source of truly random bits x ∈ {0, 1}ⁿ, and k parties, who have noisy version of the source bits yⁱ ∈ {0, 1}ⁿ, when for all i and j, it holds that P [y = x_j] = 1 ? ?, independently for all i and j. That is, each party sees each bit correctly with probability 1 ? ?, and incorrectly (flipped) with probability ?, independently for all bits and all parties. The parties, who cannot communicate, wish to agree beforehand on balanced functions f_i: {0, 1}ⁿ → {0, 1} such that P [f₁(y¹) = … = f_k(y^k)] is maximized. In other words, each party wants to toss a fair coin so that the probability that all parties have the same coin is maximized. The function f_i may be thought of as an error correcting procedure for the source x. When k = 2,3, no error correction is possible, as the optimal protocol is given by f_i(yⁱ) = y. On the other hand, for large values of k, better protocols exist. We study general properties of the optimal protocols and the asymptotic behavior of the problem with respect to k, n, and ?. Our analysis uses tools from probability, discrete Fourier analysis, convexity, and discrete symmetrization. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Multiple Solutions and Its Morse Index for One-Dimensional Nonlinear Problem

The multiple solutions for one-dimensional cubic nonlinear problem u" u~3=0,u(0)=u(π)=0are computed,on the basis of the eigenpairs of-φ"_k=λ_(kφk),k=1,2,3....There exist two nonzero solutions±u_k corresponding to each k,and their Morse index MI(k) for 1(?)k(?)20 is to be exactly determined.It isshown by the numerical results that MI(k)(?)k.     

Distances to the two and three furthest points

Let a compact setF ⁿ contain no less thank points. The functionf _k : ⁿ defined by the formulaf _k (M)=sup _i ^=1/k ¦MA _i ¦, whereA _i are distinct points inF, is convex. Fork=2 its minimum is attained at the center of the smallest ball containingF or on a segment passing through this center. Fork=3 (as well as for any oddk) the minimum point off _k is unique, whereas for evenk the domain wheref _k attains its minimum can include a segment.Translated fromMatematicheskie Zametki, Vol. 59, No. 5, pp. 703–708, May, 1996.This research was partially supported by the Russian Foundation for Basic Research under grant No. 94-01-01044