14. A recursive property of linear dashed lines with two by two coprime components

Prerequirements:

In this post we’ll talk about a recursive property, that is true for all linear dashed lines with two by two coprime components. Given a dashed line $T$ of that kind, we’ll see that every its proper dashed subline $T^{\prime}$ can be found “immersed” into $T$; moreover, recursively, also every proper dashed subline $T^{\prime \prime}$ of $T^{\prime}$ can be found “immersed” into $T^{\prime}$, and so on.

In the simplest case, i.e. in a second order dashed line $(n_1, n_2)$ with $n_1$ and $n_2$ coprime, the property is that, if you look at the row of $n_1$ in correspondence with dashes of component $n_2$ along a whole period, you can see exactly the same outline as the first order dashed line $(n_1)$, that is given by $n_1 - 1$ spaces followed by one dash. In addition, the property is symmetrical, because a similar thing happens if you look at the row of $n_2$ in correspondence with dashes of component $n_1$.

Let’s set $n_1 := 4$ and $n_2 := 5$. Let’s highlight the cells in the row of 4 that correspond to dashes in the row of 5:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

In the highlighted cells you can note the alternation of three spaces with one dash, that is exactly the same outline of the dashed line $(n_1) = (4)$.
Conversely, if you look at the cells of the row of 5 corresponding to dashes of the row of 4, you can see the alternation of four spaces with one dash, just like the dashed line $(n_2) = (5)$:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

We remark that the hypothesis that the components are coprime is essential. For example, if in the dashed line $(n_1, n_2) = (4, 6)$ we highlight the cells of the row of 4 corresponding to the dashes of the row of 6, we’ll obtain the following table:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

The alternation we can read in the highlighted cells is space-dash-space-dash, that does not correspond to the table of the dashed line $(n_1) = (4)$.
By the way, it’s not by chance that the observed alternation space-dash-space-dash is the one we’d observe along two periods of the dashed line $(2)$, where $2 = \mathrm{GCD}(4, 6)$. This remark can bring us to the formulation of a generalized version of the property we are studying, but for our purposes at the moment we’re interested only to the case when components are two by two coprime.

This property is true also for higher order dashed lines. For example, in a third order dashed line $(n_1, n_2, n_3)$ with $n_1, n_2, n_3$ two by two coprime:

• in the rows of $n_1$ and $n_2$, in correspondence with the dashes of component $n_3$, along the whole period that extends from 1 to $n_1 n_2 n_3$, you can see exactly the same outline as the second order dashed line $(n_1, n_2)$;
• in the rows of $n_1$ and $n_3$, in correspondence with the dashes of component $n_2$ and along the same period, you can see exactly the same outline as the second order dashed line $(n_1, n_3)$;
• in the rows of $n_2$ and $n_3$, in correspondence with the dashes of component $n_1$ and along the same period, you can see exactly the same outline as the second order dashed line $(n_2, n_3)$.

Let’s consider the dashed line $(n_1, n_2, n_3) := (2, 3, 5)$. Let’s look at the cells of the rows of 2 and 3, in the columns corresponding to the dashes of the row of 5:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

You can note that, joining the highlighted cells, you can obtain exactly the outline of a period of the dashed line $(2, 3)$:

0 1 2 3 4 5 6

In third order dashed line there is also another way to observe this property. If, instead of starting from the dashes of a single component, we consider the columns that contain the dashes of two components simultaneously, and if we look at the row of the remaining component, we can read the same outline of the corresponding dashed line.

Let’s consider again the dashed line $(n_1, n_2, n_3) := (2, 3, 5)$ and let’s choose the couple of components 2 and 3. We’ll consider the columns that contain the dashes of these two components simultaneously and we’ll highlight on such columns the cell of the row of the remaining component, that is 5:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

This time, joining the highlighted cells, we’ll obtain one period of the dashed line $(5)$:

0 1 2 3 4 5

Generally, for a linear dashed line $T$ of order $k \gt 1$, the property we can observe is the following: choosing a subset of the components of $T$ that contains between one and $k - 1$ components, taking within a period of $T$ the columns that contain simultaneously one dash for each chosen component, highlighting within such columns the cells associated to the discarded components, and finally joining all the highlighted cells column by column, we’ll obtain the outline of the dashed line having as components the discarded ones.
Let’s try to express this property in more formal terms, step by step:

Recursivity of the dashed sublines of a linear dashed line with two by two coprime components

Let $T = (n_1, \ldots, n_k)$, with $k \gt 1$, a linear dashed line with two by two coprime components. Let’s consider the following algorithm:

