DOC

Groener Bases - RISC

By Brandon Rodriguez,2015-02-17 18:16
7 views 0
Groener Bases - RISCRISC,bases

    UNIVERSITY OF NAIROBI

    The Department of Mathematics Groebner Bases over finite Fields and over finite extensions of Q

    Maingi M Damian

    I/56/7485/2003

    Academic year 2003/2005

    Supervised by Claudio Achola

     1

Declaration

    This project, as presented in this report is my original work and has not been presented for any other

    University award in any university.

    Maingi Muindi Damian (I/56/7485/2003)

    Signature

    Date

    Signed by Supervisor:

    Claudio Achola

    Signature

    Date

    Authenticated by the Chairman

    Prof John W Owino

    Signature

    Date

    A Research Project submitted to the Department of Mathematics, University of Nairobi in partial

    fulfillment of the requirements for the award of a Degree in Master of Science in Pure Mathematics.

    February 25, 2014

     2

Dedication

    To the great Mathematicians of all time like David Hilbert, Cauchy, Paul Erdos and all men of good will. Let us push on in search for the depths of truth!

     3

Acknowledgement

    To God who has enabled me to undertake this work. To my Dad and Mom who have been such a great source of inspiration and support. To my supervisor, Claudio Achola; how could I forget you? Who has been to me more than a supervisor, you have instilled in me all I could say I know about algebra and many more things about life in general, I will be eternally grateful. I really appreciate the kindness extended to me by Professor Buchberger himself; he assisted me despite the distance and never having met me.

    My sincere thanks go to ICTP and ISP for had it not been there organizing and funding the conferences we have had in Nairobi and Kampala I would not have had an inspiration, I thank Profs Rikaard Bogvad and Enrico Rogora who spend their time reading my dissertation and actually sat down with me to show the corrections I had to make. I also thank Profs Jennifer Morse, Claudio Procesi and Mike Zabrocki since they were the people on ground conducting the conferences. I also remember to thank the Professor Owino for his support as well, sincere thanks go to Dr Patrick Weke for his concern and care for me, I shall not forget people like Dan Odera and Ken Odhiambo, Peter Maina, Linet Muhati, Ngare Odhiambo my former classmates, sincere thanks to Cecilia, Irene and Winnie, to all especially the department members and to all who contributed to the success of this project. How could I ever thank all of you?

     4

Table of contents

    UNIVERSITY OF NAIROBI ........................................................................................................... 1 Dedication ......................................................................................................................................... 3

    1. Introduction................................................................................................................................. 6

    2. Problem statement ....................................................................................................................... 8

    3. Abbreviations and Symbols ......................................................................................................... 9

    4. Concepts and Theorems used .................................................................................................... 10

    4.1 Monomial Ideals and Dickson’s Lemma ............................................................................ 12 4.2 Definitions on monomial orderings .................................................................................. 12 4.3 Hilbert basis theorem ......................................................................................................... 15

    4.4 The notion of “Groebner Bases” ........................................................................................ 16 4.5 The notion of "S-polynomials''........................................................................................... 18

    5 Groebner Bases Computation and the Theory behind ................................................................ 19 5.1 Buchberger’s Algorithm .................................................................................................... 19 5.2 Buchberger’s Algorithm(Another version)- ....................................................................... 20

    Z5.3 Groebner bases for polynomials ideals with coefficients in .......................................... 23 p

    Q(i)5.4 Groebner bases for polynomials ideals with coefficients in ................................... 24

    Q()5.5 Groebner bases for polynomials ideals with coefficients in ................................... 26

    Q()5.6 Groebner Basis for polynomial ideals with coefficients in ................................... 29

    5.6.1 Theorem on simple extensions of fields. Herstein ..................................................... 32

    Q5.6.2 Theorem on Groebner basis over finite extensions of ......................................... 33

    6 Appendix .................................................................................................................................. 36

    7 References ................................................................................................................................ 37

     5

    1. Introduction

    The concept of Groebner Bases was introduced by Buchberger an Austrian, in 1965 in the context of his work on performing algorithmic computations in residue classes of polynomial rings. Buchberger's algorithm for computing Groebner Bases is a powerful tool for solving many important problems in polynomial ideal theory. The algorithm was named after Wolfgang Groebner who was the Ph.D. Advisor to Buchberger and who stimulated the research on the subject. Groebner Bases orderings on monomials. [1]

    Wolfgang Groebner proposed the problem by asking how a multiplicative table for the associative algebra, formed by the residue ring modulo a polynomial ideal can be constructed algorithmically and Buchberger showed that it sufficed to adjoin the differences of each critical pair (S-Polynomials) to get a certain basis that solves this problem in finite number of steps. [5]

    The basic idea of Groebner Bases is that starting from a finite set say A, of polynomials that generate an Ideal, I, say then there is a method that is used to transform the set A into a certain standard form S, this is by following Buchberger’s algorithm.

