Minimal invariant Markov basis for sampling contingency tables with fixed marginals

In this paper we define an invariant Markov basis for a connected Markov chain over the set of contingency tables with fixed marginals and derive some characterizations of minimality of the invariant basis. We also give a necessary and sufficient condition for uniqueness of minimal invariant Markov bases. By considering the invariance, Markov bases can be presented very concisely. As an example, we present minimal invariant Markov bases for all 2 × 2 × 2 × 2 hierarchical models. The invariance here refers to permutation of indices of each axis of the contingency tables. If the categories of each axis do not have any order relations among them, it is natural to consider the action of the symmetric group on each axis of the contingency table. A general algebraic algorithm for obtaining a Markov basis was given by Diaconis and Sturmfels (The Annals of Statistics, 26, 363–397, 1998). Their algorithm is based on computing Gröbner basis of a well-specified polynomial ideal. However, the reduced Gröbner basis depends on the particular term order and is not symmetric. Therefore, it is of interest to consider the properties of invariant Markov basis.     

On the Connection Between Ritt Characteristic Sets and Buchberger–Gröbner Bases

For any polynomial ideal \(\mathcal {I}\), let the minimal triangular set contained in the reduced Buchberger–Gröbner basis of \(\mathcal {I}\) with respect to the purely lexicographical term order be called the W-characteristic set of \(\mathcal {I}\). In this paper, we establish a strong connection between Ritt’s characteristic sets and Buchberger’s Gröbner bases of polynomial ideals by showing that the W-characteristic set \(\mathbb {C}\) of \(\mathcal {I}\) is a Ritt characteristic set of \(\mathcal {I}\) whenever \(\mathbb {C}\) is an ascending set, and a Ritt characteristic set of \(\mathcal {I}\) can always be computed from \(\mathbb {C}\) with simple pseudo-division when \(\mathbb {C}\) is regular. We also prove that under certain variable ordering, either the W-characteristic set of \(\mathcal {I}\) is normal, or irregularity occurs for the jth, but not the \((j+1)\)th, elimination ideal of \(\mathcal {I}\) for some j. In the latter case, we provide explicit pseudo-divisibility relations, which lead to nontrivial factorizations of certain polynomials in the Buchberger–Gröbner basis and thus reveal the structure of such polynomials. The pseudo-divisibility relations may be used to devise an algorithm to decompose arbitrary polynomial sets into normal triangular sets based on Buchberger–Gröbner bases computation.     

Graph representation of projective resolutions

We generalize the concept — dimension tree and the related results for monomial algebras to a more general case — relations algebras Λ by bringing Gröbner basis into play. More precisely, we will describe the minimal projective resolution of a left Λ-module M as a rooted ‘weighted’ diagraph to be called the minimal resolution graph for M. Algorithms for computing such diagraphs and applications as well will be presented.     

Recurrence Formulas for Kostka and Inverse Kostka Numbers via Quantum Cohomology of Grassmannians

A Gröbner basis for the small quantum cohomology of Grassmannian G _k,n is constructed and used to obtain new recurrence relations for Kostka numbers and inverse Kostka numbers. Using these relations it is shown how to determine inverse Kostka numbers which are related to the mod-p Wu formula.     

Specifying periodic words by restrictions

Consider a periodic sequence over a finite alphabet, say ..ababab.... This sequence can be specified by prohibiting the subwords aa and bb. In the paper, the maximum period of a word that can be defined by using k restrictions is determined. A sharp exponential bound is obtained: the period of a word determined by k restrictions cannot exceed the kth Fibonacci number. Thus, the period colength is estimated. The problem is studied in the context of Gröbner bases, namely, the growth of a Gröbner basis of an ideal (the cogrowth of an algebra). The proof uses the technique of Rauzy graphs.     

On the robust hardness of Gröbner basis computation

The computation of Gröbner bases is an established hard problem. By contrast with many other problems, however, there has been little investigation of whether this hardness is robust. In this paper, we frame and present results on the problem of approximate computation of Gröbner bases. We show that it is NP-hard to construct a Gröbner basis of the ideal generated by a set of polynomials, even when the algorithm is allowed to discard a $1??$ fraction of the generators, and likewise when the algorithm is allowed to discard variables (and the generators containing them). Our results show that computation of Gröbner bases is robustly hard even for simple polynomial systems (e.g. maximum degree 2, with at most 3 variables per generator). We conclude by greatly strengthening results for the Strong c-Partial Gröbner problem posed by De Loera et al. [10]. Our proofs also establish interesting connections between the robust hardness of Gröbner bases and that of SAT variants and graph-coloring.     

Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals

