Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-11-06T18:45:09Z No. of bitstreams: 1 maurorodriguesrochajunior.pdf: 550118 bytes, checksum: 5b26ad1ab2bd9d4a190d742762346968 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-11-09T14:32:38Z (GMT) No. of bitstreams: 1 maurorodriguesrochajunior.pdf: 550118 bytes, checksum: 5b26ad1ab2bd9d4a190d742762346968 (MD5) / Made available in DSpace on 2017-11-09T14:32:38Z (GMT). No. of bitstreams: 1 maurorodriguesrochajunior.pdf: 550118 bytes, checksum: 5b26ad1ab2bd9d4a190d742762346968 (MD5) Previous issue date: 2017-08-11 / O principal objetivo desse trabalho é estudar duas aplicações distintas das bases de Gröbner a códigos lineares. Com esse objetivo, estudamos como relacionar códigos a outras estruturas matemáticas, fazendo com que tenhamos novas ferramentas para a realização da codificação. Em especial, estudamos códigos cartesianos afins e os códigos algébrico-geométricos de Goppa. / The main objective of this work is to study two different applications of Gröbner basis to linear codes. With this purpose, we study how to relate codes to other mathematical structures, allowing us to use new tools to do the coding. In particular, we study affine cartesian codes e algebraic-geometric Goppa codes.

Neste trabalho estudamos algumas características das álgebras de Koszul, como por exemplo, a maneira como elas se relacionam com suas respectivas álgebras de Yoneda. Descrevemos a álgebra de Yoneda de uma álgebra monomial e como aplicação construímos uma família de álgebras: as chamadas homologicamente auto-duais. Uma álgebra de Koszul pode ser definida a partir da existência de resoluções lineares dos módulos simples. Por isso faz-se necessário a dedicação de parte de nossa atenção ao estudo destas resoluções. Além disso, achamos interessante estudar métodos para a construção de resoluções projetivas de módulos sobre quocientes de álgebras de caminhos. Para tal construção usamos essencialmente a teoria de bases de Gröbner não comutativas. Finalmente, para o caso de módulos lineares sobre álgebras de Koszul, veremos que é possível modicar essa construção de modo que a resolução resultante seja linear. / In this work we study some features of Koszul algebras as, for example, the way that they are related with their Yoneda algebras. We describe the Yoneda algebra of a monomial algebra and as an application we construct a family of algebras: the so called homologically self-dual algebras. A Koszul algebra can be dened as an algebra for which there are linear resolutions of their simple modules. Because of this we dedicate part of our attention to the study of projective resolutions. The study of methods for the construction of projectives resolutions of modules over quotients of path algebras, has an of interest its own. For the study of projective resolutions we used the theory of noncommutative, Gröbner bases. Finally, for the case of linear modules over Koszul algebras, we will see that it is possible to modify the general construction described here, so that the resulting resolution is linear.

Dans cette thèse, nous étudions le concept d’algèbre pré-Lie libre engendrée par un ensemble (non-vide). Nous rappelons la construction par A. Agrachev et R. Gamkrelidze des bases de monômes dans les algèbres pré-Lie libres. Nous décrivons la matrice des vecteurs d’une base de monômes en termes de la base d’arbres enracinés exposée par F. Chapoton et M. Livernet. Nous montrons que cette matrice est unipotente et trouvons une expression explicite pour les coefficients de cette matrice, en adaptant une procédure suggérée par K. Ebrahimi-Fard et D. Manchon pour l’algèbre magmatique libre. Nous construisons une structure d’algèbre pré-Lie sur l’algèbre de Lie libre $\mathcal{L}$(E) engendrée par un ensemble E, donnant une présentation explicite de $\mathcal{L}$(E) comme quotient de l’algèbre pré-Lie libre $\mathcal{T}$^E, engendrée par les arbres enracinés (non-planaires) E-décorés, par un certain idéal I. Nous étudions les bases de Gröbner pour les algèbres de Lie libres dans une présentation à l’aide d’arbres. Nous décomposons la base d’arbres enracinés planaires E-décorés en deux parties O(J) et $\mathcal{T}$(J), où J est l’idéal définissant $\mathcal{L}$(E) comme quotient de l’algèbre magmatique libre engendrée par E. Ici, $\mathcal{T}$(J) est l’ensemble des termes maximaux des éléments de J, et son complément O(J) définit alors une base de $\mathcal{L}$(E). Nous obtenons un des résultats importants de cette thèse (Théorème 3.12) sur la description de l’ensemble O(J) en termes d’arbres. Nous décrivons des bases de monômes pour l’algèbre pré-Lie (respectivement l’algèbre de Lie libre) $\mathcal{L}$(E), en utilisant les procédures de bases de Gröbner et la base de monômes pour l’algèbre pré-Lie libre obtenue dans le Chapitre 2. Enfin, nous étudions les développements de Magnus classique et pré-Lie, discutant comment nous pouvons trouver une formule de récurrence pour le cas pré-Lie qui intègre déjà l’identité pré-Lie. Nous donnons une vision combinatoire d’une méthode numérique proposée par S. Blanes, F. Casas, et J. Ros, sur une écriture du développement de Magnus classique, utilisant la structure pré-Lie de $\mathcal{L}$(E). / In this thesis, we study the concept of free pre-Lie algebra generated by a (non-empty) set. We review the construction by A. Agrachev and R. Gamkrelidze of monomial bases in free pre-Lie algebras. We describe the matrix of the monomial basis vectors in terms of the rooted trees basis exhibited by F. Chapoton and M. Livernet. Also, we show that this matrix is unipotent and we find an explicit expression for its coefficients, adapting a procedure implemented for the free magmatic algebra by K. Ebrahimi-Fard and D. Manchon. We construct a pre-Lie structure on the free Lie algebra $\mathcal{L}$(E) generated by a set E, giving an explicit presentation of $\mathcal{L}$(E) as the quotient of the free pre-Lie algebra $\mathcal{T}$^E, generated by the (non-planar) E-decorated rooted trees, by some ideal I. We study the Gröbner bases for free Lie algebras in tree version. We split the basis of E- decorated planar rooted trees into two parts O(J) and $\mathcal{T}$(J), where J is the ideal defining $\mathcal{L}$(E) as a quotient of the free magmatic algebra generated by E. Here $\mathcal{T}$(J) is the set of maximal terms of elements of J, and its complement O(J) then defines a basis of $\mathcal{L}$(E). We get one of the important results in this thesis (Theorem 3.12), on the description of the set O(J) in terms of trees. We describe monomial bases for the pre-Lie (respectively free Lie) algebra $\mathcal{L}$(E), using the procedure of Gröbner bases and the monomial basis for the free pre-Lie algebra obtained in Chapter 2. Finally, we study the so-called classical and pre-Lie Magnus expansions, discussing how we can find a recursion for the pre-Lie case which already incorporates the pre-Lie identity. We give a combinatorial vision of a numerical method proposed by S. Blanes, F. Casas, and J. Ros, on a writing of the classical Magnus expansion in $\mathcal{L}$(E), using the pre-Lie structure.

