# Small generating set of third degree polynomials in $R=\mathbb{Z}_2[x_1,\dots,x_n]/\langle x_1^2-x_1,\dots,x_n^2-x_n\rangle$

Let $R=\mathbb{Z}_2[x_1,\dots,x_n]/\langle x_1^2-x_1,\dots,x_n^2-x_n\rangle$, i.e., we can think of $R$ as the ring of multivariate polynomials with the additional property that one can "linearize" higher powers (e.g. $x^2+y^3$ is the same as $x+y$). Note that I sometimes use "$y$","$z$" etc. instead of $x_2,x_3$.

I wish to generate the set of all third degree monomials, e.g. monomials of the form $xyz$. That is, I wish to find a set $p_1,\dots,p_t\in R$ such that every monomial can be written as sums and products of $p_1,\dots,p_t$.

One can see that we have two trivial cases: If we allow products of any number of elements, then $xyz$ can always be written as a product of three elements $x\cdot y\cdot z$ and so $x_1,\dots,x_n$ is a generating set which seems to me to be minimal (although I have no proof), so in this case the size of the generating set is probably $\Theta(n)$.

Also, if we disallow products, i.e. only allow linear combinations, than the generating set must be of size $\Theta(n^3)$ since this is the dimension of the set of monomials $xyz$ seen as a vector space.

The interesting case is when we allow products of pairs of the generating set, i.e. we look at combinations of the form $\sum p_ip_j$. Trivial arguments can only show a lower bound of $\Omega(n^{1.5})$ but I have no idea how to search for a generating set of such size and it seems to be that $\Theta(n^2)$ is the correct size in this case (it's very easy to see it's an upper bound: take all monomials $xy$ to be in the generating set and now $xyz=xy\cdot xz$).

So my question is what is the correct bound, and even more - what is the "correct" way to attack a problem like that.

I highly wish to exploit the underlying structure of $R$, which seems to be a classical algebraic-geometry object, but so far I haven't got a clue.

-
I expected you would know better to use \langle rather than <. –  Asaf Karagila Nov 24 '11 at 15:14
I embarrass myself so much in this question that this is the least of my problems. But I'll fix it. –  Gadi A Nov 24 '11 at 15:20
The ring $R$ is isomorphic to the ring of functions from $\mathbb{F}_2^n$ to $\mathbb{F}_2$, with $x_j$ being projection onto the $j$th coordinate, and with addition and multiplication being pointwise. But this doesn't make the answer any clearer to me. –  David Speyer Nov 24 '11 at 17:16