  We provide upper bounds on the density of a symmetric generalized arithmetic
progression lacking nonzero elements of the form h(n) for natural numbers n, or
h(p) with p prime, for appropriate polynomials h with integer coefficients. The
prime variant can be interpreted as a multi-dimensional, polynomial extension
of Linnik's Theorem. This version is a revision of the published version. Most
notably, the properness hypotheses have been removed from Theorems 2 and 3, and
the numerology in Theorem 2 has been improved.
