Opened 13 years ago
Closed 13 years ago
#1284 closed defect (fixed)
[with patch, with positive review] G.subgroup([...]) for G an abelian group has at least one lame property
Reported by: | was | Owned by: | rlm |
---|---|---|---|
Priority: | minor | Milestone: | sage-3.0.3 |
Component: | algebra | Keywords: | |
Cc: | fwclarke | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Francis Clarke to sage-support Subgroups of abelian groups: sage: G.<a, b> = AbelianGroup(2) sage: A = G.subgroup([a]) sage: B = G.subgroup([b]) sage: A == B True Surely not! On the other hand for vector spaces: sage: W.<u, v> = QQ^2 sage: U = W.subspace([u]) sage: V = W.subspace([v]) sage: U == V False As expected.
I have verified this and I agree that this is stupid. The problem is that the cmp method is just comparing the groups abstract structure:
if not is_AbelianGroup(right): return -1 return cmp(self.invariants(), right.invariants())
It should also take into account the embedding.
Attachments (1)
Change History (25)
comment:1 Changed 13 years ago by
- Milestone changed from sage-2.10 to sage-2.9.1
comment:2 Changed 13 years ago by
- Owner changed from somebody to rlm
- Status changed from new to assigned
comment:3 Changed 13 years ago by
- Summary changed from G.subgroup([...]) for G an abelian group has at least one lame property to [with patch, needs review] G.subgroup([...]) for G an abelian group has at least one lame property
comment:4 Changed 13 years ago by
- Summary changed from [with patch, needs review] G.subgroup([...]) for G an abelian group has at least one lame property to [with patch, negative review] G.subgroup([...]) for G an abelian group has at least one lame property
Negative review: if I understand the code for __contains__
in the first patch correctly, it looks very inefficient. There must be vastly better ways of handling finite abelian groups than this: the code is the equivalent of testing whether m divides n by repeated subtraction instead of division with remainder.
Of course I may be wrong, and perhaps having an inefficient implementation temporarily is better than the wrong answers reported in the orginal posting. Does the patch solve that, by the way? It would be good to have a doctest which proced it but I did not see one.
comment:5 Changed 13 years ago by
John,
You're right about the efficiency part. I was just trying to take the code from not working to working. Will post another patch soon.
comment:6 Changed 13 years ago by
Hi John, Robert,
I would even go so far and choose a working, but slow/sucky implementation over a future perfect one. Perfection is the enemy of the good. Since this issue has made it into trac three times I would like to have this ticket resolved in 3.0.2. So assuming this work let's merge it as is and open an enhancement ticket for a proper fast implementation.
Thoughts?
Cheers,
Michael
comment:7 Changed 13 years ago by
+1
comment:8 Changed 13 years ago by
- Cc fwclarke added
Since Francis reported this bug initially let's get him uptodate on this ticket. I didn't look at the ticket in detail, but we should certainly add a doctest that test this specific bug for obvious reasons :)
Cheers,
Michael
comment:9 Changed 13 years ago by
Sorry for the missing doctest, however:
sage: G.<a,b> = AbelianGroup(2) sage: A = G.subgroup([a]) sage: B = G.subgroup([b]) sage: A == B False
comment:10 Changed 13 years ago by
Yes, the original problem is solved, but others remain. With the two patches installed:
sage: G.<a, b> = AbelianGroup(2) sage: H.<c> = AbelianGroup(1) sage: H < G True
which is not what I would expect. There is no reason to assume H is a subgroup of G.
But anyway __cmp__
and __contains__
are inconsistent. For
sage: c in H True sage: c in G False
Moreover
sage: A = G.subgroup([a]) sage: A == H False sage: H == A True
comment:11 Changed 13 years ago by
With this latest patch:
sage: G.<a, b> = AbelianGroup(2) sage: H.<c> = AbelianGroup(1) sage: H < G False sage: c in H True sage: c in G False sage: A = G.subgroup([a]) sage: A == H False sage: H == A False
I know it's still missing some documentation, I just want to see if there is more work necessary.
comment:12 Changed 13 years ago by
- Component changed from basic arithmetic to algebra
- Milestone changed from sage-3.0.2 to sage-wishlist
I am beginning to think the problem is rather deeper. There are many inconsistencies in the way that algebraic objects are implemented. It should be possible for a user to learn the basic syntax for, say, rings, and then adopt most of the basics when working with vector spaces, or abelian groups, etc.
Some examples of inconsistent behaviour follow.
sage: R.<r> = PolynomialRing(QQ) sage: S.<s> = PolynomialRing(QQ) sage: R == S False sage: R.ideal(r^2 - 1) < S True
sage: U.<u1, u2> = QQ^2 sage: V.<v1, v2> = QQ^2 sage: U == V True sage: W = VectorSpace(QQ, 2) sage: U == W True sage: W.<w1, w2> = VectorSpace(QQ, 2) --------------------------------------------------------------------------- <type 'exceptions.TypeError'> Traceback (most recent call last) /Users/mafwc/<ipython console> in <module>() <type 'exceptions.TypeError'>: VectorSpace() got an unexpected keyword argument 'names'
In my experience of doing calculations (rather than looking at the code) number fields have the best implementation of the algebraic objects which I have encountered . But even so there are things that could be improved. For example:
sage: K.subfield((theta^4 + 26*theta)/84) (Number Field in theta0 with defining polynomial x^3 - 2, Ring morphism: From: Number Field in theta0 with defining polynomial x^3 - 2 To: Number Field in theta with defining polynomial x^6 + 40*x^3 + 1372 Defn: theta0 |--> 1/84*theta^4 + 13/42*theta)
Here a subfield is generated by a single element. There is no definition for a subfield generated by a list of elements; K.subfield([(theta^4 + 26*theta)/84])
leads to a long, unhelpful error message. In contrast, subgroups of abelian groups and subspaces of vector spaces must be generated by a list.
Surely X.subobject([x,y,z])
should be standard, with X.subobject(x)
equivalent to X.subobject([x])
. Ideals of rings work well in this respect:
sage: R.<r> = PolynomialRing(QQ) sage: R.ideal([r^2, r^3]) Principal ideal (r^2) of Univariate Polynomial Ring in r over Rational Field sage: R.ideal(r^2 - 1) Principal ideal (r^2 - 1) of Univariate Polynomial Ring in r over Rational Field sage: R.ideal([r^2 - 1]) Principal ideal (r^2 - 1) of Univariate Polynomial Ring in r over Rational Field sage: R.ideal([r^2 - 1, r - 1]) Principal ideal (r - 1) of Univariate Polynomial Ring in r over Rational Field
But
sage: R.ideal([r^2, r - 1]) Principal ideal (1) of Univariate Polynomial Ring in r over Rational Field sage: R == R.ideal([r^2, r - 1]) False
and at the moment there doesn't seem to be any subring construction, while is_subring
restricts itself to 'natural' inclusions.
One thing that appears to be missing from most (all?) the algebraic objects is intersection of subobjects.
Probably what is needed to to rethink, and eventually, rewrite all the standard algebraic categories in a consistent and standard way.
comment:13 Changed 13 years ago by
I agree strongly with Francis on this. There are serious issues here which cannot be dealt with by treating the problem as a small bug that can be fixed with a small patch.
comment:14 Changed 13 years ago by
Actually, the issue I was treating with these patches was in fact a pretty deep bit of circular logic in the abelian group code. Perhaps we can close this ticket, open another for the division optimization, and move the discussion to sage-devel?
comment:15 Changed 13 years ago by
- Summary changed from [with patch, negative review] G.subgroup([...]) for G an abelian group has at least one lame property to [with patch, needs review] G.subgroup([...]) for G an abelian group has at least one lame property
John,
I've addressed your concerns regarding efficiency. I think that the rest of Francis' complaints are not specific to abelian groups, so I say that this ticket is finished. We should move the rest of his complaints to another ticket. My guess is that in many cases people are implementing __cmp__
for equality/inequality testing only, which gives adverse results for < and <=. The problem is that __cmp__
assumes that exactly one of <, ==, or > holds, which isn't true unless the ordering is linear-- in particular this isn't the case in general for subobjects.
comment:16 Changed 13 years ago by
OK. But I haven't time right now to do any testing, so I haven't looked at patches 3 and 4 and haven't tested any of it so you'll need to find someone who has.
Changed 13 years ago by
comment:17 Changed 13 years ago by
comment:18 Changed 13 years ago by
On the above thread, it is nearly unanimous that G<=H
should mean "Is G a subgroup of H?". Therefore, I propose we merge the patch as-is, and create a ticket to provide is_subgroup
functionality.
comment:19 Changed 13 years ago by
- Milestone changed from sage-wishlist to sage-3.0.3
I agree with rlm. Could someone review trac1284-flattened.patch? Then we can take it from there with a new ticket.
Cheers,
Michael
comment:20 follow-up: ↓ 21 Changed 13 years ago by
Sorry about this, but: we all agreed that H<=G should mean "H is a subgroup of G" and have nothing to do with order-comparison. But you still have H<G meaning such an order-comparison! As a user I would expect H<G to mean "H is a proper subgroup of G" so that (H<=G) == ((H<G) or (H==G)) and (H<G) == ((H<=G) and not (H==G)).
So I would be happier if < and > were defined this way!
comment:21 in reply to: ↑ 20 Changed 13 years ago by
Replying to cremona:
Sorry about this, but: we all agreed that H<=G should mean "H is a subgroup of G" and have nothing to do with order-comparison. But you still have H<G meaning such an order-comparison! As a user I would expect H<G to mean "H is a proper subgroup of G" so that (H<=G) == ((H<G) or (H==G)) and (H<G) == ((H<=G) and not (H==G)).
So I would be happier if < and > were defined this way!
Look more carefully: this is exactly what they *are* defined to do.
comment:22 Changed 13 years ago by
Apologies -- you are right of course. It's a bit late in the evening where I live. I'll test applying the patch to 3.0.2 on Monday, but the code does appear to do what we agree it should.
comment:23 Changed 13 years ago by
- Summary changed from [with patch, needs review] G.subgroup([...]) for G an abelian group has at least one lame property to [with patch, with positive review] G.subgroup([...]) for G an abelian group has at least one lame property
The immediate problem with abelian groups has been solved, and all the group-related problems posted with this patch are dealt with by this patch, which I think can go ahead.
The wider problems raised by Frances are not touched by this and should somehow be preserved in a new patch. I also believe that the whole f.g. abelian groups implementation would benefit from a rewrite using ultra-efficient matrix operations (HNF and SNF) to do everything; but that would be a serious undertaking, and talk is cheap...
comment:24 Changed 13 years ago by
- Resolution set to fixed
- Status changed from assigned to closed
Merged in Sage 3.0.3.alpha0. Somebody please open up a follow up ticket with the issues Frances described.
Cheers,
Michael
This fixes the bugs at #2272 and #3127 as well.