On a Class of Symmetric Balanced Generalized Weighing Matrices

Let q be a prime power and m a positive integer. A construction method is given to multiply the parametrs of an -circulant BGW(v=1+q+q ₂+·+q ^m , q ^m , q ^m –q ^m–1) over the cyclic group C _n of order n with (q–1)/n being an even integer, by the parameters of a symmetric BGW(1+q ^m+1, q ^m+1, q ^m+1–q ^m ) with zero diagonal over a cyclic group C _vn to generate a symmetric BGW(1+q+·+q ^2m+1,q ^2m+1,q ^2m+1–q ^2m) with zero diagonal, over the cyclic group C _n . Applications include two new infinite classes of strongly regular graphs with parametersSRG(36(1+25+·+25^2m+1),15(25)^2m+1,6(25)^2m+1,6(25)^2m+1), and SRG(36(1+49+·+49^2m+1),21(49)^2m+1,12(49)^2m+1,12(49)^2m+1).     

The complexity and construction of many faces in arrangements of lines and of segments

We show that the total number of edges ofm faces of an arrangement ofn lines in the plane isO(m ^2/3– n ^2/3+2 +n) for any>0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of thesem faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and its expected time complexity isO(m ^2/3– n ^2/3+2 logn+n logn logm). If instead of lines we have an arrangement ofn line segments, then the maximum number of edges ofm faces isO(m ^2/3– n ^2/3+2 +n (n) logm) for any>0, where(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and takes expected timeO(m ^2/3– n ^2/3+2 log+n(n) log² n logm).The first author is pleased to acknowledge partial support by the Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the National Science Foundation under Grant CCR-8714565. Work on this paper by the third author has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD-the Israeli National Council for Research and Development. A preliminary version of this paper has appeared in theProceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 44–55.     

The complexity of many cells in arrangements of planes and related problems

We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m ^2/3 n logn +n ²); we can calculatem such cells specified by a point in each, in worst-case timeO(m ^2/3 n log³ n+n ² logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m ^2/3 n logn+n ²), but this number is onlyO(m ^3/5– n ^4/5+2 +m+n logm), for any>0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m ^3/4– n ^3/4+3 +m) log² n+n logn logm) for any>0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m ^3/4– n ^3/4+3 +m] log² n+n logn logm) for any>0. (v) The maximum number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d>3, isO(m ^2/3 n ^d/3 logn+n ^d–1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight.Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by NSF Grant CCR-8714565. Work by the third author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-82-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development. An abstract of this paper has appeared in theProceedings of the 13th International Mathematical Programming Symposium, Tokyo, 1988, p. 147.     

Laurent–Padé Approximants to Four Kinds of Chebyshev Polynomial Expansions. Part II: Clenshaw–Lord Type Approximants

Laurent–Padé (Chebyshev) rational approximants P _m (w,w ^–1)/Q _n (w,w ^–1) of Clenshaw–Lord type [2,1] are defined, such that the Laurent series of P _m /Q _n matches that of a given function f(w,w ^–1) up to terms of order w ^±(m+n), based only on knowledge of the Laurent series coefficients of f up to terms in w ^±(m+n). This contrasts with the Maehly-type approximants [4,5] defined and computed in part I of this paper [6], where the Laurent series of P _m matches that of Q _n f up to terms of order w ^±(m+n), but based on knowledge of the series coefficients of f up to terms in w ^±(m+2n). The Clenshaw–Lord method is here extended to be applicable to Chebyshev polynomials of the 1st, 2nd, 3rd and 4th kinds and corresponding rational approximants and Laurent series, and efficient systems of linear equations for the determination of the Padé–Chebyshev coefficients are obtained in each case. Using the Laurent approach of Gragg and Johnson [4], approximations are obtainable for all m0, n0. Numerical results are obtained for all four kinds of Chebyshev polynomials and Padé–Chebyshev approximants. Remarkably similar results of formidable accuracy are obtained by both Maehly-type and Clenshaw–Lord type methods, thus validating the use of either.     

Many triangulated spheres

Lets(d, n) be the number of triangulations withn labeled vertices ofS ^d–1, the (d–1)-dimensional sphere. We extend a construction of Billera and Lee to obtain a large family of triangulated spheres. Our construction shows that logs(d, n)C ₁(d)n ^[(d–1)/2], while the known upper bound is logs(d, n)C ₂(d)n ^[d/2] logn.Letc(d, n) be the number of combinatorial types of simpliciald-polytopes withn labeled vertices. (Clearly,c(d, n)s(d, n).) Goodman and Pollack have recently proved the upper bound: logc(d, n)d(d+1)n logn. Combining this upper bound forc(d, n) with our lower bounds fors(d, n), we obtain, for everyd5, that lim _n(c(d, n)/s(d, n))=0. The cased=4 is left open. (Steinitz's fundamental theorem asserts thats(3,n)=c(3,n), for everyn.) We also prove that, for everyb4, lim _d(c(d, d+b)/s(d, d+b))=0. (Mani proved thats(d, d+3)=c(d, d+3), for everyd.)Lets(n) be the number of triangulated spheres withn labeled vertices. We prove that logs(n)=2^{0.69424n(1+o(1))}. The same asymptotic formula describes the number of triangulated manifolds withn labeled vertices.Research done, in part, while the author visited the mathematics research center at AT&T Bell Laboratories.     

On the greatest length of a dead-end disjunctive normal form for almost all Boolean functions

The maximal numberl(f) of conjunctions in a dead-end disjunctive normal form (d.n.f.) of a Boolean functionf and the number (f) of dead-end d.n.f. are important parameters characterizing the complexity of algorithms for finding minimal d.n.f. It is shown that for almost all Boolean functionsl(f)2^n–1, log₂ (f)2^n–1log₂nlog₂log₂n (n).Translated from Matematicheskie Zametki, Vol. 4, No. 6, pp. 649–658, December, 1968.     

Number of no nisomorphic subgraphs in an n-point graph

LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let v_k(G) be the number of mutually nonisomorphic k-point subgraphs of G G(n). It is proved that at least |G(n)| (1–1/n) graphs G G(n) possess the following properties: a) for any k [6log₂n], where c=–c log₂c–(1–c)×log₂(1–c) and c>1/2, we havev _k(G) > C _n ^k (1–1/n²); b) for any k [cn + 5 log₂n] we havev _k(G) = C _n ^k . Hence almost all graphs G G(n) containv(G) 2ⁿ pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971.     

