# Properties of this algebra with idempotent expressions

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.

• Since $0 \cdot P(x) = 0$ for any element, this cannot be a group (no inverse for $0$). Moreover, the "usual" thing of removing $0$ and considering the leftover elements w.r.t. $\times$ also does not give you a group in this instance, as $(x_1)(1-x_1) = x_1-x_1^2 = 0$. – AnalysisStudent0414 Dec 2 '19 at 12:32

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.
• Won't this require $2^n$ steps to confirm though? Each branch of $f$ and $g$ will need investigating? – Ben Crossley Dec 2 '19 at 18:06
• I'm not convinced the answer is correct. Consider $p(x_1,x_2) = x_1 + x_2 - 2x_1x_2$ Then $p(x_1,x_2) = x_1f(x_2) + g(x_2)$ where $f(x_2) = 1-2x_2$ and $g(x_2) = -x_2$. Here, neither $f$ nor $g$ is in $Z_{n-1}$ – Ben Crossley Dec 2 '19 at 18:11
• As for your example, there was a typo in my answer (I will fix). I meant to say $f+g$ and $f$ in $Z_{n-1}$. In your example you will get $g = 1-2x_2$ and $f = x_2$. Then $f+g = 1-x_2$ and $g = x_2$ are in $Z_1$. – gdavtor Dec 2 '19 at 18:16
• Final thought: the number of monomial coefficients of a polynomial in $n$ variables is exponential, so any algorithm that is linear in the coefficients will end up being exponential in $n$ (i.e. it takes $2^n$ steps to even check each coefficient). This probably means that you are stuck with $2^n$ (my reasoning isn't rigorous though). However, like I mentioned, there are lots of very efficient ways to implement a recursive query method using my criterion above. – gdavtor Dec 2 '19 at 18:45