10. Il calcolo della riga e le differenze tra i valori dei trattini

Prerequisiti:

Questo articolo può essere considerato un approfondimento di quelli relativi al calcolo della riga. Infatti vale la pena, prima di passare alle formule del \mathrm{t\_valore}, soffermarsi a guardare con maggiore attenzione i moduli introdotti col calcolo della riga, per esempio i moduli (1) e (4) dell’articolo Calcolo della riga nei tratteggi lineari di secondo ordine. Essi infatti hanno un significato ben preciso nel tratteggio: sono direttamente collegati alla differenza tra il valore di un trattino e quello del precedente trattino di un’altra riga. Vediamo tutto ciò nel dettaglio sia per il secondo che per il terzo ordine.

Differenza tra i valori di un trattino della riga i ed il precedente della riga j, nei tratteggi lineari di secondo ordine

Riprendiamo la Figura 1 dell’articolo Calcolo della riga nei tratteggi lineari di secondo ordine:

Figura 1: Valori della funzione (n_1 x – 1) mod (n_1 + n_2) = (3x – 1) mod 8 nel tratteggio (3, 5), per i vari ordinali x

Osserviamo, per ciascun trattino della riga 1, il valore del modulo

(n_1 x - 1) \mathrm{\ mod\ } (n_1 + n_2) \tag{1}

Osservando attentamente, si può notare una particolare coincidenza: il valore di questo modulo è proprio il numero di colonne che separano il trattino considerato della prima riga, dal precedente trattino della seconda riga. Ad esempio il primo trattino, di valore 3, ha come valore del modulo 2 (nel senso che la formula (1) dà 2 per x = 1) ed in effetti tra questo trattino ed il precedente della seconda riga ci sono esattamente due colonne. Questo vale in tutti i casi, anche quando il valore del modulo è 0 (cioè non ci sono colonne che si frappongono tra il trattino della riga 1 ed il precedente della riga 2), e quando nelle colonne che si frappongono ci sono altri trattini della riga 1:

Figura 2: Il modulo (n_1 x – 1) mod (n_1 + n_2) mostrato in Figura 1 rappresenta il numero di colonne (in grigio) che separano un trattino della prima riga (in verde) dal precedente trattino della seconda riga (in rosso).

Possiamo osservare che, preso un qualunque trattino della prima riga, il precedente trattino della seconda riga non può mai trovarsi sulla stessa colonna, ma al massimo sulla colonna immediatamente precedente. Infatti, se si trovasse sulla stessa colonna, esso sarebbe successivo nell’ordinamento, perché avrebbe indice di riga maggiore. Ad esempio, il trattino della seconda riga che precede quello che ha come modulo corrispondente 4, come si vede in Figura 2, è quello con modulo 6, non quello con modulo 7 che si trova sulla stessa colonna. In questo modo il concetto “numero di colonne che separano un trattino della prima riga dal precedente trattino della seconda riga” è ben definito, perché presuppone che i due trattini si trovino su colonne diverse: al più possono trovarsi su colonne adiacenti, ed in questo caso il numero di colonne che li separano è 0.

Se il numero di colonne che separano un trattino della prima riga dal precedente della seconda è dato dal modulo (1), sommando 1 si ottiene la differenza tra i loro valori (con riferimento alla Figura 2, queste differenze sono, dall’alto verso il basso, 3, 1, 4, 2 e 5):

(n_1 x - 1) \mathrm{\ mod\ } (n_1 + n_2) + 1\tag{2}

In questa espressione compare un -1 dentro il modulo ed un +1 fuori: ci si potrebbe chiedere se si possono semplificare tra loro, ottenendo n_1 x \mathrm{\ mod\ } (n_1 + n_2). La risposta è che questa semplificazione è possibile, ma solo in questo caso specifico. Infatti, dati due generici numeri naturali a e b, non è sempre vero che (a - 1) \mathrm{\ mod\ } b + 1 = a \mathrm{\ mod\ } b. L’uguaglianza corretta è la seguente (Teoria dei tratteggi, Proprietà 2.15 pagg. 61-62):

(a - 1) \mathrm{\ mod\ } b + 1 = \begin{cases} b & \text{se }a \mathrm{\ mod\ } b = 0 \\ a \mathrm{\ mod\ } b & \text{altrimenti} \end{cases}

Utilizzando la notazione speciale “modulo star“, possiamo riscrivere la (2) in modo più compatto:

n_1 x \mathrm{\ mod^{\star}\ } (n_1 + n_2) \tag{3}

Tuttavia, come accennavamo, non è un errore semplificare la (2) anche come