For an ideal I??[x] given by a set of generators, a new semidefinite characterization of its real radical I(V _?(I)) is presented, provided it is zero-dimensional (even if I is not). Moreover, we propose an algorithm using numerical linear algebra and semidefinite optimization techniques, to compute all (finitely many) points of the real variety V _?(I) as well as a set of generators of the real radical ideal. The latter is obtained in the form of a border or Gröbner basis. The algorithm is based on moment relaxations and, in contrast to other existing methods, it exploits the real algebraic nature of the problem right from the beginning and avoids the computation of complex components.     

Gröbner bases of characteristic ideals of LRS over UFD

LetR be a unique factorization domain (UFD). A method of Gröbner bases and localization in commutative algebra is applied to compute and analyze the characteristic ideals of semi-infinite linear recurring sequences (lrs), infinite linear recurring sequences (LRS), and finite lrs over UFD. The canonical form of a minimal Gröbner basis of the homogeneous characteristic ideal is described for a finite segment of an lrs, from which a precise relation between every step in the classical Berlekamp-Massey algorithm and every member of the Gröbner basis is derived.     

The Gröbner ring conjecture in the lexicographic order case

We prove that a valuation domain $\mathbf{V}$ has Krull dimension $\le $ 1 if and only if, for any $n$ , fixing the lexicographic order as monomial order in $\mathbf{V}[X_1,\ldots ,X_n]$ , for every finitely generated ideal $I$ of $\mathbf{V}[X_1,\ldots ,X_n]$ , the ideal generated by the leading terms of the elements of $I$ is also finitely generated. This proves the Gröbner ring conjecture in the lexicographic order case. The proof we give is both simple and constructive. The same result is valid for Prüfer domains. As a “scoop”, contrary to the common idea that Gröbner bases can be computed exclusively on Noetherian ground, we prove that computing Gröbner bases over $\mathbf{R}[X_1,\ldots , X_n]$ , where $\mathbf{R}$ is a Prüfer domain, has nothing to do with Noetherianity, it is only related to the fact that the Krull dimension of $\mathbf{R}$ is $\le $ 1.     

W-Gröbner basis and monomial ideals under polynomial composition

The notion of weakly relatively prime and W-Gröbner basis in K[x ₁, x ₂, …, x _n ] are given. The following results are obtained: for polynomials f ₁, f ₂, …, f _m , \(\{ f_1^{\lambda _1 } ,f_2^{\lambda _2 } ,...,f_m^{\lambda _m } \} \) is a Gröbner basis if and only if f ₁, f ₂, …, f _m are pairwise weakly relatively prime with λ ₁, λ ₂, …, λ _m arbitrary non-negative integers; polynomial composition by Θ = (θ ₁, θ ₂, …, θ _n ) commutes with monomial-Gröbner bases computation if and only if θ ₁, θ ₂, …, θ _m are pairwise weakly relatively prime.     

Computing Final Polynomials and Final Syzygies Using Buchberger’s Gröbner Bases Method

Final polynomials and final syzygies provide an explicit representation of polynomial identities promised by Hilbert’s Nullstellensatz. Such representations have been studied independently by Bokowski [2,3,4] and Whiteley [23,24] to derive invariant algebraic proofs for statements in geometry. In the present paper we relate these methods to some recent developments in computational algebraic geometry. As the main new result we give an algorithm based on B. Buchberger’s Gröbner bases method for computing final polynomials and final syzygies over the complex numbers. Degree upper bound for final polynomials are derived from theorems of Lazard and Brownawell, and a topological criterion is proved for the existence of final syzygies. The second part of this paper is expository and discusses applications of our algorithm to real projective geometry, invariant theory and matrix theory.     

On noncommutative Gröbner bases over rings

Let R be a commutative ring. It is proved that for verification of whether a set of elements {f _α} of the free associative algebra over R is a Gröbner basis (with respect to some admissible monomial order) of the (bilateral) ideal that the elements f _α generate it is sufficient to check the reducibility to zero of S-polynomials with respect to {f _α} iff R is an arithmetical ring. Some related open questions and examples are also discussed.     

Variation of cost functions in integer programming

We study the problem of minimizingc · x subject toA · x =b. x ≥ 0 andx integral, for a fixed matrixA. Two cost functionsc andc′ are considered equivalent if they give the same optimal solutions for eachb. We construct a polytopeSt(A) whose normal cones are the equivalence classes. Explicit inequality presentations of these cones are given by the reduced Gröbner bases associated withA. The union of the reduced Gröbner bases asc varies (called the universal Gröbner basis) consists precisely of the edge directions ofSt(A). We present geometric algorithms for computingSt(A), the Graver basis, and the universal Gröbner basis.     

Local properties of Richardson varieties in the Grassmannian via a bounded Robinson-Schensted-Knuth correspondence

