Introduction to Y sequence

View full site to see MathJax equation

\( \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 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. See the page to try expansion.

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:

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:

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.)

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.

Read off the argument [n], and copy the bad part that many times.

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]

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:

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).

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:

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.

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].

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.

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.

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.

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:

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.

This makes the parent of the second 2 the first 1 instead of the second. The rest is the same as before:

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].

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,4,6), 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:

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).

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,3)\) and Beyond

Let's draw the limit up to this point, \(1,2,4,8,16,32,\cdots,2^n\).

We have a clean triangle shape. But if we look from the original 1 to down right, we find that there is a line of 1's. Can we somehow get this from another (1,2), and possibly extend it further? This is the concept of (1,3) in Y sequence.

However, if we use the rules above to expand sequences with its second number greater than 2, for example (1,3,8,17,12,8), the rules above would not work correctly, since we will eventually be unable to find a parent for the last number before finding a difference of 1. We need to introduce a new rule.

Diagonal

To prepare us for the new rule, we introduce an important concept, the diagonal of a sequence.

To find the diagonal, we first take the differential sequences until none of the numbers has a parent to another number. Note that this is different from before, where we could stop when we had the difference of 1 at the end.

We then extract the numbers connected to roots (X). Using the example, they are (1,2,3,1,2,3). These are the numerical values of the diagonal.

Like differential sequences, we use the information from the previous sequences to build the diagram. We start with the number in the diagonal in the diagram we have built:

• If the number we are on has a parent (in the hydra), go to that parent.
• If it does not have a parent (i.e. connected to an X) but has a dotted line attached above, go up the dotted line and then to the left on the solid line that is connected to.
• If we reach a number that is less than the number we started from and is part of the diagonal (i.e. connected to an X), that is the parent in the diagonal.
• If none of the above are true, meaning we reach a number that is connected to an X, does not have a dotted line above, and never reaches a number in diagonal less than what we started from, then we say that it has no parent in the diagonal.

Notice that we don't connect the second 2 to the second 1, or the second 3 to the second 2, which would be the case if we were to draw (1,2,3,1,2,3) normally. This is similar to when we calculate differential sequences, where the parent is also not necessarily the rightmost number that is to the left and less than the number.

Expansion of 1,3,8,17,12,8[2]

First, we take the diagonal of the last number if we never get the difference of 1 and there are no more parents by taking the differential sequences. We still take differential sequences like before if we can. We continue taking diagonals and differential sequences until we get the difference of 1. The addition of diagonals allows us to find the difference of 1 for sequences larger than (1,3).

Then, when we have found the difference of 1, we mark the bad root like before. Now we let the bad root propagate.

To expand sequences that we don't get the difference of 1 by taking differential sequences, we need the expansion of its diagonal. So, we expand the diagonal (1,2,3,1,2,3). We found the difference of 1 here, so we will expand this by the old rules and end up with (1,2,3,1,2,2,3,1,2,2,3,1,2). Note that we have an unusual structure, making the expansion different from normal (1,2,3,1,2,3). We will use this later.

Now, let's look at the first group of hydras. For this, we need to get all differential sequences until we no longer can take a difference on any number, just like what we did when finding the diagonal.

We draw boxes for the good part and the bad part. We also use three colors for the bad part, using orange for the one drawn on the same hydra with the bad root which does not have a parent, blue for the ones drawn above the orange one, and purple for the ones drawn below the orange one. We also color each vertices green and purple like before. For the blue and orange boxes, we color them just like before. For the purple boxes, we don't have a bad root there, so instead, we color them the same as the corresponding ones in the orange box. In this case, everything is colored purple.

Now we can expand. Like before, we chain the bad part. We can expand the blue and the orange boxes just like before. However, some of the purple boxes have OUT but not IN. In this case. we duplicate the orange box and connect that to OUT. The purple boxes are then placed below the orange boxes just like the original, but they will be in different hydras since there are multiple orange boxes now. This places 1 more orange boxes for each subsequent copy.

We also fill in the numbers slightly differently. We first fill in the spaces which are connected to X, which are underlined. This is also the diagonal for the expansion. Then, we take the expansion of the diagonal, (1,2,3,1,2,2,3,1,2,2,3,1,2), and write each number in order. After that, we fill in the blanks like before, and get (1,3,8,17,12,8)[2] = (1,3,8,17,12,7,16,34,24,15,32,67,48).

Expansion of 1,3,9,23[2]

(1,3,9,23)[2] = (1,3,9,22,50,110,238)

Since there are 2 purple boxes with OUT, there are also 2 more orange boxes for each copy. Also notice that the numbers in the diagonal are increasing, reflective of the expansion result of the diagonal, (1,2,4,4).

Expansion of 1,3,4,2,5,11,6,8,12,5[2]

(1,3,4,2,5,11,6,8,12,5)[2] = (1,3,4,2,5,11,6,8,12,4,9,20,10,12,16,8,17,37,18,20,24)

Now, we have some stuff colored green: 1,2,4, 1,2, and 1. The green numbers which are in the orange and the purple boxes will not be duplicated into the lower hydras, but they will instead stay within the original hydra.

Expansion of 1,4[3]

(1,4)[3] = (1,3,9,27)

To expand (1,4), we first need to expand its diagonal, (1,3). This itself needs the expansion of its diagonal, (1,2). The expansion of (1,2)[3] is (1,1,1,1), and we use it to get (1,3)[3] = (1,2,4,8). Now we can use this to get the result. In general, \((1,m+1)[n]=(1,m,m^2,\cdots,m^n)\).