Simplexes of L-subdivisions of Euclidean spaces

It is shown that necessary and sufficient conditions for a basic simplex of a point lattice in Eⁿ space to be an L-simplex are equivalent to conditions imposed on the coefficients a_ij of the form _i,j=1 ⁿ a_ijx_ix_j– _i=1 ⁿ a_iix_i. namely, that it should assume positive values for all possible integer values of the variables x₁..., x_n (excluding the obvious n+1 cases when the form is equal to 0). These conditions are obtained for n 5.Translated from Matematicheskie Zametkij Vol. 10, No. 6, pp. 659–670, December, 1971.     

A Bernstein Property of Affine Maximal Hypersurfaces

Let x: M A ^{n + 1} be a locally strongly convex hypersurface, given as a graph of a locally strongly convexfunction x _{n + 1} =f(x ₁, ..., x _n )defined in a domain A ⁿ . We introduce a Riemannian metricG ^# = (² f/x _i x _j )dx _i dx _j on M. In this paper, we investigate the affine maximalhypersurfaces which are complete with respect to the metricG ^# and prove a Bernstein property for the affine maximalhypersurfaces.     

Numerical solutions of AXB = C for centrosymmetric matrix X under a specified submatrix constraint

We say that X = [x_ij] is centrosymmetric if x_ij = x_{n ? j + 1, n ? i + 1}, 1?i, j?n. In this paper, we present an efficient algorithm for minimizing ∥AXB ? C∥ where ∥·∥ is the Frobenius norm, A∈?^{m × n}, B∈?^{n × s}, C∈?^{m × s} and X∈?^{n × n} is centrosymmetric with a specified central submatrix [x_ij]_{p?i, j?n ? p}. Our algorithm produces a suitable X such that AXB = C in finitely many steps, if such an X exists. We show that the algorithm is stable in any case, and we give results of numerical experiments that support this claim. Copyright © 2011 John Wiley & Sons, Ltd.     

A parallel selection algorithm

The problem of selecting thekth largest or smallest element of {x _i +y _j |x _i X andy _j Y i,j} whereX=(x ₁,x ₂, ..,x _n ) andY=(y ₁,y ₂, ...,y _n ) are two arrays ofn elements each, is considered. Certain improvements to an existing algorithm are proposed. An algorithm requiringO(logk·logn) units of time on a Shared Memory Model of a parallel computer havingO(n ^1+1/) processors is presented where is a pre-assigned constant lying between 1 and 2.     

Simplex pivots on the set packing polytope

This paper considers the set packing problem max{wx: Ax b, x 0 and integral}, whereA is anm × n 0–1 matrix,w is a 1 ×n weight vector of real numbers andb is anm × 1 vector of ones. In equality form, its linear programming relaxation is max{wx: (x, y) P(A)} whereP(A) = {(x, y):Ax +I _m y =b, x0,y0}. Letx ¹ be any feasible solution to the set packing problem that is not optimal and lety ¹ =b – Ax ¹; then (x ¹,y ¹) is an integral extreme point ofP(A). We show that there exists a sequence of simplex pivots from (x ¹,y ¹) to (x*,y*), wherex* is an optimal solution to the set packing problem andy* =b – Ax*, that satisfies the following properties. Each pivot column has positive reduced weight and each pivot element equals plus one. The number of pivots equals the number of components ofx* that are nonbasic in (x ¹,y ¹).This research was supported by NSF Grants ECS-8005360 and ECS-8307473 to Cornell University.     

A structure theorem for sum form functional equations

