Integer values of polynomials

Let $f(X)$ be a polynomial with rational coefficients, $S$ be an infinite subset of the rational numbers and consider the image set $f(S)$. If $g(X)$ is a polynomial such that $f(S)=g(S)$ we say that $g$ \emph{parametrizes} the set $f(S)$. Besides the obvious solution $g=f$ we may want to impose some conditions on the polynomial $g$; for example, if $f(S)\subset\Z$ we wonder if there exists a polynomial with integer coefficients which parametrizes the set $f(S)$. Moreover, if the image set $f(S)$ is parametrized by a polynomial $g$, there comes the question whether there are any relations between the two polynomials $f$ and $g$. For example, if $h$ is a linear polynomial and if we set $g=f\circ h$, the polynomial $g$ obviously parametrizes the set $f(\Q)$. Conversely, if we have $f(\Q)=g(\Q)$ (or even $f(\Z)=g(\Z)$) then by Hilbert's irreducibility theorem there exists a linear polynomial $h$ such that $g=f\circ h$. Therefore, given a polynomial $g$ which parametrizes a set $f(S)$, for an infinite subset $S$ of the rational numbers, we wonder if there exists a polynomial $h$ such that $f=g\circ h$. Some theorems by Kubota give a positive answer under certain conditions. The aim of this thesis is the study of some aspects of these two problems related to the parametrization of image sets of polynomials. \bigskip In the context of the first problem of parametrization we consider the following situation: let $f$ be a polynomial with rational coefficients such that it assumes integer values over the integers. Does there exist a polynomial $g$ with integer coefficients such that it has the same integer values of $f$ over the integers? This kind of polynomials $f$ are called \emph{integer-valued} polynomials. We remark that the set of integer-valued polynomials strictly contains polynomials with integer coefficients: take for example the polynomial $X(X-1)/2$, which is integer-valued over the set of integers but it has no integer coefficients. So, if $f$ is an integer-valued polynomial, we investigate whether the set $f(\Z)$ can be parametrized by a polynomial with integer coefficients; more in general we look for a polynomial $g\in\Z[X_1,\ldots,X_m]$, for some natural number $m\in\N$, such that $f(\Z)=g(\Z^m)$. In this case we say that $f(\Z)$ is $\Z$-\emph{parametrizable}. In a paper of Frisch and Vaserstein it is proved that the subset of pythagorean triples of $\Z^3$ is parametrizable by a single triple of integer-valued polynomials in four variables but it cannot be parametrized by a single triple of integer coefficient polynomials in any number of variables. In our work we show that there are examples of subset of $\Z$ parametrized by an integer-valued polynomial in one variable which cannot be parametrized by an integer coefficient polynomial in any number of variables. If $f(X)$ is an integer-valued polynomial, we give the following characterization of the parametrization of the set $f(\Z)$: without loss of generality we may suppose that $f(X)$ has the form $F(X)/N$, where $F(X)$ is a polynomial with integer coefficients and $N$ is a minimal positive integer. If there exists a prime $p$ different from $2$ such that $p$ divides $N$ then $f(\Z)$ is not $\Z$-parametrizable. If $N=2^n$ and $f(\Z)$ is $\Z$-parametrizable then there exists a rational number $\beta$ which is the ratio of two odd integers such that $f(X)=f(-X+\beta)$. Moreover $f(\Z)=g(\Z)$ for some $g\in\Z[X]$ if and only if $f\in\Z[X]$ or there exists an odd integer $b$ such that $f\in\Z[X(b-X)/2]$. We show that there exists integer-valued polynomials $f(X)$ such that $f(\Z)$ is $\Z$-parametrizable with a polynomial $G(X_1,X_2)\in\Z[X_1,X_2]$, but $f(\Z)\not=g(\Z)$ for every $g\in\Z[X]$. \bigskip In 1963 Schinzel gave the following conjecture: let $f(X,Y)$ be an irreducible polynomial with rational coefficients and let $S$ be an infinite subset of $\Q$ with the property that for each $x$ in $S$ there exists $y$ in $S$ such that $f(x,y)=0$; then either $f$ is linear in $Y$ or $f$ is symmetric in the variables $X$ and $Y$. We remark that if a curve is defined by a polynomial with Schinzel's property then its genus is zero or one, since it contains infinite rational points; here we use a theorem of Faltings which solved the Mordell conjecture (if a curve has genus greater or equal to two then the set of its rational points is finite). We will focus our attention on the case of rational curves (genus zero). Our objective is to describe polynomials $f(X,Y)$ with Schinzel's property whose curve is rational and we give a conjecture which says that these rational curves have a parametrization of the form $(\varphi(T),\varphi(r(T)))$. This problem is related to the main topic of parametrization of image sets of polynomials in the following way: if $(\varphi(T),\psi(T))$ is a parametrization of a curve $f(X,Y)=0$ (which means $f(\varphi(T),\psi(T))=0$), where $f$ is a polynomial with Schinzel's property, let $S=\{\varphi(t)|t\in S'\}$ be the set of the definition of Schinzel, where $S'\subset\Q$. Then for each $t\in S'$ there exists $t'\in S'$ such that $\psi(t)=\varphi(t')$, hence $\psi(S')\subset\varphi(S')$. So, in the case of rational curves, the problem of Schinzel is related to the problem of parametrization of rational values of rational functions with other rational functions (we will show that under an additional hypothesis we can assume that $(\varphi(T),\psi(T))$ are polynomials). In particular, if $(\varphi(T),\psi(T))$ is a parametrization of a curve defined by a symmetric polynomial, then $\psi(T)=\varphi(a(T))$, where $a(T)$ is an involution (that is $a\circ a=Id$). So in the case of rational symmetric plane curves we have this classification in terms of the parametrization of the curve. It turns out that this argument is also related to Ritt's theory of decomposition of polynomials. His work is a sort of "factorization" of polynomials in terms of indecomposable polynomials, that is non-linear polynomials $f$ such that there are no $g,h$ of degree less than $\deg(f)$ such that $f=g\circ h$. The indecomposable polynomials are some sort of "irreducible" elements of this kind of factorization. \vspace{1.5cm} % 1o capitolo In the first chapter we recall some basic facts about algebraic function fields in one variable, the algebraic counterpart of algebraic curves. In particular we state the famous Luroth's theorem, which says that a non trivial subextension of a purely trascendental field of degree one is purely trascendental. We give the definition of minimal couple of rational functions that we will use later to characterize algebraically a proper parametrization of a rational curve. We conclude the chapter with the general notion of valuation ring of a field and we characterize valuation rings of a purely trascendental field in one variable (which corresponds geometrically to the Riemann sphere, if for example the base field is the field of the complex numbers). Moreover valuation rings of algebraic function fields in one variable are discrete valuation rings. \bigskip %2o capitolo In the second chapter we state the first theorem of Ritt, which deals with decomposition of polynomials with complex coefficients with respect to the operation of composition. In a paper of 1922 Ritt proved out that two maximal decompositions (that is a decomposition whose components are neither linear nor further decomposable) of a complex polynomial have the same number of components and their degrees are the same up to the order. We give a proof in the spirit of the original paper of Ritt, which uses concepts like monodromy groups of rational functions, coverings and theory of blocks in the action of a group on a set. %Several other proof of this theorem have been given after that, This result can be applied in the case of an equation involving compositions of polynomials: thanks to Ritt's theorem we know that every side of the equation has the same number of indecomposable component. \bigskip %3o capitolo In the third chapter we give the classical definition of plane algebraic curves, both in the affine and projective case. We show that there is a bijection between the points of a non-singular curve and the valuation rings of its rational function field (which are called places of the curve). More generally speaking, if we have a singular curve $C$, the set of valuation rings of its rational function field is in bijection with the set of points of a non-singular model $C'$ of the curve (that is the two curves $C$ and $C'$ are birational), called desingularization of the curve. Then we deal with curves whose points are parametrized by a couple of rational functions in one parameter; we call these curves rational. From a geometric point of view a rational curve has desingularization which is a compact Riemann surface of genus zero, thus isomorphic to $\mathbb{P}^1$. Finally we expose some properties of parametrizations of rational curves; we show a simple criterium which provides a necessary and sufficient condition that lets a rational curve have a polynomial parametrization in terms of places at infinity. \bigskip %4o capitolo In the fourth chapter we study the aforementioned conjecture of Schinzel. For example, if $f(X,Y)=Y-a(X)$ then by taking $S$ the full set of rational numbers we see that the couple $(f,S)$ satisfies the Schinzel's property. If $f$ is symmetric and the set of rational points of the curve determined by $f$ is infinite, then if we define $S$ to be the projection on the first coordinate of the rational points of the curve we obtain another example of polynomial with the above property. The hypothesis of irreducibility of the polynomial $f$ is required because we want to avoid phenomenon such as $f(X,Y)=X^2-Y^2$ and $S=\Q$, where $f$ is neither linear nor symmetric. In general if a polynomial $f(X,Y)$ has $X-Y$ as a factor, then it admits the full set of rational numbers as set $S$. Another example is the following (private communication of Schinzel): let $$f(X,Y)=(Y^2-XY-X^2-1)(Y^2-XY-X^2+1)$$ and $S=\{F_n\}_{n\in\N}$, where $F_n$ is the Fibonacci sequence which satisfies the identity $F_{n+1}^2-F_{n+1}F_n-F_n^2=(-1)^n$ for each natural number $n$; if $f_1,f_2\in\Q[X,Y]$ are the two irreducible factors of $f$ then for each $n\in\N$ the couple of integers $(F_n,F_{n+1})$ is a point of the curve associated to the polynomial $f_1$ or $f_2$, according to the parity of $n$. Zannier has recently given the following counterexample to Schinzel's conjecture: $$f(X,Y)=Y^2-2(X^2+X)Y+(X^2-X)^2$$ with $S$ equal to the set of rational (or integer) squares. The idea is the following: it is well known that for each couple of rational functions $(\varphi(t),\psi(t))$ with coefficients in a field $k$ there exists a polynomial $f\in k[X,Y]$ such that $f(\varphi(t),\psi(t))=0$. In fact $k(t)$ has trascendental degree one over $k$; we also say that $\varphi$ and $\psi$ are algebraically dependent. Moreover if we require that the polynomial $f$ is irreducible then it is unique up to multiplication by constant. This procedure allows us to build families of polynomials with Schinzel's property: it is sufficient to take couples of rational functions $(\varphi(t),\varphi(r(t)))$, where $\varphi(t),r(t)$ are rational functions. If we consider the irreducible polynomial $f\in\Q[X,Y]$ such that $f(\varphi(t),\varphi(r(t)))=0$ and the set $S=\{\varphi(t)|t\in\Q\}$, we see that $(f,S)$ has Schinzel's property. In particular Zannier's example is obtained from the couple of rational functions $(\varphi(t),r(t))=(t^2,t(t+1))$. If $\deg(\varphi)>1$ and $\deg(r(t))>1$ then it turns out that $f$ is neither linear nor symmetric in $X$ and $Y$, but it is a polynomial with Schinzel's property. \bigskip %5o capitolo In the last chapter we deal with the problem of parametrization of integer-valued polynomials and we prove the results mentioned at the beginning of this introduction. The idea of the proof is the following: let $f(X)=F(X)/N$ be an integer-valued polynomial as above; since the set of integer-valued polynomials is a module over $\Z$, we can assume that $N$ is a prime number $p$. We remark that a bivariate polynomial of the form $f(X)-f(Y)$ has over $\Q$ only two linear factors; moreover, the set of integer values $n$ such that there exists $q\in\Q$ such that $(n,q)$ belongs to an irreducible component of the curve $f(X)-f(Y)=0$ which is not linear in $Y$, has zero density, by a theorem of Siegel. If $f(\Z)$ is $\Z$-parametrizable by a polynomial $g\in\Z[X_1,\ldots,X_m]=\Z[\underline{X}]$ then by Hilbert's irreducibility theorem there exists $Q\in\Q[\underline{X}]$ such that $F(Q(\underline{X}))=pg(\underline{X})$; we obtain necessary conditions for such polynomial $Q$ in order to satisfy the previous equality. In the same hypothesis, for each $n\in\Z$ there exists $\underline{x}_n\in\Z^m$ such that $f(n)=f(Q(\underline{x}_n))$. So we study how the points $(n,Q(\underline{x}_n))$, for $n\in\Z$, distribute among the irreducible components of the curve $f(X)-f(Y)=0$; by the aforementioned theorem of Siegel it turns out that, up to a subset of density zero of $\Z$, they belong to components determined by linear factors of $f(X)-f(Y)$. For each of them, the projection on the first component of this kind of points is a set of integers contained in a single residue class modulo the prime $p$. So if $p$ is greater then two, which is the maximum number of linear factors of a bivariate separated polynomial over $\Q$, the set $f(\Z)$ is not $\Z$-parametrizable. The problem of factorization of bivariate separated polynomials, that is polynomials of the form $f(X)-g(Y)$, is a topic which has been intensively studied for years (Cassels, Fried, Feit, Bilu, Tichy, Zannier, Avanzi, Cassou-Noguès, Schinzel, etc...) Our next aim is the classification of the integer-valued polynomials $f(X)$ such that $f(\Z)$ is parametrizable with an integer coefficient polynomial in more than one variable (for example $f(X)=3X(3X-1)/2$). I conjecture that such polynomials (except when $f\in\Z[X]$) belong to $\Z[p^kX(p^kX-a)/2]$, where $p$ is a prime different from $2$, $a$ is an odd integer coprime with $p$ and $k$ a positive integer. I show in my work that if $f(X)$ is such a polynomial, then $f(\Z)$ is $\Z$-parametrizable. Moreover we want to study the case of number fields, that is the parametrization of sets $f(O_K)$, where $O_K$ is the ring of integers of a number field $K$ and $f\in K[X]$ such that $f(O_K)\subset O_K$, with polynomials with coefficients in the ring $O_K$.