Polynomial interpolation over the residue rings $Z_n$

We consider the problem of polynomial interpolation over the residue rings $Z_n$. The general case can be easily reduced to the case of $n=p^k$ due to the Chinese reminder theorem. In contrast to the interpolation problem over fields, the case of rings is much more complicated due to the existence of nonzero polynomials representing the zero function. Also, the result of interpolation is not unique in the general case. We compute, in the frame of the CAS system Singular, the Gröbner bases of ideals of null-polynomials over residue rings. This allows us to obtain a canonical form for the results of interpolation. We also describe a connection between estimates of the cardinality of interpolating sets and of the total number of permutation polynomials over the ring. As a consequence, we give a recurrence formula for the number of permutation polynomials over $Z_p^k$.