On tilings of the binary vector space

Let n be a positive integer, L a subset of {0, 1,…,n}. We discuss the existence of partitions (or tilings) of the n-dimensional binary vector space F_n into L-spheres. By a L-sphere around an x in F_n we mean {y ? F_n, d(x, y) ? L}, d(x, y) being the Hamming distance betwe en x and y. These tilings are generalizations of perfect error correcting codes. We show that very few such tilings exist (Theorem 2) and characterize them all for any L ? {0, 1,…,[$\text{1}\text{2}$n]}.     

Existence of stable equilibrium point for dynamical systems of Volterra type

This paper presents sufficient conditions for the existence of a nonnegative and stable equilibrium point of a dynamical system of Volterra type, (1) $\text{(}\text{d}\text{dt}\text{) x}{}_{\mathrm{i}}\text{(t) = ?x}{}_{\mathrm{i}}\text{(t)[f}{}_{\mathrm{i}}\text{(x}{}_1\text{(t),…, x}{}_{\mathrm{n}}\text{(t)) ? q}{}_{\mathrm{i}}\text{], i = 1,…, n}$, for every q = (q₁,…, q_n)^T?Rⁿ. Results of a nonlinear complementarity problem are applied to obtain the conditions. System (1) has a nonnegative and stable equilibrium point if (i) f(x) = (f₁(x),…,f_n(x))^T is a continuous and differentiable M-function and it satisfies a certain surjectivity property, or (ii), f(x) is continuous and strongly monotone on R₊₀ⁿ.     

A characterization of robert's inequality for boxicity

F.S. Roberts defined the boxicity of a graph G as the smallest positive integer n for which there exists a function F assigning to each vertex x?G a sequence F(x)(1),F(x)(2),…, F(x)(n) of closed intervals of R so that distinct vertices x and y are adjacent in G if and only if F(x)(i)∩F(y)(i)≠? fori = 1, 2, 3, …, n. Roberts then proved that if G is a graph having 2n + 1 vertices, thentheboxicityofGisatmostn. In this paper, we provide an explicit characterization of this inequality by determining for each n ? 1 the minimum collection $\text{C}$_n of graphs so that a graph G having 2n + 1 vertices has boxicity n if and only if it contains a graph from $\text{C}$_n as an induced subgraph. We also discuss combinatorial connections with analogous characterization problems for rectangle graphs, circular arc graphs, and partially ordered sets.     

Classes of orderings of measures and related correlation inequalities. I. Multivariate totally positive distributions

A function f(x) defined on $\text{X}$ = $\text{X}$₁ × $\text{X}$₂ × … × $\text{X}$_n where each $\text{X}$_i is totally ordered satisfying f(x ∨ y) f(x ∧ y) ≥ f(x) f(y), where the lattice operations ∨ and ∧ refer to the usual ordering on $\text{X}$, is said to be multivariate totally positive of order 2 (MTP₂). A random vector Z = (Z₁, Z₂,…, Z_n) of n-real components is MTP₂ if its density is MTP₂. Classes of examples include independent random variables, absolute value multinormal whose covariance matrix Σ satisfies ?DΣ^?1D with nonnegative off-diagonal elements for some diagonal matrix D, characteristic roots of random Wishart matrices, multivariate logistic, gamma and F distributions, and others. Composition and marginal operations preserve the MTP₂ properties. The MTP₂ property facilitate the characterization of bounds for confidence sets, the calculation of coverage probabilities, securing estimates of multivariate ranking, in establishing a hierarchy of correlation inequalities, and in studying monotone Markov processes. Extensions on the theory of MTP₂ kernels are presented and amplified by a wide variety of applications.     

Phase reconstruction from magnitude of band-limited multidimensional signals

In this paper, the problem of phase reconstruction from magnitude of multidimensional band-limited functions is considered. It is shown that any irreducible band-limited function f(z₁…,z_n), z_i ? $\text{C}$, i=1, …, n, is uniquely determined from the magnitude of f(x₁…,x_n): | f(x₁…,x_n)|, x_i ? $\text{R}$, i=1,…, n, except for (1) linear shifts: ^{i(α1z1+…+α_n2n+β}), β, α_i?$\text{R}$, i=1,…, n; and (2) conjugation: $\text{f}{}^1\text{(z}{}_1{}^1\text{,…,z}{}_{\mathrm{n}}{}^1\text{)}$.     

A method of feasible directions using function approximations,with applications to min max problems

