Timeline for Finding short linear combinations in abelian groups
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 23, 2017 at 19:57 | history | edited | François Brunault | CC BY-SA 3.0 |
Added the definition of the length of a linear combination
|
| Dec 23, 2017 at 19:50 | comment | added | François Brunault | @all Thank you very much for your ideas, I will study them. Regarding the definition of the length of a linear combination, I simply take the cardinality of the support (ok, this is not a particularly natural metric, but it is adapted to my computations). My guess was that (in my case) it is not too hard to obtain a length roughly equal to the rank of $M$, but I hope to do better (on my examples the length is $\approx 3/5$ the rank on average). I don't know a good algorithm except the brute force one, which has tremendous complexity. | |
| Dec 23, 2017 at 19:16 | comment | added | YCor | I expect that when $M$ is given, there is a very efficient algorithm (and even something akin to a formula, depending on the class modulo some fixed number). But I don't claim this should be very efficient if $M$ is part of the input. | |
| Dec 23, 2017 at 17:38 | comment | added | Luc Guyot | 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$. | |
| Dec 23, 2017 at 17:12 | comment | added | YCor | 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...). | |
| Dec 23, 2017 at 16:30 | comment | added | YCor | 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. | |
| Dec 23, 2017 at 16:15 | history | edited | François Brunault |
edited tags
|
|
| Dec 23, 2017 at 16:12 | comment | added | François Brunault | @tj_ I haven't thought about this approach but in some sense I need to keep track of the original generators. In the special case where the module of relations is $\langle g_1,\ldots,g_{r'} \rangle$ I agree that the answer is trivial. In my case however each relation involve 2 or 3 generators -- they are of the form $g_i+g_j $ or $g_i+g_j+g_k $. | |
| Dec 23, 2017 at 16:03 | comment | added | François Brunault | @Luc Guyot In the special case $r=2$ and $\mathrm{rk}(M)=1$ the module of relations is generated by a single vector $ag_1+bg_2$ with $(a,b)=1$ since $M$ is torsion free. Then a generator $x$ of $M$ cannot be a multiple of some $g_i $ unless $a$ or $b $ is $\pm 1$. I don't know if such an analysis extends for $r>2$. | |
| Dec 23, 2017 at 15:05 | comment | added | tj_ | 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. | |
| Dec 23, 2017 at 9:48 | comment | added | Luc Guyot | 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. | |
| Dec 23, 2017 at 6:05 | history | asked | François Brunault | CC BY-SA 3.0 |