If $n$ is squarefree, $k\ge 2$, then $\exists f\in\Bbb Z[x_1,\dots,x_k] : f(\overline x)\equiv 0\pmod n\iff \overline x\equiv \overline 0\pmod n$

Question

Starting from this question, we set $n=k=2$ and use the function $f\in\Bbb Z[x,y]$ where $f(x,y)=x\cdot y+x+y$, then the proofs applied to that question satisfy this case.

Note that for $k=1$ the function $f(x)=x$ satisfies the title statement (except the $k$ condition) for all $n$, so this case is considered not to be part of this question.

Note further that if $n$ is prime, the title statement is easy to prove:

Let $n\ge 2$ and $k\ge 2$ and let $m$ be the multiplicative order$\mod n$. The function $f\in\Bbb Z[x_1,\dots,x_k],f(\overline x)=\prod\limits_{i=1}^k(x^m-1)-(-1)^k$ will have value $f(\overline x)\equiv (-1)^k\pmod n$ whenever $\exists i:$GCD$(x_i, n)=1$ (since $x_i^m-1\equiv 0\pmod n$ in that case), so the important part to consider is $\forall i:$GCD$(x_i,n)\gt 1$. For prime $n$, this will occur exactly when $\overline x\equiv \overline 0\pmod n$, so that case need not be considered further.

What proof is there for the title statement for $n\ge 2,k\ge 2$ and $n$ is squarefree? (Notation: $\overline x\in\Bbb Z^k$ is the "vector $x$" having dimension $k$; $\overline 0$ is the "zero vector" i.e., a vector of specified size having all entries be $0$.)

To prove:

• For all $k\ge 1$ and squarefree $n$ there exists a function $f\in\Bbb Z[x_1,\dots,x_k] : f(\overline x)\equiv 0\pmod n\iff \overline x\equiv \overline 0\pmod n$ (proven, but feel free to offer an alternate proof, especially along the lines of the contrapositive)
• For all $k\ge 2$ and squareful $n$ no such function exists

Answer 1

If $R$ has an ideal $I$ where the multiplication from $R$ is $0$ on $I$ (which is true for $Z/p^{t+2}Z$ by taking $I$ to be the elements divisible by $p^{t+1}$, and false for $Z/nZ$ with $n$ squarefree), no polynomial in $k \geq 2$ variables meets the conditions of the problem. Fix a nonzero element $j \in I$ and let $(x_1,\dots,x_k)$ run through the $k$-tuples that have all but one coordinate equal to $0$, and the other coordinate equal to $j$. For our polynomial to be nonzero on these $k$-tuples, its degree $ \leq 1$ part must be $\sum a_i x_i$ with every $ja_i \neq 0$. But then we can set $y_1 = a_2j$ and $y_2 = -a_1j$ and let $Y$ be the $k$-tuple $(y_1,y_2, 0,0,0, \dots, 0)$. We have found a nonzero vector with $f(Y)=0$.

If $R$ is a finite field of $q$ elements, the constructions used in proving Chevalley-Warning type theorems suffice to form the desired polynomial, such as $f=1 - \prod(1-x_i^{q-1})$.

The Chinese remainder theorem argument shows that for any ring $R$ of characteristic $n > 0$, there is a polynomial in $k$ variables vanishing only at $(0,0,0...,0)$ if and only if there is one over every $p$-power torsion part $R_p$. There is a finite direct sum decomposition $R = \oplus R_{p_i}$ and the isomorphisms in both directions are integer linear combinations, which apply equally well to polynomials (with $\mathbb{Z}$ or $R$ coefficients). The problem therefore reduces to the case where $p^uR=0$ for a prime power $p^u > 1$. I think that for finite rings the problem is always reduced to one of the two cases listed above; solutions exist for finite fields and no other finite ring of characteristic a power of $p$. Taking direct sums we get the general classification. [And if the "I think..." is incorrect then at least we have a proof for the original problem.]

Answer 2

With $n$ squarefree, the ring $\def\Z{\mathbf Z}\Z/n\Z$ is a product of fields $\Z/p\Z$ for the prime divisors $p$ of$~n$, by the Chinese remainder theorem, and $(\Z/n\Z)[X_1,\ldots,X_k]$ is the product of the corresponding polynomial rings $R_p=(\Z/p\Z)[X_1,\ldots,X_k]$. So it suffices to find for each such$~p$ an element $f_p\in R_p$ with $f_p[\overline a]=0\iff\overline a=\overline 0$ for all $\overline a\in(\Z/p\Z)^k$. Given these, one can construct the corresponding element $f_n\in(\Z/n\Z)[X_1,\ldots,X_k]$ such that for each monomial in the $X_i$s, the coefficient of$~f$ reduces modulo$~p$ to the corresponding coefficient of$~f_p$, for all$~p$; such a coefficient exists (uniquely) by the Chinese remainder theorem. For $\overline a\in(\Z/n\Z)^k$, the reduction modulo$~p$ of $f_n[\overline a]$ is $f_p[\overline a]$, and this is zero for all$~p$ if and only if $\overline a=\overline 0\in(\Z/n\Z)^k$. Any lift$~f$ of $f_n$ to $\Z[X_1,\ldots,X_k]$ will answer the question.

The polynomial $f_p=(p-1)!^k-\prod_{i=1}^k\prod_{a=1}^{p-1}(X_i-a)\in\Z[X_1,\ldots,X_k]$ has the property of the question for $n=p$ prime, since the product is designed to give a factor divisible by$~p$ in its evaluation at $\overline a$ if and only if $\overline a\not\equiv\overline0\pmod p$, and the constant that it is subtracted from is the value of the product at$~\overline0$. Its reduction modulo$~p$ gives a suitable element in $(\Z/p\Z)[X_1,\ldots,X_k]$ for the above.