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.

  • 1
    $\begingroup$ 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$. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Won't this require $2^n$ steps to confirm though? Each branch of $f$ and $g$ will need investigating? $\endgroup$ – Ben Crossley Dec 2 '19 at 18:06
  • $\begingroup$ 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}$ $\endgroup$ – Ben Crossley Dec 2 '19 at 18:11
  • $\begingroup$ Yes. If you keep a table of known polynomials you can speed up the query for lower degree polynomials. $\endgroup$ – gdavtor Dec 2 '19 at 18:11
  • 1
    $\begingroup$ 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$. $\endgroup$ – gdavtor Dec 2 '19 at 18:16
  • 1
    $\begingroup$ 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. $\endgroup$ – gdavtor Dec 2 '19 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.