When Shaunak posed this problem to me I suggested that $ c(n) = \frac {1}{n!}$, but I'm not 100% certain. We can suppose WLOG that $ b = 0$ and $ f(0) = 0$ due to translation invariance, so write $ f(x) = \sum_{i = 1}^{n} a_i {x \choose i}$ for some integers $ a_i$. We want to minimize $ \left| \frac {f(x)}{x} \right|$ over all choices of $ a_i$ and $ x$ such that the quotient is well-defined and nonzero. Lemma 1: For fixed $ x$, the minimum nonzero value of $ f(x)$ over all choices of $ a_i$ is $ \gcd \left( {x \choose 1}, {x \choose 2}, ... {x \choose n} \right)$. Proof. This is Bezout's identity. Lemma 2: $ \gcd \left( {x \choose 1}, {x \choose 2}, ... {x \choose n} \right) \ge \frac {x}{n!}$. Proof. Induction. I don't know a nice way to prove this. The conclusion follows; the equality case occurs whenever $ x$ is a multiple of $ n!$.

It looks like $ 1/(\text{lcm}\{1,2,\cdots,n\})$ to me. We have $ \binom{m}{k}=\frac{m}{k}\binom{m-1}{k-1}$, so $ \frac1{m}\binom{m}{k}=\frac1k\binom{m-1}{k-1}$ Multiply by that least common multiple $ L$, and all of the denominators are cleared. Also, if $ m$ is divisible by $ k$, $ \binom{m-1}{k-1}\equiv 1\mod k$. If $ m$ is a multiple of $ L$, we therefore have that the actual denominator of each $ \frac1k\binom{m-1}{k-1}$ is $ k$, and the common denominator is $ L$. That makes $ \frac{m}{L}$ the gcd of $ \{\binom{m}{1},\binom{m}{2},\cdots,\binom{m}{k}\}$ as desired for the equality case.

jmerry wrote: It looks like $ 1/(\text{lcm}\{1,2,\cdots,n\})$ to me. We have $ \binom{m}{k} = \frac {m}{k}\binom{m - 1}{k - 1}$, so $ \frac1{m}\binom{m}{k} = \frac1k\binom{m - 1}{k - 1}$ Multiply by that least common multiple $ L$, and all of the denominators are cleared. Also, if $ m$ is divisible by $ k$, $ \binom{m - 1}{k - 1}\equiv 1\mod k$. If $ m$ is a multiple of $ L$, we therefore have that the actual denominator of each $ \frac1k\binom{m - 1}{k - 1}$ is $ k$, and the common denominator is $ L$. That makes $ \frac {m}{L}$ the gcd of $ \{\binom{m}{1},\binom{m}{2},\cdots,\binom{m}{k}\}$ as desired for the equality case. when :$ c(n)=|\frac{f(a)-f(b)}{a-b}|$ where $ c(n)=\frac1{lcm(1,2,...,n)}$

Read the other post in the thread. Also, don't quote the entire preceding post. It just wastes space.

Can anybody post a complete solution ?

can MellowMelon post offical solution?

