Hall–Mal’cev Coordinates and Bass–Guivarc’h Growth

For $K\le {\mathbb{Z}}^n$, induct on $n$. When $n=0$, $K=0$ has the empty basis. For $n>0$, project to the last coordinate: its image is $d\mathbb{Z}$. If $d=0$, apply the induction hypothesis in ${\mathbb{Z}}^{n-1}$. If $d>0$, take $v\in K$ projecting to $d$. For each $x\in K$, write its last coordinate uniquely as $ad$; then $x-av$ lies in the projection kernel $K_0$. Thus $K=\mathbb{Z}v\oplus K_0$: the intersection is zero because $ad=0$ implies $a=0$. A basis of $K_0$ together with $v$ spans and is independent, so has at most $n$ members. Only one lift at each of at most $n$ stages is selected.

Choose a finite ordered generating list of $M$, giving $\pi :{\mathbb{Z}}^n\twoheadrightarrow M$. For any subgroup $L\le M$, its inverse image under $\pi$ is free with a finite basis by step 1.1. Images of that basis generate $L$, since every $l\in L$ has a preimage. In particular $K=\ker \pi$ has a finite basis, whose columns form an integer matrix $A$.

Row swaps, column swaps, sign changes, and adding an integer multiple of another row or column are invertible: undo the swap or sign, or subtract the same multiple. Column operations preserve the image subgroup, while a row operation carries it by an automorphism of ${\mathbb{Z}}^n$ and therefore induces an isomorphism of quotients. If the current rectangle is zero, stop. Otherwise move a nonzero entry to its top left and change its sign to obtain a positive pivot $d$.

If an entry in the pivot row is $a=qd+r$ with $0<r<d$, subtract $q$ times the pivot column and swap that column into the pivot position. The new positive pivot is $r<d$. The same procedure with rows treats the pivot column. If all row and column entries are divisible by $d$, clear them. If the remaining rectangle has an entry $b$ not divisible by $d$, add its row to the pivot row. The first pivot stays $d$, while the pivot row now contains $b$; column division again decreases the pivot. Each failed divisibility therefore strictly decreases a positive integer. Such descents terminate, since the attained pivots have a least member.

The terminal pivot divides the entire rectangle. Clear its row and column and repeat on the smaller rectangle. There are at most $\min (n,\mathrm{columns}(A))$ pivots. The resulting diagonal $d_1,\dots ,d_k>0$ presents the quotient as ${⨁}_{j=1}^k\mathbb{Z}\mathrm{/}{d}_j\mathbb{Z}\oplus {\mathbb{Z}}^{n-k}$: the coordinate quotient map is onto and its kernel is exactly the diagonal image. Delete unit summands, which are zero. A zero matrix has $k=0$; an empty matrix gives the same rule.

Each finite cyclic summand has exactly the $d_j$ residues $0,\dots ,d_j-1$. Their finite product is finite and torsion. A nonzero integer vector has infinite order, since a nonzero coordinate cannot be annihilated by a nonzero integer. Hence the displayed finite summand is exactly the torsion subgroup. In particular a finitely generated torsion group is finite, and a finitely generated torsion-free abelian group is free.

Let $V(M)=\mathrm{Hom}(M,(\mathbb{Q},+))$ with pointwise rational addition and scalar multiplication. The vector space laws follow pointwise from the field laws. A map to $\mathbb{Q}$ kills every finite-order element: $da=0$ implies $a=0$. Evaluation on the $r$ free generators identifies $V(M)$ with ${\mathbb{Q}}^r$: any assigned rational values extend by $\sum n_j{e}_j+t\mapsto \sum n_j{a}_j$, and this is the only extension. If a second decomposition has $r^{\mathrm{\prime }}$ free generators, the resulting two bases of $V(M)$ give $r\le r^{\mathrm{\prime }}$ and $r^{\mathrm{\prime }}\le r$. Thus $r=r^{\mathrm{\prime }}$, including $r=0$.

If $f:M\twoheadrightarrow N$ has finite kernel, every $u:M\to \mathbb{Q}$ kills that kernel by step 7.1. Define $\bar{u}(f(x))=u(x)$; different lifts differ by the kernel, so this is well-defined, additive and unique. Thus precomposition by $f$ is a rational-linear bijection $V(N)\to V(M)$. Transporting bases and applying the independence bound twice proves equal ranks.

