función de crecimiento de los grupos

Question

¿Puede alguien decir cómo demostrar que la función de crecimiento del grupo aditivo de los enteros está polinomialmente acotada por arriba? Tengo la intuición de que no está acotada polinómicamente, pero no puedo demostrarlo. Tal vez sea muy sencillo, pero me he quedado atascado, así que cualquier ayuda será muy apreciada.

Answer 1

Tomemos el conjunto generador simétrico $\{+1,-1\}$ . Elija una secuencia de hasta $n$ elementos y sumarlos. La secuencia se compone de $+1$ y $-1$ 's, digamos $k$ de $+1$ y $l$ de $-1$ , donde $k,l \in \{0,1,...,n\}$ y $k+l \le n$ . La suma es igual a $$k \cdot (+1) + l \cdot (-1) = k-l \in \{-n,-n+1,...,n-1,n\} $$ por lo que la suma es una de las $2n+1$ enteros de $-n$ a $n$ . Por lo tanto, la función de crecimiento está limitada por la función polinómica de primer grado $2n+1$ .