Search

This paper studies the complexity of the polynomial-time samplable ( P -samplable) distributions, which can be approximated within an exponentially small factor by sampling algorithms in time polynomial in the length of their outputs. The paper shows that common assumptions in complexity theory yield the separation of polynomial-time samplable distributions from the polynomial-time computable distributions with respect to polynomial domination, average-polynomial domination, polynomial equivalence, and average-polynomial equivalence.

This paper considers the possibility of tiling surfaces using dominoes. Orientable surfaces consisting of unit squares are studied. It presents more generalized discussions than the necessary and sufficient condition given for the multiply connected surfaces on the author's previous paper (Ito, 1996,J. Combin. Theory Ser. A75, No. 2, 173–186).

Let G be a two-connected graph. A family F of circuits of G is called a circuit double cover (CDC) if each edge of G is contained in exactly two circuits of F. In this paper, we show that if a simple cubic graph G (G ≠ K4) of order n has a CDC, then G has a CDC containing at most n/2 circuits. This result establishes the equivalence of the circuit double cover conjecture (due to Szekeres, Seymour) and the small circuit double cover conjecture (due to Bondy) for any cubic graph. Actually, a stronger result is obtained in this paper for all loopless cubic graphs. Another result in this paper establishes an upper bound on the size of any CDC of a cubic graph.

This is the first of three papers that aim to bring the known theory of projective modules over a hereditary Noetherian prime ring R up to roughly the same level as the well-known commutative case, where R is a Dedekind domain. This first paper lays the foundations by introducing the notion of an integral extension S of R in the Goldie quotient ring of R, and elucidating the relationship between integrality and the R-module structure of simple S-modules.

In this paper we continue the method of a previous paper and get various class number 2 criteria for real quadratic fields of the Richaud–Degert type. In the appendix, as an application of our method, we construct real quadratic fields of class number divisible by n , where n is any positive integer.

The topic of this paper concerns a certain relation between the jacobians of various quotients of the modular curve $X(p)$, which relates the jacobian of the quotient of $X(p)$ by the normaliser of a non-split Cartan subgroup of $GL_2(F_p)$ to the jacobians of more standard modular curves. In this paper, we confirm a conjecture of Merel found in a paper of Darmon-Merel, "Winding quotients and some variants of Fermat's Last Theorem", Crelle, v. 490, p. 81-100, 1997, which describes this relation in terms of explicit correspondences. The method used is to reduce the conjecture to showing a certain $Z[GL_2(F_p)]$-module homomorphism is an isomorphism. This is accomplished by using some peculiar relations between double coset operators to find a expression for the eigenvalues of this homomorphism in terms of Legendre character sums and Soto-Andrade sums. A ramification argument then shows that these eigenvalues are non-zero.

LetVbe a set of ordernand letFbe a set of orderq. A setS⊆{φ:V→F} of functions fromVtoFis an (n,q,t)-perfect hash familyif for allX⊆Vwith |X|=t, there existsφ∈Swhich is injective when restricted toX. Perfect hash families arise in compiler design, in circuit complexity theory and in cryptography. LetSbe an (n,q,t)-perfect hash family. The paper provides lower bounds on |S|, which better previously known lower bounds for many parameter sets. The paper exhibits new classes of perfect hash families which show that these lower bounds are realistic.

In this paper we study the existence and characterization of spaces which are images of minimal-norm projections that are required to interpolate at given functionals and satisfy additional shape-preserving requirements. We will call such spaces optimal interpolating spaces preserving shape. This investigation leads to concrete solutions in classical settings and, as examples, Πn will be determined to be such spaces with regard to certain interpolation and shape-preserving requirements on the projections. Restated, the theory of this paper gives rist to an n-dimensional Hahn–Banach extension theorem, where the minimal-norm extension is required to keep invariant a fixed cone.

The Gilbert–Pollak conjecture, posed in 1968, was the most important conjecture in the area of “Steiner trees.” The “Steiner minimal tree” (SMT) of a point setPis the shortest network of “wires” which will suffice to “electrically” interconnectP. The “minimum spanning tree” (MST) is the shortest such network when onlyintersite line segmentsare permitted. The generalized GP conjecture stated thatρd=infP⊂Rd(lSMT(P)/lMST(P)) was achieved whenPwas the vertices of a regulard-simplex. It was showed previously that the conjecture is true ford=2 and false for 3⩽d⩽9. We settle remaining cases completely in this paper. Indeed, we show that any point set achievingρdmust have cardinality growing at least exponentially withd. The real question now is: What are the true minimal-ρpoint sets? This paper introduces the “d-dimensional sausage” point sets, which may have a lit to do with the answer.

