CAAP – QM Decomposition Approach

1. Introduction

The topic of this post is the QM decomposition approach to computer-assisted aperiodicity proof (CAAP).

Table of Contents
1. Introduction
2. Definitions
3. QM Composition of a Periodic Resultant Sequence
4. QM Composition of an Aperiodic Resultant Sequence
5. CAAP Using QM Decomposition – I
6. CAAP Using QM Decomposition – II
7. QM Decomposition of an R Sequence – Manual Search
8. QM Decomposition of an R Sequence, Automatic Search, PVA M0 Sequence, Top-Down
9. QM Decomposition of an R Sequence, Automatic Search, PVA M0 Sequence, Bottom-Up
10. SEQ 806.4 R Sequence QM Decomposition Verification
11. SEQ 806.dv R Sequences – QM Decomposition Extrapolation
12. Open Questions
13. What’s Next?

Sections 3 and 4 discuss using QM to compose an r sequence. “Q” stands for a q sequence, which is always periodic. “M” stands for an m sequence, which is a series of mutations applied a q sequence. The application of a mutation sequence m to a periodic sequence q creates an r (resultant) sequence, which may or may not be aperiodic.

Sections 5 through 11 discuss the decomposition of an r sequence into q and m sequences such that the q and m sequences found facilitate aperiodicity proof.

The author investigated the QM decomposition approach to CAAP between March 2023 and August 2023.

2. Definitions

Figure 1.1 provides an example of a q sequence. The q sequence shown is periodic with period 5 and is constructed from the repeating block [1 0 0 1 1].

A mutation sequence m consists of indicies into a q sequence. Each index is the position of a mutation applied to the q sequence. A mutation flips a q sequence element’s value from 0 to 1 or vice-versa. In contexts in which the mutation sequence is differenced, the m sequence containing positions is called m0; the sequence consisting of first differences (velocities) is called m1, and the sequence consisting of second differences (accelerations) is called m2, and so on. Figure 1.1 shows an m0 sequence in both numerical and graphical form; the associated m1 and m2 sequences are also shown. The m0 sequence shown can be described by the [initial-position initial-velocity constant-acceleration] [P V A] triplet [2 1 1]. PVA m0 sequences will feature prominently in this post.

Figure 1.2 shows how an r (resultant) sequence can be generated by applying the mutations specified by an m0 sequence to a q sequence. An r sequence can be either periodic or aperiodic depending upon the nature of the mutation sequence applied, as will be discussed in subsequent sections. If we define µ as the mutation operator, the process of using q and m sequences to generate an r sequence can be written as q µ m ==> r (q mutated by m generates r). In contrast, when an r sequence is decomposed into q and m sequences, the process can be written as r ==> q µ m (r decomposed into q and m).

The infinite-length versions of the sequences mentioned in this section are indicated with apostrophe: q’, m0′, m1′, m2′, and r’.

3. QM Composition of a Periodic Resultant Sequence

Figure 2.1 shows a q sequence constructed from the length 5 repeating block [1 0 0 1 1]. The blocks are shown in alternating green and red color. A single mutation is applied to the q sequence at index 23. The resulting r sequence is piecewise periodic, with the mutation position separating the two periodic pieces. The mutated block is shown in gold. This is the first small step toward aperiodic r sequences, showing that a mutation can disrupt periodicity.

Figure 2.2 shows a q sequence constructed from the same repeating block as in Figure 2.1. The mutation sequence m0 applied to q can be described as [P V]:length = [1 7]:16, where P is position and V is velocity. The resulting r sequence is periodic with period 35. The period is the least common multiple of block length 5 and mutation velocity 7. The block length and mutation velocity interact to produce a length 35 meta-block, as shown in Figure 2.2.

Figure 2.3 shows a q sequence constructed from the same repeating block as in Figure 2.1. The mutation sequence m0 applied to q alternates between two velocities and can be described as [P [V1 V2]]:length = [1 [3 4]]:16, where P is position and [V1 V2] are the velocities. The resulting r sequence is periodic with period 35. The block length and two mutation velocities interact to produce a length 35 meta-block, as shown in Figure 2.3.

