Wikipedia said that Gershgorin Circle Theorem was relevant. I’m not sure why so yet, but here’s a proof of that theorem anyways:Question:
Suppose \(f\) is a polynomial with small integer coefficients and that \(f(0)\neq 0\). Then, how small can the smallest root of \(f\) be in absolute value?
Theorem. Fix complex matrix \(A\). Let \(R_i = \sum_{j\neq i} |a_{ij}|\). Define \(D(x, r)\) to be a disc in the complex plane of radius \(r\) centered at \(x\).
All eigenvalues of \(A\) lie in \(\bigcup_{i} D(a_{ii}, R_i)\).
Proof. Let \(x\) be an eigenvector with \(Ax=\lambda x\) and let \(x_i\) be the largest absolute value coordinate of \(x\). Then \[ \sum_j a_{ij} x_j = \lambda x_i \] and so \[ |\lambda - a_ii| = \sum_{j\neq i} a_{ij} x_j/x_i. \] Using the triangle inequality we have \[ |\lambda - a_ii| \le \sum_{j\neq i} |a_{ij}| = R_i. \]
Theorem. Let \(P(x) =a_0+a_1x + \cdots + a_n x^{n}\) be a polynomial with \(a_0,a_n\neq 0\). Then the absolute values of the roots of \(x\) are all at most \(1+\max_i \frac{|a_i|}{|a_n|}\).
Proof. Let \(z\) be a root with absolute value larger than \(1\). \[ |a_n||z^{n}| = | \sum_{i=0}^{n-1} a_i z^{i}| \le \sum_{i=0}^{n-1}|a_i||z|^{i} \le \max_i |a_i| \sum_{i=0}^{n-1}|z|^{i} .\] Re-arranging it works.
Remark. The roots of \[a_0 + a_1x + \cdots a_n x^{n}\] and \[ a_n + a_{n-1}x +\cdots + a_0x^{n} \] are inverses of each other. So upper bounds on the absolute values of roots for one of them can be translated into lower bounds for the other.