21. Characterization of spaces: insights

Prerequisites:

• Characterization of spaces

In the article Characterization of spaces we saw, for the first three orders of linear dashed lines, the formulas which calculate all and only the spaces that precede (or, respectively, that follow) a dash of component n_1 (the smallest component of the dashed line). In this article we’ll take a more in-depth look at these formulas, arriving at giving a graphical interpretation. We will analyze mainly the second and third order formulas, because in the first order ones many properties assume a degenerate form that makes them difficult to identify.

Meaning of the second argument of the module

Both in the second-order and third-order characterizations we find relations involving the modulo operator. For example, for the second order, in the Corollary of Proposition L.C.3 the x must satisfy the relation n_1 x \textrm{\ mod\ } (n_1 + n_2) \in P_T(1); as for the third order, in Proposition L.C.5 the x must satisfy the relation (n_2 + n_3) n_1 x \textrm{\ mod\ } (n_1 n_2 + n_1 n_3 + n_2 n_3) \in P_T(1).
Let us now focus on the second argument of the modulo operator, that is n_1 + n_2 in the second order and n_1 n_2 + n_1 n_3 + n_2 n_3 in the third order. From the algebraic point of view we have already observed that these are elementary symmetric polynomials (see the last open point of the article Characterization of spaces), but these formulas also have a meaning related to the dashed line, in the case in which the components are all two by two coprime. In this case the formulas calculate the number of dashes in a period of the dashed line. In fact:

• By Property T.4, the number of dashes in one period of a linear dashed line (n_1, n_2, \ldots, n_k) is \frac{M}{n_1} + \frac{M}{n_2} + \ldots + \frac{M}{n_k}, where M is the least common multiple of the components.
• If the components are two by two coprime, the least common multiple coincides with the product, that is M = n_1 n_2 \ldots n_k, so the number of dashes in a period is \frac{n_1 n_2 \ldots n_k}{n_1} + \frac{n_1 n_2 \ldots n_k}{n_2} + \ldots + \frac{n_1 n_2 \ldots n_k}{n_k}.
• If the dashed line is of second order, the formula becomes \frac{n_1 n_2}{n_1} + \frac{n_1 n_2}{n_2} = n_2 + n_1 = n_1 + n_2.
• If the dashed line is of third order, the formula becomes \frac{n_1 n_2 n_3}{n_1} + \frac{n_1 n_2 n_3}{n_2} + \frac{n_1 n_2 n_3}{n_3} = n_2 n_3 + n_1 n_3 + n_1 n_2 = n_1 n_2 + n_1 n_3 + n_2 n_3.

We have thus found the formulas that constitute the second argument of the module, in the characterizations of the spaces for second and third order dashed lines.

Meaning of the module

In the previous paragraph we have explored the meaning of the second argument of the module in the expressions

Now let’s see what the meaning of the expressions is in full.

Second order

As for the second order, by Proposition 6.2 on page 146 of the Dashed line theory text, applied to the first row (so with \{i, j\} = \{1, 2\}), we’ll have that:

where v is the value of the x-th dash, i.e. the column which contains it (assuming it belongs to the first row).

This formula is similar to the one in the Corollary of Proposition L.C.3, which we can get closer to by removing the term -1 from the left-hand expression. To do this, we can use Property 2.15 on page 61 of the Dashed line theory text, according to which (n_1 x - 1) \textrm{\ mod\ } (n_1 + n_2) = n_1 x \textrm{\ mod}^{\star}\ (n_1 + n_2) - 1. Applying the same Property to the right-hand side, we can therefore conclude that:

from which

But in our case, as we observed just before stating the Corollary, we have that n_1 x \textrm{\ mod}^{\star}\ (n_1 + n_2) = n_1 x \textrm{\ mod\ } (n_1 + n_2). So we can conclude that:

Let’s make the expression on the right more explicit by recalling the definition of the \textrm{\ mod}^{\star} operator:

