**Intro**


The question is about [Game of Life](http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life). 


Let us denote the set of points obtained from initial configuration $A$ after $m$ steps as $A(m)$ (we are only interested in finite initial configuration, i.e. those one which formed by finite number of marked cells).


Let us denote the number of marked cells at configuration $A$ as $N(A)$. Then increment at $m$-th step could be computed as $i(A, m) = \max(0, N(A(m+1)) - N(A(m))$.


Majority of configurations doesn't grow in size after some number of steps. There are
known examples which grows linearly or quadratically in time. For all of this 
examples the relative increment decay as times goes by: $\frac{i(A,m)}{N(A(m))} \to 0$ as
$m \to \infty$. 


**Question**


Is it possible to prove some uniform result of this type: 


is it true that $\forall \epsilon > 0$ (may be some other restriction) $\exists M\_\epsilon$ such that $\forall A$ (for any arbitrary chosen initial configuration) and $\forall m > M\_\epsilon$: $\frac{i(A,m)}{N(A(m))} < \epsilon$?


May be it makes sense for some good family of initial configurations $A$?




---


This is rather a probe question which I asked with a hope to find some references or ideas in answers which will direct me in more useful settings. 



Decay of Relative Growth in Conway's Game of Life
*[expanded from the comment above]*


There cannot be such a result. The simplest aperiodic counterexample
is a "lightweight spaceship gun" of even period $p$, whose
$m$-th generation has population $9m/p + O(1)$ or $12m/p + O(1)$
according to the parity of $m$, whence
$i(A,m)/N(A(m)) \rightarrow 1/3$ in one congruence class mod $2$.


There are also more complicated counterexamples such as
"[sawtooth](http://en.wikipedia.org/wiki/Sawtooth_(cellular_automaton))"
patterns whose population at time $m$ oscillates between $O(1)$ and $cm+O(1)$,
and for which the same pair $\bigl(N(A(m)),N(A(m+1))\bigr)$ and the same $i(a,M)>0$
occurs infinitely often but for different configurations.


In general it's a reliable heuristic that if you imagine any kind of
behavior of a pattern in Conway's Game of Life then either it's
obviously impossible (e.g. exponential growth, or an aperiodic pattern
that always stays within a fixed rectangle), or somebody has
wasted devoted enough time and/or ingenuity to
construct a pattern showing that behavior.


[For the benefit of those who know little more of Conway's Game of Life
than the basic rules: a "spaceship" or "ship" of period $n$ is a finite pattern
$S$ that after $n$ steps reappears shifted by some translation $T$,
and thus moves through space with speed $T/n$. A period-$p$ "gun"
$G$ for a spaceship $S$ is a finite pattern whose $p$-th generation is
the disjoint union of $G$ with a copy of $S$ that does not further
interact with $G$; thus $G$ produces a stream of ships of type $S$.
The first few Life ships have period $4$; the smallest of these, the
[glider](http://en.wikipedia.org/wiki/File:Game_of_life_animated_glider.gif),
has constant population (namely 5) so cannot be used here, but the next-smallest, the
["lightweight
spaceship" (LWSS)](http://en.wikipedia.org/wiki/File:Game_of_life_animated_LWSS.gif), alternates between populations of $9$ and $12$,
so works for any even $p$. If you know a glider gun of sufficiently large period $p$
(and the classic $p=30$ of
[Gosper's gun](http://en.wikipedia.org/wiki/File:Gospers_glider_gun.gif)
is large enough) then you can position three of them to make an LWSS gun
by colliding their glider streams.]


