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

Leave a Reply

Your email address will not be published. Required fields are marked *