In this paper we present a Process Algebra for the specification of concurrent, communicating processes which incorporates operators for the refinement of actions by processes, in addition to the usual operators for communication, nondeterminism, internal actions, and restrictions, and study a suitable notion of semantic equivalence for it. We argue that action refinements should not, in some formal sense, interfere with the internal evolution of processes and their application to processes should consider the restriction operator as a "binder." We show that, under the above assumptions, the weak version of the refine equivalence introduced by Aceto and Hennessy ((1993) Inform. and Comput.103, 204-269) is preserved by action refinements and, moreover, is the largest such equivalence relation contained in weak bismulation equivalence. We also discuss an example showing that, contrary to what happens in Aceto and Hennessy ((1993) Inform. and Comput.103, 204-269), refine equivalence and timed equivalence are different notions of equivalence over the language considered in this paper.

In this paper we study the Steiner tree problem in graphs for the case when vertices as well as edges have weights associated with them. A greedy approximation algorithm based on “spider decompositions” was developed by Klein and Ravi for this problem. This algorithm provides a worst case approximation ratio of 2lnk, wherekis the number of terminals. However, the best known lower bound on the approximation ratio is (1−o(1))lnk, assuming thatNP⊈DTIME[nO(loglogn)], by a reduction from set cover. We show that for the unweighted case we can obtain an approximation factor of lnk. For the weighted case we develop a new decomposition theorem and generalize the notion of “spiders” to “branch-spiders” that are used to design a new algorithm with a worst case approximation factor of 1.5lnk. We then generalize the method to yield an approximation factor of (1.35+ε)lnk, for any constantε>0. These algorithms, although polynomial, are not very practical due to their high running time, since we need to repeatedly find many minimum weight matchings in each iteration. We also develop a simple greedy algorithm that is practical and has a worst case approximation factor of 1.6103lnk. The techniques developed for this algorithm imply a method of approximating node weighted network design problems defined by 0–1 proper functions as well. These new ideas also lead to improved approximation guarantees for the problem of finding a minimum node weighted connected dominating set. The previous best approximation guarantee for this problem was 3lnnby Guha and Khuller. By a direct application of the methods developed in this paper we are able to develop an algorithm with an approximation factor of (1.35+ε)lnnfor any fixedε>0.

Let G be a finite group and let k be a field. We say that a kG-module V has a quadratic geometry or is of quadratic type if there exists a non-degenerate (equivalently non-singular) G-invariant quadratic form on V. If V is irreducible or projective indecomposable and k of odd characteristic, the existence of a quadratic geometry can be read off from invariants of representation theory. In terms of the group algebra the existence of such a geometry is characterized by the existence of an idempotent e which corresponds to V and is invariant under the antiautomorphism on kG given by g → ĝ = g−1 for g ∈ G. In characteristic two the problem is more delicate. For an irreducible module the existence of a quadratic geometry is partly a question in cohomology. Unfortunately, a satisfactory answer does not seem to be known. However, if V is projective, liftability of the module to characteristic zero may help to find the geometry more easily. This is the subject of the paper. The notation which we shall use throughout the paper is standard and may be taken from Huppert and Blackburn ("Finite Groups II," Springer-Verlag, Berlin, 1982) and Isaacs ("Character Theory of Finite Groups," Academic Press, New York, 1976).

This paper shows that a simple graph which can be cellularly embedded on some closed surface in such a way that the size of each face does not exceed 7 is upper embeddable. This settles one of two conjectures posed by Nedela and Škoviera (1990, in “Topics in Combinatorics and Graph Theory,” pp. 519–529, Physica Verlag, Heidelberg). The other conjecture will be proved in a sequel to this paper.

For locally compact groups, Fourier algebras and Fourier–Stieltjes algebras have proven to be useful dual objects. They encode the representation theory of the group via the positive definite functions on the group: positive definite functions correspond to cyclic representations and span these algebras as linear spaces. They encode information about the algebra of the group in the geometry of the Banach space structure, and the group appears as a topological subspace of the maximal ideal space of the algebra. Because groupoids and their representations appear in studying operator algebras, ergodic theory, geometry, and the representation theory of groups, it would be useful to have a duality theory for them. This paper gives a first step toward extending the theory of Fourier–Stieltjes algebras from groups to groupoids. IfGis a locally compact (second countable) groupoid, we show that B(G), the linear span of the Borel positive definite functions onG, is a Banach algebra when represented as an algebra of completely bounded maps on aC*-algebra associated withG. This necessarily involves identifying equivalent elements of B(G). An example shows that the linear span of the continuous positive definite functions need not be complete. For groups, B(G) is isometric to the Banach space dual ofC*(G). For groupoids, the best analog of that fact is to be found in a representation of B(G) as a Banach space of completely bounded maps from aC*-algebra associated withGto aC*-algebra associated with the equivalence relation induced byG. This paper adds weight to the clues in earlier work of M. E. Walter on Fourier–Stieltjes algebras that there is a much more general kind of duality for Banach algebras waiting to be explored.

