SZTAKI Desktop Grid - BinSYS

Lo scopo del progetto è di trovare tutti i sistemi numerici binari generalizzati con dimensione maggiore di 11. Qui di seguito diamo una descrizione breve del concetto di sistema numerico e citare alcune possibile applicazioni.

 

Sia n un numero intero maggiore di 1. Quando parliamo di sistema numerico nel caso originale, usiamo il fatto che ogni numero naturale z può essere scritto, univocamente, nella forma finita

Diciamo che n è la base del sistema numerico, i d_j sono chiamate "cifre". Se n=2 allora parliamo di un sistema numerico binario. Questi sistemi sono troppo poveri per rappresentare i numeri negativi quindi abbiamo bisogno di un segno. Se permettiamo alla base di essere un intero negativo, una rappresentazione di tutti gli interi può diventare possibile. Per esempio se utilizziamo la base -2, ogni intero ha una forma

Questo può essere generalizzato per gli interi algebrici di estensione finita per il campo dei numeri razionali. Un semplice esempio: tutti gli interi gaussiani (numeri complessi nella forma x+yi, dove x,y sono interi) possono essere scritti univocamente nella base (-1+i) come segue

Utilizzando l'algebra lineare possiamo definire sistemi numerici in un modo molto più generale. La base è ora una matrice e le cifre sono vettori. Possiamo riformulare il precedente esempio. Ogni vettore intero bidimensionale è rappresentato come una somma finita

v = ∑_j M^_j · d_j,

dove

e

Parliamo di un sistema binario se il determinante di M è ±2. In questo caso ci sono solo due cifre e una di loro è l'origine. Questo significa che, se abbiamo un sistema numerico, allora ogni vettore intero può essere rappresentato come una serie finita di 0 e 1.

Non ogni matrice M può essere una base per un sistema numerico. Finora nessuna caratterizzazione di "buone" matrici è stata fatta. Ci sono condizioni necessarie e sufficienti ma il divario tra loro è troppo grande. Non c'è nessun metodo efficiente conosciuto, per trattare con le matrici, che soddisfi le condizioni necessarie ma scarti le condizioni sufficienti. Una cosa da notare è che se fissiamo il determinante e la dimensione allora, in linea generale, ci sono solamente un numero finito di possibili matrici.

 

Risultati previsti

Lo scopo del programma è di trovare diversi sistemi numerici binari generalizzati. Una ricerca intensiva è eseguita in un insieme finito di matrici di dimensione data che soddisfano alcune condizioni necessarie. La difficoltà è che la dimensione di questo insieme finito è una funziona esponenziale della dimensione. Ora sembra possibile l'attacco al caso delle matrici 11x11. Per verificare ulteriormente le condizioni necessarie il programma esegue molti calcoli in floating-point (virgola mobile). Così è richiesto molto tempo di cpu. Fortunatamente, è possibile parallelizzare e possiamo ottenere benefici dall'esecuzione su diverse macchine.

L'output del programma è una lista di matrici (essendo polinomi caratteristici più precisi) che sono già, probabilmente, la base del sistema numerico. La lista è elaborata con un altro programma (che non richiede molta CPU). Il risultato finale è, poi, una lista (completa) dei sistemi numerici binari ad una determinata dimensione.

Successivamente eseguiamo un'analisi teorica delle informazioni. I sistemi numerici forniscono una rappresentazione binaria dei vettori di interi. Utilizzando le coordinate abbiamo un'altra (più standard) rappresentazione. Le due rappresentazioni di solito differiscono nella lunghezza. Inoltre, vettori vicini l'un l'altro nello spazio, possono avere rappresentazioni binarie che sembrano molto differenti. Queste osservazioni suggeriscono che si potrebbero applicare i sistemi numerici nella compressione dei dati, codifica o crittografia.

I sistemi numerici sono interessanti dal punto di vista geometrico. Se permettiamo potenze negative di M di apparire nella rappresentazione binaria, possiamo ottenere una possibile rappresetazione infinita di vettori reali (potremmo dire che utilizziamo un punto radix). L'output del programma può essere utilizzato per analizzare queste serie. Questo strumento di analisi topologica, es. calcolo della dimensione, connessione, ecc. Se utilizziamo la matrice M sopra, possiamo ottenere la seguente serie.

Infine, conoscendo tutte le matrici fino alla dimensione data potrebbe aiutarci a conoscere più in profondità la matematica dei sistemi numerici generalizzati.