$[x,y]y[x,z]y^{-1}=xy{x}^{-1}{y}^{-1}yxz{x}^{-1}{z}^{-1}{y}^{-1}=xyz{x}^{-1}{z}^{-1}{y}^{-1}=[x,yz]$.

$x[y,z]x^{-1}[x,z]=xyz{y}^{-1}{z}^{-1}{x}^{-1}xz{x}^{-1}{z}^{-1}=xyz{y}^{-1}{x}^{-1}{z}^{-1}=[xy,z]$. Also $[x,y{]}^{-1}=yx{y}^{-1}{x}^{-1}=[y,x]$.

If commutators are central, their conjugates in steps 1.1 and 1.2 are unchanged. Each variable then defines a homomorphism on any subgroup where that centrality hypothesis holds. The identity has commutator $1$, and $1=[x{x}^{-1},y]=[x,y][x^{-1},y]$ gives the inverse rule. Repeated multiplication gives positive powers, the identity gives exponent zero, and the inverse rule gives negative powers. Applying this in both variables yields $[x^a,y^b]=[x,y{]}^{ab}$.

Put $P=x[[x^{-1},y],z]x^{-1}$, $Q=z[[z^{-1},x],y]z^{-1}$ and $R=y[[y^{-1},z],x]y^{-1}$. Direct substitution gives $P=yx{y}^{-1}zy{x}^{-1}{y}^{-1}x{z}^{-1}{x}^{-1}$, $Q=xz{x}^{-1}yx{z}^{-1}{x}^{-1}z{y}^{-1}{z}^{-1}$, and $R=zy{z}^{-1}xz{y}^{-1}{z}^{-1}y{x}^{-1}{y}^{-1}$. Cancelling adjacent inverse pairs in $PQ$ gives $yx{y}^{-1}zy{z}^{-1}{x}^{-1}z{y}^{-1}{z}^{-1}=R^{-1}$. Thus $PQR=1$.

For normal $U,V$, $[U,V]$ is normal: conjugation sends its generator $[u,v]$ to $[gu{g}^{-1},gv{g}^{-1}]$. Therefore $N=[[B,C],A][[C,A],B]$ is a normal subgroup (a product of two normal subgroups is a subgroup since its factors can be interchanged). Work in $G\mathrm{/}N$. Substituting $x\in A,y\in B,z\in C$ into step 1.1 makes $Q=R=1$, so $[[x^{-1},y],z]=1$. Replacing $x$ by its inverse shows that every $[a,b]$ commutes with every $c\in C$ in this quotient.

If $u$ and $v$ commute with every $c\in C$ in the quotient, the product identity gives $[uv,c]=u[v,c]u^{-1}[u,c]=1$; and $[u^{-1},c]=1$ follows from $1=[u{u}^{-1},c]$. Consequently every finite product of the generators $[a,b]$ and their inverses centralizes $C$. Hence $[[A,B],C]$ has trivial image in $G\mathrm{/}N$, which is precisely the claimed containment. This includes any of $A,B,C$ equal to $1$.

All ${\gamma }_i$ are characteristic: an automorphism preserving ${\gamma }_i$ preserves the generating commutators for $[G,{\gamma }_i]$; start at $G$. Also $[U,V]=[V,U]$ because $[u,v{]}^{-1}=[v,u]$. For $i=1$, $[G,{\gamma }_j]={\gamma }_{j+1}$ is the required inclusion.

Induct on $i$, uniformly for all $j\ge 1$. Normality and the three-subgroup containment give $[{\gamma }_{i+1},{\gamma }_j]\le [{\gamma }_{j+1},{\gamma }_i][[{\gamma }_j,{\gamma }_i],G]$. By symmetry and the induction hypothesis these two factors lie respectively in ${\gamma }_{i+j+1}$ and $[{\gamma }_{i+j},G]={\gamma }_{i+j+1}$. This proves the inclusion for $i+1$ and every $j$.

Each ${\gamma }_i\mathrm{/}{\gamma }_{i+1}$ is central in $G\mathrm{/}{\gamma }_{i+1}$ and therefore abelian. Replacing $x\in {\gamma }_i$ by $xu$ with $u\in {\gamma }_{i+1}$ changes $[x,y]$ only by commutators of weight at least $i+j+1$ and conjugations of $[x,y]$. The latter also change it only by $[G,{\gamma }_{i+j}]\le {\gamma }_{i+j+1}$. The same argument replaces $y$ by $yv$, $v\in {\gamma }_{j+1}$. Thus the displayed map is independent of representatives.

