6. The downcast problem

Prerequirement: First order linear dashed lines

As you can realize from the previous posts, the difficulty of computing \mathrm{t}, \mathrm{t\_value} and \mathrm{t\_space} functions, increases as the order of the dashed line does.
In the previous post we saw that the formulas for computing these functions for first order dashed lines are very simple, in particular those ones for \mathrm{t} and \mathrm{t\_value} functions descend directly from the definition of linear dashed line. In higher order dashed line things get complicated. In fact, the dashed line function is defined in a different way for each row index (like in formula (5) in the post Dashed line, dashed and spaces: some definitions and simple properties), whereas for example the \mathrm{t\_value} function still returns the value of the n-th dash on the whole, that is combining rows according to the ordering defined by Definition T.4 (Dash ordering).
The situation is similar for the \mathrm{t} and \mathrm{t\_space} functions: it’s very simple to compute them for first order dashed lines, while for higher order ones their computation is more difficult, being functions concerning the whole dashed line and not its single rows.

The main strategy for solving this problem consists, as usually people do in mathematics, in reducing to a simpler case: the computation of one of the functions \mathrm{t}, \mathrm{t\_value} or \mathrm{t\_space} for a second order dashed line is reduced to the computation of the same function for a first order dashed line; for a third order dashed line, you reduce to the second order which in turn is reduced to the first order, and so on: the computation for a generic order is done descending from an order to another, till the first order, where there are no difficulties.

At the basis of this descending mechanism from an order to another, there is the concept of dashed subline (Definition T.6). Starting from a dashed line of order k and excluding one of its rows, a dashed subline of order k - 1 in obtained. Being a proper dashed subline, its dashes constitute a proper subset of those of the original dashed line. This entails two things:

  • The x-th dash of the original dashed line can belong to the dashed subline or not;
  • In the case it belongs to the dashed subline, with respect to the subline it will no longer be the x-th, but the y-th, for some y which generally is different from x.

Let’s compare the dashed line (3, 4) with its dashed subline (3). In this case in the passage to the subline the dashes in the second row are lost, whereas those of the first row are kept, but generally they change ordinal:

Figure 1: change of dash ordinals when passing from a dashed line to one of its proper dashed sublines

So the strategy for computing \mathrm{t}_T(x) for a dashed line T of order k \gt 1 is the following:

  1. Finding a proper dashed subline of T, U, containing the dash to compute
  2. Computing the dash ordinal in U, so finding a number y such that \mathrm{t}_T(x) = \mathrm{t}_U(y)
  3. Computing \mathrm{t}_U(y)

The last passage is the computation of the \mathrm{t} function for the dashed line U which has order less than k, at most k - 1. At this point, if U has order 1, then we can directly compute \mathrm{t}_U(y); otherwise by the same mechanism we can find a proper dashed subline of U, V, such that t_U(y) = t_V(z) for some z, so descending to an even lower order, and so on, till arriving, sooner or later, to the first order.

Concerning step 2, in the next posts we’ll see we can find a function that, given T and its dashed subline U, maps any x to the corresponding y, that is mapping the ordinal of a dash of T to the ordinal of the same in U, as long as it belongs to U. Such a function is called a downcast function of \mathrm{t} from T to U.

Let’s consider the dashed line T = (3, 4, 5) and focus our attention to its seventh dash. As we can see in Figure 2, this dash is the second of the third row, that is \mathrm{t}_T(7) = (3, 2). But if we consider the dashed subline U = T[2,3] = (4, 5), the dash (3, 2) no longer has ordinal 7, but 4. Again, we can consider the dashed subline V = U[3] = T[3] = (5), in which the starting dash has ordinal 2:

Figure 2: ordinal change of a dash of the dashed line (3, 4, 5), descending till a first order dashed subline

