4
$\begingroup$

Let $M$ be a finitely generated abelian group. Assume we are given a presentation of $M$, that is \begin{equation*} M = \frac{\bigoplus_{i=1}^r \mathbf{Z}g_i}{\sum_{j=1}^s \mathbf{Z} r_j} \end{equation*} where the $g_i$ are the generators and the $r_j$ are the relations.

Let $x$ be an element of $M$, given as a linear combination of the generators. I want to express $x$ as a linear combination of the generators of the shortest length (EDIT : the length of a linear combination $\sum_{i=1}^r \lambda_i g_i$ is the number of nonzero $\lambda_i$'s). Is there an efficient algorithm to do this?

If that helps, I know that $M$ is torsion free and that $x$ generates the kernel of a family of linear operators on $M$ (given explicitly in terms of the generators).

My motivation for asking comes from the theory of modular symbols. If $M$ denotes the space of modular symbols of weight 2 on $\Gamma_0(N)$ and $x_E^\pm$ is the modular symbol associated to an elliptic curve $E/\mathbf{Q}$ of conductor $N$, I want to express $x_E^\pm$ as a short linear combination of the Manin symbols $\{g_i 0, g_i \infty\}$ with $g_i \in \Gamma_0(N) \backslash \mathrm{SL}_2(\mathbf{Z})$.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ It would be nice if you could state what you already know, for instance when $M = \mathbb{Z}$ is generated by $g_1 = 2$ and $g_2 = 3$ and the like. $\endgroup$
    – Luc Guyot
    Commented Dec 23, 2017 at 9:48
  • 2
    $\begingroup$ You could try to compute an elementary divisors basis of the numerator such that a relation is just a multiple of an element from that basis. $\endgroup$
    – tj_
    Commented Dec 23, 2017 at 15:05
  • 2
    $\begingroup$ Burago proved that given a word metric in $\mathbf{Z}^d$, there exists a norm on $\mathbf{R}^d$ with rational polyhedral unit ball, such that the word length is equal to the restriction to the norm plus a bounded error. [D. Yu. Burago, Periodic metrics, in Representation Theory and Dynamical Systems, 205-210, Adv. Soviet Math. 9 Amer. Math. Soc. (1992).] I don't know how quantitative the proof is, but this should help getting an idea. $\endgroup$
    – YCor
    Commented Dec 23, 2017 at 16:30
  • 1
    $\begingroup$ PS if I remember correctly, the polyhedron in my previous comment is the obvious one: the convex hull of the (symmetrized) generating subset. In particular, an optimal writing for a word should use a bounded number of letters outside extremal points of this polyhedron (for instance in $\mathbf{Z}$ with 1,2, we use 1 at most once; in $\mathbf{Z}$ with 2,3, we use 2 at most twice...). $\endgroup$
    – YCor
    Commented Dec 23, 2017 at 17:12
  • 3
    $\begingroup$ Putting the matrix of relations into its Smith normal form and using the by-product transformation matrices yields an $k \times r$ matrice $A$ over $\mathbb{Z}$ of rank $k = \text{rank}_{\mathbb{Z}}(M)$ whose columns correspond to the generators $g_i$. Finding the shortest length of a word on $g_1,\dots, g_r$ is equivalent to find the minimum of the $\ell_1$ norm on the solution set of $Ax = b$ for some input $b \in \mathbb{Z}^r$. In the case $M = \mathbb{Z}$, we just look at the diophantine equation $\sum_i a_i x_i = b$. $\endgroup$
    – Luc Guyot
    Commented Dec 23, 2017 at 17:38

0

Reset to default

You must log in to answer this question.