Modulo ${\gamma }_{i+j+1}$ the conjugations in both product identities disappear, so the pairing sends a product in either input to the product of its values. Identity inputs give identity output; inverses give inverse outputs by applying the product rule to $x{x}^{-1}$. This is biadditivity for the abelian factors, for all positive indices, also when any factor is trivial.

The $i=1$ quotient is generated by the images of $S$. Suppose ${\gamma }_i\mathrm{/}{\gamma }_{i+1}$ is generated by the $i$-fold simple commutators. The next quotient is generated by $[u,g]{\gamma }_{i+2}$ for $u\in {\gamma }_i,g\in G$, since $[{\gamma }_i,G]={\gamma }_{i+1}$. Expand the two entries in their factor generators. Biadditivity expresses this class as a product of the $(i+1)$-fold simple commutators and their inverses. Their number is at most $\mathrm{\mid }S{\mathrm{\mid }}^{i+1}$ before repetitions. This proves the claim by induction.

Abelianness follows from centrality of ${\gamma }_i\mathrm{/}{\gamma }_{i+1}$. In a nilpotent group start with the empty generating list for ${\gamma }_{c+1}=1$. If ${\gamma }_{i+1}$ has a finite generating list and $u_1,\dots ,u_t$ lift factor generators, then for any $g\in {\gamma }_i$ a word $w$ in the $u_j$ has the same coset, so $w^{-1}g\in {\gamma }_{i+1}$. The union of the two finite lists generates ${\gamma }_i$. Descending induction reaches $i=1$; terms after $c$ are trivial. If $S$ is empty, $G=1$ and all lists are empty.

Put $K_i=K\cap {\gamma }_i(G)$. The homomorphism $K_i\to {\gamma }_i\mathrm{/}{\gamma }_{i+1}$ has kernel $K_{i+1}$. Its image is a subgroup of a finitely generated abelian group, so has a finite generating list. Thus $K_i\mathrm{/}{K}_{i+1}$ is finitely generated: explicitly its isomorphism to that image sends $x{K}_{i+1}$ to $x{\gamma }_{i+1}$, with injectivity given by the kernel calculation.

Start with $K_{c+1}=1$. Lift a finite generating list of $K_i\mathrm{/}{K}_{i+1}$ to $K_i$. For $x\in K_i$, a word $w$ in these lifts has coset $x{K}_{i+1}$, so $w^{-1}x\in K_{i+1}$. Consequently those lifts together with generators of $K_{i+1}$ generate $K_i$. There are finitely many layers, hence this gives finite generators of $K_1=K$. Empty factor lists require no lift, and $c=0$ gives $K=1$.

In an abelian group, if $a^m=b^n=1$ with $m,n>0$, then $(ab{)}^{mn}=1$; inverses retain finite order. This also covers the trivial group. For a group of class $c\ge 2$ and $b\in G$, put $B=⟨b,{\gamma }_2(G)⟩$. It is normal, being the inverse image of the cyclic subgroup generated by $b{\gamma }_2$ in the abelianization. Modulo ${\gamma }_3$, ${\gamma }_2$ is central, so two elements $b^{r}u,b^{s}v$ commute. Therefore ${\gamma }_2(B)\le {\gamma }_3(G)$; inductively ${\gamma }_j(B)\le {\gamma }_{j+1}(G)$ for $j\ge 2$, using $[B,{\gamma }_{j+1}(G)]\le {\gamma }_{j+2}(G)$. Thus ${\gamma }_c(B)=1$.

Induct on class for torsion closure, with step 1.1 as base. For torsion $a,b$ in class $c$ with $a^m=1$, the subgroup $B$ has smaller class. Its torsion elements form a subgroup $T(B)$ by induction. Automorphisms preserve orders, so $T(B)$ is characteristic in $B$ and normal in $G$. Now $(ab{)}^m=(ab{a}^{-1})(a^{2}b{a}^{-2})\cdots (a^{m}b{a}^{-m})a^m$ is a product of conjugates of $b$ in $T(B)$. It has finite order, hence so does $ab$. Identity and inverses have finite order; thus $T(G)$ is a subgroup. Preservation of orders under every automorphism makes it characteristic.

For the original finitely generated $G$, $T=T(G)$ is finitely generated and nilpotent. Each of its lower-central factors is finitely generated abelian and torsion, since every representative in $T$ has finite order. An abelian group generated by elements of finite orders $d_1,\dots ,d_t$ has at most $\prod d_j$ elements: reduce each exponent modulo $d_j$. Hence all these factors are finite. Lifting their finite sets through the finite series proves $T$ finite (cardinalities multiply in each finite extension).

