# 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\rangle$

Let $R=\mathbb{Z}_2[x_1,\dots,x_n]/\langle x_1^2-x_1,\dots,x_n^2-x\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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 28, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9602919220924377, "perplexity_flag": "head"}