Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $d$ be a positive integer greater than 2. Define an equivalence relation on monic integer polynomials of degree $d$: $f\sim g \iff f(k_1 x+k_2)=g(k_3 x+k_4)$ for some integers $k_1,...,k_4$.

Is there a number $m$ such that for any $m$ distinct integers, there is at most one equivalence class that attains these at integer coordinates?

I ask for $d>2$ since it is vacuous for $d=1$ (only one class) and it fails for $d=2$: $x^2-1$ and $2y^2$ are not in the same class and having infinitely many common values.

From some short calculations I think it is true that for $d+1$ (maybe a bit more) distinct values there are at most a finite number of equivalence classes possible, but I don't see how to bound the number of classes uniformly, let alone by 1.

share|improve this question
Does $k$ depend on $f$ and $g$? –  Anthony Quas Jan 20 '11 at 19:25
@darij: based on his example I think he means just outputs, and no given inputs to be paired with them, though I don't claim this changes much if anything. –  Adam Hughes Jan 20 '11 at 19:34
What do you mean by "one equivalence class that attains these"? Could you give a formal definition? –  Kevin O'Bryant Jan 20 '11 at 20:06
OK, now that you allowed affine transformations, I choose $m$ integers $p_1$, $p_2$, ..., $p_m$ which can be written both as values of $x^2-1$ and as values of $2y^2$. And I take $f(p_1)$, ..., $f(p_m)$. These are values of the polynomial $f(x^2-1)$ and of the polynomial $f(2x^2)$. Where is your god now? –  darij grinberg Jan 20 '11 at 20:09
This is becoming interesting ;) Let $u$ be a big number with over $9000$ different representations in the form $x^2+y^2$ (with $x$ and $y$ integers). Then, the polynomials $x^2$ and $u-x^2$ have many common values, and by composing them with an even-degree polynomial, you get two monic polynomials with many common values. They should not be affine-equivalent. –  darij grinberg Jan 20 '11 at 20:22
show 12 more comments

2 Answers

up vote 5 down vote accepted

You are asking for a condition on $f$ and $g$ such that the curve: $$C: f(y) - g(x) = 0$$ has a uniformly bounded number of rational points. Note that if $f$ and $g$ are equivalent under an affine transformation, then $C$ is divisible by a linear factor and is not reducible. The converse is almost true. Namely, as long as the degree of $f$ and $g$ is sufficiently large, and $f$ and $g$ are not of the form $a \circ b$ for polynomials $a$ and $b$ of degree $> 1$, then $C$ will be irreducible. (This follows from CFSG. Of course, using composition of functions one can create many degenerate examples: $P(y)^2 - Q(x)^2$ is divisible by $P(y) - Q(x)$. The example in the comments giving a example in even degrees arises in this way, by taking a degree two example and using composition.) If the degree $d$ of $f$ (and $g$) is prime, then $f$ and $g$ are certainly indecomposible, so let's concentrate on that case, since there are no reductions to smaller degree. For convenience, let's also only consider the case when $C$ is irreducible (if $d$ is prime, this is automatic if $d$ is sufficiently large, by the remark above.)

If $C$ has genus at least two, then $C$ will have only finitely many rational points (Faltings). Work of Caporaso, Harris, and Mazur:


suggests that the number of solutions may be even be bounded in terms of the genus, and hence in terms of the degree. Whether you believe Lang's conjectures or not, you are unlikely to disprove Lang's conjectures easily, so any negative example to your claim should come from a pair of functions $f$ and $g$ so that $C$ has small genus.

In small genus, we may have many rational points, but as far as integral points we also have Siegel's theorem to content with. A projective model $\widetilde{C}$ of $C$ is given by $Z^d f(Y/Z) - Z^d g(X/Z) = 0$. Setting $Z = 0$, we obtain the equation "at infinity" $Y^d - X^d = 0$, which has $d$ points over the complex numbers. Hence, assuming $d \ge 3$, $$\\# \widetilde{C} \setminus C \ge 3.$$ By Siegel's theorem we deduce $C$ has only finitely many integral solutions. Thus, when the degree $d$ is prime and sufficiently large (or more generally, providing one avoids degeneracies arising from the phenomena alluded to in the first paragraph), any $f$ and $g$ in different equivalence classes will only coincide on a fixed number of integers.

Your question, however, asks whether there is a uniform bound. There is certainly no uniform bound for Seigel's theorem, at least when the genus is $\le 1$. There is a standard ``renomalization'' trick which takes a curve with infinitely many rational points and produces a curve with many integral points. This trick works in this case. Specifically, suppose that $C: f(y) - g(x) = 0$ has infinitely many rational points. Then there certainly exists some integer $N$ such that $C$ has a bizillion points of the form $(u/N,v/N)$ (take $N$ to be a common denominator). We may then write down the different integral model: $$C': N^d f(y/N) - N^d g(x/N) = 0,$$ which now has a bizillion integral points $(u,v)$. This also allows one to answer your question in general degrees, simply by choosing $f$ and $g$ so that $C$ has infinitely many rational points, and then renomalizing appropriately. The easiest specific example would be to take $C$ of genus zero. For example, take $f = t^n$ and $g = t^{n-1}(t-1)$. Then $C: f(y) - g(x) = y^n - x^{n-1}(x-1)$ has genus zero, as can be seen from the paremetrization $$x = \frac{1}{1 - t^n}, \qquad y = \frac{t}{1 - t^n}.$$ From the above construction, there will exist positive integers $N$ such that the polynomials $t^n$ and $t^{n-1}(t - N)$ will take on the same bizillion values. This answers your question in the negative.

EDIT: I guess the last example can be made quite concrete. Let $$N = (1 - 2^d)(1 - 3^d)(1 - 4^d) \ldots (1 - M^d).$$ Then $t^d$ and $t^{d-1}(t-N)$ both take on the values $\displaystyle{\left(\frac{aN}{1 - a^d} \right)^d}$ for $a = 2, \ldots, M$.

share|improve this answer
What is CFSG ? –  Anton Geraschenko Jan 21 '11 at 3:32
Google says it's the China Fire and Security Group, also Community Financial Services Group, Combat Flight Simulator Group, ...., but here I suspect it's the Classification of Finite Simple Groups. –  Gerry Myerson Jan 21 '11 at 3:53
Dear Esperantist, do you know a reference for the statement involving the CFSG? I have been thinking about related problems and would be really interested in reading something on this. Thanks! –  damiano Jan 21 '11 at 10:04
So if I were to confine the question even further to "primitive" polynomials, in the sense that they are not the composition of polynomials of smaller degree, then Lang's conjectures imply a uniform bound? –  Dror Speiser Jan 21 '11 at 14:49
@Esperantist: thank you very much for the reference! You do bring hope... ;) –  damiano Jan 25 '11 at 12:09
add comment

This is not true. $f(x)$ and $f(2x)$ will not be in the same equivalence class in general, yet their images will agree on infinitely many points. Hence there is no fixed value $m$ such that any $m$ points determine a single equivalence class

share|improve this answer
ahhhhh. now that's true. then let's go all the way to all affine transformations! –  Dror Speiser Jan 20 '11 at 20:05
I don't get it. Did you mean to write $f(x) = g(ax+k)$? But even then you get more examples via $f(x)$ and $g(h(x))$ for polynomials $h$ of degree $> 1$. Or do I misunderstand the problem completely? –  Franz Lemmermeyer Jan 20 '11 at 20:12
Degree is fixed. –  Dror Speiser Jan 20 '11 at 20:16
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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