Certain sign equivalence classes of n-dimensional nonlinear dynamical systems correspond to n-vertex hypergraphs, The global stability of some such dynamical systems can be guaranteed if the associated hypergraphs have a simplicity of structure and meet certain quantitative path product conditions. A purely algebraic version of the same problem can be described as follows. Suppose we are given a rectangular matrix pattern of signs; each entry in the matrix is +, −, or 0. For every real matrix κ of the same sign pattern, is there a real vector λ, each component of which is positive, such that κ · λ = 0? This paper presents graph theoretic sufficient conditions on a hypergraph generated from the sign pattern of κ which guarantee the existence of λ. For κ with more highly connected hypergraphs, this paper also presents sufficient qualitative conditions on the sign pattern of κ and certain quantitative conditions on sums of hypergraph path products which together guarantee the existence of λ.

In this paper we give a detailed description of the fixed point subgroups of certain Kac-Moody groups under particular automorphisms. We consider Kac-Moody groups arising from simply laced extended Cartan matrices and their fixed point subgroups under automorphisms which contain a non-trivial field automorphism constituent as well as a non-trivial graph automorphism constituent. We show that such a situation satisfies all the conditions of a theorem of J-Y. Hee ["Torsion de groupes munis d′une donnee radicelle, Theoreme (4.5)"] which concludes that the fixed point subgroup has a (B, N)-pair and a system of root subgroups. This paper contains some of the results in the author′s doctoral thesis ["On Some Twisted Kac-Moody Groups"].

The goal of this paper is to examine the relationship between a domain R and its subring of invariants R L , under the action of a finite-dimensional restricted Lie algebra L . We first show that there exists a nondegenerate ( R L , R L )-bimodule "trace-like" map g : R → R L and therefore I ∩ R L ≠ 0, for every ideal I ≠ 0 of R . Next, we show that there exists a right R L -module embedding φ of R into a finite direct sum of copies of R L . Using the maps g and φ, we obtain the following, which is a combination of several of the main results of this paper.

Let G = ( VG , EG ) be a bipartite planar graph embedded in the euclidean plane and H be a subset of its faces ( holes ). A. Schrijver proved that if | H | = 2 then there exists a collection C = { m 1 , ..., m k } of cut metrics on VG such that: (i) m 1 ( e )+ ··· + m k ( e ) ≤ 1 for any e ∈ EG ; and (ii) for any vertices s and t in the boundary of a hole, the value m 1 ( s , t )+ ··· + m k ( s , t ) is equal to the distance between s and t. This is, in general, not true for | H | = 3. In the present paper one proves that: (*) for | H | = 3, (i)-(ii) hold for some C consisting of cut metrics and 2, 3-metrics (metrics induced by the graph K 2, 3 ); and (**) for | H | =4, (i)-(ii) hold for some C consisting of metrics induced by planar graphs with at most four faces. Using (*), in the sequel to the present paper (Part II) we give a criterion of the existence of edge-disjoint paths connecting certain vertices in a planar graph with three holes, provided that the so-called "parity condition" holds. This extends, in a sense, Okamura′s theorem on edge-disjoint paths in planar graphs with two holes.

This paper concerns the maximum genus orientable surface upon which a given graph cellularly embeds. Classical theorems of Xuong and Nebeský give exact values for the maximum genus. The former is suited to constructing embeddings while the latter is suited to forbidding embeddings of larger genus. However, using either theorem alone requires an exhaustive search to establish the exact value. Herein we examine relative embeddings of graphs, where certain facial cycles and their orientations have been prescribed. The relative graph analogue of Xuong's theorem is known. In this paper we establish the relative graph analogue of Nebeský's theorem.

In this paper a q-analogue of the Coxeter complex of a finite Coxeter group W is constructed for the (generic) Hecke algebra H associated to W. It is shown that the homology of this chain complex, together with that of its truncations, vanishes away from top dimension. The remainder of the paper investigates the representations of H afforded by the top homology modules of these complexes. In particular necessary and sufficient conditions are given for a specialisation of the Hecke algebra to decompose into a direct sum of its "truncation" representations.

