# A Non-Commutative Nullstellensatz

In studying presentations of pro-$p$-groups via generators and relations, one is led (via the so-called Magnus embedding) to questions involving power series in non-commuting variables. Results from local algebraic geometry occasionally shed some insight on how to make progress, but more often that not, I find myself lacking appropriate analogs of major theorems from the commutative case. I haven't had much luck in books on non-commutative ring theory or non-commutative algebraic geometry -- the focus seems to be on completely different ideas (though I'll happily stand corrected). In any case, here's an important and seemingly basic question that I don't know how to answer.

Let $\mathbb{F}_p\langle\langle x,y\rangle\rangle$ be the ring of formal power series over $\mathbb{F}_p$ in two non-commuting variables $x$ and $y$. This ring has a unique two-sided maximal ideal $I=(x,y)$. Suppose $f,g\in I$. Can anything be said about the smallest $n$, if one exists, such that $I^n\subset (f,g)$? Namely, when does this quantity exist? Is this quantity computable? Boundable?

It's trivial to come up with examples for which there is no $n$, e.g., $(xy,yx)$, since no $x^n$ is contained in this ideal. I'm not sure how exactly to quantify this observation. Is there some kind of non-commutative resultant at play here?

Edit: I think it might be helpful for me to update with some examples as we go along. Here's one that I thing captures at least some of the interesting parts of this question.

Take $p=3$, $f=x+y$, and $g=x^3$. Then the inclusion $I^3\subset (f,g)$ can be seen by taking each of the 8 monomials in $I^3$ verifying that they are in $(f,g)$, e.g., $yxy=yfy-f^3+g\in (f,g)$. The same argument applies with the same $f$ and taking $g=x+y+x^3$. This seems to me evidence that this question can't be answered only by looking at the leading monomials (though admittedly it might be easy enough to exclude these trivial counter-examples).

