Prerequirement: The downcast problem
In the previous post we defined the downcast problem, the solution of which lets compute the \mathrm{t}, \mathrm{t\_value} and \mathrm{t\_space} functions for dashed lines of arbitrary order. In this post we’ll see that, assuming all involved dashed lines to be linear, solving the downcast problem means finding the solution of particular equations, named downcast characteristic equations. In this post we’ll see the characteristic equations that let solve the problem of downcast of \mathrm{t} and \mathrm{t\_value}, while later we’ll see those ones valid for the \mathrm{t\_space} function.
The hypothesis of dashed lines linearity is very important. To understand why, let’s consider how the downcast problem is formulated (Definition T.10 (Downcast function)):
Though this definition is valid for any type of dashed line, when you try to translate the equation f_T(x) = f_U(y) into formulas, you have to know the exact expressions of the f_T and f_U functions (where f can be \mathrm{t}, \mathrm{t\_value} or \mathrm{t\_space}), and they depend on the type of dashed line. So we’ll proceed with the hypothesis to always treat linear dashed lines.
As a matter of principle, one person could try to solve the downcast problem also for non-linear dashed lines, but dashed line theory does not face this matter yet. Another open point is looking for properties of the downcast holding for any dashed line, or for classes of dashed lines wider than linear dashed lines.
General downcast characteristic equations of linear \mathrm{t}
Let’s examine now in detail the problem of the downcast of \mathrm{t} from a dashed line T to one of its dashed sublines U (recall that a downcast function of \mathrm{t} is also a downcast function of \mathrm{t\_value}, so we only talk about \mathrm{t}).
Let’s fix an ordinal x and call t the x-th dash of T. Suppose that t \in U (so that the downcast is possible) and call y its ordinal in U. Then, as we saw in the post The downcast problem, a downcast function of \mathrm{t} from T to U maps the number x into the number y. In order to obtain this function, we have to understand first of all how the numbers x and y are linked. As we said initially, this link consists in an equation, named downcast characteristic equation. Indeed, there isn’t just one characteristic equation, but there are several ones, differing by the form in which they are written, or by the assumptions made on T and U. The most general ones are stated in the following Proposition:
General downcast characteristic equations of \mathrm{t}, for linear dashed lines
Let T) be a linear dashed line and U one of its dashed sublines. Let t be a dash of both, having ordinal x in T and y in U. Let i be the index of the row of t. Then the following equality is true:
x = y + \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U,\ i^{\prime} \lt i} \left \lfloor \frac{\mathrm{t\_value}_U(y)}{n_{i^{\prime}}} \right \rfloor + \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U,\ i^{\prime} \gt i} \left \lfloor \frac{\mathrm{t\_value}_U(y) - 1}{n_{i^{\prime}}} \right \rfloor \tag{4}Or, equivalently:
x = y + \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U} \left \lfloor \frac{\mathrm{t\_value}_U(y) - (i^{\prime} \gt i)}{n_{i^{\prime}}} \right \rfloor \tag{4$^{\prime}$}In particular, if U is of the first order (U = T[i]), the following equality is true
x = y + \sum_{i^{\prime} \lt i} \left \lfloor \frac{n_i y}{n_{i^{\prime}}} \right \rfloor + \sum_{i^{\prime} \gt i} \left \lfloor \frac{n_i y - 1}{n_{i^{\prime}}} \right \rfloor \tag{6}Or, equivalently:
x = y + \sum_{i^{\prime} \neq i} \left \lfloor \frac{n_i y - (i^{\prime} \gt i)}{n_{i^{\prime}}} \right \rfloor \tag{6$^{\prime}$}In this Proposition there are two couples of characteristic equations: (4) and (4′), (6) and (6′). The first couple is the most generic one, valid for any T and U, whereas the equations of the second couple are valid only if U has order one (concerning T there is no hypothesis about the order in neither couple). Within each couple, the two equations differ between them just by the form in which they are written: those with the apostrophe, (4′) and (6′), are a compact form of those ones without it, (4) and (6) respectively, and they adopt the compact notation (i^{\prime} \gt i), that is 1 if the condition inside the parenthesis is true, and false otherwise.
For example the numerator of the fraction in (6′), n_i y - (i^{\prime} \gt i), is n_i y if i^{\prime} \le i, n_i y - 1 if i^{\prime} \gt i, hence you can easily see that (6′) is equivalent to (6); a similar argument holds also for formulas (4) and (4′).
We note that, if U is of the first order, necessarily U = T[i], as stated in the Proposition. In fact the dashed subline U contains the dash t and so must contain its row, that has index i, i.e. it must contain T[i]. But then, since we have supposed it to have order one, it must be just equal to T[i].
Lastly, we note that in formulas (4′) and (6′) the summation indexes run among the indexes of the rows of T not belonging to U (concerning (6) you have to take into account that U = T[i]). Almost the same thing happens in formulas (4) and (6), with the difference that the summation is split into two parts; but in any case, for each summation index, there is a term with the integer part. So the number of terms with the integer part, once summations have been expanded, is always equal to the number of rows of T that are not in U, that is the order of T minus the order of U. In practice, the number of integer parts tells us how many orders we descend by, when we make the downcast from T to U. In the next paragraph we’ll see some examples.
But what do these terms with the integer part represent? They are no more that counts of dashes in a single row, coming from Proposition T.2 (Count of dashes up to a certain value in a linear first order dashed line) and its Corollary (see the following details for an in-depth analysis).
We have said that x is the ordinal of t in T, so in T there exist x dashes less than or equal to t. We can call X this set of dashes and partition it into two subsets, according to the dash membership to U:
- Set Y: dashes of U less than or equal to t
- Set \bcancel{Y}: dashes of T not belonging to U, less than t (if a dash does not belong to U, it cannot be equal to t, because t \in U)
We have called Y the first subset because it contains exactly y dashes. In fact saying that t is the y-th dash of U is equivalent to say that in U there are y dashes less than or equal to t, that just form the set Y.
Analogously, we can ask ourselves how many elements the other subset, \bcancel{Y}, contains. The strategy we’ll adopt for counting them is to divide them by rows, count them row by row, and then sum up all. In this regard, we have to observe that the count of dashes in a row depends on the position of the row itself compared with the row of t. In fact, by Definition T.4 (Dash ordering), the dashes less than or equal to t are those having value less than the value of t or, among those ones with the same value, those belonging to a row with a smaller index. So, in order to count the dashes of \bcancel{Y} by rows, established that t is in row i, we have to proceed this way:
- In rows with index smaller than i (green rows in Figure 1), we have to count all dashes having value less than or equal to the value of t, that we call v. We can call \bcancel{Y}_- this set of dashes (where – stands for “smaller index”).
- In rows with index greater than i (red rows in Figure 1), we have to count all dashes having value less than v. We can call \bcancel{Y}_+ this set of dashes (where + stands for “greater index”).
Now, thanks to Proposition T.2 (Count of dashes up to a certain value in a linear first order dashed line) and its Corollary, we can count the elements of the sets \bcancel{Y}_- and \bcancel{Y}_+. The set \bcancel{Y}_- contains, by Proposition T.2, \left \lfloor \frac{v}{n_{i^{\prime}}} \right \rfloor dashes for each row not in U with index i^{\prime} \lt i. So on the whole we have:
|\bcancel{Y}_-| = \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U,\ i^{\prime} \lt i} \left \lfloor \frac{v}{n_{i^{\prime}}} \right \rfloor \tag{1}The set \bcancel{Y}_+ instead contains, by the Corollary of Proposition T.2, \left \lfloor \frac{v - 1}{n_{i^{\prime}}} \right \rfloor dashes for each row not included in U with index i^{\prime} \gt i. So:
|\bcancel{Y}_+| = \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U,\ i^{\prime} \gt i} \left \lfloor \frac{v - 1}{n_{i^{\prime}}} \right \rfloor \tag{2}Now it remains only to put all elements back together in order to obtain an equation that links x and y:
- The set X of the dashes of T less than or equal to t contains x elements and is partitioned into two subsets, Y and \bcancel{Y}
- The subset Y has y elements
- The subset \bcancel{Y} is in turn partitioned into the subsets \bcancel{Y}_- and \bcancel{Y}_+, the number of elements of which is given by formulas (1) and (2) respectively
Hence
\begin{aligned} x &= |X| \\&= |Y| + |\bcancel{Y}| \\&= |Y| + |\bcancel{Y}_-| + |\bcancel{Y}_+| \\&= y + \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U,\ i^{\prime} \lt i} \left \lfloor \frac{v}{n_{i^{\prime}}} \right \rfloor + \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U,\ i^{\prime} \gt i} \left \lfloor \frac{v - 1}{n_{i^{\prime}}} \right \rfloor \end{aligned}So
x = y + \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U,\ i^{\prime} \lt i} \left \lfloor \frac{v}{n_{i^{\prime}}} \right \rfloor + \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U,\ i^{\prime} \gt i} \left \lfloor \frac{v - 1}{n_{i^{\prime}}} \right \rfloor \tag{3}Now we have an equation that links x and y, that’s what we were looking for. But this equation does not let compute y yet (thus solving the downcast problem), because it still contains the unknowns v and i, that are the value and the row index of t. However, i is not a real unknown, because it can be computed by applying some theorems, as we’ll see in the next posts. Assuming to apply these theorems we can regard i as already known, and think only about v. It, differently from i, is a true unknown, also because, if we knew v in addition to i, we could directly compute t = (i, \frac{v}{n_i}) and so the downcast would be useless, as its goal is just the computation of the dash t. So, if we want to solve the downcast problem, we have to cancel the unknown v from the equation (3) somehow. A way to do that is to express this unknown as a function of the others. In particular, it’s possible to express v as a function of y; in fact, being v the value of t, which is the y-th dash of U, we’ll have that v = \mathrm{t\_value}_U(y). By placing this into (3) we’ll have:
x = y + \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U,\ i^{\prime} \lt i} \left \lfloor \frac{\mathrm{t\_value}_U(y)}{n_{i^{\prime}}} \right \rfloor + \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U,\ i^{\prime} \gt i} \left \lfloor \frac{\mathrm{t\_value}_U(y) - 1}{n_{i^{\prime}}} \right \rfloor \tag{4}We can express this equation in a more compact form by using Definition T.12, with C := i^{\prime} \gt i:
x = y + \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U,\ i^{\prime} \neq i} \left \lfloor \frac{\mathrm{t\_value}_U(y) - (i^{\prime} \gt i)}{n_{i^{\prime}}} \right \rfloorNow the two summations in (4), the first for the indexes greater than i and the second for the lower ones (still among the indexes which are not considered in U), have been joined into a single summation, gathering all the indexes, both greater and lower.
We note that now the condition i^{\prime} \neq i has become redundant, because if T[i^{\prime}] \nsubseteq U then i^{\prime} is not any of the row indexes of U, even i. So the previous formula can be rewritten more simply as follows:
There is a particular case in which equations (4) and (4′) assume a particularly simple form: it’s when the dashed subline U is of the first order. As we already noted, this is equivalent to say that U = T[i]. In this case, being t the y-th dash of U, its value must be v = n_i y. Putting this into (4), we’ll have
x = y + \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U,\ i^{\prime} \lt i} \left \lfloor \frac{n_i y}{n_{i^{\prime}}} \right \rfloor + \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U,\ i^{\prime} \gt i} \left \lfloor \frac{n_i y - 1}{n_{i^{\prime}}} \right \rfloor \tag{5}Now the conditions T[i^{\prime}] \nsubseteq U,\ i^{\prime} \lt i and T[i^{\prime}] \nsubseteq U,\ i^{\prime} \gt i can be simplified, because as U = T[i] we have that T[i^{\prime}] \nsubseteq U \Leftrightarrow T[i^{\prime}] \nsubseteq T[i] \Leftrightarrow i^{\prime} \neq i, but the latter condition is redundant because it’s included into the conditions i^{\prime} \lt i and i^{\prime} \gt i, so (5) becomes simply:
x = y + \sum_{i^{\prime} \lt i} \left \lfloor \frac{n_i y}{n_{i^{\prime}}} \right \rfloor + \sum_{i^{\prime} \gt i} \left \lfloor \frac{n_i y - 1}{n_{i^{\prime}}} \right \rfloor \tag{6}Or, in a more compact form:
x = y + \sum_{i^{\prime} \neq i} \left \lfloor \frac{n_i y - (i \lt i^{\prime})}{n_{i^{\prime}}} \right \rfloor \tag{6$^{\prime}$}Downcast characteristic equations of linear \mathrm{t}: particular cases
Now let’s see some particular cases of the general downcast characteristic equations, that are in the statement of Proposition T.4.
Let’s start from the case when T has order 2. In this case the dashed subline U must be of order one (unless you want to consider the improper dashed subline U = T, but in that case the downcast is trivial because it would be x = y). So we can start from formulas (6) and (6′), specific for this case. Concerning formula (6), let’s consider the cases i = 1 and i = 2 separately:
- If i = 1, there is no index i^{\prime} \lt i, so the first summation is empty, while in the second one the only possible value for i^{\prime} is 2;
- If i = 2, there is no index i^{\prime} \gt i, so the second summation is empty, while in the first one the only possible value for i^{\prime} is 1.
So equation (6) becomes:
- If i = 1: x = y + \left \lfloor \frac{n_1 y - 1}{n_2} \right \rfloor
- If i = 2: x = y + \left \lfloor \frac{n_2 y}{n_1} \right \rfloor
If, on the other hand, we start from formula (6′), we’ll obtain the compact form x = y + \left \lfloor \frac{n_i y - (j \gt i)}{n_j} \right \rfloor, where j is the unique index different from i: j = 2 if i = 1 and, conversely, j = 1 if i = 2. We can express this constraint between i and j with the expression \{i, j\} = \{1, 2\}. Thus in fact we are telling that i and j, taken together, must form the set \{1, 2\}, so:
- if i = 1, in order to form the set \{1, 2\}, j must be 2
- if i = 2, for the same reason j must be 1
So for second order dashed lines Proposition T.4 becomes:
Downcast characteristic equations of \mathrm{t} from the second to the first order, for linear dashed lines
Let T be a linear dashed line of the second order and U one of its dashed sublines of the first order. Let t be a dash of both, having ordinal x in T and y in U. Let i be the index of the row of t. Then the following equalities are true:
x = \begin{cases} y + \left \lfloor \frac{n_1 y - 1}{n_2} \right \rfloor & \text{if } i = 1\\ y + \left \lfloor \frac{n_2 y}{n_1} \right \rfloor & \text{if } i = 2 \end{cases} \tag{7}Equivalently, with j such that \{i, j\} = \{1, 2\}:
x = y + \left \lfloor \frac{n_i y - (j \gt i)}{n_j} \right \rfloor \tag{7$^{\prime}$}Let’s see now what happens if T is of order three. In this case the dashed subline U may be of the first or the second order.
If U is of the first order, we can proceed like before, obtaining the following Corollary:
Downcast characteristic equations of \mathrm{t} from the third to the first order, for linear dashed lines
Let T be a linear dashed line of the third order and U one of its dashed sublines of the first order. Let t be a dash of both, having ordinal x in T and y in U. Let i be the index of the row of t. Then the following equalities are true:
x = \begin{cases} y + \left \lfloor \frac{n_1 y - 1}{n_2} \right \rfloor + \left \lfloor \frac{n_1 y - 1}{n_3} \right \rfloor & \text{if } i = 1\\ y + \left \lfloor \frac{n_2 y}{n_1} \right \rfloor + \left \lfloor \frac{n_2 y - 1}{n_3} \right \rfloor & \text{if } i = 2\\ y + \left \lfloor \frac{n_3 y}{n_1} \right \rfloor + \left \lfloor \frac{n_3 y}{n_2} \right \rfloor & \text{if } i = 3 \end{cases} \tag{8}Equivalently, with j and k such that \{i, j, k\} = \{1, 2, 3\}:
x = y + \left \lfloor \frac{n_i y - (j \gt i)}{n_j} \right \rfloor + \left \lfloor \frac{n_i y - (k \gt i)}{n_k} \right \rfloor \tag{8$^{\prime}$}Note that formula (8′) is not ambiguous, though the condition \{i, j, k\} = \{1, 2, 3\} does not exactly define what j and k are. In fact, if for example i = 1, in order to have \{i, j, k\} = \{1, 2, 3\}, it may be j = 2 and k = 3, or k = 2 and j = 3. In the first case, substituting in (8′), we’ll have:
x = y + \left \lfloor \frac{n_1 y - (2 \gt 1)}{n_2} \right \rfloor + \left \lfloor \frac{n_1 y - (3 \gt 1)}{n_3} \right \rfloorWhile in the second case we’ll have:
x = y + \left \lfloor \frac{n_1 y - (3 \gt 1)}{n_3} \right \rfloor + \left \lfloor \frac{n_1 y - (2 \gt 1)}{n_2} \right \rfloorBut it’s the same equation, because only the order of addends is different. This happens because, in (8′), the expression \left \lfloor \frac{n_i y - (j \gt i)}{n_j} \right \rfloor + \left \lfloor \frac{n_i y - (k \gt i)}{n_k} \right \rfloor is symmetrical with respect to j and k, i.e. it does not change if you swap the two symbols.
The fact that (8′) is symmetrical with respect to j and k comes directly from the general formula (6′), from which (8′) is derived by assuming that T is of the third order. The expression \left \lfloor \frac{n_i y - (j \gt i)}{n_j} \right \rfloor + \left \lfloor \frac{n_i y - (g \gt i)}{n_k} \right \rfloor that you can see in (8′) is the expanded form of the following summation in (6′):
\sum_{i^{\prime} \neq i} \left \lfloor \frac{n_i y - (i \lt i^{\prime})}{n_{i^{\prime}}} \right \rfloor \tag{9}Actually in (8′) we are simply calling j and k the two possible values of the summation index i^{\prime}, that are the two indexes different from i. So swapping j and k means summing up the addends of (9) into a different order, but by the commutative property this doesn’t affect the final result.
We also note that in formula (8), contrary to (7), there are two integer parts and not one, because this time we are descending by two orders (from the third to the first) (see the previous note).
Suppose now the dashed subline U to be of the second order, that is U = T[i, j] for some j (i is fixed and it’s always the index of the row of the dash t). In this case we cannot start from formulas (6) and (6′), valid only if U is of the first order, but we have to apply formulas (4) and (4′). Let’s consider in particular the compart formula (4′).
Having established that U = T[i, j], there is only one index i^{\prime} that does not identify a row of U: we can call it k, with the usual condition \{i, j, k\} = \{1, 2, 3\} (where k this time is uniquely given: for example, if (i, j) = (1, 2), then k = 3). So the summation \sum_{i^{\prime}\ |\ T[i^{\prime}] \nsubseteq U} is reduced to a single element, with i^{\prime} = k, and the formula becomes:
Here we have again only one integer part, because we are descending by only one order, from the third to the second.
Starting from this formula, if you want, you can obtain the specific formulas for every possible choice of i and j: we state them in the following Corollary.
Downcast characteristic equations of \mathrm{t} from the third to the second order, for linear dashed lines
Let T) be a linear dashed line of the third order and U = T[i, j] one of its dashed sublines of the second order. Let t be a dash of both, having ordinal x in T and y in U. Let i be the index of the row of t. Then the following equalities are true:
x = \begin{cases} y + \left \lfloor \frac{\mathrm{t\_value}_U(y) - 1}{n_3} \right \rfloor & \text{if } (i, j) = (1, 2) \text{ or } (i, j) = (2, 1)\\ y + \left \lfloor \frac{\mathrm{t\_value}_U(y) - 1}{n_2} \right \rfloor & \text{if } (i, j) = (1, 3) \\ y + \left \lfloor \frac{\mathrm{t\_value}_U(y)}{n_2} \right \rfloor & \text{if } (i, j) = (3, 1) \\ y + \left \lfloor \frac{\mathrm{t\_value}_U(y)}{n_3} \right \rfloor & \text{if } (i, j) = (2, 3) \text{ or } (i, j) = (3, 2) \end{cases} \tag{10}Equivalently, with k such that \{i, j, k\} = \{1, 2, 3\}:
x = y + \left \lfloor \frac{\mathrm{t\_value}_U(y) - (k \gt i)}{n_k} \right \rfloor \tag{10$^{\prime}$}