So:

• The first case occurs when the x-th dash (\mathrm{t}_{(n_1, n_2)}(x)), has a value v that is a multiple of n_2; but by hypothesis the x-th dash belongs to the first row, so we are in a situation like this:
  

  0	1	…	v \textrm{such that} \mathrm{lcm}(n_1, n_2) \mid v
  –		…	\mathrm{t}_{(n_1, n_2)}(x)
  –		…	–

• The second case occurs when the value of the x-th dash is not a multiple of n_2, so the cell under the dash is empty:
  

  0	1	…	v \textrm{such that} n_2 \nmid v
  –		…	\mathrm{t}_{(n_1, n_2)}(x)
  –		…

In both cases we can say that the expression n_1 x \textrm{\ mod\ } (n_1 + n_2) represents the difference between v and the value of the previous dash of the second row. In fact:

• In the first case, the dash following the x-th is on the second row, in the cell below in the same column, so the previous dash of component n_2 will be found n_2 columns further to the left;
• In the second case, the value of the previous dash in the second row will be equal to the largest multiple of n_2 less than v; to find this dash we must therefore move to the left by as many columns as the remainder of the division of v by n_2, that is, of v \textrm{\ mod\ } n_2 columns.

Third order

As for the third order, the meaning of the expression (n_2 + n_3) n_1 x \textrm{\ mod\ } (n_1 n_2 + n_1 n_3 + n_2 n_3) is clarified by Proposition 6.6 on page 163 of the text of Dashed line theory:

where, like before, we have indicated with v the value of the x-th dash (still assuming that it belongs to the first row).
But, by Proposition L.C.5:

where a \in \set{2, \ldots, n_3}, b \in \set{2, \ldots, n_2}.

Comparing (3) and (4), we’ll have that:

We can note that, if n_2 and n_3 are coprime, the expression n_2 h + n_3 k, as h varies \in \set{1, \ldots, n_3} and k \in \set{1, \ldots, n_2}, generates unique values.

Now, v \textrm{\ mod}^{\star}\ n_3 is between 1 and n_3, but so is a, being by hypothesis between 2 and n_3; similarly, both v \textrm{\ mod}^{\star}\ n_2 and b are between 1 and n_3. Therefore, by the property of uniqueness mentioned above, the following equalities must hold:

We have therefore found the meaning of the variables a and b of Proposition L.C.5.
As for the second order, by applying the definition of the \mathrm{mod}^{\star} operator, we can further clarify this meaning:

• a is equal to the difference between v and the value of the previous dash belonging to the third row
• b is equal to the difference between v and the value of the previous dash belonging to the second row

Meaning of the quotient

The characterization of the spaces that precede (or follow) a dash in the first row uses the expressions (1) and (2) that we have explored in the previous paragraph; however, the same expressions give further information if the modulo is replaced with the quotient of the division. By making this substitution, the two expressions become respectively:

If the x-th dash is on the first row, we have verified that these expressions calculate the number of dashes on rows other than the first that precede it. This property has not yet been proven, so we’ll state it, both in the second and third order, in the form of a Hypothesis. Let’s start with the second order:

We can observe that, if t is the x-th dash of a linear dashed line T and if it belongs to the first row, then any dash preceding it has a lower value. In fact, by Definition T.4, if a dash u precedes t, it can have a lower value or at most the same, but in this last case the row of u must have a lower index than the row of t, which however cannot happen if t belongs to the first row.
The dashes of T that precede t and belong to the second row are therefore all and only the dashes of the second row that have a value lower than that of t. Indicating this last value with v, the number of such dashes, by the Corollary of Proposition T.2, is given by the formula:

Therefore from Hypothesis H.3 we can derive the following Corollary:

Let’s now look at the equivalent of Hypothesis H.3 for the third order:

We can apply the Corollary of Proposition T.2 also in this case, for the second and third rows taken separately. As for the second row, the number of dashes of T that belong to it and that precede t, still indicating with v the value of t, is given by the same formula as before:

As for the third row, only the denominator changes:

So, to get the number of dashes that precede t and that belong to the second or third row, we have to add the two previous formulas, obtaining the following Corollary:

Graphic interpretation and maximum distance between spaces

Consider a linear dashed line (n_1, n_2, n_3) with two-by-two coprime components.

Let’s define the set:

We also define:

For x \gt 0, from Theorem T.4 we know that the x-th dash belongs to the first row if and only if the following condition holds:

Using (1) we can therefore associate each dash of the first row with an element of R.

We will call sequence a set of the kind

where b \in \set{1, \ldots, n_2} is an integer which is fixed for each sequence.

There are then n_2 sequences. For example if n_2 = 3 the set R can be written as the disjoint union of the sequences:

In general there will be n_2 sequences, each of which contains n_3 elements of an arithmetic progression of common difference n_2.

As a consequence of the theory we saw in the paragraph Meaning of the module, the dashs associated with the sequence (2), i.e. such that the result of the expression (1) belongs to it, always have a distance b from the previous dash of the second row.

These sequences, being formed by numbers distant n_2 from each other, can be understood in a similar way to first order linear dashed lines (two orders less than the initial dashed line), with two differences:

• The initial value is not 0 but n_2 + n_3, n_2 + 2 n_3, n_2 + 3 n_3, etc., depending on the sequence
• The number of dashes is not infinite, but is n_3 for all sequences

Graphically, we can illustrate the sequences as colored points on a circle containing T points equally spaced and numbered from 0 to T - 1 (the possible remainders modulo T), using a different color for each sequence and sorting the points in ascending order:

From this representation it’s clear how the sequences occupy a considerable part of the circle, and how the shifts between one sequence and another mean that some portions of the circle are occupied by only one sequence, others by more than one sequence.

The points of the set R thus highlighted are associated, through (1), to all and only the dashes of the first row. We can observe that the first dash of the first row (which is also the first dash in absolute terms) is associated to the number K \mathrm{\ mod\ } T, which is equal to K, because K \lt T, therefore it’s associated to the number n_1(n_2 + n_3). If n_1 = 2, the number associated to the first dash is 2(n_2 + n_3) which is the smallest value of the sequence S_1. Starting from this number and going around the circumference clockwise, skipping K-1 points and taking the K-th, you will obtain the next value of the expression (1); always proceeding in this way, you will sooner or later obtain another element of R, which will be the one associated with the next dash of the first row of the dash.

How many jumps of K points can be made at most, to go from one element of R to another? The problem seems complicated from a numerical point of view, but the solution is very simple, since the number sought is nothing other than the maximum distance between two dashes of the first row measured in dash ordinals (i.e. in the variable x). Between two consecutive dashes of the first row there can be at most one dash for each other line (if there were more than one, their distance in columns would exceed that between the two dashes of the first row, because the other components are all larger than the first). Therefore, the maximum distance in ordinals between two dashes of the first row in a third order dashed line is 3 (at most 2 intermediate dashes of other rows, plus the ordinal of the next dash of the first row). So we can be sure that, with at most 3 jumps of K on the circumference, we can go from one point of R to another point of R.

Now let’s see what changes when we want to consider only the dashes of the first row that are preceded by a space. In this case the set R is replaced by the set P:

For x \gt 0, we know that the x-th dash belongs to the first row and is preceded by a space if and only if the condition is true:

Even in this case we can identify sequences, which are now of the kind:

where b \in \set{2, \ldots, n_2} is an integer which is fixed for each sequence.

In this case there exist n_2 - 1 sequences. For example if n_2 = 3 the set P can be written as the disjoint union of sequences:

The differences compared to before are essentially two:

• The sequence S_1 has been deleted
• The other sequences have lost one element each

On a graphical level, the situation that is obtained for the dashed line (2, 5, 7) is the following:

We can now ask ourselves a question similar to the previous one: how many jumps of K can be made at most, to go from an element of P to another element of P? This question is important, because it would mean calculating how many ordinals can separate at most two dashes of the first row that are both preceded by a space; it would be like calculating the maximum distance between two spaces, net of having to transform from ordinals to columns, an operation that is not complicated (we’ll talk about it at the end of the article).

You might think of answering the question by reasoning from a numerical point of view. Supposing we start from the first element of the first sequence, that is, from n_1(n_2 + n_3), the next element of P will be larger, but lower than n_1(n_2 + n_3) + K, so we’ll need to do at least one complete turn of the circumference. To do a complete turn, being T the length of the circumference and K the length of the jump, we need at least \left\lceil \frac{T}{K} \right\rceil jumps (this observation also applies to the previous case, with R instead of P). At this point, let’s say:

This number represents the number of positions that one advances, from a starting position, after completing a complete turn of the circle jumping K by K. Doing the calculations, we get that:

So, starting from n_1(n_2 + n_3), the next number, after going around the circle once, will be n_1(n_2 + n_3) + r. If r is small, this number will still be in the portion of the circumference occupied by the sequences, so there is a chance that it will fall into some sequence (and therefore into P); if this is not the case, you can go around the circle again to get the numbers n_1(n_2 + n_3) + 2r, n_1(n_2 + n_3) + 3r, etc. The problem is that this approach doesn’t work if r is large, because the numbers n_1(n_2 + n_3) + hr might go outside the portion of the circle occupied by the sequences, even for a very low value of h.

The numerical approach seems too complicated to be solved directly. The best approach would be to find a dashed line that somehow represents (1′) a bit like the starting dashed line represents (1); this way we could find the maximum number of jumps needed to go from one element of P to another by reasoning on such representation rather than numerically.

Probabilistic approximation

It might be possible to simplify the problem if we were to look for an approximate solution, based on the concept that, in the representation we have seen, in some parts of the circle there are more elements of P, either consecutive or possibly separated by points that are not in P. Following this principle, the previous picture can be divided into zones, for example this way:

in which:

• Zone A contains points that are all elements of P, i.e. 100%;
• Zone B contains 8 points which are P elements out of 9, i.e. 88%;
• Zone C contains 18 points which are P elements out of 28, or 64%;
• Zone D contains 20 points which are P elements out of 35, or 57%;
• The whole circle contains 20 points which are P elements out of 59, or 33%.

More generally, then, the percentages indicate the probability that, falling in a certain area, an element of P is found. The previous problem, then, could be interpreted this way: how many jumps of K can be made at most, to fall on a point such that the probability of being an element of P is above a certain threshold?

Transforming an ordinal distance into a columnar distance

If we were to get to the bottom of this proof strategy, we would end up calculating the maximum distance between two dashes both preceded by a space, measured in dash ordinals. We need the distance in columns instead, because clearly the distance in columns between the two dashes in question is the same as that of the spaces that precede them. So we need to answer this question: if two dashes are at most d apart in terms of ordinals, what can be at most their distance measured in columns?
In any third order linear dashed line, the minimum number of dashes in c consecutive columns is given by the formula:

So, if we have d consecutive dashes and we want to know the maximum number of columns that can contain them, we need to find the smallest c such that

Since \left\lfloor \frac{c}{n_1} \right\rfloor + \left\lfloor \frac{c}{n_2} \right\rfloor + \left\lfloor \frac{c}{n_3} \right\rfloor \lt \frac{c}{n_1} + \frac{c}{n_2} + \frac{c}{n_3}, all the more reason we can find the smallest c such that:

Doing the calculations, we’ll have:

So \left\lfloor \frac{d n_1 n_2 n_3}{T} \right\rfloor + 1 columns surely contain more than d dashes, so d consecutive dashes can occupy a maximum of \left\lfloor \frac{d n_1 n_2 n_3}{T} \right\rfloor columns.