Polynomials over $\mathbb{F}_2$ with certain values in $\mathbb{F}_4$ Let $\mathbb{F}_4=\{0,1,u,u^2\}$ be the field with $4$ elements. Is there a polynomial $p \in \mathbb{F}_2[x,y]$ with the following property?
(1) For $r,s \in \mathbb{F}_4$, we have $p(r,s)=u \Leftrightarrow r=u \wedge s=u$.
Also, is there a polynomial $p \in \mathbb{F}_2[x,y]$ with the following property?
(2) For $r,s \in \mathbb{F}_4$, we have $p(r,s)=u \Leftrightarrow r=u \vee s=u$.
I don't see any reason why such polynomials should not exist, but so far I have no idea how to construct them. In principle, there are only finitely many choices which one could check via computer, since $p$ essentially comes from $\mathbb{F}_2[x,y]/(x^4-x,y^4-y)$. The existence of such polynomials would solve another problem which I am currently thinking about.
 A: For (1) try
$$
p(x,y)=x[1-(x-y)^3].
$$
If $r,s\in \Bbb{F}_4$ are distinct, then $(r-s)^3=1$, and $p(r,s)=0$. If $r=s$, then $p(r,s)=r$. Thus $p(r,s)$ attains the value $u$ for inputs $r,s\in\Bbb{F}_4$ only when $r=s=u$.
The bad news is that the question (2) has a negative answer. Such a polynomial does not exist. Recall that the Frobenius automorphism $F$ interchanges $u$ and $u+1$. Also recall that $F$ respects evaluation of polynomials with coefficients in the prime field.
Your condition dictates that $p(u,u+1)=u$. In view of the Frobenius action this implies that
$$
p(u+1,u)=p(F(u),F(u+1))=F(p(u,u+1))=F(u)=u+1.
$$
Thus the desired polynomial does not exist.

Describing "near miss" polynomials for (2). I am relying heavily on the fact that the polynomial function $f:\Bbb{F}_4\to\Bbb{F}_2, x\mapsto x^2+x$ takes the value $1$ when
$x\notin\Bbb{F}_2$ and the value $0$, when $x\in\Bbb{F}_2$. Thus
$$
p_1(x,y)=x(x^2+x)(y^2+y+1)
$$
agrees with $x$ when $x\in \Bbb{F}_4\setminus\Bbb{F}_2, y\in\Bbb{F}_2$ and vanishes elsewhere. Similarly
$$
p_2(x,y)=y(x^2+x+1)(y^2+y)
$$
agrees with $y$ when $y\in \Bbb{F}_4\setminus\Bbb{F}_2, x\in\Bbb{F}_2$.
For its part the polynomial 
$$
q_3(x,y)=(x^2+x)(y^2+y)
$$
gives a function that vanishes when either $x$ or $y$ is in the prime field, and takes the value $1$, when both $x,y\in \Bbb{F}_4\setminus\Bbb{F}_2$.
Putting those pieces together we get near miss polynomials
$$
p^\flat(x,y)=p_1(x,y)+p_2(x,y)+xq_3(x,y)
$$
that behaves as prescribed except that $p^\flat(u^2,u)=u^2$, and its cousin
$$
p^\sharp(x,y)=p_1(x,y)+p_2(x,y)+yq_3(x,y)
$$
that behaves as prescribed except that $p^\sharp(u,u^2)=u^2$.
A: Your second polynomial has the property  $f(u^2,u)=u$.
Applying the automorphism $u\leftrightarrow u^2$, this implies $f(u,u^2)=u^2$, contrary to what you want.
