Fast computation of a rational point of a variety over a finite field

We exhibit a probabilistic algorithm which computes a rational point of an absolutely irreducible variety over a finite field defined by a reduced regular sequence. Its time-space complexity is roughly quadratic in the logarithm of the cardinality of the field and a geometric invariant of the input system. This invariant, called the degree, is bounded by the Bézout number of the system. Our algorithm works for fields of any characteristic, but requires the cardinality of the field to be greater than a quantity which is roughly the fourth power of the degree of the input variety.

     

On the expected number of real roots of polynomials and exponential sums

The expected number of real projective roots of orthogonally invariant random homogeneous real polynomial systems is known to be equal to the square root of the Bézout number. A similar result is known for random multi-homogeneous systems, invariant through a product of orthogonal groups. In this note, those results are generalized to certain families of sparse polynomial systems, with no orthogonal invariance assumed.     

Block-diagonal reduction of matrices over an <Emphasis Type="Italic">n</Emphasis>-simple Bézout domain (n ≥ 3)

It is known that a simple Bézout domain is the domain of elementary divisors if and only if it is 2-simple. The block-diagonal reduction of matrices over an n -simple Bézout domain (n ≥ 3) is realized.     

A condition number theorem for underdetermined polynomial systems

The condition number of a numerical problem measures the sensitivity of the answer to small changes in the input. In their study of the complexity of Bézout's theorem, M. Shub and S. Smale prove that the condition number of a polynomial system is equal to the inverse of the distance from this polynomial system to the nearest ill-conditioned one. Here we explain how this result can be extended to underdetermined systems of polynomials (that is with less equations than unknowns).

     

Smale’s Fundamental Theorem of Algebra Reconsidered

In his 1981 Fundamental Theorem of Algebra paper Steve Smale initiated the complexity theory of finding a solution of polynomial equations of one complex variable by a variant of Newton’s method. In this paper we reconsider his algorithm in the light of work done in the intervening years. Smale’s upper bound estimate was infinite average cost. Ours is polynomial in the Bézout number and the dimension of the input. Hence it is polynomial for any range of dimensions where the Bézout number is polynomial in the input size. In particular it is not just for the case that Smale considered but for a range of dimensions as considered by Bürgisser–Cucker, where the max of the degrees is greater than or equal to n ^1+? for some fixed ?. It is possible that Smale’s algorithm is polynomial cost in all dimensions and our main theorem raises some problems that might lead to a proof of such a theorem.     

Eine Bemerkung über den speziellen Bezoutschen Satz

Some synthetic methods in a projective space are devellopped and using them a theorem connected with the theorem of Bézout is proved without using any postulation about algebraic closure.

---

---

Herrn Professor Dr. WERNER BURAU zum 70. Geburtstag     

Jaffard-Ohm correspondence and Hochster duality

We study categorical aspects of the Jaffard–Ohm correspondencebetween abelian l-groups and Bézout domains and showthat this correspondence is close to a localization. For thispurpose, we establish a general extension theorem for valuationswith value group that is an abelian l-group. As an application,we prove Anderson's conjecture which refines the Jaffard–Ohmcorrespondence. We then extend the correspondence to sheaveson spectral spaces and show that the spectrum of a Bézoutdomain and the spectrum of its corresponding abelian l-groupprovide a concrete example for Hochster's duality of spectralspaces.     

A note on the stability of local zeta functions

We show the existence of an interval of stability under small perturbations of local zeta functions corresponding to non-trivial local solutions of an elliptic equation with Lipschitz coefficients.

RÉSUMÉ. Nous démontrons l'existence d'un intervalle de stabilité pour la fonction zêta associée à une équation uniformément elliptique du second ordre à coefficients lipschitziens.

     

Existence and nonexistence of hypercyclic semigroups

In these notes we provide a new proof of the existence of a hypercyclic uniformly continuous semigroup of operators on any separable infinite-dimensional Banach space that is very different from--and considerably shorter than--the one recently given by Bermúdez, Bonilla and Martinón. We also show the existence of a strongly dense family of topologically mixing operators on every separable infinite-dimensional Fréchet space. This complements recent results due to Bès and Chan. Moreover, we discuss the Hypercyclicity Criterion for semigroups and we give an example of a separable infinite-dimensional locally convex space which supports no supercyclic strongly continuous semigroup of operators.

     

A Mordell-Lang plus Bogomolov type result for curves in $${\mathbb{G}_{m}^{2}}$$

We prove a sharper so-called Mordell-Lang plus Bogomolov type result for curves lying in the two-dimensional linear torus. We mainly follow the approach of Rémond in (Comp Math 134:337–366, 2002), using Vojta and Mumford type inequalities. In the special case we consider, we improve Rémond’s main result using a better Bogomolov property and an elementary arithmetic Bézout theorem.      

Gröbner bases and generalized Padé approximation

It is shown how to find general multivariate Padé approximation using the Gröbner basis technique. This method is more flexible than previous approaches, and several examples are given to illustrate this advantage. When the number of variables is small compared to the degree of approximation, the Gröbner basis technique is more efficient than the linear algebra methods in the literature.

     

Neat rings

