Commutative Gröbner bases theory is well known and widely used. In this thesis, we will discuss thoroughly its generalization to noncommutative polynomial ring <em>k</em><<em>X</em>> which is also an associative free algebra. We introduce some results on monomial orders due to John Lawrence and the author. We show that a noncommutative monomial order is a well order while a one-sided noncommutative monomial order may not be. Then we discuss the generalization of polynomial reductions, S-polynomials and the characterizations of noncommutative Gröbner bases. Some results due to Mora are also discussed, such as the generalized Buchberger's algorithm and the solvability of ideal membership problem for homogeneous ideals. At last, we introduce Newman's diamond lemma and Bergman's diamond lemma and show their relations with Gröbner bases theory.

Commutative Gröbner bases theory is well known and widely used. In this thesis, we will discuss thoroughly its generalization to noncommutative polynomial ring <em>k</em><<em>X</em>> which is also an associative free algebra. We introduce some results on monomial orders due to John Lawrence and the author. We show that a noncommutative monomial order is a well order while a one-sided noncommutative monomial order may not be. Then we discuss the generalization of polynomial reductions, S-polynomials and the characterizations of noncommutative Gröbner bases. Some results due to Mora are also discussed, such as the generalized Buchberger's algorithm and the solvability of ideal membership problem for homogeneous ideals. At last, we introduce Newman's diamond lemma and Bergman's diamond lemma and show their relations with Gröbner bases theory.

<p>We study the power series ring R= K[[x₁,x₂,x₃,...]]on countably infinitely many variables, over a field K, and two particular K-subalgebras of it: the ring S, which is isomorphic to an inverse limit of the polynomial rings in finitely many variables over K, and the ring R', which is the largest graded subalgebra of R.</p><p>Of particular interest are the homogeneous, finitely generated ideals in R', among them the <i>generic ideals</i>. The definition of S as an inverse limit yields a set of <i>truncation homomorphisms</i> from S to K[x₁,...,x_n] which restrict to R'. We have that the truncation of a generic I in R' is a generic ideal in K[x₁,...,x_n]. It is shown in <b>Initial ideals of Truncated Homogeneous Ideals</b> that the initial ideal of such an ideal converge to the initial ideal of the corresponding ideal in R'. This initial ideal need no longer be finitely generated, but it is always <i>locally finitely generated</i>: this is proved in <b>Gröbner Bases in R'</b>. We show in <b>Reverse lexicographic initial ideals of generic ideals are finitely generated</b> that the initial ideal of a generic ideal in R' is finitely generated. This contrast to the lexicographic term order.</p><p> If I in R' is a homogeneous, locally finitely generated ideal, and if we write the Hilbert series of the truncated algebras K[x₁,...,x_n] module the truncation of I as q_n(t)/(1-t)ⁿ, then we show in <b>Generalized Hilbert Numerators </b>that the q_n's converge to a power series in t which we call the <i>generalized Hilbert numerator</i> of the algebra R'/I.</p><p>In <b>Gröbner bases for non-homogeneous ideals in R'</b> we show that the calculations of Gröbner bases and initial ideals in R' can be done also for some non-homogeneous ideals, namely those which have an <i>associated homogeneous ideal</i> which is locally finitely generated.</p><p>The fact that S is an inverse limit of polynomial rings, which are naturally endowed with the discrete topology, provides S with a topology which makes it into a complete Hausdorff topological ring. The ring R', with the subspace topology, is dense in R, and the latter ring is the Cauchy completion of the former. In <b>Topological properties of R'</b> we show that with respect to this topology, locally finitely generated ideals in R'are <i>closed</i>.</p>

We study the power series ring R= K[[x1,x2,x3,...]]on countably infinitely many variables, over a field K, and two particular K-subalgebras of it: the ring S, which is isomorphic to an inverse limit of the polynomial rings in finitely many variables over K, and the ring R', which is the largest graded subalgebra of R. Of particular interest are the homogeneous, finitely generated ideals in R', among them the generic ideals. The definition of S as an inverse limit yields a set of truncation homomorphisms from S to K[x1,...,xn] which restrict to R'. We have that the truncation of a generic I in R' is a generic ideal in K[x1,...,xn]. It is shown in <b>Initial ideals of Truncated Homogeneous Ideals</b> that the initial ideal of such an ideal converge to the initial ideal of the corresponding ideal in R'. This initial ideal need no longer be finitely generated, but it is always locally finitely generated: this is proved in <b>Gröbner Bases in R'</b>. We show in <b>Reverse lexicographic initial ideals of generic ideals are finitely generated</b> that the initial ideal of a generic ideal in R' is finitely generated. This contrast to the lexicographic term order. If I in R' is a homogeneous, locally finitely generated ideal, and if we write the Hilbert series of the truncated algebras K[x1,...,xn] module the truncation of I as qn(t)/(1-t)n, then we show in <b>Generalized Hilbert Numerators </b>that the qn's converge to a power series in t which we call the generalized Hilbert numerator of the algebra R'/I. In <b>Gröbner bases for non-homogeneous ideals in R'</b> we show that the calculations of Gröbner bases and initial ideals in R' can be done also for some non-homogeneous ideals, namely those which have an associated homogeneous ideal which is locally finitely generated. The fact that S is an inverse limit of polynomial rings, which are naturally endowed with the discrete topology, provides S with a topology which makes it into a complete Hausdorff topological ring. The ring R', with the subspace topology, is dense in R, and the latter ring is the Cauchy completion of the former. In <b>Topological properties of R'</b> we show that with respect to this topology, locally finitely generated ideals in R'are closed.

