Study of existence of complementary space pairs based on second order dashed lines

Prerequisites:

• Dashed line theory definitions and symbols
• Our proof strategies
• Proof strategy based on dashes
• Characterization of spaces

The purpose of the study we’re going to expose here is to prove that the Hypothesis H.1.T.A (Hypothesis of existence of pairs of complementary spaces based on dashes) is valid for second order hatches. We will adopt the following strategy:

• Reformulating the initial statement referring to second order dashed lines, in order to clarify which actual constraints must be satisfied by a possible solution;
• Proving that there is at least one solution that satisfies the constraints.

Statement of the initial hypothesis for the second order

As already indicated, the first step is to rewrite the starting hypothesis to relate it to the second order dashed lines. For clarity, we report below the text of the hypothesis rewritten by setting k = 2:

Once all the constraints are made explicit using the known properties of the second order dashed lines, following the approach of the characterization of spaces, the previous Hypothesis can be reformulated like this:

Looking for solutions

So, we have rewritten the Hypothesis H.1.T.A (Hypothesis of existence of pairs of complementary spaces based on dashes) referring to the second order dashed lines; the next step is to prove that it is true, i.e. there is at least one pair (x, y) which meets the required criteria. The first obstacle in facing the problem is given by the fact that, in the last equation, there’s the operation \lceil \cdot \rceil, which cannot be treated easily. However, the problem can be overcome through the properties of operation \mathrm{\ mod\ } and of its variant \mathrm{\ mod^{\star}\ }, which allow us to move on to a further reformulation. The last equation, in fact, can be rewritten like this:

In the following, we will indicate the two addends on the left with the symbols v and w:

So, taking into account how the hypothesis H.1.T.A.2 was obtained, we have:

From these equations it is clear that the two spaces that interest us, \mathrm{t\_value}(x) - 1 and \mathrm{t\_value}(y) + 1, actually depend on v and w, more than on x and y (in fact, as we will see below, different values of x and y can give the same value of v and w, and then the same spaces). So even if, as the Hypothesis is formulated, the unknowns are x and y, we can consider equivalently v and w as unknowns, as actually we’ll do.

Proving the existence of solutions

Using this formulation, we can proceed with the final step, that is, to prove that the equation thus rewritten has at least one solution (x, y) which satisfies all constraints. The proof will start from an example, namely the equation developed on n = 6 with the dashed line T = (3, 5), so n_1 = 3, n_2 = 5, n_1 + n_2 = 8, and n_1 n = 3 \cdot 6 = 18:

Although the proof starts from this example, the conclusions that derive from it, as we will see, will go beyond the latter, being valid universally for all second order dashed lines that have prime numbers as components.

As a starting point for the demonstration, we can build a table like this:

• In the first row there are the values of x, starting from;
• In the second row there are the corresponding values of the expression (n_2 x + 1) \mathrm{\ mod^{\star}\ } (n_1 + n_2), which occurs in the equation and constraints, and in this case we have (5 x + 1) \mathrm{\ mod^{\star}\ } 8;
• In the third row we will insert the value of v := \cfrac {5 x + 1 - (5 x + 1) \mathrm{\ mod^{\star}\ } 8}{8}, that is equal to the left addend that appears in the first member of the equation (6);
• The table continues until it reaches a value of v equal to n - 2, i.e. up to 6 - 2 = 4.

The table is the following:

Next, we’ll group the columns that have the same value of v:

Now, let’s proceed in the same way for y, but creating a table made differently:

• The first two lines are similar to the first two of the previous table, but they refer to y;
• In the third row, instead of v, we’ll insert the value of w := \cfrac {5 y + 1 - (5 y + 1) \mathrm{\ mod^{\star}\ } 8}{8}, i.e. equal to the other addend which appears on the left of the equation (6);
• The columns of the table are reversed with respect to the previous one, that is, they begin from the last column instead of the first one.

The table is the following:

Starting from these two tables, then we can create another one, made this way:

• At the top there are the first two rows of the first table;
• Then there are the first two rows of the second table, swapped places;
• Then there is a row containing the sum of v and w, taken from the two tables.

Then we’ll obtain the following table:

We can see v + w is always 4, as provided by equation (6) from which we started to create v and w.

Now, we can highlight with a black border all the values of the second row which satisfy the constraint (4), and those of the third row which satisty the constraint (5):

Then, we can indicate in yellow the columns that have at least one number highlighted on both the second and third row, i.e. such that at least one x and at least one y of the column satisfy the respective constraints (4) and (5):

