Session on Gröbner Bases and their Applications

Organized by   Elizabeth Arnold (Virginia, USA),   Ilias Kotsireas (Waterloo, Canada)   Markus Rosenkranz (Linz, Austria)

in the frame of the conference

ACA 2008, RISC-Linz, Castle of Hagenberg, Austria, July 27-30, 2008.

Honorary Session Chairman: Bruno Buchberger
The recipient of the 2007 ACM Paris Kanellakis Theory and Practice Award

JSC special issue




The theory of Gröbner Bases is a cornerstone of Computer Algebra which has also found (often unexpected) applications to a wide spectrum of areas in Science and Engineering. All major computer algebra systems offer Gröbner Bases functionalities, and powerful stand-alone implementations are also available.

This session is intended to discuss recent theoretical and practical developments in the theory of Gröbner bases as well as applications of Gröbner bases to other fields. Research contributions as well as expository papers are solicited. For more information and/or to present a paper at the session, please contact the session organizers by e-mail.

This session is a continuation of a series of sessions on the theory of Gröbner bases and its applications organized at previous ACA conferences and other workshops.

Session Topics inlcude (but are not limited to):

  • elimination theory
  • computational commutative algebra
  • multivariate polynomial ideal theory
  • solving systems of algebraic equations
  • Algorithms for computing GB's
  • GB for improving oil drilling platforms
  • GB for guessing "missing links" in palaeontology
  • GB in cryptography (code breaking)
  • GB in software engineering (automated inductive assertion generation)
  • GB for sudoku
  • GB in origami
  • GB in combinatorial design theory
  • GB in computer aided design
  • GB in solid modeling
  • GB in mathematics
  • GB in logic
  • GB in education
  • GB in geometrical theorem proving
  • GB in integer programming
  • GB in sciences and engineering

     SCHEDULE OF TALKS, ALL TALKS WILL BE HELD IN ROOM A
SUNDAY
13:30 - 14:00 Robbiano
14:00 - 14:30 Abbott
15:00-15:30 Bulygin
15:30-16:00 Chionh
16:00-16:30 Dahan
17:00-17:30 Gerdt
17:30-18:00 Bigatti
18:00-18:30 Sato

 MONDAY
9:00-9:30 Schenzel
9:30-10:00 Ida
10:00-10:30 Montes
11:00-11:30 Rosenkranz
11:30-12:00 Blanco
15:00-15:30 Reccio
15:30-16:00 Kalorkoti
16:00-16:30 Pommaret
17:00-17:30 Wang
17:30-18:00 Motsak
18:00-18:30 La Scala

 WEDNESDAY
9:00-9:30 Martinez-Moro
9:30-10:00 Lichtblau
10:00-10:30 Diaz-Toca