A Closely related concept i.e. that of “standard bases” was discovered in 1964 by Hironaka. He did

    this independently, but he only gave an unconstructive existence proof. Whereas Buchberger gave a proof for their existence and proceeded to give an algorithmic way of constructing them.

    In the thesis dissertation of Buchberger, we find that he succeeded in establishing the existence of Groebner basis and gave an algorithm for their computation with coefficients in the any field. Our aim

    is to see what happens in the case of finite fields mainly integers modulo a prime number p i.e. Z in p

    Qrelation to the Groebner basis over a rational number field and also whether it is possible to make

    arithmetic in the computation of the Groebner basis with coefficients in the finite extensions of the rational number field. This project is more theoretical oriented in the sense that we do not aim at actually computing Groebner basis since that has already been done see[5] but ours is to facilitate

    the process and to establish some kind of theorem using the theory of fields and especially field extensions to do this.

     6

    After their introduction by Buchberger in 1965, there have been many studies carried out relating to this subject, some of them carried by Buchberger himself with some of his colleagues for instance he

    ]. gives a better version of his algorithm in [6

    Some of the studies that have been carried out relating to this area are: For example in the work of D Kapur and Y Y Cai [7], where they give an algorithm for computing a Groebner Bases of an ideal of

     and , polynomials whose coefficients are taken from a ring with zero divisors, i.e. rings like ZZ[i]nn

    where n is not a prime number. The algorithm is patterned after Buchberger’s algorithm for computing

    a Groebner Bases of a polynomial ideal whose coefficients are from a field and its extension developed by Kandri-Rody and Kapur when the coefficients appearing in the polynomials are from a Euclidean domain. The algorithm works as Buchberger’s algorithm when a polynomial ideal is over a field and as Kandri-Rody and Kapur’s algorithm when a polynomial ideal is over a Euclidean domain.

    There have been many publications and texts on Groebner basis, bearing in mind that they were developed in 1965 and Buchberger gave many papers on their improvement and again many people have studied them and this we can get an idea by looking at the webpage of Buchberger where we find that has co-published many papers on the subject.

     7

    2. Problem statement

    As we will see how to compute Groebner Basis, we will find that their computation over finite fields i.e. having their coefficients in fields is easier than in their computation over rational number fields and it gets more complicated as the field grows or as we extend the field for in instance when we have

    Q()[x,y,z]Qfinite extensions of for instance where is irrational. Then manipulation of

    polynomials over such a field would be agony even for the computer it would take a lot of memory space and thus the speed would be quite compromised. Thus we set out to investigate what could be done to solve these problems and thus to facilitate dealings with happens in the case of Groebner Basis

    Q()computation over more general fields for example finite extensions of the rational number field,

    Q.

Now what drove us to such areas of study?

    We had a school on Algebraic Geometry and Commutative Algebra in August 2004 some of the striking areas at least for me were the part II of the course which were covered by Jennifer Morse and Rikard Bogvad i.e. Ideals, varieties and algorithms and the computer implementation by Mike Zabrocki. Under this we covered;

    ? Division algorithm

    ? Monomial ideals and Dickson’s lemma

    ? Hilbert basis theorem and Groebner Basis

    ? Buchberger’s algorithm

    ? Ideal membership problem, implication problem and elimination theory

    After having attended the conference, I consulted with my supervisor, who gave me a list of projects from [2]. I read the appendix and came across a possible project on improvement of Buchberger’s algorithm for the computation of Groebner basis.

     8

    3. Abbreviations and Symbols

K…………………………………………Field

    ………………………………………Polynomial ring over K K[x]

    …………………………………………Ideal I

    R…………………………………………Ring (Our usual ring is ) K[x]

    I;RR……………………………………Iis an ideal of

    x{x,x...x}…………………………bar stands for n variables x12,n

    ……………………………An Ideal generated by f,f,...f?f,f,...f12n12n

    ………………………………………Integers modulo p ZP

    2Z[i]{xiy/x,y?Zi10}……Gaussian Integers Pp

    Q…………………………………………Rational number field

    2………Gaussian Rational numbers Q(i){xiy/x,y?Qi10}

    Q[x,y,z]Q…………………………………Polynomial ring over x,y,z with coefficients in Q()[x,y,z]……………………………. Polynomial ring over x,y,z with coefficients in

    Q()Q()Q , where is an extension field of

    ………………………………………with respect to w.r.t

     9

4. Concepts and Theorems used

    The ideas we present here are applicable to any polynomial ring RKxKxxx,,[][,,...,] 12k

    I;RKRwhere is a field, and , i.e. I is an ideal of the ring .

Finite extensions [8]

    KA field is said to be an extension field (or field extension, or extension), denoted , of a KF/

    KFFfield if is a subfield of . For example, the complex numbers are an extension field of the real numbers, and the real numbers are an extension field of the rational numbers. The extension field degree (or relative degree, or index) of an extension field , denoted KF/

    [:]KFKF, is the dimension of as a vector space over , i.e.,

    [:]dimKFK F

    FGiven a field , there are a couple of ways to find an extension field. If F is contained in a larger

    F()FF('field, . Then by picking some elements not in F, one defines to be the ?F'

    F'smallest subfield of containing F and the . For instance, the rational numbers can be

    Qi()extended by the complex number , yielding . If there is only one new element, the extension i

    is called a simple extension. The process of adding a new element is called 'adjoining.'

    I;RLet

    i1,2,...nNow the ideal I can be generated by some finite number of elements where g'si

    Ig,g,...g?R, if is Noetherian, for example the polynomial ring that we 12n

    will consider it.

Definition Noetherian Ring [9]

    A ring is called left (respectively, right) Noetherian if it does not contain an infinite ascending

    chain of left (respectively, right) ideals. In this case, the ring in question is said to satisfy the

    ascending chain condition on left (respectively, right) ideals.

     10

Report this document

For any questions or suggestions please email
cust-service@docsford.com