Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2110.15060 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916839040221184 |
|---|---|
| author | Bui, Vuong |
| author_facet | Bui, Vuong |
| contents | A good range of problems on trees can be described by the following general setting: Given a bilinear map $*:\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 $*$ to $n$ instances of $s$. When the coefficients of $*$ are nonnegative and the entries of $s$ are positive, the value $g(n)$ is known to follow a growth rate $λ=\lim_{n\to\infty} \sqrt[n]{g(n)}$. In this article, we prove that for such $*$ and $s$ there exist nonnegative numbers $r,r'$ and positive numbers $a,a'$ 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 $λ$ 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 $λ$, which are followed by a good estimation of $λ$ when we have the value of $g(n)$ for an $n$ large enough. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_15060 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Growth of bilinear maps II: Bounds and orders Bui, Vuong Combinatorics 15A63, 15A69, 05C05 A good range of problems on trees can be described by the following general setting: Given a bilinear map $*:\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 $*$ to $n$ instances of $s$. When the coefficients of $*$ are nonnegative and the entries of $s$ are positive, the value $g(n)$ is known to follow a growth rate $λ=\lim_{n\to\infty} \sqrt[n]{g(n)}$. In this article, we prove that for such $*$ and $s$ there exist nonnegative numbers $r,r'$ and positive numbers $a,a'$ 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 $λ$ 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 $λ$, which are followed by a good estimation of $λ$ when we have the value of $g(n)$ for an $n$ large enough. |
| title | Growth of bilinear maps II: Bounds and orders |
| topic | Combinatorics 15A63, 15A69, 05C05 |
| url | https://arxiv.org/abs/2110.15060 |