This paper presents a demonstrably convergent method of feasible directions for solving the problem min{φ(ξ)| gⁱ(ξ)?0i=1,2,…,m}, which approximates, adaptively, both φ(x) and ▽φ(x). These approximations are necessitated by the fact that in certain problems, such as when $\text{φ(x) =}\text{max}\text{{f(x, y) ¦ y ? Ω}{}_{\mathrm{y}}\text{}}$, a precise evaluation of φ(x) and ▽φ(x) is extremely costly. The adaptive procedure progressively refines the precision of the approximations as an optimum is approached and as a result should be much more efficient than fixed precision algorithms.It is outlined how this new algorithm can be used for solving problems of the form $\text{min}{}_{\mathrm{y}}\text{? Ω}{}_{\mathrm{x}}\text{max}{}_{\mathrm{y}}\text{? Ω}{}_{\mathrm{y}}\text{f(x, y)}$ under the assumption that Ωm_ξ={x|gⁱ(x)?0, j=1,…,s} ∩$\text{R}$ⁿ, Ω_y={y|ζ_i(y)?0, i-1,…,t} ∩ $\text{R}$^m, with f, g^j, ζⁱ continuously differentiable, f(x, ·) concave, ζⁱ convex for $\text{i = 1,…, t,}\text{and}\text{Ω}{}_{\mathrm{x}}\text{, Ω}{}_{\mathrm{y}}$ compact.     

On distribution by rank of bases for vector spaces of matrices over a finite field

