Minimal Gröbner bases and the predictable leading monomial property

We focus on Gröbner bases for modules of univariate polynomial vectors over a ring. We identify a useful property, the “predictable leading monomial (PLM) property” that is shared by minimal Gröbner bases of modules in F[x]^q, no matter what positional term order is used. The PLM property is useful in a range of applications and can be seen as a strengthening of the wellknown predictable degree property (= row reducedness), a terminology introduced by Forney in the 70’s. Because of the presence of zero divisors, minimal Gröbner bases over a finite ring of the type Z_p^r (where p is a prime integer and r is an integer >1) do not necessarily have the PLM property. In this paper we show how to derive, from an ordered minimal Gröbner basis, a so-called “minimal Gröbner p-basis” that does have a PLM property. We demonstrate that minimal Gröbner p-bases lend themselves particularly well to derive minimal realization parametrizations over Z_p^r. Applications are in coding and sequences over Z_p^r.     

Gröbner-Shirshov basis of the Adyan extension of the Novikov group

The goal of this paper is to give a comparatively short and simple analysis of the Adyan origional group constraction (S.I. Adyan, Unsolvability of some algorithmic problems in the theory of groups, Trudy MMO 6 (1957) 231-298).     

Gröbner bases of balanced polyominoes

We introduce balanced polyominoes and show that their ideal of inner minors is a prime ideal and has a squarefree Gröbner basis with respect to any monomial order, and we show that any row or column convex and any tree‐like polyomino is simple and balanced.     

Gröbner bases of ideals cogenerated by Pfaffians

We characterise the class of one-cogenerated Pfaffian ideals whose natural generators form a Gröbner basis with respect to any anti-diagonal term order. We describe their initial ideals as well as the associated simplicial complexes, which turn out to be shellable and thus Cohen-Macaulay. We also provide a formula for computing their multiplicity.     

Finite lattices and Gröbner bases

Gröbner bases of binomial ideals arising from finite lattices will be studied. In terms of Gröbner bases and initial ideals, a characterization of finite distributive lattices as well as planar distributive lattices will be given.     

Gröbner–Shirshov bases of some monoids

The main goal of this paper is to define Gröbner–Shirshov bases for some monoids. Therefore, after giving some preliminary material, we first give Gröbner–Shirshov bases for graphs and Schützenberger products of monoids in separate sections. In the final section, we further present a Gröbner–Shirshov basis for a Rees matrix semigroup.     

Multivariate Refinable Functions of High Approximation Order Via Quotient Ideals of Laurent Polynomials

We give an algebraic interpretation of the well-known zero-condition or sum rule for multivariate refinable functions with respect to an arbitrary scaling matrix. The main result is a characterization of these properties in terms of containment in a quotient ideal, however not in the ring of polynomials but in the ring of Laurent polynomials.     

On the number of distinct multinomial coefficients

We study M(n), the number of distinct values taken by multinomial coefficients with upper entry n, and some closely related sequences. We show that both pP(n)/M(n) and M(n)/p(n) tend to zero as n goes to infinity, where pP(n) is the number of partitions of n into primes and p(n) is the total number of partitions of n. To use methods from commutative algebra, we encode partitions and multinomial coefficients as monomials.     

Gröbner bases for the Hilbert ideal and coinvariants of the dihedral group D2p

We consider a finite dimensional representation of the dihedral group D_2p over a field of characteristic two where p is an odd integer and study the corresponding Hilbert ideal I_H. We show that I_H has a universal Gröbner basis consisting of invariants and monomials only. We provide sharp bounds for the degree of an element in this basis and in a minimal generating set for I_H. We also compute the top degree of coinvariants when p is prime.     

On the complexity of solving quadratic Boolean systems

A fundamental problem in computer science is that of finding all the common zeros of m$m$ quadratic polynomials in n$n$ unknowns over _F2${\mathbb{F}}_2$. The cryptanalysis of several modern ciphers reduces to this problem. Up to now, the best complexity bound was reached by an exhaustive search in 4_log2n2ⁿ$4{log}_{2}n{2}^n$ operations. We give an algorithm that reduces the problem to a combination of exhaustive search and sparse linear algebra. This algorithm has several variants depending on the method used for the linear algebra step. We show that, under precise algebraic assumptions on the input system, the deterministic variant of our algorithm has complexity bounded by O(2^0.841n)$O\left(2^{0.841n}\right)$ when m=n$m=n$, while a probabilistic variant of the Las Vegas type has expected complexity O(2^0.792n)$O\left(2^{0.792n}\right)$. Experiments on random systems show that the algebraic assumptions are satisfied with probability very close to 1. We also give a rough estimate for the actual threshold between our method and exhaustive search, which is as low as 200, and thus very relevant for cryptographic applications.     

