# On the growth rate of Conway's game of life.

I'm reading a book in which Conway's game of life is mentioned: the author states that it can be proved that the growth rate cannot be exponential but it's at most quadratic.

Can someone suggest me some reference for a proof of this statement? Thanks!

If you have a finite configuration of living cells, it fits inside an $$N \times N$$ bounding box, for some large $$N$$. Over the next $$t$$ generations, no matter what your finite configuration is doing, it cannot affect anything outside an larger $$(N+2t) \times (N+2t)$$ bounding box (padded by $$t$$ cells on each side).
Therefore the number of living cells in the $$t^{\text{th}}$$ generation is at most $$(N+2t)^2$$, which is a quadratic function of $$t$$.
Consider two infinite Game of Life grids that are identical except for some bounded region (for instance one can be completely dead and one can have finitely many live cells). Then the region where they differ in the next generation can at most extend a single cell beyond the region where they currently differ. So a difference between the two grids can propagate and spread by at most a single cell per generation. (Incidentally, this speed is called $$c$$. A glider moves at $$c/2$$.)