1
$\begingroup$

If $G$ is a group, by a presentation of a group $G$, I mean a representation of $G$ by generators and relations.

If we have that the bound on a presentation length is $O({\left( {\log \;\left| G \right|} \right)^2})$ [Babai et al.], and you have a presentation of length e.g. 136 and the order of your group is e.g. 20160, how do you know whether or not your length 136 is within the bound of $O({\left( {\log \;20160} \right)^2})$? My problem might be understanding the asymptotic notation, as I am not that familiar with it.

$\endgroup$
0
$\begingroup$

Saying that the length is $O((\log |G|)^2)$ means that there is an unknown constant $K$ such that the length is at most $K(\log |G|)^2$. Since we don't know what $K$ is, and the author of the author of the paper probably does not care, you cannot possibly judge the correctness of the assertion from a single group $G$.

The information from a group $G$ only enables you to find a lower bound for the constant, so you would need a range of examples of different sizes $|G|$ in order to make a sensible assessment of $K$ and whether the bound is correct.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.