Prerequirement: From a problem about jogging to dashed lines
In the previous post we saw that one of the main problems of dashed line theory is computing the \mathrm{t}, \mathrm{t\_value} and \mathrm{t\_space} functions. Now we’ll see how to make this calculation for linear first order dashed lines, whereas the next posts will be devoted to higher order dashed lines. We take into consideration linear dashed lines because, besides being rather simple, they are also the most important, being directly related to prime numbers (see for example Dashed lines and prime numbers).
Linear first order \mathrm{t} and \mathrm{t\_value} functions
The formulas for computing linear first order \mathrm{t} and \mathrm{t\_value} functions (that is \mathrm{t}_T and \mathrm{t\_value}_T, where T is linear and of the first order) descend directly from the main definitions of dashed line theory. Let’s see how.
First of all a first order dashed line T has only one row, which we can suppose to have index 1. So, being a linear dashed line, we know it’s a function like
where we called n_1 the unique component of the dashed line. From the expression of the T function it’s clear that the dash values are all and only the non-negative multiples of n_1.
For example, with n_1 = 3 we have the following dashed line, of which we show both the dashes in mathematical form and their ordinals, for x \gt 0:
As it’s clear in the example, in general the x-th dash is (1, x) and has value n_1 \cdot x. In general, assuming a generic index instead of 1, the following Proposition is true:
Linear first order \mathrm{t} and \mathrm{t\_value} functions
Let T = (n_i) be a linear first order dashed line. Then:
Since T has only one row of index i, all its dashes are of kind (i, x). Applying the ordering (Definition T.4 (Dash ordering)) on these dashes for x \gt 0, you can find that (1, 1) \lt (1, 2) \lt (1, 3) \lt \ldots. So the x-th dash, that is \mathrm{t}_T(x) by Definition T.7 (\mathrm{t} function), is (i, x).
Concerning \mathrm{t\_value}_T(x), by Definition T.8 (\mathrm{t\_value} function) we have that \mathrm{t\_value}_T(x) = T(\mathrm{t}_T(x)). Substituting the formula for the \mathrm{t} function we have just obtained, this is in turn equal to T(i, x) = n_i \cdot x.
Count of dashes up to a certain value
A simple but fundamental property of linear first order dashed lines is the count of the dashes the value of which is less than or equal to a certain natural number v (apart from the dash with value 0, as formulas assume a simpler form if we do not consider it). For counting these dashes we can count their values, that is, assuming i=1, the positive multiples of n_1 less than or equal to v. In fact in a first order dashed line two dashes cannot have the same value (formally, there exists the bijection n_1 \cdot x \leftrightarrow (1, x) between dashes and their values), so each value identifies a dash univocally. For example, in Figure 1 the values 3 and 6 univocally identify the dashes (1, 1) and (1, 2) respectively, so the number of dashes having positive value up to 6 (two dashes) is equal to the number of positive multiples of 3 less than or equal to 6.
It can be proved that the number of positive multiples of n_1 less than or equal to v in turn is given by the integer part of v divided by n_1, so in general we can state the following Proposition:
Count of dashes up to a certain value in a linear first order dashed line
Let T = (n_i) be a linear first order dashed line. The number of dashes of T with positive value less than or equal to a certain natural number v is given by:
Let’s try to give an intuitive explanation for the reason why the number of multiples of n_i less than or equal to v is indeed \left \lfloor \frac{v}{n_i} \right \rfloor:
- If v is a multiple of n_i, the number of multiples of n_i less than or equal to v is \frac{v}{n_i} = \left \lfloor \frac{v}{n_i} \right \rfloor. For example 2 = \frac{6}{3} = \left \lfloor \frac{6}{3} \right \rfloor is the number of multiples of 3 less than or equal to 6).
- If v is not a multiple of n_i, the number we are looking for is the same we would obtain by decreasing v one unity at a time, till arriving to a multiple of n_1. For example, 8 and 7 are not multiples of 3, whereas 6 is, so searching the mulyiples of 3 less than or equal to 8, to 7 or 6 is the same thing. So a formula that computes the number of multiples of n_i less than or equal to x, if we call it f(x), has to be such that f(8) = f(7) = f(6). But this is just the behaviour of the function f(x) = \left \lfloor \frac{x}{3} \right \rfloor, in fact \left \lfloor \frac{8}{3} \right \rfloor = \left \lfloor \frac{7}{3} \right \rfloor = \left \lfloor \frac{6}{3} \right \rfloor = \frac{6}{3} = 2.
It’s worth observing that the dashes with value less than v are those with value less that or equal to v - 1, obtainable still by the previous Proposition. So we have the following Corollary:
Count of dashes having value less than a certain number in a linear first order dashed line
Let T = (n_i) be a linear first order dashed line. The number of dashes of T with positive value less than a certain natural number v is given by:
Linear first order \mathrm{t\_space} function
The computation of the \mathrm{t\_space} function for a linear first order dashed line is not as immediate as for the \mathrm{t} and \mathrm{t\_value} functions, but we can achieve it starting from a simple argument.
Suppose to have a linear first order dashed line T = (n_1) and let s := \mathrm{t\_space}_T(x). This means that:
- Among the first s positive columns of T there are x spaces, the last of which is just s.
- The s - x columns which are not spaces must contain by definition at least one dash, but since the dashed line has order one, they contain only one dash.
The dashes identified in the second point are all the ones with positive value less than or equal to s, or also, since s is a space, the ones with positive value less than s. So their number, if on one side is by construction s - x, on the other side, by Proposition T.2 and its Corollary, is given respectively by the formulas \left \lfloor \frac{s}{n_1} \right \rfloor and \left \lfloor \frac{s - 1}{n_1} \right \rfloor. So we can write the equation:
named characteristic equation of linear first order \mathrm{t\_space} (with i = 1).
It can be proved that an integer s satisfies equation (1) if and only if s = \mathrm{t\_space}_T(x) (so far we proved only that if s = \mathrm{t\_space}_T(x), then s satisfies (1), not the converse). The details of this proof are in Teoria dei tratteggi (Dashed line theory), Proposition 8.1 pages 200-202 (in Italian).
It can be also proved that (1) is equivalent to the single equation s - x = \left \lfloor \frac{s}{n_1} \right \rfloor, combined with the condition that s is a space. Indeed, the fact that s is a space means that \left \lfloor \frac{s}{n_1} \right \rfloor = \left \lfloor \frac{s - 1}{n_1} \right \rfloor, as stated by the following Proposition:
Spaces characterization of a first order linear dashed line by means of an equation with the integer part
Let T = (n_1) be a first order linear dashed line. For any natural number s the following equivalence is true:
We propose two proofs: one more intuitive and one more technical. The first is simpler, but it’s instructive to know both, for understanding how sometimes, if you look at things by the right perspective, you can save a lot of calculations.
More intuitive proof
If s is a space of T, it isn’t the value of a dash, so the number of dashed with value less than or equal to s is equal to the number of dashes the value of which is less than s. This, by Proposition T.2 and its Corollary, is immediately translated into the condition \left \lfloor \frac{s}{n_1} \right \rfloor = \left \lfloor \frac{s - 1}{n_1} \right \rfloor.
Conversely, if \left \lfloor \frac{s}{n_1} \right \rfloor = \left \lfloor \frac{s - 1}{n_1} \right \rfloor, by the cited Proposition and Corollary, it means that the dashes having value less than s are as many as those ones having value less than or equal to s. Then s cannot be a dash value, because, if it was, the two counts would not coincide (the count of dashes with value less than or equal to s would be one more than the count of the others). So s must be a space.
More technical proof
In order to prove the Proposition we can resort to Property 2.21 at page 65 of Teoria dei tratteggi (Dashed line theory), in Italian. Letting, in the statement of this Property, in the particular case of k := 1, a := s - 1 and b := n_1, we have that:
But in the right side expression, in the statement we have to prove, we say that \left \lfloor \frac{s}{n_1} \right \rfloor = \left \lfloor \frac{s - 1}{n_1} \right \rfloor: this, in the light of (2), means that ((s - 1) \mathrm{\ mod\ } n_1 = n_1 - 1) = 0, that is the condition (s - 1) \mathrm{\ mod\ } n_1 = n_1 - 1 is false, i.e. (s - 1) \mathrm{\ mod\ } n_1 \neq n_1 - 1:
Now, for establishing if s is a space of T, we have to understand what is s \mathrm{\ mod\ } n_1. Applying Property 2.4 at page 53 of op. cit., with a := s - 1, k = 1 and n := n_1, we’ll obtain that:
Then, in (3), the condition (s - 1) \mathrm{\ mod\ } n_1 \neq n_1 - 1 is equivalent to the condition s \mathrm{\ mod\ } n_1 \neq 0, that means that s is a space of T. So, summarizing:
Starting from equation (1), applying Proposition T.5 and considering a generic index i instead of 1, we obtain the equation we’ll call characteristic equation of first order linear \mathrm{t\_space}:
Characteristic equation of first order linear \mathrm{t\_space}
Let T = (n_i) be a linear first order dashed line. Then
where the right side equation is called characteristic equation of first order linear \mathrm{t\_space}.
Let’s consider again the dashed line (3) of Figure 1 and see what properties its seventh space has. It turns out to be 10:
We can see that among the first 10 positive dashed line columns there are:
- 7 spaces (1, 2, 4, 5, 7, 8, 10), the last of which is 10
- 3 columns containing one and only one dash (3, 6, 9)
The three dashes we identified are those with positive value less than or equal to 10, but also with positive value less than 10, since 10 is a space. Then by Proposition T.2 and its Corollary, their number is given by \left \lfloor \frac{10}{3} \right \rfloor and also by \left \lfloor \frac{9}{3} \right \rfloor. Indeed, both these expressions are equal to 3. This, by
that, by the cited Proposition, is equivalent to say that 10 is a space of T.
More specifically, 10 is the seventh space of T, because it satisfies the characteristic equation with x = 7:
that by Proposition T.3 is equivalent to say that 10 = \mathrm{t\_space}_T(7).
By Proposition T.3, in order to compute the \mathrm{t\_space} function, we have to solve the characteristic equation (4) for the unknown s. The solution is given by the following Theorem, proved in Teoria dei tratteggi (Dashed line theory), Theorem 8.1 page 202 (in Italian).
Formula for computing the linear first order \mathrm{t\_space} function
Let T = (n_i) be a linear first order dashed line. Then
Resuming the previous example, we can apply formula (5) with x = 7 obtaining:
Thus we have found again the result shown in Figure 2.
More generally, applying formula (5) with x = 1, 2, 3, 4, 5, 6, 7, 8, \ldots we’ll obtain, making the calculations, that \mathrm{t\_space}_{(3)}(x) = 1, 2, 4, 5, 7, 8, 10, 11, \ldots. This is an example that formula (5) computes all and only the spaces of a linear first order dashed line in an orderly fashion, skipping the multiples of the dashed line component (in this case 3).
The characteristic equation (4) is rather unusual, for the presence of the integer part, compared with what is taught in scholastic maths. On the contrary, in dashed line theory equations of this kind are rather common, and a way for solving them is to apply some properties that are the subject, for the people who want to examine in depth, of Chapter 2 of Teoria dei tratteggi (Dashed line theory), in Italian.
In spite of this, it’s possible to sketch the solution by simply removing the integer parts and solving the resulting algebric equation. For example, if we consider the first part of the characteristic equation:
After removing the integer parts we have:
The approximate solution obtained is very similar to the exact solution \left \lfloor \frac{n_1 x - 1}{n_1 - 1} \right \rfloor. The main problem is to understand in general how much the solution found by means of this method is close to the exact one: in the next posts we’ll see this aspect to be of fundamental importance.