For arbitrary Banach spaces Butzer and Scherer in 1968 showed that the approximation order of best approximation can characterized by the order of certain K-functionals. This general theorem has many applications such as the characterization of the best approximation of algebraic polynomials by moduli of smoothness involving the Legendre, Chebyshev, or more general the Jacobi transform. In this paper we introduce a family of seminorms on the underlying approximation space which leads to a generalization of the Butzer–Scherer theorems. Now the characterization of the weighted best algebraic approximation in terms of the so-called main part modulus of Ditzian and Totik is included in our frame as another particular application. The goal of the paper is to show that for the characterization of the orders of best approximation, simultaneous approximation (in different spaces), reduction theorems, and K-functionals one has (essentially) only to verify three types of inequalities, namely inequalities of Jackson-, Bernstein-type and an equivalence condition which guarantees the equivalence of the seminorm and the underlying norm on certain subspaces. All the results are given in weak-type estimates for almost arbitrary approximation orders, the proofs use only functional analytic methods.

In this paper we investigate the irreducibility of certain modules for the Lie-algebra of diffeomorphisms of torus T . The Lie-algebra of diffeomorw "1 "1 x Ž phisms can be described as the derivations of A s C t , . . . t see 1 d w x. w x RSS . We denote this Lie-algebra by Der A. Larsson L1 constructed a functor from gl -modules to Der A modules. In this paper we prove that d the image of a finite-dimensional irreducible gl module is most often d irreducible. The only exceptions are fundamental modules and the onedimensional modules. In these cases we describe the sub-modules and the Ž quotients. Surprisingly the same class of modules image of finite dimen. w x sional gl -module are also constructed in E without any reference to d gl -modules. They are motivated by the vertex operator constructions in d w x Ž . EM more details near the end of this introduction . We will now describe our results in more detail. Let gl be the d Lie-algebras of d = d matrices over complex numbers C. Let gl s sl [ d d C Id where sl is the finite-dimensional simple Lie-algebra of trace zero d matrices and Id, the identity matrix which is central. It is well known that finite dimensional irreducible modules and dominant integral weights are in one]one correspondence for a finite dimensional simple Lie-algebra. So Ž . let V c be finite dimensional irreducible sl module corresponding to a d dominant integral weight c . Let Id, the central element, act by a complex Ž . number b and denote the corresponding gl module by V c , b . d Ž . a Ž d d. Larsson defined see 1.6 a functor F for a belonging to C rZ from w x gl modules to Der A modules in L1 . These modules are weight modules d

In this paper we prove two main results. The first one is the existence of a right self-injective regular ring of type III with center any given commutative self-injective regular ring. The second one is a characterization of the lattice of two-sided ideals for a large class of right self-injective regular rings of type III. In a previous paper, this lattice was described as the lattice of order ideals of a certain lattice of continuous functions. Now we prove the converse: for a large class of complete boolean spaces X, let C be the set of all continuous functions from X into {0} ∪ [ℵ0, γ], where γ is any infinite cardinal number, and let Δ be the lattice of all functions of C that are less than or equal to a given nonvanishing function of C. Then there exists a right self-injective regular ring R of type III such that the lattice of two-sided ideals of R is isomorphic to the lattice of order ideals of Δ.

The purpose of this paper is to revise the definitions of Ishikawa and Mann iterative processes with errors, by using a new inequality to study the unique solution of the nonlinear strongly accretive operator equationTx = fand the convergence problem of Ishikawa and Mann iterative sequences for strongly pseudo-contractive mappings without the Lipschitz condition. The results presented in this paper improve and extend the corresponding results in [ 4 , 5 , 7 – 10 , 12 , 15 , 16 ] in the more general setting. In particular, the open problem mentioned by Chidume in [ 5 ] has been given an affirmative answer.

In [6], G. Taddei has studied normality of the elementary subgroups of Chevalley groups over commutative rings. In this paper, applying the same method as used in his paper, we study normality of the elementary subgroups of twisted Chevalley groups over commutative rings. The main theorem is stated in Section 1. In Section 2, we deal with some subgroups over quotient rings. Under a key proposition which is proved in Section 4, we prove the main theorem in Section 3. We shall freely use the definitions, the notations, and the relations between elements of twisted Chevalley groups over commutative rings given in E. Abe [2].

