Upper bound for maximum distance between consecutive spaces

Prerequisite:

General aspects

One of the still open problems of dashed line theory is, given a linear dashed line T = (p_1, p_2, \ldots p_k) of order k, finding an expression that is able to represent an upper bound for the maximum distance between a space and the one immediately preceding it. That is, given two columns s_1 and s_2 of a dashed line, both spaces, such that s_1 \lt s_2, without other spaces between them, the purpose of this investigation is finding h such that s_2 - s_1 \leq h, for each possible pair of consecutive spaces (s_1, s_2) of the dashed line considered.

Surely h exists, since, to calculate it, it is sufficient to take all possible pairs of neighboring spaces of a given dashed line, calculate the distance for each of them, and take the maximum one. The Visualizzatore di tratteggi, among the other information provided, shows also the maximum distance between consecutive spaces, so it can be used as a basis for possible investigation in this sense.

Let’s consider the dashed line T = (2, 3), limiting its representation to columns until 12. This simplification is enough for our purposes, because the dashed line is periodic: since the sequence of the spaces repeats itself, even the distances between them remain the same for the rest of the dashed line. The table describing the dashed line is the following:

0 1 2 3 4 5 6 7 8 9 10 11 12
2
3

The pairs of consecutive spaces are the following:

  • Columns 1 and 5, whose distance is 5 – 1 = 4;
  • Columns 5 and 7, whose distance is 7 – 5 = 2;
  • Columns 7 and 11, whose distance is 11 – 7 = 4.

The third pair, in reality, is nothing more than the repetition of the first, but it was important to go beyond the period of the dashed line, because, in correspondence with the column equal to the period (i.e. column 6), there is in turn a pair of spaces.

So, given all possible pairs (s_1, s_2) ,we have s_2 - s_1 \leq 4.

So, it is certainly true that the upper bound can be found through an algorithm (i.e. a procedure made of a series of steps), but the purpose of this investigation is to look for a formula.

Upper bound for the maximum distance for first order dashed lines

The dashed lines of which it is easier to find a universally valid upper bound are thw first order ones, because their structure is extremely regular: a first order dashed line T_1(p_1), in fact, always consists of the repetition of a sequence formed by a dash followed by p_1 - 1 spaces.

For example, this is the dashed line T = (5) up to 25:

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
5

So, the possible pairs of consecutive spaces, not only for this example dashed line but for any first order one, are only two:

  • A space immediately followed by another space (such as columns 2 and 3 in the example); the distance between these spaces is 1;
  • A space immediately followed by a dash, immediately followed by another space (such as columns from 4 to 5 in the example); the distance between these spaces is 2.

For a first order hatch, then, this Property applies:

Upper bound for the maximum distance between consecutive spaces for first order dashed lines

In a first order dashed line, the maximum distance between consecutive spaces is 2.

Upper bound for maximum distance for second order dashed lines

The previous reasoning is also applicable to second order dashed lines, but it must be considered that their structure is slightly more complex than the first order ones. The starting point are some properties, which apply precisely to second order dashed lines and are a direct consequence of their own structure:

  1. Each column of the dashed line may not contain dashes (i.e. be a space), or contain one in both rows, or one in the first row, or one in the second;
  2. The minimum distance between two dashes of the first row is 2, equal to the smallest value of the first component;
  3. The minimum distance between two dashes of the second row is 3, equal to the smallest value of the second component;
  4. A dash, in the row in which it is located, cannot be immediately preceded or followed by another dash: it is a direct consequence of the two previous properties;
  5. A column containing a dash in both rows is always immediately preceded and followed by at least one space: it is a direct consequence of the previous property.

To find the upper bound we are looking for, we must determine what is the maximum number of dashes that can be between two consecutive spaces, that is, given a column s that is a space, we must find the maximum value d such as the columns s + 1, s + 2, \ldots, s + d - 1 are dashes, and s + d it is another space. So let’s analyze the various cases that can occur for these intermediate columns:

  1. The simplest case is that in which s + 1 falls in the first case of property A, i.e. it is a space: in this case we have a space followed immediately by another space, so d = 1.
  2. Or, s + 1 falls in the second case of the property A, i.e. it contains dashes in both lines: in this case, for the property E, it is immediataly preceded and followed by a space, so s + 2 is also a space. So we have a space, a column that is not a space, and then another space, so d = 2.
  3. Or, s + 1 falls into the third case of property A, i.e. it contains a dash in the first row. With regard to the next column, i.e. s + 2, the property D guarantees that it cannot contain a dash in the first row, so only two subcases can occur:
    1. The column s + 2 does not even contain a dash in the second row, so it is a space: therefore we have a space, followed by two columns that are not spaces, followed by another space, so d = 3.
    2. The column s + 2 contains a dash in the second row. With regard to the next column, s + 3, the property D guarantees us that it cannot contain a dash in the second row, then only two subcases can occur in turn:
      1. The column s + 3 does not even contain a dash in the first row, so it is a space: therefore we have a space, followed by two columns that are not spaces, followed by a space, so d = 3.
      2. Or, the column s + 3 contains a dash in the first row. In this case, the column s + 4 is certainly a space: in fact, the property D guarantees that this column cannot contain a dash in the first row; but it cannot contain a dash even in the second, because, if it were so, we would have both s + 2 and s + 4 with a dash in the second row, i.e. two dashes of the second row with distance 2, which would lead to a contradiction with the property C. So, we have a space, followed by three columns which are not spaces, followed by another space, so d = 4.
  4. A, that is, it contains a dash in the second row. The reasoning, in this case, is identical to the previous one, but with the first row instead of the second and vice versa.

