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)?



What does this permutation polynomial look like?
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).$$


