Search

In the area of symbolic-numerical computation within computer algebra, an interesting question is how “close” a random input is to the “critical” ones. Examples are the singular matrices in linear algebra or the polynomials with multiple roots for Newton's root-finding method. Bounds, sometimes very precise, are known for the volumes over R or C of such neighborhoods of the varieties of “critical” inputs; see the references below. This paper deals with the discrete version of this question: over a finite field, how many points lie in a certain type of neighborhood around a given variety? A trivial upper bound on this number is given by the product (size of the variety) ⋅ (size of a neighborhood of a point). It turns out that this bound is usually asymptotically tight, in particular for the singular matrices, polynomials with multiple roots, and pairs of non-coprime polynomials. The interesting question then is: for which varieties is this bound not asymptotically tight? We show that these are precisely those that admit a shift, that is, where one absolutely irreducible component of maximal dimension is a shift (translation by a fixed nonzero point) of another such component. Furthermore, the shift-invariant absolutely irreducible varieties are characterized as being cylinders over some base variety. Computationally, determining whether a given variety is shift-invariant turns out to be intractable, namely NP-hard even in simple cases.

Finding minimal fields of definition for representations is one of the most important unsolved problems of computational representation theory. While good methods exist for representations over finite fields, it is still an open question in the case of number fields. In this paper we give a practical method for finding minimal defining subfields for absolutely irreducible representations. We illustrate the new algorithm by determining a minimal field for each absolutely irreducible representation of Sz(8).

Let K be a number field and F(X,Y) an absolutely irreducible polynomial of K[X,Y] such that the algebraic curve defined by the equation F(X,Y)=0 is rational. In this paper we present practical algorithms for the determination of all solutions of the Diophantine equation F(X,Y)=0 in algebraic integers of K.

Let f(X, Y) be an absolutely irreducible polynomial with integer coefficients such that the curve defined by the equation f(X, Y) = 0 is of genus 0 having at most two infinite valuations. This paper describes a practical general method for the explicit determination of all integer solutions of the diophantine equation f(X, Y) = 0. Several elaborated examples are given. Furthermore, a necessary and sufficient condition for a curve of genus 0 to have infinitely many integer points is obtained.

Given a squarefree polynomial P∈k0[ x,y ], k0a number field, we construct a linear differential operator that allows one to calculate the genus of the complex curve defined by P= 0 (when P is absolutely irreducible), the absolute factorization of P over the algebraic closure of k0, and calculate information concerning the Galois group of P over ___ k0(x) as well as overk0 (x).

This paper describes an algebraic approach to computing the system of adjoint curves to a given absolutely irreducible plane algebraic curve. The proposed algorithm utilizes the integral closure of the coordinate ring rather than expanding neighborhood graphs using quadratic transformations.

We present a fast parallel deterministic algorithm for testing multivariate integral polynomials for absolute irreducibility, that is irreducibility over the complex numbers. More precisely, we establish that the set of absolutely irreducible integral polynomials belongs to the complexity class NC of Boolean circuits of polynomial size and logarithmic depth. Therefore it also belongs to the class of sequentially polynomial-time problems. Our algorithm can be extended to compute in parallel one irreducible complex factor of a multivariate integral polynomial. However, the coeffieients of the computed factor are only represented modulo a not necessarily irreducible polynomial specifying a splitting field. A consequence of our algorithm is that multivariate polynomials over finite fields can be tested for absolute irreducibility in deterministic sequential polynomial time in the size of the input. We also obtain a sharp bound for the last prime p for which, when taking an absolute irreducible integral polynomial modulo p, the polynomial's irreducibility in the algebraic closure of the finite field of order p is not preserved.