Markov bases and subbases for bounded contingency tables

In this paper we study the computation of Markov bases for contingency tables whose cell entries have an upper bound. It is known that in this case one has to compute universal Gröbner bases, and this is often infeasible also in small- and medium-sized problems. Here we focus on bounded two-way contingency tables under independence model. We show that when these bounds on cells are positive the set of basic moves of all 2 × 2 minors connects all tables with given margins. We also give some results about bounded incomplete table and we conclude with an open problem on the necessary and sufficient condition on the set of structural zeros so that the set of basic moves of all 2 × 2 minors connects all incomplete contingency tables with given positive margins.     

Some characterizations of minimal Markov basis for sampling from discrete conditional distributions

In this paper we given some basic characterizations of minimal Markov basis for a connected Markov chain, which is used for performing exact tests in discrete exponential families given a sufficient statistic. We also give a necessary and sufficient condition for uniqueness of minimal Markov basis. A general algebraic algorithm for constructing a connected Markov chain was given by Diaconis and Sturmfels (1998,The Annals of Statistics,26, 363–397). Their algorithm is based on computing Gröbner basis for a certain ideal in a polynomial ring, which can be carried out by using available computer algebra packages. However structure and interpretation of Gröbner basis produced by the packages are sometimes not clear, due to the lack of symmetry and minimality in Gröbner basis computation. Our approach clarifies partially ordered structure of minimal Markov basis.     

Invariant G2V algorithm for computing SAGBI-Gröbner bases

Faugère and Rahmany have presented the invariant F5 algorithm to compute SAGBI-Grbner bases of ideals of invariant rings. This algorithm has an incremental structure, and it is based on the matrix version of F5 algorithm to use F5 criterion to remove a part of useless reductions. Although this algorithm is more efficient than the Buchberger-like algorithm, however it does not use all the existing criteria (for an incremental structure) to detect superfluous reductions. In this paper, we consider a new algorithm, namely, invariant G2V algorithm, to compute SAGBI-Grbner bases of ideals of invariant rings using more criteria. This algorithm has a new structure and it is based on the G2V algorithm; a variant of the F5 algorithm to compute Grbner bases. We have implemented our new algorithm in Maple , and we give experimental comparison, via some examples, of performance of this algorithm with the invariant F5 algorithm.     

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.     

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.     

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.     

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.     

Parallel algorithms for Gröbner-basis construction

The problem of the Gröbner-basis construction is important both from the theoretical and applied points of view. As examples of applications of Gröbner bases, one can mention the consistency problem for systems of nonlinear algebraic equations and the determination of the number of solutions to a system of nonlinear algebraic equations. The Gröbner bases are actively used in the constructive theory of polynomial ideals and at the preliminary stage of numerical solution of systems of nonlinear algebraic equations. Unfortunately, many real examples cannot be processed due to the high computational complexity of known algorithms for computing the Gröbner bases. However, the efficiency of the standard basis construction can be significantly increased in practice. In this paper, we analyze the known algorithms for constructing the standard bases and consider some methods for increasing their efficiency. We describe a technique for estimating the efficiency of paralleling the algorithms and present some estimates.     

Parametrized Gröbner–Shirshov bases

We consider the problem of describing Gröbner–Shirshov bases for free associative algebras in finite terms. To this end we consider parametrized elements of an algebra and give methods for working with them which under favorable conditions lead to a basis given by finitely many patterns. On the negative side we show that in general there can be no algorithm. We relate our study to the problem of verifying that a given set of words in certain groups yields Bokut’ normal forms (or groups with a standard basis).     

Optimising Gröbner Bases on Bivium

Bivium is a reduced version of the stream cipher Trivium. In this paper we investigate how fast a key recovery attack on Bivium using Gröbner bases is. First we explain the attack scenario and the cryptographic background. Then we identify the factors that have impact on the computation time and show how to optimise them. As a side effect these experiments benchmark several Gröbner basis implementations. The optimised version of the Gröbner attack has an expected running time of 2^39.12 s, beating the attack time of our previous SAT solver attack by a factor of more than 330. Furthermore this approach is faster than an attack based on BDDs, an exhaustive key search, a generic time-memory trade-off attack and a guess-and-determine strategy.     

Permanental ideals of Hankel matrices

We provide the Gröbner basis and the primary decomposition of the ideals generated by 2 × 2 permanents of Hankel matrices.     

Smooth Wavelet Tight Frames with Zero Moments

This paper considers the design of wavelet tight frames based on iterated oversampled filter banks. The greater design freedom available makes possible the construction of wavelets with a high degree of smoothness, in comparison with orthonormal wavelet bases. In particular, this paper takes up the design of systems that are analogous to Daubechies orthonormal wavelets—that is, the design of minimal length wavelet filters satisfying certain polynomial properties, but now in the oversampled case. Gröbner bases are used to obtain the solutions to the nonlinear design equations. Following the dual-tree DWT of Kingsbury, one goal is to achieve near shift invariance while keeping the redundancy factor bounded by 2, instead of allowing it to grow as it does for the undecimated DWT (which is exactly shift invariant). Like the dual tree, the overcomplete DWT described in this paper is less shift-sensitive than an orthonormal wavelet basis. Like the examples of Chui and He, and Ron and Shen, the wavelets are much smoother than what is possible in the orthonormal case.     

Markov and Artin Normal Form Theorem for Braid Groups∗

In this article, we will present the results of Artin–Markov on braid groups by using the Gröbner–Shirshov basis. As a consequence, we can reobtain the normal form of Artin–Markov–Ivanovsky as an easy corollary.     

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.     

Toric rings generated by special stable sets of monomials

In this paper we consider some subalgebras of the d-th Veronese subring of a polynomial ring, generated by stable subsets of monomials. We prove that these algebras are Koszul, showing that the presentation ideals have Gröbner bases of quadrics with respect to suitable term orders. Since the initial monomials of the elements of these Gröbner bases are square- free, it follows by a result of STURMFELS [S, 13.15], that the algebras under consideration are normal, and thus Cohen-Macaulay.     

Gröbner basis and free resolution of the ideal of 2-minors of a 2 × n matrix of linear forms *

We give a Gröbner basis for the ideal of 2-minors of a 2 × n utiatrix of linear forms. The minimal free resolution of such an ideal is obtained in [4] when the corresponding Kronecker-Weierstrass normal form has no iiilpotent blocks. For the general case, using this result, the Grobner basis and the Eliahou-Kervaire resolution for stable monomial ideals, we obtain a free resolution with the expected regularity. For a specialization of the defining ideal of ordinary pinch points, as a special case of these ideals, we provide a minimal free resolution explicitly in terms of certain Koszul complex.     

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 basis for the Braid group in the Birman–Ko–Lee generators

In this paper, we obtain Gröbner–Shirshov (non-commutative Gröbner) bases for braid groups in the Birman–Ko–Lee generators enriched by “Garside word” δ [J. Birman, K.H. Ko, S.J. Lee, A new approach to the word and conjugacy problems for the braid groups, Adv. Math. 139 (1998) 322–353]. It gives a new algorithm for getting the Birman–Ko–Lee normal forms in braid groups, and thus a new algorithm for solving the word problem in these groups.