A ring is called clean if every element is the sum of a unit and an idempotent. Throughout the last 30 years several characterizations of commutative clean rings have been given. We have compiled a thorough list, including some new equivalences, in hopes that in the future there will be a better understanding of this interesting class of rings. One of the fundamental properties of clean rings is that every homomorphic image of a clean ring is clean. We define a neat ring to be one for which every proper homomorphic image is clean. In particular, the ring of integers, Z, and any nonlocal PID are examples neat rings which are not clean. We characterize neat Bézout domains using the group of divisibility. In particular, it is shown that a neat Bézout domain has stranded primes, that is, for every nonzero prime ideal the set of primes either containing or contained in the given prime forms a chain under set-theoretic inclusion.     

An efficient start system for multi-homogeneous polynomial continuation

Summary When solving a system of polynomial equations using homotopy continuation, the number of solution paths can often be significantly reduced by casting the equations in multi-homogeneous form. This requires a multi-homogeneous start system having a full set of nonsingular solutions that can be easily computed. We give a general form of such a start system that works for any multi-homogeneous structure and that can be used efficiently in continuation.     

A Mordell-Lang plus Bogomolov type result for curves in \mathbbGm2{\mathbb{G}_{m}^{2}}

We prove a sharper so-called Mordell-Lang plus Bogomolov type result for curves lying in the two-dimensional linear torus. We mainly follow the approach of Rémond in (Comp Math 134:337–366, 2002), using Vojta and Mumford type inequalities. In the special case we consider, we improve Rémond’s main result using a better Bogomolov property and an elementary arithmetic Bézout theorem.     

A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization

In this paper we propose a subspace limited memory quasi-Newton method for solving large-scale optimization with simple bounds on the variables. The limited memory quasi-Newton method is used to update the variables with indices outside of the active set, while the projected gradient method is used to update the active variables. The search direction consists of three parts: a subspace quasi-Newton direction, and two subspace gradient and modified gradient directions. Our algorithm can be applied to large-scale problems as there is no need to solve any subproblems. The global convergence of the method is proved and some numerical results are also given.

     

Fourier-Padé approximations and filtering for spectral simulations of an incompressible Boussinesq convection problem

In this paper, we present rational approximations based on Fourier series representation. For periodic piecewise analytic functions, the well-known Gibbs phenomenon hampers the convergence of the standard Fourier method. Here, for a given set of the Fourier coefficients from a periodic piecewise analytic function, we define Fourier-Padé-Galerkin and Fourier-Padé collocation methods by expressing the coefficients for the rational approximations using the Fourier data. We show that those methods converge exponentially in the smooth region and successfully reduce the Gibbs oscillations as the degrees of the denominators and the numerators of the Padé approximants increase.

Numerical results are demonstrated in several examples. The collocation method is applied as a postprocessing step to the standard pseudospectral simulations for the one-dimensional inviscid Burgers' equation and the two-dimensional incompressible inviscid Boussinesq convection flow.

     

A posteriori analysis of the finite element discretization of some parabolic equations

We are interested in the discretization of parabolic equations, either linear or semilinear, by an implicit Euler scheme with respect to the time variable and finite elements with respect to the space variables. The main result of this paper consists of building error indicators with respect to both time and space approximations and proving their equivalence with the error, in order to work with adaptive time steps and finite element meshes.

RÉSUMÉ. Nous considérons la discrétisation d'équations paraboliques, soit linéaires soit semi-linéaires, par un schéma d'Euler implicite en temps et par éléments finis en espace. L'idée de cet article est de construire des indicateurs d'erreur liés à l'approximation en temps et en espace et de prouver leur équivalence avec l'erreur, dans le but de travailler avec des pas de temps adaptatifs et des maillages d'éléments finis adaptés à la solution.

     

Equitable total coloring of <Emphasis Type="Italic">F</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> ⋁ <Emphasis Type="Italic">W</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

The minimum number of total independent partition sets of V ∪ E of graph G(V,E) is called the total chromatic number of G denoted by χ _t (G). If the difference of the numbers of any two total independent partition sets of V ∪ E is no more than one, then the minimum number of total independent partition sets of V ∪ E is called the equitable total chromatic number of G, denoted by χ _et (G). In this paper, we obtain the equitable total chromatic number of the join graph of fan and wheel with the same order. Supported by the National Natural Science Foundation of China (No. 10771091).     

Semiperfect ipri-rings and right Bézout rings

We present a survey of some results on ipri-rings and right Bézout rings. All these rings are generalizations of principal ideal rings. From the general point of view, decomposition theorems are proved for semiperfect ipri-rings and right Bézout rings.     

On the absolutely continuous spectrum of one-dimensional quasi-periodic Schrödinger operators in the adiabatic limit

In this paper we study the spectral properties of families of quasi-periodic Schrödinger operators on the real line in the adiabatic limit in the case when the adiabatic iso-energetic curves are extended along the position direction. We prove that, in energy intervals where this is the case, most of the spectrum is purely absolutely continuous in the adiabatic limit, and that the associated generalized eigenfunctions are Bloch-Floquet solutions.

RÉSUMÉ. Cet article est consacré à l'étude du spectre de certaines familles d'équations de Schrödinger quasi-périodiques sur l'axe réel lorsque les variétés iso-énergetiques adiabatiques sont étendues dans la direction des positions. Nous démontrons que, dans un intervalle d'énergie où ceci est le cas, le spectre est dans sa majeure partie purement absolument continu et que les fonctions propres généralisées correspondantes sont des fonctions de Bloch-Floquet.