1. Choose $h$ components, with $1 \leq h \leq k - 1$. Let $i_1, \ldots, i_h$ be the indexes of that components, with $\{i_1, \ldots, i_h\} \subset \{1, \ldots, k\}$. Let $j_1, \ldots, j_{k - h}$ be the indexes of the discarded components, i.e. $\{j_1, \ldots, j_{k - h}\} = \{1, \ldots, k\} \setminus \{i_1, \ldots, i_h\}$.
2. Within the period that extends from column 1 to column $M := n_1 \cdot \ldots \cdot n_k$, locate the columns that contain simultaneously one dash for each chosen component (the numbers of such columns are all and only the multiples of the components product within the period, that are $M^{\prime} := n_{i_1} \cdot \ldots \cdot n_{i_h}, 2M^{\prime}, 3M^{\prime}, \ldots, M$).
3. Within the columns so located, highlight the cells that belong to the rows with indexes $j_1, \ldots, j_{k - h}$ (the ones of the discarded components).
4. Join column by column all the highlighted cells, thus obtaining a new table.

The table obtained by means of this algorithm is the one that represents the period of the dashed line $(n_{j_1}, \ldots, n_{j_{k-h}})$ having as first column 1 and as last column $n_{j_1} \cdot \ldots \cdot n_{j_{k-h}}$.

First of all, let’s count how many columns are considered in step 2. Their number is equal to the number of multiples of $M^{\prime} := n_{i_1} \cdot \ldots \cdot n_{i_h}$ between 1 and $M := n_1 \cdot \ldots \cdot n_k$. This numbers is in turn equal to $\left \lfloor \frac{M}{M^{\prime}} \right \rfloor$ (we talked about this formula in the post about first order linear dashed lines). Making the calculations, we’ll have that:

$$\left \lfloor \frac{M}{M^{\prime}} \right \rfloor = \left \lfloor \frac{n_1 \cdot \ldots \cdot n_k}{n_{i_1} \cdot \ldots \cdot n_{i_h}} \right \rfloor = \left \lfloor \frac{n_{i_1} \cdot \ldots \cdot n_{i_h} \cdot n_{j_1} \cdot \ldots \cdot n_{j_{k - h}}}{n_{i_1} \cdot \ldots \cdot n_{i_h}} \right \rfloor = \left \lfloor n_{j_1} \cdot \ldots \cdot n_{j_{k - h}} \right \rfloor = n_{j_1} \cdot \ldots \cdot n_{j_{k - h}}$$

But this is just the number of columns of the table that represents any period of the dashed line $(n_{j_1}, \ldots, n_{j_{k-h}})$, considering that its components are two by two coprime, and so $\mathrm{LCM}(n_{j_1}, \ldots, n_{j_{k-h}}) = n_{j_1} \cdot \ldots \cdot n_{j_{k-h}}$. Then, at least concerning the number of columns, the thesis turns out to be true: the number of highlighted columns, which is equal to the number of columns of the table obtained in the final step of the algorithm, is equal to the one of the table that represents the period of the dashed line $(n_{j_1}, \ldots, n_{j_{k-h}})$ extending from column 1 to column $n_{j_1} \cdot \ldots \cdot n_{j_{k-h}}$. From now on, we’ll call the latter table $T_D$ (from “Table of Dashed line”), while we’ll call the table obtained by the algorithm $T_A$ (“Table obtained by the Algorithm”). So it remains to be proved that tables $T_D$ and $T_A$ are just identical, i.e. they coincide cell by cell.
For proving that, let’s consider a generic row number $r$ and a generic column number $c$ and let’s see if the corresponding cells of the two tables coincide. Of course, by contruction, there are some bounds for $r$ and $c$, in particular $r \in \{j_1, \ldots, j_{k-h}\}$ and $c \in \{1, \ldots, n_{j_1} \cdot \ldots \cdot n_{j_{k - h}}\}$. We can note that these are all and only the allowed values for $r$ and $c$ in both tables, because they have the same number of rows and the same number of columns, and they both start from column 1. So if we prove that, for any $r$ and $c$, the cell $(r, c)$ of $T_D$ coincides with the cell $(r, c)$ of $T_A$, then it means that the two tables are identical.

So let’s see what the cell $(r, c)$ of $T_D$ contains. Since this table represents a linear dashed line, by construction the cell $(r, c)$ contains one dash if and only if $c$ is a multiple of $n_r$:

