4
$\begingroup$

Is there a class of solvable groups $G$ having a derived length $O(\log\lvert G\rvert)$?

See Wikipedia for the definition of Big-Oh ($O$) and the definition of derived series of a group.

Any help would be appreciated. Thank you in advance!

Edit (YCor, after comments below): the intended meaning of big-O is probably not the one linked at, but "$u_n=O(v_n)$" if $c_1v_n<u_n<c_2v_n$ for positive constants $c_1,c_2$ and $n\gg 1$, usually denoted $u_n=\Theta(v_n)$. [The main mathematical use of $u_n=O(v_n)$ being only $u_n<c_2v_n$, which makes the question not interesting.]

$\endgroup$
7
  • 1
    $\begingroup$ $G$ being the group of strictly upper triangular $n\times n$ matrices over $\mathbb F_p$ gives $O(\sqrt{\log|G|})$. $\endgroup$ Commented Apr 29 at 18:19
  • 6
    $\begingroup$ Yes, (nontrivial) abelian groups. Their derived length is $1$, which is $O(\log |G|)$. $\endgroup$
    – Derek Holt
    Commented Apr 29 at 19:10
  • 2
    $\begingroup$ @KentaSuzuki You might be thinking of nilpotence class. The derived length is logarithmic in $n$, so it's much smaller than $\sqrt{\log|G|}$. I guess it's still big-O of it, but it's possible that's not what you intended, nor the original poster. $\endgroup$ Commented Apr 29 at 19:54
  • $\begingroup$ I don’t understand the edit: “$c_1v_n<u_n<c_2v_n$ for positive constants $c_1,c_2$ and $n\gg 1$” is the computer science meaning of $u_n=\Theta(v_n)$, not of $u_n=O(v_n)$. In fact, the $\Theta$ notation was invented by Knuth, a computer scientist, for this very purpose. $\endgroup$ Commented Apr 30 at 9:40
  • 2
    $\begingroup$ I disagree with labelling this misuse of $O$ as being "computer science" usage. The definition of $O$ in computer science is the same as elsewhere in mathematics. I'm sure many people get it wrong, especially in informal contexts, but this is not limited to computer science. As for what was, actually, the question intended by the OP, I think this is hard to guess without further input. Your interpretation may or may not be correct, I won't speculate on that. In any case, Dave Benson's answer clarifies the situation. $\endgroup$ Commented Apr 30 at 11:10

2 Answers 2

10
$\begingroup$

A paper of Glasby, "The composition and derived lengths of a soluble group", shows that if a soluble group $G$ has composition length $n$ then its derived length $d$ satisfies $d < 3 \log_2(n) + 9$. Since $n \leqslant \log_2|G|$, this makes $d<3\log_2\log_2|G|+9$ (assuming $|G|>1$).

Edit: As Will Sawin points out, the group $G$ of $s\times s$ upper triangular matrices over $\mathbb{F}_2$ with ones on the diagonal has $|G|=2^{\binom{s}{2}}$, so $\log_2|G|=\binom{s}{2}<s^2$ and $\log_2\log_2|G|< 2\log_2 s$. The derived length is $d=\lceil \log_2 s\rceil$ and so $d> \frac{1}{2}\log_2 \log_2|G|$.

Let $f(m)$ be the maximum derived length of a soluble group of order $m$, and let $$\alpha=\limsup_{m\geqslant 3,\ m\to\infty}\frac{f(m)}{\log_2\log_2m}.$$ Then the above shows that $\frac{1}{2} < \alpha < 3$, and in fact the paper of Glasby shows that $\alpha<2.578$. It would be interesting to have better estimates for this constant $\alpha$.

Edit 2: Using David Speyer's observation and the example of $3^2\!:\!2S_4\leqslant S_9$ of derived length five, we now have $$\frac{5}{\log_2(9)}\ \leqslant\ \alpha\ \leqslant\ 1+\frac{5}{\log_2(9)},$$ where $5/\log_2(9)\approx 1.577324$.

$\endgroup$
7
  • 2
    $\begingroup$ I've tried to answer the intended question, rather than take big-O literally. $\endgroup$ Commented Apr 29 at 19:55
  • 2
    $\begingroup$ @YCor, re, I take the intended question to be one with what I would call $\Theta$ (or just $\asymp$) in place of $O$, per what Wikipedia says is the use in computer science. $\endgroup$
    – LSpice
    Commented Apr 29 at 20:35
  • 2
    $\begingroup$ I should add that this bound is not particularly sharp, but seems about the right order of magnitude. It would be interesting to know what the actual asymptotics are, in the sense of limb soup. $\endgroup$ Commented Apr 29 at 21:49
  • 5
    $\begingroup$ The $n\times n$ upper-triangular matrices have derived length $(1/2) \log_2 \log_2 |G| +O(1)$ since $|G|= p^{n^2}$ so $\log_2 |G|= n^2 \log p$ and the derived length is $\log_2 n$. So the bound is sharp to within a factor of $6$. $\endgroup$
    – Will Sawin
    Commented Apr 30 at 1:06
  • 2
    $\begingroup$ Now that we have a possible value beating $1.5$, we should actually fill in the details in computing the derived length of $(\cdots ((H \wr H) \wr H) \cdots \wr H) \wr H$. It looks to me like every group in the derived sequence looks something like $L \rtimes R$ where $L$ is the kernel of a map from $(\cdots ((H \wr H) \wr H) \cdots \wr H)$ to an abelian group and $R$ is in the derived sequence of $H$, with the result that each wreath product contributes a factor of $d(H)$ to the derived length of the wreath product. Can you (or someone else) verify this? $\endgroup$ Commented Apr 30 at 14:56