I've spent several days on that problem and I've really got much pleasure from it, even though I haven't got the full solution yet. Here's what I've done. Lemma: Assume the polynomial $ P$ with degree $ n$ is taking integers to integers. If we write $ P(x) = \frac {a_{n}}{b_{n}}x^{n} + \frac {a_{n - 1}}{b_{n - 1}}x^{n - 1} + ... + \frac {a_{1}}{b_{1}}x + \frac {a_{0}}{b_{0}}$, where numbers $ a_{1},...,a_{n},b_{1},...,b_{n}$ are integers and $ (a_{i},b_{i}) = 1$ for any $ i$, then $ lcm(b_{1},...,b_{n})\leq{n!}.$ Proof: Represent $ P$ is the following way: $ P(x) = L_{n}(x - 1)(x - 2)...(x - n) + L_{n - 1}(x - 1)(x - 2)...(x - (n - 1)) + ... + L_{2}(x - 1)(x - 2) + L_{1}(x - 1) + L_{0}$(Easy to notice that it can be done in an unique way). As $ P(m)$ is an integer for any integer value of $ m$, the numbers $ P(1),P(2),...,P(n)$ are all integers: $ P(1) = L_{0}$ is an integer. $ P(2) = L_1(2 - 1) + L_{0}$ is an integer. So, $ L_{1}$ is an integer. It's quite easy to prove bu induction that for any integer $ 0\leq{k}\leq{n - 1}$, $ k!\cdot{L_{k}}$ is an integer number. Now consider $ P(n + 1)$: $ P(n + 1) = L_{n}\cdot{n!} + L_{n - 1}2\cdot{3}\cdots{n} + ... + L_{k}(n - k + 1)...(n - 1)n + ... + L_{1}n + L_{0}$, but easy to prove that for any positive integer $ 1\leq{k}\leq{n}$, $ \frac {(n - k + 1)(n - k + 2)...n}{k!}$ is an integer (It's the same as $ \binom{n}{k}$). So, $ L_{k}(n - k + 1)(n - k + 2)...n)$ is an integer for any $ 0\leq{k}\leq{n - 1}$ but $ P(n + 1)$ is also an integer. It means that $ n!\cdot{L_{n}}$ is an integer too. As $ k!\cdot{L_{k}}$ is an integer and $ n\geq{k}$, $ n!\cdot{L_{k}}$ is an integer. Easy to see that $ \frac {a_{i}}{b_{i}}$ can be represented as a linear combination of numbers $ L_{0},...,L{n}$. It means that $ n!a_{i}$ is divisible by $ b_{i}$,(As ${ n!\cdot{\frac {a_{i}}{b_{i}}}}$ must be integer) but $ (a_{i},b_{i}) = 1$. So, $ b_{i}|n!$, which means that $ lcm(b_{0},...,b_{n})\leq{n!}$, Q.E.D. pent several days on that problem and I've really got much pleasure from it, even though I haven't got the full solution yet. Here's what I've done. Lemma: Assume the polynomial $ P$ with degree $ n$ is taking integers to integers. If we write $ P(x) = \frac {a_{n}}{b_{n}}x^{n} + \frac {a_{n - 1}}{b_{n - 1}}x^{n - 1} + ... + \frac {a_{1}}{b_{1}}x + \frac {a_{0}}{b_{0}}$, where numbers $ a_{1},...,a_{n},b_{1},...,b_{n}$ are integers and $ (a_{i},b_{i}) = 1$ for any $ i$, then $ lcm(b_{1},...,b_{n})\leq{n!}.$ Proof: Represent $ P$ is the following way: $ P(x) = L_{n}(x - 1)(x - 2)...(x - n) + L_{n - 1}(x - 1)(x - 2)...(x - (n - 1)) + ... + L_{2}(x - 1)(x - 2) + L_{1}(x - 1) + L_{0}$(Easy to notice that it can be done in an unique way). As $ P(m)$ is an integer for any integer value of $ m$, the numbers $ P(1),P(2),...,P(n)$ are all integers: $ P(1) = L_{0}$ is an integer. $ P(2) = L_1(2 - 1) + L_{0}$ is an integer. So, $ L_{1}$ is an integer. It's quite easy to prove bu induction that for any integer $ 0\leq{k}\leq{n - 1}$, $ k!\cdot{L_{k}}$ is an integer number. Now consider $ P(n + 1)$: $ P(n + 1) = L_{n}\cdot{n!} + L_{n - 1}2\cdot{3}\cdots{n} + ... + L_{k}(n - k + 1)...(n - 1)n + ... + L_{1}n + L_{0}$, but easy to prove that for any positive integer $ 1\leq{k}\leq{n}$, $ \frac {(n - k + 1)(n - k + 2)...n}{k!}$ is an integer (It's the same as $ \binom{n}{k}$). So, $ L_{k}(n - k + 1)(n - k + 2)...n)$ is an integer for any $ 0\leq{k}\leq{n - 1}$ but $ P(n + 1)$ is also an integer. It means that $ n!\cdot{L_{n}}$ is an integer too. As $ k!\cdot{L_{k}}$ is an integer and $ n\geq{k}$, $ n!\cdot{L_{k}}$ is an integer. Easy to see that $ \frac {a_{i}}{b_{i}}$ can be represented as a linear combination of numbers $ L_{0},...,L{n}$. It means that $ n!a_{i}$ is divisible by $ b_{i}$,(As ${ n!\cdot{\frac {a_{i}}{b_{i}}}}$ must be integer) but $ (a_{i},b_{i}) = 1$. So, $ b_{i}|n!$, which means that $ lcm(b_{0},...,b_{n})\leq{n!}$, Q.E.D. Easy to see also that any polynomial $ f$ taking integers to integers can be represented as $ f(x) = \frac {P(x)}{lcm(b_{0},...,b_{n})}$,where $ P$ is a polynomial with integer coefficients, but $ lcm(b_{0},...,b_{n})\leq{n!}$. So, $ c_{n}\geq{n!}$, because otherwise there would be a polynomial $ f$ and integer mu,bers $ a,b$ such that $ f(a)$ and $ f(b)$ are distinct and $ \frac {1}{n!} > \frac {P(a) - P(b)}{(a - b)lcm(b_{0}...,b_{n})}\geq{\frac {1}{n!}}$, which is obviously contradiction. (As $ P$ is having integer coefficients, $ \frac {P(a) - P(b)}{a - b}$ is an integer). Hence, $ c_{n}$ can't be less than $ \frac {1}{n!}$. Now we are left to produce a polynomial $ P$ such that $ lcm(b_{0},...,b_{b}) = n!$ and there exist two distinct integers $ x,y$ with $ P(x) - P(y) = x - y$. This polynomial can be like a $ P(x) = \frac {(x + 1)(x + 2)...(x + n)}{n!}$, which is obviously taking integers to integers. Note that for $ n = 3$, the polynomial $ P(x) = \frac {(5x^{3} - 179x)}{6}$ is such that $ P(x) - P(y) = x - y$ holds for $ (x,y) = (6,0)$.

Well, i'm reviving this post, but to post a complete solution. In fact, we have $c(n)= \frac{1}{lcm(1,2,...,n)}$. In order to prove this, we first prove that, for every polynomial $f$ taking integers to integers, we have $M (\frac{f(a)-f(b)}{a-b}) \in \mathbb{Z}$, where $M=lcm(1,2,...,n)$ and $a>b$ are integers. Let $g(x)=f(x+b)-f(b)$. Clearly, $g$ take intergers to integers, and $\frac{f(a)-f(b)}{a-b} = \frac{g(\delta)}{\delta}$, where $\delta = a-b$. Also, note that we can write $g(x)=\sum_{k = 1}^{n}a_i{x\choose k}$, with $a_i \in \mathbb{Z}$ and $a_0=0$, since $g(0)=0$. So, we have: $M \frac{g(\delta)}{\delta}= \frac{M}{\delta} ( \sum_{k = 1}^{n}a_k{ \delta \choose k}) = \frac{M}{\delta} ( \sum_{k = 1}^{n}a_k \frac{ \delta}{k}{ \delta - 1 \choose k -1}) =\sum_{k = 1}^{n}a_k \frac{M}{k}{ \delta - 1 \choose k -1}$, which is an integer, since $a_k , \frac{M}{k}, { \delta - 1 \choose k -1} \in \mathbb{Z}, \forall k=1, \dots , n; \delta \in \mathbb{Z}$. So, we proved that $M (\frac{f(a)-f(b)}{a-b}) \in \mathbb{Z}$, which implies $\left|\frac{f(a)-f(b)}{a-b}\right| \ge \frac{1}{M} = \frac{1}{lcm(1,2,...,n)}$ when $f(a)\ne f(b)$. Thus, we have $c(n) \ge \frac{1}{lcm(1,2,...,n)}$, since $c(n)$ is the largest. Now we only need to prove that $c(n)= \frac{1}{M}$ works. To do this, we want to find a polynomial $f_0(x)= \sum_{k = 1}^{n}a_i{x\choose k}$, with $a_i \in \mathbb{Z}$, such that $f_0(M)=1$. If that happens, we'll have $\left|\frac{f_0(M)-f_0(0)}{M-0}\right| = \frac{1}{M}$, showing that $c(n)= \frac{1}{M}$. Let $d=gcd({M \choose 1},{M \choose 2}, \dots, {M \choose n})$. If there's a prime $p$ such that $p|d$, then $p| {M \choose 1}$, since $d|{M \choose 1}$. Thus, $p|M$, which implies $p \le n$. Let $\alpha \in \mathbb{N}$ such that $p^{\alpha} \le n <p^{ \alpha +1}$. We have $d|{M \choose p^{\alpha}} \Rightarrow p|{M \choose p^{\alpha}}$, but this is a contradiction, since $M=M_0 . p^{\alpha}$, where $M_0$ isn't divisible by $p$ (you can see quickly that this is a contradiction using Lucas Theorem). So, $gcd({M \choose 1},{M \choose 2}, \dots, {M \choose n})=1$, and Bézout Theorem states that there exists $a_1,a_2, \dots, a_n \in \mathbb{Z}$ such that $\sum_{k = 1}^{n}a_i{x\choose k}=1$. This implies $f_0(M)=1$, which finishes the proof that $c(n)= \frac{1}{M}$ works.

Let $L_n=\text{lcm} (1,2,3,...,n)$. We claim that $c(n)=\frac{1}{L_n}$. Note that any polynomial $f(X)$ that maps the integers to the integers has a representation $f(X)=c_0+c_1\binom{X}{1}+c_2\binom{X}{2}+...+c_n\binom{X}{n}$. Lemma 1: $L_n\cdot\frac{\binom{a}{n}-\binom{b}{n}}{a-b}\in\mathbb{Z}$. Proof: Write $g(X)=\binom{X+b}{n}-\binom{b}{n}$. Note that $g(X)=d_1\binom{X}{1}+...+d_{n}\binom{X}{n}$. Now, $\frac{1}{X}\binom{X}{n}=\frac{1}{n}\binom{X-1}{n-1}$ and so the denominator of $\frac{g(X)}{X}$ must have size at most $L_n$; thus $L_n\cdot\frac{g(X)}{X}\in\mathbb{Z}$ as desired. $\blacksquare$ Now, write $T=\frac{f(a)-f(b)}{a-b}=\sum_{k=0}^n c_k\frac{\binom{a}{k}-\binom{b}{k}}{a-b}$. In particular, $v_p\left(c_k\frac{\binom{a}{k}-\binom{b}{k}}{a-b}\right)\ge -v_p(L_k)\ge -v_p(L_n)$, and thus $v_p(T)\ge -v_p(L_n)$, so $T\cdot L_n\in\mathbb{Z}$. Thus if $T\neq 0$, then $T\ge\frac{1}{L_n}$, so we established a lower bound on $c(n)$. We show that this lower bound is attainable. We claim that, for a suitable choice of $c_i$, $\frac{f(N!)-f(0)}{N!}=\frac{1}{L_n}$ for large $N$. First, note that $\frac{\binom{N!}{k}-\binom{0}{k}}{N!-0}=\frac{\binom{N!}{k}}{N!}=\frac{\binom{N!-1}{k-1}}{k}$. Moreover, no prime less than or equal to $k$ divides $\binom{N!-1}{k-1}$, as the expression can be written as $\prod_{i=1}^{k-1}\frac{N!-i}{i}$ and note that $\gcd\left(\frac{N!-i}{i}, L_k\right)=1$ for large $N$ and $k\le n$. In particular, this means that $\frac{f(N!)-f(0)}{N!-0}=\sum_{k=0}^{n} \frac{c_k t_k}{k}$ for $\gcd(t_k,k)=1$ fixed and some $c_k$. By Bezout, we can choose a suitable choice of $c_i$ such that the expression equals $\frac{1}{L_n}$, so we are done. $\square$

Let $g(x)=f(x+b)-f(b)$ and $m=a-b$. Then, $g(x)$ is an integer-valued polynomial with $g(0)=0$, and we want to find the largest $c(n)$ such that \[c(n)\le\left|\frac{g(m)}{m}\right|\]for all $m$. As $g$ is integer-valued with $g(0)=0$, we can use Newton interpolation and find integers $c_1,c_2,\ldots,c_n$ such that \[g(x)=c_1\binom x1+c_2\binom x2+\ldots+c_n\binom xn\]so \[\frac{g(m)}{m}=\frac{c_1\binom m1+c_2\binom m2+\ldots+c_n\binom mn}{m}=\frac{c_1\binom{m-1}0}1+\frac{c_2\binom{m-1}1}2+\ldots+\frac{c_n\binom{m-1}{n-1}}n\]which must be some integer divided by $\text{lcm}(1,2,\ldots,n)$, so $c(n)\ge\frac1{\text{lcm}(1,2,\ldots,n)}$. To show that $c(n)\le \frac1{\text{lcm}(1,2,\ldots,n)}$, note that a construction is to set $m=1$ so it suffices to find integers $c_1,c_2,\ldots,c_n$ such that $\frac{c_1}1+\frac{c_2}2+\ldots+\frac{c_n}n=\frac1{\text{lcm}(1,2,\ldots,n)}$, which is an easy exercise in induction and Bezout's lemma.

Let $L = \operatorname{lcm}(1,\dots,n)$. We claim the answer is $c(n) = 1/L$. By shifting suitably, we seek \[ c(n) = \min_{\substack{f(0)=0 \\ \deg f = n}} \min_{\substack{x \\ f(x) \neq 0}} \left\lvert \frac{f(x)}{x} \right\rvert. \]Taking the basis $\tbinom x1$, $\tbinom x2$, ..., $\tbinom xn$ for ${\mathbb Z} \to {\mathbb Z}$ polynomials, we may write $f(x) = a_1 \tbinom x1 + a_2 \tbinom x2 + \dots + a_n \tbinom xn$. Now for a fixed $x$ the smallest nonzero value of $f(x)$ across all choices of $f$ is exactly $\gcd_{1 \le k \le n} \tbinom xk$, by using Euclidean algorithm on $a_k$. So we now interchange the order of the $\min$ operators to obtain \[ \boxed{c(n) = \min_{x \neq 0} \frac{\left\lvert G(x) \right\rvert}{x}} \quad\text{where}\quad \boxed{G(x) \overset{\text{def}}{=} \gcd\left( \tbinom x1, \tbinom x2, \dots, \tbinom xn \right)}. \]First, we note $G(L) = 1$, since if $p^e$ exactly divides $L$ (even if $e=0$) then $p \nmid \tbinom{L}{p^e}$ by Lucas theorem, say. Thus $c(n) \le 1/L$. On the other hand since \[ L \cdot \binom xk = L \cdot \frac{x}{k} \binom{x-1}{k-1} = x \cdot \frac Lk \binom{x-1}{k-1} \in x \cdot {\mathbb Z} \]we see that $L \cdot G(x) \ge x$ for any $x \in {\mathbb Z}$. Hence $c(n) \ge 1/L$, as desired.

The following problem appears as an exercise in chapter 10 of PftB. It is cited as "MOSP 2001." Quote: Let $f$ be a polynomial with rational coefficients such that $f(n) \in \mathbb{Z}$ for all $n \in \mathbb{Z}$. Prove that for any integers $m$, $n$ the number \[\mathrm{lcm}[1, 2, \dots, \deg(f)] \cdot \frac{f(m) - f(n)}{m - n}\]is an integer.

The answer is $c(n)=1/d_n$ where $d_n:=\mathrm{lcm}(1,\ldots,n)$. We first show that $c(n)\le 1/d_n$. To do this, we need a lemma. Lemma 1: $\gcd\left[\binom{d_n}{1},\ldots,\binom{d_n}{n}\right]=1$. Proof of Lemma 1: Suppose that there was a common prime factor, call it $p$. Now, let $p^e$ be the largest power of $p$ that is at most $n$. We see that $e=\nu_p(d_n)$ (this is the key fact of the lcm we are using). Now, we claim that $\nu_p\left(\binom{n}{p^e}\right)=1$, which would be a contradiction. We have that $d_n=kp^e$ for $\gcd(k,p)=1$. For $0\le a<p^e$, we have $\nu_p(kp^e-a)=\nu_p(p^e-a)$ (if $a=0$ then this is obvious, and if not, both quantities are equal to $\nu_p(a)$). Thus, \[\nu_p((kp^e)(kp^e-1)\cdots(kp^e-p^e+1))=\nu_p((p^e)(p^e-1)\cdots(p^2-p^e+1)),\]so $\nu_p\left(\binom{n}{p^e}\right)=1$, which is the desired contradiction. $\blacksquare$ Now, by induction with Bezout's lemma as a base case, we have that there are integers $a_1,\ldots,a_n$ such that \[a_1\binom{d_n}{1}+\cdots+a_n\binom{d_n}{n}=1.\]Let $f(X)=a_1\binom{X}{1}+\cdots+a_n\binom{X}{n}$. Then, \[\frac{f(d_n)-f(0)}{d_n-0}=\frac{1}{d_n},\]so we must have have $c(n)\le 1/d_n$. We'll now show that $c(n)\ge 1/d_n$, which is the same as showing that \[\left|\frac{f(a)-f(b)}{a-b}\right|\ge\frac{1}{d_n}.\]We have a lemma. Lemma 2: $d_n\frac{f(a)-f(b)}{a-b}\in\mathbb{Z}$. Proof of Lemma 2: Let $\delta=a-b$. We see that \[g(\delta):=f(b+\delta)-f(b)\]is a polynomial in $\delta$ with degree at most $n$ that outputs integral values, and $g(0)=0$. Expand $g(X)$ in the binomial basis, so \[f(X)=a_1\binom{X}{1}+\cdots+a_n\binom{X}{n}\]for some rational numbers $a_1,\ldots,a_n$. Since $g(1)\in\mathbb{Z}$, we have $a_1\in\mathbb{Z}$. Now, since $g(2)\in\mathbb{Z}$, we deduce $a_2\in\mathbb{Z}$, and so on. Therefore, all the $a_i$ are integers. Now, $\frac{1}{X}\binom{X}{p}=\frac{1}{p}\binom{X-1}{p-1}$, so \[f(X)/X=\frac{a_1}{1}\binom{X-1}{0}+\frac{a_2}{2}\binom{X-1}{1}+\cdots+\frac{a_n}{n}\binom{X-1}{n-1}.\]In particular then, we see that \[\frac{f(a)-f(b)}{a-b}=g(\delta)/\delta=\frac{A}{d_n}\]for some integer $A$. Therefore, the lemma follows. $\blacksquare$ Now, since $\frac{f(a)-f(b)}{a-b}\ne 0$, and its an integer over $d_n$, its smallest possible absolute value is $1/d_n$, so $c(n)\ge 1/d_n$, as desired. Combining the two parts, we have $c(n)=1/d_n$. $\blacksquare$