How can I find integers $a,b$ with $x^2+ax+b\approx 0$?

Question

Here

https://stackoverflow.com/questions/41857938/how-can-i-find-linear-dependencys-when-one-or-more-coefficients-are-fixed

I asked how I can find linear dependency's with PARI/GP, if one or more coefficients are fixed, for example

How can I find integers $a,b$ with $x^2+ax+b\approx 0$ ?

I know how to find such dependency's with PARI/GP , but not with fixed coefficients. I know the lin-dep and the qflll-command. Does anyone know modifications solving my problem, or does anyone know a mathematical trick that helps ?

Answer 1

I don't know PARI/GP but here is an algorithm that works for any affine function that does not represent a horizontal or vertical line. In particular it can be used with $$\ell\begin{pmatrix}a\\b\end{pmatrix} = x^2 + a x+b$$ for $x\neq 0$. Start with the matrix $$P=\left(p_1\,p_2 \, p_3\right) = \begin{pmatrix}0&1&0\\0&0&1\end{pmatrix}$$ and repeat the three steps below. Then after each round there will be increasingly accurate approximations in the quadruple of points $(p_1, p_1+p_2, p_1+p_3, p_1+p_2+p_3)$.

1. Find $\lambda \in \mathbb{Z}$ such that $$\ell P\begin{pmatrix}1\\0\\\lambda\end{pmatrix} \textrm{ and } \ell P\begin{pmatrix}1\\0\\\lambda+1\end{pmatrix}$$ have different signs.
2. Find $\mu \in \mathbb{Z}$ such that $$\ell P\begin{pmatrix}1\\1\\\mu\end{pmatrix} \textrm{ and } \ell P\begin{pmatrix}1\\1\\\mu+1\end{pmatrix}$$ have different signs.
3. Substitute $$P \leftarrow P \begin{pmatrix}1&0&0\\0&0&1\\\lambda&1&\mu-\lambda\end{pmatrix}$$

For example for $x = \pi$ the matrices after the first few rounds are $$ \begin{pmatrix}0&0&1\\-10&1&-4\end{pmatrix}, \begin{pmatrix}-1&1&2\\-6&-4&-7\end{pmatrix}, \begin{pmatrix}1&2&-3\\-13&-7&10\end{pmatrix}, \ldots $$ The best approximations found along the way are: $$ \pi^2 + \pi - 13 \textrm{ after one round}$$ $$ \pi^2 + 8 \pi - 35 \textrm{ after eight rounds}$$ $$ \pi^2 - 24393 \pi + 76623 \textrm{ after nine rounds}$$ $$ \ldots $$