Let $A$ and $B$ be two monic polynomials with integers coefficients (in $\mathbb{Z}[x]$), with no integer roots, and sharing no roots in common. Let $r$ be the rational function such that $r(x) = \frac{A(x)}{B(x)}$ for all $x$ where $B$ is non-zero.
Let $E$ be the set of all integers $n$ satisfying $r(n) \in \mathbb{Z}$, and $C$ the cardinality (number of elements) of $E$. We can also see $C$ as the number of lattice points lying on the curve of the equation $y = r(x)$.
If the degrees of $A$ and $B$ are respectively $deg(A)$ and $deg(B)$, can we find an upper bound, in terms of $deg(A)$ and $deg(B)$, for the number C?
So far:
- Note that if we want $A$ to be monic, it is because otherwise the problem becomes too easy: we can for example set $A(x) = \prod_{i=1}^{n}{B(i)}$, we would then have $C \geq n$, but $n$ can be as big as we want, showing that such a maximum can't be expressed in terms of $deg(A)$ and $deg(B)$.
- This problem wouldn't be interesting if $C$ could be $\infty$, but we can prove by contradiction that it can't be. Let's suppose $E$ is an infinite set. Using polynomial long division, there must be two polyonimals $Q$ and $R$ in $\mathbb{Z}[x]$ with $deg(R) < deg(B)$ such that $A = QB + R$ (we know that $Q$ have integer coefficients because $B$ is monic, and $Q = 0$ if $deg(A) < deg(B)$).
$A = QB + R \iff \frac{A}{B} = Q + \frac{R}{B} \iff \frac{R}{B} = r –
Q$ which implies that for all $x \in E$ we have $\frac{R(x)}{B(x)}$
that is an integer, since $r(x)$ and $Q(x)$ also are, hence, on one
hand, there's an infinite number of integers $x$ such that
$\frac{R(x)}{B(x)}$ is an integer. On the other hand, since $deg(R) <
deg(B)$ we know that $R(x) \geq B(x)$ is true only for a finite
number of integers $x$, because if $|x|$ is beyond some value then
$R(x) < B(x)$. This leads to a contradiction. - Let denote the elements of $E$ with a sequence, $E = \{x_1,x_2,…,x_C\}$. By fixing $B$ and $E$ we can create a polynomial $A$ such that the above conditions are respected. We can set $A(x) = \prod_{i=1}^C{(x – x_i)} + \prod_{i=1}^C{B(x_i)}$, and we clearly see that $\frac{A(x_k)}{B(x_k)} = \prod_{i\neq k}{B(x_i)} \in \mathbb{Z}$. This means that the maximum value of $C$ is at least $deg(A)$, since in this example $deg(A) = C$. We can find many other polynomials that are of a certain form, such as $A(x) = \prod_{i=1}^{C}{(B(x) + x – x_i)}$, but they don't seem to help much as their degree is too big.
- Maybe examples of ordered pair $(A,B)$ where we have $C \geq deg(A) + 1$ are not too hard to find (if they exist), but I didn't dig too much into numeric examples.
Why such a question:
I hesitated posting this question, since it seems like one that many could've asked, but I didn't find anything. Yet, proofs of $E$ being finite are also given in this post.
The main motivation of the problem is that, if such a maximum exists, we can then find an algorithm that tells if a polynomial $B$ divides another another polynomial $A$ of known degrees, only by testing for some integer values of $x$ if $B(x) | A(x)$. Indeed, if $B$ divides $A$ as polynomials, then $\frac{A}{B}$ is a monic polynomial with integer coefficients (as said before it's because $B$ is itself monic), which if $B(x) | A(x)$ is not true for some integer $x$ then we know that $B$ cannot divide $A$ (we can stop the algorithm). But if the condition $B(x) | A(x)$ is satisfied for $C$ possible integer values of $x$, then we should deduce that $B$ divides $A$ and stop the algorithm.
The algorithm can only know when to stop if he has a formula of an upper bound for $C$, that's why I posted this. A formula for the maximum of $C$, and not only an upper bound, would even be better.
Maybe the condition for $A$ and $B$ to have no integer roots or no roots in common is unnecessary for the problem: if this actually doesn't avoid any problem, I will edit the post. There may also be a problem with the title, since the problem is more restricted than integer-valued polynomial, but I don't know for a better one, or maybe the problem can be generalized to integer-valued polynomials.
Edit (08/29/2021):
Actually, if $deg(A) > deg(B)$ such a maximum can't exist, if we only consider the degree: we can find many counterexamples. The idea is to start with an integer constant $l = \prod_{i=1}^{C}{B(x_i)}$. Then we set a polynomial $R$ of degree $deg(R) < deg(B)$ such that $R = lP$ where $P$ is any polynomial of degree $deg(R)$. Only thing left to do is to take any monic polynomial $Q$ of degree $deg(Q)$ and to set $A = QB + R$ where $deg(A) = deg(Q) + deg(B)$. But we have $\frac{A}{B} = Q + \frac{R}{B} = Q + \frac{P\prod_{i=1}^C{B(x_i)}}{B}$, which means $Q$ and $\frac{R}{B}$ are both integers when evaluated at $x \in E$, and then that $B(x_i) | A(x_i)$. But in this example we can basically choose $C$ to be as big as we want.
Maybe, for this case (where $deg(A) > deg(B)$), we have to reduce the problem further, and adding the data of upper bound and lower bound for all coefficients or the roots. Adding this hypothesis may lead us to remove the condition for A to be monic.
Best Answer
I got an answer for this question from a person. Actually $C$ doesn't have a maximum, we can construct many polynomials $B$ and $A$ for an arbitrary large size of $E$; the following family of counterexamples may further be generalized.
Set the constant term of $B$ to be $\pm 1$, and let $P$ be some monic polynomial with integer coefficients and $2 \leq deg P < deg B$, then set the polynom $A(x) = P(x) + kx$ with $k$ an integer (hence $deg A = deg P < deg B$ and A is monic). The idea is to find a $k$ such that $B(x) | A(x)$ for an arbitrary large number of integers $x$.
First, notice that $B(x)$ and $x$ are coprime, since $B(x) \equiv \pm 1 \text{ (mod $x$)}$, this allows us to construct the following sequence $(x_i)_{i\in [1,C]}$ (which will be our set $E$) with $C$ arbitrary large: first $x_1 \in \mathbb{N}$, and then we construct each next nerm with $x_{i+1} = LCM(B(x_i),B(x_{i-1}),...,B(x_1))$ where LCM is the least common multiple of the numbers. $B(x_{i+1})$ and $x_{i+1}$ are coprime, implying that $B(x_{i+1})$ and any $B(x_j)$ with $j \leq i$ are coprime since $x_{i+1}$ is a multiple of $B(x_j)$; hence all $B(x_j)$ with $1 \leq j \leq C$ are coprimes.
We now want to find/show there exists $k$ s.t $B(x_j) | A(x_j)$ for every term of our sequence, this can be written as $ \\ A(x_j) \equiv 0 \text{ (mod $B(x_j)$)} \\ \iff P(x_j) + kx_j \equiv 0 \text{ (mod $B(x_j)$)} \\ \iff -P(x_j) \equiv kx_j \text{ (mod $B(x_j)$)}$
But as $x_j$ and $B(x_j)$ are coprime, $x_j$ is invertible in $\mathbb{Z}/B(x_j)\mathbb{Z}$, and then we have a solution for $k$: $\\ \iff k \equiv -P(x_j)x_j^{-1} \text{ (mod $B(x_j)$)}$
This gives a system of equation, which gives remainders for $k$ when divided by the $B(x_j)$. But since the $B(x_j)$ are all coprime, the Chinese Remainder Theorem tell us that there exists such a solution for $k$ and how to find it, which finishes the construction of $A$ and then show that there's no such maximum for $C$ as it can be as large as we want.
It's clear that we can even generalize to more polynomials $A$ for a given polynomial $B$ with constant term $\pm 1$ for example by adding $x^nk$ instead of $xk$ to $P$, with $n \geq 0$. The question remains for the case where $B$ doesn't have constant term, but the previous result strongly suggests that there's also counterexamples for $B$ with cosntant term $\neq \pm 1$, and seems to be generalizable somehow (I will edit the post if such a thing is found).
It seems that there's actually no nice restriction to the polynomials such that a maximum can be find. If the coefficients/roots of $A$ and $B$ are lower and upper bounded it is clear that there's maximum, but if they're not it probably doesn't exist.