Let F^m×n_q denote the vector space of all m×n matrices over the finite field F_q of order q, and let $\text{B}\text{=(A}{}_1\text{,A}{}_2\text{,…,A}{}_{\mathrm{mn}}\text{)}$ denote an ordered basis for F^m×n_q. If the rank of A_i is r_i,i=1,2,…,mn, then $\text{B}$ is said to have rank (r₁,r₂,…,r_mn), and the number of ordered bases of F^mxn_q with rank (r₁,r₂,…,r_mn is denoted by N_q(r₁, r₂,…,r_mn). This paper determines formulas for the numbers N_q(r₁,r₂,…,r_mn) for the case m=n=2, q arbitrary, and while some of the techniques of the paper extend to arbitrary m and n, the general formulas for the numbers N_q(r₁,r₂,…,r_mn) seem quite complicated and remain unknown. An idea on a possible computer attack which may be feasible for low values of m and n is also discussed.     

A new inequality for symmetric functions

Let x_i ≥ 0, y_i ≥ 0 for i = 1,…, n; and let a_j(x) be the elementary symmetric function of n variables given by a_j(x) = ∑_{1 ≤ ii < … <ij ≤ n}x_ii … x_ij. Define the partical ordering x <y if a_j(x) ≤ a_j(y), j = 1,… n. We show that $\text{x}\text{\$}\text{?}\text{y ? x}{}^{\mathrm{\alpha }}\text{\$}\text{?}\text{y}{}^{\mathrm{\alpha }}\text{, 0}\text{\$}\text{?}\text{α ≤ 1}$, where {x^α}_i = x^α_i. We also give a necessary and sufficient condition on a function f(t) such that x <y ? f(x) <f(y). Both results depend crucially on the following: If x <y there exists a piecewise differentiable path z(t), with z_i(t) ≥ 0, such that z(0) = x, z(1) = y, and z(s) <z(t) if 0 ≤ s ≤ t ≤ 1.     

Arithmetic in generalized Artin-Schreier extensions of k(x)

If k is a perfect field of characteristic p ≠ 0 and k(x) is the rational function field over k, it is possible to construct cyclic extensions K_n over k(x) such that [K : k(x)] = pⁿ using the concept of Witt vectors. This is accomplished in the following way; if [β₁, β₂,…, β_n] is a Witt vector over k(x) = K₀, then the Witt equation $\text{y}{}^{\mathrm{p}}\text{?}\text{y}\text{= β}$ generates a tower of extensions through $\text{K}{}_{\mathrm{i}}\text{= K}{}_{\mathrm{i?1}}\text{(}\text{y}{}_{\mathrm{i}}\text{)}$ where $\text{y}\text{= [}\text{y}{}_1\text{,}\text{y}{}_2\text{,…,}\text{y}{}_{\mathrm{n}}\text{]}$. In this paper, it is shown that there exists an alternate method of generating this tower which lends itself better for further constructions in K_n. This alternate generation has the form K_i = K_i?1(y_i); y_i^p ? y_i = B_i, where, as a divisor in K_i?1, B_i has the form . In this form q is prime to Πp_j^λ_j and each λ_j is positive and prime to p. As an application of this, the alternate generation is used to construct a lower-triangular form of the Hasse-Witt matrix of such a field K_n over an algebraically closed field of constants.     

Decomposability of symmetric multilinear functions

Let V denote a finite dimensional vector space over a field K of characteristic 0, let T_n(V) denote the vector space whose elements are the K-valued n-linear functions on V, and let S_n(V) denote the subspace of T_n(V) whose members are the fully symmetric members of T_n(V). If $\text{L}$_n denotes the symmetric group on {1,2,…,n} then we define the projection $\text{P}{}_{\mathrm{<mtext>L</mtext>}}\text{: T}{}_{\mathrm{n}}\text{(V) → S}{}_{\mathrm{n}}\text{(V)}$ by the formula , where P_σ : T_n(V) → T_n(V) is defined so that P_σ(A)(y₁,y₂,…,y_n = A(y_σ(1),y_σ(2),…,y_σ(n)) for each A?T_n(V) and y_i?V, 1 ? i ? n. If $\text{x}{}_{\mathrm{i}}\text{? V}{}^1\text{, 1 ? i ? n}$, then x₁?x₂? … ?x_n denotes the member of T_n(V) such that $\text{(x}{}_1\text{?x}{}_2\text{· ? ? ?x}{}_{\mathrm{n}}\text{)(y}{}_1\text{,y}{}_2\text{,…,y}{}_{\mathrm{n}}\text{) = П}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{x}{}_{\mathrm{i}}\text{(y}{}_{\mathrm{i}}\text{)}$ for each y₁ ,₂,…,y_n in V, and x₁·x₂… x_n denotes $\text{P}{}_{\mathrm{<mtext>L</mtext>}}\text{(x}{}_1\text{?x}{}_2\text{? … ?x}{}_{\mathrm{n}}\text{)}$. If B? S_n(V) and there exists $\text{x}{}_{\mathrm{i}}\text{? V}{}^1\text{, 1 ? i ? n}$, such that B = x₁·x₂…x_n, then B is said to be decomposable. We present two sets of necessary and sufficient conditions for a member B of S_n(V) to be decomposable. One of these sets is valid for an arbitrary field of characteristic zero, while the other requires that K = R or C.     

An interpolant defined by subdivision and the analysis of the error

Given a set of points x_i, i=0,…,n on [−1,1] and the corresponding values y_i, i=0,…,n of a 2-periodic function y(x), supplied in some way by interpolation or approximation, we describe a simple method that by doubling iteratively this original set, produces in the limit a smooth function. The analysis of the interpolation error is given.We show that if $\text{y∈}\text{C}{}^4$ then the error in the p-norm, $\text{p=1,}\text{2}$ and ∞ depends on the magnitude of the fourth derivative of the function y(x) and on a function α(x) which is even, concave and bounded on [−1,1].     

Numerical approximation of product integrals

A technique for the numerical approximation of matrix-valued Riemann product integrals is developed. For a ? x < y ? b, I_m(x, y) denotes

$\text{∫}\text{χ}\text{y}\text{∫}\text{χ}\text{v}{}_2\text{?}\text{∫}\text{χ}\text{v}{}_2\text{∏}\text{i=1}\text{m}\text{F(ν}{}_{\mathrm{i}}\text{)dν}{}_1\text{dν}{}_2\text{?dν}{}_{\mathrm{m}}$

, and A_m(x, y) denotes an approximation of I_m(x, y) of the form

$\text{(y?x)}{}^{\mathrm{m}}\text{∑}\text{k=1}\text{n}\text{a}{}_{\mathrm{k}}\text{∏}\text{i=1}\text{m}\text{F(χ}{}_{\mathrm{ik}}\text{)}$

, where a_k and y_ik are fixed numbers for i = 1, 2,…, m and k = 1, 2,…, N and x_ik = x + (y ? x)y_ik. The following result is established. If p is a positive integer, F is a function from the real numbers to the set of w × w matrices with real elements and F⁽¹⁾ exists and is continuous on [a, b], then there exists a bounded interval function H such that, if n, r, and s are positive integers, $\text{(b ? a)}\text{n}\text{= h < 1, x}{}_{\mathrm{i}}\text{= a + hi}\text{for}\text{i = 0, 1,…, n}\text{and}\text{0 < r ? s ? n}$, then

$\text{∏}\text{χ}{}_{\mathrm{r?}}\text{χ}{}_{\mathrm{s}}\text{(I+F dχ)?}\text{∏}\text{i=r}\text{s}\text{I+}\text{∑}\text{j=1}\text{p}\text{I}{}_{\mathrm{j}}\text{(χ}{}_{\mathrm{i?1}}\text{,χ}{}_{\mathrm{i}}\text{)}$

$\text{=h}{}^{\mathrm{p}}\text{H(χ}{}_{\mathrm{r?1}}\text{,χ}{}_{\mathrm{s}}\text{)+O(h}{}^{\mathrm{p+1}}\text{)}$

Further, if F^(j) exists and is continuous on [a, b] for j = 1, 2,…, p + 1 and A is exact for polynomials of degree less than p + 1 ? j for j = 1, 2,…, p, then the preceding result remains valid when A_j is substituted for I_j.     

On moment-discretization and least-squares solutions of linear integral equations of the first kind

Let K(s, t) be a continuous function on [0, 1] × [0, 1], and let $\text{K}$ be the linear integral operator induced by the kernel K(s, t) on the space $\text{L}$₂[0, 1]. This note is concerned with moment-discretization of the problem of minimizing 6K_x?y6 in the $\text{L}$₂-norm, where y is a given continuous function. This is contrasted with the problem of least-squares solutions of the moment-discretized equation: ∝₀¹K(s_i, t) x(t) dt = y(s_i), i = 1, 2,h., n. A simple commutativity result between the operations of “moment-discretization” and “least-squares” is established. This suggests a procedure for approximating $\text{K2y}$ (where $\text{K}$² is the generalized inverse of $\text{K}$), without recourse to the normal equation $\text{K1Kx = K1y}$, that may be used in conjunction with simple numerical quadrature formulas plus collocation, or related numerical and regularization methods for least-squares solutions of linear integral equations of the first kind.     

An existence theorem for antichains

Let k₁, k₂,…, k_n be given integers, 1 ? k₁ ? k₂ ? … ? k_n, and let S be the set of vectors x = (x₁,…, x_n) with integral coefficients satisfying 0 ? x_i ? k_i, i = 1, 2, 3,…, n. A subset H of S is an antichain (or Sperner family or clutter) if and only if for each pair of distinct vectors x and y in H the inequalities x_i ? y_i, i = 1, 2,…, n, do not all hold. Let |H| denote the number of vectors in H, let K = k₁ + k₂ + … + k_n and for 0 ? l ? K let (l)H denote the subset of H consisting of vectors h = (h₁, h₂,…, h_n) which satisfy h₁ + h₂ + … + h_n = l. In this paper we show that if H is an antichain in S, then there exists an antichain H′ in S for which |(l)H′| = 0 if $\text{l <}\text{K}\text{2}$, $\text{|(}\text{K}\text{2}\text{)H′| = |(}\text{K}\text{2}\text{)H|}$ if K is even and |(l)H′| = |(l)H| + |(K ? l)H| if $\text{l>}\text{K}\text{2}$.     

Infinite-variate wide-sense Markov processes and functional analysis for bounded operator-forming vectors

Let p, q be arbitrary parameter sets, and let $\text{H}$ be a Hilbert space. We say that x = (xⁱ)_i?q, xⁱ ? $\text{H}$, is a bounded operator-forming vector (?$\text{H}$_F^q) if the Gram matrix 〈x, x〉 = [(xⁱ, x^j)]_i?q,j?q is the matrix of a bounded (necessarily ≥ 0) operator on $\text{l}{}_{\mathrm{q}}{}^2$, the Hilbert space of square-summable complex-valued functions on q. Let A be p × q, i.e., let A be a linear operator from $\text{l}{}_{\mathrm{q}}{}^2$ to $\text{l}{}_{\mathrm{p}}{}^2$. Then exists a linear operator ǎ from (the Banach space) $\text{H}$_F^q to $\text{H}$_F^p on $\text{D}$(A) = {x:x ? $\text{H}$_F^q, $\text{A〈x, x〉}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ is p × q bounded on $\text{l}{}_{\mathrm{q}}{}^2$} such that y = ǎx satisfies y^j?σ(x) = {space spanned by the xⁱ}, 〈y, x〉 = A〈x, x〉 and $\text{〈y, y〉 = A〈x, x〉}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{(A〈x, x〉}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}{}^1$. This is a generalization of our earlier [J. Multivariate Anal.4 (1974), 166–209; 6 (1976), 538–571] results for the case of a spectral measure concentrated on one point. We apply these tools to investigate q-variate wide-sense Markov processes.     

A continuation method for solving separable nonlinear least squares problems

Given the data (x_i, y_i), i=1, 2, …, n, the problem is to find the values of the linear and nonlinear parameters â and b? which minimize the nonlinear functional |F(b)a?y|₂² over $\text{a ?}\text{R}{}^{\mathrm{p}}\text{, b ?}\text{R}{}^{\mathrm{q}}\text{,}\text{where}\text{F ?}\text{R}{}^{\mathrm{n\times p}}$ is a variable matrix and assumed to be of full rank, and $\text{y ?}\text{R}{}^{\mathrm{n}}$ is a constant vector.In this paper, we present a method for solving this problem by imbedding it into a one-parameter family of problems and by following its solution path using a predictor-corrector algorithm. In the course of iterations, the original problem containing p+q+1 variables is transformed into a problem with q+1 nonlinear variables by taking the separable structure of the problem into account. By doing so, the method reduces to solving a series of equations of smaller size and a considerable saving in the storage is obtained.Results of numerical experiments are reported to demonstrate the effectiveness of the proposed method.     

Construction of translation planes from t-spread sets

A t-spread set [1] is a set $\text{C}$ of (t + 1) × (t + 1) matrices over GF(q) such that ∥C∥ = q^t+1, 0 ? C, I?C, and det(X ? Y) ≠ 0 if X and Y are distinct elements of $\text{C}$. The amount of computation involved in constructing t-spread sets is considerable, and the following construction technique reduces somewhat this computation. Construction: Let $\text{G}$ be a subgroup of GL(t + 1, q), (the non-singular (t + 1) × (t + 1) matrices over GF(q)), such that ∥G∥|a^t+1, and det (G ? H) ≠ 0 if G and H are distinct elements of $\text{G}$. Let A₁, A₂, …, A_n?GL(t + 1, q) such that det(A_i ? G) ≠ 0 for i = 1, …, n and all G?G, and det(A_i ? A_jG) ≠ 0 for i > j and all G?G. Let $\text{C = \&{0\&} ∪ G ∪ A}{}_1\text{G ∪ … ∪ A}{}_{\mathrm{n}}\text{G}$, and ∥C∥ = q^t+1. Then $\text{C}$ is a t-spread set. A t-spread set can be used to define a left V ? W system over V(t + 1, q) as follows: x + y is the vector sum; let e?V(t + 1, q), then xoy = yM(x) where M(x) is the unique element of $\text{C}$ with x = eM(x). Theorem: Let$\text{C}$be a t-spread set and F the associatedV ? Wsystem; the left nucleus = {y | CM(y) = C}, and the middle nucleus = }y | M(y)C = C}. Theorem: For$\text{C}$constructed as aboveG ? {M(x) | x?N_λ}. This construction technique has been applied to construct a V ? W system of order 25 with ∥N_λ∥ = 6, and ∥N_μ∥ = 4. This system coordinatizes a new projective plane.     

