Suppose we're in the multivariate polynomial ring $\Bbb C[x_1,x_2,...,x_n]$, and we construct some quotient ring. I'm interested in the following case in particular:
- $\Bbb C[x_1,x_2,...,x_n]/(x_1^2-1,x_2^2-1,...,x_n^2-1)$
Given an arbitrary polynomial in this quotient ring, is there some general way to see if it factors within the ring?
I don't care if the algorithm is slow, I just want to understand the approach for quotient rings like these. I can't tell if this translates nicely into some easily solvable problem in the ambient complex multivariate polynomial ring, or if something else is needed here.
I'm particularly interested in polynomials where the coefficients are all $\pm 1$.
Well, your example $R=\Bbb C[x_1,x_2,...,x_n]/(x_1^2-1,x_2^2-1,...,x_n^2-1)$ is a very easy to understand ring: it is just isomorphic to $\mathbb{C}^{2^n}$. Explicitly, given a function $e:\{1,\dots,n\}\to \{-1,1\}$, define a homomorphism $R\to\mathbb{C}$ by sending $x_k$ to $e(k)$ for each $k$. This gives $2^n$ homomorphisms $R\to\mathbb{C}$ which together give a homomorphism $R\to\mathbb{C}^{2^n}$ which is an isomorphism. (There are many ways you can show it is an isomorphism--for instance, you can show it is surjective, and then conclude it must be injective as well since $R$ and $\mathbb{C}^{2^n}$ have the same finite dimension as $\mathbb{C}$-vector spaces.)
Assuming that you say $f$ "factors" if you can write $f=gh$ where neither $g$ nor $h$ is a unit, an element $f\in\mathbb{C}^{2^n}$ factors iff at least one of its coordinates is $0$. Indeed, if the $e$th coordinate of $f$ is $0$, then $f$ factors as $fh$ where $h$ is $1$ in every coordinate except the $e$th and $0$ in the $e$th coordinate. Conversely, if all the coordinates of $f$ are nonzero, $f$ is a unit, so $f=gh$ implies $g$ and $h$ are both units.
Explicitly in terms of polynomials, this means that $f\in R$ factors iff $f(\pm1,\pm1,\dots,\pm1)=0$ for some choice of signs.
If by "factors" you mean you can write $f=gh$ where neither $g$ nor $h$ is a unit multiple of $f$, then $f\in\mathbb{C}^{2^n}$ factors iff at least two of its coordinates are $0$. Indeed, if the $e$ and $e'$ coordinates are $0$, let $g$ be $f$ modified so that its $e$ coordinate is $1$, and let $h$ be $0$ on its $e'$ coordinate and $1$ on all others. Conversely, if $f$ has at most one nonzero coordinate and $f=gh$, then one of $g$ and $h$ must have the same set of nonzero coordinates as $f$, and thus be a unit multiple of $f$.