Consider variables $x_i \in \{0,1\}$ each variable is idempotent, that is, ${x_i}^2=x_i$. Now consider polynomials in $n$ variables where each evaluation across all $x_i$ is either $0$ or $1$.
In 1 variable we have the polynomials
- $0$
- $1-x_1$
- $x_1$
- $1$
These polynomials are made by varying $c_i$ in the expression
$c_1 x_i + c_2(1-x_i)$ for $c_i \in \{0,1\}$
In 2 variables we have the polynomials
- $0$
- $1-x_1-x_2+x_1x_2$
- $x_2 - x_1x_2$
- $x_1 - x_1x_2$
- $x_1x_2$
- $1-x_1$
- $1-x_2$
- $1-x_1-x_2 + 2x_1x_2$
- $x_1 + x_2 - 2x_1x_2$
- $x_2$
- $x_1$
- $1-x_1x_2$
- $1-x_1+x_1x_2$
- $1-x_2+x_1x_2$
- $x_1+x_2-x_1x_2$
- $1$
Again, made by varying $c_i \in \{0,1\}$ for the expression
$c_1 x_1x_2 + c_2x_1(1-x_2) + c_3(1-x_1)x_2 + c_4 (1-x_1)(1-x_2)$
What I would like to know is: given a polynomial in $n$ variables, how can I determine whether or not the polynomial is one that I am interested in without checking all outputs of the function? I could square the expression to see if it changes but there are a potential $2^n$ terms, so I would rather avoid that if possible.
The second question, is there a name for this set of polynomials? I know they are related to Boolean algebra but I don't know if they're important enough to have been given a name.
Finally, does combining the set of polynomials with the operation $\times$ turn these polynomials into a group? It satisfies the axioms but the use of $0$ seems to make it trivial.
There is a recursive way to do this. Let $Z_n$ be the set of boolean polynomials of degree $n$ that evaluate to $0$ or $1$. Let $p(x_1,...,x_n) \in Z_n$ be given. Write $p = x_1 g(x_2,...,x_n) + f(x_2,...,x_n)$. By construction, $g$ and $f$ must have degree at most $n-1$. Moreover, $p \in Z_n$ if and only if $g+f \in Z_{n-1}$ and $f \in Z_{n-1}$ (see this by putting $x_1 = 0$ or $1$).
With regard to your question about it being a group, as mentioned in the comment above, it has zero divisors so that won't work. I don't expect any nice algebraic structure on $Z_n$ because it is the union of $\ker(\text{ev})$ and $\ker(\text{ev})+1$, where $\text{ev}$ is the evaluation map: $$ \mathbb{Z}[x_1,...,x_n]/(x_i^2-x_i) \to \mathbb{Z} $$ The former is an ideal and the latter is a translate of that ideal. There isn't a standard name for the union of such objects. Perhaps one might call it a $\ker(\text{ev})$-torsor, but that isn't very enlightening.
If it's algebraic structure you're after, reduce everything mod $2$ and you'll get the binary boolean algebra: $$ \mathbb{F}_2[x_1,\bar{x}_1,...,x_{n},\bar{x}_n]/(x_i^2+x_i,\bar{x}_i+x_i+1) $$ Everything here trivially evaluates to zero or one and it has a well-studied algebraic structure.