The mutation velocity sequence m1 for the sequence m0 in Figure 2.2 can be described as {7 7 7 7 … }. The m1 sequence is periodic with period 1. The mutation velocity sequence m1 for the sequence m0 in Figure 2.3 can be described as {3 4 3 4 3 4 3 4 … }. The m1 sequence is periodic with period 2. The resultant sequences in Figures 2.2 and 2.3 are both periodic. In general, a mutation sequence m0 with an associaged periodic m1 sequence applied to a q sequence produces a periodic r sequence. A meta-block is always formed in this scenario. This can be written succintly as q µ m0 ==> r (periodic) when m1 is periodic. The infinite length version is q’ µ m0′ ==> r ‘(periodic) when m1 is periodic.

4. QM Composition of an Aperiodic Resultant Sequence

This section provides an intuitive understanding of the claim that q µ m0 ==> r (aperiodic) when m1 is aperiodic.

Figure 3 shows the r sequence that results when a stepped-velocity m0 sequence is applied to a period 5 q sequence generated by the repeating block [1 1 0 0 1]. The mutation sequence is generated as follows:

  • the initial mutation position m0 is located at q sequence index 2
  • the mutation velocities m1 are 7 for 20 iterations, then 8 for 20 iterations, then 9 for 20 iterations, etc.
  • the mutation accelerations m2 are 0 for 19 iterations and then 1 for one iteration, 0 for 19 iterations then 1 for one iteration, 0 for 19 iterations then 1 for one iteration, etc.

The mutation sequence can be described succintly as:
m0 = {2 9 16 … }
m1 = {7 7 7 … 7 8 8 8 … 8 9 9 9 … 9 10 10 10 … 10 11 11 11 …}
m2 = {0 0 0 … 1 0 0 0 …. 1 0 0 0 …. 1 0 0 0 … 1 0 0 0 …}

The Figure 3 r sequence shows that for the span in which the mutation velocities are 7, a meta-block of length 35 is created, as expected. Then, when the mutation velocity jumps to 8, a meta-block of length 40 is created (the least common multiple of 5 and 8). For mutation velocities of length 9, the meta-block length is 45 (the least common multiple of 5 and 9), and for mutation velocities of length 10, the meta-block is length 10 (the least common multiple of 5 and 10).

The mutation velocities m1 associated with the stepped-velocity mutation sequence m0 are aperiodic (the mutation velocity increases without limit). The mutation velocity aperiodicity manifests in the r sequence as the repeated ‘disruption’ of a meta-block once formed. All of the meta-blocks in the r sequence have a finite lifespan; when a mutation velocity changes the existing meta-block ends and a new meta-block is created. For r’, the infinite-length version of r, this process of repeated meta-block formation disruption continues forever. Therefore, r’ is aperiodic.

5. CAAP Using QM Decomposition – I

Computer-Assisted Aperiodic Proof (CAAP) using QM decomposition involves decomposing an r’ sequence into a q’ and m0′ sequences such that the particular q’ and m0′ sequences found facilitate proving that r’ is aperiodic. If the m1′ (velocity) sequence associated with the m0′ (position) sequence is obviously or easily proven aperiodic, then it’s only necessary to show that q’ µ m0′ = r’ to prove that r’ is aperiodic. This section provides two examples of m0′ sequences, one where the associated m1′ sequence is obviously aperiodic, and another where the aperiodicity is much less obvious.

Example 1: Figure 4.1 shows the decomposition of the SEQ 806.4 r sequence into a q sequence created by the length 3 repeating block [1 0 0] and an m0 sequence that can be described as [P V A]:L = [4 9 2]:42, where P = Position, V = Velocity, A = Acceleration, and L = Length. The m1 (velocity) sequence is obviously aperiodic, increasing by 2 r sequence elements each iteration. The corresponding infinite length mutation sequence m0′ = [4 9 2]:INF also has an obviously aperiodic m1′ velocity sequence.

Example 2: Figure 4.2 shows the decomposition of the SEQ 806.4 r sequence into a q sequence created by the length 2 repeating block [1 0] and an m0 sequence that lacks a simple description. The m1 (velocity) sequence is not obviously aperiodic, although upon close inspection it appears that the interval between the appearance of velocity 5 grows larger as the sequence progresses, suggesting that m1 is in fact aperiodic. The m2 (acceleration) sequence is provided for completeness. The uncommon event is the [+4 -4] acceleration pair that brackets each appearance of velocity 5. The corresponding infinite length mutation sequence m0′ also lacks a simple description.

