#36986 has broken .subgroup(...) badly

[dimpase]

This has broken .subgroup(...) rather badly, see sage-devel
e.g. with this one gets

sage: g=AbelianGroup([2,2])
sage: g.cardinality().factor()
2^2
sage: gg=g.subgroup(g.list())
sage: gg.cardinality().factor()
2^3

Originally posted by @dimpase in #36986 (comment)

[dimpase]

A quick way to back out the wrong change is to download
https://patch-diff.githubusercontent.com/raw/sagemath/sage/pull/36986.diff
into the main Sage directory and apply it as patch -p1 -R < 36986.diff

[dimpase]

@amanmoon

[tscrim]

What happened is that the ambient space code assumes that the generators are all distinct, but the subgroups can violate this. We just need to tell the ambient space to use the abelian invariants rather than the group generators.

[tscrim]

Okay, so this is a mess. There is a major issue with how the subgroups were implemented IMO. On #36986, that was fixing an issue, but this shows it was not done in the correct way (which it was unfortunate that there were no doctests for the case when there was redundancy with the generators). Now I am thinking we need to go back to the "reduced" generators, but the subgroup needs to keep track of the lifting (and perhaps also the defining generators).

[dimpase]

Am I correct that Abelian groups in Sage are implemented via Smith Normal Form algorithms, and related things?

[tscrim]

It is done that way and via GAP. I was just battling with GAP to find something that works, which I finally figured out can be done with IndependentGeneratorsOfAbelianGroup. This is now on

https://github.com/tscrim/sage/tree/groups/abelian_subgroups-36986

However, it doesn't work (quickly) for large groups. I'm playing whack-a-mole with problems. Really we just need some way to remove redundant generators. We might need a very refined strategy here to keep construction quick, perhaps with check for word problem solutions iteratively for certain group sizes.

I need to sleep now. Hopefully you can figure something out where everything works.

[amanmoon]

Can we use the following code for finding independent generators?

        independent_gens = []
        mat = []
        curr_rank = 1
        for row in gens:
            mat.append(row.exponents())
            if matrix(mat).rank() == curr_rank:
                curr_rank += 1
                independent_gens.append(row)

I tried it here and it worked fine

[tscrim]

I think that would get it down to something close to an independent set, but it probably isn’t sufficient for the torsion subgroup.

[dimpase]

I think it should be well-known how to deal with this problem as efficiently as possible, so it's a question of finding a reference.

We have a f.g. Abelian group $A$ given as a direct sum of $N$ cyclic subgroups $C_{k_j}=\langle x_j\rangle$, with $k_j\in {2,\dots,\infty}, 1\leq j \leq N,$ and the associated homomorphism $\phi:\mathbb{Z}^N\to A.$ And we have $B\leq A,$ a subgroup given by generators $g_i=\sum_j u_{ij} x_j$, then $B=\phi(\hat{B})$, and $\hat{B}$ may be computed by taking the SNF of the matrix $(u_{ij})$.

So the question is how to tie all this up together. Should I ask on Mathoverflow or some other place, such as GAP forum?

PS. I've asked here: https://mathoverflow.net/q/468433/11100

PPS. The SNF of the matrix $U:=(u_{ij})$ corresponds to $\mathbb{Z}^N/\hat{B}$, not to $\hat{B}$.

[tscrim]

Mathoverflow should be good. My current WIP branch uses what is already provided by GAP, but it just takes very long in “obvious” cases.

In the short term, we might just want to revert #36986. The inconsistency addressed there is (far) less bad than the errors we are getting here IMO.

I believe the following bug was still there before #36986:

sage: A.<a,b> = AbelianGroup([0,0])
sage: S = A.subgroup([a,b,a*b])
sage: S
Multiplicative Abelian subgroup isomorphic to Z x Z x Z generated by {a, b, a*b}
sage: S.equals(A)
False

This is clearly not true as S is clearly all of A.

We might just have to either do some heuristics for the “obvious” independent case to still handle some large groups and otherwise just take the speed loss for correctness. Although there might be a better linear algebra approach using the relations of the generators. I vaguely remember learning something about how to do this in my algebra course, but I don’t remember much.

[dimpase]

