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?



Relative density of images of diophantine polynomials
Faltings theorem seems overkill here. As Gerry suggested, you should use Siegel's theorem since you are dealing with integer points and the hypotheses are easier to check. It states that an affine irreducible curve has finitely many integer points unless it is of genus zero and has at most two points at infinity.


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.