$$\text{the cell (r, c) of T_D contains one dash} \Leftrightarrow n_r \mid c \tag{1}$$

Let’s see now what the cell $(r, c)$ of $T_A$ contains. By the algorithm definition, it corresponds to the cell $(r, cM^{\prime})$ of the dashed line $(n_1, \ldots, n_k)$. In fact, the operation from which the final table arises, in step 4, does not change row numbers, but joins the columns that originally, in the table of the dashed line $(n_1, \ldots, n_k)$, corresponded to the multiples of $M^{\prime}$. Thus, column $M^{\prime}$ becomes column 1 of $T_A$, column $2M^{\prime}$ becomes column 2 of $T_A$, …, generally column $cM^{\prime}$ becomes column $c$ of $T_A$. So we can say that, by the algorithm definition:

\begin{aligned} \text{the cell (r, c) of T_A contains one dash} & \Leftrightarrow \\ \text{cell (r, cM^{\prime}) of the table of the dashed line (n_1, \ldots, n_k) contains one dash} \end{aligned} \tag{2}

But in turn, by the construction of the table of the dashed line $(n_1, \ldots, n_k)$, the cell $(r, cM^{\prime})$ of this table contains one dash if and only if $cM^{\prime}$ is a multiple of $n_r$:

\begin{aligned} \text{the cell (r, cM^{\prime}) of the table of the dashed line (n_1, \ldots, n_k) contains one dash} & \Leftrightarrow \\ n_r \mid cM^{\prime} \end{aligned} \tag{3}

Now we can note that, being $M^{\prime}$ the product of the components $n_{i_1}, \ldots, n_{i_h}$, among which there isn’t $n_r$ because $r \in \{j_1, \ldots, j_{k-h}\}$, and being $n_1, \ldots, n_k$ two by two coprime, $n_r$ is coprime with $M^{\prime}$. Then, if $n_r \mid cM^{\prime}$, since $n_r$ has no common prime factors with $M^{\prime}$, it necessarily divides $c$. Conversely, if $n_r \mid c$, it’s all the more true that $n_r \mid cM^{\prime}$. So we have proved that:

$$n_r \mid cM^{\prime} \Leftrightarrow n_r \mid c \tag{4}$$

Joining formulas (1), (2), (3) and (4) we’ll finally obtain:

\begin{aligned} \text{the cell (r, c) of T_D contains one dash} & \Leftrightarrow \text{[by (1)]} \\ n_r \mid c & \Leftrightarrow \text{[by (4)]} \\ n_r \mid cM^{\prime} & \Leftrightarrow \text{[by (3)]} \\ \text{the cell (r, cM^{\prime}) of the table of the dashed line (n_1, \ldots, n_k) contains one dash} & \Leftrightarrow \text{[by (2)]} \\ \text{the cell (r, c) of T_A contains one dash} \end{aligned}

So we have proved that the cell $(r, c)$ of $T_D$ contains one dash if and only if the cell $(r, c)$ of $T_A$ contains one dash. By arbitrariness of $r \in \{j_1, \ldots, j_{k-h}\}$ and $c \in \{1, \ldots, n_{j_1} \cdot \ldots \cdot n_{j_{k - h}}\}$, this concludes the proof.

Let’s come back to the previous example in the light of Property T.7:

• We chose $h = 2$ components, with indexes $(i_1, \ldots, i_h) = (i_1, i_2) = (1, 2)$. The indexes of the discarded components make up the set $\{j_1, \ldots, j_{k - h}\} = \{1, \ldots, k\} \setminus \{i_1, \ldots, i_h\} = \{1, 2, 3\} \setminus \{1, 2\} = \{3\}$. So $\{j_1, \ldots, j_{k - h}\} = \{j_1\} = \{3\}$.
• The last column of the considered period is $M := n_1 \cdot \ldots \cdot n_k = 2 \cdot 3 \cdot 5 = 30$. The product of the chosen components is $M^{\prime} := n_{i_1} \cdot \ldots \cdot n_{i_h} = n_1 \cdot n_2 = 2 \cdot 3 = 6$. Thus the numbers of the columns that contain simultaneously one dash for each chosen component are $M^{\prime}, 2M^{\prime}, 3M^{\prime}, \ldots, M = 6, 12, 18, 24, 30$.
• Within the columns located this way, we highlighted the cells of the third row, because $j_1 = 3$ is the index of the only discarded component.
• The obtained table is the one that represents one period of the dashed line $(n_{j_1}) = (n_3)$.