La résolution de systèmes polynomiaux est un problème aux multiples applications, et les bases de Gröbner sont un outil important dans ce cadre. Il est connu que de nombreux systèmes issus d'applications présentent une structure supplémentaire par rapport à des systèmes arbitraires, et que ces structures peuvent souvent être exploitées pour faciliter le calcul de bases de Gröbner.Dans cette thèse, on s'intéresse à deux exemples de telles structures, pour différentes applications. Tout d'abord, on étudie les systèmes homogènes avec poids, qui sont homogènes si on calcule le degré en affectant un poids à chaque variable. Cette structure apparaît naturellement dans de nombreuses applications, dont un problème de cryptographie (logarithme discret). On montre comment les algorithmes existants, efficaces pour les polynômes homogènes, peuvent être adaptés au cas avec poids, avec des bornes de complexité générique divisées par un facteur polynomial en le produit des poids.Par ailleurs, on étudie un problème de classification de racines réelles pour des variétés définies par des déterminants. Ce problème a une application directe en théorie du contrôle, pour l'optimisation de contraste de l'imagerie à résonance magnétique. Ce système particulier s'avère insoluble avec les stratégies générales pour la classification. On montre comment ces stratégies peuvent tirer profit de la structure déterminantielle du système, et on illustre ce procédé en apportant des réponses aux questions posées par le problème d'optimisation de contraste. / Polynomial system solving is a problem with numerous applications, and Gröbner bases are an important tool in this context. Previous studies have shown that systèmes arising in applications usually exhibit more structure than arbitrary systems, and that these structures can be used to make computing Gröbner bases easier.In this thesis, we consider two examples of such structures. First, we study weighted homogeneous systems, which are homogeneous if we give to each variable an arbitrary degree. This structure appears naturally in many applications, including a cryptographical problem (discrete logarithm). We show how existing algorithms, which are efficient for homogeneous systems, can be adapted to a weighted setting, and generically, we show that their complexity bounds can be divided by a factor polynomial in the product of the weights.Then we consider a real roots classification problem for varieties defined by determinants. This problem has a direct application in control theory, for contrast optimization in magnetic resonance imagery. This specific system appears to be out of reach of existing algorithms. We show how these algorithms can benefit from the determinantal structure of the system, and as an illustration, we answer the questions from the application to contrast optimization.

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