On 5 April 2024 14:44:53 CEST, Travis Scrimshaw ***@***.***> wrote: Mathoverflow should be good. My current WIP branch uses what is already provided by GAP, but it just takes very long in “obvious” cases. In the short term, we might just want to revert #36986. The inconsistency addressed there is (far) less bad than the errors we are getting here IMO. I believe the following bug was still there before #36986: ``` sage: A.<a,b> = AbelianGroup([0,0]) sage: S = A.subgroup([a,b,a*b]) sage: S Multiplicative Abelian subgroup isomorphic to Z x Z x Z generated by {a, b, a*b} sage: S.equals(A) False ``` This is clearly not true as `S` is clearly all of `A`. We might just have to either do some heuristics for the “obvious” independent case to still handle some large groups and otherwise just take the speed loss for correctness. Although there might be a better linear algebra approach using the relations of the generators. I vaguely remember learning something about how to do this in my algebra course, but I don’t remember much.

I am not sure whether GAP does proper Kannan-Bachem algorithm for HNF/SNF - or whatever the best currently know is.

[dimpase]

see https://mathoverflow.net/a/468442/11100
for an answer by Derek Holt, whom I would consider an authority

[tscrim]

I don’t quite see how from that to extract some generators that realize the $C_8 \times C_8$. The first part gets a nice list of generators, but I don’t see how to get the corresponding generators.

[dimpase]

I think Derek took my question so that one has to swap B and A/B. We have $A=\phi(\mathbb{Z}^3)$, and $\ker\phi$ generated by the diagonal matrix D with 4,8,16 on the diagonal.

Now, we have B generated by two generators he gives. Taking these two row vectors and D gives us the kernel for the homomorphism $\psi$ so that $A/B=\psi(\mathbb{Z}^3)$. We need to find a complement C to $\ker\psi$, so that together one gets the whole $\mathbb{Z}^3$. Then C and D will give us the kernel for the homomorphism sending $\mathbb{Z}^3$ to B, and SNF for this C and D-matrix will tell us all about B.

Still, computing C there in Derek's answer looks like magic to me (but I am on vacation:-))

[tscrim]

I am not sure you're correct about what is being considered. My understanding is we should get $C_8 \times C_8$, and one example of generators of $B$ that realize this are $(1,0,2)$ and $(0,1,0)$. (I also checked we can get the image under $\phi$ of the generated in Derek's answer from the original generators.) So the quotient $A / B = C_8$. Hence, I think the SNF given is telling us information about $B$, and the transformation is somehow giving us the COB.

[dimpase]

You can see Derek's comment to his answer, where he insists that $A/B=C_8\times C_8$, and $B=C_8$. I've edited my MO question and added the computation there showing that he swaps the two (unless I'm mixing up something trivial, as I do once in a while :-)).

[dimpase]

https://mathoverflow.net/a/468601/11100 - it's more coherent answer

[tscrim]

Yes, it is more coherent, but it also has more typos and imprecision: The matrix $M$ is not defined; I believe Aurel means $K$. Aurel is also using column HNF. Taking ideas from Aurel's answer, I can now produce the kernel in Holt's answer:

sage: S = matrix([[1,2,2],[2,1,4]]).transpose()
sage: K = matrix.diagonal([4,8,16])
sage: SK = S.augment(K)
sage: SK.transpose().hermite_form(include_zero_rows=False).transpose().augment(K)
[ 1  0  0  4  0  0]
[ 0  1  0  0  8  0]
[ 2  0  8  0  0 16]
sage: _.right_kernel_matrix()
[ 4  0 -1 -1  0  0]
[ 0  8  0  0 -1  0]
[ 0  0  2  0  0 -1]

However, what we need to know is how to get the generators in the ambient group $A$ that realize the $C_8 \times C_8$ structure from the SNF. We get matrices $U$ and $V$ such that $U K' V$ is the SNF of $K'$. I just don't understand how to use that information to get the desired generators.

---

Side remark: There are inconsistencies with HNF between dense and sparse matrices!

sage: SK.transpose().sparse_matrix().hermite_form(include_zero_rows=False)
...
ValueError: cannot echelonize in place and delete zero rows

This is because HNF is simply the generic echelon_form() (which also is computed by the dense matrix, so it is pointless to not call HNF of the dense matrix in this case!) and has an explicit exception for this.

[dimpase]

Perhaps @AurelPage - the author of the MO answer - can point out more details?

[tscrim]

Just as a reminder, as we get closer to the stable release, we might be better off reverting #36986 since that is a "less bad" bug if we cannot find another workable method.

[dimpase]

let's revert that while we work on a fix