The quotient is nilpotent. If $(gT{)}^n=T$ for some $n>0$, then $g^n\in T$, so $(g^n{)}^m=1$ for some $m>0$. Thus $g^{nm}=1$, giving $g\in T$ and $gT=T$. This proves torsion-freeness, also when $T=G$ or $T=1$.

For each fixed $g\in G$, define ${\varphi }_g:Z_2\mathrm{/}{Z}_1\to Z_1$ by ${\varphi }_g(y{Z}_1)=[y,g]$. The value lies in $Z_1$ by the definition of $Z_2$; multiplying $y$ by a central element does not change it. The product identity, with central values, proves ${\varphi }_g$ is a homomorphism. If $y{Z}_1$ has finite order $m>0$, then ${\varphi }_g(y{Z}_1{)}^m=1$. Torsion-freeness of $Z_1$ implies $[y,g]=1$ for every $g$, hence $y\in Z_1$. Thus $Z_2\mathrm{/}{Z}_1$ is torsion-free.

Induct on an upper-central length $c$. For $c=0$ the group is trivial; for $c=1$ the claim is the assumed torsion-freeness of the center. For $c\ge 2$, the group $\bar{G}=G\mathrm{/}{Z}_1$ has length at most $c-1$ and center $Z_2\mathrm{/}{Z}_1$, torsion-free by step 1.1. Recursion on the definitions gives $Z_j(\bar{G})=Z_{j+1}(G)\mathrm{/}{Z}_1$ for $j\ge 0$: after quotienting this subgroup, its next center is exactly the defining next upper-center factor. The induction hypothesis therefore proves torsion-freeness of $Z_{j+2}(G)\mathrm{/}{Z}_{j+1}(G)$; the first factor is torsion-free by assumption.

If $x^m=1$ with $m>0$, its image in $G\mathrm{/}{Z}_{c-1}$ is torsion and therefore trivial, so $x\in Z_{c-1}$. Repeating down the torsion-free factors gives $x\in Z_0=1$. Factors after $Z_c$ are trivial. This proves both conclusions with the stated ascending indices.

The center is a subgroup of torsion-free $G$, so is torsion-free. Every upper-central factor is torsion-free and abelian; it is finitely generated as a quotient of a finitely generated subgroup. Hence it has a finite ordered free basis. Refine it by the spans of its successive basis vectors, omitting zero factors. Lifting to $G$ gives a finite central series: for each lifted intermediate subgroup the commutators with $G$ lie in the previous upper-center subgroup, hence in the previous refined subgroup. Normality follows from this containment. Each new nontrivial factor is infinite cyclic.

Reverse the series and choose one generator lift $u_j$ per cyclic factor. For $g\in H_0$, there is a unique integer $a_1$ with $g{H}_1=u_1^{a_1}{H}_1$. Then $u_1^{-a_1}g\in H_1$. Iterate: at stage $j$ remove $u_j^{a_j}$ on the left. The last remainder is in $H_m=1$, giving $g=u_1^{a_1}\cdots u_m^{a_m}$. All selections are finite; the exponents are uniquely determined, without choices.

If two products are equal, their images in $H_0\mathrm{/}{H}_1$ force equality of their first exponents, since that factor is infinite cyclic. Cancel those first powers and repeat in $H_1\mathrm{/}{H}_2$, obtaining equality of every exponent. The zero tuple represents $1$; when $G=1$, $m=0$ and the single empty tuple represents its identity. Thus the product map is bijective.

Surjectivity gives $q({\gamma }_{1}G)=G\mathrm{/}F$. If $q({\gamma }_{i}G)={\gamma }_i(G\mathrm{/}F)$, then $q([g,u])=[q(g),q(u)]$ shows that the images of the generators of ${\gamma }_{i+1}G$ generate exactly ${\gamma }_{i+1}(G\mathrm{/}F)$. This proves equality for every $i$ and gives a surjection on each factor. Both source and target factors are finitely generated abelian, since a quotient of a finite generating list is finite and the quotient group is nilpotent.