Approximation of discrete functions and Chebyshev polynomials orthogonal on the uniform grid

Let _N+2m ={−m, −m+1, …, −1, 0, 1, …,N−1,N, …,N−1+m}. The present paper is devoted to the approximation of discrete functions of the formf : _N+2m → ℝ by algebraic polynomials on the grid Ω _N ={0, 1, …,N−1}. On the basis of two systems of Chebyshev polynomials orthogonal on the sets Ω _N+m and Ω _N , respectively, we construct a linear operatorY _{n+2m, N} =Y _{n+2m, N} (f), acting in the space of discrete functions as an algebraic polynomial of degree at mostn+2m for which the following estimate holds (x ε Ω _N ):

A Variation of an Extremal Theorem Due to Woodall

We consider a variation of an extremal theorem due to Woodall [12, or 1, Chapter 3] as follows: Determine the smallest even integer (₃C₁,n), such that every n-term graphic sequence = (d₁, d₂,..., d_n) with term sum () = d₁ + d₂ + ... + d_n (₃C₁,n) has a realization G containing a cycle of length r for each r = 3,4,...,l. In this paper, the values of (₃C_l,n) are determined for l = 2m – 1,n 3m – 4 and for l = 2m,n 5m – 7, where m 4.AMS Mathematics subject classification (1991) 05C35Project supported by the National Natural Science Foundation of China (Grant No. 19971086) and the Doctoral Program Foundation of National Education Department of China     

An extreme value theory for long head runs