A nonidentity element of a permutation group is said to be semiregular if all of its orbits have the same length. The work in this paper is linked to [6] where the problem of existence of semiregular automorphisms in vertex-transitive digraphs was posed. It was observed there that every vertex-transitive digraph of orderpkormp, wherepis a prime,k≥1 andm≤pare positive integers, has a semiregular automorphism. On the other hand, there are transitive permutation groups without semiregular elements [4]. In this paper, it is proved that every cubic vertex-transitive graph contains a semiregular automorphism, and moreover, it is shown that every vertex-transitive digraph of order 2p2, wherepis a prime, contains a semiregular automorphism.

This paper deals with the general nonlinear congruential method for generating uniform pseudorandom numbers, in which permutation polynomials over finite prime fields play an important role. It is known that these pseudorandom numbers exhibit an attractive equidistribution and statistical independence behavior. In the context of parallelized simulation methods, a large number of parallel streams of pseudorandom numbers with strong mutual statistical independence properties are required. In the present paper, such properties of parallelized nonlinear congruential generators are studied based on the discrepancy of certain point sets. Upper and lower bounds for the discrepancy both over the full period and over (sufficiently large) parts of the period are established. The method of proof rests on the classical Weil bound for exponential sums.

Matrices M ( n ), one for each positive integer n , arise in the theory of Birkhoff-Lewis equations for chromatic polynomials. Students of those equations think it would be helpful to have a formula for the determinant of M ( n ). Finding that determinant is the main object of this paper. It has been conjectured that the determinant is a product of a power of the colour-variable λ and powers of certain polynomials in λ, those called "Beraha polynomials" by combinatorialists. That would explain the observed occurrences of Beraha polynomials in the solutions of the Birkhoff-Lewis equations for small values of n . The formula obtained in this paper verifies the conjecture. This paper is closely connected with work done by R.Dahab, D. H. Younger, and the present author on partial solutions of the Birkhoff- Lewis equations. The first two computed det M ( n ) up to n = 6, and so made the above-mentioned conjecture seem plausible.

Over a commutative Noetherian ring R, the Bass invariants μi(p, M) were defined for any module M and any prime p ∈ Spec R by H. Bass (Math. Z. 82, 1963, 8-28). In the first part of this paper, we study these numbers further. We are concerned primarily with the modules having a certain vanishing property of their Bass numbers. For instance, we show that R is Gorenstein if and only if μi(p, F) = 0 whenever ht(p) ≠ i for any nat module F. In the second part, we define the invariants πi(p, M) for any prime p ∈ Spec R and module M by a minimal flat resolution of M. As with the Bass invariants, we can characterize Gorenstein rings and modules by a vanishing property of these numbers. For instance, injective modules are just those modules M having πi(p, M)= 0 for all prime p with ht(p) ≠ i and all i ≥ 0. Finally, we introduce strongly cotorsion modules and show that these modules M are just those modules having πi(p, M) = 0 for all prime p with ht(p) > i and all i ≥ 0. From this paper we will see that nat covers defined by E. Enochs (Israel J. Math.39, 1981, 189-209) behave in a manner dual to the behavior of injective envelopes.

The aim of this paper is, in the notation of Kac, to extend results about Kac-Moody algebras to corresponding groups by proving that certain affine Kac-Moody groups of types II and III arise as the fixed point subgroups of affine Kac-Moody groups of type I of higher rank under particular automorphisms. We prove an analogue of a theorem of Hee which enables us to deduce some results about the fixed point subgroups of Kac-Moody groups arising from simply-laced extended Cartan matrices under automorphisms which are the product of a graph and a diagonal automorphism. We then prove that the groups obtained in this way are in fact isomorphic to Kac-Moody groups arising from affine Cartan matrices which are not of extended type. This paper contains the main results in the author′s doctoral thesis.

In 1985, Martel published a linear time algorithm with a 43 asymptotic worst-case ratio for the one-dimensional bin packing problem. The algorithm is based on a linear time classification of the sizes of the items, and thereafter—according to the number of elements in certain subclasses—pairing the items in a clever way. In his paper Martel mentioned a natural generalization of this algorithm, that suggested a 54 algorithm. Although this seemed to be very simple, the improvement has not been realized until now. In this paper we present an algorithm which uses the ideas of Martel and has a 54 asymptotic worst-case ratio.

Consider the linear delay difference equation xn+1 − xn = anxnk, where an′s are real numbers and k is a positive integer. In this paper we establish asymptotic formulae for the solutions of the above equation assuming Σ∞n=0 |an|p < ∞ for some p ≥ 1. The asymptotic formulae are given by an appropriate recursive sequence. For p ∈ {1, 2, 3, 4} we present explicit formulae. We also construct an example which shows that some comparison results in a recent paper of Yan and Qian are incorrect.

