# Relative density of images of diophantine polynomials

My current research project involves sampling a sequence along non-constant polynomials with non-negative integer coefficients defined over the natural numbers, and I'd like to be able to say when two such polynomials are "independent".

Say for two polynomials of this type $p$ and $q$, that $q$ is independent of $p$ if \begin{equation*} \limsup_{n \to \infty} \frac{p(\mathbb{N}) \bigcap q(\mathbb{N}) \bigcap \{1,2,\ldots,n\}}{p(\mathbb{N})\bigcap \{1,2,\ldots,n\}} = 0 \end{equation*}

That is, $q$ is independent of $p$ if the relative upper asymptotic density of the image of $q$ in the image of $p$ is $0$. Say $q$ is dependent on $p$ if this property does not hold.

It's pretty easy to show that if $\deg(q)>\deg(p)$ then $p$ is independent of $q$ (though $q$ is not necessarily independent of $p$). However, I'm stuck classifying when $p$ and $q$ are independent when they are of the same degree. If we define $g_{mr}(n) = mn+r$, it seems like if $\deg(q)=\deg(p)$, then $p$ and $q$ are dependent on each other if and only if there exist $m$, $m'$, $r$, $r'$ such that $q \circ g_{mr} = p \circ g_{m'r'}$. The forward direction is trivial, but I'm having a lot of trouble with the reverse direction.

This problem can be viewed as a diophantine equation of the form $p(n)-q(m)=0$, and I'd like to know how these solutions are distributed. Unfortunately, all papers I've found that might be relevant have only classified whether there are finitely or infinitely many solutions for restricted classes of these polynomials. Even for quadratics it seems difficult. I know there exist recurrence relations that generate further solutions given one solution, but I don't know if these generate all solutions.

I could use Falting's theorem if I could show the algebraic curve defined by $p(x)-q(y)=0$ has genus $>0$ when $deg(p)=deg(q)>2$ and $p$ and $q$ are not equal under compositions of these linear functions. I do not know much algebraic geometry, so I was wondering if this condition seems likely to hold. When $p$ and $q$ are quadratics, I believe the problem can be reduced to Pell's equation, but I'm not sure.

Could you suggest any papers or theorems on the subject, or if I'm on the right track?

• Previously posted to m.se, math.stackexchange.com/questions/443173/… where I made some comments that OP has chosen not to acknowledge. – Gerry Myerson Jul 19 '13 at 12:52
• I am so sorry. I thought I had posted a response, but I see now that I had not. Thank you very much for your response there. I understand how to apply Siegel's theorem now, but I am still having trouble with Pell's equation. If I start with the general quadratic, I can reduce it to the equation for a hyperbola (I will post the exact equation soon, looking through my notes) but I am having trouble reducing it to Pell's equation from there. Do you have any other suggestions for how to use Pell's equation. Again, very sorry for not responding on stack exchange, and thank you. – Dylan Airey Jul 19 '13 at 19:07

In the case you are interested, $p(x)=q(y)$ with $\deg p = \deg q = d >2$, then the curve has $d$ points at infinity, so if the curve is irreducible, Siegel's theorem applies and you are done. It could happen that the curve is reducible with a component having one point at infinity (with asymptote $x=y$), e.g., if one polynomial is a reparametrization of the other. I guess you have to figure out when that happens.
• This has been carried out, even without the assumption $\deg p=\deg q$, by Bilu and Tichy. – Peter Mueller Jul 19 '13 at 17:17
• Just to amplify what Felipe said: since the question is about the case that $\text{deg} p = \text{deg} q > 2$, one really doesn't need Faltings' theorem. Under these hypotheses, a degree-$k$ factor of $p(x)-q(y)$ which is irreducible in $\mathbb{C}[x,y]$ will have $k$ points at infinity, so by Siegel's theorem the equation $p(m)=q(n)$ can only have infinitely many integral solutions if $p(x)-q(y)$ has a factor of degree at most $2$. Degree-$1$ factors are easy to detect, they just mean that $q(x)=p(ax+b)$. Degree-$2$ factors were determined in Bilu's paper "Quadratic factors of $f(x)-g(y)$" – Michael Zieve Aug 3 '13 at 0:43