Both of the QM decompositions of the SEQ 806.4 r sequence shown in Examples 1 and 2 are correct. In each case, r ==> q µ m0. QM decomposition search succeeds when it finds a particular QM decomposition that facilitates proving that r’ is aperiodic. The primary criterion for QM decomposition search success is therefore utility. I suspect that a mathematician would find it much easier to prove that r’ ==> q’ µ m0′ when q’ = {[1 0 0] …} and m0′ = [4 9 2]:INF as in Example 1 rather than the much more complex m0′ shown in Example 2, where q’ = {[1 0] …} and m0′ lacks a simple description. So, Example 1 provides a potentially useful QM decomposition for SEQ 806.4 r sequence aperiodicity proof whereas Example 2 is probably much less useful.

6. CAAP Using QM Decomposition – II

This article formalizes computer-assisted aperiodicity proof (CAAP) employing QM decomposition. The approach to CAAP presented in this post will be called CAAP2 to distinguish it from other versions. Figure 5 provides a 10-step process for CAAP2:

(1) Inquirer provides r’ to the Analyst and asks whether r’ is aperiodic.

For example, the Inquirer could send the Combination of Delayed Periodic Sequences (CDPS) algorithm for generating SEQ 806.4 to the Analyst.

(2) The Analyst generates r from r’.

For example, the Analyst could use the SEQ 806.4 CDPS algorithm to generate the first 16,384 elements of the r’ sequence.

(3) The Analyst sends r to the Computer.

(4) The Computer searches the r sequence for a QM decomposition such q µ m0 = r and it is straightforward to prove that m1 is aperiodic.

For example, Figure 4.1 shows the QM decomposition of the SEQ 806.4 r sequence into q and m0; m1 is obviously aperiodic (has constant positive acceleration).

(5) The Analyst converts the q and m0 sequences found into q’ and m0′ sequences, respectively.

For example, as discussed in Section 5 the q and m0 sequences shown in Figure 4.1 are easy to convert into q’ and m0′ sequences.

(6) The Analyst provides the m0′ sequence to the Mathematician, and asks whether the associated m1′ sequence is aperiodic.

(7) The Mathematician proves that m1′ is aperiodic and provides the proof to the Analyst.

(8) The Analyst provides q’, m0′, and r’ to the Mathematican, and asks for proof that r’ can be decomposed into q’ and mp’.

(9) The Mathematican proves that r’ can be decomposed into q’ and mp’ and provides the proof to the Analyst.

(10) The Analyst reports to the Inquirer that r’ is aperiodic.

There are three failure points within CAAP1:
(1) the Computer fails to find a suitable QM decomposition for the r sequence;
(2) the Mathematician fails to prove that the m1′ sequence is aperiodic;
(3) the Mathematician fails to prove that r’ can be decomposed into q’ and m0′.

7. QM Decomposition of an R Sequence – Manual Search

In the manual search for a QM decomposition of an r sequence, the user directs the search by identifying candidate q sequences. For each q sequence identified by the user, the computer calculates the associated m0 sequence such that r = q µ m0. This section describes how QMSA1 supports the manual search approach.

Figure 6 shows how QMSA1 supports the SEQ 806.4 r sequence QM decomposition shown in Figure 4.1. In this case, the user has identified a q sequence consisting of the [1 0 0] repeating block as a candidate. The method by which the user arrived at this candidate q sequence will vary depending upon the particular r sequence being decomposed and is beyond the scope of this post. QMSA1 generates the m0 (position) sequence from the r and q sequences. The user then requests that m0 be shown. The resulting m0 sequence is shown in red. The user then requests the differencing of m0, which generates the m1 (velocity) sequence. The user then requests that m1 be shown. The same procedure is used to generate and show the m2 (acceleration) sequence. Upon observing the constant acceleration in the m2 sequence, the user would conclude that m0 can be described as [P V A]:L = [4 9 2]:42 and halt the QM decomposition search.

8. QM Decomposition of an R Sequence, Automatic Search, PVA M0 Sequence, Top-Down

