#3749: [with patch; needs work] Request for a method "is_cyclic" for groups in
SAGE
--------------------------+-------------------------------------------------
Reporter: ljpk | Owner: joyner
Type: defect | Status: new
Priority: minor | Milestone: sage-3.2.2
Component: group_theory | Resolution:
Keywords: |
--------------------------+-------------------------------------------------
Changes (by was):
* summary: Request for a method "is_cyclic" for groups in SAGE => [with
patch; needs work] Request for a method
"is_cyclic" for groups in SAGE
Comment:
REFEREE REPORT:
This implementation is wrong and inefficient.
1. Wrong -- the group Z/2 + Z/4 is cyclic.
{{{
sage: AbelianGroup([2,4]).is_cyclic()
True
}}}
2. Inefficient -- even if it were right, the actual way it is coded is
inefficient, since once you find a duplicate you would be done. No need
to iterate through the whole loop then check a flag at the end.
---
I just noticed that the function elementary_divisors on finite abelian
groups isn't documented, in that it doesn't say what it does. Since it
could be ambiguous I wish it were documented.
I think A.is_cyclic() should be true if and only if every element of the
output of elementary_divisors is coprime. Given that factoring prime
powers is fast, the following should be a reasonable is_cyclic function
(and it's only 2 lines!):
{{{
sage: def is_cyclic(A):
v = [a.factor()[0][0] if a else 0 for a in A.elementary_divisors()]
return len(v) == len(set(v))
}}}
This works on finite groups:
{{{
sage: is_cyclic(AbelianGroup([3,5]))
True
sage: is_cyclic(AbelianGroup([2,4]))
False
sage: is_cyclic(AbelianGroup([2,2]))
False
sage: is_cyclic(AbelianGroup([6]))
True
sage: is_cyclic(AbelianGroup([15,1,21]))
False
}}}
This fails on infinite groups since the function elementary_divisors
itself has a bug on infinite groups!
{{{
sage: AbelianGroup([0,5]).elementary_divisors()
...
ArithmeticError: Prime factorization of 0 not defined.
}}}
I think the above should return [0,5].
That said, it is disturbing that elementary_divisors isn't documented, and
moreover the choice of definition is inconsistent with the one for
matrices over ZZ (made by pari, actually):
{{{
sage: a = matrix(ZZ, 3, [0,0,0, 0,5,0, 0,0,3]) ; a
[0 0 0]
[0 5 0]
[0 0 3]
sage: a.elementary_divisors()
[1, 15, 0]
sage: AbelianGroup([5,3]).elementary_divisors()
[3, 5]
}}}
So elementary_divisors for matrices gives invariants d_i where d_1 | d_2 |
...,
With that choice of elementary divisors definition, the is_cyclic function
would be easy:
{{{
def is_cyclic(A):
return len(A.elementary_divisors()) <= 1
}}}
I think the elementary_divisors function for abelian groups could be
"cheesily" fixed for now by just defining things in terms of matrices:
{{{
sage: def elementary_divisors(A):
....: v = A.invariants()
....: return diagonal_matrix(ZZ,v).elementary_divisors()
....:
sage: elementary_divisors(AbelianGroup([5,3]))
[1, 15]
sage: elementary_divisors(AbelianGroup([0,0,5,3]))
[1, 15, 0, 0]
}}}
This obviously sucks because of the waste of memory (a matrix takes more),
but is good because at least it is definitely *correct* and consistent,
and I think correct and consistent is more important than speed. We can
fix the speed later once this consistency is established and tested.
Summary:
1. Change elementary_divisors to use matrices for consistency and
correctness, and fix all corresponding doctests.
2. Change is_cyclic to just be "len(self.elementary_divisors()) <= 1", and
add much better doctests for is_cyclic, e.g, testing infinite groups and
Z/2 x Z/3, etc.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/3749#comment:7>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