So, summarizing, \mathrm{t}_T(7) = \mathrm{t}_U(4) = \mathrm{t}_V(2) = (3, 2). In these passages we applied:

  • A method for establishing that \mathrm{t}_T(7) \in U = T[2, 3] (an exclusively graphical method for now)
  • A downcast function of \mathrm{t} from T to U, that starting from the ordinal 7 computes the ordinal 4
  • A method for establishing that \mathrm{t}_U(4) \in V = U[3] = T[3] (still of graphical kind)
  • A downcast function of \mathrm{t} from U to V, that starting from the ordinal 4 computes the ordinal 2
  • The \mathrm{t} function for the first order dashed line V: being 3 the index of the unique row of V, by Proposition T.1 (Linear first order \mathrm{t} and \mathrm{t\_value} functions) we have that \mathrm{t}_V(2) = (3, 2).

We can schematically describe this procedure as follows:

T \longrightarrow T[2,3] \longrightarrow T[3]

As an alternative, using other dashed sublines, we could obtain the same final result in the following way:

T \longrightarrow T[1,3] \longrightarrow T[3]

Or, more quickly, we can think about doing a downcast directly from T to its first order dashed subline T[3], passing directly from the ordinal 7 to the ordinal 2:

T \longrightarrow T[3]

So, in a downcast we do not necessarily descend of one order at a time. Though, the downcast functions which let us descend of more than one order in a single step can be more complex, or subject to more limitations (we’ll analyze this matter in the next posts).

We can repeat the argument of downcast also for the \mathrm{t\_value} function.
Given a dashed line T and a positive integer x, we know that by definition the x-th dash of T has value v := \mathrm{t\_value}_T(x). So, given a proper dashed subline of T, U, we can ask ourselves if also U contains a dash with value v and, in positive case, what is a number y such that \mathrm{t\_value}_T(x) = \mathrm{t\_value}_U(y). If we find a function that, given T and U, maps a generic x to the corresponding y, it would be a downcast function of \mathrm{t\_value} from T to U.
But, if you think about it, we already know such a function, and it’s the same of the downcast of \mathrm{t}. Let’s try to understand why. Let’s fix a positive integer x, call t the x-th dash of T, and indicate with v its value, that is \mathrm{t\_value}_T(x). We’ll have that:

  • If t \in U, we can apply a downcast function of \mathrm{t} for the ordinal x. This function will map x to a some number y, indicating that t is the y-th dash of U;
  • But, since we’re always talking about the same dash, its value is always v either if we see it in T or in U, that is T(t) = U(t);
  • Then \mathrm{t\_value}_T(x) = T(t) = U(t) = \mathrm{t\_value}_U(y).

In other terms, reading the ends of the equality at the third point, we have that the downcast function of \mathrm{t} of the first point, which maps x to y, is also a downcast function of \mathrm{t\_value}, still from T to U, because these x and y satisfy the condition \mathrm{t\_value}_T(x) = \mathrm{t\_value}_U(y).

In the previous example we saw that, with T = (3, 4, 5) and U = T[2, 3], \mathrm{t}_T(7) = \mathrm{t}_U(4), so a downcast function of \mathrm{t} from T to U maps the ordinal 7 to the ordinal 4. Now let’s try to do the same thing with the \mathrm{t\_value} function, looking for a number y such that

\mathrm{t\_value}_T(7) = \mathrm{t\_value}_U(y)

We saw that the seventh dash of T, \mathrm{t}_T(7), is (3, 2). We can call this dash \mathrm{t} and write:

\mathrm{t\_value}_T(7) = T(\mathrm{t}_T(7)) = T(t) = T(3, 2) = 10

But we saw that t is the fourth dash of U: in formulas, t = \mathrm{t}_U(4). Then:

\mathrm{t\_value}_U(4) = U(\mathrm{t}_U(4)) = U(t) = U(3, 2) = 10

So:

\mathrm{t\_value}_T(7) = 10 = \mathrm{t\_value}_U(4)

that is, a downcast function of \mathrm{t\_value} from T to U maps the ordinal 7 to the ordinal 4 too.
The same argument can be repeated for any x, not just x = 7: generally speaking, a downcast function of \mathrm{t} is also a downcast function of \mathrm{t\_value}, for the same couple dashed line-subline.