The aim of this paper is to give a criterion for a 2 × 2 matrix order Λ over a discrete valuation ring to be (lattice) tame. Here "tame" means, as in previous papers by the first author, that indecomposable Λ-lattices of any fixed rank form at most 1-parameter families. It is also shown that otherwise Λ is (lattice) wild, i.e., the classification of Λ-lattices contains in some sense that of the representations of any finite generated algebra over the residue field (see Section 1 for precise definitions). Namely, Theorem 1 asserts that there exists a unique order Λ1 such that the wild orders are just those conjugate to ist suborders (including Λ1 itself) and all other orders are tame. Furthermore, in Proposition 2 this result is reformulated in terms of some standard basis of Λ.

In a previous paper [ J. Number Theory , 39 (1991), 50-64], we obtained a basic relationship between Gauss sums and Jacobi sums for a ring of residues modulo a prime power, and determined the absolute value of the Jacobi sums. This paper generalizes those results to finite commutative rings with identity.

Convergence theory is a primary topic in topology. In fact, topology and so-called convergence class are characterized by each other. In fuzzy topology ( L -fuzzy topology), more than 40 papers published in the last ten years were concerned with convergence theory. Among these papers, the problem of convergence class was solved for the case of L = [0, 1] [ 7 ]. Since the neighbor structure, so called “quasi-coincident neighborhood system,” of an L -fuzzy point in an L -fuzzy topological space is in general not directed under the inclusion order, the conditions of convergence class in [0, 1]-fuzzy topology will not be valid any longer in the case of lattice. Moreover, quite different from the cases of {0, 1}-fuzzy topology (i.e., ordinary topology) and [0, 1]-fuzzy topology, the so called Bolzano–Weierstrass property does not hold, i.e., a net with a cluster point in an L -fuzzy topological space is not still necessary to have a subnet converging to the point. In this paper, a necessary and sufficient condition for the Bolzano–Weierstrass property is produced, the result is also used in a satisfactory theory of convergence classes in L -fuzzy topological spaces, and the associated characterization theorem between L -fuzzy topologies and convergence classes is established.

In a recent paper, A. Bialostocki (Israel J. Math.41 (1982), 261-273) has defined a nilpotent injector in an arbitrary finite group G to be a maximal nilpotent subgroup of G, containing a subgroup H of G of maximal order satisfying class (H) ≤2. In the present paper, the author determines the nilpotent injectors of GL(n, q) and shows that they form a unique conjugacy class of subgroups of GL(n, q). It is also proved that if n ≠ 2 or n = 2 and q ≠ 9 is not a Fermat prime >3, then the nilpotent injectors of GL(n, q) are the nilpotent subgroups of maximal order.

Throughout this paper R will denote a valuation domain. P. Eklof and w x L. Fuchs 3 showed that an R-module M is free if and only M is a Baer 1 Ž . module, that is, Ext M, T s 0 for all torsion R-modules T. What can we R 1 Ž . say about R-modules M for which Bext M, T s 0 for all torsion modR ules T ? Here Bext is a subfunctor of Ext consisting of balanced R R extensions. Torsion-free R-modules M with the last property are called Butler modules. Is a Butler R-module M completely decomposable? L. w x Fuchs and E. Monari-Martinez 7 answered this in the affirmative when rank M F / . This paper attempts to investigate this question using the 1 w x recent work 11 on modules with balanced-projective dimension one. Ž . It is known that every torsion-free R-module M possesses a G / 9-family 0 Ž . C of pure submodules, namely, C satisfies the following conditions: 1 0, Ž . Ž . M g C , 2 C is closed under unions of chains, and 3 for any A g C and any countable subset X of M, there is a B g C such that A j X ; B and BrA has countable rank. For instance, we can take C to consist of all the Ž . pure submodules of M. If the condition 2 above is replaced by the Ž . condition 2 9 S N g C if N g C for each i g I, then we call C an ig I i i axiom-39 family. These are modifications of the original definition of an Ž w x. axiom-3 family by Paul Hill see, e.g., 1 and have also occurred with w x other variations under the name tight systems in 8 . Ž . Our main theorem Theorem 4.6 asserts that a Butler R-module B will be completely decomposable if and only if B has an axiom-39 family of pure submodules. We first show that the above condition on B is equiva

In this paper we discuss several computations with elements of algebraic number fields F which either require numerical calculations or are at least speeded up considerably by their use. Since the results can be uniquely represented by (sequences of) rational integers, those numerical calculations should clearly be performed by validated methods. Hence, the intention of this paper is to point out important number theoretical problems which can be adequately solved only by the use of symbolic and validated computations.