n_1 x \mathrm{\ mod\ } (n_1 + n_2) \tag{4}

ma questa seconda semplificazione è possibile solo perché non si può mai verificare che n_1 x \mathrm{\ mod\ } (n_1 + n_2) = 0 (v. i dettagli seguenti per la dimostrazione), caso in cui, per la definizione di modulo star, la (3) e la (4) assumerebbero valori diversi. Tuttavia, preferiremo la semplificazione (3) per affinità con quello che accade nel terzo ordine, come vedremo nel prossimo paragrafo.

Se n_1 x diviso per n_1 + n_2 desse resto 0, l’intero precedente, n_1 x - 1, darebbe resto n_1 + n_2 - 1. Il modulo (1) quindi varrebbe n_1 + n_2 - 1. Ma per la (8) del Teorema T.2 (Calcolo della riga dell’x-esimo trattino in un tratteggio lineare di secondo ordine), dato che per ipotesi l’x-esimo trattino si trova sulla riga 1, questo modulo deve essere minore di n_2, quindi non può mai valere n_1 + n_2 - 1.

Riassumendo, possiamo dire che la formula (3) calcola la differenza tra il valore dell’x-esimo trattino del tratteggio (n_1, n_2), se questo appartiene alla prima riga, ed il precedente trattino della seconda riga.

E se l’x-esimo trattino appartiene alla seconda riga?
Come si può immaginare, in questo caso bisogna analizzare l’altro modulo che abbiamo introdotto col calcolo della riga nei tratteggi lineari di secondo ordine:

n_2 x \mathrm{\ mod\ } (n_1 + n_2)\tag{5}

Questo caso è però più semplice, perché il modulo (5) fornisce direttamente la differenza tra i valori dei due trattini (e non il numero di colonne frapposte), come si può vedere nell’immagine seguente:

Figura 3: Il modulo n_2 x mod (n_1 + n_2) rappresenta la differenza tra i valori (numero di colonne in grigio) tra un trattino della seconda riga (in verde) ed il precedente trattino della prima riga (in rosso).

Ricapitolando, possiamo enunciare il seguente Teorema ed il seguente Lemma:

Differenza tra i valori di un trattino della riga i ed il precedente della riga j, in un tratteggio lineare di secondo ordine

Sia T = (n_1, n_2) un tratteggio lineare di secondo ordine. Siano x \gt 0, t := \mathrm{t}_T(x) ed i l’indice della riga di t. Sia j tale che \{i, j\} = \{1, 2\}. Allora la differenza tra il valore di t e quello del precedente trattino della riga j è data da:

\begin{cases} n_1 x \mathrm{\ mod^{\star}\ } (n_1 + n_2) & \text{se }t \in T[1] \\ n_2 x \mathrm{\ mod\ } (n_1 + n_2) & \text{se }t \in T[2] \end{cases}

Uguaglianza tra (n_1 x - 1) \mathrm{\ mod\ } (n_1 + n_2) + 1 e n_1 x \mathrm{\ mod^{\star}\ } (n_1 + n_2)

Siano n_1, n_2 ed x degli interi, con n_1 \gt 1, n_2 \gt 1 ed x \geq 0. Allora vale l’uguaglianza:

(n_1 x - 1) \mathrm{\ mod\ } (n_1 + n_2) + 1 = n_1 x \mathrm{\ mod^{\star}\ } (n_1 + n_2)
Osserviamo che il Teorema T.3 consente di calcolare la differenza tra i valori di due trattini, ma questi valori non sono noti. Sono noti solo l’ordinale e la riga dell’ultimo dei due trattini (tra l’altro, la riga può essere calcolata dall’ordinale grazie al Teorema T.2, quindi si potrebbe partire anche solo dall’ordinale). In uno dei prossimi articoli vedremo i teoremi per calcolare il valore di un trattino, ma questo Teorema ci mostra che è possibile dire qualcosa di non banale sui valori dei trattini senza calcolarli.

Nell’esempio dell’articolo Calcolo della riga nei tratteggi lineari di secondo ordine abbiamo visto che l’ottavo trattino del tratteggio (3, 5) appartiene alla seconda riga. Applicando il Teorema T.3, calcoliamo la differenza tra il valore di questo trattino e quello del precedente trattino della prima riga.

Applicando la formula relativa al caso t \in T[2] con i valori (n_1, n_2, x) = (3, 5, 8), abbiamo:

