Diophantine geometry over groups I: Makanin-Razborov diagrams

Manucsrit re?u le 4 janvier 2000.     

Diophantine geometry over groups V2: quantifier elimination II

This paper is the sixth in a sequence on the structure of sets of solutions to systems of equations in a free group, projections of such sets, and the structure of elementary sets defined over a free group. In the two papers on quantifier elimination we use the iterative procedure that validates the correctness of an AE sentence defined over a free group, presented in the fourth paper, to show that the Boolean algebra of AE sets defined over a free group is invariant under projections, hence, show that every elementary set defined over a free group is in the Boolean algebra of AE sets. The procedures we use for quantifier elimination, presented in this paper, enable us to answer affirmatively some of Tarski’s questions on the elementary theory of a free group in the last paper of this sequence. Received (resubmission): January 2004 Revision: November 2005 Accepted: March 2006 Partially supported by an Israel Academy of Sciences Fellowship.     

Diophantine geometry over groups III: Rigid and solid solutions

This paper is the third in a series on the structure of sets of solutions to systems of equations in a free group, projections of such sets, and the structure of elementary sets defined over a free group. In the third paper we analyze exceptional families of solutions to a parametric system of equations. The structure of the exceptional solutions, and the global bound on the number of families of exceptional solutions we obtain, play an essential role in our approach towards quantifier elimination in the elementary theory of a free group presented in the next papers of this series. The argument used for proving the global bound is a key in proving the termination of the quantifier elimination procedure presented in the sixth paper of the series. Partially supported by an Israel Academy of Sciences Fellowship.     

Diophantine geometry over groups V1: Quantifier elimination I

This paper is the first part (out of two) of the fifth paper in a sequence on the structure of sets of solutions to systems of equations in a free group, projections of such sets, and the structure of elementary sets defined over a free group. In the two papers on quantifier elimination we use the iterative procedure that validates the correctness of anAE sentence defined over a free group, presented in the fourth paper, to show that the Boolean algebra ofAE sets defined over a free group is invariant under projections, and hence show that every elementary set defined over a free group is in the Boolean algebra ofAE sets. The procedures we use for quantifier elimination, presented in this paper and its successor, enable us to answer affirmatively some of Tarski's questions on the elementary theory of a free group in the sixth paper of this sequence. Partially supported by an Israel Academy of Sciences Fellowship.     

Diophantine geometry over groups VI: the elementary theory of a free group

This paper is the sixth in a sequence on the structure of sets of solutions to systems of equations in a free group, projections of such sets, and the structure of elementary sets defined over a free group. In the sixth paper we use the quantifier elimination procedure presented in the two parts of the fifth paper in the sequence, to answer some of A. Tarski’s problems on the elementary theory of a free group, and to classify finitely generated (f.g.) groups that are elementarily equivalent to a non-abelian f.g. free group. Received (resubmission): January 2004 Revision: January 2006 Accepted: January 2006 Partially supported by an Israel Academy of Sciences fellowship.     

An iterative estimation and validation procedure for specification of semi-Markov models with application to hospital patient flow

This article presents a methodology to identify and specify a continuous time semi-Markov model of population flow within a network of service facilities. An iterative procedure of state space definition, population disaggregation, and parameter estimation leads to the specification of a model which satisfies the underlying semi-Markov assumptions. We also present a test of the impact of occupancy upon realizations of population flows. The procedure is applied to data describing the movement of obstetric patients in a large university teaching hospital. We use the model to predict length-of-stay distributions. Finally, we compare these results with those that would have been obtained without the procedure, and show the modified model to be superior.     

An iterative procedure for differential analysis of gene expression

Microarrays are a popular technology to study genes that are differentially expressed between two conditions. In this Note, we propose an iterative procedure to determine the biggest subset of non-differentially expressed genes. We prove a pseudo Markov relationship that allows practical computations. We obtain explicit expressions for FDR and the level of the proposed test at each step. To cite this article: A. Bar-Hen, S. Robin, C. R. Acad. Sci. Paris, Ser. I 337 (2003).     

An iterative procedure for determining an unknown spacewise-dependent coefficient in a parabolic equation