Characterization of projective graphs

We denote the distance between vertices x and y of a graph by d(x, y), and p_ij(x, y) = ∥ {z : d(x, z) = i, d(y, z) = j} ∥. The (s, q, d)-projective graph is the graph having the s-dimensional subspaces of a d-dimensional vector space over GF(q) as vertex set, and two vertices x, y adjacent iff $\text{dim}\text{(x ? y) = s ? 1}$. These graphs are regular graphs. Also, there exist integers λ and μ > 4 so that μ is a perfect square, p₁₁(x, y) = λ whenever d(x, y) = 1, and p₁₁(x, y) = μ whenever d(x, y) = 2. The (s, q, d)-projective graphs where $\text{2d}\text{3}\text{≤ s < d ? 2}$ and $\text{(s, q, d) ≠ (}\text{2d}\text{3}\text{, 2, d)}$, are characterized by the above conditions together with the property that there exists an integer r satisfying certain inequalities.     

Diophantine problems in variables restricted to the values 0 and 1

Let $\text{F}$x₁,…,x_s be a form of degree d with integer coefficients. How large must s be to ensure that the congruence $\text{F}$(x₁,…,x_s) ≡ 0 (mod m) has a nontrivial solution in integers 0 or 1? More generally, if $\text{F}$ has coefficients in a finite additive group G, how large must s be in order that the equation $\text{F}$(x₁,…,x_s) = 0 has a solution of this type? We deal with these questions as well as related problems in the group of integers modulo 1 and in the group of reals.