Prime Ideals of <Emphasis Type="Italic">q</Emphasis>-Commutative Power Series Rings

We study the “q-commutative” power series ring R: = k _q [[x ₁,...,x _n ]], defined by the relations x _i x _j  = q _ij x _j x _i , for mulitiplicatively antisymmetric scalars q _ij in a field k. Our results provide a detailed account of prime ideal structure for a class of noncommutative, complete, local, noetherian domains having arbitrarily high (but finite) Krull, global, and classical Krull dimension. In particular, we prove that the prime spectrum of R is normally separated and is finitely stratified by commutative noetherian spectra. Combining this normal separation with results of Chan, Wu, Yekutieli, and Zhang, we are able to conclude that R is catenary. Following the approach of Brown and Goodearl, we also show that links between prime ideals are provided by canonical automorphisms. Moreover, for sufficiently generic q _ij , we find that R has only finitely many prime ideals and is a UFD (in the sense of Chatters).     

Bipartite Graphs Whose Edge Algebras Are Complete Intersections

Let R be a monomial subalgebra of k[x₁,…,x_N] generated by square free monomials of degree two. This paper addresses the following question: when is R a complete intersection? For such a k-algebra we can associate a graph G whose vertices are x₁,…,x_N and whose edges are {(x_i, x_j)|x_ix_j  R}. Conversely, for any graph G with vertices {x₁,…,x_N} we define the edge algebra associated with G as the subalgebra of k[x₁,…,x_N] generated by the monomials {x_ix_j|(x_i, x_j) is an edge of G}. We denote this monomial algebra by k[G]. This paper describes all bipartite graphs whose edge algebras are complete intersections.     

Approximation of elements of a generalized Orlicz sequence space by nonlinear, singular kernels

Let l be a generalized Orlicz sequence space generated by a modular (x) = ∑_{i − 0}^∞ _i(¦t_i¦), X = (t_i), with s-convex functions _i, 0 < s 1, and let K_w,j: R₊ → R₊ for j=0,1,2,…, w ε Wwhere is an abstract set of indices. Assuming certain singularity assumptions on the nonlinear kernel K_w,j and setting T_wx = ((T_wx)_i)_{i = 0}^∞, with (T_wx)_i = ∑_{j = 0}ⁱ K_{w,i − j}(¦t_j¦) for x = (t_j), convergence results: T_wx → x in l are obtained (both modular convergence and norm convergence), with respect to a filter of subsets of the set .     

A Note on K-Theory of Azumaya Algebras

For an Azumaya algebra A which is free over its centre R, we prove that K-theory of A is isomorphic to K-theory of R up to its rank torsions. We conclude that K _i (A, ?/m) = K _i (R, ?/m) for any m relatively prime to the rank and i ≥ 0. This covers, for example, K-theory of division algebras, K-theory of Azumaya algebras over semilocal rings, and K-theory of graded central simple algebras indexed by a totally ordered abelian group.     

K2 of a Ring via the G-Construction

We interpret the Steinberg symbols x_i,j(a) as homotopies contracting the elementary matrices e_i,j(a), the latters being represented by certain arcs in a simplicial model of the K-theory. We further prove the Steinberg relations for these homotopies. This provides an explicit map from K₂ of a ring, defined classically as ker(St(R) → GL(R)), to π₂ of the G-construction assigned to R. Though the two groups are known to be isomorphic, a certain work is to be done to prove that this explicit map is an isomorphism. Mathematics Subject Classification 1991: Primary 19B99, 19D99; secondary 18E10, 18F25.     

Graph monoids

A graph semigroup refers to a monoid whose defining relations are of the form x_ix_j=x_jx_i. We describe the centralizer of an arbitrary element of a graph semigroup, show that there exists a unique factorization of any element into commuting parts, and prove related results. Dedicated to L. M. Gluskin on the occasion of his sixtieth birthday     

Betti numbers of determinantal ideals

Let R=k[x₁,…,x_n] be a polynomial ring and let IR be a graded ideal. In [T. Römer, Betti numbers and shifts in minimal graded free resolutions, arXiv: AC/070119], Römer asked whether under the Cohen–Macaulay assumption the ith Betti number β_i(R/I) can be bounded above by a function of the maximal shifts in the minimal graded free R-resolution of R/I as well as bounded below by a function of the minimal shifts. The goal of this paper is to establish such bounds for graded Cohen–Macaulay algebras k[x₁,…,x_n]/I when I is a standard determinantal ideal of arbitrary codimension. We also discuss other examples as well as when these bounds are sharp.     

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|².     

Smallest maximal snakes of translates of convex domains

LetK be a convex domain. A maximal snake of sizen is a set of non-overlapping translatesK ₁, ...,K _N ofK, whereK _i touchesK _j if and only if |i –j|=1 and no translate ofK can touchK ₁ orK _n without intersecting an additionalK _i ,i=1, ...,n. The size of the smallest maximal snake is proved to be 11 ifK is a parallelogram and to be 10 otherwise.     

Matrices associated with arithmetical functions

