Roots of polynomials modulo prime powers (Q1367589)

For \(n\in\mathbb{N}\), a subset \(R\) of \(\mathbb{Z}/n\mathbb{Z}\) is called a root set modulo \(n\) provided that there exists a polynomial \(f(x)\) such that \(f(\alpha)\equiv 0\pmod n\) if and only if \(\alpha\in R\). The trivial cases are the empty set and \(\mathbb{Z}/n\mathbb{Z}\), which are always root sets modulo \(n\). Also, for \(p\) a prime, \(\mathbb{Z}/p\mathbb{Z}\) is a root set modulo \(p\). However, in general, root sets are rare. The seminal works on root sets modulo \(n\) are [\textit{M. M. Chojnacka-Pniewska}, Ann. Polon. Math. 3, 9-12 (1956; Zbl 0071.03803); and \textit{W. Sierpiński}, Ann. Polon. Math. 1, 89-90 (1954; Zbl 0055.27101)]. The authors of the paper under review provide methods for efficient computation of the number of roots sets modulo a prime power. One result established is that only a small portion of all possible polynomials modulo \(p^k\) need be solved to determine the total number of root sets modulo \(p^k\). In particular, only the number of root sets modulo a prime power \(p^k\) containing only multiples of \(p\) needs to be determined. The paper concludes with a section on numerical results including a table giving values for the above.