LIST OF TALKS

  1. John Abbott

    Title: Stable Border Bases

    Abstract: Empirical data are represented as approximate points; the aim is to determine a border basis (a generalization of Grobner basis) valid up to the given uncertainty in the data.

  2. Anna Bigatti

    Title: The Self-saturating Buchberger Algorithm

    Abstract: The difficulties in computing Groebner bases for non-homogeneous inputs are addressed by a combination of homogenization and dynamic saturation.

  3. Victor Blanco

    Title: Multiobjective Polynomial Integer Programming using Groebner Bases

    Abstract: We give a new methodology for solving multiobjective polynomial integer programming, based in the construction of certain Gröbner bases. Specifically, with this tool we compute the entire set of efficient solutions of any multiobjective polynomial integer problem. Some examples will illustrate the application of the algorithm.
  4. Stanislav Bulygin

    Title: Obtaining and solving systems of equations in key variables only for the small variants of AES

    Abstract: In this talk I discuss an algebraic attack on small scale variants of the Advanced Encryption Standard (AES). The idea is to put up a system of polynomial equations, solving which would reveal the secret key. As opposed to previous works, we try to eliminate all intermediate variables, so that only variables that correspond to the key remain. This approach potentially gives an opportunity to use several plaintext/ciphertext pairs for the attack. We also discuss the meet-in-the-middle attack. This talk is a result of joint work with Michael Brickenstein.

  5. Eng-Wee Chionh

    Title: Some "Numerology" for the Moving Surfaces Implicitization Technique with Gröbner Blending Functions
    Abstract

  6. Xavier Dahan

    Title: Lexicographic Gröbner basis as generalized Lagrange interpolation polynomials and its applications

    Abstract: We give a simple framework for regarding the polynomials of a zero-dimensional radical lexicographic Gröbner basis as a generalization of Lagrange interpolation polynomials. This extends a previous work (Dahan - Schost, ISSAC 2004) which dealt only with very specific lexicographic Gröbner bases, the Lazard triangular sets. We show how to derive some bounds on the size of the coefficients (for a first approach, those do not concern *reduced* Gröbner bases yet. At the time of the talk, this drawback may certainly change...) Such bounds provide a numerical criterion for choosing a lucky prime p (term borrowed from Arnold's "Modular algorithms for computing Gröbner bases bases", JSC 2003). in the background of modular methods. Some variations may be given also: parametrization of all the Gröbner bases of a given finite family of points with a caracterization of the reduced one, introduction to a transformation (used in Dahan Schost, ISSAC 2004) for general radical zero dimensional lexicographic Gröbner, in order to reduce the size of the coefficients.

  7. Gema M. Diaz-Toca

    Title: Dynamic Galois Theory and Gröbner Basis
    Abstract

  8. Gerdt V.P., Zinin M.V.

    Title: On efficiency of involutive criteria in computing Boolean Groebner bases
    Abstract

  9. Tetsuo Ida

    Title: Analysis of Automated Proof of Origami Morley's Theorem
    Abstract

  10. Kyriakos Kalorkoti

    Title: Model Checking in the Modal mu-Calculus by Substitutions and Generic Solutions

    Abstract: We give an algebraic method for model checking in the modal mu-calculus over finite state labelled transition systems. This can be used to provide solutions that are in a sense generic, i.e., in a formula the quantifiers can be left as unknowns. The resulting solution can then be used with the method of Gröbner bases to determine for which choice of quantifiers in a formula (and all sub-formulae) have a chosen truth value. The ability to provide generic solutions can be seen as a useful tool for providing examples either for pedagogical reasons of for case studies.

  11. Roberto La Scala and Viktor Levandovskyy

    Title: Letterplace ideals and non-commutative Groebner bases

    Abstract: In this paper we propose a 1-to-1 correspondence between graded two-sided ideals of the free associative algebra and some class of ideals of the algebra of polynomials whose variables are double-indexed commuting ones. We call these ideals the ``letterplace analogues'' of graded two-sided ideals. We study the behaviour of the generating sets of the ideals under this correspondence and in particular that of the Groebner bases. In this way, we obtain a new method to compute non-commutative homogeneous Groebner bases via polynomials in commuting variables. Since the letterplace ideals are stable under the action of a monoid of endomorphisms of the polynomial algebra, the proposed algorithm results an example of a Buchberger procedure ``reduced by symmetry''. Owing to portability of our algorithm in any computer algebra system able to compute commutative Groebner bases, we present an experimental implementation of our method in Singular. By means of a representative set of examples, we show finally that our implementation is competitive with professional computer algebra systems that provide non-commutative Groebner bases.

  12. Daniel Lichtblau

    Title: Exact Computation using Approximate Groebner Bases
    Abstract: We discuss computation of approximate Groebner bases at high but finite precision. We show how this can be used to deduce exact results.

  13. Edgar Martínez Moro

    Title: Groebner presentations of a monoid algebras and applications
    Abstract

  14. Antonio Montes

    Title: Canonical reduced comprehensive Groebner System

    Abstract: I will present the basic features of the "Minimal Canonical Comprehensive Groebner System" (MCCGS), and the algorithm to obtain it. It works under the hypothesis of a conjecture to produce the most compact canonical reduced possible CGS. It can be used for ideals in the affine space. Using Wibmer's Theorem for homogeneous polynomials I will show that the conjecture can be avoided for non-homogeneous polynomials as well. This also allows to obtain a better natural canonical partition of the parameter space whose existence is theoretically proved and that is described by locally closed sets.

  15. Oleksandr Motsak

    Title: Supercommutative algebras

    Abstract: We consider supercommutative algebras which generalize both commutative polynomial algebra as well as exterior (Grassmann) algebra. In contrast to the usual treatment as a factor algebras we introduce the usual computer algebra notions directly for supercommutative algebras and emphase differences occurring due to the presence of zero divisors. Although being essentially the same as the general non-commutative Buchberger algorithmus for factor algebras our Groebner basis (GB) algorithmus efficiently uses an intrinsic characterization of a GB in a supercommutative algebra. Moreover, it turns out that the product criterion holds true for Z_2-homogeneous polynomials. Thus we get an efficient GB algorithm in a supercommutative algebra and in particular in an exterior (Grassmann) algebra whose applications include: automatic geometrical theorem proving, analysis of properties of exterior differential systems, computation of sheaf cohomologies.

  16. Jean-François Pommaret

    Title: Macaulay inverse systems revisited with application to control identifiability
    Abstract

  17. Tomas Recio

    Title: A protocol for automatic discovery of geometry theorems through Minimal Canonical Comprehensive Gröbner Basis

    Abstract: The main proposal in this talk is the merging of two techniques that have been recently developed (cf. Montes-Recio, Springer Lect. Notes Artificial Intelligence, 4869, pp. 113-139, 2007). On the one hand, we consider a new approach for computing some specializable Gröbner basis, the so called Minimal Canonical Comprehensive Gröbner Systems (MCCGS) that is -roughly speaking- a computational procedure yielding ``good" bases for ideals of polynomials over a field, depending on several parameters, that specialize ``well", for instance, regarding the number of solutions for the given ideal, for different values of the parameters. The second ingredient is related to automatic theorem discovery in elementary geometry. Automatic discovery aims to obtain complementary (equality and inequality type) hypotheses for a (generally false) geometric statement to become true. The talk presents and discusses a protocol for automatic discovery and shows how to use MCCGS in this context. Joint work with Antonio Montes.

  18. Lorenzo Robbiano

    Title: Border Basis and Groebner Basis Schemes, Lorenzo Robbiano

    Abstract: These schemes parameterize families of border/Groebner bases; they give a solid mathematical foundation to situations dealing with approximate data.

  19. Markus Rosenkranz, Georg Regensburger

    Title: Groebner Bases for Boundary Value Problems

    Abstract: In symbolic analysis, operator algebras are modelled by noncommutative polynomials modulo ideals encoding their relations. The setup is simple in the case of the Weyl algebra (with the Leibniz rule as the only nontrivial relation) but needs some work for more involved operator algebras. We present one such example: The algebra of integro-differential operators is an extension of the univariate Weyl algebra (or of a ring of differential operators) that contains integral and boundary operators. The ideal of relations is described by a constructive infinite Groebner basis with noetherian reduction. We show how this operator algebra can be applied to compute the Green's operator of Stieltjes boundary problems for linear ordinary differential equations.

  20. Yosuke Sato

    Title: Boolean Gröbner Bases and Sudoku
    Abstract

  21. Peter Schenzel

    Title: Towards a classification of projective varieties by their degree
    Abstract

  22. Haohao Wang, Xiaohong Jia, Ron Goldman

    Title: Axial Moving Planes and Singularities of Rational Space Curves

    Abstract: Relationships between the singularities of rational space curves and the moving planes that follow these curves are investigated. Given a space curve C with a generic 1-1 rational parametrization F(s,t) of degree d, we show that if P and Q are two singular points of orders k and k' on the space curve C, then there is a moving plane of degree d-k-k' with axis PQ that follows the curve. We also show that a point P is a singular point of order k on the space curve C if and only if there are two axial moving planes L_1 and L_2 of degree d-k such that: (1) the axes of L_1, L_2 are orthogonal and intersect at P, and (2) the intersection of the moving planes L_1 and L_2 is the cone through the curve C with vertex P together with d-k copies of the plane containing the axes of L_1 and L_2. In addition, we study relationships between the singularities of rational space curves and generic moving planes that follow these curves. We show that if p(s,t), q(s,t), r(s,t) are a mu-basis for the moving planes that follow a rational space curve F(s,t), then P is a singular point of F(s,t) of order k, if and only if deg(gcd(p(s,t).P, q(s,t).P, r(s,t).P))=k. Moreover, the roots of this gcd are the parameters, counted with proper multiplicity, that correspond to the singularity P. Using these results, we provide straightforward algorithms for finding all the singularities of low degree rational space curves. Our algorithms are easy to implement, requiring only standard techniques from linear algebra. Examples are provided to illustrate these algorithms.

Relevant Links:


Papers presented at the session will be considered for publication at a special issue of a journal.