Initial ideals of tangent cones to Schubert varieties in orthogonal Grassmannians

We compute the initial ideals, with respect to certain conveniently chosen term orders, of ideals of tangent cones at torus fixed points to Schubert varieties in orthogonal Grassmannians. The initial ideals turn out to be square-free monomial ideals and therefore define Stanley-Reisner face rings of simplicial complexes. We describe these complexes. The maximal faces of these complexes encode certain sets of non-intersecting lattice paths.     

Gröbner-Shirshov bases for the lie algebra <Emphasis Type="Italic">A</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

We estimate Gröbner-Shirshov bases for the Lie algebra A_n given arbitrary orders of generators (nodes of a Dynkin graph). Previously, the Gröbner-Shirshov basis was computed in [1] for the particular case where nodes of the Dynkin graph are ordered successively.Supported by RFBR grant Nos. 05-01-00230 and 02-01-00258 and by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools, project NSh-2069.2003.1.__________Translated from Algebra i Logika, Vol. 44, No. 2, pp. 131–147, March–April, 2005.     

An algebraic geometry algorithm for scheduling in presence of setups and correlated demands

We study here a problem of schedulingn job types onm parallel machines, when setups are required and the demands for the products are correlated random variables. We model this problem as a chance constrained integer program.Methods of solution currently available—in integer programming and stochastic programming—are not sufficient to solve this model exactly. We develop and introduce here a new approach, based on a geometric interpretation of some recent results in Gröbner basis theory, to provide a solution method applicable to a general class of chance constrained integer programming problems.Out algorithm is conceptually simple and easy to implement. Starting from a (possibly) infeasible solution, we move from one lattice point to another in a monotone manner regularly querying a membership oracle for feasibility until the optimal solution is found. We illustrate this methodology by solving a problem based on a real system.Corresponding author.     

On the Gröbner complexity of matrices

In this paper we show that if for an integer matrix A the universal Gröbner basis of the associated toric ideal I_A coincides with the Graver basis of A, then the Gröbner complexity u(A) and the Graver complexity g(A) of its higher Lawrence liftings agree, too. In fact, if the universal Gröbner basis of I_A coincides with the Graver basis of A, then also the more general complexities u(A,B) and g(A,B) agree for arbitrary B. We conclude that for the matrices A_3×3 and A_3×4, defining the 3×3 and 3×4 transportation problems, we have u(A_3×3)=g(A_3×3)=9 and u(A_3×4)=g(A_3×4)≥27. Moreover, we prove that u(A_a,b)=g(A_a,b)=2(a+b)/gcd(a,b) for positive integers a,b and .     

Test sets of integer programs

This article is a survey about recent developments in the area of test sets of families of linear integer programs. Test sets are finite subsets of the integer lattice that allow to improve any given feasible non-optimal point of an integer program by one element in the set. There are various possible ways of defining test sets depending on the view that one takes: theGraver test set is naturally derived from a study of the integral vectors in cones; theScarf test set (neighbors of the origin) is strongly connected to the study of lattice point free convex bodies; the so-calledreduced Gröbner basis of an integer program is obtained from a study of generators of polynomial ideals. This explains why the study of test sets connects various branches of mathematics. We introduce in this paper these three kinds of test sets and discuss relations between them. We also illustrate on various examples such as the minimum cost flow problem, the knapsack problem and the matroid optimization problem how these test sets may be interpreted combinatorially. From the viewpoint of integer programming a major interest in test sets is their relation to the augmentation problem. This is discussed here in detail. In particular, we derive a complexity result of the augmentation problem, we discuss an algorithm for solving the augmentation problem by computing the Graver test set and show that, in the special case of an integer knapsack problem with 3 coefficients, the augmentation problem can be solved in polynomial time.Supported by a Gerhard-Hess-Forschungsförderpreis of the German Science Foundation (DFG).     

On the existence and nonexistence of extremal metrics on toric Kähler surfaces

In this paper we study the existence of extremal metrics on toric Kähler surfaces. We show that on every toric Kähler surface, there exists a Kähler class in which the surface admits an extremal metric of Calabi. We found a toric Kähler surface of 9 -fixed points which admits an unstable Kähler class and there is no extremal metric of Calabi in it. Moreover, we prove a characterization of the K-stability of toric surfaces by simple piecewise linear functions. As an application, we show that among all toric Kähler surfaces with 5 or 6 -fixed points, is the only one which allows vanishing Futaki invariant and admits extremal metrics of constant scalar curvature.