Nt1310 Unit 1 Math Test Paper

\begin{abstract} It is known that Groebner bases is EXP-SPACE in general.
We show that this remains true over Boolean rings.
\end{abstract}
\section{Boolean Rings}
Let $\mathbb{F}_2 = \mathbb{Z}/(2)$. Let $R_n = \mathbb{F}_2[x_1,\ldots,x_n, y_1,\ldots,y_n, z_1,\ldots,z_n]$ and % \footnote{Over $\mathbb{F}_2$, $+$ is the same as $-$.}
\[ S_n := \{c^2 -c \,\, | \,\, c \in \{x_1,\ldots,x_n, y_1,\ldots,y_n, z_1,\ldots,z_n\} \}. \]
Let
\[ R_n^{\rm b} := R_n / (S_n). \]
This is {\em Boolean ring}, which means $r^2 = r$ for all $r \in R_n^{\rm b}$. \\[1pt]

% Any element $r \in R_n^B$ can be lifted to an element $r^{\rm lift}$ of $R_n$. The lift becomes unique
% by requiring that $r^{\rm lift}$ has degree 1 w.r.t. any of the variables that appear in it.

Ideals in …show more content…
\eindebewijs

\begin{lemma}
Let $\tilde{I}_n$ be the ideal generated by $S_n \bigcup L_n \bigcup \{Z_n\}$. Then $I_n = \tilde{I}_n$
\end{lemma}
\noindent Proof: $\tilde{I}_n \subseteq I_n$ since $Z_n \in P_n$. Remains to prove that $T_n \subseteq \tilde{I}_n$ and $P_n \subseteq \tilde{I}_n$. \\[5pt]
$x_1 z_1$ is congruent to $x_1 (x_1 y_1 + x_1 + y_1) = x_1^2 y_1 + x_1^2 + x_1 y_1$ mod $(L_n)$, which is congruent to
$x_1 y_1 + x_1 + x_1 y_1 = x_1$ mod $(S_n)$. Since $L_n$ and $S_n$ are in $\tilde{I}_n$, one sees that $x_1 z_1$ is congruent to $x_1$ mod $\tilde{I}_n$ and so $x_1 z_1 - x_1 \in \tilde{I}_n$. The same proof shows $T_n \subseteq \tilde{I}_n$. \\[5pt]
Since $x_1 z_1$ is congruent to $x_1$ mod $\tilde{I}_n$, it follows that
$x_1 \cdot Z_n$ is congruent to $x_1 z_2 \cdots z_n$ mod $\tilde{I}_n$. Repeating this idea shows that any element of $P_n$ is congruent a multiple of $Z_n$ mod $\tilde{I}_n$, and is hence in $\tilde{I}_n$. \eindebewijs
\begin{cor}
Any total-degree ordered Gr\"obner basis of $S_n \bigcup L_n \bigcup \{Z_n\}$ has at least $6n + 3^n$ elements.
\end{cor}