Let $n$ be a natural number not equal to $0$. Find the maximum value of the constant $\psi(n)$ for which for every polynomial $f(x)$, with $\deg f = n$, with the property that for every integer $x$, $f(x)$ is also an integer, satisfies the following relation: $$\psi |x - y| \leq |f(x) - f(y)|$$ for every distinct integers for which $f(x) \neq f(y)$.
Attempt
I will prove that $\psi = 1$. For the polynomial $f(x) = x^n$ (obviously satisfies the property mentioned), and for $x = 1$, $y = 0$, we will get: $$\psi|1 - 0| \leq |1 - 0|$$ so $$\psi \leq 1$$
Now I shall prove that for every polynomial of every degree, $\psi = 1$ is a solution. I'm thinking somehow informal at the 'discrete' derivative, defined on discrete valued polynomials: $$\frac{\delta P}{\delta x} = \lim_{\ell \to 1} \frac{P(x + \ell) - P(x)}{\ell}$$
And what we need to prove it's true that, for each polynomial of non-zero degree, $\left|\frac{\delta P}{\delta x}\right| > 1$ for every $x$, and this looks true, since induction principles say that 'polynomial function beats the linear/identity' (while considering only discrete/integer values).
Question:
How can I formalize my proof? Is it correct? Have you any other suggestions of how to approach this type of problem?
We will show that $\psi(n) = \frac{1}{\text{lcm}(1,2,...,n)}$.
$\textbf{Background}:$
For a prime $p$ and a natural number $n$ we set
$M(p,n) = \max{\{j: p^j|n}\}$. I.e $M(3,15) = 1$.
$L(p,n) = \max{\{j: p^j \leq n\}}$. I.e $M(3,15) = 2$
$\text{lcm}(1,2,...n)$ is the least common multiple of the numbers $1,2,...,n$. I.e $\text{lcm}(1,2,3) = 6, \text{lcm}(1) = 1$.
$\textbf{Proof}:$
By translating the polynomial and making the constant term $0$, it suffices to show that whenever $f(y) \neq 0$ we have $$|f(y)| \geq \frac{1}{\text{lcm}(1,2,...,n)}|y|$$ whenever $f$ is a degree $n$ polynomial.
Set $$g_{n}(x) = \binom{x}{n} = \frac{x(x-1)...(x-n+1)}{n!}$$
Note by https://en.wikipedia.org/wiki/Integer-valued_polynomial that for a degree $n$ integer polynomial which vanishes at $0$, there exists constants $\lambda_{j} \in \mathbb{Z}$ so that
$$(1) \text{ }\text{ }\text{ }f(x) = \sum_{j=1}^{n}\lambda_{j}g_{j}(x).$$
We need to show for all $x$ that
$$\gcd_{1 \leq j \leq n}{g_{j}(x)} \geq \frac{|x|}{\text{lcm}(1,2,...,n)}.$$
As this will show whenever $f(x)$ is non-zero we have
$$|f(x)| \geq \frac{|x|}{\text{lcm}(1,2,...,n)}$$
when we consider $(1)$ and linear number theory.
Suppose $x \neq 0$ is of the form $bc$ where $\gcd(c,n!) = 1$, if some prime $p | b \Rightarrow p \leq n$ $\Rightarrow$ then $\gcd_{1 \leq j \leq n}{g_{j}(x)}$ is a multiple of $c$ and is a divisor of $x$ as $g_{1}(x) = x$. We have two cases
Case 1) Some prime $p |b$ satisfies $M(p,b)>L(p,n)$.
Set $M(p,b) = d$. so that $x = p^d\alpha$; note that
$$g_{j}(p^{d}\alpha) = \frac{(p^d\alpha)(p^d\alpha-1)...(p^d\alpha-j+1)}{j!}$$
So that $$M(p, g_{j}(p^{d}\alpha)) = d + M(p,(j-1)!) - M(p,j!) = d - M(p,j) \geq d - L(p,n)$$ with equality iff $j \equiv 0 \mod p^{L(p,n)}$, $1 \leq j \leq n$. Thus $$M(p, \gcd_{1 \leq j \leq n}{g_{j}(x)}) = d - L(p,n) = M(p,b) - L(p,n).$$
Case 2) Some prime $p|b$ satisfies $M(p,b) \leq L(p,n)$
Note that $g_{p^{M(p,n)}}(x) \not \equiv 0 \mod p$ as
Set $M(p,n) = d$ so that $x = p^d \alpha$. Note
$$g_{p^{d}}(x) = \frac{(p^d\alpha)(p^d\alpha-1)...(p^d\alpha-p^d+1)}{(p^d)(p^d-1)...1}$$
Thus $$M(p,g_{p^{d}}(x) ) = M(p,p^d\alpha)+M((p^d-1)!) - M(p,p^d)- M(p,(p^d-1)!) = 0.$$
Thus $$p \not \div \gcd_{1 \leq j \leq n}{g_{j}(x)} $$.
Hence by the above cases, we have the equality
$$\gcd_{1 \leq j \leq n}{g_{j}(x)} = \prod_{p, p \text{ prime},\text{ } p|x,\text{ } 1\leq p \leq n,\text{ } M(p,x) \geq L(p,n)}p^{M(p,x)-L(p,n)}\prod_{p, p\text{ prime }p >n}p^{M(p,x)}$$
$$\geq \frac{|x|}{\prod_{p, p \text{ prime},\text{ } 1\leq p \leq n}p^{L(p,n)}} = \frac{|x|}{\text{lcm}(1,2,...,n)}$$
with equality iff $x$ is a multiple of $\text{lcm}(1,2,...,n)$. This shows that $\psi(n) \geq \frac{1}{\text{lcm}(1,2,...,n)}$. Now consider $y = \text{lcm}(1,2,...,n)$. Note $\text{gcd}_{1 \leq j \leq n}(g_{j}(y)) = 1$. Hence by $(1)$ there exists constants $\lambda_{j} \in \mathbb{Z}$ so that
$$\sum_{j=1}^{n}\lambda_{j}g_{j}(y) = 1$$ so that
$$|\sum_{j=1}^{n}\lambda_{j}g_{j}(y)-\sum_{j=1}^{n}\lambda_{j}g_{j}(0)| = 1 = \frac{1}{\text{lcm}(1,2,...,n)}|y|.$$
This finishes the proof.