We consider the question of certifying that a polynomial in ${mathbb Z}[x]$ or ${mathbb Q}[x]$ is irreducible. Knowing that a polynomial is irreducible lets us recognise that a quotient ring is actually a field extension (equiv.~that a polynomial ide
al is maximal). Checking that a polynomial is irreducible by factorizing it is unsatisfactory because it requires trusting a relatively large and complicated program (whose correctness cannot easily be verified). We present a practical method for generating certificates of irreducibility which can be verified by relatively simple computations; we assume that primes and irreducibles in ${mathbb F}_p[x]$ are self-certifying.
The main focus of this paper is on the problem of relating an ideal $I$ in the polynomial ring $mathbb Q[x_1, dots, x_n]$ to a corresponding ideal in $mathbb F_p[x_1,dots, x_n]$ where $p$ is a prime number; in other words, the textit{reduction modulo
$p$} of $I$. We first define a new notion of $sigma$-good prime for $I$ which does depends on the term ordering $sigma$, but not on the given generators of $I$. We relate our notion of $sigma$-good primes to some other similar notions already in the literature. Then we introduce and describe a new invariant called the universal denominator which frees our definition of reduction modulo~$p$ from the term ordering, thus letting us show that all but finitely many primes are good for $I$. One characteristic of our approach is that it enables us to easily detect some bad primes, a distinct advantage when using modular methods.
Given a zero-dimensional ideal I in a polynomial ring, many computations start by finding univariate polynomials in I. Searching for a univariate polynomial in I is a particular case of considering the minimal polynomial of an element in P/I. It is w
ell known that minimal polynomials may be computed via elimination, therefore this is considered to be a resolved problem. But being the key of so many computations, it is worth investigating its meaning, its optimization, its applications (e.g. testing if a zero-dimensional ideal is radical, primary or maximal). We present efficient algorithms for computing the minimal polynomial of an element of P/I. For the specific case where the coefficients are in Q, we show how to use modular methods to obtain a guaranteed result. We also present some applications of minimal polynomials, namely algorithms for computing radicals and primary decompositions of zero-dimensional ideals, and also for testing radicality and maximality.
We present a survey on the developments related to Groebner bases, and show explicit examples in CoCoA. The CoCoA project dates back to 1987: its aim was to create a mathematician-friendly computational laboratory for studying Commutative Algebra, mo
st especially Groebner bases. Always maintaining this friendly tradition, the project has grown and evolved, and the software has been completely rewritten. CoCoA offers Groebner bases for all levels of interest: from the basic, explicit call in the interactive system CoCoA-5, to problem-specific optimized implementations, to the computer--computer communication with the open source C++ software library, CoCoALib, or the prototype OpenMath-based server. The openness and clean design of CoCoALib and CoCoA-5 are intended to offer different levels of usage, and to encourage external contributions.
We present new, practical algorithms for the hypersurface implicitization problem: namely, given a parametric description (in terms of polynomials or rational functions) of the hypersurface, find its implicit equation. Two of them are for polynomial
parametrizations: one algorithm, ElimTH, has as main step the computation of an elimination ideal via a textit{truncated, homogeneous} Grobner basis. The other algorithm, Direct, computes the implicitization directly using an approach inspired by the generalized Buchberger-Moller algorithm. Either may be used inside the third algorithm, RatPar, to deal with parametrizations by rational functions. Finally we show how these algorithms can be used in a modular approach, algorithm ModImplicit, for avoiding the high costs of arithmetic with rational numbers. We exhibit experimental timings to show the practical efficiency of our new algorithms.
Let $n$ be a positive integer and let $f_1, ldots, f_r$ be polynomials in $n^2$ indeterminates over an algebraically closed field $K$. We describe an algorithm to decide if the invertible matrices contained in the variety of $f_1, ldots, f_r$ form a
subgroup of $GL(n,K)$; that is, we show how to decide if the polynomials $f_1, ldots, f_r$ define a linear algebraic group.
In this paper we present two efficient methods for reconstructing a rational number from several residue-modulus pairs, some of which may be incorrect. One method is a natural generalization of that presented by Wang, Guy and Davenport in cite{WGD198
2} (for reconstructing a rational number from textit{correct} modular images), and also of an algorithm presented in cite{Abb1991} for reconstructing an textit{integer} value from several residue-modulus pairs, some of which may be incorrect.
We present a new algorithm for refining a real interval containing a single real root: the new method combines characteristics of the classical Bisection algorithm and Newtons Iteration. Our method exhibits quadratic convergence when refining isolati
ng intervals of simple roots of polynomials (and other well-behaved functions). We assume the use of arbitrary precision rational arithmetic. Unlike Newtons Iteration our method does not need to evaluate the derivative.
We gather together several bounds on the sizes of coefficients which can appear in factors of polynomials in Z[x]; we include a new bound which was latent in a paper by Mignotte, and a few minor improvements to some existing bounds. We compare these
bounds and show that none is universally better than the others. In the second part of the paper we give several concrete examples of factorizations where the factors have unexpectedly large coefficients. These examples help us understand why the bounds must be larger than you might expect, and greatly extend the collection published by Collins.
Let $X$ be a set of points whose coordinates are known with limited accuracy; our aim is to give a characterization of the vanishing ideal $I(X)$ independent of the data uncertainty. We present a method to compute a polynomial basis $B$ of $I(X)$ whi
ch exhibits structural stability, that is, if $widetilde X$ is any set of points differing only slightly from $X$, there exists a polynomial set $widetilde B$ structurally similar to $B$, which is a basis of the perturbed ideal $ I(widetilde X)$.
