What does this permutation polynomial look like?

Question

What is the number of terms of the unique multilinear polynomial $f\in\Bbb F_2[x_{1,1},\dots,x_{n,n}]$ in $n^2$ variables such that $f$ vanishes only on matrices that are permutations?

Are there good bounds?

Note that such a polynomial should have $S_n\times S_n$ symmetry.

I think one can even guess how such a polynomial should look like. It is just sum of $n!$ terms. However there could be unreasonable cancellations (at least under some mild error criteria). This could make the polynomial efficiently representable.

There are many many reasons I ask this. One reason is can there be unreasonable cancellations if we replace $\Bbb F_2$ by $\Bbb R$ (note either $1\in\Bbb F_2$ translates to $\neq0$ in $\Bbb R$ and $0\in\Bbb F_2$ translates to $=0$ in $\Bbb R$ or $1\in\Bbb F_2$ translates to $<0$ in $\Bbb R$ and $0\in\Bbb F_2$ translates to $>0$ in $\Bbb R$ are variations)?

Answer 1

For any permutation $\sigma\in S_n$ let's define $X(\sigma)=\prod_{i=1}^n x_{i\sigma(i)}$ and $Y(\sigma)=\prod_{i=1}^n\prod_{j\neq\sigma(i)}(1+x_{ij})$.

---

Lemma: Our polynomial can be written explicitly as $$f(x_{ij})=1+\sum_{\sigma\in S_n}X(\sigma)Y(\sigma)$$ To prove this notice that $X(\sigma)Y(\sigma)=1$ if and only if the $(x_{ij})$ matrix represents $\sigma$.

---

Let us now write the monomial expansion $$f(x_{ij})=1+\sum_{A\in M_n(\mathbb F_2)}c(A)x^A$$ where $c(A)\in \mathbb F_2$ and $A$ runs over all $n\times n$ matrices with $\{0,1\}$ entries. Here I am using the short hand notation $x^A$ to represent the monomial $\prod_{ij} x_{ij}^{A_{ij}}$.

When we expand the product $X(\sigma)Y(\sigma)$ we see that a term $x^A$ appears if and only if $\prod_{i=1}^n A_{i\sigma(i)}=1$. For a given $A$, let $S(A)$ denote the set of all $\sigma\in S_n$ for which $\prod_{i=1}^n A_{i\sigma(i)}=1$.

From the Lemma we see that $c(A)=|S(A)|\pmod{2}$. In other words $c(A)=\det(A)$.

We conclude that the number of nonzero terms in $f$ is $1+$ the number of matrices $A$ which satisfy $c(A)=1$ which, in turn, is equivalent to $\det{A}\neq 0$. So we get

$$1+|\operatorname{Gl}_n(\mathbb F_2)|=1+2^{\binom{n}{2}}\prod_{i=1}^n (2^i-1).$$