13. Computation of spaces in second order linear dashed lines

Prerequirements:

In this post we’ll see how to obtain the formula for computing the \mathrm{t\_space} function for second order linear dashed lines. As we already said about \mathrm{t} and \mathrm{t\_value} functions, the general approach we’ll follow is the downcast one. In the case of \mathrm{t\_space}, it turns out to be simpler, because the function is down-conservative (v. Property T.6 (Down-conservativity of functions \mathrm{t}, \mathrm{t\_value} and \mathrm{t\_space})). In fact, given the x-th space of a second order linear dashed line T, we know that it’s also a space of any first order dashed subline T[i], so there always exists, for any x, an integer y such that

\mathrm{t\_space}_T(x) = \mathrm{t\_space}_{T[i]}(y)

The right member, referred to a first order dashed line, can be computed with the formula of Theorem T.1, so the main problem when computing \mathrm{t\_space}_T(x) is to find the number y. Before finding it, we’ll characterize it, as a solution of an equation, similarly to what we did for the first order in Proposition T.3 (Characteristic equation of first order linear \mathrm{t\_space} function). But we’ll see that the passage from the characterization to the formula is not easy, and we’ll see that it’s more convenient to find an approximated formula first, that can be modified in order to achieve the exact formula.

Characteristic equation of second order linear \mathrm{t\_space}

Let T = (n_1, n_2) be a second order linear dashed line, x a fixed positive integer, and s := \mathrm{t\_space}_T(x). Then:

  • Being s the x-th space of T, the first s columns of T can be divided into x spaces and s - x columns containing at least one dash
  • Among the s - x columns containing at least one dash, only the ones divisible by both n_1 and n_2, that are the ones divisible by \mathrm{LCM}(n_1, n_2), contain two dashes; the other ones contain only one dash.

Let’s ask ourselves now: how many dashes are there in the first s columns of T? In order to answer this question, it’s possible to count dashes in at least two manners: by columns and by rows.

  • If we count dashes by columns, we have to count 1 for every column containing only one dash, and 2 for those ones containing two dashes (more than two is not possible, because the dashed line has order two).
  • If instead we count dashes by rows, we have to sum up the number of dashes in the first row, with the number of dashes in the second row, in both cases limiting ourselves to those ones with value less than or equal to s. We can compute these numbers by applying Proposition T.2 (Count of dashes up to a certain value in a first order linear dashed line).
