1. Introduction
In this post I compare the s sequence and QM decomposition approaches to Computer-Assisted Aperiodicity Proof (CAAP). I employ the terminology and definitions introduced in the individual posts dedicated to each of these approaches.
Table of Contents
- Introduction
- Comparison of CAAP1 (S Sequence) and CAAP2 (QM Decomposition)
- Comparison of the SEQ 806.4 S Sequence and QM Decompositions
- CAAP1 (S Sequence) or CAAP2 (QM Decomposition): Which is Better?
- A Rosetta Stone for CAAP?
This post was created in January 2026.
2. Comparison of CAAP1 (S Sequence) and CAAP2 (QM Decomposition)
Review: in the s sequence approach, the computer searches an r sequence for a conjectured-aperiodic subsequence, called s. A mathematician then proves that the s’ sequence (the infinite extension of the s sequence found by the computer) is aperiodic and is a subsequence of the r’ sequence. In the QM decomposition approach, the computer searches the r sequence for q and m0 sequences such that q µ m0 = r and m1 is aperiodic. A mathematician then proves that q’ µ m0′ = r’ and m1′ is aperiodic.
Some notes:
(1) Similar: for SEQ 806.4, both the s sequence and QM decomposition search algorithms (SSSA1 and QMSA1, respectively) found entities employing constant acceleration. SSSA1 found the conjectured-aperiodic [P V [A A]] s sequences 0:[1 12 [6 3]]:L and 1:[4 15 [3 6]]:L (see s sequence Figure 15.5). QMSA1 found the q sequence {[1 0 0] …} and the m0 sequence [P V A] = [4 9 2] (see QM decomposition Figure 8.4).
(2) Different: the s sequence approach to CAAP does not involve the obligatory decomposition of the r sequence into some combination of entities. Instead, s sequence search looks for a signature of aperiodicity within the r sequence (a conjectured-aperiodic subsequence). In contrast, QM decomposition involves the obligatory decomposition of an entire r sequence into q and m0 sequences such that aperiodicity proof is facilitated.
(3) Similar: both s sequence search and QM decomposition search are only as useful as the specific ‘detectors’ built into the software. For example, SSSA1 can detect PVA and PVAA s sequences; it can’t detect PVAAA s sequences. If SSSA1 is run on an r sequence containing an aperiodic PVAAA s sequence, SSSA1 will fail to find it. Likewise, QMSA1 supports only two detectors – PVA and ax+b. If QMSA1 is run on an r sequence containing an ax^2+bx+c m0 sequence, QMSA1 will fail to find it.
3. Comparison of the SEQ 806.4 S Sequence and QM Decompositions
Although the s sequence approach to CAAP does not require the decomposition of the r sequence into s sequences and a periodic ‘background’ sequence, it is interesting to compare the s sequence and QM decompositions of SEQ 806.4.
Some notes:
(1) Different: both the s sequence and QM decomposition approaches rely upon the [1 0 0] repeating block in similar but not identical ways. In the s sequence based decomposition of the SEQ 806.4 r sequence, the repeating block [1 0 0] was used to fill in any elements of the r sequence not occupied by a component of one of the three PVAA s sequences found (see s sequence Figure 15.4). In the QM decomposition of the SEQ 806.4 r sequence, the periodic q sequence that results in an m0 sequence with an obviously aperiodic m1 sequence is constructed from the [1 0 0] repeating block (see QM decomposition Figure 9).
(2) Different: One of the three s sequences used to decompose the SEQ 806.4 r sequence didn’t pass SSSA1’s “can conjecture aperiodic” test (CCA). Instead, it was labelled “cannot conjecture aperiodic (XCA). SSSA1 found that block length 9 is consistent with the s sequence (i.e., there exists at least one block of length 9 that can pass through the “filter” represented by the s sequence – see s sequence Figure 15.5). SSSA1 concluded that this s (sub)sequence cannot be used to prove that the SEQ 806.4 r supersequence is aperiodic. In contrast, for the QM decomposition the m0 sequence doesn’t distinguish between elements within CCA or XCA s sequences. Instead, elements from both types of s sequence are used to construct the m0 sequence. So, QMSA1 doesn’t view XCA s sequence elements as any less useful than CCA s sequence elements for aperiodicity proof.
4. CAAP1 (S Sequence) or CAAP2 (QM Decomposition): Which is Better?
I currently do not have an aperiodicity proof for a nontrivial r sequence using either CAAP1 (s sequence) or CAAP2 (QM decomposition). So, it may be premature to speculate which of these approaches will eventually be more useful (it’s also possible that future analysts will find neither approach useful). However, I will go out on a limb and suggest that s sequences will prove more useful. Why? An aperiodic s’ subsequence consists of only a tiny amount of the r’ supersequence data – the particular components of the s’ sequence found. In contrast, a QM decomposition of an r’ sequence involves all of the r’ sequence data. A QM decomposition is essentially an alternative algorithm for generating an r’ sequence. QM decomposition may not scale as easily to more complex r sequences because it involves all of the r’ sequence data rather than just a subset.
A caveat: my initial CAAP investigation involving SEQ 806.4 does not appear to support my conjecture that s sequences will ultimately be more useful for aperiodicity proof. SSSA1 found two conjectured-aperiodic PVAA s sequences within the SEQ 806.4 r sequence. QMSA1 found that SEQ 806.4 can be QM decomposed into a q sequence and a PVA m0 sequence. Superficially, the two s sequences found by CAAP1 are more complex than the single m0 sequence found by CAAP2 (PVAA vs. PVA). However, SEQ 806.4 is among the simpler conjectured-aperiodic r sequences available for study, so I’m reluctant to draw any broad conclusions from this initial investigation.
5. A Rosetta Stone for CAAP?
For 806.4, it would be interesting to have three different aperiodicity proofs available for comparison, constructed using:
(1) off-the-shelf mathematical tools;
(2) CAAP1 – s sequence;
(3) CAAP2 – QM decomposition.
Since I’m not a mathematician I’ll leave this challenging task in more capable hands.
Stephen P. Hershey 