Im looking for an algorithm that does the following in a quick way:

Input: Natural number $r \geq 2$, natural number $s \geq 3$, prime power $q$. Output:

Finds all two-sided ideals in $J^2/J^s \subseteq \mathbb{F}_q \langle x_1,...,x_r\rangle/J^s$ ,where $A=\mathbb{F}_q \langle x_1,...,x_r\rangle $ is the noncommutative polynomial ring in r variables over the finite field with q elements and $J=(x_1,...,x_r)$ is the ideal generated by $x_1, ... , x_r$.

How many ideals are there?

And how many up to isomorphism? (Two ideals $I_1$ and $I_2$ are isomorphic iff $A/ I_1$ and $A/I_2$ are isomorphic as $K$-algebras)

It might be also interesting to replace the noncommutative polynomial ring by a commutative one.

Note that the problem can also be formulated as to find all admissible ideals containing $J^2$ of a quiver algebra with one point and $r$ loops over a finite field.

As a motivation I offer a 100 Euro reward if someone can make a quick programm which works for small r and s (lets say $r=2,3$ and $s=2,3,4$ and choosing $q=2,3,5$). It should be programmed with the GAP-packet qpa.

edit: I rewrote the question to make it shorter.Easiest special case is a question on stackexchange: https://math.stackexchange.com/questions/2322214/number-of-ideals-with-gap .

  • $\begingroup$ How fast is "quick" ? Do you already have an algorithm which you want to beat? $\endgroup$ – Johannes Hahn Jul 1 '18 at 21:08
  • 1
    $\begingroup$ If my heurestic is right, the number of isomorphism classes is bounded below by some double-exponential of the form $q^{O(r^{3s})}$ (see the newest edit to my answer). Even for your smallish numbers, this will make it impossible to actually enumerate all isomorphism classes. The only way out is probably to use a coarser equivalence relation than isomorphism. $\endgroup$ – Johannes Hahn Jul 3 '18 at 16:00
  • $\begingroup$ @JohannesHahn Thanks for your answer. It will probably take me some time to understand it in every detail. Sadly I think $r=3,s=4,q=5$ might be the first really interesting case... I think about adding another restriction to make the number much smaller, but probably it will get much more complicated. $\endgroup$ – Mare Jul 3 '18 at 16:40

Here are some observations:

  1. $A$ is just a tensor algebra $T(V)$ for $V=K^r=span\{x_1,\ldots,x_r\}=J/J^2$. Let's work with that because choosing bases is evil.

  2. Every morphism $\phi: A/I \to A/I'$ lifts to a (in fact multiple) morphism(s) $\Phi: A\to A$ which maps $I$ into $I'$ simply because polynomial algebras are free algebras. But it is not clear that $\Phi$ needs to be an isomorphism as well and I think it might not be true in general.

But! It would also be nice to have a lift in between so to speak which is an automorphism of $A/J^s$ instead and that works out nicely because everything is local and finite-dimensional.

Lemma 1: Every isomorphism $\phi: A/I\to A/I'$ lifts to an automorphism $\widehat{\phi}$ of $A/J^s$ which sends $I$ to $I'$.

Proof: You require $I$ and $I'$ to be contained in $J^2$, the radical of $A/I$ is $J/I$, every isomorphism of algebras sends the radical to the radical and induces an automorphism of $A/J^2=K\oplus V$. Therefore $\forall x\in J: \Phi(x)\equiv \alpha(x) \mod J^2$ for some $\alpha\in GL(V)$. In particular $\Phi(J)\subseteq J$, thus $\Phi(J^i)\subseteq J^i$ for all $i$ and we get a well-defined endomorphism $\widehat{\phi}$ of $A/J^s$.

Also $im(\widehat{\phi})+J^2/J^s=A/J^s$ so that $\widehat{\phi}$ is surjective by Nakayama's lemma and therefore bijective as a map $A/J^s\to A/J^s$. QED.

Alright, we now face the problem of describing and distinguishing the orbits of $\operatorname{Aut}(A/J^s) \curvearrowright \operatorname{Ideals}(A/J^s)$.

Since automorphisms respects the radical, we have a natural filtration here which gets respected by all automorphisms. This first distinguising invariant of ideals we should consider is where in the filtration $A \supseteq J \supseteq J^2 \supseteq \ldots$ we first see $I$, i.e. what is the smallest degree of a monomial occuring in a generating set $I$, i.e. the smallest number $d(I)\in\mathbb{N}$ such that $I\not\subseteq J^{d+1}$. A second invariant is the subspace $I+J^{d+1} \leq J^d/J^{d+1}$, more specifically its orbit under the $Aut(A/J^s)$-action on $J^d/J^{d+1}$.