\begin{aligned} n_2 x \mathrm{\ mod\ } (n_1 + n_2) = \\ 5 \cdot 8 \mathrm{\ mod\ } (3 + 5) = \\ 40 \mathrm{\ mod\ } 8 = \\ 0 \end{aligned}

Abbiamo ottenuto 0: ciò significa che i due trattini hanno lo stesso valore, cioè si trovano sulla stessa colonna, come si può vedere nella Figura 3 dell’articolo citato, riportata qui per comodità:

L’ottavo trattino del tratteggio lineare (3, 5) appartiene alla riga 2

Osserviamo che in questo esempio è fondamentale l’utilizzo dell’operatore \mathrm{\ mod\ } anziché \mathrm{\ mod^{\star}\ }: se avessimo utilizzato il secondo operatore il risultato sarebbe stato, erroneamente, 8.

Diretta conseguenza del Teorema T.3 è il seguente Corollario:

Differenza tra i valori di un trattino della riga i ed il successivo della riga j, in un tratteggio lineare di secondo ordine

Sia T = (n_1, n_2) un tratteggio lineare di secondo ordine. Siano x \gt 0, e t := \mathrm{t}_T(x) appartenente alla riga i. Sia j tale che \{i, j\} = \{1, 2\}. Allora la differenza tra il valore di t e quello del trattino successivo della riga j, è data da:

n_j - n_i x \mathrm{\ mod^{\star}\ } (n_i + n_j)

Indichiamo con t_p il trattino che precede t nella riga j, e con t_s quello che lo segue:

Figura 4: Posizione reciproca di t, t_p e t_s nel tratteggio T = (3, 5)

Poniamo inoltre:

  • d_{tot}: distanza tra t_s e t_p;
  • d_{prec}: distanza tra t e t_p;
  • d_{succ}: distanza tra t_s e t;

Per costruzione, si ha:

d_{tot} = d_{prec} + d_{succ}

Per definizione, d_{prec} è la distanza tra il trattino t della riga i e quello che lo precede nella riga j, per cui, per il Teorema T.3, si ha

d_{prec} = n_i x \mathrm{\ mod^{\star}\ } (n_i + n_j)

da cui

d_{tot} = n_i x \mathrm{\ mod^{\star}\ } (n_i + n_j) + d_{succ}

Ma d_{tot} è la distanza tra due trattini della riga j del tratteggio, che è pari a n_j:

n_j = n_i x \mathrm{\ mod^{\star}\ } (n_i + n_j) + d_{succ}

da cui

d_{succ} = n_j - n_i x \mathrm{\ mod^{\star}\ } (n_i + n_j)

che era la tesi da dimostrare.

Differenza tra il valore di un trattino di una riga e quelli dei precedenti delle altre righe, per i tratteggi lineari di terzo ordine

Analogamente a quanto visto per il secondo ordine, i moduli che compaiono nelle formule (5), (8) e (10) dell’articolo Calcolo della riga nei tratteggi lineari di terzo ordine, non ci dicono soltanto a quale riga appartiene l’x-esimo trattino, ma ci dicono anche qualcosa sulla sua posizione rispetto ai trattini delle altre righe. Questa informazione è presente nei numeri a e b mediante cui i moduli menzionati si esprimono come elementi di R_T(i). Vale infatti il seguente Teorema:

Differenza tra il valore di un trattino di una riga e quelli dei precedenti trattini delle altre righe, in un tratteggio lineare di terzo ordine

Sia T = (n_1, n_2, n_3) un tratteggio lineare di terzo ordine. Siano x \gt 0, t := \mathrm{t}_T(x) ed i l’indice della riga di t (ottenibile applicando il Teorema T.4 (Calcolo della riga dell’x-esimo trattino in un tratteggio lineare di terzo ordine con componenti a due a due coprime)). Siano \{i, j, k\} = \{1, 2, 3\}. Siano a e b gli interi, che esistono per il Teorema T.4, tali che

(n_j + n_k) n_i x \mathrm{\ mod\ } N = n_j a + n_k b \in R_T(i) \tag{6}

Dove N ed R_T(i) sono definiti come nel Teorema T.4. Allora:

  • a è la differenza tra il valore di t e quello del precedente trattino della riga k
  • b è la differenza tra il valore di t e quello del precedente trattino della riga j