Summary For an infinite sequence of independent coin tosses withP(Heads)=p(0,1), the longest run of consecutive heads in the firstn tosses is a natural object of study. We show that the probabilistic behavior of the length of the longest pure head run is closely approximated by that of the greatest integer function of the maximum ofn(1-p) i.i.d. exponential random variables. These results are extended to the case of the longest head run interrupted byk tails. The mean length of this run is shown to be log(n)+klog(n)+(k+1)log(1–p)–log(k!)+k+/–1/2+ r₁(n)+ o(1) where log=log_1/p , =0.577 ... is the Euler-Mascheroni constant, =ln(1/p), andr ₁(n) is small. The variance is ₂/6²+1/12 +r ₂(n)+ o(1), wherer ₂(n) is again small. Upper and lower class results for these run lengths are also obtained and extensions discussed.This work was supported by a grant from the System Development Foundation     

On the rigidity of super-Grassmannians

The rigidity of the complex super-Grassmannian Gr _m|n,k|l with 0<k<m, 0<l<n, supposing that (k, l) (1,n–1), (m–1, 1), (1,n–2), (m–2, 1), (2,n–1), (m–1, 2), is proved.Partially supported by Erwin Schrödinger International Institute for Mathematical Physics (Vienna, Austria)     

Partitions of bipartite numbers

Letp _j(m, n) be the number of partitions of (m, n) into at mostj parts. We prove Landman et al.'s conjecture: for allj andn, p _j(x, 2n–x) is a maximum whenx-n. More generally we prove that for all positive integersm, n andj, p _j(n, m)=p_j(m, n)p_j(m–1, n+1) ifmn.     

Partitioning arrangements of lines II: Applications

In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m ^2/3 n ^2/3 · log^2/3 n · log^/3 (m/n)+(m+n) logn) algorithm to compute all incidences betweenm points andn lines, where is a constant <3.33; (ii) anO(m ^2/3 n ^2/3 · log^5/3 n · log^/3 (m/n)+(m+n) logn) algorithm to computem faces in an arrangement ofn lines; (iii) anO(n ^4/3 log^(+2)/3 n) algorithm to count the number of intersections in a set ofn segments; (iv) anO(n ^4/3 log^{( + 2)/3} n) algorithm to count red-blue intersections between two sets of segments, and (v) anO(n ^3/2 log^/3 n) algorithm to compute spanning trees with low stabbing number for a set ofn points. We also present an algorithm that, given set ofn points in the plane, preprocesses it, in timeO(nm log^+1/2 n), into a data structure of sizeO(m) forn lognmn ², so that the number of points ofS lying inside a query triangle can be computed inO((n/m) log^3/2 n) time.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 11–22.     

Free Resolution Invariants for Finite Groups

Given a finite group G and a G-free resolution F _* of Z, then d _G (Im(F _m+1F _m ))–(–1) ^m–i d _G (F _i ) is almost always an invariant of G.     

Milnor K-Groups and Finite Field Extensions

Let E/F be a finite separable field extension and let m denote the integral part of log₂ [E : F]. David Leep recently showed that if char(F) 2, then for n m the nth power of the fundamental ideal in the Witt ring of E satisfies the equality I ⁿ E = I ^n–m F · I ^m E. The aim of this note is to prove the analogous equality for the Milnor K-groups, that is K _n E = K _n–m F · K _m E for n m. In either of these equalities one may not replace m by m – 1, as examples of certain m-quadratic extensions indicate.     

Control of stochastic distributed-parameter systems

