\( \newcommand{\len}{ {\rm len}} \renewcommand{\value}{ {\rm value}} \newcommand{\ifu}{ {\rm if}} \newcommand{\gtone}{ {\rm gt1}} \newcommand{\parent}{ {\rm parent}} \newcommand{\diff}{ {\rm diff}} \newcommand{\ancestor}{ {\rm ancestor}} \newcommand{\bm}[1]{ {\boldsymbol #1}} \newcommand{\w}{\omega} \newcommand{\e}{\varepsilon} \newcommand{\nat}{\mathbb{N}} \newcommand{\p}{\psi} \) Y sequence is a notation made by Yukito. In this page, we give introduction of Y sequence[1] without assuming knowledge of Bashicu matrix system for readers' convenience, although there are several intersections in the studies of Y sequence and Bashicu matrix system. See the code if you want to know its definition.[2] See the page to try expansion.[3]

Notation

Expressions in Y sequence consists of finite sequences of positive integers \((a_0,a_1,a_2,\cdots,a_k)\). For example, (1), (1,1,1), (1,2,2), (1,2,3), (1,2,4), (1,2,3,4,1,2,3,3,3), (1,2,4), (1,2,4,5,4), (1,2,4,8,9,8), (1,2,4,8,16), (1,3), (1,4,4) and (1,1024) are all valid expressions in Y sequence.

Expansion up to \(\w\)

The fundamental operation in Y sequence is expansion, which transforms a given sequence into another. Whenever a sequence is expanded, there are infinitely many possible results - specific results are selected by appropriate choice of an argument n, usually enclosed in brackets. For instance, the expression (1,2,3) can expand to (1,2), (1,2,2), (1,2,2,2), (1,2,2,2,2), etc., and in particular (1,2,3)[2] = (1,2,2,2). When Y sequence is used as a fast-growing function, we keep the [n] and replace it with [n+1] at each expansion step, i.e. (1,2,3)[2] = (1,2,2,2)[3].

The rest of this page will describe how expressions in Y sequence are expanded.

The simplest case consists of expressions ending in 1: whenever this occurs, the last 1 is simply removed, regardless of the value of n. (1,1,1,1)[2]=(1,1,1), (1,1,1,1,1,1)[100]=(1,1,1,1,1), and (1)[300]=(). In this way, we can expand all (standard) sequences less than (1,2) (which corresponds to \(\w\)).

Searching Parent

Let's expand (1,2,3,4,1,2,3,3,3)[2].

To expand sequences ending in numbers greater than 1, we must first find the parent of all the numbers in the sequence. To find the parent of a given number, start at its position and read from right to left. The first number you encounter that is smaller than the number you started at is its parent. [NOTE: Since Y sequence expressions never contain 0, 1's will never have a parent.]

As an example, let's find the parent of the 3 circled in red below:

Koteitan explainy 00.png

In this example, the parent of the 3 is the circled 2.

Drawing Hydra Diagram

To help illustrate the rules later on, it will be helpful to draw hydra diagrams.

For each number in the sequence, we find its parent, and connect the two with a line. For the purpose of readability, it usually helps to place the children (the numbers having it as a parent) of a given number one level higher than the number itself. Since 1's have no parent, we connect them to a "root" (think of it like an imaginary "0" element). For the sequence we looked at in the previous section, the corresponding hydra diagram looks like this:

Koteitan explainy 01.png

Expansion up to \(\e_0\)

If a sequence ends in a number greater than 1, the last element will have a parent. Check the difference between the two - if it is 1, we can expand the sequence in the following way:

First, delete the last number - we call this element the cut child.

Then, find the parent of the cut child, and highlight it. (We use anger marks for this, since it is a reasonable response to having one's children cut.)
Koteitan explainy 02.png
The marked parent is called the bad root. Every element in the sequence from the bad root rightward is called the bad part, and everything else is called the good part.
Koteitan explainy 03.png
Read off the argument [n], and copy the bad part that many times.
Koteitan explainy 04.png

The expansion method so far is essentially the same as Primitive Sequence System. When the difference from the parent is 2 or higher, there is another rule, which will be explained in the next section.

Expansion up to \(\e_{\w+1}\)

For expansions where the difference between the cut child and its parent is greater than 1, there are some additional steps that need to be followed. For example, let's consider the expansion of (1,2,4)[2].

Expansion of (1,2,4)[2]

Koteitan explainy 05.png
In the sequence, The cut child is 4, and its parent is 2, so, the difference between the parent and the child is 2, which is greater than 1. In order to expand this we need to create a differential sequence. Differential sequences are quite similar to difference sequences in regular mathematics, except in this case difference are taken between each number and its parent. Differential sequences can be described by hydra diagrams in much the same way as the original sequence: each of the differences is connected to the corresponding branch of the hydra, and then lines connecting parents and children are drawn. [More on this later.] Call (1,2,4) the "first level" and its differential sequence the "second level".

Since the second level has a difference of 1, we can expand it using the same rules as before:
Koteitan explainy 06.png

As you can see, the bad root from the second level propagates upward: a given number and all differences between it and its parents behave as a single unit - when one is modified, copied, or deleted, the rest change accordingly.

After the second level is expanded, the first level must be reconstructed. In the first level, the bad root is the 2 and the bad part is determined as before: clearly, it only contains the 2.

Copying the 1st level sequence requires a slightly more special method than the 2nd level. First, we need to analyze the "branch connection" of the bad part of the first Y sequence (1,2,4).

Koteitan explainy 07.png
Notice the height of the location of the bad root's parent (IN) and the location of the cut child (OUT). The IN is one level below the bad root, and the OUT is one level above the bad root. When copying, we copy the structure of the bad part, connecting the INs of each part to the OUTs of the previous. Initally, the numbers themselves haven't been calculated yet, so we use circles as placeholders:

Koteitan explainy 08.png
After the structure is calculated, connect the second level to the corresponding branches of the first level, and use the differences to fill in the blanks using simple addition.

Koteitan explainy 09.png
Finally, we obtain (1,2,4)[2]=(1,2,3,4).

Expansion of (1,2,4,1,2,4)[2]

Let's expand (1,2,4,1,2,4)[2].
Koteitan explainy 10.png
As explained in the previous section, 1's have no parent: we must add another root node for the second-level 1 to connect to. (Alternatively, you could connect it to the original root - it makes no difference.)

The remainder of the procedure is the same: expand the differential Y sequence (1,2,1,2)[2] to (1,2,x,1,1,1), and then expand the 1st level sequence based on that. The result is (1,2,4,1,2,3,4).

By the way, this is the Y sequence corresponding to \(\e_02\).

Expansion of (1,2,4,4)[2]

Next is the expansion of (1,2,4,4)[2]. This can be expanded with the same rule.
Koteitan explainy 11.png
First, the bad root in the 2nd level is the parent of the rightmost 2, so it becomes 1, yielding a bad part of (1,2), so the second level expands to (1,2,1,2,1,2).

Now consider how the 1st level will be copied.
Koteitan explainy 12.png
The IN is one below the bad root, the cut child is 4, and the parent is 2, so the OUT is one above the bad root. As before, we copy the bad part, connecting INs to OUTs.

Koteitan explainy 13.png
Then, as before, we will use the numbers in the 2nd level as hints to reconstruct the 1st level sequence. Add up the corresponding branches: 2+1=3, 3+2=5, 3+1=4, 4+2=6, and so on, until the circles are filled with 3, 5, 4, and 6. So, (1,2,4,4)[2]=(1,2,4,3,5,4,6).

This rule is sufficient to describe everything below \(\epsilon_{\w+1}\).

Expansion up to \(\p_0(\p_\w(0))\)

One thing to watch out for arises in (1,2,4,5,4). This is the Y sequence equivalent to \(\e_{\w+1}\).

The differential Y sequence is (1,2,1,2), and blindly applying the parenthood rules gives us something like the diagram below:
Koteitan explainy 14.png
However, when finding parents in levels above the first, parents in lower levels must be respected. When you start looking left from the 2, look to the 4 in the level above and skip directly to its parent. Then, you can look back to the second level and see if you've arrived at a smaller number. Otherwise, just back to the first level and repeat until you find a smaller number in the second level.
Koteitan explainy 15.png

This makes the parent of the second 2 the first 1 instead of the second. The rest is the same as before:
Koteitan explainy 16.png
The bad root of the 2nd level is the leftmost 1 and the bad part is (1,2,1). The bad root of the 1st level is 2, and the bad part is (2,4,5). After they are copied by the value of the bracket, the 2nd level should be (1,2,1,1,2,1,1,2,1), the circles of the 1st level should be filled by using the 2nd level numbers, to be (1,2,4,5,3,5,6,4,6,7).

Now, we can expand all Y sequences less than (1,2,4,8) - that is, all expressions with at most two levels.

Expansion up to \(\p_0(\p_\w(1)+\p_\w(0))\)

Next, we will talk about the sequence that gives rise to the 3rd level. Let's expand (1,2,4,8,8)[2].

Koteitan explainy 17.png
In this case, we have a parent-child difference of 4, so we first construct the second-level sequence as before. However, this sequence has a difference of 2, so we must also construct a third-level sequence from the second level. When we find parents in the third level, we now have to respect the second-level parents in addition to the first-level ones: generally speaking, to find a parent in the n'th level, look at its corresponding element in the (n-1)'th level, skip to its parent, then jump back to the n'th level and check if you've encountered something smaller.

In most cases, such as this one, the third-level sequence expands as normal, and reconstructing the lower levels works the same as before: the third level sequence (1,2,2) expands to (1,2,1,2,1,2), which determines the second level to be (1,2,4,3,5,6,4), and then the first level sequence (1,2,4,8,7,12,11,17) follows form that. Allowing third-level sequences can get us to (1,2,4,8,9,8) by the methods above.

Expansion up to \((1,3)\)

(1,2,4,8,9,8) requires some extra consideration, so we'll have to discuss it in this section before proceeding further.

Drawing the hydra diagram for this sequence is fairly straightforward - it should look like the left side of the picture below:
Koteitan explainy 18.jpg
To expand it, however, we need to modify the rules a little. Let's paint the nodes in the bad parts in two colors: numbers that are descended from the bad root (i.e. connected to it through some number of upward branches) will be colored pink and the rest will be colored green.

In the second level, the bad root 2 and its child 4 are colored pink, but the 1 is green because it skips the 2 and connects directly to the root. In the preceding sections, the entire bad part would have been painted pink: the green 1 in the second level is the first.

When we expand this sequence, the pink sections of the bad part are connected IN-to-OUT as before, but the green nodes remain connected to their original parent (the root, in this case): the second level becomes 2,4,1,3,5,1,4,6,1. [NOTE: Even though the last level is colored like the rest, its parent-child difference is still 1: its bad part is simply copied, not chained.]

Let's practice with (1,2,4,8,10,8).
Koteitan explainy 19.jpg
After drawing the hydra diagram, we again color the bad part. In the second level, the bad root and its child are again colored pink, and the second 2 is green as before. The rest of the expansion is the same: pink parts are chained, green parts are copied, and the changed numbers are filled in using the lower levels, giving us (1,2,4,8,10,8)[2] = (1,2,4,8,10,7,12,14,11,17,19).

Modifying the rule this way allows us to reach the limit of Bashicu Matrix System: \(1,2,4,8,16,32,\cdots,2^n\) is equivalent to (0,...,0)(1,...,1) with n rows.

  1. koteitan, "The introduction of Y sequence", Feb. 13, 2021.
  2. Naruyoko, expand() function of YNySequence, Sep. 1, 2020.
  3. Naruyoko, "YNySequence", Sep. 1, 2020.
  4. Community content is available under CC-BY-SA unless otherwise noted.