Sameness up to bounded error
Guide 2 left us with an embarrassment: the word metric changes when we change generators. The fix is to declare two metric spaces ‘the same’ if they agree after we forget bounded errors. A map f: X → Y is a quasi-isometry if there are constants L ≥ 1, C ≥ 0 with (1/L)·d(x,x′) − C ≤ d(f(x), f(x′)) ≤ L·d(x,x′) + C for all x, x′, and every point of Y lies within C of the image. It need not be continuous or injective — it is geometry seen from very far away.
Why generators don't matter (up to QI):
Let S, T be two finite generating sets of G.
Each t in T is a word in S, so |t|_S <= M := max_{t in T} |t|_S.
Then for any g: |g|_S <= M * |g|_T (replace each T-letter by <= M S-letters).
Symmetrically |g|_T <= M' * |g|_S.
Hence (1/M') |g|_T <= |g|_S <= M |g|_T : identity map (G,d_S) -> (G,d_T)
is a quasi-isometry with L = max(M, M'), C = 0.
Consequence: a finitely generated group has a WELL-DEFINED
quasi-isometry type, independent of generators. Now QI invariants
are honest invariants OF THE GROUP.How fast does the group grow?
A first quasi-isometry invariant you can compute. The growth function β(n) counts the elements within distance n of the identity: β(n) = #{g : |g| ≤ n}, the size of the n-ball. Its growth rate — polynomial, exponential, or in between — is a quasi-isometry invariant (up to a natural equivalence on functions). It detects deep structure: groups grow exponentially when they contain enough freeness, and polynomially when they are nearly abelian.
Counting balls:
Z : |k| = |k|, so ball of radius n has 2n+1 elements. beta(n) ~ n (LINEAR)
Z^2 : ball is a diamond |x|+|y| <= n. beta(n) = 2n^2+2n+1 ~ n^2 (QUADRATIC)
Z^d : beta(n) ~ n^d (POLYNOMIAL deg d)
F_2=<a,b> : reduced words. #{length exactly n} = 4*3^(n-1) for n>=1.
beta(n) = 1 + 4(3^n - 1)/2 ~ 3^n (EXPONENTIAL)
The free group's tree branches by 3 at every step (you can't immediately
backatrack), so the ball size triples -- exponential growth is visible
in the picture.