A scheme is proposed for the feedback control of distributed-parameter systems with unknown boundary and volume disturbances and observation errors. The scheme consists of employing a nonlinear filter in the control loop such that the controller uses the optimal estimates of the state of the system. A theoretical comparison of feedback proportional control of a styrene polymerization reactor with and without filtering is presented. It is indicated how an approximate filter can be constructed, greatly reducing the amount of computing required.Notation a(t) l-vector noisy dynamic input to system - A(t, a) l-vector function - A frequency factor for first-order rate law (5.68×10⁶ sec^–1) - b distance to the centerline between two coil banks in the reactor (4.7 cm) - B k-vector function defining the control action - c(, ) concentration of styrene monomer, molel ^–1 - C _p heat capacity (0.43 cal · g^–1 · K^–1) - C _ij constants in approximate filter, Eqs. (49)–(52) - E activation energy (20330 cal · mole^–1) - expectation operator - f(t,...) n-vector function - g ₀,g ₁(t,...) n-vector functions - h(t, u) m-vector function relating observations to states - H(t) function defined in Eq. (36) - k dimensionality of control vectorv(x, t) - k _i constants in approximate filter, Eqs. (49)–(52) - K dimensionless proportional gain - l dimensionality of dynamic inputa(t) - m dimensionality of observation vectory(t) - n dimensionality of state vectoru(x, t) - P ^(vv)(x, s, t) n×n matrix governed by Eq. (9) - P ^(va)(x, t) n×l matrix governed by Eq. (10) - P ^(aa)(t) l×l matrix governed by Eq. (11) - q _i (t) diagonal elements ofm×m matrixQ(x, s, t) - Q(x, s, t) m×m weighting matrix - R universal gas constant (1.987 cal · mole^–1 · K^–1) - R(x, s, t) n×n weighting matrix - R _i (t) n×n weighting matrix - s dimensionless spatial variable - S(x, s, t) matrix defined in Eq. (11) - t dimensionless time variable - T(, ) temperature, K - u(x, t) n-dimensional state vector - u _c (t) wall temperature - u _d desired value ofu ₁(1,t) - u _c * reference control value ofu _c - u _c ^max maximum value ofu _c - u _c ^min minimum value of _c - v(x, t) k-dimensional control vector - W(t) l×l weighting matrix - x dimensionless spatial variable - y(t) m-dimensional observation vector - _i constants in approximate filter, Eqs. (49)–(52) - dimensionless parameter defined in Eq. (29) - H heat of reaction (17500 cal · mole^–1) - dimensionless activation energy, defined in Eq. (29) - (x) Dirac delta function - (x, t) m-dimensional observation noise - thermal conductivity (0.43×10^–3 cal · cm^–1 · sec^–1 · K^–1) - density (1 g · cm^–3) - time, sec - dimensionless parameter defined in Eq. (29) - spatial variable, cm - * reference value - ^ estimated value     

Generating Random Elements in SL n (F q ) by Random Transvections

This paper studies a random walk based on random transvections in SL _n(F _q ) and shows that, given > 0, there is a constant c such that after n + c steps the walk is within a distance from uniform and that after n – c steps the walk is a distance at least 1 – from uniform. This paper uses results of Diaconis and Shahshahani to get the upper bound, uses results of Rudvalis to get the lower bound, and briefly considers some other random walks on SL _n(F _q ) to compare them with random transvections.     

Ray shooting and intersection searching amidst fat convex polyhedra in 3-space

We present a data structure for ray-shooting queries in a set of convex fat polyhedra of total complexity n in . The data structure uses O(n^2+ε) storage and preprocessing time, and queries can be answered in O(log²n) time. A trade-off between storage and query time is also possible: for any m with n<m<n², we can construct a structure that uses O(m^1+ε) storage and preprocessing time such that queries take time.We also describe a data structure for simplex intersection queries in a set of n convex fat constant-complexity polyhedra in . For any m with n<m<n³, we can construct a structure that uses O(m^1+ε) storage and preprocessing time such that all polyhedra intersecting a query simplex can be reported in O((n/m^1/3)logn+k) time, where k is the number of answers.     

The empirical process of a short-range dependent stationary sequence under Gaussian subordination

Summary Consider the stationary sequenceX ₁=G(Z ₁),X ₂=G(Z ₂),..., whereG(·) is an arbitrary Borel function andZ ₁,Z ₂,... is a mean-zero stationary Gaussian sequence with covariance functionr(k)=E(Z ₁ Z _k+1) satisfyingr(0)=1 and _k=1 |r(k)| ^m < , where, withI{·} denoting the indicator function andF(·) the continuous marginal distribution function of the sequence {X _n }, the integerm is the Hermite rank of the family {I{G(·) x} –F(x):xR}. LetF _n (·) be the empirical distribution function ofX ₁,...,X _n . We prove that, asn, the empirical processn ^1/2{F _n (·)-F(·)} converges in distribution to a Gaussian process in the spaceD[–,].Partially supported by NSF Grant DMS-9208067     

Rate of Convergence of Positive Series

We investigate the rate of convergence of series of the form