Growth of bilinear maps II: Bounds and orders

Abstract

A good range of problems on trees can be described by the following general setting: Given a bilinear map $\ast :{\mathbb{R}}^d\times {\mathbb{R}}^d\to {\mathbb{R}}^d$ and a vector $s\in {\mathbb{R}}^d$, we need to estimate the largest possible absolute value $g(n)$ of an entry over all vectors obtained from applying $n-1$ applications of $\ast$ to $n$ instances of $s$. When the coefficients of $\ast$ are nonnegative and the entries of $s$ are positive, the value $g(n)$ is known to follow a growth rate $\lambda ={\lim }_{n\to \infty }\sqrt[n]{g(n)}$. In this article, we prove that for such $\ast$ and $s$ there exist nonnegative numbers $r,r^{\prime }$ and positive numbers $a,a^{\prime }$ so that for every $n$, \[ a n^{-r}λ^n\le g(n)\le a' n^{r'}λ^n. \] While proving the upper bound, we actually also provide another approach in proving the limit $\lambda$ itself. The lower bound is proved by showing a certain form of submultiplicativity for $g(n)$. Corollaries include a lower bound and an upper bound for $\lambda$, which are followed by a good estimation of $\lambda$ when we have the value of $g(n)$ for an $n$ large enough.

18 pages; minor update for the final version of publication

References in corpus (2)

• On the joint spectral radius of nonnegative matrices
• An asymptotic lower bound on the number of polyominoes

Cited by in corpus (1)

• Growth of bilinear maps III: Decidability