Search

In this paper we introduce a method of characteristic sets with respect to several term orderings for inversive difference polynomials. Using this technique, we prove the existence and obtain a method of computation of multivariate dimension polynomials of finitely generated inversive difference field extensions. We also find new invariants of such extensions that are not carried by univariate dimension polynomials.

Recent applications of decision procedures for nonlinear real arithmetic (the theory of real closed fields, or RCF) have presented a need for reasoning not only with polynomials but also with transcendental constants and infinitesimals. In full generality, the algebraic setting for this reasoning consists of real closed transcendental and infinitesimal extensions of the rational numbers. We present a library for computing over these extensions. This library contains many contributions, including a novel combination of Thom's Lemma and interval arithmetic for representing roots, and provides all core machinery required for building RCF decision procedures. We describe the abstract algebraic setting for computing with such field extensions, present our concrete algorithms and optimizations, and illustrate the library on a collection of examples.

Let K be a field, and let \(f\left( X\right) \in \mathbf{K}\left[ X \right] \) be a polynomial with coefficients in K. In general, the equation \(f\left( x\right) =0\) has solutions in an extension of K, not in K itself. For example, if K = ℚ , the equation x2 + 2 = 0 has no solution in ℚ , it has in ℂ its full set of solutions \(\left\{ i\sqrt{2},-i\sqrt{2}\right\} \), and these solutions are already in the extension \( \mathbb{Q} \left( i,\sqrt{2}\right) \subsetneq \mathbb{C} \) of ℚ . The study of algebraic field extensions is the Galois theory, recalled in Section 4.2.

An algebraic field extension of *** or ***/(p ) may be regarded either as a structure in its own right, or as a subfield of its algebraic closure $\overline{F}$ (either $\overline{\mathbb{Q}}$ or $\overline{{\mathbb{Z}}/(p)}$). We consider the Turing degree spectrum of F in both cases, as a structure and as a relation on $\overline{F}$, and characterize the sets of Turing degrees that are realized as such spectra. The results show a connection between enumerability in the structure F and computability when F is seen as a subfield of $\overline{F}$.

We study cyclic extensions arising from Kummer theory of norm algebraic tori. In particular, we compute quintic cyclic polynomials defining ‘Kummer extension’. The polynomials do not only give all the quintic cyclic extensions over the rationals by choosing the parameters but also classify all such extensions. Some arithmetic properties of the polynomials are also derived.

Let Σ be an alphabet of size t, let f:Σ*→Σ* be a non-erasing morphism, let w be an infinite fixed point of f, and let E(w) be the critical exponent of w. We prove that if E(w) is finite, then for a uniform f it is rational, and for a non-uniform f it lies in the field extension ${{\mathbb Q}[{\lambda_1},\ldots,{\lambda_\ell}]}$, where λ1,...,λl are the eigenvalues of the incidence matrix of f. In particular, E(w) is algebraic of degree at most t. Under certain conditions, our proof implies an algorithm for computing E(w). MSC: 68R15

Let E be an elliptic curve defined over F-2n. The inverse operation of point doubling, called point halving, can be done up to three times as fast as doubling. Some authors have therefore proposed to perform a scalar multiplication by an "halve-and-add" algorithm, which is faster than the classical double-and-add method. If the coefficients of the equation defining the curve lie in a small subfield of F-2n, one can use the Frobenius endomorphism tau of the field extension to replace doublings. Since the cost of tau is negligible if normal bases are used, the scalar multiplication is written in "base tau" and the resulting "tau-and-add" algorithm gives very good performance. For elliptic Koblitz curves, this work combines the two ideas for the first time to achieve a novel decomposition of the scalar. This gives a new scalar multiplication algorithm which is up to 14.29% faster than the Robenius method, without any additional precomputation.

