Dependencies

For \(k \in \mathbb {N}\), \(X_{\le k}\) (below) filters genes with rank \(\le k\), and \(X_{{\gt} k}\) (above) filters genes with rank \({\gt} k\). We have \(X = X_{\le k} + X_{{\gt} k}\).

A chromosome is a finitely supported function \(X \colon \mathtt{Gene} \to \mathbb {N}\), i.e. a formal sum of genes with non-negative integer multiplicities. We write \(\mathtt{Chromosome} = \mathtt{Gene} \to _0 \mathbb {N}\).

For chromosomes \(X\) and \(Y\), we say \(X\) dominates \(Y\) (written \(Y \le X\)) if \(\mathrm{sig}(X^{(k)}) \le \mathrm{sig}(Y^{(k)})\) componentwise for all \(k \ge 0\), where \(X^{(k)}\) denotes the \(k\)-th derivative.

The lift operation is an additive homomorphism mapping a gene \((n, \varepsilon )\) to \((n+1, -\varepsilon )\).

The prime (derivative) operation \(X \mapsto X'\) is the additive homomorphism that maps a gene \((n, \varepsilon )\) with \(n \ge 1\) to \((n-1, -\varepsilon )\), and sends genes of rank \(0\) to \(0\).

The rank of a chromosome \(X\) is \(\mathrm{rank}(X) = \sum _g X(g) \cdot \mathrm{rank}(g)\).

The signature of a chromosome \(X\) is the additive extension: \(\mathrm{sig}(X) = \sum _{g} X(g) \cdot \mathrm{sig}(g) \in \mathbb {Q} \times \mathbb {Q}\).

A gene \(g = (n, \varepsilon )\) consists of a rank \(n \in \mathbb {N}\) and a type \(\varepsilon \in \mathtt{GeneType}\).

The signature of a gene \(g = (n, \varepsilon )\) is a pair \((a, b) \in \mathbb {Q} \times \mathbb {Q}\) defined by:

• If \(\varepsilon = \mathtt{NonPolarized}\): \((a,b) = (n/2,\, n/2)\).

• If \(\varepsilon = \mathtt{Positive}\): \((a,b) = (\lceil n/2 \rceil ,\, \lfloor n/2 \rfloor )\).

• If \(\varepsilon = \mathtt{Negative}\): \((a,b) = (\lfloor n/2 \rfloor ,\, \lceil n/2 \rceil )\).

A gene type is one of three polarization types: \(\mathtt{NonPolarized}\), \(\mathtt{Positive}\), or \(\mathtt{Negative}\). There is a natural involution \(\varepsilon \mapsto -\varepsilon \) that swaps \(\mathtt{Positive}\) and \(\mathtt{Negative}\) and fixes \(\mathtt{NonPolarized}\).

A pair \((X, Y)\) of chromosomes forms a mutation if:

1. \(X \ne Y\),

2. \(\mathrm{sig}(X) = \mathrm{sig}(Y)\),

3. \(Y \le X\) (dominance).

A chromosome is non-polarized if every gene in its support has type \(\mathtt{NonPolarized}\).

A chromosome \(X\) is polarized if every gene in its support has type \(\ne \mathtt{NonPolarized}\).

The prime operation on varieties induces a permutation of the five labels: \(V_i' = V_{\pi (i)}\).

Every chromosome decomposes as \(X = X_{\mathrm{odd}} + X_{\mathrm{even}}\) where \(X_{\mathrm{odd}}\) (resp. \(X_{\mathrm{even}}\)) collects genes of odd (resp. even) rank.

A primitive mutation on \(\mathrm{Pi}\) is one of the three types above (up to adding a common chromosome \(Z\)).

A step on \(\mathrm{Pi}\) is a primitive mutation plus an arbitrary summand: \(\mathrm{Step}(X+Z, Y+Z)\) whenever \(\mathrm{Primitive}(X, Y)\).

Given \(\varepsilon \), \(k \le m\): \(X_1 = (m, \varepsilon ) + (k, -\varepsilon )\) and \(Y_1 = (m+1, -\varepsilon ) + (k-1, \varepsilon )\) (when \(k \ge 1\)).

Given \(\varepsilon \), \(k \le m\): \(X_2 = (m, \varepsilon ) + (k, \varepsilon )\) and \(Y_2 = (m+1, \varepsilon ) + (k-1, \varepsilon )\) (when \(k \ge 1\)).

Given \(\varepsilon \), \(k \le m\): \(X_3 = (m, \varepsilon ) + (k, -\varepsilon )\) and \(Y_3 = (m+2, -\varepsilon ) + (k-2, \varepsilon )\) (when \(k \ge 2\)).

For a chromosome \(X\), the sigma sequence is the function \(\sigma _X(k) = \mathrm{sig}(X^{(k)}) \in \mathbb {Q} \times \mathbb {Q}\). We write \(a_X(k) = \sigma _X(k).1\) and \(b_X(k) = \sigma _X(k).2\).

A variety is an additive submonoid of \(\mathtt{Chromosome}\).

The five labeled varieties \(V_0, \ldots , V_4\) indexed by \(\mathrm{Fin}\, 5\) are:

• \(V_0 = \mathrm{Pi}\)

• \(V_1 = \mathrm{Mix}(\mathrm{Pi}, \mathrm{Lambda})\)

• \(V_2 = \mathrm{Lambda}\)

• \(V_3 = \mathrm{Mix}(\mathrm{Lambda}, \mathrm{Pi})\)

• \(V_4 = \mathrm{Mix}(\mathrm{Lambda}, \mathrm{Lambda})\)

The variety \(\mathrm{Lambda}\) is the filtered variety of all non-polarized chromosomes.

Given a pair of varieties \((V_1, V_2)\), the mixed variety \(\mathrm{Mix}(V_1, V_2)\) consists of all chromosomes whose odd part lies in \(V_1\) and even part lies in \(V_2\).

The variety \(\mathrm{Pi}\) is the filtered variety of all polarized chromosomes.

Given a predicate \(p\) on genes, the filtered variety \(V_p\) consists of all chromosomes whose support satisfies \(p\).

For any chromosome \(X\), the sum of the two signature components equals the rank: \(\mathrm{sig}(X).1 + \mathrm{sig}(X).2 = \mathrm{rank}(X)\).

If \(X, Y \in \mathrm{Pi}\) satisfy \(\mathrm{sig}(X^{(k)}) = \mathrm{sig}(Y^{(k)})\) for all \(k \ge 0\), then \(X = Y\).

For any gene \(g\), we have \(a(g) + b(g) = \mathrm{rank}(g)\).

If \(X \ne 0\), then \(\mathrm{maxRank}(X') {\lt} \mathrm{maxRank}(X)\).

Given a mutation \((X, Y)\) in variety \(V_i\) with \(X' = Y'\), there exists \(Z \in V_{\pi (i)}\) such that \((Z, Y)\) is a mutation in \(V_{\pi (i)}\) and \(Z' = X\).

Type 1 mutations satisfy \(Y_1 \le X_1\).

Type 1 mutations preserve the signature at all levels: \(\mathrm{sig}(X_1^{(k)}) = \mathrm{sig}(Y_1^{(k)})\) for all \(k\).

Type 2 mutations satisfy \(Y_2 \le X_2\).

Type 2 mutations preserve the signature at all levels.

Type 3 mutations satisfy \(Y_3 \le X_3\).

Type 3 mutations preserve the signature at all levels.

\((X')_{\mathrm{even}} = (X_{\mathrm{odd}})'\) and \((X')_{\mathrm{odd}} = (X_{\mathrm{even}})'\).

Every primitive mutation satisfies the mutation conditions.

For \(X, Y \in \mathrm{Pi}\), if \(X \le Y\) and \(Y \le X\), then \(X = Y\). Hence \(\mathrm{Pi}\) carries a partial order.

\(\mathrm{Lambda}' = \mathrm{Lambda}\).

The prime operation is a left inverse to lift: \((\mathrm{lift}\, X)' = X\) for all \(X\).

\(\mathrm{Pi}' = \mathrm{Pi}\).

If \(p\) is lift-stable (i.e. \(p(g)\) iff \(p(\mathrm{lift}(g))\)), then the prime of a filtered variety is itself: \(V_p' = V_p\).

The sigma sequence is antitone (componentwise decreasing).

If \(X \in \mathrm{Pi}\), then \(a_X(k) - b_X(k+1) \le 1\) and \(b_X(k) - a_X(k+1) \le 1\).

If \(X {\lt} Y\) in \(\mathrm{Pi}\), then \(\sigma _X(k) \le \sigma _Y(k)\) componentwise for all \(k\) with strict inequality for some \(k\).

There exists \(K\) such that \(\sigma _X(k) = 0\) for all \(k \ge K\).

The components of the sigma sequence satisfy interlacing inequalities. If \(k\) is even, then \(b_X(k+1) \le a_X(k)\) and \(a_X(k+1) \le b_X(k)\). If \(k\) is odd, the inequalities are reversed.

If \(X \in \mathrm{Pi}\), the signature components of \(X\) are natural numbers.

For any \(X, Y \in \mathrm{Pi}\) with \(\mathrm{rank}(X) = \mathrm{rank}(Y) = n\) and \(Y \le X\), either \(X = Y\) or there exists a step mutation from \(X\) towards \(Y\): there exist \(X' \in \mathrm{Pi}\) with \(\mathrm{Step}(X, X')\) and \(Y \le X' {\lt} X\).