Being the problem of downcast of \mathrm{t\_value} reducible to the one of \mathrm{t}, dashed line theory is focused to the latter, though the downcast of \mathrm{t\_value} would deserve greater attention.

We said that a downcast function of \mathrm{t} is also a downcast function of \mathrm{t\_value}, but not all downcast functions of \mathrm{t\_value} are downcast functions of \mathrm{t}. Let’s try to understand why. Let’s consider the dashed line T = (3, 4, 5) and its dashed subline V^{\prime} = T[1, 2] = (3, 4):

Figure 3: the dashed line T = (3, 4, 5) and its dashed subline V’ = T[1, 2] = (3, 4)

Let’s consider the downcast T \longrightarrow V^{\prime}. We ask ourselves: what’s the result of a downcast function of \mathrm{t\_value} from T to V^{\prime}, for x = 8? In other terms, we ask ourselves what is a number y such that

\mathrm{t\_value}_T(8) = 12 = \mathrm{t\_value}_{V^{\prime}}(y) \tag{1}

Note that in V^{\prime} there are two dashes with value 12: (1, 4) e (2, 3), respectively the sixth and the seventh ones. So (1) has two solutions, y = 6 and y = 7:

Figure 4: A downcast function of t_value from (3, 4, 5) to (3, 4) can map the number 8 to the number 6 or the number 7
\mathrm{t\_value}_T(8) = 12 = \mathrm{t\_value}_{V^{\prime}}(6) = \mathrm{t\_value}_{V^{\prime}}(7)

So a downcast function of \mathrm{t\_value} from T to V^{\prime}, for x = 8, can return either 6 or 7. But of course a function can assume only one value at a time, so in this case there exist at least two downcast functions: a function f such that f(8) = 6 and a function g such that g(8) = 7 (the expression at least is necessary because the same situation could happen for other values of x, and in this case there would be a different function for each combination of possible values). The function g behaves, for x = 8, like a downcast function of \mathrm{t}, because the eighth dash of T is the sixth of V^{\prime}. But also the seventh dash of V^{\prime}, though not coinciding with the eighth of T, has the same value: that’s the reason why function f is a downcast function of \mathrm{t\_value}, but not of \mathrm{t}.

From this example it’s clear that, generally, the existance of downcast functions of \mathrm{t\_value} that are not downcast functions of \mathrm{t}, derives from the presence, in the dashed line and the dashed subline taken into consideration, of different dashes having the same value. This aspect of dashed line theory hasn’t been studied in a general way yet: so it constitutes an open point.

The term downcast comes from the world of programming languages. In this context the term indicates, generally, a conversion of the type of a variable, from a more general type to a more specific one.

After having analyzed the problem of downcast for the \mathrm{t} and \mathrm{t\_value} functions, it remains to be seen what happens for the \mathrm{t\_space} function. In this last case the substantial difference is that, while not all the dashes of a dashed line belong to one of its proper dashed sublines (and, as a consequence, also their values are not necessarily values of dashed subline dashes), we cannot say the same thing about spaces. In fact, as a consequence of the Definition of space, all the spaces of a dashed line are also spaces of any of its dashed subline, whereas the converse is not true: it’s just the opposite of what happens for dashes. In other terms, in the transition from a dashed line to one of its dashed sublines, generally dashes decrease, while spaces increase. For example, the dashed line V = (3, 4) of Figure 4:

  • has less dashed than T = (3, 4, 5), because it does not have all those of the third row;
  • has more spaces: in fact all the spaces of T (1, 2, 7, 11, 13, 14, 17, …) can be found also in V, in addition 5 and 10 are spaces of V but not of T.

However, the fact that a dashed subline has simultaneously “less dashes” and “more spaces” appears rather natural, since intuitively dashes occupy positions that, in their absence, become spaces.