Orientador: Patrícia Helena Araújo da Silva Nogueira / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-17T08:03:36Z (GMT). No. of bitstreams: 1 Staib_FredericoFontes_M.pdf: 14016255 bytes, checksum: 4ec6112a82029b5e16c1c450779bf803 (MD5) Previous issue date: 2010 / Resumo: Neste trabalho, estudamos a teoria das bases de Gröbner e sua aplicação ao problema da k-coloração de grafos, estabelecendo assim uma interessante conexão entre a álgebra abstrata e a matemática discreta. Fazemos também uma abordagem de caráter lúdico, traduzindo o passatempo chamado Sudoku em um problema de 9-coloração e utilizando a teoria apresentada para resolvê-lo através das bases de Gröbner / Abstract: In the present work, we study the Gröbner basis theory and its application on the graph k-coloring problem, establishing an interesting relation between abstract algebra and discrete mathematics. We make a ludic approach, translating the puzzle called Sudoku to a 9-coloring problem and using the given theory to solve it by the Gröbner basis / Mestrado / Algebra / Mestre em Matemática

This paper continues our study of applications of factorized Gröbner basis computations in [8] and [9]. We describe a way to interweave factorized Gröbner bases and the ideas in [5] that leads to a significant speed up in the computation of isolated primes for well splitting examples. Based on that observation we generalize the algorithm presented in [22] to the computation of primary decompositions for modules. It rests on an ideal separation argument. We also discuss the practically important question how to extract a minimal primary decomposition, neither addressed in [5] nor in [17]. For that purpose we outline a method to detect necessary embedded primes in the output collection of our algorithm, similar to [22, cor. 2.22]. The algorithms are partly implemented in version 2.2.1 of our REDUCE package CALI [7].

Let k be a field, S = k[xv : v ϵ V] be the polynomial ring over the finite set of variables (xv : v ϵ V), and m = (xv : v ϵ V) the ideal defining the origin of Spec S. It is theoretically known (see e.g. Alonso et el., 1991) that the algorithmic ideas for the computation of ideal (and module) intersections, quotients, deciding radical membership etc. in S may be adopted not only for computations in the local ring Sm but also for term orders of mixed type with standard bases replacing Gröbner bases. Using the generalization of Mora's tangent cone algorithm to arbitrary term orders we give a detailed description of the necessary modifications and restrictions. In a second part we discuss a generalization of the deformation argument for standard bases and independent sets to term orders of mixed type. For local term orders these questions were investigated in Gräbe (1991). The main algorithmic ideas described are implemented in the author's REDUCE package CALI (Gräbe, 1993a).

Please download dissertation to view abstract.

How does the brain encode the spatial structure of the external world? A partial answer comes through place cells, hippocampal neurons which become associated to approximately convex regions of the world known as their place fields. When an organism is in the place field of some place cell, that cell will fire at an increased rate. A neural code describes the set of firing patterns observed in a set of neurons in terms of which subsets fire together and which do not. If the neurons the code describes are place cells, then the neural code gives some information about the relationships between the place fields–for instance, two place fields intersect if and only if their associated place cells fire together. Since place fields are convex, we are interested in determining which neural codes can be realized with convex sets and in finding convex sets which generate a given neural code when taken as place fields. To this end, we study algebraic invariants associated to neural codes, such as neural ideals and toric ideals. We work with a special class of convex codes, known as inductively pierced codes, and seek to identify these codes through the Gröbner bases of their toric ideals.

Title: Applications of Gröbner bases in cryptography Author: Aleš Fuchs Department: Department of Algebra Supervisor: Mgr. Jan Št'ovíček Ph.D., Department of Algebra Abstract: In the present paper we study admissible orders and techniques of multivariate polynomial division in the setting of polynomial rings over finite fields. The Gröbner bases of some ideal play a key role here, as they allow to solve the ideal membership problem thanks to their properties. We also explore features of so called reduced Gröbner bases, which are unique for a particular ideal and in some way also minimal. Further we will discuss the main facts about Gröbner bases also in the setting of free algebras over finite fields, where the variables are non-commuting. Contrary to the first case, Gröbner bases can be infinite here, even for some finitely generated two- sided ideals. In the last chapter we introduce an asymmetric cryptosystem Polly Cracker, based on the ideal membership problem in both commutative and noncommutative theory. We analyze some known cryptanalytic methods applied to these systems and in several cases also precautions dealing with them. Finally we summarize these precautions and introduce a blueprint of Polly Cracker reliable construction. Keywords: noncommutative Gröbner bases, Polly Cracker, security,...