Minimised Geometric Buchberger Algorithm for Integer Programming

Recently, various algebraic integer programming (IP) solvers have been proposed based on the theory of Gröbner bases. The main difficulty of these solvers is the size of the Gröbner bases generated. In algorithms proposed so far, large Gröbner bases are generated by either introducing additional variables or by considering the generic IP problem IP _A,C . Some improvements have been proposed such as Hosten and Sturmfels' method (GRIN) designed to avoid additional variables and Thomas' truncated Gröbner basis method which computes the reduced Gröbner basis for a specific IP problem IP _A,C (b) (rather than its generalisation IP _A,C ). In this paper we propose a new algebraic algorithm for solving IP problems. The new algorithm, called Minimised Geometric Buchberger Algorithm, combines Hosten and Sturmfels' GRIN and Thomas' truncated Gröbner basis method to compute the fundamental segments of an IP problem IP _A,C directly in its original space and also the truncated Gröbner basis for a specific IP problem IP _A,C (b). We have carried out experiments to compare this algorithm with others such as the geometric Buchberger algorithm, the truncated geometric Buchberger algorithm and the algorithm in GRIN. These experiments show that the new algorithm offers significant performance improvement.     

New developments in the theory of Gröbner bases and applications to formal verification

We present foundational work on standard bases over rings and on Boolean Gröbner bases in the framework of Boolean functions. The research was motivated by our collaboration with electrical engineers and computer scientists on problems arising from formal verification of digital circuits. In fact, algebraic modelling of formal verification problems is developed on the word-level as well as on the bit-level. The word-level model leads to Gröbner basis in the polynomial ring over Z/2ⁿ while the bit-level model leads to Boolean Gröbner bases. In addition to the theoretical foundations of both approaches, the algorithms have been implemented. Using these implementations we show that special data structures and the exploitation of symmetries make Gröbner bases competitive to state-of-the-art tools from formal verification but having the advantage of being systematic and more flexible.     

Computations in differential and difference modules

Constructive methods based on the Gröbner bases theory have been used many times in commutative algebra over the past 20 years, in particular, they allow the computation of such important invariants of manifolds given by systems of algebraic equations as their Hilbert polynomials. In differential and difference algebra, the analogous roles play characteristic sets.In this paper, algorithms for computations in differential and difference modules, which allow for the computation of characteristic sets (Gröbner bases) in differential, difference, and polynomial modules and differential (difference) dimension polynomials, are described. The algorithms are implemented in the algorithmic language REFAL.     

Integral Schur algebras forGL 2

The structure of Schur algebrasS(2,r) over the integral domainZ is intensively studied from the quasi-hereditary algebra point of view. We introduce certain new bases forS(2,r) and show that the Schur algebraS(2,r) modulo any ideal in the defining sequence is still such a Schur algebra of lower degree inr. A Wedderburn-Artin decomposition ofS _K (2,r) over a fieldK of characteristic 0 is described. Finally, we investigate the extension groups between two Weyl modules and classify the indecomposable Weyl-filtered modules for the Schur algebrasS _Zp(2,r) withr<p ² . Research supported by ARC Large Grant L20.24210     

Group actions and Helly's theorem

We describe a connection between the combinatorics of generators for certain groups and the combinatorics of Helly's 1913 theorem on convex sets. We use this connection to prove fixed point theorems for actions of these groups on nonpositively curved metric spaces. These results are encoded in a property that we introduce called “property FAr”, which reduces to Serre's property FA when r=1. The method applies to S-arithmetic groups in higher Q-rank, to simplex reflection groups (including some nonarithmetic ones), and to higher rank Chevalley groups over polynomial and other rings (for example SLn(Z[x₁,…,xd]), n>2).     

Enumeration of non-crossing pairings on bit strings

A non-crossing pairing on a bit string is a matching of 1s and 0s in the string with the property that the pairing diagram has no crossings. For an arbitrary bit-string w=p₁¹q₁⁰…pr¹qr⁰, let φ(w) be the number of such pairings. This enumeration problem arises when calculating moments in the theory of random matrices and free probability, and we are interested in determining useful formulas and asymptotic estimates for φ(w). Our main results include explicit formulas in the “symmetric” case where each pi=qi, as well as upper and lower bounds for φ(w) that are uniform across all words of fixed length and fixed r. In addition, we offer more refined conjectural expressions for the upper bounds. Our proofs follow from the construction of combinatorial mappings from the set of non-crossing pairings into certain generalized “Catalan” structures that include labeled trees and lattice paths.     

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.     

On replacement axioms for the Jacobi identity for vertex algebras and their modules

We discuss the axioms for vertex algebras and their modules, using formal calculus. Following certain standard treatments, we take the Jacobi identity as our main axiom and we recall weak commutativity and weak associativity. We derive a third companion property that we call “weak skew-associativity”. This third property in some sense completes an S₃-symmetry of the axioms, which is related to the known S₃-symmetry of the Jacobi identity. We do not initially require a vacuum vector, which is analogous to not requiring an identity element in ring theory. In this more general setting, one still has a property, occasionally used in standard treatments, which is closely related to skew-symmetry, which we call “vacuum-free skew-symmetry”. We show how certain combinations of these properties are equivalent to the Jacobi identity for both vacuum-free vertex algebras and their modules. We then specialize to the case with a vacuum vector and obtain further replacement axioms. In particular, in the final section we derive our main result, which says that, in the presence of certain minor axioms, the Jacobi identity for a module is equivalent to either weak associativity or weak skew-associativity. The first part of this result has appeared previously and has been used to show the (nontrivial) equivalence of representations of and modules for a vertex algebra. Many but not all of our results appear in standard treatments; some of our arguments are different from the usual ones.     