The Richardson variety X _α ^γ in the Grassmannian is defined to be the intersection of the Schubert variety X ^γ and opposite Schubert variety X _α . We give an explicit Gröbner basis for the ideal of the tangent cone at any T-fixed point of X _α ^γ , thus generalizing a result of Kodiyalam-Raghavan (J. Algebra 270(1):28–54, 2003) and Kreiman-Lakshmibai (Algebra, Arithmetic and Geometry with Applications, 2004). Our proof is based on a generalization of the Robinson-Schensted-Knuth (RSK) correspondence, which we call the bounded RSK (BRSK). We use the Gröbner basis result to deduce a formula which computes the multiplicity of X _α ^γ at any T-fixed point by counting families of nonintersecting lattice paths, thus generalizing a result first proved by Krattenthaler (Sém. Lothar. Comb. 45:B45c, 2000/2001; J. Algebr. Comb. 22:273–288, 2005).     

Gröbner Bases for Ideals of σ-PBW Extensions

In this article, we introduce the σ-PWB extensions and construct the theory of Gröbner bases for the left ideals of them. We prove the Hilbert's basis theorem and the division algorithm for this more general class of Poincaré–Birkhoff–Witt extensions. For the particular case of bijective and quasi-commutative σ-PWB extensions, we implement the Buchberger's algorithm for computing Gröbner bases of left ideals.     

Standard bases concordant with the norm and computations in ideals and polylinear recurring sequences

Standard bases of ideals of the polynomial ring R[X] = R[x ₁, …, x _k ] over a commutative Artinian chain ring R that are concordant with the norm on R have been investigated by D. A. Mikhailov, A. A. Nechaev, and the author. In this paper we continue this investigation. We introduce a new order on terms and a new reduction algorithm, using the coordinate decomposition of elements from R. We prove that any ideal has a unique reduced (in terms of this algorithm) standard basis. We solve some classical computational problems: the construction of a set of coset representatives, the finding of a set of generators of the syzygy module, the evaluation of ideal quotients and intersections, and the elimination problem. We construct an algorithm testing the cyclicity of an LRS-family L _R (I), which is a generalization of known results to the multivariate case. We present new conditions determining whether a Ferre diagram $\mathcal{F}$ and a full system of $\mathcal{F}$ -monic polynomials form a shift register. On the basis of these results, we construct an algorithm for lifting a reduced Gröbner basis of a monic ideal to a standard basis with the same cardinality.     

Relative Reduction and Buchberger’s Algorithm in Filtered Free Modules

In this paper we develop a relative Gröbner basis method for a wide class of filtered modules. Our general setting covers the cases of modules over rings of differential, difference, inversive difference and difference–differential operators, Weyl algebras and multiparameter twisted Weyl algebras (the last class of rings includes the classes of quantized Weyl algebras and twisted generalized Weyl algebras). In particular, we obtain a Buchberger-type algorithm for constructing relative Gröbner bases of filtered free modules.     

Cyclotomic Hecke Algebras of <Emphasis Type="Italic">G</Emphasis>(<Emphasis Type="Italic">r</Emphasis>, <Emphasis Type="Italic">p</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)

In this note, we find a monomial basis of the cyclotomic Hecke algebra \({\mathcal{H}_{r,p,n}}\) of G(r,p,n) and show that the Ariki-Koike algebra \({\mathcal{H}_{r,n}}\) is a free module over \({\mathcal{H}_{r,p,n}}\), using the Gröbner-Shirshov basis theory. For each irreducible representation of \({\mathcal{H}_{r,p,n}}\), we give a polynomial basis consisting of linear combinations of the monomials corresponding to cozy tableaux of a given shape.     

Distributive Lattices,Bipartite Graphs and Alexander Duality

A certain squarefree monomial ideal H _P arising from a finite partially ordered set P will be studied from viewpoints of both commutative algbera and combinatorics. First, it is proved that the defining ideal of the Rees algebra of H _P possesses a quadratic Gröbner basis. Thus in particular all powers of H _P have linear resolutions. Second, the minimal free graded resolution of H _P will be constructed explicitly and a combinatorial formula to compute the Betti numbers of H _P will be presented. Third, by using the fact that the Alexander dual of the simplicial complex Δ whose Stanley–Reisner ideal coincides with H _P is Cohen–Macaulay, all the Cohen–Macaulay bipartite graphs will be classified.     

An efficient algorithm for factoring polynomials over algebraic extension field

An efficient algorithm is proposed for factoring polynomials over an algebraic extension field defined by a polynomial ring modulo a maximal ideal. If the maximal ideal is given by its Gröbner basis, no extra Gröbner basis computation is needed for factoring a polynomial over this extension field. Nothing more than linear algebraic technique is used to get a characteristic polynomial of a generic linear map. Then this polynomial is factorized over the ground field. From its factors, the factorization of the polynomial over the extension field is obtained. The algorithm has been implemented in Magma and computer experiments indicate that it is very efficient, particularly for complicated examples.