Fault-Tolerant Modular Reconstruction of Rational Numbers

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{WGD1982} (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.

Quadratic Interval Refinement for Real Roots

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 isolating 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.

Bounds on Factors in Z[x]

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.

Stable Border Bases for Ideals of Points

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)$ which 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)$.