Diophantine Equations and Linear Recurrences

Diophantine equations appear when one searches for solutions of algebraic equations in two or more variables which are easy to represent as numbers like integers, or fractions. In the simplest case non-trivial case of equations of degree 2, called quadratic, this leads to the study of so–called Pell equations which is well understood although even here there are many open questions. In the next simplest case of equations of degree at least 3 which are points on elliptic curves it leads to looking at common values of intersections of two linearly recurrent sequences. The project addresses methods for efficiently computing such intersections when the sequences depend on some natural parameter. Examples are sequences like the Fibonacci sequence which starts with 0, 1 and each term is the sum of the preceding two terms and the questions being asked is which ones of the members of this sequence belong to some other similar sequence such as the powers of 2 for example. The project explores novel methods of dealing with such equations which combine traditional algebraic methods with elements from analysis in order to advance our understanding of the arithmetic of such numbers. The project has also an applied theoretical computer science component as it presents applications to classical problems from decidability theory such as the Skolem problem on the set of zeros of linear recurrences and the reachability problem.