An inverse problem for the determination of an unknown spacewise-dependent coefficient in a parabolic equation is considered. The problem is reformulated as a nonclassical parabolic equation along with the initial and boundary conditions. The iterative fixed point projection method is applied to solve the reformulated problem. The comparison analysis of proposed method with a least square method and some numerical examples are presented.     

An iterative approximation procedure for the distribution of the maximum of a random walk

Let I(F) be the distribution function (d.f.) of the maximum of a random walk whose i.i.d. increments have the common d.f. F and a negative mean. We derive a recursive sequence of embedded random walks whose underlying d.f.'s F_k converge to the d.f. of the first ladder variable and satisfy FF₁F₂ on [0,∞) and I(F)=I(F₁)=I(F₂)=. Using these random walks we obtain improved upper bounds for the difference of I(F) and the d.f. of the maximum of the random walk after finitely many steps.     

An iterative procedure for approximating fixed points of relaxed monotone operators

Based on a modified iterative algorithm, fixed points of a combination of relaxed monotone and Lipschitz continuous operators in the context of the solvability of a class of associated generalized variational inequality problems are approximated     

Diophanting geometry over groups II: Completions,closures and formal solutions

This paper is the second in a series on the structure of sets of solutions to systems of equations in a free group, projections of such sets, and the structure of elementary sets defined over a free group. In the second paper we generalize Merzlyakov’s theorem on the existence of a formal solution associated with a positive sentence [Me]. We first construct a formal solution to a generalAE sentence which is known to be true over some variety, and then develop tools that enable us to analyze the collection of all such formal solutions. Partially supported by an Israel Academy of Sciences Fellowship.     

An iterative procedure for solving integral equations related to optimal stopping problems

We present an iterative algorithm for computing values of optimal stopping problems for one-dimensional diffusions on finite time intervals. The method is based on a time discretization of the initial model and a construction of discretized analogues of the associated integral equation for the value function. The proposed iterative procedure converges in a finite number of steps and delivers in each step a lower or an upper bound for the discretized value function on the whole time interval. We also give remarks on applications of the method for solving the integral equations related to several optimal stopping problems.     

On an iterative procedure for solving a routing problem with constraints

The generalized precedence constrained traveling salesman problem is considered in the case when travel costs depend explicitly on the list of tasks that have not been performed (by the time of the travel). The original routing problem with dependent variables is represented in terms of an equivalent extremal problem with independent variables. An iterative method based on this representation is proposed for solving the original problem. The algorithm based on this method is implemented as a computer program.     

An iterative method for the creation of structured hexahedral meshes over complex orography

In this paper we propose a technique for measuring the quality of hexahedral Cartesian meshes used to model meso-scale atmospheric circulation in 3D. It is used to verify the progress of a novel method for satisfying the Delaunay criterion for structured hexahedral meshes over complex orography with high gradients and wide gradient variability. Based on a simile with potential energy, the iterative method of mesh smoothing is shown to improve mesh quality with logarithmic convergence. The method is evaluated in a practical application in a specific geographic location.     

Metric Diophantine approximation over a local field of positive characteristic

The conjectures of Sprind?uk in the metric theory of Diophantine approximation are established over a local field of positive characteristic. In the real case, these were settled by D. Kleinbock and G.A. Margulis using a new technique which involved nondivergence estimates for quasi-polynomial flows on the space of lattices. We extend their technique to the positive characteristic setting.     

An iterative procedure for the solution of constrained nonlinear equations with application to optimization problems

LetH ₁ andH ₂ denote Hilbert spaces and suppose thatD is a subset ofH ₁. This paper establishes the local and linear convergence of a general iterative technique for finding the zeros ofG:DH ₂ subject to the general constraintP(x)=x, whereP:DD. The results are then applied to several classes of problems, including those of least squares, generalized eigenvalues, and constrained optimization. Numerical results are obtained as the procedure is applied to finding the zeros of polynomials in several variables.This work was supported by NSF grant G J 34737.     

Explicit upper bound of the solution-free region for a Diophantine equation over number fields

Lithuanian Mathematical Journal - It is known that there exist only finitely many trivial solutions of a certain Diophantine equation over number fields except for the case the rational number...