Coming back to the difference among the \mathrm{t}, \mathrm{t\_value} and \mathrm{t\_space} functions, we’ll say that the \mathrm{t\_space} function is down-conservative indicating that it preserves spaces (optionally adding some other ones) when passing from a dashed line to one of its dashed sublines, whereas the \mathrm{t} and \mathrm{t\_value} functions are not down-conservative, bacause dashes and their values are not preserved in dashed sublines, rather generally they are lost.

For being down-conservative, the \mathrm{t\_space} function makes the downcast operation easier with respect to the other two functions: we don’t have to ask ourselves, as we did for dashes, if the space of the initial dashed line belongs to the dashed subline too: we already know this is true, so we just have to find the downcast function.

With reference to the dashed lines T, U and V of Figure 1, we see that the fourth space of T is 11, and it corresponds to the seventh space of U and the ninth of V:

Figure 5: downcast of t_space from (3, 4, 5) to (4, 5) and from the latter to (5)

In formulas:

\mathrm{t\_space}_T(4) = 11 = \mathrm{t\_space}_U(7) = \mathrm{t\_space}_V(9)

So a downcast function of \mathrm{t\_space} from T to U maps 4 to 7, and one from U to V maps 7 to 9. Incidentally, we note that it’s not by chance that the space ordinal increases as we descend into dashed sublines: a dashed subline generally contains more spaces than the dashed line it comes from, and so, being \mathrm{t\_space} increasing, in order to reach the same space a greater ordinal has to be used generally.

We recap what we have seen so far into the following definitions:

Downcast function

Let f_T be a function defined on \mathbb{N}^{\star}, the definition of which depends on a dashed line T, like \mathrm{t}_T, \mathrm{t\_value}_T and \mathrm{t\_space}_T. Let U be a dashed line and V one of its dashed sublines.
Let d: \mathbb{N}^{\star} \rightarrow \mathbb{N}^{\star} be a function such that:

\exists y\text{ such that }f_T(x) = f_U(y) \implies d(x) = y \tag{2}

then d is called a downcast function of f from T to U. The operation consisting in applying such a function, verifying the existence of the y of (2), is called downcast from T to U. If y does not exist, we say that the downcast of f from T to U is not possible for x.

Down-conservative function

Let f_T be a function defined on \mathbb{N}^{\star}, the definition of which depends on a dashed line T, like \mathrm{t}_T, \mathrm{t\_value}_T and \mathrm{t\_space}_T. Let U be a dashed line and V one of its dashed sublines. If the set of possible values assumed by f_V is a subset of those ones assumed by f_U, i.e. if

f_V(\mathbb{N}^{\star}) \subseteq f_U(\mathbb{N}^{\star})

Then the f_U function is said to be down-conservative. In addition, consistently with the definitions of \mathrm{t}, \mathrm{t\_value} and \mathrm{t\_space} (Definitions T.7, T.8 and T.9):

  • If f_U is down-conservative for every U, the function f is said to be down-conservative.
  • If there exists a dashed line U such that f_U is not down-conservative, then the function f is said to be not down-conservative.

With reference to the dashed line T = (3, 4, 5) and its dashed subline U = (3, 4) shown in Figure 5, with f = \mathrm{t\_space}, we have that

\mathrm{t\_space}_T(\mathbb{N}^{\star}) = \mathrm{t\_space}_T(\{1, 2, 3, 4, 5, 6, 7, \ldots\}) = \{1, 2, 7, 11, 13, 14, 17, \ldots\}
\mathrm{t\_space}_U(\mathbb{N}^{\star}) = \mathrm{t\_space}_T(\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 \ldots\}) = \{1, 2, 3, 6, 7, 9, 11, 13, 14, 17, 18, \ldots\}

So, as expected by Definition T.11:

\mathrm{t\_space}_T(\mathbb{N}^{\star}) = \{1, 2, 7, 11, 13, 14, 17, \ldots\} \subseteq \{1, 2, 3, 6, 7, 9, 11, 13, 14, 17, 18, \ldots\} = \mathrm{t\_space}_U(\mathbb{N}^{\star})