I Teoremi T.4 e T.5 sono fortemente connessi. Per il Teorema T.4, se l’x-esimo trattino appartiene alla riga i, allora il modulo (n_j + n_k) n_i x \mathrm{\ mod\ } N appartiene all’insieme R_T(i). Ma se vi appartiene, allora per definizione di R_T(i) esso si può scrivere nella forma n_j a + n_k b, dove a e b soddisfano i vincoli posti dalla definizione stessa (formule (4), (7) e (9) dell’articolo Calcolo della riga nei tratteggi lineari di terzo ordine). Il Teorema T.5 fa un passo in avanti: questi a e b non solo esistono, ma hanno un significato ben preciso. Sono le differenze tra il valore dell’x-esimo trattino e quelli dei precedenti trattini delle altre righe. Osserviamo che, se è vero questo, allora a e b sono anche unici. Infatti, sia il precedente trattino della riga k che quello della riga j sono univocamente determinati: non parliamo di “un” trattino precedente, ma “del” precedente, ossia il trattino più grande tra i precedenti, che è appunto uno solo. Di conseguenza, anche i numeri a e b, che sono le differenze tra il valore di t e quello di questi due trattini, sono univocamente determinati, ossia vale la seguente versione più forte della (5 + 8 + 10) dell’articolo citato:

\mathrm{t}_T(x) \in T[i] \Leftrightarrow \exists! a\ \exists! b \text{ t.c. } (n_j + n_k) n_i x \mathrm{\ mod\ } N = n_j a + n_k b \in R_T(i)

Tornando all’enunciato del Teorema T.5, possiamo anche osservare che nella (6) il coefficiente di una componente indica la differenza col valore del precedente trattino della riga dell’altra componente: a, che è il coefficiente di n_j, indica la differenza col valore del precedente trattino della riga di n_k, e viceversa. Questo è importante per non confondersi tra a e b, evitando nel contempo notazioni più complesse (ad esempio potremmo scrivere n_j d_k + n_k d_j, dove d_{\cdot} indicherebbe la differenza col valore del precedente trattino della riga indicata nel pedice; ma la semplice regola mnemonica che abbiamo osservato rende superflua questa notazione).

Infine notiamo che in questo teorema, a differenza del Teorema T.4, non c’è l’ipotesi che le componenti siano a due a due coprime: esso vale per qualsiasi tratteggio lineare di terzo ordine.

Riprendiamo l’esempio dell’articolo Calcolo della riga nei tratteggi lineari di terzo ordine e vediamo cos’altro possiamo dire, grazie al Teorema T.5, sul sesto trattino di T = (2, 3, 5), che possiamo chiamare t. Abbiamo visto che il modulo (n_1 + n_3) n_2 x \mathrm{\ mod\ } N per questo tratteggio, per x = 6, vale 2; inoltre questo numero si può scrivere nella forma 2 = 2 a + 5 b,\ a \in \{1, 2, 3, 4, 5\},b \in \{0, 1\} come:

2 = 2 \cdot 1 + 5 \cdot 0

Utilizzando la regola mnemonica dell’osservazione precedente, abbiamo che il coefficiente della componente 2, cioè 1, è la differenza tra il valore di t e quello del precedente trattino della riga della componente 5; viceversa, il coefficiente della componente 5, 0, è la differenza tra il valore di t e quello del precedente trattino della riga della componente 2. In altri termini, la prima coppia di trattini si trova su colonne adiacenti, la seconda su un’unica colonna:

Figura 5: Sesto trattino del tratteggio (2, 3, 5) (in grigio) ed i precedenti trattini delle altre righe (in verde). Le differenze tra il valore del primo e quelli degli altri due sono rispettivamente 0 e 1.

Per verificare altri casi, possiamo costruire esplicitamente l’intero insieme R_T(2), che rappresenta tutti i possibili valori del modulo (n_1 + n_3) n_2 x \mathrm{\ mod\ } N per i trattini della seconda riga. Per farlo partiamo dalla definizione (formula (7) dell’articolo Calcolo della riga nei tratteggi lineari di terzo ordine) e scriviamo in una tabella i valori ottenuti al variare dei parametri a e b:

Figura 6: Costruzione esplicita dell’insieme R_T(2) per il tratteggio T = (2, 3, 5)

A questo punto, ricercando nella tabella il modulo di un qualsiasi trattino della seconda riga, possiamo immediatamente “scomporre” il modulo nei due parametri che abbiamo chiamato a e b, ottenendo così le differenze di valore rispetto ai precedenti trattini delle altre righe:

Figura 7: Scomposizione di un elemento dell’insieme R_T(2) della Figura 6 nei parametri a e b.

Figura 8: Differenze di valore tra il trattino della seconda riga che ha il modulo evidenziato nella Figura 7 ed i precedenti trattini della prima riga e della terza riga. Queste differenze corrispondono ai parametri a e b evidenziati nella Figura 7.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.