QMSA1 supports the automatic search for the QM decomposition of an r sequence where the m0 sequence can be described by PVA (position, velocity, and constant acceleration). QMSA1 supports two techniques for searching for a PVA m0 sequence QM decomposition:
(1) top-down (exhaustive);
(2) bottom-up (data-driven).
This section discusses the top-down approach. The next section deals with the bottom-up approach.

Figure 7 shows top-down search for the SEQ 806.4 r sequence. The user specifies a range of q sequence repeating block lengths to search (not shown), and then QMSA1 exhaustively checks each block within the range to see if it has an associated PVA m0 sequence. The figure shows that repeating blocks are checked in the following order: [0], [1], [0 0], [1 0], [0 1], [1 1], [0 0 0], and [1 0 0]. QMSA1 detected a PVA m0 sequence associated with the q sequence composed of the [1 0 0] repeating block, and thus stopped searching. In this case, [P V A] = [4 9 2]. If search had continued the other 6 blocks of length 3 would have been checked.

The QMSA1 top-down search algorithm doesn’t attempt to optimize the search by eliminating larger repeating blocks that duplicate smaller blocks. For example, if there isn’t a PVA m0 sequence associated with the [0] repeating block, then there certainly is not one associated with the [0 0] or [0 0 0] repeating blocks.

The advantages of QMSA1 top-down search are: (1) it is guaranteed to find a q sequence with an associated PMA m0 sequence as long the repeating block length is within the range of block lengths checked; and (2) the algorithm is simple to implement in software. The disadvantage of QMSA1 top-down search is that the number of blocks to check for each block length increases exponentially as block length increases. The number of blocks to check is 2^L for a block of length L. Section 11 shows that the block length that results in a PVA m0 sequence can be quite large depending upon the particular r sequence being decomposed. The top-down approach is impractical for such r sequences.

9. QM Decomposition of an R Sequence, Automatic Search, PVA M0 sequence, Bottom-Up

9.1. Introduction

This section discusses the bottom-up approach to the automatic search for a QM decomposition of an r sequence where the m0 sequence is PVA. Using r sequence data as the source for the repeating blocks used to generate candidate q sequences avoids top-down search’s exponentially increasing number of possible blocks as the block length increases. If a QM decomposition where the m0 sequence is PVA exists for the given r sequence, the primary challenge associated with data-driven search is that any contiguous sequence of r sequence elements used as the repeating block for creating a q sequence may contain one or more PVA m0 sequence mutations. The q sequence that results from using a block containing such mutations is valid for QM decomposition of the r sequence but is unlikely to yield a PVA m0 sequence. Therefore, QMSA1 must identify and remove such mutations from the block before constructing a q sequence.

A PVA m0 sequence has mutations that become less frequent (i.e., the mutation density declines) as the r sequence index increases. It is easiest to find blocks that are free of mutations (or have relatively few mutations) on the far right side of the r sequence (i.e., maximum r sequence indicies). Therefore, QMSA1 constructs a q sequence using repeating blocks (Q blocks) derived from the far right side of the r sequence.

9.2. Q, RM, and NRM blocks

The QMSA1 user specifies the range of block lengths to search. For each block length examined, QMSA1 extracts the rightmost (RM) and next-rightmost (NRM) blocks from the r sequence data. Figure 8.1 shows length 6 RM and NRM blocks extracted from an arbitrary-length r sequence.

The convention is that blocks used to construct a q sequence (Q blocks) are aligned with the left side of the r sequence (i.e., r sequence index 0 corresponds to Q block index 0, r sequence index 1 corresponds to Q block index 1, etc.) In this post, the terms “Q block” and “LM block” (leftmost block) are used interchangeably. There is no guarantee that a Q block when repeated to the end of the q sequence will be perfectly aligned with the right side of the q sequence (i.e., the last element of the q sequence corresponds to index L-1 of the last Q block). Figure 8.1 shows an example of this misalignment – the RM block straddles two repeating length 6 Q blocks.

9.3. Differences between NRM and RM blocks

There are three possible cases to consider:
(1) no difference between the NRM and RM blocks;
(2) one difference between the NRM and RM blocks;
(3) two of more differences between the NRM and RM blocks.
These three cases will be dealt with below.

Case 1: no difference between the NRM and RM blocks

