Proprieta' interi

[Speed]

Non sono esperto di teoria dei numeri e di ideali. Mi occorre sapere, per risolvere un problema di teoria dei controlli, se vale la seguente proprieta':

PROPRIETA':

Siano dati 2 interi positivi M e n. Esistono M interi positivi $z_1,z_2,\cdots,z_M$ tali che, tutti gli interi che posso costruire da essi nel seguente modo:

\[
\sum_{i=1}^Mc_iz_i
\]

dove $c_i$ sono $M$ interi positivi, compreso lo 0, tali che $\sum_{i=1}^Mc_i\le n$, hanno una scrittura unica. Cioe' vale sempre

\[
\sum_{i=1}^Mc_iz_i\neq
\sum_{i=1}^Md_iz_i
\]

con $\sum_{i=1}^Mc_i\le n$ e $\sum_{i=1}^Md_i\le n$ e i coefficienti $c_i$ differiscono dai $d_i$ per almeno un valore di $i$.


E' sempre possibile? A quale condizione sugli $z_i$? Che tipo di teoria devo studiare per capire meglio?

Ad esempio se $M=3$ e $n=2$, gli $M$ numeri $z_1=3$, $z_2=5$, $z_3=7$, non soddisfano la proprieta'. Infatti posso formare 10 sia con $c_1=0$, $c_2=2$, $c_3=0$ ma anche con $d_1=1$, $d_2=0$, $d_3=1$.
Contrariamente i numeri $z_1=5$, $z_2=7$, $z_3=11$ soddisfano la proprieta'.

[gugo82]

Riassumendo...
Assegnati due naturali $M,n$ ti interessa sapere se ci sono condizioni da imporre su una $M$-upla di numeri naturali $z_1,..., z_M$ che siano sufficienti alla validità della seguente proprietà:

Ogni naturale del tipo $c_1z_1+... + c_Mz_M$ con coefficienti $c_1, ..., c_M in NN$ tali che $sum_(i=1)^M c_i <= n$ si può scrivere in unico modo come combinazione degli $z_1, ..., z_M$.

Chiaramente, la prima condizione che viene in mente è che gli $z_1, ..., z_M$ siano primi tra loro... Ma questa condizione da sola non è sufficiente.

Osserva anche che la condizione cercata, evidentemente, dipende da $n$. Infatti, la terna $z_1=5,z_2=7,z_3=11$ soddisfa la proprietà richiesta quando $n=2$ (come hai già osservato), ma non la soddisfa per $n=4$ (perché $0*5 + 0*7+2*11 = 22 = 3*5+1*7 + 0*11$).

Più di questo al momento non riesco a dirti, poiché non sono esperto di Aritmetica nemmeno io e questo problema non l'ho mai incontrato.

[Speed]

Esatto. Or ora mi pare di esser riuscito a dimostrarne la validita'...dopo l'ennesimo caffe'.
ma di solito poi uno si accorge che c'e' un errore. Intanto la posto.

E' per induzione su $M$. Ovviamente vale banalmente per $M=1$.
Siano ora $z_1,\cdots,z_{M-1}$ un set di $M-1$ naturali che soddsfano la proprieta' per un dato $n$. Voglio trovarne $M$. Li costruisco cosi'.

\[
z'_i=z'_0+z_i
\]

con $z'_0$ il nuovo naturale da definire.

Voglio che

\[
\sum_{i=1}^{M-1}c_iz'_i +c_0 z'_0\neq
\sum_{i=1}^{M-1}d_iz'_i +d_0 z'_0
\]

con $c\equiv \sum_{i=0}^{M-1}c_i\le n$ e $d\equiv \sum_{i=0}^{M-1}d_i\le n$. Sviluppando si ottiene



\[
\sum_{i=1}^{M-1}c_iz_i +c z'_0\neq
\sum_{i=1}^{M-1}d_iz_i +d z'_0
\]

ora, se $c=d$ la precedente vale per ipotesi induttiva. Assumiamo che $c$ e $d$ siano diversi. Allora, $(c-d)z'_0$ e', in valore assoluto, almeno $z'_0$. D'altra parte la differenza

\[
\sum_{i=1}^{M-1}c_iz_i -
\sum_{i=1}^{M-1}d_iz_i
\]

non potra' mai superare $nz_m-z_1$ (assumendo che gli $z$ sono ordinati in ordine crescente). Ma allora basta scegliere un qualunque $z'_0$ piu' grande di $nz_m-z_1$.

O sbaglio???

[gugo82]

Non ho letto con attenzione, ma quanto hai scritto mi pare una risposta ad un'altra domanda, cioè:

Fissato $n in NN setminus \{ 0\}$, è vero che per ogni $M in NN setminus \{ 0\}$ esistono $M$ naturali $z_1, ..., z_M$ che soddisfano la proprietà scritta sopra?

[Speed]

...e non e' la stessa cosa? non essendovi relazione tra $n$ e $M$, vale dunque $\forall n$.

Grazie del feedback!