We describe the extension of the techniques implemented in [DSS] to the computation of provably accurate values for the lead term at s = 0 of abelian L-functions having higher order zeros, and provide some explicit examples. In particular we raise the question of applying the higher order extensions of the abelian Stark Conjecture to the explicit construction of an interesting field extension in a manner analogous to the applications here and in [DSS], [Ro] in the case of zeros of rank one.

There are various algorithms known for deciding the parametrizability (rationality) of a plane algebraic curve, and if the curve is rational, actually computing a parametrization. Optimality criteria such as low degrees in the parametrization or low degree field extensions are met by some parametrization algorithms. In this paper we investigate real curves. Given a parametrizable plane curve over the complex numbers, we decide whether it is in fact real. Furthermore, we discuss methods for actually computing a real parametrization for a parametrizable real curve.

We discuss various techniques for exhibiting specific polynomials of provably high complexity which originate in a landmark paper by Strassen [499] written in 1974. In the first section we restrict ourselves to computations in the polynomial algebra (no divisions) and derive a lower bound in an elementary way. In the next section we study computations in the ring of formal power series, define complexity classes, and prove a representation theorem for them. Based on this, a general lower bound theorem on the multiplicative complexity follows. As a result we exhibit in Sect. 9.3 various specific polynomials with algebraic coefficients which are hard to compute. Some tools from algebraic number theory are required for computing the degrees of the occurring field extensions. In Sect. 9.4 we proceed with rather technical lower bound proofs for polynomials with rapidly growing integer coefficients. Finally, in Sect. 9.5, we extend most of what we have done so far to other complexity measures, in particular to additive complexity.

This chapter is devoted to the discussion of fast matrix multiplication algorithms. We define the exponent ω of matrix multiplication, a quantity measuring the asymptotic complexity of this problem. Strassen’s original algorithm gives ω ≤ 2.81 (see Chap. 1). The robustness of the exponent with respect to various cost functions, and its invariance with respect to field extensions is shown. (Further motivation for the investigation of ω is given in Chap. 16.) We introduce the concept of border rank of tensors due to Bini, Capovani, Lotti, and Romani [49], and deduce Schonhage’s asymptotic sum inequality [460], which has become one of the main tools for gaining upper estimates of the exponent. Then we present the laser method [508] and its generalization by Coppersmith and Winograd [134], and prove their estimate ω < 2.39. Finally, an extension of the asymptotic sum inequality to the multiplication of partially filled matrices is considered. As an application, we describe Coppersmith’s construction of astonishingly rapid algorithms for the multiplication of rectangular matrices.

We assume the reader is familiar with the standard ways of constructing “simple” field extensions of a given field F, using polynomials. These are of two kinds: the simple transcendental extension F(t), which is the field of fractions of the polynomial ring F[t] in an indeterminate t, and the simple algebraic extension F[t]/(f(t)) where f(t) is an irreducible polynomial in F[t]. In this chapter we shall consider some analogous constructions of division rings based on certain rings of polynomials D[t; σ, δ] that were first introduced by Oystein Ore [33] and simultaneously by Wedderburn. Here D is a given division ring, σ is an automorphism of D, δ is a σ-derivation (1.1.1) and t is an indeterminate satisfying the basic commutation rule $$ta=(\sigma a)t+\delta a$$ (1.0.1) for a∈D. The elements of D[t; σ, δ] are (left) polynomials $$a_0+a_1t+\cdots +a_nt^n,\qquad a_i\in D$$ (1.0.2) where multiplication can be deduced from the associative and distributive laws and (1.0.1) (cf. Draxl [83]). We shall consider two types of rings obtained from D[t; σ, δ]: homomorphic images and certain localizations (rings of quotients) by central elements. The special case in which δ=0 leads to cyclic and generalized cyclic algebras. The special case in which σ=1 and the characteristic is p≠0 gives differential extensions analogous to cyclic algebras.