Figure 8.1 shows that there are two sub-cases when there is no difference between the NRM and RM blocks: A) there are no mutations within either block, or B) there is one mutation with each block, and they affect the same block index in both blocks. The location of a mutation is marked with an ‘m’ in the figure. Although sub-case A) should be much more common than B), QMSA1 must confirm that sub-case A) is indeed the case by employing the left-shift algorithm (LSA). In the LSA, the NRM and RM blocks are repeatedly shifted left one element until a difference is detected between the two blocks (if the blocks are shifted all the way to left side of the r sequence without finding a difference, the r sequence is periodic). For sub-case A), the LSA will find the first mutation located on the left side of the two blocks. For sub-case B), the LSA will eventually shift the two blocks to the left of the second mutation, leaving only the first. For both sub-cases, the QMSA1 LSA eventually finds exactly one difference between the NRM and RM blocks and thus Case 1 becomes Case 2.

Case 2: one difference between the NRM and RM blocks

Figure 8.2 provides an example where there is exactly one difference between the NRM and RM blocks. In this example, Q block index 4 differs between the two blocks. The possible locations of a mutation are marked with a “v”. QMSA1 does not know whether the mutation that caused the difference between the two blocks is located within the NRM or RM block. Therefore, QMSA1 generates a q sequence using each of the possible values for block index 4: 0 or 1. For each q sequence, QMSA1 calculates the associated m0 sequence and checks whether it is PVA. When QMSA1 finds a QM decomposition of the r sequence that has a PVA m0 sequence, it halts the search and indicates to the user that the QM decomposition search has been successful.

Case 3: two of more differences between the NRM and RM blocks

Figure 8.3 provides an example where there are two differences between the NRM and RM blocks. In this example, indicies 2 and 4 differ between the two blocks. QMSA1 generates a q sequence using each of the possible joint values for block indicies 2 and 4: [0 0], [0 1], [1 0], and [1 1]. For each q sequence, QMSA1 calculates the associated m0 sequence and checks whether it is PVA. When QMSA1 finds a QM decomposition of the r sequence that has a PVA m0 sequence it halts the search and indicates to the user that the QM decomposition search has been successful.

9.4. Maximum number of NRM/RM block differences parameter

The QMSA1 user specifies the maximum number of differences permitted between the NRM and RM blocks. If QMSA1 finds that the number of NRM/RM differences is greater than the user-specified maximum for a certain NRM/RM block pair, then no QM decompositions are performed for the NRM/RM block length, and the next block length within the user-specified range of block lengths is checked. There is a risk, therefore, that if the maximum number of NRM/RM differences is set too low then QMSA1 could miss a QM decomposition that results in a PVA m0 sequence. The maximum number of NRM/RM differences parameter prevents an exponential increase in the number of QM decompositions performed as the block length increases. As shown in Section 11, the block length sometimes becomes quite large before a QM decomposition resulting in a PVA m0 sequence is found by QMSA1.

9.5. QM decomposition search example

Figure 8.4 shows QMSA1 in action on the SEQ 806.4 r sequence. The first 1024 elements of the 50,000 element r sequence are shown. First blocks of length 1 are checked, then length 2, and finally length 3.

For the blocks of length 1, leftmost (LM) blocks [0] and [1] are used to generate a q sequence. Neither of the QM decompositions results in a PVA m0 sequence, so the search continues with blocks of length 2.

For the blocks of length 2, the LM blocks [0 0] and [1 0] are used to generate a q sequence. Neither of the QM decompositions results in a PVA m0 sequence, so the search continues with blocks of length 3.

For blocks of length 3, the first LM block ([1 0 0]) used to generate a q sequence results in a QM decomposition of the r sequence where m0 is PVA, thus the search halts. The listing shows that for the block of length 3 QMSA1 initially found no differences between the NRM and RM blocks, and left-shifted the RM block by 277 elements to find the first difference between the NRM and RM blocks. The listing shows that RM block indicies need to be converted into LM block indicies prior to QM decomposition; this is why the listing mentions ‘rotating’ the RM block indicies.

9.6. QM decomposition search user interface

