Evolutionary Group Theory - or what happens when algebraic groups have sex.
Population Dynamics of Algebraic Groups
We construct a dynamical population whose individuals are assigned elements from an algebraic group \(G\) and subject them to sexual reproduction. We investigate the relationship between the dynamical system and the underlying group and present three dynamical properties equivalent to the standard group properties.
Introduction
Consider a sufficiently large population of \(N\) individuals. Sexual reproduction between individuals is a binary action, that is, sex involves two individuals. An interesting assumption is to consider if the population consists of individuals from an algebraic group. Recall the definition of a group : A set, \(G\), and binary operator \(\ast\) is called a group iff
-
there exists an identity element, \(e\), s.t. \(\forall x \in G, x\ast e=e \ast x = x\).
-
\(\forall x \in G\) there exists an inverse, \(x^{-1}\), s.t. \(x\ast x^{-1}=x^{-1}\ast x = e\).
-
\(\forall x,y \in G, x\ast y \in G\) and \(y\ast x \in G\).
What would the behaviour of a sexual system look like if all individuals were members of a group? Can we find such systems in nature, or are our constructions purely artificial?
Some notation and terminology of Group Theory
We call the order of group \(G\) the number of elements in the group, denoted \(|G|\). A group, \(G\), is called abelian if the operation is commutative, i.e. \(\forall x,y \in G, x\ast y = y\ast x\). A subset \(H \subset G\) is called a subgroup iff \(e\in H, \forall x \in H \Rightarrow x^{-1} \in H\), and \(H\) is closed under the binary operation. A Cayley table of a group is \(n \times n\) matrix where the \((ij)th\) entry is the product of the \(ith\) and \(jth\) element. For example, consider \(\mathbb{Z}_2\times \mathbb{Z}_2=\{(0,0),(1,0),(0,1),(1,1)\}\) under addition mod 2. The Cayley table is \[\left[ \begin{array}{cccc} (0,0) & (1,0) & (0,1) & (1,1)\\ (1,0) & (0,0) & (1,1) & (0,1)\\ (0,1) & (1,1) & (0,0) & (1,0)\\ (1,1) & (0,1) & (1,0) & (0,0) \end{array} \right]\]
This matrix completely defines the group.
A simple stochastic model
We describe a stochastic process that will characterize our evolving population. Consider again a population of \(N\) individuals where \(N_i(t)\) denote the number of \(i\) individuals in the population. We consider the interaction between two individuals to represent sexual reproduction. The birth-death process begins by two individuals being randomly chosen proportional to their frequency in the population. The new offspring ( product of the two individuals) is substituted for another randomly chosen individual, again proportional to frequency (thus the population size is constant). The process is repeated for each time step. For example, consider the group \(\mathbb{Z}_2=\{0,1\}\). Recall that in this group \(1\ast1=0\), so the probability that the population of 1s increases, i.e. \(N_1(t+1) = N_1(t) + 1\), is equal to the probabilty a 1 and 0 are chosen as parents, and a 0 is chosen to die:
\[\begin{aligned} P^{+} &=P(N_1(t+1)=N_1(t)+1| N_1(t))\\ &=\left( \frac{N_1(t)}{N} \frac{N_0(t)}{N-1}+\frac{N_0(t)}{N} \frac{N_1(t)}{N-1}\right) \frac{N_0(t)}{N}\\ &=\left( \frac{2N_1(t)}{N} \frac{N_0(t)}{N-1}\right) \frac{N_0(t)}{N}\end{aligned}\]
since for the population \(N_1(t)\) to increase by one in a time step, the new individual resulting from the interaction must be a 1 and the death must be a 0. Similarly,
\[\begin{aligned} P^{-} &=P(N_1(t+1)=N_1(t)-1| N_1(t))\\ &=\left( \frac{N_1(t)}{N} \frac{N_1(t)-1}{N-1}+\frac{N_0(t)}{N} \frac{N_0(t)-1}{N-1}\right) \frac{N_1(t)}{N}\\\end{aligned}\]
and \(P^{0}=P(N_1(t+1)=N_1(t)| N_1(t))=1-P^{+} -P^{-}\). Thus we have
\[\begin{aligned} E[N_1(t+1)|N_1(t)] &=P^+\cdot (N_1(t)+1)+P^-\cdot (N_1(t)-1)+P^0\cdot (N_1(t))\\ &=P^+-P^-+N_1(t)\Rightarrow\end{aligned}\]
\[E[N_1(t+1)-N_1(t)|N_1(t)]=P^+-P^-\] Working with probabilities can be unwieldy, so we take the limit as \(\Delta t\rightarrow 0\) and \(N \rightarrow \infty\). If we denote\(N_1(t)/N \approx x\) (then \(N_0(t)/N \approx 1-x\)), we have
\[\begin{aligned} &P^+=2x(1-x)^2\\ &P^-=x(x^2+(1-x)^2) \Rightarrow \\ &\frac{dx}{dt} \approx P^+-P^-= x(1-2x)\end{aligned}\]
This system has asymptotically stable points at \(x=0\) and \(x=1/2\), i.e. when the population of 1’s is extinct or equal to the population of 0’s.
General model
Initially, to model such an evolving system, we consider only \(\Delta t\rightarrow 0\) and \(N \rightarrow \infty\). Thus we enter the well-studied realm of continuous dynamical systems. Given a group of order \(n\), we need some way to introduce the group structure into the dynamical system. The Reverse Cayley matrix, \(A\), is defined as an \(n\times n\) matrix where the \(ith\) column of \(A\) contains the product of frequencies such that the product of the corresponding elements is the \(ith\) element of the group. For example, consider \(\mathbb{Z}_2\times \mathbb{Z}_2=\{(0,0),(1,0),(0,1),(1,1)\}\), and let \(e,x,y,z\) denote the frequencies of the enumerated set. Then define \(A\) as \[\left[ \begin{array}{cccc} e^2 & ex & ey & ez\\ x^2 & xe & xz & xy\\ y^2 & yz & ye & yx\\ z^2 & zy & zx & ze \end{array} \right]\] The matrix can easily be constructed from the group Cayley table. In each row, for every element \(g \in G\), there exists a pair of elements such that the product is \(g\). Compare the Reverse Cayley matrix with the the Cayley matrix for \(\mathbb{Z}\times \mathbb{Z}_2\) given in section 2.
The dynamics of the system are given by the following system of equations, analogous to the limiting case in the example with \(\mathbb{Z}_2\). It is straightforward to show the dynamics are the same. In what follows, \(\mathbf{1}\)=(1,1…,1) and \(\mathbf{e_i}\) are the standard euclidean basis vectors and \(x_i\) is the \(ith\) element in the group.
\[\begin{aligned} \dot{x}_j &=P^{+}_{j}-P^{-}_{j}\\ &=\left(\sum^{n}_{i=1}\ A_{ij}\right)(1-x_j) - \left(1-\sum^{n}_{i=1}\ A_{ij}\right)x_j\\ &= \sum^{n}_{i=1}\ A_{ij} - x_j \\ &= \mathbf{1}\cdot A \mathbf{e_j} - x_j \text{ which can also be rewritten, if convenient, as}\\ &=\mathbf{1}\cdot A (-x_1,\ldots, -x_{i-1},1-x_i,-x_{i+1}, \ldots,-x_n)^T\end{aligned}\]
This greatly simplifies our dynamics. In fact, it is now trivial to show that the barycenter of the \(n\)-simplex, \(S_n\), is an interior stable point: suppose the frequency vector \(\vec{\mathbf{x}}=(1/n, \ldots, 1/n)\), then \(A=A(\vec{\mathbf{x}})=\frac{1}{n^2}J_n\), where \(J_n\) is the matrix full of ones, then
\[\begin{aligned} \dot{x}_i &=\frac{1}{n^2}\mathbf{1}\cdot J_n (1/n,\ldots,1-1/n,\ldots, 1/n)^T\\ &=\frac{1}{n^2} n\mathbf{1}\cdot (1/n,\ldots,1-1/n,\ldots, 1/n)^T\\ &=\frac{1}{n}(1-\frac{1}{n}-\ldots -\frac{1}{n})=0\end{aligned}\]
For the rest of the paper, let \(x_1\) represent the frequency of the identity element of the underlying group \(G\). Recall the heuristic definition of an invariant manifold is a manifold, \(N\), such that if the system starts somewhere in \(N\), it stays in \(N\) for all time . A useful concept in this study is the support of an invariant manifold, \(N\), defined as the following: \(i\in Supp(N)\) iff \(x_i>0\) in \(Int(N)\). Define the order of the manifold, denoted \(|N|\), as \(|Supp(N)|\).
Theorem 1
\(\{ i_1, i_2, ...,i_k\}\) is an subgroup of G iff the sub-manifold of the dynamical system with support \(\{ i_1, i_2, ...,i_k\}\) is invariant.
----------------------
Proof
Suppose a population is described by an underlying group \(G\), and \(H\) is a subgroup of \(G\). Let \(\vec{\mathbf{x}}\) denote the frequencies of each member of the population. Suppose the population starts at a point where only members of \(H\) are present. For example, for all \(i\in G \setminus H, x_i=0\). Let element \(i\) not be in \(H\). We can derive \(i\)'s frequency in the population by \(\dot{x}_i=\mathbf{1}\cdot A\mathbf{e_i}\). We then let the system evolve. I claim that all elements in the \(ith\) column of \(A(\vec{\mathbf{x}})\) are zero. If there was an element in the column that was non-zero, say \(x_k x_j\), then \(x_k x_j=x_i\) by definition of the reverse Cayley matrix \(A\). But as \(x_k, x_j\) are non-zero, elements \(k\) and \(j\) belong to \(H\). As \(H\) is a group, this implies \(k \ast j = i \in H\), a contradiction. Thus, as the \(ith\) column is all zero, \(\dot{x}_i=0\).
On the other hand, suppose that \(H\) is not a subgroup. Then there exists \(u,v \in H\) s.t. \(u\ast v =k \not \in H\) thus \(x_k=0\) while \(x_u,x_v>0\). Then \(x_u x_v\) is in the \(kth\) column of \(A\). Thus \(\dot{x}_k=\mathbf{1}\cdot A\mathbf{e_k}>0\) and the system is not invariant.
----------------------
The above proposition implies that not all sub-simplicies of this system are invariant. If we consider the group \(\mathbb{Z}_2\times \mathbb{Z}_2\), then the only invariant manifolds of the system, described in terms of sub-simplicies of \(S_4\), are: the interior of \(S_4\), the interior of the three edges projecting from \((1,0,0,0)\) and the point \((1,0,0,0)\). It is clear that, say, \(\mathbf{e}_2=(0,1,0,0)\) is not an invariant manifold of the system as \((1,0)\ast (1,0) = (0,0) \not= (1,0)\), thus the system will evolve away from that point. It is clear that all invariant sub-manifolds of the dynamical system are actually sub-simplicies of \(S_n\). Both terms will be used interchangeably for the remainder of the paper.
Theorem 2
\(1\in Supp(N)\) for all invariant manifolds, \(N\), of the dynamical system.
----------------------
Theorem 3
If all the 2-dimension simplicies extending from \(\mathbf{e}_1\) are invariant, then the underlying group is abelian.
----------------------
The assumption implies that \(\{e,i\}\) is a subgroup for all \(i \in G\). Thus, by the necessity of (sub)groups, \(i\ast i =e\) for all \(i \in G\). It is a well-known (and interesting) theorem in group theory that this condition implies the group is abelian.
There is an alternative way to describe the dynamical system that will be used in the next proposition. Define \(B_k\) as the binary Cayley matrix s.t. if elements \(i\ast j=k\), then \((B_k)_{ij}=1\) and 0 otherwise, for all \(1 \le k \le n\). Clearly \(\sum_k\ B_k = J_n\) where \(J_n\) is the \(n\times n\) matrix of all ones. A property of \(B_k\) is that the columns of the matrix are the standard euclidean basis vectors. It is simple to show the dynamical system can be rewritten as:
\[\dot{x}_i =\vec{\mathbf{x}}\cdot B_i \vec{\mathbf{x}} -x_i\]
Proposition
The barycenter of an invariant sub-manifold is (asymptotically) stable.
----------------------
Proof
What follows is a partial proof. Taking the time derivative of the Lyapunov function \(V(\vec{\mathbf{x}}) = \sum\ x_{i}^2\) we get
\[\begin{aligned} V'/2 & = \sum_i\ \vec{\mathbf{x}} \cdot x_i B_i \vec{\mathbf{x}} - \sum_i x_{i}^2 \\ & = \vec{\mathbf{x}} \cdot \sum_i \ x_i B_i \vec{\mathbf{x}} - \vec{\mathbf{x}} \cdot I \vec{\mathbf{x}} \\ & = \vec{\mathbf{x}} \cdot ( D-I) \vec{\mathbf{x}}\end{aligned}\]
where \(D = \sum \ x_i B_i\). Next is an exercise to show that \(D-I\) is a (semi) negative definite matrix which is equivalent to showing its eigenvalues are (negative) non-positive. I have not been able to generalize the idea to every system yet.
----------------------
Using this new approach in notation, we can translate the properties of groups, outlined in the introduction, to the language of dynamical systems if the population follows our birth-death process.
Theorem 4
-
Unique Identity Element: the only invariant sub-manifold with order 1 is \(\mathbf{e}_1=(1,0,..,0)\).
-
Unique Inverse Element: \(B_1\) is symmetric.
-
Closure: the interior of the simplex \(S_n\) is invariant.
----------------------
Proof
-
This is clear as the only subgroup of order 1 of any group is \(\{e\}\), thus the only invariant manifold with order 1 is a population of just identity elements. On the other hand, if the only invariant manifold with order 1 is \((1,0,..0)\), then \(\{x_1\}\) is the only subgroup of order 1 of the underlying group. Thus, as \(e\) belongs to every (sub)group, \(x_1=e\).
-
For any \(x \in G\) with enumeration \(i_x\), there exists a 1 in the \(i_x\) column of \(B_1\). This means, there exists a \(y \in G\) s.t. \(x*y=e\). As \(B_1\) is symmetric, this also implies in the \(i_y\)th column of \(B_1\), there is a 1 in row \(i_x\), implying \(y*x=e\) . A remark: this is a poor characteristic of the unique inverse element property, as it relies too much on \(B_i\). I would prefer a more dynamical definition.
-
Follows from the proof of proposition 3.1.
----------------------
Aside from the poor definition of a unique inverse element, it would be a interesting question to ask, if a dynamical system satisfies the three characteristics above then does there exists an underlying group? Let’s tentatively say, if a given dynamical system satisfies the above three properties, we call such a system a Group-Equivalent system. Then, if there exists an underlying group, the system is Group-Equivalent i.e. satisfies the above properties; if a system is Group-Equivalent, does there exist an underlying group “driving” the system? A system driven by group \(G\) is not unique as adding multiplicative constant does not change the dynamics.
Suppose a dynamical system has an underlying group structure. Then by Lagrange’s Theorem (the order of every subgroup of \(G\) divides the order of \(G\)) we know that the order of every invariant sub-manifold divides the order of \(S_n\) (recall \(|Int(S_n)|=n\)). Suppose now that a system is Group-Equivalent, and it is true that this implies an underlying group structure. Can we prove Lagrange’s Theorem using a dynamical approach?
Conclusion
The last few remarks foreshadow the possibilities of studying a dynamical system with an underlying group, or a Group-Equivalent system. Two ideas can next occur: First, we use dynamical systems theory to prove theorems in group theory; second, we use group theory to solve problems involving dynamical systems. I believe the former to be of little value outside of itself; the literature and research in group theory is already so large that this novel approach to group theory will lead to nothing novel in the field as a whole. The latter idea is more fruitful I believe. If it is possible to transform a dynamical system into a system satisfying the properties outlines above, then we can apply very strong ideas from group theory to the system.
Further extensions include including fitness levels to the populations and finding real-world applications of group-driven systems, both of which have been addressed, to some degree, in a companion paper to this, see Extensions of Population Dynamics of Algebraic Groups.
J. Hofbauer, K. Sigmund, The Theory of Evolution and Dynamical Systems. Cambridge UP. 1988.
M. Hirsch, S. Smale, R.L. Devaney Differential Equations, Dynamical Systems & An Introduction to Chaos. Elsevier Academic Press. 2004.
J.A. Gallian, Contemporary Abstract Algebra. Houghton Mifflin. 2006.
C. Davidson-Pilon Extensions of Population Dynamics of Algebraic Groups Submitted to Journal of Theoretical Biology 2011.