Figure 1: count of dashes by rows and by columns. In the count by columns (on the top), we count 1 for every column containing only one dash (the number of such columns is indicated with #C(1)), and 2 for every column containing two dashes (the number of such columns is indicated with #C(2)). In the count by rows, the dashes of the first row (the number of which is indicated with #R(1)) and the ones of the second row (the number of which is indicated with #R(2)) are counted separately.

So, making some calculations, we can obtain two different formulas that however, since they compute the same amount of dashes, can be equalized, originating the following equation:

s - x + \left \lfloor \frac{s}{\mathrm{LCM}(n_1, n_2)} \right \rfloor = \left \lfloor \frac{s}{n_1} \right \rfloor + \left \lfloor \frac{s}{n_2} \right \rfloor \tag{6}

Let’s indicate with \#C(i) the number of columns containing i dashes, for i = 1, 2. Then, when counting dashes by columns, their total number, that we’ll call \#t, is given by the formula:

\#t = \underbrace{1 + \ldots + 1}_{\#C(1)\text{ times}} + \underbrace{2 + \ldots + 2}_{\#C(2)\text{ times}} = \#C(1) + 2 \cdot \#C(2) \tag{1}

We can note that \#C(1) + \#C(2) is the number of columns containing at least one dash, because in a second order dashed line, if a column contains at least one dash, either it contains just one (and so is counted within \#C(1)), or it contains two (and so is counted within \#C(2)). But we said that the number of columns containing at least one dash is s - x, hence

\#C(1) + \#C(2) = s - x \tag{2}

Putting (2) into (1), we’ll have that

\#t = \#C(1) + 2 \cdot \#C(2) = (\#C(1) + \#C(2)) + \#C(2) = s - x + \#C(2) \tag{3}

It remains to be understood how to compute \#C(2). If a column contains two dashes, it means that it’s divisible by both n_1 and n_2, so it’s divisible by \mathrm{LCM}(n_1, n_2). Conversely, all multiples of \mathrm{LCM}(n_1, n_2) are divisible by n_1 and n_2, so they are columns containing two dashes. So the concepts of “column with two dashes” and “multiple of \mathrm{LCM}(n_1, n_2)” coincide perfectly. Then \#C(2) is equal to the number of multiples of \mathrm{LCM}(n_1, n_2) less than or equal to s, which can be thought about as the number of dashes of the dashed line (\mathrm{LCM}(n_1, n_2)) having value less than or equal to s. In turn, by Proposition T.2 (Count of dashes up to a certain value in a first order linear dashed line), it is given by the formula \left \lfloor \frac{s}{\mathrm{LCM}(n_1, n_2)} \right \rfloor:

\#C(2) = \#\text{multiples of }\mathrm{LCM}(n_1, n_2)\text{ less than or equal to }s = \left \lfloor \frac{s}{\mathrm{LCM}(n_1, n_2)} \right \rfloor

Substituting into (3) we’ll have:

\#t = s - x + \#C(2) = s - x + \left \lfloor \frac{s}{\mathrm{LCM}(n_1, n_2)} \right \rfloor \tag{4}

Let’s see what happens if we instead count dashes by rows. Let’s indicate with \#R(i) the number of dashes in row i, having value less than or equal to s. As we have said, we can compute this number by applying Proposition T.2, hence the total number of dashes is

\#t = \#R(1) + \#R(2) = \left \lfloor \frac{s}{n_1} \right \rfloor + \left \lfloor \frac{s}{n_2} \right \rfloor \tag{5}

Counting dashes in different ways, we have obtained different formulas; but, since we counted the same amount of dashes, that we called \#t, the two formulas must coincide. So, joining formulas (4) and (5), formula (6) is obtained.

As we noted about first order dashed lines, when counting dashes by rows we can stop at column s - 1 instead of s, because the latter is a space by hypothesis. In other terms, by applying Proposition T.2 and its Corollary, we’ll have that

\begin{cases}\left \lfloor \frac{s}{n_1} \right \rfloor = \left \lfloor \frac{s - 1}{n_1} \right \rfloor \\ \left \lfloor \frac{s}{n_2} \right \rfloor = \left \lfloor \frac{s - 1}{n_2} \right \rfloor \end{cases} \tag{7}

Condition (7) can be in turn expressed by saying that s is a space of T:

Characterization of the spaces of a second order linear dashed line, by means of a system of equations with the integer part

Let T = (n_1, n_2) be a second order linear dashed line. For every positive integer s the following equivalence is true:

s \text{ is a space of }T \Leftrightarrow \begin{cases} \left \lfloor \frac{s}{n_1} \right \rfloor = \left \lfloor \frac{s - 1}{n_1} \right \rfloor \\ \left \lfloor \frac{s}{n_2} \right \rfloor = \left \lfloor \frac{s - 1}{n_2} \right \rfloor \end{cases} \tag{7'}

This Proposition is an easy extension of Proposition T.5 (Characterization of the spaces of a first order linear dashed line by means of an equation with the integer part), according to which the first equation is equivalent to say that s is a space of the first order dashed line (n_1), and similarly the second equation is equivalent to say that s is a space of (n_2). Hence

\begin{cases} \left \lfloor \frac{s}{n_1} \right \rfloor = \left \lfloor \frac{s - 1}{n_1} \right \rfloor \\ \left \lfloor \frac{s}{n_2} \right \rfloor = \left \lfloor \frac{s - 1}{n_2} \right \rfloor \end{cases} \Leftrightarrow \begin{cases} s \text{ is a space of }(n_1) \\ s \text{ is a space of }(n_2) \end{cases}

In other terms, s is not divisible either by n_1 (because it’s a space of (n_1)), either by n_2 (because it’s a space of (n_2)). But this means that s is a space of T = (n_1, n_2).

Joining formula (6), where for improving readability we bring all the integer parts to the right, with the condition that s is a space of T, that we characterized in the previous Proposition, we’ll obtain the equation we call characteristic equation of second order linear \mathrm{t\_space}:

Characteristic equation of second order linear \mathrm{t\_space}

Let T = (n_1, n_2) be a second order linear dashed line. Then

s = \mathrm{t\_space}_T(x) \Leftrightarrow \begin{cases} s - x = \left \lfloor \frac{s}{n_1} \right \rfloor + \left \lfloor \frac{s}{n_2} \right \rfloor - \left \lfloor \frac{s}{\mathrm{LCM}(n_1, n_2)} \right \rfloor \\ s \text{ is a space of }T \end{cases} \tag{8}

Formula (8) is called characteristic equation of second order linear \mathrm{t\_space}

For simplicity we call “equation” formula (8) even if it’s, actually, an equation joined with a constraint about its solutions.

Count of the spaces in a period of a second order linear dashed line

Before seeing the formula for computing \mathrm{t\_space}, let’s stop for a while, for answering the following question that we’ll often find later: “how many spaces are there in a period of a second order linear dashed line?”.
First of all this question makes sense because, by the Corollary of Property T.3 (Number of spaces in a period), all the periods of a periodical dashed line have the same number of spaces, and linear dashed lines are periodical, by Property T.4. We can say, in other terms, that the answer does not depend on the chosen period, but only on the dashed line. Since this number will often appear later, it’s convenient to give it a name:

Number of spaces in a period of a periodical dashed line

Let T be a periodical dashed line. The number of spaces in a period of T is denoted with the symbol S(T).

If T is a second order linear dashed line, the number S(T) is given by the following Property:

Computation of the number of spaces in a second order linear dashed line

Let T = (n_1, n_2) be a second order linear dashed line. Then the number of spaces in a period of T is

S(T) = \frac{(n_1 - 1)(n_2 - 1) - 1}{\mathrm{GCD}(n_1, n_2)} + 1 \tag{9}

In addition, the number of the remaining columns, that are not spaces, is given by the formula:

\frac{n_1 + n_2}{\mathrm{GCD}(n_1, n_2)} - 1 \tag{10}

Property T.7, besides the formula that computes the number of spaces, gives also the one that computes the number of columns that are not spaces. However this number could be obtained by subtracting the number of spaces from the total period length, that we know to be \mathrm{LCM}(n_1, n_2). So why giving both formulas? There are two reasons:

  • The formula that computes the number of columns that are not spaces is easier to compute, so much that it may be convenient to start from it in order to compute S(T):
    S(T) = \mathrm{LCM}(n_1, n_2) - (\mathrm{LCM}(n_1, n_2) - S(T)) = \mathrm{LCM}(n_1, n_2) - \left( \frac{n_1 + n_2}{\mathrm{GCD}(n_1, n_2)} - 1 \right)
  • The proof (Teoria dei tratteggi (Dashed line theory, in Italian), pages 122-123) turns out to be simpler if (10) is proved first and (9) last

Lastly we note that, if the dashed line components are coprime, the formula for S(T) can be simplified a lot:

S(T) = \frac{(n_1 - 1)(n_2 - 1) - 1}{\mathrm{GCD}(n_1, n_2)} + 1 = \frac{(n_1 - 1)(n_2 - 1) - 1}{1} + 1 = (n_1 - 1)(n_2 - 1) \tag{9'}

Approximated formula for computing second order linear \mathrm{t\_space}

If you try to compute the \mathrm{t\_space} function by solving the characteristic equation (8), you can soon realize that the term causing most problems in calculations is - \left \lfloor \frac{s}{\mathrm{LCM}(n_1, n_2)} \right \rfloor. However, this term is the smallest in absolute value among the terms with the integer part, being the one with the greatest denominator. So as a first step we may think about disregarding it, thus obtaining the equation:

\begin{cases} s - x = \left \lfloor \frac{s}{n_1} \right \rfloor + \left \lfloor \frac{s}{n_2} \right \rfloor \\ s \text{ is a space of }T \end{cases}

The unknown is always s, that now is no more \mathrm{t\_space}_T(x), but something similar, as we specify with the following Theorem:

Solution of the modified characteristc equation of second order linear \mathrm{t\_space}

Let T = (n_1, n_2) be a second order linear dashed line different from (2, 2), let x \gt 0 a fixed integer. Let’s consider the following equation, obtained by modifying the characteristic equation(8), in the unknown s:

\begin{cases} s - x = \left \lfloor \frac{s}{n_1} \right \rfloor + \left \lfloor \frac{s}{n_2} \right \rfloor \\ s \text{ is a space of }T \end{cases} \tag{8'}

Then two cases are possible:

  • If x is of the kind k (S(T) - 1) + 1 (for the computation of S(T) see Property T.7), with k \gt 0, then equation (8′) has two solutions, given by
    k \cdot \mathrm{LCM}(n_1, n_2) \pm 1
  • Otherwise, equation (8′) has only one solution. In this case, choose i and j such that \{i, j\} = \{1, 2\}, and let s^{\prime}_{i}: \mathbb{N}^{\star} \rightarrow \mathbb{N} be the function defined as
    s^{\prime}_i (x) := \left \lfloor \frac{(n_i - 1)(n_j x - 1) - 1}{(n_i - 1)(n_j - 1) - 1} \right \rfloor

    Then the solution of (8′) is given by \mathrm{t\_space}_T^{\prime}(x), where the function \mathrm{t\_space}_T^{\prime}: \mathbb{N}^{\star} \rightarrow \mathbb{N} is defined as

    \mathrm{t\_space}_T^{\prime}(x) := \mathrm{t\_space}_{(n_i)} \left( s^{\prime}_{i}(x) \right) \tag{11}

    and the function so defined is the same for both possible choices of i.

Finally, in the first case the equation (11) gives the value of the greatest solution of the two.

We can note that definition (11) looks a lot like a downcast, because it resorts to the first order function \mathrm{t\_space}_{(n_i)}. But in this case we cannot strictly speak about downcast, because the function computed by (11) is not the second order \mathrm{t\_space} function, but an approximation of it.
However, there is a strong formal similarity between formula (11) and the formula for downcast of second order \mathrm{t\_space}. With the downcast approach, in fact, we compute the function \mathrm{t\_space}_T by means of a formula like

\mathrm{t\_space}_T(x) = \mathrm{t\_space}_{(n_i)} \left( s_{i}(x) \right) \tag{11'}

where s_{i}(x) is a downcast function of \mathrm{t\_space} from T to T[i]. Comparing (11′) with (11), you can note that the exact downcast function s_{i}(x) has been replaced by the function s^{\prime}_{i}(x), that is an approximation of it, thus generating an approximation in the result, that becomes a new function called \mathrm{t\_space}_T^{\prime}(x) instead of \mathrm{t\_space}_T(x).

It’s interesting to note that, when doing this approximation, symmetry did not get lost: like formula (11′) is true for any choice of i, generating two different formulas computing \mathrm{t\_space}_T(x), one for i = 1 and one for i = 2, in the same way formula (11) defines the function \mathrm{t\_space}_T^{\prime} in two different ways according to the choice of i, but the function defined in the two cases is the same. This properties descends from the fact that equation (8′), from which \mathrm{t\_space}^{\prime}_T is obtained, is symmetrical with respect to the variables n_1 and n_2 just like (8), from which \mathrm{t\_space}_T is obtained. This symmetry in the original equation implies that, if we prove a formula for computing \mathrm{t\_space}_T or \mathrm{t\_space}^{\prime}_T, automatically the formula obtained by it exchanging n_1 and n_2 is also proved. In fact, if n_1 and n_2 can be exchanged in the starting equation, without changing it, then they can also be exchanged in the formula that expresses the solution, without changing the result.

The proof is rather complicated and you can find it in Teoria dei tratteggi (Dashed line theory, in Italian), pages 208-220. However, the important thing, rather than the proof, that is very technical, is to understand the sense of the statement. First of all the function \mathrm{t\_space}_T^{\prime} is of some interest, because it’s a “space generator”. In fact Theorem T.12 states that the result of formula (11) is a space, being the solution of equation (8′) that, like (8), allows only spaces as solutions. Another interesting feature of the \mathrm{t\_space}_T^{\prime} function is that it generates spaces in an orderly fashion, being a function increasing in x.
Actually it’s not difficult to find functions with these features: some very simple examples are the functions \mathrm{LCM}(n_1, n_2) \cdot x - 1 and \mathrm{LCM}(n_1, n_2) \cdot x + 1, that return spaces for all x and are increasing in x. However these formulas generate a very scarce number of spaces, only one for each period of the dashed line, among S(T) total spaces. For example, considering the dashed line T = (3, 5), the only value assumed by the first function on the period from column 0 to column \mathrm{LCM}(n_1, n_2) - 1 = 14 is just \mathrm{LCM}(n_1, n_2) - 1 = 14, while in this period, like in any period, there are 8 spaces (we’ll check this with calculations in the next example). The virtue of the \mathrm{t\_space}_T^{\prime} function is to generate, instead, many spaces: it generates S(T) - 1 spaces for each period, skipping just one. We illustrate by an example this behaviour, that is a consequence of Theorem T.12 and we do not prove it for the moment.

Let’s consider the dashed line T = (n_1, n_2) = (3, 5). By Property T.7, the number of spaces in a period of the dashed line is S(T) = \frac{(n_1 - 1)(n_2 - 1) - 1}{\mathrm{GCD}(n_1, n_2)} + 1 = \frac{2 \cdot 4 - 1}{1} + 1 = 7 + 1 = 8. The function \mathrm{t\_space}_T^{\prime}(x) for this dashed line is the following:

\begin{aligned} \mathrm{t\_space}_{(n_1,n_2)}^{\prime}(x) & = \\ \mathrm{t\_space}_{(n_1)} \left( \left \lfloor \frac{(n_1 - 1)(n_2 x - 1) - 1}{(n_1 - 1)(n_2 - 1) - 1} \right \rfloor \right) & = \\ \mathrm{t\_space}_{(3)} \left( \left \lfloor \frac{2(5 x - 1) - 1}{2 \cdot 4 - 1} \right \rfloor \right) & = \\ \mathrm{t\_space}_{(3)} \left( \left \lfloor \frac{10 x - 3}{7} \right \rfloor \right) & = \text{[by Theorem T.1]}\\ \left \lfloor \frac{ 3 \cdot \left \lfloor \frac{10 x - 3}{7} \right \rfloor - 1 }{2} \right \rfloor \end{aligned}

The first 15 values assumed by this function, for x = 1, 2, 3, \ldots, are the following:

x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
\mathrm{t\_space}_{(n_1,n_2)}^{\prime}(x) 1 2 4 7 8 11 13 16 17 19 22 23 26 28 31

Theorem T.12 states that, for each x, the number s := \mathrm{t\_space}_{(n_1,n_2)}^{\prime}(x) is a solution of equation (8′), which in our case is

\begin{cases} s - x = \left \lfloor \frac{s}{3} \right \rfloor + \left \lfloor \frac{s}{5} \right \rfloor \\ s \text{ is a space of }(3, 5) \end{cases} \tag{12}

For example, substituting the couple (x, s) = (8, 16) highlighted in bold in the table, we’ll have:

\begin{cases} 16 - 8 = \left \lfloor \frac{16}{3} \right \rfloor + \left \lfloor \frac{16}{5} \right \rfloor \\ 16 \text{ is a space of }(3, 5) \end{cases}

Indeed the equation is satisfied, since \left \lfloor \frac{16}{3} \right \rfloor + \left \lfloor \frac{16}{5} \right \rfloor = 5 + 3 = 8 = 16 - 8, and being 16 non divisible either by 3, either by 5. The same thing is true for the remaining couples of the table.

Representing these couples (x, s) together with the dashed line, we can see how in each period all the spaces, except the last one, are values assumed by the function \mathrm{t\_space}_{(n_1,n_2)}^{\prime}, i.e. are some “s“. In other terms, the function “skips” all the spaces of the kind \mathrm{LCM}(n_1, n_2) \cdot k - 1 = 15 k - 1:

Figure 2: graphical representation of the function t_space’. It returns all the spaces of a second order linear dashed line, except the last of each period (the last of the first period has been highlighted in red).

The most interesting values of x are those that are part of the first case of Theorem T.12, i.e. those of the kind k (S(T) - 1) + 1, with k \gt 0: the first of such xs is S(T) and the next ones are 2 \cdot S(T) - 1, 3 \cdot S(T) - 2, etcetera. Let’s focus on the first one, obtained with k = 1, that in our case is 8. The cited Proposition states that, for x = 8, equation (8′) has two solutions, that are

k \cdot \mathrm{LCM}(n_1, n_2) \pm 1 = \mathrm{LCM}(n_1, n_2) \pm 1 = 15 \pm 1 = 14, 16 \tag{13}

We saw before the solution 16: it’s one of the values assumed by the \mathrm{t\_space}_{(n_1,n_2)}^{\prime} function, and we checked it to satisfy equation (8′), that in our case is (12). But the same equation is also satisfied by the other number:

\begin{cases} 14 - 8 = \left \lfloor \frac{14}{3} \right \rfloor + \left \lfloor \frac{14}{5} \right \rfloor \\ 14 \text{ is a space of }(3, 5) \end{cases}

We have that \left \lfloor \frac{14}{3} \right \rfloor + \left \lfloor \frac{14}{5} \right \rfloor = 4 + 2 = 6 = 14 - 8, and 14 is a space of the dashed line too, so also 14 is a solution of the equation. Theorem T.12 says that these cases, when the equation has a double solution, happens only when x is of the kind k (S(T) - 1) + 1, with k \gt 0; in addition, when this happens, the solution is given by formula (13), far simpler than the one that expresses \mathrm{t\_space}_{(n_1,n_2)}^{\prime}(x). However, even in these cases the formula for \mathrm{t\_space}_{(n_1,n_2)}^{\prime}(x) does not make a mistake, but it simply “choose” one of the two solutions, the biggest one. In fact, as we have seen, \mathrm{t\_space}_{(3,5)}^{\prime}(8) = 16 and not 14.

We can note that in the statement of Theorem T.12 the dashed line (2,2) has been excluded. In fact, if n_1 = n_2 = 2, the denominator of the fraction appearing in the expression of s^{\prime}_i would be zero, hence this function would not be defined, and the same would be true for \mathrm{t\_space}^{\prime}, that is defined by means of s^{\prime}_i.

In the light of the previous example, the reason for the exclusion of the dashed line (2,2) appears clearer. First of all this dashed line may be considered degenerate, because it has two equal components, and for the same reason it’s little useful in practice, but at a theoretical level it’s a possible case. It has periods of length 2, each having only one space. So, given that the \mathrm{t\_space}^{\prime} function skips one space for each period, it could never return the spaces of this dashed line. For the function \mathrm{t\_space}^{\prime} to be applicable, there must be at least two spaces per period, so that, after one space has been skipped, there is another one to compute. This is true in all second order linear dashed lines, just apart from (2,2). This explanation integrates the former, purely algebrical.

Exact formula for computing second order linear \mathrm{t\_space}

Now that we have seen in detail the \mathrm{t\_space}^{\prime} function, which in light of the previous example we can regard at all effects as an “approximated” \mathrm{t\_space} functions, thanks to a technical artifice we can construct the exact function. The mathematical details are in Teoria dei tratteggi (Dashed line theory, in Italian), pages 221-224, and the final result is the following:

Downcast of linear \mathrm{t\_space} from the second order to the first one

Let T = (n_1, n_2) be a second order linear dashed line, let i and j be such that \{i, j\} = \{1, 2\}. Then a downcast function of \mathrm{t\_space} from T to T[i] is the function s_i: \mathbb{N}^{\star} \rightarrow \mathbb{N}^{\star} such that:

s_i(x) := \begin{cases} \frac{x}{S(T)} (n_i - 1) \frac{\mathrm{LCM}(n_i, n_j)}{n_i} & \text{if }S(T) \mid x \\ s^{\prime}_i \left ( x - \left \lfloor \frac{x}{S(T)} \right \rfloor \right ) & \text{otherwise} \end{cases} \tag{14}

where S(T) is the number of spaces in a period of T (see Property T.7), and s^{\prime}_i is the function defined in Theorem T.12.

In definition (14) there are two cases:

  • The first case is when x is a multiple of S(T), that is x = S(T), 2 \cdot S(T), 3 \cdot S(T), \ldots. But, since every period of T has S(T) spaces, the S(T)-th space is the last space of the first period, the 2 \cdot S(T)-th space is the last of the second period, and so on. Then this case is helpful for computing the last space of each period. It’s not by chance that these spaces are exactly those “skipped” by the \mathrm{t\_space}^{\prime} function, as we saw in the previous example.
  • In the second case we have that s_i(x) = s^{\prime}_i \left (x - \left \lfloor \frac{x}{S(T)} \right \rfloor \right ), i.e. the downcast function s_i employs its approximation, though introducing in its argument the term - \frac{x}{S(T)}, that is a “correction” for taking account of the skipped spaces.

In order to understand better definition (14), it’s worth first of all sketching it, identifying the three main functions involved:

  • The function that maps x to \frac{x}{S(T)} (n_i - 1) \frac{\mathrm{LCM}(n_i, n_j)}{n_i}, that is involved in the first case; we’ll call it f_i
  • The function that maps x to x - \left \lfloor \frac{x}{S(T)} \right \rfloor , that we’ll call g
  • The function s^{\prime}_i

This way, formula (14) becomes:

s_i(x) := \begin{cases} f_i(x) & \text{if }S(T) \mid x \\ s^{\prime}_i(g(x)) & \text{otherwise} \end{cases} \tag{14'}

The role of the functions f_i, g and s^{\prime}_i, is clarified by the following example.

Let’s recall the dashed line T = (3, 5) of the previous example, having S(T) = 8. Applying definition (14′) with i = 1, we can compute the function s_1(x) for x = 1, \ldots, 11:

Figure 3: graphical representation of the downcast function s1, which maps the ordinal of a space of a second order linear dashed line (at top) to the corresponding ordinal in its dashed subline T[1] (at bottom). To do this, it makes use of functions g (black arrows), s’1 (blue arrows) and f (green arrow).

We can note that the aim of function g is to map the ordinal x referred to the dashed line T to the corresponding argument of function s^{\prime}_1, taking into account that the latter “skips” one space out of S(T), in this case one space out of 8. This way the downcast can be made for all spaces which are not the last of a period. For the other spaces, the corresponding first order ordinal is computed in a single step by means of the f_1 function (for example, in Figure 3 the ordinal 8 is mapped directly to ordinal 10). In fact, it could never be obtained by applying s^{\prime}_1, because it does not make part of its image (that are the numbers “reached” by the blue arrows).

Starting from Theorem T.13, we can obtain an explicit formula for computing the second order linear \mathrm{t\_space} function:

Formulas for computing second order linear \mathrm{t\_space}

Let T = (n_1, n_2) be a second order linear dashed line, let i and j be such that \{i, j\} = \{1, 2\}. Then:

\mathrm{t\_space}_T(x) = \begin{cases} \frac{x}{S(T)} \mathrm{LCM}(n_i, n_j) - 1 & \text{if }S(T) \mid x \\ \left \lfloor \frac{n_i \left \lfloor \frac{(n_i - 1)\left (n_j \left (x - \left \lfloor \frac{x}{S(T)} \right \rfloor \right ) - 1 \right ) - 1}{(n_i - 1)(n_j - 1) - 1} \right \rfloor - 1}{n_i - 1} \right \rfloor & \text{otherwise} \end{cases}

where S(T) is the number of spaces in a period of T (see Property T.7).

The explicit formula for second order linear \mathrm{t\_space} is obtained by the downcast equation (11′), where the \mathrm{t\_space}_{(n_i)} function is given by Theorem T.1 and s_i(x) is given by Theorem T.13, which in turn refers to Theorem T.12. So it’s all about substituting one formula into the other one, however it’s worth analyzing what happens in the first case, when S(T) \mid x. In this case in fact we’ll have that:

\begin{aligned} \mathrm{t\_space}_T(x) & = \\ \mathrm{t\_space}_{(n_i)} \left( s_{i}(x) \right) & = \text{[in the case that }S(T) \mid x\text{]}\\ \mathrm{t\_space}_{(n_i)} \left( \frac{x}{S(T)} (n_i - 1) \frac{\mathrm{LCM}(n_i, n_j)}{n_i} \right) & = \text{[by Theorem T.1]}\\ \left \lfloor \frac{n_i \frac{x}{S(T)} (n_i - 1) \frac{\mathrm{LCM}(n_i, n_j)}{n_i} - 1}{n_i - 1} \right \rfloor & = \\ n_i \frac{x}{S(T)} \frac{\mathrm{LCM}(n_i, n_j)}{n_i} - 1 & = \\ \frac{x}{S(T)} \cdot \mathrm{LCM}(n_i, n_j) - 1\end{aligned}

In the passages above you can note how the downcast function s_i and the \mathrm{t\_space}_{(n_i)} function simplify each other: this indicates that in this case the downcast approach was not necessary, but the problem could be solved in a more direct way. This problem comes from the fact that we obtained the exact formula starting from an approximated one, in a not exactly “polite” way. Whether we can do better, it’s still an open point (see the last part of the post).

In the explicit form, the complexity of the formula for computing second order linear \mathrm{t\_space} is clearer. This complexity is also due to the presence of three nested integer part operations:

  • the most external integer part comes from the first order function \mathrm{t\_space}_{(n_i)}
  • the central one comes from the approximated downcast function s^{\prime}_i
  • the most internal integer part is necessary in order to transform the approximated downcast function in the exact one

Let’s check, with explicit calculations, that \mathrm{t\_space}_{(3, 5)}(10) = 17 (as you can see in Figure 3, expanding the details).

First of all S(T) = 8 does not divide 10, so we have to apply the second case of the formula. Let’s choose the formula with i = 1:

\begin{aligned} \mathrm{t\_space}_T(x) = \left \lfloor \frac{n_1 \left \lfloor \frac{(n_1 - 1)\left (n_2 \left (x - \left \lfloor \frac{x}{S(T)} \right \rfloor \right ) - 1 \right ) - 1}{(n_1 - 1)(n_2 - 1) - 1} \right \rfloor - 1}{n_1 - 1} \right \rfloor & = \\ \left \lfloor \frac{3 \left \lfloor \frac{2 \left (5 \left (10 - \left \lfloor \frac{10}{8} \right \rfloor \right ) - 1 \right ) - 1}{2 \cdot 4 - 1} \right \rfloor - 1}{2} \right \rfloor = \left \lfloor \frac{3 \left \lfloor \frac{2(5 (10 - 1) - 1) - 1}{7} \right \rfloor - 1}{2} \right \rfloor &= \\ \left \lfloor \frac{3 \left \lfloor \frac{2(45 - 1) - 1}{7} \right \rfloor - 1}{2} \right \rfloor = \left \lfloor \frac{3 \left \lfloor \frac{87}{7} \right \rfloor - 1}{2} \right \rfloor &= \\ \left \lfloor \frac{3 \cdot 12 - 1}{2} \right \rfloor = \left \lfloor \frac{35}{2} \right \rfloor &= \\ 17 \end{aligned}

The most curious of you will want to check that the same result is achieved, with different calculations, using the formula with i = 2.

You could think that Theorem T.13 (second form) is the final solution to the problem of finding second order linear \mathrm{t\_space} function. Well, we have find an algebrical expression of the function, but in our opinion it’s not yet enough. In particular, we have strong doubts about the scalability of the formula to the orders greater than the second one. In fact, the formula for \mathrm{t\_space} has been obtained from the one for \mathrm{t\_space}^{\prime} by means of a technical artifice, but it’s not sure that the same operation is possible for orders higher than the second one, where things get much more complicated. However, if for higher orders we limit ourselves to use the formula for \mathrm{t\_space}^{\prime}, it may not be as accurate as it should in order to be used in proofs: in fact, if in the second order it skips just one space for each period, the fraction of skipped spaces, over the total number of spaces of the period, may increase as the order increases.
So the question of \mathrm{t\_space} is still open for us, even for the second order. In fact our current formula for second order \mathrm{t\_space} has at least three defects that make it difficult to be used:

  • it’s complicated
  • it’s defined by cases
  • it contains three integer part operations, while the first order formula contains just one

So we ask ourselves: is such a complicated formula, defined by cases, and with three integer parts, really necessary for computing second order linear \mathrm{t\_space} function? Or there exists a simpler formula for computing the same function, maybe not defined by cases and with less than three integer parts? Potentially, is it possible to compute second order \mathrm{t\_space} by giving up the downcast approach, i.e. without using the first order \mathrm{t\_space} function? Till now these questions remain without an answer.

Leave a Reply

Your email address will not be published.