So in total, given any second order space s, we have 1 \leq d \leq 4 . Therefore, with regard to the maximum possible distance, the following Property applies:

Upper bound of the maximum distance between consecutive spaces for second order dashed lines

In a second order dashed line, the maximum distance between consecutive spaces is 4.

Upper bound for maximum distance for third order dashed lines

The conformation of third order dashed lines is more complex than that of lower orders, which in fact prevents the same reasoning from being applied in order to find an upper bound: in principle it would be possible to do so, but the cases to be verified would be in excessive number. In order to arrive to a valid upper bound, in this case, it is necessary to use more theoretical tools, through which we get the following result:

Upper bound for maximum distance for third order dashed lines

In a third order dashed line T = (n_1, n_2, n_3) with coprime components, the maximum possible distance between consecutive spaces cannot me more than n_1 \cdot (n_3 + 4).

The starting point of the proof is the Characterization C.3 (Spaces of a third order dashed line), which asserts that, given the dashed line T = (n_1, n_2, n_3) with coprime components, all the spaces x preceding a das of the first row are given by the following relationship:

(n_2 + n_3) \cdot n_1 x \mathrm{\ mod\ } (n_1 n_2 + n_1 n_3 + n_2 n_3) \in P_T(1)

where

P_T(1) = \{n_2 a + n_3 b \mid a \in \{2, \ldots, n_3\}, b \in \{2, \ldots, n_2\}\}

The set P_T(1), which is not present in the original statement but is in its proof, is reintroduced here for clarity.

The quantity n_1 n_2 + n_1 n_3 + n_2 n_3 corresponds with the total number of dashes, so, for clarity, we define a symbol for representing it:

tot := n_1 n_2 + n_1 n_3 + n_2 n_3

Then, we define a set, which we’ll name X, containing all the values of x which satisfy the previous relationship, which we can simplify by using tot:

X := \{x \in \{0, \ldots, tot - 1\} \mid (n_2 + n_3) \cdot n_1 x \mathrm{\ mod\ } tot \in P_T(1) \}

The starting bound on the values of x is due to the fact they are dashes, then, if we indicate the first with 0, the last surely is tot - 1.

The sets X and P_T(1) hve both cardinality (n_2 - 1) \cdot (n_3 - 1), because:

  • P_T(1), by construction, has cardinality equal to the product of those of the sets \{2, \ldots, n_3\} and \{2, \ldots, n_2\}, i.e. (n_3 - 1) \cdot (n_2 - 1);
  • The number of remainders allowed for the division on which the definition of X is based, as it is defined, is equal to the cardinality of P_T(1), then, consequently, it is also the number of allowed values of x.
The assertion stating that the cardinality of X is equal to that of P_T(1) needs a formal demonstration, but it can be easily verified: given for example the dashed line T = (2, 3, 5), we have n_1 = 2, n_2 = 3, n_3 = 5, and tot = 2 \cdot 3 + 3 \cdot 5 + 2 \cdot 5 = 31. The sets P_T(1) e X are:

P_T(1) = \{n_2 a + n_3 b \mid a \in \{2, \ldots, n_3\}, b \in \{2, \ldots, n_2\}\} = \\ \{3 a + 5 b \mid a \in \{2, \ldots, 5\}, b \in \{2, \ldots, 3\}\} = \{16,19,21,22,24,25,27,30\}
X = \{x \in \{0, \ldots, 30\} \mid (3 + 5) \cdot 2 x \mathrm{\ mod\ } 31 \in P_T(1) \} = \{x \in \{0, \ldots, 30\} \mid 16 x \mathrm{\ mod\ } 31 \in P_T(1) \}

Given each x \in \{0, \ldots, 30\}, all the corresponding 16 x \mathrm{\ mod\ } 31 are the following, in which the ones belonging to P_T(1) are underlined:

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

Taking only the underlined items, we just obtain P_T(1).

The definition of X allows to simplify the characterization of spaces for the third order. By indicating with S the set of spaces preceding a dash of the first row, the characterization can be rewritten as follows:

S = \{\mathrm{t\_value}(x) - 1 \mid x \in X\}

Since we are considering only the dashes of the first component, the function \mathrm{t\_value} turns out to be strictly increasing, because, taking only the first row, each dash corresponds to a distinct value of \mathrm{t\_value}, which is a different column. If instead we had considered multiple rows, there could have been the possibility of having more dashes in the same column, and therefore they could have had the same \mathrm{t\_value} in correspondence with two different dashes.
From the definition of P_T(1), we can also observe that it can be seen as the union of multiple sets, given i \in \{2, \ldots n_3\}:

A_i := \{n_2 \cdot i + n_3 \cdot b | b \in \{2, \ldots, n_2\} \}

These sets are surely disjointed by construction, and their union is P_T(1), so, by definition, \{A_2, \ldots A_{n_3}\} is a partition of it, with cardinality n_3 - 2.

Let’s apply the same principle to X, defining, for i \in \{2, \ldots n_3\}, the sets

X_i := \{x \mid (n_2 + n_3) \cdot n_1 x \mathrm{\ mod\ } tot \in A_i \}

Also these sets, whose union is X by construction, are disjointed, then \{X_2, \ldots X_{n_3}\} is in turn a partition of X, and also it has cardinality n_3 - 2 by construction.

Now that we have obtained a partition of X, we can use it to create one of S: always given i \in \{2, \ldots n_3\}, we define

S_i = \{\mathrm{t\_value}(x) - 1 \mid x \in X_i\}