In this thesis, we address problems from two topics of applied mathematics: linear integer programming and polyhedral computation. Linear integer programming concerns solving optimisation problems to maximise a linear cost function over the set of integer points in a polyhedron. Polyhedral computation is concerned with algorithms for computing different properties of convex polyhedra. First, we explore the theory and computation of Gröbner bases and Markov bases for linear integer programming. Second, we investigate and improve an algorithm from polyhedral computation that converts between different representations of cones and polyhedra. A Markov basis is a set of integer vectors such that we can move between any two feasible solutions of an integer program by adding or subtracting vectors in the Markov basis while never moving outside the set of feasible solutions. Markov bases are mainly used in algebraic statistics for sampling from a set of feasible solutions. The major contribution of this thesis is a fast algorithm for computing Markov bases, which we used to solve a previously intractable computational challenge. Gröbner basis methods are exact local search approaches for solving integer programs. We present a Gröbner basis approach that can use the structure of an integer program in order to solve it more efficiently. Gröbner basis methods are interesting mainly from a purely theoretical viewpoint, but they are also interesting because they may provide insight into why some classes of integer programs are difficult to solve using standard techniques and because someday they may be able to solve these difficult problems. Computing the properties of convex polyhedra is useful for solving problems within different areas of mathematics such as linear programming, integer programming, combinatorial optimisation, and computational geometry. We investigate and improve an algorithm for converting between a generator representation of a cone or polyhedron and a constraint representation of the cone or polyhedron and vice versa. This algorithm can be extended to compute circuits of matrices, which are used in computational biology for metabolic pathway analysis.

En cinématique il n'existe aucune méthode permettant de générer les conditions d'assemblage sous forme symbolique pour les systèmes de solides, éventuellement surcontraints. En revanche il existe un grand nombre de formules permettant- en principe - de calculer la mobilité. Les noms de Kutzbach, Grübler et Tchebytcheff sont associés à différentes formules bien connues mais aucune formule infaillible n'a jamais été trouvée. C'est ce qui motive notre proposition de méthodes numériques et symboliques constructives. Celles-ci permettent de générer automatiquement les conditions d'assemblage et de mobilité à partir de la connaissance des équations de fermeture des boucles de solides. Les méthodes numérique et symbolique présentées dans cette thèse se basent sur un socle commun. Elles utilisent les paramètres de Denavit-Hartenberg et les classent en deux catégories: la première catégorie, notée u pour usinage, représente les dimensions géométriques des solides, la seconde, notée m pour mobilité, représente les paramètres de position relative de deux solides en contact. Ensuite, les équations de fermeture sont obtenues par une méthode ''coordinate free'' à partir d'une matrice de Gram. C'est à cette étape que les deux méthodes diffèrent. Dans le cas de l'analyse numérique locale, le système d'équations est linéarisé. La décomposition en valeur singulière est utilisée pour l'élimination des paramètres. Nous obtenons ensuite les conditions d'assemblage dans un voisinage de la configuration initiale. Les conditions de mobilité sont calculées à partir des conditions d'assemblage issues d'un nombre fini de configurations. Dans le cas de l'analyse symbolique, nous calculons formellement la base de Gröbner associée aux équations de fermeture et cela grâce à l'algorithme FGb de Faugère. Il existe peu de références sur l'utilisation des Bases de Gröbner en cinématique, et aucune ne présente une analyse exhaustive du problème. Avec l'ordre lexicographique, nous ne gardons que des paramètres u et éliminons tous les autres. Lorsque ces relations en u sont vérifiées, elles représentent les conditions d'assemblage, dites relations de surcontraintes. Cet ensemble peut être vide lorsque le système est isocontraint. Pour générer les conditions de mobilité, nous gardons tous les u et un paramètre de mobilité. En annulant les coefficients en facteur de ce paramètre de mobilité, un nouveau système qui ne dépend que de u est construit. Les conditions de mobilité sont obtenues en calculant la base de Gröbner du nouveau système. Pour atteindre les résultats désirés, nous avons également proposé deux outils: saturation et contrainte. Ils permettent de parcourir un sous-ensemble de solutions représentées par une base de Gröbner. La confrontation des résultats obtenus dans la thèse avec ceux de la littérature, pour quelques de mécanismes connus, permet d'affirmer la validité et la complétude de la méthode.

Orientador: Fernando Eduardo Torres Orihuela / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-11T03:53:44Z (GMT). No. of bitstreams: 1 Tizziotti_GuilhermeChaud_D.pdf: 891044 bytes, checksum: 4e90b377185548b051c39ead60bdf183 (MD5) Previous issue date: 2008 / Resumo: Estendemos resultados de Heegard, Little e Saints relacionados a bases de Gröbner para códigos Hermitianos pontuais. Trabalhamos com códigos Hermitianos bipontuais e n-pontuais, e com códigos sobre a curva Norma-Traço. Além disso, determinamos o semigrupo de Weierstrass de um certo par de pontos racionais sobre a curva Norma-Traço e com esse semigrupo conseguimos melhorar a cota da distância mínima de códigos construídos sobre tais curvas / Abstract: We extend results of Heegard, Little and Saints concerning the Gröbner basis algorithm for one-point Hermitian codes. We work with two-point and n-point Hermitian codes and codes arising from the Norm-Trace curve. We also determine the Weierstrass semigroup at a certain pair of rational points in such curves and uses these computations to improve the lower bound on the minimum distance of two-point algebraic geometry codes arising from them / Doutorado / Algebra, Geometria Algebrica / Doutor em Matemática