Computing border bases

This paper presents several algorithms that compute border bases of a zero-dimensional ideal. The first relates to the FGLM algorithm as it uses a linear basis transformation. In particular, it is able to compute border bases that do not contain a reduced Gröbner basis. The second algorithm is based on a generic algorithm by Bernard Mourrain originally designed for computing an ideal basis that need not be a border basis. Our fully detailed algorithm computes a border basis of a zero-dimensional ideal from a given set of generators. To obtain concrete instructions we appeal to a degree-compatible term ordering σ and hence compute a border basis that contains the reduced σ-Gröbner basis. We show an example in which this computation actually has advantages over Buchberger's algorithm. Moreover, we formulate and prove two optimizations of the Border Basis Algorithm which reduce the dimensions of the linear algebra subproblems.     

On the prediction of vector-valued random fields and the spectral distribution of their evanescent component

Let (X_m,n)_(m,n)∈Z² be a C^p-valued wide sense stationary process. We study the prediction theory of such processes according to different total orders on Z². In the case of a “rational order”, we give the spectral distribution of the resulting evanescent component and prove that for two different rational orders, the resulting evanescent components are mutually orthogonal.     

When Does a Submodule of (ℝ[x 1 ⋯, x k]) n Contain a Positive Element?

We characterize for modules consisting of tuples of Laurent polynomials with real coefficients whether such a module contains a positive element. The two conditions needed are numerical and directional positivity. The proof applies universal Gröbner bases.     

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.     

Equidimensionality of convolution morphisms and applications to saturation problems

Fix a split connected reductive group G over a field k, and a positive integer r. For any r-tuple of dominant coweights μi of G, we consider the restriction mμ_• of the r-fold convolution morphism of Mirkovic-Vilonen to the twisted product of affine Schubert varieties corresponding to μ_•. We show that if all the coweights μi are minuscule, then the fibers of mμ_• are equidimensional varieties, with dimension the largest allowed by the semi-smallness of mμ_•. We derive various consequences: the equivalence of the non-vanishing of Hecke and representation ring structure constants, and a saturation property for these structure constants, when the coweights μi are sums of minuscule coweights. This complements the saturation results of Knutson-Tao and Kapovich-Leeb-Millson. We give a new proof of the P-R-V conjecture in the “sums of minuscules” setting. Finally, we generalize and reprove a result of Spaltenstein pertaining to equidimensionality of certain partial Springer resolutions of the nilpotent cone for GLn.     

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 .     

Applying Gröbner basis techniques to group theory

We apply the machinery of Gröbner bases to finitely presented groups. This allows for computational methods to be developed which prove that a given finitely presented group is not n-linear over a field k assuming some mild conditions. We also present an algorithm which determines whether or not a finitely presented group G is trivial given that an oracle has told us that G is n-linear over an algebraically closed field k.     

Locally finite polynomial endomorphisms

We study polynomial endomorphisms F of C^N which are locally finite in the following sense: the vector space generated by r°Fⁿ (n≥0) is finite dimensional for each r∈C[x₁,…,x_N]. We show that such endomorphisms exhibit similar features to linear endomorphisms: they satisfy the Jacobian Conjecture, have vanishing polynomials, admit suitably defined minimal and characteristic polynomials, and the invertible ones admit a Dunford decomposition into “semisimple” and “unipotent” constituents. We also explain a relationship with linear recurrent sequences and derivations. Finally, we give particular attention to the special cases where F is nilpotent and where N=2.     

The symmetric group given by a Gröbner basis

We present a Gröbner basis associated with the symmetric group of degree n, which is determined by a strong generating set of the symmetric group and is defined by means of a term ordering with the elimination property.     

Gate points in continuous location between regions with different ?p norms

In this paper, a set of notable points is given from the ?_p-distance between a point P and a straight line r. The problem of the geodesic path between two points of R² separated by a straight line r with different norms in each half-plane is then studied from the notable points of these points. This geodesic path provides a point in r, called the “Gate point”, which is studied by varying ?_p- and ?_q-distances, and the slope m of the straight line r. The analytical expression of the Gate point is given in some particular cases.     

Factoring Polynomials over Special Finite Fields

We exhibit a deterministic algorithm for factoring polynomials in one variable over finite fields. It is efficient only if a positive integer k is known for which Φ_k(p) is built up from small prime factors; here Φ_k denotes the kth cyclotomic polynomial, and p is the characteristic of the field. In the case k=1, when Φ_k(p)=p−1, such an algorithm was known, and its analysis required the generalized Riemann hypothesis. Our algorithm depends on a similar, but weaker, assumption; specifically, the algorithm requires the availability of an irreducible polynomial of degree r over Z/pZ for each prime number r for which Φ_k(p) has a prime factor l with l≡1 mod r. An auxiliary procedure is devoted to the construction of roots of unity by means of Gauss sums. We do not claim that our algorithm has any practical value.