#17792: Word problem for FareySymbol
-------------------------------------+-------------------------------------
Reporter: mmasdeu | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.7
Component: modular forms | Resolution:
Keywords: farey symbol, | Merged in:
SL2Z, word problem | Reviewers:
Authors: Marc Masdeu | Work issues:
Report Upstream: N/A | Commit:
Branch: | 18e034409e8b62c81821e93132a11dd15d7fd432
public/ticket/17792 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by mmasdeu):
Replying to [comment:8 vdelecroix]:
> Quoting Sage in order to prove that you are right is wrong ;-) This
Tietze representation is AFAIK something internal to GAP system (which is
1-based). IMHO The fact that we used it as a non hidden attribute in free
group is wrong. I did not find any mathematical reference mentioning
"Tietze representation".
Both GAP and Magma use this representation (yes, they are both are
1-based, also). In any case, converting back and forth consists of two one
liners:
{{{
sage: gapway = [sgn(a)*(i + 1) for i,a in yourway for _ in range(abs(a))]
sage: yourway = [(a-1,len(list(g))) if a > 0 else (-a-1,-len(list(g))) for
a,g in groupby(gapway)]
}}}
>
> When somebody calls "word problem" he/she is even expecting a list of
generators! Using > the (possibly more compact) list of `(gen, power)` is
fine. Replacing `gen` with its
> index is already a little bit of a hack.
I am not so sure about this. Magma users get a "Tietze" list when they do
the word problem for (say) units of quaternion orders. It is the one that
comes out naturally out of any kind of "reduction" algorithm (like the one
done in Farey symbols) and it might be good for input into other
functions, so I would advocate for avoiding the extra processing.
A list of the type (gen,power) is unlikely to be more compact as soon as
you have more than two generators, also.
I like your Factorization alternative, but I see two problems with it:
1. Again, the user might want the more "raw" data, which we threw away.
2. Suppose you have a group homomorphism defined by the images of the
generators, which you stored in a list. How would you evaluate this
homomorphism on a given group element? Well, you call the word_problem
function, and then you still need to keep doing linear searches on your
list of generators to figure out their index. This information was known
to the `word_problem` method and you just threw it away...
> I would be happy to fix the `Factorization._repr_` if you like this
solution.
What about having a `word_problem` method and a `factor` method? The first
one can be as it is now, the `factor` could output a `Factorization`
object exactly like you suggest, which would be good for visualizing but
maybe not so much for programming.
> Very elegant and very natural!
I do agree ;-).
--
Ticket URL: <http://trac.sagemath.org/ticket/17792#comment:9>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
