# for which truth-operations f can f-membership in a prime ideal be represented by a polynomial?

Nota bene: all rings are supposed commutative with $1$ and all ring homomorphism should be unital.

Let $B$ be the set of truth values {True, False}. For a formula $\phi$ denote by $[\phi]\in B$ it's truth value. E.g. $[x=x] = True$ for all $x$.

Let $o\colon B^n \to B$ a $n$-ary truth-operation, $0≠n\in \mathbb{N}$.
Let $B$ be a Rings $\mathfrak p\subset B$ a prime Ideal. We say the triple $(o,\mathfrak p,B)$ is $A$-guessable if $B$ is an $A$-Algebra (i.e. there is a chosen ring homomorphism $A\to B$) and there exists a polynomial $f_o=f_o(T_1,\ldots,T_n)\in A[T_1,\ldots,T_n]$ such that for all $x_1,\ldots, x_n\in B$ we have $[f_o(x_1,\ldots,x_n)\in\mathfrak{p}]=o([x_1\in \mathfrak{p}],\ldots,[x_n\in\mathfrak{p}])$.

Clearly for any Ring $A$ a triple $(o,\mathfrak p,B)$ is $B$-guessable (with $id\colon B\to B$) if it is $A$-guessable if it is $\mathbb{Z}$-guessable (with the obvious map $\mathbb{Z}\to B$).
Call a triple $(o, \mathfrak p,B)$ guessable if it is $B$-guessable
Call $o$ (very) easy if every triple $(o, \mathfrak p,B)$ is ($\mathbb{Z}$-) guessable.

Examples:
if $o=pr_i\colon(v_1,\ldots,v_n)\mapsto v_i$ for some $i$, then trivially every $(o, \mathfrak p,B)$ is guessable by $\mathbb{Z}$ via $f_o=T_i$
if $o=\vee\colon (v_1,\ldots,v_n)=v_1\vee\ldots\vee v_n$, then every $(o', \mathfrak p,B)$ is guessable by $\mathbb{Z}$ via $f_{o'}=T_1\cdot T_2\cdots T_n$. (because $\mathfrak{p}$ is prime)
So both $o$ and $o'$ are very easy.

Question 1: Are there other easy or very easy $n$-ary truth-operations other than $\vee$ and $pr$? In particular I would like to know if $\wedge$ is (very) easy.
Question 2: Is there a difference between guessable and $\mathbb{Z}$-guessable, i.e. are there triples which are guessable but not $\mathbb{Z}$-guessable? For which rings $B$ can such a difference occur?

-

The only easy operations are the constant operation $\operatorname{False}$ (represented by $0$), the constant operation $\operatorname{True}$ (represented by $1$), and the operation where we apply OR to a subset of the variable (basically a combination of your two examples).

To see this, like $k$ be any field that's an $A$-algebra. Let $B=k[x_1,\dots,x_n]$. We divide into two cases: $f=0$ or $f \neq 0$.

If $f=0$, then clearly the logical operation must be $\operatorname{True}$.

If $f\neq 0$, then if $\mathfrak p=(0)$ then $x_1,\dots,x_n,f\not\in \mathfrak p$, so $o(\operatorname{False},\dots,\operatorname{False})=\operatorname{False}$. Next, we can factor $f$ into irreducible polynomials. We will show that each irreducible factor of $f$ is one of the variables $x_1,\dots,x_n$. Suppose for contradiction that $g$ is an irreducible factor of $f$ that is not one of $x_1,\dots,x_n$. If $\mathfrak p=(g)$, then $x_1,\dots x_n \not \in \mathfrak p$ but $f \in \mathfrak p$, so $o(\operatorname{False},\dots,\operatorname{False})=\operatorname{True}$.

So the only irreducible factors are $x_1,\dots x_n$, so $f=c x_1^{r_1} \dots x_n^{r_n}$ for $c$ a nonzero constant. Clearly in this case we can check that $f$ is one of the operations I describe - it is just OR applied to the set of $v_i$ such that $r_i$ is nonzero.

For a fixed $B$, more logical operations may be possible. For instance, over $\mathbb F_2$ it is clear that every logical operation is possible. One can also see this for any finite field $\mathbb F_q$. But for a general ring, these are all.

-