Some inequalities about the covering radius of Reed-Muller codes

Let R(r, m) be the rth order Reed-Muller code of length 2 ^m , and let (r, m) be its covering radius. We prove that if 2 k m - r - 1, then (r + k, m + k) (r, m + 2(k - 1). We also prove that if m - r 4, 2 k m - r - 1, and R(r, m) has a coset with minimal weight (r, m) which does not contain any vector of weight (r, m) + 2, then (r + k, m + k) (r, m) + 2k(. These inequalities improve repeated use of the known result (r + 1, m + 1) (r, m).This work was supported by a grant from the Research Council of Wright State University.     

Further results on the covering radii of the Reed-Muller codes

LetR(r, m) by therth order Reed-Muller code of length2 ^m , and let (r, m) be its covering radius. We obtain the following new results on the covering radius ofR(r, m): 1. (r+1,m+2) 2(r, m)+2 if 0rm–2. This improves the successive use of the known inequalities (r+1,m+2)2(r+1,m+1) and (r+1,m+1) (r, m).2.(2, 7)44. Previously best known upper bound for (2, 7) was 46. 3. The covering radius ofR(1,m) inR(m–1,m) is the same as the covering radius ofR(1,m) inR(m–2,m) form4.     

Approximation of the viability kernel

We study recursive inclusionsx ⁿ⁺¹ G(x ⁿ ). For instance, such systems appear for discrete finite-difference inclusionsx ⁿ⁺¹ G (x ⁿ) whereG :=1+F. The discrete viability kernel ofG , i.e., the largest discrete viability domain, can be an internal approximation of the viability kernel ofK underF. We study discrete and finite dynamical systems. In the Lipschitz case we get a generalization to differential inclusions of the Euler and Runge-Kutta methods. We prove first that the viability kernel ofK underF can be approached by a sequence of discrete viability kernels associated withx ⁿ⁺¹ (xⁿ) where (x) =x + F(x) + (ML/2) ². Secondly, we show that it can be approached by finite viability kernels associated withx _h ⁿ⁺¹ ( (x _h ⁿ⁺¹ ) +(h) X _h .     

Wave operators in a multistratified strip

One investigates the scattering theory for the positive self-adjoint operatorH=–· acting in with = × and a bounded open set in ^n–1,n2. The real-valued function belongs toL (), is bounded from below byc>0 and there exist real-valued functions ₁ and ₂ inL () such that – _j ,j=1,2 is a short range perturbation of _j when (–1) ^j x _n +. One assumes _j = ^(j) 1_R,j=1,2, with ^(j) L bounded from below byc>0. One proves the existence and completeness of the generalized wave operators _j ^± =s – _j e ^–itHj ,j=1,2, withH _j =–· _j and _j : equal to 1 if (–1) ^j x _n >0 and to 0 if (–1) ^j x _n <0. The ranges ofW _j ^± :=( _j ^± )^* are characterized so that W ₁ ^± =Ran and . The scattering operator can then be defined.     

A lower bound on solutions of Chartrand's problem

In this paper it is shown that if a connected graphG without loops contains spanning trees withm andn end-vertices, respectively, withm, thenG contains at least spanning trees withk end-vertices for every integerk withm where is the circuit rank ofG.     

Finite clusters in high-density continuous percolation: Compression and sphericality

Summary A percolation process inR ^d is considered in which the sites are a Poisson process with intensity and the bond between each pair of sites is open if and only if the sites are within a fixed distancer of each other. The distribution of the number of sites in the clusterC of the origin is examined, and related to the geometry ofC. It is shown that when andk are large, there is a characteristic radius such that conditionally on |C|=k, the convex hull ofC closely approximates a ball of radius , with high probability. When the normal volumek/ thatk points would occupy is small, the cluster is compressed, in that the number of points per unit volume in this -ball is much greater than the ambient density . For larger normal volumes there is less compression. This can be compared to Bernoulli bond percolation on the square lattice in two dimensions, where an analog of this compression is known not to occur.Research supported by NSF grant number DMS-9006395     

Some observations on the distribution of values of continued fractions

Summary There have been many studies of the values taken on by continued fractionsK(a _n /1) when its elements are all in a prescribed setE. The set of all values taken on is the limit regionV(E). It has been conjectured that the values inV(E), are taken on with varying probabilities even when the elementsa _n are uniformly distributed overE. In this article, we present the first concrete evidence that this is indeed so. We consider two types of element regions: (A)E is an interval on the real axis. Our best results are for intervals [–(1–), (1–)], 0 <1/2. (B)E is a disk in the complex plane defined byE={z:|z|(1–)}., 0<1/2.     

Preprojective components of wild tilted algebras

If A is a finite dimensional, connected, hereditary wild k-algebra, k algebraically closed and T a tilting module without preinjective direct summands, then the preprojective componentP of the tilted algebra B=End_A (T) is the preprojective component of a concealed wild factoralgebra C of B. Our first result is, that the growth number (C) of C is always bigger or equal to the growth number (A). Moreover the growth number (C) can be arbitrarily large; more precise: if A has at least 3 simple modules and N is any positive integer, then there exists a natural number n>N such that C is the Kronecker-algebraK _n, that is the path-algebra of the quiver (n arrows).     

On the estimation of prediction errors in linear regression models

Estimating the prediction error is a common practice in the statistical literature. Under a linear regression model, lete be the conditional prediction error andê be its estimate. We use (ê, e), the correlation coefficient betweene andê, to measure the performance of a particular estimation method. Reasons are given why correlation is chosen over the more popular mean squared error loss. The main results of this paper conclude that it is generally not possible to obtain good estimates of the prediction error. In particular, we show that (ê, e)=O(n ^–1/2) whenn . When the sample size is small, we argue that high values of (ê, e) can be achieved only when the residual error distribution has very heavy tails and when no outlier presents in the data. Finally, we show that in order for (ê, e) to be bounded away from zero asymptotically,ê has to be biased.     

Near boundary behavior of primal—dual potential reduction algorithms for linear programming

This paper is concerned with selection of the-parameter in the primal—dual potential reduction algorithm for linear programming. Chosen from [n + , ), the level of determines the relative importance placed on the centering vs. the Newton directions. Intuitively, it would seem that as the iterate drifts away from the central path towards the boundary of the positive orthant, must be set close ton + . This increases the relative importance of the centering direction and thus helps to ensure polynomial convergence. In this paper, we show that this is unnecessary. We find for any iterate that can be sometimes chosen in a wide range [n + , ) while still guaranteeing the currently best convergence rate of O( L) iterations. This finding is encouraging since in practice large values of have resulted in fast convergence rates. Our finding partially complements the recent result of Zhang, Tapia and Dennis (1990) concerning the local convergence rate of the algorithm.Research supported in part by NSF Grant DDM-8922636.     

Minimum steiner trees in normed planes

A minimum Steiner tree for a given setX of points is a network interconnecting the points ofX having minimum possible total length. In this note we investigate various properties of minimum Steiner trees in normed planes, i.e., where the unit disk is an arbitrary compact convex centrally symmetric domainD having nonempty interior. We show that if the boundary ofD is strictly convex and differentiable, then each edge of a full minimum Steiner tree is in one of three fixed directions. We also investigate the Steiner ratio(D) forD, and show that, for anyD, 0.623<(D)<0.8686.Part of this work was done while Ding-Zhu Du was at the Computer Science Department, Princeton University and the Center for Discrete Mathematics and Theoretical Computer Science at Rutgers. Supported by NSF under Grant STC88-09648.     

The Whitehead Group of the Novikov Ring

The Bass–Heller–Swan–Farrell–Hsiang–Siebenmann decomposition of the Whitehead group K ₁(A[z,z^-1]) of a twisted Laurent polynomial extension A[z,z^-1] of a ring A is generalized to a decomposition of the Whitehead group K ₁(A((z))) of a twisted Novikov ring of power series A((z))=A[[z]][z^-1]. The decomposition involves a summand W₁(A, ) which is an Abelian quotient of the multiplicative group W(A,) of Witt vectors 1+a₁z+a₂z²+ ··· A[[z]]. An example is constructed to show that in general the natural surjection W(A, )^ab W₁(A, ) is not an isomorphism.     

Properties of solutions of linear functional-differential equations depending on a parameter

On the segment 0 t1 we study the equation A(d/dt, )x(t) + [F()x](t)=f(t), whereA (d/dt, ) x=x( ⁿ )+A ₁ x(^n–1 +...+ ⁿ A _n x, the matrices A₁,...,A_n are of size m × m, x is an unknown and f a given function with values in the m-dimensional space ^m , F() is a linear operator acting from a Hölder space to a Lebesgue space of vectorfunctions with values in ^m and depending on a complex parameter . We find the set of those at which a one-to-one correspondence is established between the solutions of the given equation and the solutions of the equation A(d/dt, )x(t)=0.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 43, No. 9, pp. 1213–1231, September, 1991.     

Asymptotics of the fundamental system of solutions of a linear functional-differential equation with respect to a parameter

We study a functional-differential equation, whereF is a linear operator acting from the Hölder spaceH into the Sobolev space W _p ^s [0, 1] and is a complex parameter. For large absolute values of , we construct a one-to-one correspondence between the solutionsx(;t) andy(;t) of the equations andy ⁽ⁿ⁾+y ⁿ=0. We also establish conditions that should be imposed on the operatorF in order that specially selected fundamental systems of solutions of these equationsx _j (;t) andy _j (;t), j=1,...,n, satisfy the estimate with constantsc, >0 for the functional space=W _q ^l [0, 1] or.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 6, pp. 811–836, June, 1995.This work was financially supported by the International Science Foundation and the Foundation for Fundamental Research of the Ukrainian State Committee on Science and Technology.     

An Extension of the Pizzetti Formula for Polyharmonic Functions

We represent the integral over the unit ball B in R ⁿ of any poly-harmonic function u(x) of degree m as a linear combination with constant coefficients of the integrals of its Laplacians ^j u (j = 0,...,m - 1) over any fixed(n - 1)-dimensional hypersphere S() of radius (0 1). In case = 0 theformula reduces to the classical Pizzetti formula. In particular, the cubature formula derived here integrates exactly all algebraic polynomials of degree 2m - 1.     

Best approximation and best unilateral approximation of the kernel of a biharmonic equation and optimal renewal of the values of operators

For the classB _p , 0 < 1, 1p , of 2-periodic functions of the form f(t)=u(,t), whereu (,t) is a biharmonic function in the unit disk, we obtain the exact values of the best approximation and best unilateral approximation of the kernel K(t) of the convolution f= K *g, gl, with respect to the metric of L₁. We also consider the problem of renewal of the values of the convolution operator by using the information about the values of the boundary functions.Translated from Ukrainskii Matematicheskii Zhurnal, Vol.47, No. 11, pp. 1549–1557, November, 1995.     

Relationship between the Hadamard Theorem on Three Disks and Certain Problems of Polynomial Approximation of Analytic Functions

By using the classical Hadamard theorem, we obtain an exact (in a certain sense) inequality for the best polynomial approximations of an analytic function f(z) from the Hardy space H _p, p 1, in disks of radii , ₁, and ₂, 0 < ₁ < < ₂ < 1.     

On the radicals of structural matrix rings

The relationship between the radical of a ringR and a structural matrix ring overR has been determined for some radicals. We continue these investigations, amongst others, determining exactly which radicals have the property (M(,R))=M( _s ,(R))+M( _a ,⁺(R))for any structural matrix ringM(,R) and finding (M(,R)) for any hereditary subidempotent radical .     

Deformations of homogeneous foliations

Let X be a simply connected compact homogeneous Kähler manifold, b₂(X) = 1, and let E be a homogeneous vector foliation on X. A complete effective family of deformations of a holomorphic vector foliation E , this family parametrized by a neighborhood of zero in H¹(X,o End ), is constructed.Translated from Matematicheskie Zametki, Vol. 3, No. 6, pp. 651–656, June, 1968.The author is indebted to A. L. Onishchik for his assistance and interest in the completion of the paper.     

On steiner ratio conjectures

LetM be a metric space andP a finite set of points inM. The Steiner ratio inM is defined to be(M)=inf{L _s(P)/L _m(P) |P M}, whereL _s(P) andL _m(P) are the lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. In this paper, we study various conjectures on(M). In particular, we show that forn-dimensional Euclidean space _n ,( _n )>0.615.Supported in part by the National Science Foundation of China.