Contained in your problem is the classification of all ideals with $d(I)=s-1$, i.e. those $I$ that are sandwiched betweens $J^s$ and $J^{s-1}$. Since $Aut(A/J^s)$ acts on $J^{s-1}/J^s$ like $GL(V)$ on $V^{\otimes(s-1)}$, we find ourselves with

Problem A: For all $s\in\mathbb{N}_{\geq 2}$ classify the orbits of $GL(V)$ on the subspaces of $V^{\otimes s}$. Ideally, find something like a normal form algorithm.

This alone seems incredibly hard. It smells like there is a lot of non-trivial algebraic geometry involved here. I may, computationally it is easy to program in GAP, because one can write down everything completely explicit.

The number of such orbits probably does not depend on $q$ at all, but is probably polynomial in $r$ with degree depending on $s$.

Even just the one-dimensional case is non-trivial, even the case of pure tensors. Since $P(V)\times\cdots\times P(V) \to P(V\otimes\cdots\otimes V)$ is injective, the $GL(V)$-orbits on pure tensors in $V^{\otimes s}$ are the same as the $GL(V)$-orbits on $P(V)^s$ which already gives you a very crude, but very disheartening lower bound for the number of isomorphism classes of ideals:

Corollary: There are at least $2^{\lfloor\frac{s-1}{2}\rfloor}$ isomorphism classes of one-dimensional ideals of $A/J^s$.

Proof: $GL(V)$ has two orbits on $P(V)\times P(V)$ (all pairs of linearly dependent vectors and all pairs of linearly independent vectors respectively). For any $G$-sets $X,Y$, the number of $G$-orbits on $X\times Y$ is at least the number of $G$-orbits on $X$ times the number of $G$-orbits on $Y$ so that $GL(V)$ has $\geq 2^{s/2}$ orbits on $(P(V)\times P(V))^{s/2}$ so that there are at least $2^{\lfloor\frac{s-1}{2} \rfloor}$ many one-dimensional ideals generated by pure tensors in $V^{\otimes(s-1)}$. QED.

EDIT 03.07.: Speaking of algebraic geometry: The Grassmannian $Gr_k(V^{\otimes s})$ is a $k(r^s-k)$-dimensional smooth projective variety while $GL(V)$ is $r^2$-dimensional. The orbits can therefore not be more than $r^2$-dimensional. The orbit space itself isn't a scheme itself, I think, but maybe it's a stack or something. Nevertheless my heurestic is that we should expect it to be $\geq (k(r^s-k) - r^2)$-dimensional at least at some points if $s>2$. In particular, there will be something like $q^{\frac{1}{3}r^{3s}+\Theta(r^{2s})}$ isomorphism classes (at least!) of subspaces. And that's even worse than exponentially w.r.t. $s$. It is so much worse that we are now in the vicinity of the number of elements of $A$ itself.

Even in your extremely limited set of cases, this works out the be a massive number! If $(q,r,s)=(5,3,4)$, then $q^{\frac{1}{3}r^s}=5^{3^3}\approx 7.4\cdot 10^{18}$. There is no way you can enumerate all of that.

Anyway... Assuming for the moment that somehow we find a way to solve Problem A. In our situation we can decide whether the two invariants $d(I)$ and $d(I')$ as well as the subspaces $I+J^{d(I)+1}$ and $I'+J^{d(I')+1}$ are the same. Ideally we solve problem A in such a way that if they are the same, we get an explicit $\alpha\in GL(V)$ which actually maps these two subspaces onto on another so that we can simplify the problem a bit as we move on to more complex invariants.

More generally we can use a solution to Problem A to distinguish the graded structure which comes with any admissible ideal $I$: We have a filtration of $I$:

$I \supseteq I \supseteq I \supseteq I\cap J^3 \supseteq I \cap J^4 \supseteq ...$

which gives us a graded ideal $gr(I) = \bigoplus_{k=2}^{s-1} I\cap J^k/I\cap J^{k+1}$ in $gr(A/J^s) = \bigoplus_{k=0}^{s-1} J^k/J^{k+1}$. Note that $Aut(A/J^s)$ respects the radical filtration and therefore induces automorphisms of the graded algebra. In fact the graded algebra is just the tensor algebra $T(V)$ (up to degree s) once again, but now $Aut(A/J^s)$ acts as $GL(V)$ on it so that we can use Problem A to use this invariant.

This gives a whole bunch of invariants more.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.