In this way, since also the S_i are disjointed by construction, we have that \{S_2, \ldots S_{n_3} \} is precisely a partition of S, and it also has cardinality n_3 - 2.

Let’s now analyze the sets X_i for i \in \{2, \ldots, n_3\}, defining the following symbols:

y_j := \lfloor (tot \cdot j) / n_2 \rfloor \text{, for }j \in \{0, \ldots , n_2 - 1\}
Y := \{y_0, \ldots , y_{n_2 - 1} \} \text{, the set of all the values of }y_j
Y_q := Y \setminus \{y_q\} \text{, for } q \in \{0, \ldots n_2 - 1\}

The Y_q just defined can be used in turn to divide the X_i: in fact, we observe that

\exists k \in \{0, \ldots , tot - 1\}, \exists q \in \{0, \ldots , n_2 - 1 \} \mid X_i = \{ (k + y) \mathrm{\ mod\ } tot \mid y \in Y_q \} \tag{1}
The previous relationship still needs a formal theoretical proof, but it is easily verifiable; this verification is omitted for brevity, but it is enough to start from a third order dashed line, find tot and determine the X_i.

As the values of y_j have been defined, the distance between y_j and y_{j + 1} is always \lfloor tot / n_2 \rfloor or \lceil tot / n_2 \rceil; this equivalence can be proved through the properties of the “integer part” functions \lfloor x \rfloor and \lceil x \rceil.

By definition of y_j, the distance between y_{j+1} and y_j is:

y_{j + 1} - y_j = \lfloor (tot \cdot (j + 1)) / n_2 \rfloor - \lfloor (tot \cdot j) / n_2 \rfloor = \lfloor (tot \cdot j + tot) / n_2 \rfloor - \lfloor (tot \cdot j) / n_2 \rfloor \tag{2}

Let’s apply, to the first addend of (2), the property 2.21 shown in Teoria dei tratteggi, page 66, which states that \lfloor (a + k) / b \rfloor = \lfloor a / b \rfloor + \lfloor (k + a \mathrm{\ mod\ } b) / b\rfloor, setting a := tot \cdot j, b := n_2 and k := tot:

\lfloor (tot \cdot j + tot) / n_2 \rfloor = \lfloor tot \cdot j / n_2 \rfloor + \lfloor (tot + (tot \cdot j) \mathrm{\ mod\ } n_2) / n_2 \rfloor

Replacing the first addend of (2) with the one obtained in this way, we have:

y_{j + 1} - y_j = \lfloor tot \cdot j / n_2 \rfloor + \lfloor (tot + (tot \cdot j) \mathrm{\ mod\ } n_2) / n_2 \rfloor -\lfloor (tot \cdot j) / n_2 \rfloor = \\ \lfloor (tot + (tot \cdot j) \mathrm{\ mod\ } n_2) / n_2 \rfloor \tag{3}

We apply property 2.21 to the member to the right of (3), setting this time a := tot, b := n_2 and k := (tot \cdot j) \mathrm{\ mod\ } n_2:

\lfloor(tot + (tot \cdot j) \mathrm{\ mod\ } n_2) / n_2 \rfloor = \lfloor tot / n_2 \rfloor + \lfloor ((tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2) / n_2 \rfloor

In this way, (3) becomes

y_{j + 1} - y_j = \lfloor tot / n_2 \rfloor + \lfloor ((tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2) / n_2 \rfloor \tag{4}

The second addend of (4) is a fraction, whose numerator is (tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2, formed in turn by two addends, (tot \cdot j) \mathrm{\ mod\ } n_2 e tot \mathrm{\ mod\ } n_2. These two addends are both remainders of a division by n_2, so they must necessarily be less than n_2. So, adding them, we have:

(tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2 \lt 2 \cdot n_2

If we take up the second addendum of (4) at this point, we can then apply this inequality to it:

\lfloor ((tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2) / n_2 \rfloor \lt \lfloor (2 \cdot n_2) / n_2 \rfloor

Since n_2 can be simplified in the fraction, and since \lfloor 2 \rfloor = 2, this inequality becomes

\lfloor ((tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2) / n_2 \rfloor \lt 2

The left member of this inequality is an integer part, so it is definitely an integer, so it is an integer less than 2, i.e. it can only be 0 or 1:

\lfloor ((tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2) / n_2 \rfloor \in \{0, 1\}

By combining the latter condition with (4), we have:

y_{j + 1} - y_j = \lfloor tot / n_2 \rfloor + \lfloor ((tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2) / n_2 \rfloor \in \{\lfloor tot / n_2 \rfloor + 0, \lfloor tot / n_2 \rfloor + 1\}

i.e.

y_{j + 1} - y_j \in \{\lfloor tot / n_2 \rfloor, \lfloor tot / n_2 \rfloor + 1\} \tag{5}

This allows us to complete the proof, taking advantage of the equality \lfloor x \rfloor + 1 = \lceil x \rceil, which applies when x is not an integer. In our case, in fact

tot / n_2 = (n_1 \cdot n_2 + n_2 \cdot n_3 + n_1 \cdot n_3) / n2 = \\ n_1 \cdot n_2 / n2 + n_2 \cdot n_3 / n_2 + n_1 \cdot n_3 / n_2 = n_1 + n_3 + n_1 \cdot n_3 / n_2

and, since n_1, n_2 and n_3 are coprime, being components of the dashed line, n_1 \cdot n_3 / n_2 cannot be an integer (otherwise the numerator would be divisible by the denominator, which would only be possible if the numerator and denominator had common divisors), so tot/n_2 is not, either. So we have:

\lfloor tot / n_2 \rfloor + 1 = \lceil tot / n_2 \rceil

So (5) can be rewritten like this:

y_{j + 1} - y_j \in \{\lfloor tot / n_2 \rfloor, \lceil tot / n_2 \rceil\}

which completes the proof.

We have therefore shown that the set Y is made of elements spaced almost at regular intervals; now let’s try the same reasoning on the sets X_i, in order to check if their elements have similar regularities.

Let’s start with an example: take the hatch T = (2, 5, 7) and see how the X_i are made. For this hatch we have tot = 2 \cdot 5 + 2 \cdot 7 + 5 \cdot 7 = 59, n_1 = 2, n_2 = 5 and n_3 = 7:

y_j := \lfloor (59\cdot j) / 5 \rfloor \text{, per }j \in \{0, \ldots , 4\}

so, the values of y_j are:

  • y_0 = \lfloor (59 \cdot 0) / 5 \rfloor = 0;
  • y_1 = \lfloor (59 \cdot 1 / 5 \rfloor = 11;
  • y_2 = \lfloor (59 \cdot 2 / 5 \rfloor = 23;
  • y_3 = \lfloor (59 \cdot 3 / 5 \rfloor = 35;
  • y_4 = \lfloor (59 \cdot 4 / 5 \rfloor = 47;

so we have Y = \{0, 11, 23, 35, 47\}. The sets Y_j are:

  • Y_0 = Y \setminus \{y_0\} = \{11, 23, 35, 47\};
  • Y_1 = Y \setminus \{y_1\} = \{0, 23, 35, 47\};
  • Y_2 = Y \setminus \{y_2\} = \{0, 11, 35, 47\};
  • Y_3 = Y \setminus \{y_3\} = \{0, 11, 23, 47\};
  • Y_4 = Y \setminus \{y_4\} = \{0, 11, 23, 35\};

The sets A_i are:

  • A_2 = \{5 \cdot 2 + 7 \cdot b \mid b \in \{2, \ldots, 5\}\} = \{24, 31, 38, 45\};
  • A_3 = \{5 \cdot 3 + 7 \cdot b \mid b \in \{2, \ldots, 5\}\} = \{29, 36, 43, 50\};
  • A_4 = \{5 \cdot 4 + 7 \cdot b \mid b \in \{2, \ldots, 5\}\} = \{34, 41, 48, 55\};
  • A_5 = \{5 \cdot 5 + 7 \cdot b \mid b \in \{2, \ldots, 5\}\} = \{39, 46, 53, 60\};
  • A_6 = \{5 \cdot 6 + 7 \cdot b \mid b \in \{2, \ldots, 5\}\} = \{44, 51, 58, 65\};
  • A_7 = \{5 \cdot 7 + 7 \cdot b \mid b \in \{2, \ldots, 5\}\} = \{49, 56, 63, 70\};

The X_i are (considering that the remainders of the division between m and 59 can only go from 0 to 58):

  • X_2 = \{x \mid (5 + 7) \cdot 2 \cdot x \mathrm{\ mod\ } 59 \in A_2\} = \{1, 24, 36, 48\};
  • X_3 = \{x \mid (5 + 7) \cdot 3 \cdot x \mathrm{\ mod\ } 59 \in A_3\} = \{7, 19, 31, 43\};
  • X_4 = \{x \mid (5 + 7) \cdot 4 \cdot x \mathrm{\ mod\ } 59 \in A_4\} = \{2, 14, 26, 49\};
  • X_5 = \{x \mid (5 + 7) \cdot 5 \cdot x \mathrm{\ mod\ } 59 \in A_5\} = \{9, 32, 44, 56\};
  • X_6 = \{x \mid (5 + 7) \cdot 6 \cdot x \mathrm{\ mod\ } 59 \in A_6\} = \{15, 27, 39, 51\};
  • X_7 = \{x \mid (5 + 7) \cdot 7 \cdot x \mathrm{\ mod\ } 59 \in A_7\} = \{10, 22, 34, 57\}.

Analyzing the X_i, we notice how they have a structure almost similar to that of the y_j, but with a particularity. In the case of the y_j, the distance between y_ {j + 1} and y_j was always equal to \lfloor tot / n_2 \rfloor = \lfloor 59 / 5 \rfloor = 11 or to \lceil tot / n_2 \rceil = \lceil 59 / 5 \rfloor = 12, while the one between an element of X_i and the next is almost always equals to one of these values, except in a pair of elements. For example, the distances between the consecutive elements of X_2 are as follows:

  • 24 - 1 = 23;
  • 36 - 24 = 12 = \lceil tot / n_2 \rceil;
  • 48 - 36 = 12 = \lceil tot / n_2 \rceil.

The distance between the second element and the first does not follow the main rule, since 23 is neither \lfloor tot / n_2 \rfloor nor \lceil tot / n_2 \rceil; however, it can be observed that it is equal to their sum. So if the right element was added to each X_i, the rule would be respected.

To find out what is the missing element in each set, we can take advantage of (1), given that, as it is possible to verify:

  • X_2 = \{(1 + y) \mathrm{\ mod\ } 59 \mid y \in Y_1\};
  • X_3 = \{(43 + y) \mathrm{\ mod\ } 59 \mid y \in Y_1\};
  • X_4 = \{(26 + y) \mathrm{\ mod\ } 59 \mid y \in Y_1\};
  • X_5 = \{(9 + y) \mathrm{\ mod\ } 59 \mid y \in Y_1\};
  • X_6 = \{(4 + y) \mathrm{\ mod\ } 59 \mid y \in Y_0\};
  • X_7 = \{(34 + y) \mathrm{\ mod\ } 59 \mid y \in Y_1\};

If, for each set obtained, we replaced Y_q with \{y_q\}, we would obtain sets containing only one element, which we will call m_i, which are the following:

  • \{m_2\} = \{(1 + y) \mathrm{\ mod\ } 59 \mid y \in \{y_1\}\} = \{(1 + y_1) \mathrm{\ mod\ } 59\} = \{(1 + 11) \mathrm{\ mod\ } 59\} = \{12\};
  • \{m_3\} = \{(43 + y) \mathrm{\ mod\ } 59 \mid y \in \{y_1\}\} = \{(43 + y_1) \mathrm{\ mod\ } 59\} = \{(43 + 11) \mathrm{\ mod\ } 59\} = \{54\};
  • \{m_4\} = \{(26 + y) \mathrm{\ mod\ } 59 \mid y \in \{y_1\}\} = \{(26 + y_1) \mathrm{\ mod\ } 59\} = \{(26 + 11) \mathrm{\ mod\ } 59\} = \{37\};
  • \{m_5\} = \{(9 + y) \mathrm{\ mod\ } 59 \mid y \in \{y_1\}\} = \{(9 + y_1) \mathrm{\ mod\ } 59\} = \{(9 + 11) \mathrm{\ mod\ } 59\} = \{20\};
  • \{m_6\} = \{(4 + y) \mathrm{\ mod\ } 59 \mid y \in \{y_0\}\} = \{(4 + y_0) \mathrm{\ mod\ } 59\} = \{(4 + 0) \mathrm{\ mod\ } 59\} = \{4\};
  • \{m_7\} = \{(34 + y) \mathrm{\ mod\ } 59 \mid y \in \{y_1\}\} = \{(34 + y_1) \mathrm{\ mod\ } 59\} = \{(34 + 11) \mathrm{\ mod\ } 59\} = \{45\}.

As can be easily verified, the sets X_i \cup \{m_i\} are such that the distance between one element and the next is always 11 or 12, therefore the m_i are just the missing elements we were looking for.

To continue, let’s define a new set, which we will indicate with M (“Missing”), which contains all the m_i found in the example. This set, which in the case of the example is M = \{4, 12, 20, 37, 45, 54\}, in turn has a regularity similar to that seen in the X_i: if in fact we calculate the distance between one of its elements and the next, we obtain

  • 12 - 4 = 8;
  • 20 - 12 = 8;
  • 37 - 20 = 17;
  • 45 - 37 = 8;
  • 54 - 45 = 9.

In this case, we see that the distance between one element and the next is 8 or 9, except in one case (between 20 and 37), in which it is equal to their sum. The main rule, in this case, turns out to be that the distance is almost always equal to 8 = \lfloor 59 / 7 \rfloor = \lfloor tot / n_3 \rfloor or to 8 = \lceil 59 / 7 \rceil = \lceil tot / n_3 \rceil; in particular, we can observe that this distance is never less than \lfloor tot / n_3 \rfloor, which is an important aspect for the rest of the proof.

The properties, verified in the previous example, according to which:

x_{j + 1} - x_j \in \{\lfloor tot / n_2 \rfloor, \lceil tot / n_2 \rceil\}, x_q \in X_i \cup \{m_i\} \tag{6}
m_{i + 1} - m_i \in \{\lfloor tot / n_3 \rfloor, \lceil tot / n_3 \rceil\}, m_q \in M \tag{7}
m_{i + 1} - m_i \geq \lfloor tot / n_3 \rfloor, m_q \in M \tag{8}

need formal demonstrations, but are verifiable for any dashed line, following the same steps seen in the example.

Thanks to these intermediate considerations, we can take the main problem, i.e. find an upper bound for the distance between the elements of S (the spaces), and review it using the sets we have defined: the calculation of the maximum distance between the consecutive elements of S can in fact be traced, as S and X, to the calculation of the maximum distance between consecutive elements of X, which in turn has been partitioned as \{X_2, \ldots, X_{n_3}\}.

Let’s start again from (1), which allows us, given two appropriate k and q, to rewrite X_i as

X_i = \{ (k + y) \mathrm{\ mod\ } tot \mid y \in Y_q \}

Let’s also define a new set, which we will call X'_i, formed starting from X_i by adding the element m_i:

X'_i = X_i \cup \{m_i\}

For (7), we can therefore say that the distance between its elements is equal to \lfloor tot / n_3 \rfloor or to latex]\lceil tot / n_3 \rceil[/latex], so the maximum possible one is \lceil tot / n_3 \rceil.

By how X'_i is defined, it is also true that

X'_2 \cup \ X'_3 \cup \ldots \cup X'_{n_3} = X \cup M \tag{9}

At this point, let’s analyze the distance between the consecutive elements of X, considering the fact that the starting hatch has period tot, so also the elements of X have the same period: for this, given two elements x_p and x_q = x_p + tot that belong to it, we have x_p \mathrm{\ mod\ } tot = x_q \mathrm{\ mod\ } tot. For this reason, the analysis can be carried out even only between the elements of X up to tot, and we will speak, rather than consecutive elements, of elements “cyclically consecutive”, given that they follow one another in a cycle, period after period.

Let’s ask ourselves, taken x \in X_2, how much the maximum distance between two cyclically consecutive elements can be worth. The fact of referring to X_2 instead of X is a sufficient simplification, since the reasoning would be identical if we took for example X_3 or any other X_i[/ ​​latex].</p> <p>To continue, let's define a new set [latex]I, which contains all the cyclically consecutive integers with respect to a generic x \in X_2:

I := \{(x + 1) \mathrm{\ mod\ } tot, (x + 2) \mathrm{\ mod\ } tot, \ldots \mid x \in X_2 \}

The cardinality of the set, which can be obtained from the definition of X_2, is certainly \lfloor tot / n_2 \rfloor, so we can rewrite the expression like this:

I = \{(x + 1) \mathrm{\ mod\ } tot, \ldots, x + \lfloor tot / n_2 \rfloor \mathrm{\ mod\ } tot\}

This set is related to our X, in fact the cyclically consecutive elements of the other sets X'_3, \ldots, X'_{n_3}, for (7), have a distance equal to \lfloor tot / n_3 \rfloor or \lceil tot / n_3 \rceil, and these sets, as they are defined, are certainly disjointed. So, I definitely contains an element of each of them, and this element is unique, because:

  • If I did not contain an element of X'_3, then, as this set is defined, there would be an element less than x and another greater than x + \lfloor tot/n_2\rfloor, and these two elements would be at least distant from each other x + \lfloor tot/n_2 \rfloor + 1 - (x-1) = \lfloor tot/n_2 \rfloor + 2 = \lceil tot/n_2 \rceil + 1 \gt \lceil tot/n_2 \rceil, and this is not possible, because it would be greater than the allowed distance;
  • If I contained more than one element of X'_3, these elements would be distant from each other at most x + \lfloor tot/n_2 \rfloor - (x + 1) = \lfloor tot/n_2 \rfloor - 1 \lt \lfloor tot/n_2 \rfloor, and this is not possible, because it would be less than the allowed distance;
  • The same reasoning is applicable to the other X'_i, varying the index.

So, I contains one element for each of the X'_3, \ldots, X'_{n_3}, so it contains at least as many elements as there are these sets, i.e. n_3 - 2:

|I| \geq n_3 - 2 \tag{10}

For (9), since surely X'_3 \cup \ldots \cup X'_{n_3} \subset X \cup M, these n_3 - 2 elements of I also belong to X \cup M, so we have

|I \cap (X \cup M)| \geq n_3 - 2\tag {11}

Then, let's look for a criterion to exclude from I the elements of M : as they are defined, we know that they have a minimum distance of \lfloor tot / n_3 \rfloor, so I, which is formed by \lfloor tot / n_2 \rfloor consecutive integers, can contain at most \lceil \lfloor tot / n_3 \rfloor / \lfloor tot / n_2 \rfloor \rceil elements, since, in general, a set of n consecutive integers can contain at most \lceil n / m \rceil multiples of another integer m.

Through this relationshipship, we can find an upper bound for for the cardinality of the set that contains the elements of I which are also in X:

We begin by applying the distributive property between union and intersection:

I \cap (X \cup M) = (I \cap X) \cup (I \cap M)

Let's pass to the cardinality, keeping in mind that |A \cup B| = |A| + |B| - |A \cap B|:

|I \cap (X \cup M)| = |I \cap X| + |I \cap M| - |(I \cap X) \cap (I \cap M)| = |I \cap X| + |I \cap M| - |I \cap X \cap M|

Since X and M are disjointed, their intersection is empty, so the cardinality of the set on the right (which therefore is empty) is zero:

|I \cap (X \cup M)| = |I \cap X| + |I \cap M|

Let's swap the terms of equality and leave |I \cap X| alone to the left:

|I \cap X| = |I \cap (X \cup M)| - |I \cap M|

Let's combine this relationship with (11):

|I \cap X| \geq n_3 - 2 - |I \cap M|

We've said that I \cap M cannot contain more than \lceil \lfloor tot/n_3 \rfloor / \lfloor tot/n_2 \rfloor \rceil consecutive integers, i.e. that

|I \cap M| \leq \lceil \lfloor tot/n_3 \rfloor / \lfloor tot/n_2 \rfloor \rceil

Let's combine this inequality obtained with a particular property of the components of third order dashed lines, which is the following:

\lceil \lfloor tot/n_3 \rfloor / \lfloor tot/n_2 \rfloor \rceil \leq \lceil n_3 / n_2 \rceil
This relationship needs a demonstration, but it is possible to verify it easily, starting from any third order dashed line and calculating tot.

then:

|I \cap M| \leq \lceil \lfloor tot/n_3 \rfloor / \lfloor tot/n_2 \rfloor \rceil \leq \lceil n_3 / n_2 \rceil

then:

|I \cap M| \leq \lceil n_3 / n_2 \rceil

then, reversing the sign of inequality and replacing in the previous relationship related to |I \cap X|:

|I \cap X| \geq n_3 - 2 - \lceil n_3 / n_2 \rceil

Then, the elements of I which are also in X are at least n_3 - 2 - \lceil n_3 / n_2 \rceil.

Now we can calculate the maximum distance between an element of X and the cyclically consecutive one, which is the last step necessary to be able to pass to the calculation of the maximum distance between consecutive spaces. To do this, we start from the last element of I[/latex, which is [latex]x + \lfloor tot + n_2 \rfloor, and proceed backwards until we get to the first element and overtake it: we will have, in order, x + \lfloor tot + n_2 \rfloor - 1, x + \lfloor tot + n_2 \rfloor - 2, until reaching the cyclically consecutive one, which is

x + \lfloor tot/n_2 \rfloor - (n_3 - 2 - \lceil n_3 /n_2 \rceil - 1) = x + \lfloor tot/n_2 \rfloor - n_3 + 3 + \lceil n_3 /n_2 \rceil

Therefore, the maximum distance between any element x of X and the cyclically consecutive one is the difference between their two values:

D := (x + \lfloor tot/n_2 \rfloor - n_3 + 3 + \lceil n_3 /n_2 \rceil) - x = \lfloor tot/n_2 \rfloor - n_3 + 3 + \lceil n_3 /n_2 \rceil

Since n_2 and n_3 are coprime, n_3 /n_2 is not an integer number, so the relationship \lfloor n_3 /n_2 \rfloor + 1 = \lceil n_3 /n_2 \rceil is true, then:

D = \lfloor tot/n_2 \rfloor - n_3 + 3 + \lceil n_3 /n_2 \rceil = \lfloor tot/n_2 \rfloor - n_3 + 3 + \lfloor n_3 /n_2 \rfloor + 1 = \\ \lfloor tot/n_2 \rfloor - n_3 + 4 + \lfloor n_3 /n_2 \rfloor \tag{12}

Now that we have calculated the maximum possible distance between any two cyclically consecutive elements of X, we can complete the proof, moving on to calculate that between consecutive spaces. Let's go back to the initial definition of the set S of the spaces preceding a dash of the first row of a dashed line:

S = \{\mathrm{t\_value}(x) − 1 \mid x \in X \}

We take any space s \in S, and its consecutive s' \gt s. Then, by how S is defined, there will be x and y belonging to X such that s = \mathrm{t\_value}(x) − 1, and s' = \mathrm{t\_value}(y) − 1. Since, in our case, the function \mathrm{t\_value} is strictly increasing (because we are considering only the dashes of the first row), the distance between s' and s is maximum when the one between y and x is maximum.
But the maximum distance between x and y is equal to D[/latex, so we have [latex]y \leq x + D, therefore we have:

s' - s = \mathrm{t\_value}(y) − 1 - (\mathrm{t\_value}(x) − 1) = \mathrm{t\_value}(y) - \mathrm{t\_value}(x)

Since y \leq x + D, and since \mathrm{t\_value} is strictly increasing in our case, we also have \mathrm{t\_value}(y) \leq \mathrm{t\_value}(x + D), so the previous relationship becomes:

s' - s = \mathrm{t\_value}(y) - \mathrm{t\_value}(x) \leq \mathrm{t\_value}(x + D) - \mathrm{t\_value}(x) \tag{13}

Applying the Hypothesis T.1 (Range of possible values for a downcast function of linear t from the third to the first order), replacing j = 2, k = 3, and n_i n_j + n_i n_k + n_j n_k = tot, we can determine the extreme values of \mathrm{t\_value}(x) for the first row:

\mathrm{t\_value}(x) = n_1 \cdot \Bigg \lceil \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rceil
\mathrm{t\_value}(x) = n_1 \cdot \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rfloor

Let's do the same for \mathrm{t\_value}(x + D); the related formulas are identical to the previous ones, but with x + Dinstead of x. Considering all possible combinations, the distance obtained in (13) is maximum when the value of \mathrm{t\_value}(x + D) is the highest possible, and when that of \mathrm{t\_value}(x) is as low as possible, i.e. we have to take

\mathrm{t\_value}(x + D) = n_1 \cdot \Bigg \lceil \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rceil
\mathrm{t\_value}(x) = n_1 \cdot \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rfloor

take the maximum one, and perform the intermediate calculations.

Let's start from

\mathrm{t\_value}(x + D) - \mathrm{t\_value}(x) = \\ n_1 \cdot \Bigg \lceil \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rceil - n_1 \cdot \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rfloor \tag{14}

The left fraction cannot be an integer, since n_2, n_3 and tot are coprime, so we can replace \lceil \ldots \rceil with \lfloor \ldots \rfloor + 1, so the previous relationship becomes

n_1 (\cdot \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rfloor + 1) - n_1 \cdot \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rfloor =
n_1 \cdot \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rfloor + n_1 - n_1 \cdot \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rfloor =
n_1 \cdot \Bigg ( \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rfloor - \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rfloor \Bigg ) + n_1 \tag{15}

The expression in brackets, which is the difference between two integer parts, can be given an upper bound by applying some properties of the integer part. Let's start from the first term of the difference:

\Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rfloor = \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3 \cdot D + n_2 + n_3}{tot} \Bigg \rfloor = \\ \Bigg \lfloor \frac{(n_2 \cdot n_3 \cdot x + n_2 + n_3) + (n_2 \cdot n_3 \cdot D)}{tot} \Bigg \rfloor

Let's apply property 2.21 shown in Teoria dei tratteggi, page 66, which states that \lfloor (a + k) / b \rfloor = \lfloor a / b \rfloor + \lfloor (k + a \mathrm{\ mod\ } b) / b\rfloor, setting a := n_2 \cdot n_3 \cdot D, k := n_2 \cdot n_3 \cdot x + n_2 + n_3 and b := tot:

\Bigg \lfloor \frac{(n_2 \cdot n_3 \cdot x + n_2 + n_3) + (n_2 \cdot n_3 \cdot D)}{tot} \Bigg \rfloor = \\ \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3 + (n_2 \cdot n_3 \cdot D) \mathrm{\ mod\ } tot}{tot} \Bigg \rfloor

Surely \forall q : q \mathrm{\ mod\ } tot \leq tot, then:

\Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3 + (n_2 \cdot n_3 \cdot D) \mathrm{\ mod\ } tot}{tot} \Bigg \rfloor \leq \\ \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3 + tot}{tot} \Bigg \rfloor = \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3}{tot} + 1 \Bigg \rfloor

If k is a relative number, we have \lfloor a + k \rfloor = \lfloor a \rfloor + k, then:

\Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3}{tot} + 1 \Bigg \rfloor = \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3}{tot} \Bigg \rfloor + 1

In total, the following relationship is obtained from this sequence of calculations, which takes up the first term of the subtraction present in (15):

\Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rfloor \leq \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3}{tot} \Bigg \rfloor + 1

then

\Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rfloor - \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3}{tot} \Bigg \rfloor \leq \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + 1

Using this inequality, we can have an upper bound for (15) like this:

n_1 \cdot \Bigg ( \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rfloor - \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rfloor \Bigg ) + n_1 \leq \\ n_1 \cdot \Bigg ( \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + 1 \Bigg ) + n_1

Ler's use (12) in order to replace D with its value:

n_1 \cdot \Bigg ( \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (\lfloor tot/n_2 \rfloor - n_3 + 4 + \lfloor n_3 /n_2 \rfloor)}{tot} \Bigg \rfloor + 1\Bigg ) + n_1

Since \lfloor q \rfloor \leq q, this expression can be given an upper bound like this:

n_1 \cdot \Bigg ( \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (tot/n_2 - n_3 + 4 + n_3 /n_2)}{tot} \Bigg \rfloor + 1\Bigg ) + n_1 =
n_1 \cdot \Bigg \lfloor \frac{n_3 tot - n_2 (n_3)^2 + 4 n_2 n_3 + (n_3)^2)}{tot} \Bigg \rfloor + 2n_1 \tag{16}

Let's analyze the term -n_2 (n_3)^2 + 4 n_2 n_3 + (n_3)^2: we have

-n_2 (n_3)^2 + 4 n_2 n_3 + (n_3)^2 = (n_3)^2 \cdot (n_2 - 1) + 4 n_2 n_3 \leq

(since n_2 \geq 3 by hypothesis, then -(n_2 - 1) \leq 2)

-2 (n_3)^2 + 4 n_2 n_3 \lt

(since n_2 \geq 3 by hypothesis)

-2 n_2 n_3 + 4 n_2 n_3 = 2 n_2 n_3 \lt

(since surely p + q \gt p if q \gt 0)

2 (n_2 n_3 + n_1 n_2 + n_1 n_3) =

(by definition of tot)

2 \cdot tot

In total:

-n_2 (n_3)^2 + 4 n_2 n_3 + (n_3)^2 \leq 2 \cdot tot

Let's use this relation to give an upper bound, in turn, to (16):

n_1 \cdot \Bigg \lfloor \frac{n_3 tot - n_2 (n_3)^2 + 4 n_2 n_3 + (n_3)^2)}{tot} \Bigg \rfloor + 2n_1 \leq n_1 \cdot \Bigg \lfloor \frac{n_3 tot + 2 \cdot tot}{tot} \Bigg \rfloor + 2n_1