2
$\begingroup$

$\def\ZZ{\mathbb{Z}}\def\Id{\text{Id}}$I can improve Will Sawin's bound by a factor of $2$. Let $G$ be the group of $3 \times 3$ matrices with entries in $\ZZ/2^{\ell+1} \ZZ$ that are $\Id_3 \bmod 2$. This group has cardinality $N=2^{9\ell}$ and composition length $n = 9\ell$. I'll show that it has derived length $$\geq \lfloor \log_2 \ell \rfloor= \log_2 n + O(1) = \log_2 \log_2 N + O(1).$$

Let $U_{ij}(a)$ be the matrix $\Id_3 + 2^a e_{ij}$, where $e_{ij}$ is the matrix with a $1$ in position $(i,j)$ and a $0$ everywhere else. A quick computation checks that $$(U_{ij}(a), U_{jk}(b)) = U_{ik}(a+b)$$ for $i$, $j$, $k$ distinct. Thus, by induction, $U_{ij}(2^r)$ is in the $(r-1)$-st derived subgroup for $i \neq j$ and, in particular, the derived length is at least $\lfloor \log_2 \ell \rfloor$.


Looking at the end of Glasby's paper, he gives a better example.

For a group $A$, let $A \wr S_k$ denote $A^k \rtimes S_k$, where $S_k$ acts on the product $A^k$ by permuting the factors; this is a group of order $|A|^{k} \cdot k!$. Glasby considers the $(r-1)$-fold wreath product $( \cdots ((S_4 \wr S_4) \wr S_4) \cdots \wr S_4) \wr S_4$. It has order $N:=\prod_{j=0}^{r-1} 24^{4^j} = 24^{(4^r-1)/3}$. According to Glasby, $n = (4/3) (4^r-1)= 4 \log_{24} N = c \log_2 N$ and $d = 3r$. (I have partially checked these numbers; I confirm $n = 4 \log_{24} N$ and I find $d=3r$ very plausible, but haven't fully checked it. My earlier comment claiming that Glasby's $n$ looked wrong was mistaken.) So $$d = \tfrac{3}{2} \log_2 n + O(1) =\tfrac{3}{2} \log_2 \log_2 N+O(1).$$

$\endgroup$
7
  • $\begingroup$ I'm not sure about this, but it looks like Glasby's computation generalizes to "if $H$ is a solvable subgroup of $S_k$ with derived length $b$, then we can achieve $\alpha = b/\log_2(k)$. Can anyone beat $S_4$ inside itself? $\endgroup$ Commented Apr 30 at 13:54
  • 3
    $\begingroup$ The subgroup $3^2:2S_4$ of $S_9$ has derived length $5$, achieving $\alpha=5/\log_2(9)\approx $1.577$, which is slightly better. $\endgroup$ Commented Apr 30 at 14:24
  • 2
    $\begingroup$ Your original lower bound with the $3 \times 3$ matrices gives a $p$-group example. For $p$-groups, a better upper bound was known before Glasby's work, due to P. Hall, A contribution to the theory of groups of prime-power order, Proc. London Math. Soc. 36 (1933), 29-95. This upper bound is very close to your lower bound, (also in the natural generalization of matrices over $\mathbb Z/p^{\ell+1}\mathbb Z$) which seems not to have been noticed - Glasby only gives the lower bound from upper triangular matrices. $\endgroup$
    – Will Sawin
    Commented Apr 30 at 16:57
  • 2
    $\begingroup$ Glasby's proof uses two ingredients: This upper bound in the $p$-group case and a bound of Newman that a solvable subgroup of $GL_n(\mathbb F_p)$ has derived length $\leq 5\log_9 (n/8)+14$. It would be great to understand (a) how sharp this bound is and (b) how sharp the argument that combines those two is. The best lower bound I know for the $GL_n$ problem is still the upper-triangular case (or $2\times 2$ block upper triangular for $p=2,3$) which is close to $\log_2 n$, for a gap of $5 \log(2)/2\log(3)=1.577\dots$. $\endgroup$
    – Will Sawin
    Commented Apr 30 at 17:14
  • 2
    $\begingroup$ Actually the $5/\log_2(9)$ example of a solvable subgroup of $S_n$ with large ratio of derived length to log of $n$ is sharp. This follows from work of Dixon discussed in Newman, the Soluble length of soluble linear groups. Newman also shows his upper bound in the linear case is close to sharp, by just taking this permutation group and linearizing. So if the lower bound is not sharp it must come from a construction other than wreath products and if the upper bound is not sharp it must come from the steps in Glasby's paper. $\endgroup$
    – Will Sawin
    Commented Apr 30 at 17:43

You must log in to answer this question.

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