Its kernel in layer $i$ consists of $x{\gamma }_{i+1}$ with $x\in {\gamma }_i\cap F{\gamma }_{i+1}$. Write $x=fy$, $f\in F,y\in {\gamma }_{i+1}$. Then $f=x{y}^{-1}\in F\cap {\gamma }_i$, and $x{\gamma }_{i+1}=f{\gamma }_{i+1}$. Conversely every such $f$ maps to the identity. The kernel is therefore the image of $F\cap {\gamma }_i$, a finite set. Finite-kernel rank preservation gives equal ranks layer by layer. Summing them with weights $i$ or $1$ proves equality of $D$ and $h$.

For $H={\gamma }_c$ and $i<c$, $H\le {\gamma }_{i+1}$, so the map ${\gamma }_i\mathrm{/}{\gamma }_{i+1}\to ({\gamma }_i\mathrm{/}H)\mathrm{/}({\gamma }_{i+1}\mathrm{/}H)$ is bijective: the kernel is zero and every coset lifts. In layer $c$ the quotient factor is trivial, and all later factors of both groups are trivial. Thus its dimension loses exactly $c{r}_c$. For $c=1$ the quotient is $G\mathrm{/}G=1$ and this says $0=D(G)-r_1$. For $G=1$, the first assertions are equality of empty sums.

An $S$-word of length at most $n$ projects to a $qS$-word of that length. Conversely, lift each letter in a $qS$-word to a corresponding letter of $S\cup S^{-1}$; their product lies in $B_S(n)$ and projects to its value. Only finitely many letters of this particular word need lifts. Therefore $q(B_S(n))=B_{qS}(n)$.

Each fiber of $q$ is a coset of $F$, with exactly $\mathrm{\mid }F\mathrm{\mid }$ elements. Its intersection with $B_S(n)$ has at most $\mathrm{\mid }F\mathrm{\mid }$ elements and, over $B_{qS}(n)$, at least one by step 1.1. Summing over the finite target ball yields both inequalities. At $n=0$ both balls contain only the identity, and $1\le 1\le \mathrm{\mid }F\mathrm{\mid }$. For $F=1$ both inequalities are equalities; the empty generating set gives the trivial group.

The images of a finite generating set generate $Q$. The torsion theorem makes $Q$ torsion-free nilpotent, so it has the integral central-refinement coordinates of F3. This invocation is made for $Q$, not for a possibly torsion-bearing $G$.

For either $E=G$ or $E=Q$, take a cyclic decomposition in each lower-central factor and one lift per generator. There are finitely many layers and finite lists. For $g\in E$, project to $E\mathrm{/}{\gamma }_2(E)$, obtain its unique cyclic-factor tuple, and let $p_1$ be the corresponding ordered lifted product. The remainder $p_1^{-1}g$ lies in ${\gamma }_2$. Repeat in ${\gamma }_2\mathrm{/}{\gamma }_3$, obtaining $p_2$; after layer $c$ the remainder is $1$. Thus $g=p_1\cdots p_c$ has the mixed ordered form.

Let $q:G\to Q$ be the quotient map. Induction gives $q({\gamma }_i(G))={\gamma }_i(Q)$: it is clear for $i=1$, and surjectivity sends the generators $[g,x]$ of the next term onto the generators $[q(g),q(x)]$. Hence $q$ induces a surjection ${\gamma }_i(G)\mathrm{/}{\gamma }_{i+1}(G)⟶{\gamma }_i(Q)\mathrm{/}{\gamma }_{i+1}(Q)\mathrm{.}$ If $x{\gamma }_{i+1}(G)$ is in its kernel, choose $y\in {\gamma }_{i+1}(G)$ with $q(x)=q(y)$. Then $t=x{y}^{-1}$ lies in $T(G)\cap {\gamma }_i(G)$ and $x{\gamma }_{i+1}(G)=t{\gamma }_{i+1}(G)$. Conversely every such $t$ lies in the kernel, so the kernel is the image of the finite set $T(G)\cap {\gamma }_i(G)$. The finite-kernel rank clause of [F4] therefore gives equal free ranks for the corresponding factors of $G$ and $Q$. Calling this common rank $r_i$, each construction in step 1.2 has exactly $r_i$ unbounded layer-$i$ exponents.

If two normalized products agree, project to $E\mathrm{/}{\gamma }_2$ to equate all first-layer coordinates, including the canonical residues. Their lifted first-layer products are then literally equal and may be cancelled on the left. Repeating in the next factor equates every coordinate. The identity has the all-zero tuple; for $E=1$ this is the empty tuple. Hence the mixed parametrization is bijective, whether or not some factors contain torsion.