In this paper, we generalize Hilbert's integral inequality and its equivalent form by introducing three parameterst,a, andb. Iff, g ∈ L2[0, ∞), then[formula]where π is the best value. The inequality (1) is well known as Hilbert's integral inequality, and its equivalent form is[formula]where π2is also the best value (cf. [ 1 , Chap. 9]). Recently, Hu Ke made the following improvement of (1) by introducing a real functionc(x),[formula]wherek(x) = 2/π∫∞0(c(t2x)/(1 + t2)) dt − c(x), 1 − c(x) + c(y) ≥ 0, andf, g ≥ 0 (cf. [ 2 ]). In this paper, some generalizations of (1) and (2) are given in the following theorems, which are other than those in [ 2 ].

LetAbe a set of non-negative integers. In our previous paper forh∈ Z ,h⩾2 we estimated from below the cardinality ofhAand this allowed us to obtain sharp estimates for suchG, that every integerg⩾Gmay be represented by a sum of elements ofA(the linear diophantine problem of Frobenius). However, “not only the number of elements ofhAis important, but also the way they are situated” (G. Freiman). In this paper we show thathAalways contains long continuous chains of integers and derive an estimation for the number of summands required for representation ofgof the above mentioned type.

Let $\scr H$ denote a Hilbert space consisting of functions analytic on a bounded, open, connected subset $\Omega$ of the complex plane. Given certain natural hypotheses on $\scr H$, the author characterizes the finite-codimensional subspaces of $\scr H$ that are invariant under multiplication by $z$, showing that all such subspaces have the form $(p\scr H)^-$, where $p$ is a polynomial whose zeros lie in the closure of $\Omega$ (a more precise description of $p$ is given in the paper). In addition to standard hypotheses on $\scr H$ (such as continuity of point evaluations for points in $\Omega$), the author requires that $M_z$ be subnormal and that the collection of multipliers of $\scr H$ contain all functions analytic on $\Omega$ and continuous on its closure. The final section of the paper contains a characterization of the Fredholm multiplication operators on $\scr H$, which is derived as a consequence of the author's description of finite-codimensional invariant subspaces. The results in the paper are generalizations of those obtained in the Bergman-space setting by the author [Trans. Amer. Math. Soc. 330 (1992), no. 2, 531--544; MR1028755 (92f:47025)], by S. Axler [J. Reine Angew. Math. 336 (1982), 26--44; MR0671320 (84b:30052)], and by Axler and the reviewer [Trans. Amer. Math. Soc. 306 (1988), no. 2, 805--817; MR0933319 (89f:46051)]. Hilbert spaces of analytic functions where multiplication by z is a subnormal operator with a rich commutant are considered. We determine the invariant subspaces with finite codimension and the Fredholm operators in the commutant. (Less)

Recall that a finite group is called perfect if it does not have non-trivial 1-dimensional representations (over the field of complex numbers C). By analogy, let us say that a finite dimensional Hopf algebra H over C is perfect if any 1-dimensional H-module is trivial. Let us say that H is biperfect if both H and H^* are perfect. Note that, H is biperfect if and only if its quantum double D(H) is biperfect. It is not easy to construct a biperfect Hopf algebra of dimension >1. The goal of this note is to describe the simplest such example we know. The biperfect Hopf algebra H we construct is based on the Mathiew group of degree 24, and it is semisimple. Therefore, it yields a negative answer to Question 7.5 from a previous paper of the first two authors (math.QA/9905168). Namely, it shows that Corollary 7.4 from this paper stating that a triangular semisimple Hopf algebra over C has a non-trivial group-like element, fails in the quasitriangular case. The counterexample is the quantum double D(H)., 5 pages, latex

The aim of this paper is to show that a finitely generated module over a Noetherian ring defines a unique cycle class in the components with codimension zero and one of the Chow group of the ring. The main theorem generalizes a classical result over integrally closed domains and implies the isomorphism between the Chow group and the Grothendieck group under certain conditions. We also discuss the difference between the map constructed in this paper and the Riemann–Roch map.

In two recent papers, "A Simpler Proof of a Theorem of Steinmetz" (1989, J. Math. Anal. Appl. 143 , 290-294) and "An Extension of a Theorem of Steinmetz" (1991, J. Math. Anal. Appl. 156 , 287-292), the present authors gave a new proof of Steinmetz′s theorem that avoided use of the Second Fundamental Theorem of Nevanlinna. It was also shown in the second paper how to generalize Steinmetz′s theorem to handle the case where the inner function is not precisely the same in all cases. In this paper we shall extend these results even further.

