Counting integers representable as images of polynomials modulo $n$

Abstract

Given a polynomial $f(x_1,x_2,\dots ,x_t)$ in $t$ variables with integer coefficients and a positive integer $n$, let $\alpha (n)$ be the number of integers $0\le a<n$ such that the polynomial congruence $f(x_1,x_2,\dots ,x_t)\equiv a(modn)$ is solvable. We describe a method that allows to determine the function $\alpha$ associated to polynomials of the form $c_1{x}_1^k+c_2{x}_2^k+\cdots +c_t{x}_t^k$. Then we apply this method to polynomials that involve sums and differences of squares, mainly to the polynomials $x^2+y^2,x^2-y^2$ and $x^2+y^2+z^2$.

15 pages