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?

  • 2
    $\begingroup$ Previously posted to m.se, math.stackexchange.com/questions/443173/… where I made some comments that OP has chosen not to acknowledge. $\endgroup$ – Gerry Myerson Jul 19 '13 at 12:52
  • $\begingroup$ 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. $\endgroup$ – Dylan Airey Jul 19 '13 at 19:07

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.

| cite | improve this answer | |
  • 2
    $\begingroup$ This has been carried out, even without the assumption $\deg p=\deg q$, by Bilu and Tichy. $\endgroup$ – Peter Mueller Jul 19 '13 at 17:17
  • $\begingroup$ Thank you very much for your response. I have not studied much algebraic geometry yet, so I was unsure of how to apply Siegel's theorem. Also, Siegel's theorem does not give bounds for the solutions to such equations, and I would like to be able to do so for a stronger result. I've found results in this paper for the case when p and q are monic and p(x)-q(y) is irreducible over the rationals, but I haven't found any results for the general case. Do you know of any further results for bounding these solutions? $\endgroup$ – Dylan Airey Jul 20 '13 at 23:25
  • $\begingroup$ 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)$" $\endgroup$ – Michael Zieve Aug 3 '13 at 0:43
  • $\begingroup$ and an easier proof was given in a subsequent paper with the same title by Kulkarni, Mueller and Sury. $\endgroup$ – Michael Zieve Aug 3 '13 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.