Congruences, Trees, and $p$-adic Integers

Abstract:

Let $f$ be a polynomial in one variable with integer coefficients, and $p$ a prime. A solution of the congruence $f(x) \equiv 0 (\text {mod} p)$ may branch out into several solutions modulo $p^{2}$, or it may be extended to just one solution, or it may not extend to any solution. Again, a solution modulo $p^{2}$ may or may not be extendable to solutions modulo $p^{3}$, etc. In this way one obtains the “solution tree” $T = T(f)$ of congruences modulo $p^{\lambda }$ for $\lambda = 1,2,\ldots$. We will deal with the following questions: What is the structure of such solution trees? How many “isomorphism classes” are there of trees $T(f)$ when $f$ ranges through polynomials of bounded degree and height? We will also give bounds for the number of solutions of congruences $f(x) \equiv 0 (\text {mod} p^{\lambda })$ in terms of $p, \lambda$ and the degree of $f$.