Search

Assume that we are given a sequence F of k homogeneous polynomials in n variables of degree at most d and the ideal ℐ generated by this sequence. The aim of this paper is to present a new and effective method to determine, within the arithmetic complexity d O (n) , whether F is regular. This algorithm has been implemented in Maple and its efficiency (compared to the classical approaches for regular sequence test) is evaluated via a set of benchmark polynomials. Furthermore, we show that if F is regular then we can transform ℐ into Nœther position and at the same time compute a reduced Gröbner basis for the transformed ideal within the arithmetic complexity d O (n 2) . Finally, under the same assumption, we establish the new upper bound 2 (d k / 2) 2 n − k − 1 for the maximum degree of the elements of any reduced Gröbner basis of ℐ in the case that n > k. [ABSTRACT FROM AUTHOR]

Considering a multivariate polynomial ideal over a given field as a vector space, we investigate for such an ideal a particular linear basis, a so-called staggered linear basis, which contains a Gröbner basis as well. In this paper, we present a simple and efficient algorithm to compute a staggered linear basis. The new framework is equipped with some novel criteria (including both Buchberger's criteria) to detect superfluous reductions. The proposed algorithm has been implemented in Maple, and we provide an illustrative example to show how it works. Finally, the efficiency of this algorithm compared to the existing methods is discussed via a set of benchmark polynomials. [ABSTRACT FROM AUTHOR]

In the nonlinear field of multilinear operators and homogeneous polynomials between Banach spaces, we develop a technique, based on the transformation of vector-valued sequences, to create new examples of hyper-ideals of multilinear operators, polynomial hyper-ideals and polynomial two-sided ideals. Several well-studied ideals are shown to be actually hyper-ideals or two-sided ideals. [ABSTRACT FROM AUTHOR]

We prove that equivalence of deterministic top-down tree-to-string transducers is decidable, thus solving a long-standing open problem in formal language theory. We also present efficient algorithms for subclasses: for linear transducers or total transducers with unary output alphabet (over a given top-down regular domain language), as well as for transducers with the single-use restriction. These results are obtained using techniques from multi-linear algebra. For our main result, we introduce polynomial transducers and prove that for these, validity of a polynomial invariant can be certified by means of an inductive invariant of polynomial ideals. This allows us to construct two semi-algorithms, one searching for a certificate of the invariant and one searching for a witness of its violation. Via a translation into polynomial transducers, we thus obtain that equivalence of general ydt transducers is decidable. In fact, our translation also shows that equivalence is decidable when the output is not in a free monoid but in a free group. [ABSTRACT FROM AUTHOR]

Generalizing a number of known linear and nonlinear results, we establish conditions for the space of linear operators belonging to a given operator ideal not to be complemented in the space of bounded linear operators, and for the space of n-homogeneous polynomials belonging to a given polynomial ideal not to be complemented in the space of continuous n-homogeneous polynomials. Illustrative examples are provided. [ABSTRACT FROM AUTHOR]

In this paper, following the approach by Dubé (1990) and by applying the Hilbert series method, we provide an efficient algorithm to compute the Macaulay constants of the quotient ring of a monomial ideal without computing any exact cone decomposition for the quotient ring. Then, based on this construction and the method proposed by Mayr and Ritscher (2013) , a new upper bound for the maximum degree of the elements of any reduced Gröbner basis of an ideal generated by a set of homogeneous polynomials is given. The new bound depends on the Krull dimension and the maximum degree of the generating set of the ideal. Finally, we show that the presented upper bound is sharper than the bounds proposed by Dubé (1990) and Mayr and Ritscher (2013). [ABSTRACT FROM AUTHOR]

We study extensions of compressive sensing and low rank matrix recovery to the recovery of tensors of low rank from incomplete linear information. While the reconstruction of low rank matrices via nuclear norm minimization is rather well-understand by now, almost no theory is available so far for the extension to higher order tensors due to various theoretical and computational difficulties arising for tensor decompositions. In fact, nuclear norm minimization for matrix recovery is a tractable convex relaxation approach, but the extension of the nuclear norm to tensors is in general NP-hard to compute. In this article, we introduce convex relaxations of the tensor nuclear norm which are computable in polynomial time via semidefinite programming. Our approach is based on theta bodies, a concept from real computational algebraic geometry which is similar to the one of the better known Lasserre relaxations. We introduce polynomial ideals which are generated by the second-order minors corresponding to different matricizations of the tensor (where the tensor entries are treated as variables) such that the nuclear norm ball is the convex hull of the algebraic variety of the ideal. The theta body of order k for such an ideal generates a new norm which we call the θk-norm. We show that in the matrix case, these norms reduce to the standard nuclear norm. For tensors of order three or higher however, we indeed obtain new norms. The sequence of the corresponding unit-θk-norm balls converges asymptotically to the unit tensor nuclear norm ball. By providing the Gröbner basis for the ideals, we explicitly give semidefinite programs for the computation of the θk-norm and for the minimization of the θk-norm under an affine constraint. Finally, numerical experiments for order-three tensor recovery via θ1-norm minimization suggest that our approach successfully reconstructs tensors of low rank from incomplete linear (random) measurements. [ABSTRACT FROM AUTHOR]

The aim of this paper is to investigate upper bounds for the maximum degree of the elements of any minimal Janet basis of an ideal generated by a set of homogeneous polynomials. The presented bounds depend on the number of variables and the maximum degree of the generating set of the ideal. For this purpose, by giving a deeper analysis of the method due to Dubé (SIAM J Comput 19:750–773, 1990), we improve (and correct) his bound on the degrees of the elements of a reduced Gröbner basis. By giving a simple proof, it is shown that this new bound is valid for Pommaret bases, as well. Furthermore, based on Dubé's method, and by introducing two new notions of genericity, so-called J-stable position and prime position, we show that Dubé's (new) bound holds also for the maximum degree of polynomials in any minimal Janet basis of a homogeneous ideal in any of these positions. Finally, we study the introduced generic positions by proposing deterministic algorithms to transform any given homogeneous ideal into these positions. [ABSTRACT FROM AUTHOR]

We present an effective method to compute the resolution regularity (vector) of bi-homogeneous ideals. For this purpose, we first introduce the new notion of an x-Pommaret basis and describe an algorithm to compute a linear change of coordinates for a given bi-homogeneous ideal such that the new ideal obtained after performing this change possesses a finite x -Pommaret basis. Then, we show that the x -component of the bi-graded regularity of a bi-homogeneous ideal is equal to the x -degree of its x -Pommaret basis (after performing the mentioned linear change of variables). Finally, we introduce the new notion of an ideal in x-quasi stable position and show that a bi-homogeneous ideal has a finite x -Pommaret basis iff it is in x -quasi stable position. [ABSTRACT FROM AUTHOR]

The classical coinvariant ring R n is defined as the quotient of a polynomial ring in n variables by the positive-degree S n -invariants. It has a known basis that respects the decomposition of R n into irreducible S n -modules, consisting of the higher Specht polynomials due to Ariki, Terasoma, and Yamada (Hiroshima Math J 27(1):177–188, 1997). We provide an extension of the higher Specht basis to the generalized coinvariant rings R n , k introduced in Haglund et al. (Adv Math 329:851–915, 2018). We also give a conjectured higher Specht basis for the Garsia–Procesi modules R μ , and we provide a proof of the conjecture in the case of two-row partition shapes μ . We then combine these results to give a higher Specht basis for an infinite subfamily of the modules R n , k , μ recently defined by Griffin (Trans Amer Math Soc, to appear, 2020), which are a common generalization of R n , k and R μ . [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of transforming an ideal into normal position. We present a deterministic algorithm (based on linear algebra techniques) that finds a suitable linear change of variables to transform a given zero-dimensional (not necessarily radical) ideal into normal position. The main idea of this algorithm is to achieve this position via a sequence of elementary linear changes; i.e. each change involves only two variables. Furthermore we give complete complexity analysis of all the algorithms described in this paper based on a sharp upper bound for the maximal number of required elementary linear changes in the special case of the bi-variate polynomial ideal. As an application of this investigation, we conclude the paper by giving a sharper complexity bound for computing a primary decomposition for a zero-dimensional ideal. [ABSTRACT FROM AUTHOR]

After sketching the basic theory of injective ideals of homogeneous polynomials, we characterize injective polynomial ideals by means of a domination property and applications of this characterization to some classical operator ideals and to composition polynomial ideals are provided. [ABSTRACT FROM AUTHOR]

We provide a general method for identifying real quadratic polynomial dynamical systems that can be transformed to symmetric ones by a bijective polynomial map of degree one, the so-called affine map. We mainly focus on symmetry groups generated by rotations, in other words, we treat equivariant and reversible equivariant systems. The description is given in terms of affine varieties in the space of parameters of the system. A general algebraic approach to find subfamilies of systems having certain symmetries in polynomial differential families depending on many parameters is proposed and computer algebra computations for the planar case are presented.

Source localization and spectral estimation are among the most fundamental problems in statistical and array signal processing. Methods that rely on the orthogonality of the signal and noise subspaces, such as Pisarenko's method, MUSIC, and root-MUSIC, are some of the most widely used algorithms to solve these problems. As a common feature, these methods require both a priori knowledge of the number of sources and an estimate of the noise subspace. Both requirements are complicating factors to the practical implementation of the algorithms and, when not satisfied exactly, can potentially lead to severe errors. In this paper, we propose a new localization criterion based on the algebraic structure of the noise subspace that is described for the first time to the best of our knowledge. Using this criterion and the relationship between the source localization problem and the problem of computing the greatest common divisor (GCD), or more practically approximate GCD, for polynomials, we propose two algorithms, which adaptively learn the number of sources and estimate their locations. Simulation results show a significant improvement over root-MUSIC in challenging scenarios such as closely located sources, both in terms of detection of the number of sources and their localization over a broad and practical range of signal-to-noise ratios. Furthermore, no performance sacrifice in simple scenarios is observed. [ABSTRACT FROM AUTHOR]

In this paper, we study first the relationship between Pommaret bases and Hilbert series. Given a finite Pommaret basis, we derive new explicit formulas for the Hilbert series and for the degree of the ideal generated by it which exhibit more clearly the influence of each generator. Then we establish a new dimension depending Bézout bound for the degree and use it to obtain a dimension depending bound for the ideal membership problem. [ABSTRACT FROM AUTHOR]

We consider several notions of genericity appearing in algebraic geometry and commutative algebra. Special emphasis is put on various stability notions which are defined in a combinatorial manner and for which a number of equivalent algebraic characterisations are provided. It is shown that in characteristic zero the corresponding generic positions can be obtained with a simple deterministic algorithm. In positive characteristic, only adapted stable positions are reachable except for quasi-stability which is obtainable in any characteristic. [ABSTRACT FROM AUTHOR]

Hybrid systems are dynamical systems with interacting discrete computation and continuous physical processes, which have become more common, more indispensable, and more complicated in our modern life. Particularly, many of them are safety-critical, and therefore are required to meet a critical safety standard. Invariant generation plays a central role in the verification and synthesis of hybrid systems. In the previous work, the fourth author and his coauthors gave a necessary and sufficient condition for a semi-algebraic set being an invariant of a polynomial autonomous dynamical system, which gave a confirmative answer to the open problem. In addition, based on which a complete algorithm for generating all semi-algebraic invariants of a given polynomial autonomous hybrid system with the given shape was proposed. This paper considers how to extend their work to non-autonomous dynamical and hybrid systems. Non-autonomous dynamical and hybrid systems are with inputs, which are very common in practice; in contrast, autonomous ones are without inputs. Furthermore, the authors present a sound and complete algorithm to verify semi-algebraic invariants for non-autonomous polynomial hybrid systems. Based on which, the authors propose a sound and complete algorithm to generate all invariants with a pre-defined template. [ABSTRACT FROM AUTHOR]

A Pfaffian circuit is a tensor contraction network where the edges are labeled with basis changes in such a way that a very specific set of combinatorial properties is satisfied. By modeling the permissible basis changes as systems of polynomial equations, and then solving via computation, we are able to identify classes of 0/1 planar #CSP problems solvable in polynomial time via the Pfaffian circuit evaluation theorem (a variant of L. Valiant's Holant Theorem). We present two different models of 0/1 variables, one that is possible under a homogeneous basis change, and one that is possible under a heterogeneous basis change only. We enumerate a collection of 1, 2, 3, and 4-arity gates/cogates that represent constraints, and define a class of constraints that is possible under the assumption of a “bridge” between two particular basis changes. We discuss the issue of planarity of Pfaffian circuits, and demonstrate possible directions in algebraic computation for designing a Pfaffian tensor contraction network fragment that can simulate a swap gate/cogate. We conclude by developing the notion of a decomposable gate/cogate, and discuss the computational benefits of this definition. [ABSTRACT FROM AUTHOR]

In the last decades many authors have become interested in the study of multilinear and polynomial generalizations of families of operator ideals (such as, for instance, the ideal of absolutely summing operators). However, these generalizations must keep the essence of the given operator ideal and there seems not to be a universal method to achieve this. The main task of this paper is to discuss, study, and introduce multilinear and polynomial extensions of the aforementioned operator ideals taking into account the already existing methods of evaluating the adequacy of such generalizations. Besides this subject's intrinsic mathematical interest, the main motivation is our belief (based on facts that shall be presented) that some of the already existing approaches are not adequate. [ABSTRACT FROM AUTHOR]

This paper investigates the termination problems of multi-path polynomial programs (MPPs) with equational loop guards. To establish sufficient conditions for termination and nontermination simultaneously, the authors propose the notion of strong/weak non-termination which under/over-approximates non-termination. Based on polynomial ideal theory, the authors show that the set of all strong non-terminating inputs (SNTI) and weak non-terminating inputs (WNTI) both correspond to the real varieties of certain polynomial ideals. Furthermore, the authors prove that the variety of SNTI is computable, and under some sufficient conditions the variety of WNTI is also computable. Then by checking the computed SNTI and WNTI varieties in parallel, termination properties of a considered MPP can be asserted. As a consequence, the authors establish a new framework for termination analysis of MPPs. [ABSTRACT FROM AUTHOR]

Zonotopal algebra studies pairs of dual algebraic structures that are associated with a linear matroid X and are connected to corresponding dual geometries. Both the geometry and the algebra encode in their statistics combinatorial properties of the matroid. We provide in this paper a general, unified, framework for the chapter in zonotopal algebra that is known as external. The approach is critically based on employing simultaneously the two dual algebraic constructs and invokes the underlying matroidal and geometric structures in an essential way. [ABSTRACT FROM AUTHOR]

What is an adequate extension of an operator ideal $$\mathcal{I }$$ to the polynomial and multilinear settings? This question motivated the appearance of the interesting concepts of coherent sequences of polynomial ideals and compatibility of a polynomial ideal with an operator ideal, introduced by D. Carando et al. We propose a different approach by considering pairs $$(\mathcal{U }_{k},\mathcal{M }_{k})_{k=1}^{\infty }$$ , where $$(\mathcal{U }_{k})_{k=1}^{\infty }$$ is a polynomial ideal and $$(\mathcal{M }_{k})_{k=1}^{\infty }$$ is a multi-ideal, instead of considering just polynomial ideals. It is our belief that our approach ends a discomfort caused by the previous theory: for real scalars the canonical sequence $$(\mathcal{P }_{k})_{k=1}^{\infty }$$ of continuous $$k$$ -homogeneous polynomials is not coherent according to the definition of Carando et al. We apply these new notions to test the pairs of ideals of nuclear and integral polynomials and multilinear operators, the factorisation method and different classes that generalise the concept of absolutely summing operator. [ABSTRACT FROM AUTHOR]

Abstract: We show that several spaces of holomorphic functions on a Riemann domain over a Banach space, including the nuclear and Hilbert–Schmidt bounded type, are locally m-convex Fréchet algebras. We prove that the spectrum of these algebras has a natural analytic structure, which we use to characterize the envelope of holomorphy. We also show a Cartan–Thullen type theorem. [Copyright &y& Elsevier]

We show that for each Banach ideal of homogeneous polynomials, there exists a (necessarily unique) Banach operator ideal compatible with it. Analogously, we prove that any ideal of n-homogeneous polynomials belongs to a coherent sequence of ideals of k-homogeneous polynomials. [ABSTRACT FROM AUTHOR]

Zonotopal algebra interweaves algebraic, geometric and combinatorial properties of a given linear map X. Of basic significance in this theory is the fact that the algebraic structures are derived from the geometry (via a nonlinear procedure known as "the least map"), and that the statistics of the algebraic structures (e.g., the Hilbert series of various polynomial ideals) are combinatorial, i.e., computable using a simple discrete algorithm known as "the valuation function". On the other hand, the theory is somewhat rigid since it deals, for the given X, with exactly two pairs, each of which consists of a nested sequence of three ideals: an external ideal (the smallest), a central ideal (the middle), and an internal ideal (the largest). In this paper we show that the fundamental principles of zonotopal algebra as described in the previous paragraph extend far beyond the setup of external, central and internal ideals by building a whole hierarchy of new combinatorially defined zonotopal spaces. [ABSTRACT FROM AUTHOR]

Abstract: A wealth of geometric and combinatorial properties of a given linear endomorphism X of is captured in the study of its associated zonotope , and, by duality, its associated hyperplane arrangement . This well-known line of study is particularly interesting in case . We enhance this study to an algebraic level, and associate X with three algebraic structures, referred herein as external, central, and internal. Each algebraic structure is given in terms of a pair of homogeneous polynomial ideals in n variables that are dual to each other: one encodes properties of the arrangement , while the other encodes by duality properties of the zonotope . The algebraic structures are defined purely in terms of the combinatorial structure of X, but are subsequently proved to be equally obtainable by applying suitable algebro-analytic operations to either of or . The theory is universal in the sense that it requires no assumptions on the map X (the only exception being that the algebro-analytic operations on yield sought-for results only in case X is unimodular), and provides new tools that can be used in enumerative combinatorics, graph theory, representation theory, polytope geometry, and approximation theory. [Copyright &y& Elsevier]

Abstract: We introduce the symmetric Radon–Nikodým property (sRN property) for finitely generated s-tensor norms β of order n and prove a Lewis type theorem for s-tensor norms with this property. As a consequence, if β is a projective s-tensor norm with the sRN property, then for every Asplund space E, the canonical mapping is a metric surjection. This can be rephrased as the isometric isomorphism for some polynomial ideal . We also relate the sRN property of an s-tensor norm with the Asplund or Radon–Nikodým properties of different tensor products. As an application, results concerning the ideal of n-homogeneous extendible polynomials are obtained, as well as a new proof of the well-known isometric isomorphism between nuclear and integral polynomials on Asplund spaces. An analogous study is carried out for full tensor products. [Copyright &y& Elsevier]

Abstract: We study Poincaré duality algebras over the field of two elements. After introducing a connected sum operation for such algebras we compute the corresponding Grothendieck group of surface algebras (i.e., Poincaré algebras of formal dimension 2). We show that the corresponding group for 3-folds (i.e., algebras of formal dimension 3) is not finitely generated, but does have a Krull–Schmidt property. We then examine the isomorphism classes of 3-folds with at most three generators of degree 3, provide a complete classification, settle which such occur as the cohomology of a smooth 3-manifold, and list separating invariants. The closing section and Appendix A provide several different means of constructing connected sum indecomposable 3-folds. [ABSTRACT FROM AUTHOR]

Inspired by a question of Lovász, we introduce a hierarchy of nested semidefinite relaxations of the convex hull of real solutions to an arbitrary polynomial ideal called theta bodies of the ideal. These relaxations generalize Lovász's construction of the theta body of a graph. We establish a relationship between theta bodies and Lasserre's relaxations for real varieties which allows, in many cases, for theta bodies to be expressed as feasible regions of semidefinite programs. Examples from combinatorial optimization are given. Lovász asked to characterize ideals for which the first theta body equals the closure of the convex hull of its real variety. We answer this question for vanishing ideals of finite point sets via several equivalent characterizations. We also give a geometric description of the first theta body for all ideals. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we show that the ideal of any algebraic curve in affine 3-space whose Jacobian matrix has rank at least 1 at every singular point of the curve can be generated by three polynomials and we give constructive procedures to compute such generators. [Copyright &y& Elsevier]

Let K be a field and let m0,...,mn be an almost arithmetic sequence of positive integers. Let C be a toric variety in the affine (n + 1)-space, defined parametrically by x0 = tm0,...,xn = tmn. In this article we produce a minimal Grobner basis for the toric ideal which is the defining ideal of C and give sufficient and necessary conditions for this basis to be the reduced Grobner basis of C, correcting a previous work of [6] and giving a much simpler proof than that of [1]. [ABSTRACT FROM AUTHOR]

Abstract: Let A be a subvariety of affine space whose irreducible components are d-dimensional linear or affine subspaces of . Denote by the set of exponents of standard monomials of A. We show that the combinatorial object reflects the geometry of A in a very direct way. More precisely, we define a d-plane in as being a set , where and for all . We call the d-plane thus defined to be parallel to . We show that the number of d-planes in equals the number of components of A. This generalises a classical result, the finiteness algorithm, which holds in the case . In addition to that, we determine the number of all d-planes in parallel to , for all J. Furthermore, we describe in terms of the standard sets of the intersections , where λ runs through . [Copyright &y& Elsevier]

Abstract: We study the existence of atomic decompositions for tensor products of Banach spaces and spaces of homogeneous polynomials. If a Banach space X admits an atomic decomposition of a certain kind, we show that the symmetrized tensor product of the elements of the atomic decomposition provides an atomic decomposition for the symmetric tensor product , for any symmetric tensor norm μ. In addition, the reciprocal statement is investigated and analogous consequences for the full tensor product are obtained. Finally we apply the previous results to establish the existence of monomial atomic decompositions for certain ideals of polynomials on X. [Copyright &y& Elsevier]

This paper introduces the foundations of the polynomial algebra and basic structures for algebraic geometry over the extended tropical semiring. Our development, which includes the tropical version for the fundamental theorem of algebra, leads to the reduced polynomial semiring — a structure that provides a basis for developing a tropical analogue to the classical theory of commutative algebra. The use of the new notion of tropical algebraic com-sets, built upon the complements of tropical algebraic sets, eventually yields the tropical algebraic Nullstellensatz. [ABSTRACT FROM AUTHOR]

We study the local dynamics of maps $$f(z) = -z -{\sum^{{\infty}}_{k=1}}\alpha_{k}z^{k+1},$$ where f( z) is an irreducible branch of the algebraic curve We give the complete description of bifurcations of 2-periodic points of f( z) in a small neighborhood of the origin when n is odd. For the case of even n some partial results regarding to the bifurcations of such points are obtained. [ABSTRACT FROM AUTHOR]

We determine, in a polynomial ring over a field, the arithmetical rank of certain ideals generated by a set of monomials and one binomial. [ABSTRACT FROM AUTHOR]

Abstract: We present a static analysis that approximates the relational semantics of imperative programs by systems of low-degree polynomial equalities. Our method is based on Abstract Interpretation in a lattice of polynomial pseudo ideals — finite-dimensional vector spaces of degree-bounded polynomials that are closed under degree-bounded products. For a fixed degree bound, the sizes of bases of pseudo ideals and the lengths of chains in the lattice of pseudo ideals are bounded by polynomials in the number of program variables. Despite the approximate nature of our analysis, for several programs taken from the literature on non-linear polynomial invariant generation our method produces results that are as precise as those produced by methods based on polynomial ideals and Gröbner bases. [Copyright &y& Elsevier]

Abstract: We study , the number of distinct values taken by multinomial coefficients with upper entry n, and some closely related sequences. We show that both and tend to zero as n goes to infinity, where is the number of partitions of n into primes and is the total number of partitions of n. To use methods from commutative algebra, we encode partitions and multinomial coefficients as monomials. [Copyright &y& Elsevier]

We prove the ‘strong form’ of the Clemens conjecture in decree 10. Namely, on a general quintic threefold F in P4, there are only, finitely, many smooth rational curves of decree 10, and each curve C is embedded in F with normal bundle [This symbol cannot be presented in ASCII format](-1)⊕[This symbol cannot be presented in ASCII format](-1). Moreover, in degree 10, there are no singular, reduced, and irreducible rational curves, nor any reduced, reducible, and connected curves with rational components on F. [ABSTRACT FROM AUTHOR]

Abstract: We study the algebraic varieties defined by the conditional independence statements of Bayesian networks. A complete algebraic classification is given for Bayesian networks on at most five random variables. Hidden variables are related to the geometry of higher secant varieties. [Copyright &y& Elsevier]

Abstract: In this paper we present some algorithms for computing an irreducible decomposition of an ideal in a polynomial ring where is an arbitrary effective field. [Copyright &y& Elsevier]

We present the basic concepts and results of Gröbner bases theory for readers working or interested in systems theory. The concepts and methods of Gröbner bases theory are presented by examples. No prerequisites, except some notions of elementary mathematics, are necessary for reading this paper. The two main properties of Gröbner bases, the elimination property and the linear independence property, are explained. Most of the many applications of Gröbner bases theory, in particular applications in systems theory, hinge on these two properties. Also, an algorithm based on Gröbner bases for computing complete systems of solutions (“syzygies”) for linear diophantine equations with multivariate polynomial coefficients is described. Many fundamental problems of systems theory can be reduced to the problem of syzygies computation. [ABSTRACT FROM AUTHOR]

Over a fixed finite field ${\bf F}_p$, families of polynomial equations $f_i(x_1, \dots, x_{n_N}) = 0$ for $i = 1, \dots, k_N$, that are uniformly determined by a parameter $N$, are considered. The notion of a uniform family is defined in terms of first-order logic. A notion of an abstract Euler characteristic is used to give sense to a statement that the system has a solution for infinite $N$, and a statement linking the solvability of a linear system for infinite $N$ with its solvability for finite $N$ is proved. This characterisation is used to formulate a criterion yielding degree lower bounds for various ideal membership proof systems (for example, Nullstellensatz and the polynomial calculus). Further, several results about Euler structures (structures with an abstract Euler characteristic) are proved, and the case of fields, in particular, is investigated more closely. 1991 Mathematics Subject Classification: primary 03F20, 12L12, 15A06; secondary 03C99, 12E12, 68Q15, 13L05. [ABSTRACT FROM AUTHOR]

We discuss polynomial interpolation in several variables from a polynomial ideal point of view. One of the results states that if I is a real polynomial ideal with real variety and if its codimension is equal to the cardinality of its variety, then for each monomial order there is a unique polynomial that interpolates on the points in the variety. The result is motivated by the problem of constructing cubature formulae, and it leads to a theorem on cubature formulae which can be considered an extension of Gaussian quadrature formulae to several variables. [ABSTRACT FROM AUTHOR]