-
There is an easy way to undestand your new example that applies more generally to any $f(x,y)=x+h(y)$: in order to find the quotient $A=k\langle x,y/(f,g)\rangle$ you simply need to substitute $x=-h(y)$, so that $A=k[y]/(g(-h(y),y)$ and it's easy to find the nilpotency index $n$: it's just the dimension of $A$. –  Victor Protsak May 21 '10 at 3:05
The leading monomials are relevant because of a noncommutative Grobner basis approach to computing the quotient. If what you are really interested in is an $\textit{algorithm}$ for determining whether or not the ideal $(f,g)$ contains $I^n$ (and the minimum $n$ if it does), I suggest that you tighten your question and repost. –  Victor Protsak May 21 '10 at 3:07
No, I'm more interested in a formula than an algorithm. If the answer turns out to be "No, except in simple cases there's no nice formula, but there's a Grobner basis algorithm that might work," the lack of a nice clean formula would be of interest to me as well. But, and forgive me if I'm being obtuse, it seems as if your answers are providing solutions on a case-by-case basis. If I was given two more random-looking power series (e.g., not monomials, not starting with $x+...$ or $y+...$), it's still unclear to me how to proceed. –  Cam McLeman May 21 '10 at 5:04
No problem! You've summarized the situation well: there is no nice formula except in special cases, etc. I can't really provide "solutions", since your question is vague and I've had hard time understanding what kind of answer do you expect, but one thing that $\textit{can}$ be said is that $f$ and $g$ have leading monomials of a special kind, which suggests looking for a noncommutative Groebner basis algorithm. –  Victor Protsak May 21 '10 at 5:38

Let $F$ be a field, and let $f_1,f_2,\ldots, f_k\in R:=F\langle\langle x,y\rangle\rangle$ with $k\in \mathbb{N}$. Order monomials in $R$ by degree, and then lexicographically. Since the question concerns computability, assume that there is an algorithm which spits out the coefficients of the monomials in $f_i$ (in order). I claim that:

Proposition: Given any fixed $n\in \mathbb{N}$, there is an algorithm to decide whether $I^n\subseteq (f_1,f_2,\ldots, f_k)$.

To prove this, first we need a lemma and some notation. Given $r\in R$ we write $r[n]$ for the homogeneous component of $r$ in degree $n$.

Lemma: $I^n\subseteq (f_1,f_2,\ldots, f_k)$ iff for each of the $2^n$ monomials $m$ of total degree $n$ there is a power series $g_m\in (f_1,f_2,\ldots, f_k)$ such that $g_m[n]=m$.

Proof of the lemma: The forward direction is obvious. For the reverse, let $m_1,m_2,\ldots, m_{2^n}$ be the list of all monomials of degree $n$, and let $g_i:=g_{m_i}$. Fix $h\in I^n$. We can write $h[n]=\sum m_i a_{i,n}$ for some $a_{i,n}\in R$ (all of degree $0$). Setting $h':=h-\sum g_i a_{i,n}$, we see that $h'$ has zero homogeneous components in degree $\leq n$. We can write $h'[n+1]=\sum m_i a_{i,n+1}$ for some $a_{i,n+1}\in R$ (all of degree $1$). Set $h''=h-\sum g_i(a_{i,n}+a_{i,n+1})$. Repeating this process, we obtain power series $a_i=\sum_{m\geq n}a_{i,m}$ such that $h=\sum_i g_i a_i\in (f_1,f_2,\ldots, f_k)$.$\qquad \blacksquare$

Proof of the proposition: By the lemma, it suffices to decide for each monomial $m\in I^n$, whether there is a power series $g_m\in (f_1,f_2,\ldots, f_k)$ with $g_m[n]=m$. We may as well work in the quotient ring $R/I^{n+1}$. The image of the ideal $(f_1,f_2,\ldots, f_k)$ modulo $I^{n+1}$ is a finite-dimensional $F$-vector space, and so the question is easily decided by a row-reduction style argument. [More concretely, one can modify the set $\{f_1,f_2,\ldots, f_k\}$ modulo $I^{n+1}$ so that no leading terms are linear combinations of others, and the set is closed under left and right multiplication by $x$ and $y$. Then, the leading terms of degree $n$ either do or do not generate all of the appropriate monomials.]$\qquad \blacksquare$

To give an interesting example, consider $f_1=yx-y^2+x^3$, $f_2=xy-x^2$. One can show directly (using the methodology above) that $I^{5}\subseteq (f_1,f_2)$. If we modify $f_1=yx-y^2+x^k$ (with $k\geq 3$), then we get $I^{k+2}\subseteq (f_1,f_2)$.

On the question of whether it is decidable, given as input only the algorithms describing the power series $f_1,\ldots, f_k$, whether an $n$ exists for which $I^n\subseteq (f_1,f_2,\ldots, f_k)$, I don't know the answer.

-
This is excellent, and exactly the kind of answer I was looking for. Your condition in the lemma is eminently checkable. Now to remember why I wanted to know this 5 years ago... –  Cam McLeman Jan 29 at 6:02
@Cam: Sorry I didn't answer this question 5 years ago! I joined way back in the day, but then took a long hiatus. I'm now going through old questions, in the hope that the answers might be useful to people (even if a bit tardy). –  Pace Nielsen Jan 29 at 15:40
Better late than never, by several orders of magnitude. Thanks again. –  Cam McLeman Jan 29 at 17:53

Suppose that $f$ and $g$ are monomials and that $(f,g)$ contains a power of $I$. Then every word of sufficient length must contain $f$ or $g$ as a subword (and conversely). Thus your argument with $x^n$ shows that either $f$ or $g$ is a power of $x$, and likewise, one of them is a power of $y$. If $f=x^k, g=y^m, k,m\geq 2$ then the word $(x^{k-1}y)^N$ can be arbitrarily long and doesn't contain $f$ or $g$ — contradiction. Thus up to relabelling, $f=x^k, g=y$ and $n=k$ is minimal with the property that $I^n\subset (f,g)$.

I recommend Algebraic Combinatorics on Words by M. Lothaire (google it) for related ideas.

-
Hmm. Okay, sure, though the restriction that $f$ and $g$ are monomials is pretty, well, restrictive... –  Cam McLeman May 18 '10 at 23:26
On the contrary, I think that it's the heart of the matter, since you can always deform to the leading monomial term. What this shows is that such $f, g$ are very special. –  Victor Protsak May 18 '10 at 23:53
Interesting. So what makes a monomial term "leading"? By lexicographical ordering? –  Cam McLeman May 19 '10 at 2:38
You can use any subword-compatible ordering. BTW, ideals of $k<x,y>$ containing $I^n$ are studied under the nomenclature "noncommutative Hilbert scheme". It is just rare for them to be 2-generated. –  Victor Protsak May 19 '10 at 4:23
I think I'm still confused by this deformation idea. For a trivial non-monomial example, take $p=2$, $f=x+y$, and $g=y^2$. Then $I^2\subset (f,g)$ since $x^2=f^2-g$, $xy=xf-x^2$, and $yx=fx=x^2$. So we get $n=2$. But if we take an ordering where $y<x$, then the leading terms are $y$ and $y^2$, which gives $n=1$. Perhaps I'm misunderstanding what you're saying, but it seems unlikely to me that you'll be able to give an answer that depends only on the leading terms, no? –  Cam McLeman May 19 '10 at 8:08