Solution: Day 2, problem 2

Let the elements of finite order be numbered t₁, ... ,t_N. We claim that any product t_i₁ ... t_{i_r} (1 <= i₁, ... , i_r <= N) is equal to a product t_j₁ ... t_{j_r} of the same length with 1 <= j₁ <= ... <= j_r <= N. This claim proves the result, since then every element of the group generated by t₁, ... , t_N belongs to the finite set t₁^Z ... t_N^Z and hence has finite order. To prove it, we use induction on r, the case r = 1 being trivial. Let x = t_i₁ ... t_{i_r}. Since there are only finitely many representations of x as t_j₁ ... t_{j_r}, there exists one with j_r maximal. By the induction hypothesis we may assume that j₁ <= ... <= j_{r - 1}. But the maximality of j_r and the representation x = t_j₁ ... t_{j_{r - 2}} s t_{j_{r - 1}}, where s = t_{j_{r - 1}} t_{j_r} t^-1_{j_{r - 1}} is an element of finite order and hence equal to t_j for some j, together imply that j_{r - 1} <= j_r , so we are done.

Return to the problems.

Don Zagier 1996