Non–commutative Computer Algebra for polynomial algebras: Gr¨obner bases, applications and implementation Viktor Levandovskyy Vom Fachbereich Mathematik der Universit¨at Kaiserslautern zur Verleihung des akademischen Grades Doktor der Naturwissenschaften (Doctor rerum naturalium, Dr. rer. nat) genehmigte Dissertation 1. Gutachter: Prof. Dr. G.-M. Greuel 2. Gutachter: Prof. Dr. Yu. Drozd Vollzug der Promotion: 08.06.2005 D 386 iii Viktor Levandovskyy. ”Non-commutative Computer Algebra for polynomial algebras: Gr¨obner bases, applications and implementation”. Abstract. Non-commutative polynomial algebras appear in a wide rangeofapplications, fromquantumgroupsandtheoreticalphysicstolinear differential and difference equations. In the thesis, we have developed a framework, unifying many impor- tant algebras in the classes of G– and GR–algebras and studied their ring– theoretic properties. Let A be a G–algebra in n variables. We establish necessary and sufficient conditions for A to have a Poincar´e–Birkhoff–Witt (PBW) basis. Further on, we show that besides the existence of a PBW ba- sis, A shares some other properties with the commutative polynomial ring K[x ,...,x ]. In particular, A is a Noetherian integral domain of Gel’fand– 1 n Kirillov dimension n. Both Krull and global homological dimension of A are bounded by n; we provide examples of G–algebras where these inequalities are strict. Finally, we prove that A is Auslander–regular and a Cohen– Macaulay algebra. In order to perform symbolic computations with modules over GR– algebras, we generalize Gr¨obner bases theory, develop and respectively en- hance new and existing algorithms. We unite the most fundamental algo- rithms in a suite of applications, called ”Gr¨obner basics” in the literature. Furthermore, we discuss algorithms appearing in the non-commutative case only, among others two–sided Gr¨obner bases for bimodules, annihilators of left modules and operations with opposite algebras. An important role in Representation Theory is played by various sub- algebras, like the center and the Gel’fand–Zetlin subalgebra. We discuss their properties and their relations to Gr¨obner bases, and briefly comment some aspects of their computation. We proceed with these subalgebras in the chapter devoted to the algorithmic study of morphisms between GR– algebras. We provide new results and algorithms for computing the preim- age of a left ideal under a morphism of GR–algebras and show both merits and limitations of several methods that we propose. We use this technique for the computation of the kernel of a morphism, decomposition of a mod- ule into central characters and algebraic dependence of pairwise commuting elements. We give an algorithm for computing the set of one–dimensional representations of a G–algebra A, and prove, moreover, that if the set of finite dimensional representations of A over a ground field K is not empty, then the homological dimension of A equals n. iv All the algorithms are implemented in a kernel extension Plural of the computer algebra system Singular. We discuss the efficiency of com- putations and provide a comparison with other computer algebra systems. We propose a collection of benchmarks for testing the performance of al- gorithms; the comparison of timings shows that our implementation out- performs all of the modern systems with the combination of both broad functionality and fast implementation. In the thesis, there are many new non-trivial examples, and also the solutions to various problems, arising in different fields of mathematics. All of them were obtained with the developed theory and the implementation in Plural, most of them are treated computationally in this thesis for the first time. Viktor Levandovskyy. ”Nichtkommutative Computeralgebra fu¨r Polynomalgebren: Gr¨obnerbasen, Anwendungen und Implementierung”. Zusammenfassung. Nichtkommutative Polynomalgebren entstehen in vielen verschiedenen Anwendungen, von Quantengruppen und Theoretis- cher Physik bis zu linearen Differentiellen und Differenzengleichungen. In der Arbeit wurde ein Rahmen entwickelt, in dem viele wichtige Alge- bren der Klassen G– und GR–Algebren zusammengefu¨hrt und ihre ringth- eoretischen Eigenschaften untersucht wurden. Sei A eine G–Algebra mit n Variablen. Es werden notwendige und hinreichende Bedingungen dafu¨r angegeben, daß A eine Poincar´e–Birkhoff–Witt (PBW) Basis besitzt. Es wird gezeigt, dass A neben der Existenz einer PBW Basis, weitere Eigen- schaften mit dem kommutativen Polynomring K[x ,...,x ] gemeinsam hat. 1 n A ist ein Noetherscher Integrit¨atsbereich der Gel’fand–Kirillov–Dimension n. Die Krull– und die globale homologische Dimension von A sind durch n beschr¨ankt ; es werden Beispiele von G–Algebren gegeben, bei denen diese Ungleichheiten strikt sind. Schließlich wurde bewiesen, dass A eine Auslander–regul¨are und eine Cohen–Macaulay Algebra ist. Fu¨r symbolische Berechnungen mit Moduln u¨ber GR–Algebren, wurde die Gr¨obnerbasentheorie verallgemeinert, neue und bestehende Algorith- men werden entwickelt und verbessert. Wir verbinden die grundlegendsten Algorithmen mit einer Reihe von Anwendungen, welche man in der Lit- eratur als ”Gr¨obner basics” bezeichnet. Weiterhin wurden Algorithmen v diskutiert, die nur im nichtkommutativen Fall existieren, darunter zwei- seitige Gr¨obnerbasen fu¨r Bimoduln, Annihilatoren von Linksmoduln und Operationen mit entgegengesetzten Algebren. Eine wichtige Rolle in der Darstellungstheorie spielen die verschiedenen Unteralgebren, wie z.B. das Zentrum und die Gel’fand–Zetlin Unteralgebra. Die Eigenschaften und ihre Beziehungen zu Gr¨obnerbasen wurden untersucht und einige Aspekte ihrer Berechnung diskutiert. Im Kapitel u¨ber algorithmische Studien von Morphismen zwischen GR–Algebren wurde die Untersuchung zu diesen Un- teralgebren fortgesetzt. Es wurden neue Ergebnisse and Algorithmen zur BerechnungdesUrbildseinesLinksidealsuntereinemMorphismusvonGR– Algebren erzielt. Die Ergebnisse und Begrenzungen verschiedener Meth- oden, die vorgeschlagen wurden, wurden gezeigt. Diese Technik wurde auch fu¨r die Berechnung des Kerns eines Morphismus, die Zerlegung eines Moduls in zentrale Charaktere und die algebraische Abh¨angigkeit von paar- weise kommutierenden Elementen verwendet. Es wurde ein Algorithmus fu¨r die Berechnung von eindimensionalen Darstellungen einer G–Algebra A erstellt. Es wurde bewiesen, dass die homologische Dimension von A u¨ber einem K¨orper K gleich der Anzahl der Variablen von A ist, falls es endlich–dimensionale Darstellungen von A existieren. Alle Algorithmen wurden in eine Kern-Erweiterung Plural des Com- puteralgebrasystem Singular implementiert. Die Effizienz der Berechnun- gen wurde diskutiert und ein Vergleich mit anderen Computeralgebrasys- temen erstellt. Es wurde eine Reihe von Benchmarks zum Test der Leis- tung von Algorithmen vorgeschlagen. Der Zeitvergleich zeigt, dass unsere Implementierung alle modernen Systeme hinsichtlich der Kombination von Funktionalit¨at und Geschwindigkeit u¨bertrifft. In der Arbeit gibt es eine Vielzahl von nichttrivialen Beispielen und L¨osungen zu verschiedenen Problemen aus verschiedensten Bereichen der Mathematik. All wurden mit Hilfe der entwickelten Theorie und der Im- plementation in Plural erzielt, die meisten von ihnen wurden in dieser Arbeit zum ersten Mal berechnet. Contents Introduction ix Chapter 1. From NDC Towards G–algebras 1 1. Gr¨obner Bases on Free Associative Algebras 2 2. Non–degeneracy Conditions and PBW Theorem 6 3. Introduction to G–algebras 11 4. Filtrations and Properties of G–algebras. 18 5. Opposite algebras 24 6. The Ubiquity of GR–algebras 27 7. Applications of Non–degeneracy Conditions 28 8. Conclusion and Future Work 43 Chapter 2. Gr¨obner bases in G–algebras 45 1. Left Gr¨obner Bases 45 2. Gr¨obner basics I 54 3. Two–sided Gr¨obner Bases and GR–algebras 61 4. Syzygies and Free Resolutions 67 5. Gr¨obner basics II 78 6. Conclusion and Future Work 92 Chapter 3. Morphisms of GR–algebras 95 1. Subalgebras and Morphisms 95 2. Morphisms from Commutative Algebras to GR–algebras 102 3. Central Character Decomposition of the Module 111 4. Morphisms between GR–algebras 116 5. Conclusion and Future Work 129 Chapter 4. Implementation in the system Singular:Plural 131 1. Singular and Plural: history and development 131 2. Aspects of Implementation 137 3. Timings, Performance and Experience 141 4. Download ans Support 144 5. Conclusion and Future Work 145 Chapter 5. Small Atlas of Important Algebras 147 1. Universal Enveloping Algebras of Lie Algebras 147 vii viii CONTENTS 2. Quantum Algebras 149 Chapter 6. Singular:Plural User Manual 151 1. Getting Started with Plural 151 2. Data Types (plural) 152 3. Functions (plural) 170 4. Mathematical Background (plural) 195 5. Plural Libraries 201 Appendix A. Noncommutative Algebra: Examples 240 A.1. Left and two-sided Groebner bases 240 A.2. Right Groebner bases and syzygies 242 Conclusion and Future Work 245 Bibliography 247 Introduction This thesis is devoted to symbolic computations in non–commutative algebras with PBW bases (G–algebras). These algebras already have their own history as well as symbolic methods, algorithms and implementations. Yet it is still a long way towards the acceptance and wide usage of these methodsbythecommunityofscientists, comparabletotheyearswhichwere gone before the Buchberger’s algorithm for computing a Gr¨obner basis of an ideal in a commutative ring become accepted by everybody. G–algebras appear in many fields of science, from Non–commutative Algebra, Ring Theory and Representation Theory of Algebras (being of a more theoreti- cal nature) to the concrete applications to manipulating systems of linear operator (differential, shift, difference etc) equations, System and Control Theory et cetera. These algebras arise in Algebraic Geometry, Mathemat- ical and Theoretical Physics, Statistics and many other fields of natural sciences. They appear in different contexts and everywhere some different computations are needed. We revise G–algebras and enlist a list of their properties in Chapter 1; a short overview of Gr¨obner bases in free algebras helps us to formulate the exact conditions and, on the other hand, to see similarities and differences between different setups. We point out the role of monomial orderings and show their impact on filtrations, coming to simplified and/or generalized proofs of many known results. In Chapter 2, we adopt the notion of Gr¨obner basis to G–algebras and note similarities and differences with the commutative case. Further on, we concentrateondevelopingthefundamentforapplications,basedonGr¨obner bases; continuing a tradition, we call the set of most ubiquitous applications Gro¨bner basics. We provide both theoretical background and efficiency 1 issues together with the implementation. A rich collection of examples, mostly originated from concrete research problems, is a key point of this thesis, since previous publications and even books were rather ascetic with respect to examples. 1AllGr¨obnerbasiscomputationsarenotefficientasthecomplexityisexponentialor even double exponential in the number of variables. When we talk about efficiency, we mean ”practical efficiency”, that is, implementations which allow to compute interesting and complicated examples in a reasonable time. ix x INTRODUCTION The morphisms between GR–algebras (the Chapter 3), appearing as of- ten as such morphisms do in the commutative algebra, deserved however less attention from other authors. We proceed with the partially commu- tative and purely non–commutative situations separately, describing very interesting applications in much details. A study of subalgebras such as centers and various centralizers is naturally arising in this Chapter. The implementation of all the algorithms, elaborated in previous sec- tions, in a computer algebra subsystem Singular:Plural comprises the material of the Chapter 4. We provide timings, create and evaluate bench- marks and discuss aspects of efficiency and software engineering applied to computeralgebra. Alltheexamples,providedwiththisthesis,arecomputed with Plural. It is freely distributed as an integral part of Singular, starting from the version 3-0-0. One can download binaries of Singular for various platforms, the documentation in several formats and supplemen- taryfilesfromthehttp://www.singular.uni-kl.de(note, thatthesource code is available on request). The atlas of important algebras, put in Chapter 5, contains both the explicit presentation of algebras we use in examples and applications, and structural properties like centers of every algebra. Everything in the atlas has been computed with the help of Plural. EveryChapterstartswithanexplanationonitsorganization, soweomit such descriptions here. In the Appendix we put the part of the Singular manual, organized as Chapter 6 and devoted to Plural with the detailed description of its data types, functionalities and libraries. Acknowledgments IamdeeplygratefultomyadvisorsProf.Dr.Yu.DrozdandProf.Dr.G.- M. Greuel for supporting me continuously with advises, remarks and sug- gestions through the whole working period on this thesis. Many interesting topicsofthethesiswouldnothaveevolvedwithouttheinfluence,bridescope of interests and critics of my advisors. I owe very much to the careful read- ing of this manuscript by Gert–Martin Greuel and the valuable corrections he made. Dr. H. Scho¨nemann deserves a very special cordial thanks. Together with him we have created a computer algebra subsystem Plural; we have developed it from the very experimental beginning to the integral part of the Singular kernel. On the way I have learned, what does ”effective computation” really mean in practice.