Let $x \in \mathbb{R}$ and let $\epsilon > 0$, can we always find an integer $n$ and a monic polynomial $f$ of degree $n$ with integer coefficients and complex roots $(x_1, \ldots, x_n)$ such that $|x_1-x| + \sum_{i=2}^n|x_i| < n \epsilon$?
Namely, we are looking for a polynomial where exactly one root is very close to x while the other roots are close to 0.
If so, is there an efficient way to compute such a polynomial?
The motivation is in finding integer recurrences that closely approximate a geometric growth with a factor $x$.
The answer to your question is YES. Let $n=\lfloor \frac{1}{\epsilon} \rfloor$ so that $n\epsilon \geq 1$. Then, you can take $x_1$ to be the nearest integer to $x$ (so $|x_1-x|\leq 1 \leq n\epsilon$) and $x_2=x_3=\ldots=x_n=0$, and $f(t)=(t-x_1)(t-x_2)\ldots(t-x_n)$.