All pairs (x, y) corresponding to the highlighted numbers in the yellow columns, i.e. (1, 7), (6, 3), (7, 1), are therefore, by construction, all the solutions of equation (6) that satisfy the constraints (4) and (5), which are represented in the bottom row in the form of sums v + w = n - 2.

Once the solutions are represented this way, it remains to be understood under which conditions they actually exist. Let’s start by observing that by extending the second row of the previous table:

we note how the cell not highlighted that does not contain numbers with the border (i.e. the cell containing 3, 8) appears once every 5 cells, and there are, in turn, 5 possible cells in total, that is (1, 6), (3, 8), (2, 7), (4) and (5), since, if we also considered x = 0, the first cell (6) would in turn become (1, 6). We will represent this situation using dashed line notation: that is, we transform the previous table into a new table, in which we place a dash in the cells that correspond to the cell (3, 8):

This table has a dash every 5 cells, as in the representation of the dashed line T = (5):

The table above this, therefore, is a “translated” dashed line T = (5), in the sense that its dashes alternate with empty cells in the same way, but their sequence begins in a cell different.

Now, let’s apply the same principle to the row of (5y + 1) \mathrm{\ mod^{\star}\ } 8 of the previous table:

The result is similar to the previous one: also in this case we obtain a translated dashed line, the dashes of which are at the same distance as before, even if the sequence starts in a still different cell.

Now, let’s go back to the table from which we started, but reporting the dashes instead of the numbers, and indicating in yellow the columns that were highlighted as such previously:

The second and third row of the table constitute a dashed line, which is of second order, but is translated; the interesting aspect is that the pairs of valid solutions, that is (1, 7), (6, 3) and (7, 1), are all in correspondence with the yellow columns, which correspond to the spaces of this dashed line: therefore, to prove that these solutions exist, it is sufficient to find the spaces of this translated dashed line (the representation of which has been extended compared to the original one so as to highlight the repetition of the dashes):

Finding the spaces of a dashed line done this way, and/or showing that they exist, is very simple, because the dashes are repeated both on the first and on the second line with the same periodicity, and the distance between them, in each of the lines, is equal to 5 = n_2.

Generally, whatever n_1, n_2 and n are, we can say that the first space cannot be beyond the third column. In fact, the worst case, that is the one in which the first space is as far as possible from the beginning of the dashed line, is the one in which:

• The first dash of the first row is located in the first cell of the row itself;
• The first dash of the second row is located in the second cell of the row itself.

The dashed line corresponding to this case is as follows:

In this case, or in the equivalent case in which the two rows are exchanged places, the first space is located on the third column. In general, also in any other arrangement of the dashes, provided that they are spaced from each other, on the same line, by n_2, and taking into account that n_2 \geq 3 (due to n_2 \gt n_1 \geq 2), the first space would never be beyond the third column. This can be proved by absurd: if the space farthest from the beginning of the dashed line were on the fourth column, for example, it would be preceded by three columns which are not spaces, which would mean that, in these columns, there would be at least three dashes. But, whatever is their mutual position (all three on the first row, or all three on the second, or alternating), on at least one row the distance between two consecutive dashes should be at most 2, which would be less than n_2 \geq 3, which is not possible. The reasoning is similar if the dashes are supposed to be more than three, or that the first space is in the fifth column, or sixth, and so on.

Now, let’s put again the row with v in the dashed line:

The value of v corresponding to the first space, that is the first admissible solution, is at most 2, for the previous discussion. So, we can say that at least a solution exists with v \leq 2, as long as the table has at least three columns, because the value v = 2 is located on the third column. By construction, the number of columns in the table is n - 1 (from v = 0 to v = n - 2); so, a sufficient condition for having a value of v which satisfies out hypothesis, is that n - 1 \geq 3, that is n \geq 4.
Now that we have found a condition of existence of the solution, to find the two spaces that interest us it is sufficient to remember that one precedes the x-th dash, and the other follows the y-th, then the solutions corresponding to an admissible value of v, and to the corresponding value of w = n - 2 - v, are:

We can also observe that q, once we compute p, can be simply calculated as n_1 n - p, due to the last equation of the Hypothesis H.1.T.A.1.
We have estebilished that at least a solution exists with v \leq 2, so, setting this bound in the formula (7), we can deduce that there exists a space p , corresponding to a solution of Hypothesis H.1.T.A.1, such that

So not only we found the solution, but we also found an upper bound for one of the two corresponding spaces.
In summary, we can say that the Hypothesis H.1.T.A.1 always admits a solution for n \geq 4, and in this case there is a solution such that one of the two corresponding spaces is less than or equal to 3 n_1 - 1.