Figure 8.5 shows the QMSA1 QM decomposition user interface. Some notes:

  • option 6244: the user can specify the maximum length of the m0 sequence that is provided to the built-in detectors. A large r sequence may result in the generation of a large m0 sequence from a particular q sequence. This parameter allows the user to limit the size of the m0 sequence generated in the interest of efficiency. For example, a length 2,048 m0 sequence results in a length 2,046 m2 sequence, which a user might conclude is sufficient data to determine whether the m0 sequence is PVA (all m2 sequence values are positive and equal). Also, since the ultimate length of the m0 sequence is not known prior to generation, having the user specify a maximum length means that the software need not dynamically allocate additional array space as the m0 sequence is generated.
  • option 6252: the “ax+b” detector watches for an m0 sequence that can be generated with the recurrence relation m0[i+1] = a * m0[i] + b. For example, when a = 2 and b = 3, then this detector would fire if m0[i+1] = 2 * m0[i] + 3 for all elements of the m0 sequence.

10. SEQ 806.4 R Sequence QM Decomposition Verification

Previous sections have stated that there exists a QM decomposition of the SEQ 806.4 r sequence such that the m0 sequence is PVA. This section provides independent verification of this claim when the r sequence is length 16,384.

Figure 9 shows the first 1,024 elements of the length 16,384 SEQ 806.4 r sequence generated using the CDPS algorithm. The figure then shows how SEQ 806.4 can be manually generated using QM generation (q µ m0 ==> r):
(1) A q sequence is created consisting of the [1 0 0] repeating block.
(2) The m0 sequence described by [P V A] = [4 9 2] is applied to the q sequence.
The length 16,384 r sequences generated by the CPDS algorithm and QM generation are then compared and determined to be equal.

11. SEQ 806.dv R Sequences – QM Decomposition Extrapolation

The SEQ 806.dv family of r sequences may all have QM decompositions where m0 is PVA.

Figure 10.1 shows the PVA m0 sequences for the first 11 806.dv r sequence QM decompositions. These m0 sequences were found using the QMSA1 bottom-up algorithm described in Section 9. The figure shows that the m0 sequences can be readily extrapolated to any delay velocity dv as follows:

  • A[dv] = 2;
  • V[dv] = dv + 4 for dv odd; V[dv] = dv + 5 for dv even;
  • P[dv] = P[dv-1] – 3 for dv odd (P[1] = 1); P[dv] = { [P V A] = [3 1 2] accelerating sequence } for dv even.
    There is one complication: for dv = 8, 10, and 11, the extrapolated PVA m0 sequence values are forward-iterated once. As shown in the figure, a single reverse iteration generates the PVA m0 sequence associated with the r sequence. For example, for SEQ 806.8, the extrapolated m0 sequence PVA values are [12 13 02] but the QM decomposition of the SEQ 806.8 r sequence results in an m0 sequence described by PVA [01 11 02]. Presumably, this phenomenon continues for SEQ 806.dv r sequences with dv higher than 11.

Figure 10.2 shows the SEQ 806.dv family q sequences corresponding to the PVA m0 sequences shown in Figure 10.1. Presumably, these q sequences can be extrapolated but the method is unknown. Since the m0 sequences can be readily extrapolated and the r sequence is known, the q sequence for any m0 sequence of interest can be easily derived.

12. Open Questions

(Q1) Prove that q’ µ m0′ ==> r’ (periodic) when m1′ is periodic (Section 3).

(Q2) Prove that q’ µ m0′ ==> r’ (aperiodic) when m1′ is aperiodic (Section 4).

(Q3) Use CAAP2 (Section 6) to prove that the SEQ 806.4 r’ sequence has a QM decomposition such that the m0′ sequence can be described as [P V A] = [4 9 2]:INF (Section 5 / Figure 4.1).

(Q4) Find an algorithm generating an r’ sequence having a QM decomposition such that the m0′ sequence can be described by the recurrence relation m0′[i+1] = a * m0′[i] + b, where a and b are constants (Section 9.6).

(Q5) SEQ 806.dv QM decomposition: prove that the PVA m0 sequence extrapolation conjecture presented in Section 11 / Figure 10.1 is true.

(Q6) SEQ 806.dv QM decomposition: how to extrapolate the q sequences associated with the PVA m0 sequences (Section 11 / Figure 10.2)?

13. What’s Next?

If there is sufficient interest, I can post the C-language source code developed during my investigation into CAAP using QM decomposition. Please contact me if interested.

I don’t have any immediate plans to do further work on this topic.