13
$\begingroup$

By the length of a finite presentation I mean the sum of the lengths of the relators. I am interested in knowing what the minimal length of a presentation of $\mathbb{Z}/n\mathbb{Z}$. I'm even more interested in knowing the minimal length of a balanced presentation $\mathbb{Z}/n\mathbb{Z}$.

For concreteness, I am really interested in the particular case of $\mathbb{Z}/173\mathbb{Z}$. For example this has a presentation of length 24 given by $<a,b,c | a^4c, a^3b^5, a^{-2}bc^8>$ - is this a minimal length presentation? Is this presentation minimal length among balanced presentations?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

I can beat that by one.

$$C_{173} \cong \langle a,b,c,d,e \mid a^4=b, b^2=c,c^4=d,d^4=e, abcde=1 \rangle.$$

It might be hard to prove minimality. I am sure the best you can do is $O(\log n)$, but it could be interesting to see what constant you could get. The approach of using squares of successive generators together with the binary expansion of $n$ gives a bound of $4 \log_2 n$, which could be reduced to about $3.5 (\log_2 n+1)$ by using positives and negatives in the binary expansion of $n$.

But I think using cubes and the ternary expansion of $n$ is better in general. That seems to give a bound of $5 (\log_3 n +1)\sim 3.155 \log_2 n+5$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ To get lower bounds you might already look for lower bounds in the variety of abelian groups of exponent dividing $173^2$. $\endgroup$
    – YCor
    Commented Apr 9, 2018 at 8:11
  • $\begingroup$ This problem has been studied in a more general (and sligthly different) context by Ekatarina Pervova and Carlo Petronio in a nice paper Complexity and T ‐invariant of Abelian and Milnor groups, and complexity of 3‐manifoldshttps://onlinelibrary.wiley.com/doi/pdf/10.1002/mana.200510669 $\endgroup$
    – Thomas
    Commented Apr 9, 2018 at 16:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .