Toric Initial Ideals of Δ-Normal Configurations: Cohen-Macaulayness and Degree Bounds

A normal (respectively, graded normal) vector configuration\({\cal A}\) defines the toric ideal \({I}_{\cal A}\) of a normal (respectively, projectively normal) toric variety. These ideals are Cohen-Macaulay, and when \({\cal A}\) is normal and graded, \({I}_{\cal A}\) is generated in degree at most the dimension of \({I}_{\cal A}\). Based on this, Sturmfels asked if these properties extend to initial ideals—when \({\cal A}\) is normal, is there an initial ideal of \({I}_{\cal A}\) that is Cohen-Macaulay, and when \({\cal A}\) is normal and graded, does \({I}_{\cal A}\) have a Gröbner basis generated in degree at most dim(\({I}_{\cal A}\)) ? In this paper, we answer both questions positively for Δ-normal configurations. These are normal configurations that admit a regular triangulation Δ with the property that the subconfiguration in each cell of the triangulation is again normal. Such configurations properly contain among them all vector configurations that admit a regular unimodular triangulation. We construct non-trivial families of both Δ-normal and non-Δ-normal configurations.     

Bases for Splines on a Subdivided Domain

Let S^r() be the module of all splines of smoothness r on the rectilinear partition which subdivides some domain D. Further, let S^r() be the module of all splines of smoothness r on which also subdivides D, where is a finer subdivision of . We study the relationship between a generating set of S^r() and a generating set for S^r(). This paper gives an algorithm for extending a generating set for S^r() to one for for S^r(). This method is built on algebraic properties of splines and the Gröbner Basis Algorithm.     

On the universal Gröbner bases of toric ideals of graphs

The universal Gröbner basis of an ideal is a Gröbner basis with respect to all term orders simultaneously. We characterize in graph theoretical terms the elements of the universal Gröbner basis of the toric ideal of a graph. We also provide a new degree bound. Finally, we give examples of graphs for which the true degrees of their circuits are less than the degrees of some elements of the Graver basis.     

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.     

Computing global minima to polynomial optimization problems using Gröbner bases

The local optimality conditions to polynomial optimization problems are a set of polynomial equations (plus some inequality conditions). With the recent techniques of Gröbner bases one can find all solutions to such systems, and hence also find global optima. We give a short survey of these methods. We also apply them to a set of problems termed with exact solutions unknown in the problem sets of Hock and Schittkowski. To these problems we give exact solutions.     

An algebraic approach to integer portfolio problems

Integer variables allow the treatment of some portfolio optimization problems in a more realistic way and introduce the possibility of adding some natural features to the model.     

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.     

Moduli Spaces of Curves with Quasi-Symmetric Weierstrass GAp Seqnences

In this paper we give an explicit construction of the moduli space of the pointed complete Gorenstein curves of arithmetic genus g with a given quasi-symmetric Weierstrass semigroup, that is, a Weierstrass semigroup whose last gap is equal to 2g – 2. We identify such a curve with its image under the canonical embedding in the (g – 1)-dimensional projective space. By normalizing the coefficients of the quadratic relations and by constructing Gröbner bases of the canonical ideal, we obtain the equations of the moduli space in terms of Buchberger's criterion. Moreover, by analyzing syzygies of the canonical ideal we establish criteria that make the computations less expensive.     

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.     

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 Flags and Gorenstein Algebras

The goal of this paper is to study the Koszul property and the property of having a Gröbner basis of quadrics for classical varieties and algebras as canonical curves, finite sets of points and Artinian Gorenstein algebras with socle in low degree. Our approach is based on the notion of Gröbner flags and Koszul filtrations. The main results are the existence of a Gröbner basis of quadrics for the ideal of the canonical curve whenever it is defined by quadrics, the existence of a Gröbner basis of quadrics for the defining ideal of s 2n points in general linear position in P ⁿ , and the Koszul property of the generic Artinian Gorenstein algebra of socle degree 3.     

Homological Computations in PBW Modules

In this paper the Poincaré–Birkhoff–Witt (PBW) rings are characterized. Gröbner bases techniques are also developed for these rings. An explicit presentation of Ext ⁱ (M,N) is provided when N is a centralizing bimodule.     

NON-COMMUTATIVE GRÖBNER BASES UNDER COMPOSITION

Polynomial composition is the operation of replacing the variables in a polynomial with other polynomials. In this paper we give sufficient and necessary conditions on a set Θ of non-commutative polynomials to assure that the set G ○ Θ of composed polynomials is a Gröbner basis in the free associative algebra whenever G is. The subject was initiated by Hong, treating the commutative analogue in (1998, J. Symb. Comput. 25, 643–663).     

Sequences of orthogonal Laurent polynomials,bi-orthogonality and quadrature formulas on the unit circle

In this paper, the construction of orthogonal bases in the space of Laurent polynomials on the unit circle is considered. As an application, a connection with the so-called bi-orthogonal systems of trigonometric polynomials is established and quadrature formulas on the unit circle based on Laurent polynomials are studied.     

AN ALGORITHM FOR DECOMPOSING ZERO-DIMENSIONAL POLYNOMIAL IDEALS

本文给出了一种不使用线性变换和ｖ．ｄ．Ｗａｅｒｄｅｎ的指数方法的零维多项式理想准素分解的新方法     

A Fitzpatrick algorithm for multivariate rational interpolation

In this paper, we first apply the Fitzpatrick algorithm to osculatory rational interpolation. Then based on a Fitzpatrick algorithm, we present a Neville-like algorithm for Cauchy interpolation. With this algorithm, we can determine the value of the interpolating function at a single point without computing the rational interpolating function.     

Gröbner Bases for Complete Uniform Families

We describe (reduced) Gröbner bases of the ideal of polynomials over a field, which vanish on the set of characterisic vectors of the complete unifom families . An interesting feature of the results is that they are largely independent of the monomial order selected. The bases depend only on the ordering of the variables. We can thus use past results related to the lex order in the presence of degree-compatible orders, such as deglex. As applications, we give simple proofs of some known results on incidence matrices.     

Global Minimization of a Multivariate Polynomial using Matrix Methods

The problem of minimizing a polynomial function in several variables over R ⁿ is considered and an algorithm is given. When the polynomial has a minimum the algorithm returns the global minimal value and finds at least one point in every connected component of the set of minimizers. A characterization of such points is given. When the polynomial does not have a minimum the algorithm computes its infimum. No assumption is made on the polynomial.