Let f be an arithmetical function and S={x ₁,x ₂,…,x_n } a set of distinct positive integers. Denote by [f(x_i ,x_j }] the n×n matrix having f evaluated at the greatest common divisor (x_i ,x_j ) of x_i , and x_j as its i j-entry. We will determine conditions on f that will guarantee the matrix [f(x_i ,x_j )] is positive definite and, in fact, has properties similar to the greatest common divisor (GCD) matrix

[(x_i ,x_j )] where f is the identity function. The set S is gcd-closed if (x_i ,x_j )∈S for 1≤ i j ≤ n. If S is gcd-closed, we calculate the determinant and (if it is invertible) the inverse of the matrix [f(x_i ,x_j )]. Among the examples of determinants of this kind are H. J. S. Smith's determinant det[(i,j)].     

On Characterization of Best Approximation with Certain Constraints

SupposeKis the intersection of a finite number of closed half-spaces {K_i} in a Hilbert spaceX, andx∈X\K. Dykstra's cyclic projections algorithm is a known method to determine an approximate solution of the best approximation ofxfromK, which is denoted byP_K(x). Dykstra's algorithm reduces the problem to an iterative scheme which involves computing the best approximation from the individualK_i. It is known that the sequence {x_j} generated by Dykstra's method converges to the best approximationP_K(x). But since it is difficult to find the definite value of an upper bound of the error ‖x_j−P_K(x)‖, the applicability of the algorithm is restrictive. This paper introduces a new method, called thesuccessive approximate algorithm, by which one can generate a finite sequencex₀, x₁, …, x_kwithx_k=P_K(x). In addition, the error ‖x_j−P_K(x)‖ is monotone decreasing and has a definite upper bound easily to be determined. So the new algorithm is very applicable in practice.     

On the Asymptotics of Fekete-Type Points for Univariate Radial Basis Interpolation

Suppose that K ^d is compact and that we are given a function fC(K) together with distinct points x_iK, 1in. Radial basis interpolation consists of choosing a fixed (basis) function g : ⁺→ and looking for a linear combination of the translates g(|x−x_j|) which interpolates f at the given points. Specifically, we look for coefficients c_j such that has the property that F(x_i)=f(x_i), 1in. The Fekete-type points of this process are those for which the associated interpolation matrix [g(|x_i−x_j|)]_1i,jn has determinant as large as possible (in absolute value). In this work, we show that, in the univariate case, for a broad class of functions g, among all point sequences which are (strongly) asymptotically distributed according to a weight function, the equally spaced points give the asymptotically largest determinant. This gives strong evidence that the Fekete points themselves are indeed asymptotically equally spaced.     

A new approach to the dynamic maintenance of maximal points in a plane

A pointp _i=(x _i, y_i) in thex–y plane ismaximal if there is no pointp _j=(x _j, y_j) such thatx _j>x_i andy _j>y_i. We present a simple data structure, a dynamic contour search tree, which contains all the points in the plane and maintains an embedded linked list of maximal points so thatm maximal points are accessible inO(m) time. Our data structure dynamically maintains the set of points so that insertions takeO(logn) time, a speedup ofO(logn) over previous results, and deletions takeO((logn)²) time.The research of the first author was partially supported by the National Science Foundation under Grant No. DCR-8320214 and by the Office of Naval Research on Contract No. N 00014-86-K-0689. The research of the second author was partially supported by the Office of Naval Research on Contract No. N 00014-86-K-0689.     

On numerical improvement of Gauss–Legendre quadrature rules

Among all integration rules with n points, it is well-known that n-point Gauss–Legendre quadrature rule∫₋₁¹f(x) dx∑_i=1ⁿw_if(x_i)has the highest possible precision degree and is analytically exact for polynomials of degree at most 2n−1, where nodes x_i are zeros of Legendre polynomial P_n(x), and w_i's are corresponding weights.In this paper we are going to estimate numerical values of nodes x_i and weights w_i so that the absolute error of introduced quadrature rule is less than a preassigned tolerance ε₀, say ε₀=10⁻⁸, for monomial functionsf(x)=x^j, j=0,1,…,2n+1.(Two monomials more than precision degree of Gauss–Legendre quadrature rules.) We also consider some conditions under which the new rules act, numerically, more accurate than the corresponding Gauss–Legendre rules. Some examples are given to show the numerical superiority of presented rules.     

Lambda-determinants and domino-tilings

Consider the 2n-by-2n matrix with m_i,j=1 for i,j satisfying |2i−2n−1|+|2j−2n−1|2n and m_i,j=0 for all other i,j, consisting of a central diamond of 1's surrounded by 0's. When n4, the λ-determinant of the matrix M (as introduced by Robbins and Rumsey [Adv. Math. 62 (1986) 169–184]) is not well defined. However, if we replace the 0's by t's, we get a matrix whose λ-determinant is well defined and is a polynomial in λ and t. The limit of this polynomial as t→0 is a polynomial in λ whose value at λ=1 is the number of domino-tilings of a 2n-by-2n square.     

On the spectral norms of Cauchy–Toeplitz and Cauchy–Hankel matrices

In this study, we have found upper and lower bounds for the spectral norm of Cauchy–Toeplitz and Cauchy–Hankel matrices in the forms T_n=[1/(a+(i−j)b)]ⁿ_i,j=1, H_n=[1/(a+(i+j)b)]ⁿ_i,j=1.     

A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.