If one instead lifts an integral coordinate representative $w$ of an element of $Q$ to $G$, the fiber consists exactly of the $\mathrm{\mid }T(G)\mathrm{\mid }$ elements $wt$ with $t\in T(G)$. Thus returning from the integral model retains a finite kernel representative. The mixed construction in steps 1.2–2.1 works directly in $G$ and does not discard these elements or identify the two coordinate systems.

For nonidentity $x$, define its depth as the largest $i\le c$ with $x\in {\gamma }_i$. Start with the given finite alphabet, the chosen coordinate lifts, and their inverses. Whenever two available letters $x,y$ have depths $i,j$, add $[x,y]$ and its inverse if nontrivial. Whenever a letter of depth $i$ has finite order $d$ in its factor, add $x^d$ and its inverse if nontrivial. Commutator outputs have depth at least $i+j$; carry outputs have depth at least $i+1$. Inversion preserves depth.

This closure is finite: regard every new letter as an expression built from initial letters by inverse, carry, and binary commutator operations, absorbing inverse into each operation so it is not an extra level. Along any branch of its expression tree, every non-inversion operation strictly increases depth. No branch has more than $c-1$ such operations. Binary trees of bounded height have bounded size; there are finitely many initial labels, and each carry exponent is uniquely determined by its input element. Induction on tree height therefore gives finitely many expressions and values. Closing under all these expressions yields the required alphabet. If $c=0$, it is empty after deleting identity.

Fix any resulting letter of depth $i$. Successive projection in the mixed coordinates writes it as a fixed word in the weight-$i$ coordinate lifts followed by a word of weights at least $i+1$: all earlier coordinates vanish by the uniqueness construction. There are finitely many letters, so the lengths of these replacements have a common finite bound. Replacement of an inverse uses the reversed inverse word, with the same bound. Conversely fixed coordinate lifts also have finite words in any alphabet generating their lower-central term. These words account for finite changes of layer alphabets without treating redundant letters as independent coordinates.

Enlarge the finite alphabet by the fixed coordinate lifts and close it as in F1. Assign each nonidentity letter its actual ambient depth. This can only raise its previous assigned weight; since $R\ge 1$, its cumulative count through depth $j$ is initially at most $j\lambda R^j$. At the start of a layer-$i$ stage, replace each depth-$i$ letter by its fixed word in the chosen layer-$i$ cyclic lifts followed by deeper letters. Replacing $O(R^i)$ letters by uniformly bounded words contributes $O(R^i)\le O(R^j)$ to every depth $j\ge i$. Close the finitely many new alphabets in advance for each of the finitely many layers. No replacement contains a letter of depth below $i$.

Fix one cyclic lift $t$ of weight $i$. Extract its occurrences and inverse occurrences one by one from the uncollected suffix, always taking the leftmost such occurrence. Move this letter to the front of that suffix, after already fixed coordinates, by $xt=tx[x^{-1},t^{-1}]$ (the same identity holds with $t^{-1}$ in place of $t$). Indeed multiplying the right side gives $tx{x}^{-1}{t}^{-1}xt=xt$. A crossing of a depth-$a$ letter creates at most one error of depth at least $a+i$. Place the error to the right of the moving letter; it is not crossed again during this extraction. Thus one extraction crosses each letter of the old suffix prefix at most once. It produces no new weight-$i$ occurrence.

Let $U_j(\mathrm{\ell })$ count all letters of depth at most $j$ in the uncollected suffix after $\mathrm{\ell }$ extractions, before reducing the extracted power. Set $U_j=0$ for $j<i$. The crossing rule gives $U_j(\mathrm{\ell }+1)\le U_j(\mathrm{\ell })+U_{j-i}(\mathrm{\ell })$. Induction on $\mathrm{\ell }$, using $\left(\genfrac{}{}{0px}{}{\mathrm{\ell }}{s}\right)+\left(\genfrac{}{}{0px}{}{\mathrm{\ell }}{s-1}\right)=\left(\genfrac{}{}{0px}{}{\mathrm{\ell }+1}{s}\right)$, therefore gives $U_j(L)\le {\sum }_{s\ge 0,j-si\ge i}\left(\genfrac{}{}{0px}{}{L}{s}\right)U_{j-si}(0)$. There are $L=O(R^i)$ occurrences to extract; every summand is bounded by $O(R^{si})O(R^{j-si})=O(R^j)$. The number of summands is at most $c$, independent of $R$. At intermediate extraction counts the same bound holds.