7
$\begingroup$

I'm writing some software to automatically compute things like Alexander modules, Alexander ideals, Milnor signatures and Farber-Levine pairings for 1 and 2-knot complements. So among other things I'd like to have a quick way of comparing ideals in the Laurent polynomial ring $\mathbb Z[t^{\pm 1}]$.

So my question:

Is there an efficient way of determining whether or not two ideals in $\mathbb Z[t^{\pm 1}]$ are equal? What's the most pleasant procedure you can think of?

My ideals are given by a finite number of generators.

The knot theory literature tends to stop at "$\mathbb Z[t^{\pm 1}]$ isn't a PID" but I'm hopeful there's some reasonable tools out there. Understanding ideals in $\mathbb Z[t^{\pm 1}]$ is essentially the same thing as understanding cyclic group actions on finitely generated abelian groups so I could imagine answers might be more complicated than I like. But I hope to be pleasantly surprised by some sort of "division algorithm + details" type algorithm.

For example, is there a better way to go about this problem than:

Given an ideal $I \subset \mathbb Z[t^{\pm 1}]$, consider the finitely-generated abelian group $G = \mathbb Z[t^{\pm 1}]/I$ together with the action of $\mathbb Z$ on $G$ given by multiplication by $t$. We want to determine $G$ as a $\mathbb Z$-module. So presumably you would do this on the $\mathbb Z$-torsion subgroup of $G$ (call it $\tau G$), then work out the conjugacy class of the action of $\mathbb Z$ on $G/\tau G$ (which amounts to the conjugacy problem in $GL_n(\mathbb Z)$), then there would be an extension problem to deal with.

I'm hoping there's a simpler way to deal with this problem -- simpler in the sense of implementation.

$\endgroup$
5
  • $\begingroup$ What do you mean by comparing? Testing of equality or inclusion? In that case it might be useful that this can be tested via their interesections with Z[t]. In which form are the ideals given? $\endgroup$ Jul 28, 2010 at 17:26
  • $\begingroup$ Equality is my main concern. But inclusion would be nice to know, too. The ideals are given by a finite number of generators. $\endgroup$ Jul 28, 2010 at 17:30
  • $\begingroup$ Can Grobner bases be adapted to work in this setting? $\endgroup$ Jul 28, 2010 at 18:20
  • $\begingroup$ I suppose they could help when dealing with the subgroup $\tau G$. $\endgroup$ Jul 28, 2010 at 18:33
  • $\begingroup$ Do you need to assume that $G$ is finitely generated? $\endgroup$
    – Luc Guyot
    Jul 19, 2016 at 5:32

2 Answers 2

5
$\begingroup$

It is fairly straightforward to adapt standard Gröbner basis techniques to such algebras, e.g. see the paper [1]. See also the paper [0] which applies such algorithms to the problem at hand.

[0] Jesus Gago-Vargas; Isabel Hartillo-Hermoso; Jose Marya Ucha-Enryquez
Algorithmic Invariants for Alexander Modules. LNCS 4194, 149-154
https://link.springer.com/chapter/10.1007/11870814_12

Abstract. Let G be a group given by generators and relations. It is possible to compute a presentation matrix of a module over a ring through Fox's differential calculus. We show how to use Gröbner bases as an algorithmic tool to compare the chains of elementary ideals defined by the matrix. We apply this technique to classical examples of groups and to compute the elementary ideals of Alexander matrix of knots up to 11 crossings with the same Alexander polynomial.

[1] Franz Pauer, Andreas Unterkircher.
Gröbner Bases for Ideals in Laurent Polynomial Rings and their Application to Systems of Difference Equations.
AAECC 9, 271-291 (1999)
https://link.springer.com/article/10.1007/s002000050108

Abstract. We develop a basic theory of Gröbner bases for ideals in the algebra of Laurent polynomials (and, more generally, in its monomial subalgebras). For this we have to generalize the notion of term order. The theory is applied to systems of linear partial difference equations (with constant coefficients) on ${\mathbb Z}^n$. Furthermore, we present a method to compute the intersection of an ideal in the algebra of Laurent polynomials with the subalgebra of all polynomials.

$\endgroup$
1
  • $\begingroup$ Thanks. The Pauer-Unterkircher paper seems to be precisely what I'm looking for. $\endgroup$ Jul 28, 2010 at 21:28
5
$\begingroup$

Well, $\mathbb{Z}[t,t^{-1}]$ is the localization of the polynomial ring $R=\mathbb{Z}[t]$ with respect to the multiplicative set $S$ consisting of the powers of $t$. The ideals of $S^{-1}R=\mathbb{Z}[t,t^{-1}]$ have the form $J=S^{-1}I$ where $I$ runs through the ideals of $R$. Indeed we can take $I$ to be $J\cap R$. We can deal effectively with ideals of $R$ by using Groebner bases as it's a polynomial ring over a principal ideal domain. We have $S^{-1}I=S^{-1}\overline I$ where $\overline I$ is the saturation of $I$, that is the $f\in R$ such that $t^kf\in I$ for some natural number $t$, and $S^{-1}I_1\subseteq S^{-1}I_2$ iff $\overline I_1\subseteq\overline I_2$. I think one can find a Groebner basis of $\overline I$ if one has one for $I$ (I'd have to check this), so one should be able to answer questions of inclusions/equalities of ideals in $S^{-1}R$ effectively.

$\endgroup$
3
  • $\begingroup$ Could you give me some references that work at this level of generality? The on-line definitions of Groebner basis I find need polynomials to have coefficients in a field. $\endgroup$ Jul 28, 2010 at 18:42
  • 1
    $\begingroup$ It's certainly dealt with in the book by Adams and Loustaunau: books.google.co.uk/… $\endgroup$ Jul 28, 2010 at 18:47
  • $\begingroup$ Great. Order placed. I've been looking for a reason to learn about Groebner basis for some time. It appears now is the time! $\endgroup$ Jul 28, 2010 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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