, 2009

Let $L(n) = \operatorname{lcm}(1, 2, \dots, n)$. We claim that $c(n) = \frac{1}{L(n)}$.

First we show that this $c(n)$ is a lower bound. For any choice of $f(x)$ and $(a, b)$, we can translate $f(x)$ vertically so that $f(b) = 0$, and then translate $f(x)$ horizontally so that $b = 0$. We only deal with this case. An $n$th degree polynomial with a root at $0$ which takes integers to integers can be written as
$$f(x) = \sum_{i=1}^{n} a_i \binom{x}{i},$$
where the $a_i$ are integers. Using this form for $f(x)$, we calculate $\frac{f(a)}{a}$ for some nonzero $a$:
$$\frac{f(a)}{a} = \frac{1}{a} \sum_{i=1}^{n} a_i \binom{a}{i} = \sum_{i=1}^{n} a_i \cdot \frac{\binom{a}{i}}{a} = \sum_{i=1}^{n} a_i \binom{a-1}{i-1} \cdot \frac{1}{i}$$
The $i$th summand in this sum is $\frac{1}{i}$ times the integer $a_i \binom{a-1}{i-1}$. Since $\frac{1}{i}$ is an integer multiple of $\frac{1}{L(n)}$, each summand in the sum is an integer multiple of $\frac{1}{L(n)}$, so does the $\frac{f(a)}{a}$. Hence for $f(a) \neq f(0) = 0$, we have that $\left| \frac{f(a)-f(0)}{a-0} \right| = \frac{k}{L(n)} \ge \frac{1}{L(n)}$; that is, $c(n)$ is a lower bound.

Second, we show that $c(n)$ is achievable, by finding certain $a_i$'s for $x = L(n)^2$ in
$$f(x) = \sum_{i=1}^{n} a_i \binom{x}{i}.$$
If $p$ is any prime that divides $L(n)$, then there is some $i \le n$ such that $p \nmid \frac{L(n)}{i}$, by the definition of the least common multiple. Thus
$$\gcd\left(\frac{L(n)}{1}, \frac{L(n)}{2}, \dots, \frac{L(n)}{i}, \dots, \frac{L(n)}{n}\right) = 1.$$
Let $1 \le i \le n$. We consider
$$\binom{L(n)^2 - 1}{i - 1} = \frac{(L(n)^2 - 1)(L(n)^2 - 2) \cdots (L(n)^2 - (i - 1))}{1 \cdot 2 \cdots (i - 1)}.$$
For any prime divisor $p$ of $i$, the power of $p$ which divides $L(n)^2$ is always larger than the power of $p$ which divides $k$, for any $k \le n$. Therefore the same number of factors of $p$ divide $L(n)^2-k$ and $k$. By matching these factors in the numerator and denominator, we find that $p$ does not divide $\binom{L(n)^2-1}{i-1}$; that is, $\gcd(i, \binom{L(n)^2-1}{i-1}) = 1$ for $1 \le i \le n$. Therefore, we conclude that
$$\gcd\left(\frac{L(n)}{1} \cdot \binom{L(n)^2 - 1}{1 - 1}, \dots, \frac{L(n)}{i} \cdot \binom{L(n)^2 - 1}{i - 1}, \dots, \frac{L(n)}{n} \cdot \binom{L(n)^2 - 1}{n - 1}\right) = 1.$$
By Bézout's lemma, there are integers $a_i$ such that
$$\sum_{i=1}^{n} a_i \frac{L(n)}{i} \binom{L(n)^2 - 1}{i - 1} = 1.$$
It follows that, for these $a_i$'s, we have
$$f(L(n)^2) = \sum_{i=1}^{n} a_i \binom{L(n)^2}{i} = \sum_{i=1}^{n} a_i \cdot \frac{L(n)^2}{i} \cdot \binom{L(n)^2 - 1}{i - 1} = L(n)$$
or
$$\frac{f(L(n)^2)}{L(n)^2} = \frac{1}{L(n)} = c(n)$$
completing our proof.

(Technically, we also need $a_n \ne 0$ to ensure that the polynomial has degree equal to $n$. However, if $a_n = 0$, then choose some $i$ with $a_i \ne 0$, and replace $a_n$ and $a_i$ by $a_n + \binom{L(n)^2}{i}$ and $a_i - \binom{L(n)^2}{n}$, respectively. Clearly, the resulting sequence $a'_i$ also satisfies $\sum_{i=1}^n a_i \binom{L(n)^2}{i} = L(n)$.)