Since this happens for every dashed subline U, we say that \mathrm{t\_space}_T is down-conservative. Indeed this behaviour does not depend even on the starting dashed line T, so we say that the function \mathrm{t\_space} is down-conservative.

Note that the terminology “the f function is down-conservative” is inaccurate, because f is not technically a function, but it becomes a function when a dashed line is specified in the subscript. Though it turns out to be simpler to say, for example, “the \mathrm{t\_space} function is down-conservative” than saying “the \mathrm{t\_space}_T function is down-conservative for every T“.

We already remarked that the following property is true:

Down-conservativity of \mathrm{t}, \mathrm{t\_value} and \mathrm{t\_space} functions

Function \mathrm{t\_space} is down-conservative, whereas \mathrm{t} and \mathrm{t\_value} are not.

Finally, analyzing the definition of downcast function in detail, we can note that it’s not completely deterministic, but it is only for the xs corresponding to dashes/values/spaces that belong to the dashed subline: for the other xs the definition does not specify how the function has to behave. This degree of freedom lets, generally, different possible downcast functions exist, for the same couple dashed line-subline.

Considering the downcast of \mathrm{t} from T = (3, 4) to U = (3) shown in Figure 1, by Definition T.10 (Downcast function), a downcast function is defined for all the xs such that:

\exists y \text{ such that } \mathrm{t}_T(x) = \mathrm{t}_U(y)

But not always this y exists, because the \mathrm{t} function is not down-conservative. In detail, if d is a downcast function, we’ll have that:

  • For x = 1, \mathrm{t}_T(x) = (1, 1). It’s a dash of the first row, the only one of the dashed line U, so it belongs to U. We have that \mathrm{t}_T(x) = (1, 1) = \mathrm{t}_U(1), so d(1) = 1.
  • For x = 2, \mathrm{t}_T(x) = (2, 1). It’s a dash of the second row, hence not belonging to U. So the value d(2) is not defined.
  • For x = 3, \mathrm{t}_T(x) = (1, 2) \in U. In U we have that (1, 2) = \mathrm{t}_U(2), so d(3) = 2.
  • For x = 4, \mathrm{t}_T(x) = (2, 2) \notin U. So the value d(4) is not defined.
  • For x = 5, \mathrm{t}_T(x) = (1, 3) \in U. In U we have that (1, 3) = \mathrm{t}_U(3), so d(5) = 3.

Summarizing, analyzing the xes from 1 to 5, by definition of downcast function the following values are defined:

d(1) = 1, d(3) = 2, d(5) = 3 \tag{3}

whereas the values d(2) and d(4) are not defined. This means that this d is not uniquely determined, but any function satisfying the constraints (3) is a valid downcast function (or at least it is for x = 1, \ldots, 5), no matter what d(2) and d(4) are. For example, two valid downcast functions are the following:

  • d(1) = 1, d(2) = 1, d(3) = 2, d(4) = 2, d(5) = 3
  • d(1) = 1, d(2) = 2, d(3) = 2, d(4) = 5, d(5) = 3
  • d(1) = 1, d(2) = 34, d(3) = 2, d(4) = 125, d(5) = 3

But it’s clear that the possible downcast functions are infinitely many, because we can imagine any value for d(2) and d(4).

Generally, the following Property can be proved:

Unicity of the downcast function

Let f_T be a function defined on \mathbb{N}^{\star}, the definition of which depends on a dashed line T, like \mathrm{t}_T, \mathrm{t\_value}_T and \mathrm{t\_space}_T. Let U be a dashed line and V be one of its dashed sublines.
There exists a unique downcast function of f from U to V if the number y of formula (2) of the definition of downcast exists and is unique for every x:

\forall x \exists! y \text{ such that } f_U(x) = f_V(y)

In particular:

  • if the function f_U is down-conservative, y exists for every x
  • if y exists, it’s unique if the f_V function is injective

As a consequence, there always exists a unique downcast function of f, for every couple dashed line-subline UV, if f is both down-conservative and injective: it’s just the case of the \mathrm{t\_space} function.

Leave a Reply

Your email address will not be published.