Combining it with (14) from which we started, we have:

\mathrm{t\_value}(x + D) - \mathrm{t\_value}(x) \leq n_1 \cdot \Bigg \lfloor \frac{n_3 \cdot tot + 2 \cdot tot}{tot} \Bigg \rfloor + 2n_1 = \\ n_1 \cdot \Bigg \lfloor \frac{(n_3 + 2) \cdot tot}{tot} \Bigg \rfloor + 2n_1 = \\ n_1 \cdot \lfloor n_3 + 2 \rfloor + 2n_1 = (\text{since }\lfloor q \rfloor = q)\\ n_1 \cdot (n_3 + 2) + 2n_1 = \\ n_1 \cdot n_3 + 2n_1 + 2n_1 = \\ n_1 \cdot n_3 + 4n_1 = \\ n_1 (n_3 + 4)

Then, the final result is the following:

s' - s \leq n_1 \cdot (n_3 + 4)

That is, the maximum distance between any space s and the consecutive s' is n_1 \cdot (n_3 + 4), which was the initial thesis to be proved.

Upper bound for maximum distance for dashed lines of any order

The final purpose of this study is to find an upper bound that applies to any dashed line, so the next step is to analyze those from the fourth order upwards, in order to cover the missing part of the analysis. One possible investigation is the fact that the upper bound found for the third order, i.e. n_1 \cdot (n_3 + 4), can be seen as n_1 \cdot (n_k + 4) with k = 3. Seen in this way, taking k \in \{1, 2\}, the formula is also valid for first and second order, considering that:

  • In a first order dashed line we have n_k = n_1, so the upper bound would be n_1 \cdot (n_1 + 4). Since n_1 \geq 2, it means that the minimum value of the upper bound is 2 \cdot (2 + 4) = 12. We know that the maximum possible distance for the first order dashed line is 2, and certainly 2 \leq 12, therefore the upper bound given by the formula is acceptable.
  • In a second order dashed line we have n_k = n_2, so the upper bound would be n_1 \ cdot (n_2 + 4) [/ latex]. Since [latex]n_1 \geq 2 and n_2 \geq 3, it means that the minimum value of the upper bound is 2 \cdot (3 + 4) = 14. We know that the maximum possible distance for the dashed lines of the second order is 4, and certainly 4 \leq 12, so the upper bound given by the formula is acceptable also in this case.
If one wants to look for an upper bound for the distance between consecutive spaces in a generic linear dashed line, following the approach of the proof for the third order, he or she had first to fine a general formula for \mathrm{t\_value}. This is an open point of dashed line theory, but it is possible that the formula for the third order may also apply to higher orders, by expanding it with further terms, presumably dependent on the components from the fourth onwards. A possible way to generalize the formula, currently being studied, is explained in a specific page.

Leave a Reply

Your email address will not be published.