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!
On
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$.)
More concretely, draw a large square around the region where the two grids differ, and let that square grow outwards by one cell each generation. Then the difference between the grids can't ever catch up to and pass outside the boundary of that square. And the growth of the area of the square is quadratic.
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$.