Summary It is proved that, iff _ij:]0, 1[ C (i = 1, ,k;j = 1, ,l) are measurable, satisfy the equation (1) (with some functionsg _it, h_jt:]0, 1[ C), then eachf _ij is in a linear space (called Euler space) spanned by the functionsx x ^j(logx) ^k (x ]0, 1[;j = 1, ,M;k = 0, ,m _j – 1), where ₁, , _M are distinct complex numbers andm ₁, , m_M natural numbers. The dimension of this linear space is bounded by a linear function ofN.     

A generalization of the Gagliardo inequality

Consider functions u₁, u₂,..., u_n ∈ D(ℝ^k) and assume that we are given a certain set of linear combinations of the form ∑_{i, j} a _ij ^(l) ∂_ju_i. Sufficient conditions in terms of coefficients a _ij ^(l) are indicated under which the norms are controlled in terms of the L¹-norms of these linear combinations. These conditions are mostly transparent if k = 2. The classical Gagliardo inequality corresponds to a single function u₁ = u and the collection of its partial derivatives ∂₁u,..., ∂_ku. Bibliography: 2 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 345, 2007, pp. 120–139.     

Kleine Nullstellen quadratischer Formen in Funktionenkörpern

Letk be a field of characteristic different from 2 andt an indeterminate overk. Let0 be a quadratic form inn variables with coefficients _ij = _ji ink[t]. We show that if vanishes on ad-dimensional subspace ofk(t) ⁿ , then there is a zero (x ₁ ,...,x _n )k[t] ⁿ –{(0,...,0)} with max max{deg _ij }. We also show, that the factor is best possible.

     

Majorization of Gaussian processes and geometric applications

Summary Let (x _i ^* ) _i=1 ⁿ denote the decreasing rearrangement of a sequence of real numbers (x _i ) _i=1 ⁿ . Then for everyij, and every 1kn, the 2-nd order partial distributional derivatives satisfy the inequality, . As a consequence we generalize the theorem due to Fernique and Sudakov. A generalization of Slepian's lemma is also a consequence of another differential inequality. We also derive a new proof and generalizations to volume estimates of intersecting spheres and balls in ⁿ proved by Gromov.Supported by NSF grant # DMS 8909745, and the USA-Israel Binational Science Foundation grant # 86-00074, and grant for the Promotion of Research at the Technion     

A problem arising in finite population sampling theory

A probability sampling design is a probability functionp(s) on subsetss of [1, ..., i, ..., N. Let _ij denote the joint inclusion probability fori andj. The problem is to determine conditions under which a fixed size (n) sampling designp exists so that _ij (x _i –x _j )² for a vector of real numbersx=(x ₁, ...,x _N ), or equivalently, so that for some order of the coefficients _ik = _ij + _jk . Some necessary conditions for the proportionality to hold are obtained, and it is conjectured that it is satisfied only in special circumstances.     

Approximating Scheduling Unrelated Parallel Machines in Parallel

We show how to approximate in NC the problem of scheduling unrelated parallel machines, for a fixed number of machines in which the makespan C _max is the objective function to minimize. We develop an approximate NC algorithm which finds a schedule whose length is at most (1+o(1))(C^* _max + 3 C^* _maxln(2n(n-1)/)), where C*_max denotes the optimal schedule, n the total number of jobs and a small positive constant. Our approach shows how to relate the linear program obtained by relaxing the integer programming formulation of the problem with a linear program formulation that is positive and in the packing/covering form. The established relationship enables us to transfer approximate fractional solutions from the later formulation that is known to be approximable in NC. Then, we show how to obtain an integer approximate solution, i.e. a schedule, from the fractional one, using the randomized rounding technique. We stress that our analysis assumes that the length of the schedule is (ln n) and that the min p _ij and max p _ij values are not too disparate (where p _ij is the time to run job j on machine i).Finally, we show that the same technique can be applied to the general assignment problem with a fixed number of machines and makespan T.     

Dual-orthogonal polynomials

Let (x, ) and (x,) be two functions,x[a, b] and { _j } _j=1 and { _j } _j=1 be two sequences where _{i j} and _{i j} whenij. We define the vector spacesU _k =span{(x, _j )} _j=1 ^k andV _k =span{(x, _j )} _j=1 ^k where we assume thatdim(U _k )=dim(V _k )=k,k1. We then look for the generalized polynomialsp _m xU _m+1\U _m so that _a ^b p _m (x)(x, _j )d(x)=0,j=1,2,...,m. If such generalized polynomials exist for allm1 we say that {p _m } _m=1 is a dual-orthogonal polynomial sequence from {(x, _j )} _j=1 to {(x, _j )} _j=1 with respect to the distribution (x),x[a, b]. In this article we present existence theorems for dual-orthogonal polynomials, explicit formulae forp _m(x), theorems about the zeros ofp _m(x), and, in the end, a Gauss-type quadrature formula for dual-orthogonal polynomials.     

Generalized Hadamard Matrices

The paper studies a generalized Hadamard matrix H = (g _{i j}) of order n with entries gi j from a group G of order n. We assume that H satisfies: (i) For m k, G = {g _{m i} g k i ^-1 i = 1,...., n} (ii) g _1i = g _i1 = 1 for each i; (iii) g _ij ^-1 = g _ji for all i, j. Conditions (i) and (ii) occur whenever G is a(P, L) -transitivity for a projective plane of order n. Condition (iii) holds in the case that H affords a symmetric incidence matrix for the plane. The paper proves that G must be a 2-group and extends previous work to the case that n is a square.     

Möbius Isoparametric Hypersurfaces in S n+1 with Two Distinct Principal Curvatures

A hypersurface x : M → S ⁿ⁺¹ without umbilic point is called a Möbius isoparametric hypersurface if its Möbius form Φ = ?ρ ^?2∑ _i (e _i (H) + ∑ _j (h _ij ?Hδ _ij )e _j (log ρ))θ _i vanishes and its Möbius shape operator $ {\Bbb {S}}A hypersurface x : M → S ^{n +1} without umbilic point is called a M?bius isoparametric hypersurface if its M?bius form Φ = −ρ⁻²∑ _i (e _i (H) + ∑ _j (h _ij −Hδ _ij )e _j (log ρ))θ _i vanishes and its M?bius shape operator ? = ρ⁻¹(S−Hid) has constant eigenvalues. Here {e _i } is a local orthonormal basis for I = dx·dx with dual basis {θ _i }, II = ∑ _ij h _ij θ _i ⊗θ _i is the second fundamental form, and S is the shape operator of x. It is clear that any conformal image of a (Euclidean) isoparametric hypersurface in S ^{n +1} is a M?bius isoparametric hypersurface, but the converse is not true. In this paper we classify all M?bius isoparametric hypersurfaces in S ^{n +1} with two distinct principal curvatures up to M?bius transformations. By using a theorem of Thorbergsson [1] we also show that the number of distinct principal curvatures of a compact M?bius isoparametric hypersurface embedded in S ^{n +1} can take only the values 2, 3, 4, 6. Received September 7, 2001, Accepted January 30, 2002     

Lax Representation for a Triplet of Scalar Fields

We construct a 3×3 matrix zero-curvature representation for the system of three two-dimensional relativistically invariant scalar fields. This system belongs to the class described by the Lagrangian L = [g _ij(u)u _x ⁱ u _t ^j]/2+f(u), where g _ij is the metric tensor of a three-dimensional reducible Riemannian space. We previously found all systems of this class that have higher polynomial symmetries of the orders 2, 3, 4, or 5. In this paper, we find a zero-curvature representation for one of these systems. The calculation is based on the analysis of an evolutionary system u _t = S(u), where S is one of the higher symmetries. This approach can also be applied to other hyperbolic systems. We also find recursion relations for a sequence of conserved currents of the triplet of scalar fields under consideration.     

On solutions of the Ricci curvature equation and the Einstein equation

We consider the pseudo-Euclidean space (R ⁿ , g), with n ≥ 3 and g _ij = δ _ij ε _i , ε _i = ±1, where at least one ε _i = 1 and nondiagonal tensors of the form T = Σ _ij f _ij dx _i dx _j such that, for i ≠ j, f _ij (x _i , x _j ) depends on x _i and x _j . We provide necessary and sufficient conditions for such a tensor to admit a metric ḡ, conformal to g, that solves the Ricci tensor equation or the Einstein equation. Similar problems are considered for locally conformally flat manifolds. Examples are provided of complete metrics on R ⁿ , on the n-dimensional torus T ⁿ and on cylinders T ^k ×R ^n-k , that solve the Ricci equation or the Einstein equation. Partially supported by CAPES/PROCAD. Partially Supported By Cnpq, Capes/Procad.     

Certain complexes associated to a sequence and a matrix

Let R be a commutative noetherian ring with unit. To a sequencex:=x₁,...,x_n of elements of R and an m-by-n matrix α:=(α_ij) with entries in R we assign a complex D*(x;α), in case that m=n or m=n?1. These complexes will provide us in certain cases with explicit minimal free resolutions of ideals, which are generated by the elements a_i:=∑α_ijx_j and the maximal minors of α.     

A note on "More Operator Versions of the Schwarz Inequality"

It is shown that for any (n + 1)-positive (possibly non-linear) map and any bounded linear operators A _i ,i = 1,¨,n we have [(A _i ^* A _j )] _{i,j = 1} ^*[(A _i )^*(A _j )] _{i,j = 1} ^*, and that the statement is false if "(n + 1)-positive" is replaced by "n-positive". This resolves an issue raised by Bhatia and Davis in relation to a Schwartz inequality which can be regarded as a non-commutative variance-covariance inequality [2]     

On the cost of approximating all roots of a complex polynomial

This work examines the computational complexity of a homotopy algorithm in approximating all roots of a complex polynomialf. It is shown that, probabilistically, monotonic convergence to each of the roots occurs after a determined number of steps. Moreover, in all subsequent steps, each rootz is approximated by a complex numberx, where ifx ₀ =x, x _j =x _j–1 –f(x _j–1)/f(x _j–1),j = 1, 2,, then |x _j –z| < (1/|x ₀ –z|)|x _j–1–z|².