In view of the global stability formulae (Corollary V.1.6), and the canonical decomposition (III.1.9), the computation of stability indices in the space of signs of a ring reduces to estimations of the size of fans of residue fields of that ring. We obtain in Section 1 such estimations, via real valuations, after proving the so-called trivialization theorem for fans. Then, in Section 2, we deduce upper bounds for the stability index of a field extension in terms of the ground field. These bounds are sharp when the ground field is real closed or the rational numbers field, as follows from the lower bounds discussed in Section 3. In section 4 we generalize the previous upper bounds to algebras. The results are specially good for algebras over a field, which are the matter of Section 5; again, we obtain the best estimations over a real closed field and over the rationals. Section 6 is devoted to totally archimedean rings, which are the abstract counterparts of compact spaces. These rings have two special features: firstly, their complexity bounds are low, and, secondly, generation of basic sets and separation are characterized by multilocal conditions. We end in Section 7 with the translation to concrete semialgebraic geometry of most of the abstract results obtained so far. We as well discuss several examples and counterexamples to questions raised in earlier chapters.

We use algebraic field extension theory to find self-correctors for a broad class of functions. Many functions whose translations are contained in a function field that is a finite degree extension of a scalar field satisfy polynomial identities that can be transformed into self-correctors. These functions can be efficiently corrected in a way that is simpler and different from how the functions are actually computed. This is an essential feature of program self-correcting. Among the functions for which we present self-correctors are many rational expressions of x,e x , and sin(x) (over the real and complex fields) as weD as many rational expressions of x, g x (g a generator) mapping the integers into a finite field and many rational expressions of x,log h (x) (h a generator) mapping a finite field into the reals.

An operational calculus for the Bessel operator Bμ=t-μDtμ+1D(−1

The theory of using a polynomial to create an algebraic field extension is well-defined in mathematical literature and the technique is commonly used in symbolic computation. Even when extensions are not over a field, monics polynomials are often used to extend rings (e.g., the Gaussian Integers can be formed as ℤ[x]/x2+1). As long as only algebraic integers are introduced (i.e., the extension is monic), the computational methods are straightforward and the algorithms and supporting theory are known.

Explicit solutions of partial differential equations.- Hyperfinite spin models.- Nonstandard analysis and the theory of Banach spaces.- Stochastic solutions to partial differential equations.- Existence of solutions to the martingale problem in Rd for degenerate discontinuous coefficients.- ?-Calculus as a generalization of field extension an alternative approach to nonstandard analysis.- Stochastic integration in hyperfinite dimensional linear spaces.- Stochastic processes and nonstandard analysis.- Towards a nonstandard analysis of programs.- Infinitesimal analysis of l ? in its mackey topology.

The theory which we shall develop in this chapter is of purely group theoretical nature and is concerned with an abstract profinite group G. To work in a more familiar language, however, we want to interpret G formally as a Galois group in the following sense. We denote the closed subgroups of G by G K and call the indices K fields; we refer to K as the fixed field of G K . The “field” k with G k = G is called the ground field and we denote by ¯k; the field with G¯k; = {1}. We write formally K ⊆ L or L | K if GL ⊆ GK and refer to the pair L|K as a field extension. L | K is a “finite extension” if G L is open (i.e. of finite index) in G K and we call $$[L:K] = ({G_K}:{G_L})$$ the degree of the extension L|K. L|K is called normal or Galois if G L is a normal subgroup of GK. In this case we define the Galois group of L|K by $$G(L|K) = {G_K}/{G_L}$$ .

Here we present the algebraic geometry background for the study of PAC fields. The central result is a descent argument which associates to each variety V defined over a finite extension L of a field K a variety W defined over K. Throughout this chapter, and subsequent chapters we make the following convention. Whenever we are given a collection of field extensions of a given field K we assume that all of them are contained in a common field.

We first consider an arbitrary (not necessarily algebraic) field extension L∣K. Let A (resp. B) be a valuation ring of K (resp. L). We say that B lies over A if A = B ∩ K; in this case B is also called an extension of A. Considering A and B as local subrings of L we gets: (13.1) B lies over A if and only if B dominates A.