This paper presents a theorem on the growth rate of the orbit-counting sequences of a primitive oligomorphic group: if G is not a highly homogeneous group, then the growth rate for the sequence counting orbits onn -tuples of distinct elements is bounded below by cnn!, wherec≈ 1.172. The previously known lower bounds concerned all not highly transitive groups, including highly homogeneous groups which are known to have roughly factorial growth rate. This paper shows that highly homogeneous groups are the only groups with such a growth rate, while for all other primitive groups the growth rate is faster and the bound is improved by an exponential factor.

In this paper we study the two-sided ideals of the enveloping algebraU = U(sl2(K)) over an arbitrary fieldKof characteristic zero. Starting with two basic ideas, that an irreducible Lie module is generated by its highest weight vector and that the Lie module structure ofUcomes from its ring multiplication, we have found a “good” subset ofUconsisting of highest weight vectors for irreducibleU-submodules ofUso that each two-sided ideal ofUis uniquely generated by at most two elements of that set. Actually, each ideal is generated as a two-sided ideal by just one element. By uniqueness, all the information about the ideal is encoded in the formula for its generator(s). For example, we can list and classify all the prime ideals by height, determine the intersection of an ideal with the center, find the radical ideals and the radical of an ideal, and determine when two ideals are included one in another. An interesting property is that each ideal ofUcan be uniquely written as a product of primes. We also obtain the “least common multiple” and the “greatest common divisor” formulas for the prime ideal factorizations of the intersection and the sum of two ideals. This paper contains many other results of this nature.

In this paper, Hermite interpolation by bivariate algebraic polynomials of total degree ⩽nis considered. The interpolation parameters are the values of a function and its partial derivatives up to some ordernν−1 at the nodeszν=(xν, yν),ν=1, …, s, wherenνis the multiplicity ofzν. The sequence N={n1, …, ns; n} of multiplicities associated with the degree of interpolating polynomials is investigated. Some results of the paper were announced in [GHS93].

The paper investigates the construction of biorthogonal wavelet bases on R d . Assume that M (ξ)[formula](ξ) = I for all ξ ∈ T d , where M (ξ) = ( m μ (ξ + νπ)) μ,ν∈ E , M (ξ) = ( m μ (ξ + νπ )) μ,ν∈ E with all m μ (ξ) and m μ (ξ) (μ ∈ E ) being in the Wiener class W ( T d ). Let φ and φ be the associated scaling functions, {ψ μ } and {ψ μ }(μ ∈ E - {0}) be the associated wavelet functions. Under weaker conditions and with simpler proofs, this paper obtains the following results: (1)and (2) are equivalent; (2) implies (3) always, and (3) implies (2) under some additional mild conditions; (5) implies (3); (1) implies (4); and in the case when m 0 (ξ) and m 0 (ξ) are trigonometric polynomials, (4) implies (1) and (5). These five assertions are: (1) Φ(ξ) ≍ 1 ≍ Φ(ξ)(Φ(ξ) = ∑ α |φ(ξ + 2απ)| 2 ); (2) 〈φ, φ(· - k )〉 = δ 0, k ; (3) 〈ψ μ, j , k ,ψ μ′, j ′, k ′ 〉 = δ μμ′ δ jj ′ δ kk ′ ; (4) |λ| max max P 0 ); (5) {ψ μ, j , k ,ψ μ, j , k } is a dual Riesz basis of L 2 ( R d ).

We consider the class of finite-state systems communicating through unbounded butlossyFIFO channels (calledlossy channel systems). These systems have infinite state spaces due to the unboundedness of the channels. In an earlier paper, we showed that the problems of checking reachability, safety properties, and eventuality properties are decidable for lossy channel systems. In this paper, we show that the following problems are undecidable:•The model checking problem in propositional temporal logics such as propositional linear time temporal logic (PTL) and computation tree logic (CTL).•The problem of deciding eventuality properties with fair channels: do all computations eventually reach a given set of states if the unreliable channels satisfy fairness assumptions ?The results are obtained through reduction from a variant of the Post correspondence problem.

The largely singular operators that are defined in this paper are a sharp contrast to invertible operators or Fredholm operators. Nevertheless, we discover that the set has a surprising amount of nice structure. Without assuming that the underlying Hilbert space is separable, we are able to compute the distance from an arbitrary operator to the set. The distance formula involves the modulus of invertibility, which was introduced in an earlier paper.