Campi finiti e segnale GPS

Lo scopo della tesi è quello di studiare una delle applicazioni della teoria dei campi finiti: il segnale GPS. A questo scopo si descrivono i registri a scorrimento a retroazione lineare (linear feedback shift register, LFSR), dispositivi utili in applicazioni che richiedono la generazione molto rapida di numeri pseudo-casuali. I ricevitori GPS sfruttano il determinismo di questi dispositivi per identificare il satellite da cui proviene il segnale e per sincronizzarsi con esso. Si inizia con una breve introduzione al funzionamento del GPS, poi si studiano i campi finiti: sottocampi, estensioni di campo, gruppo moltiplicativo e costruzione attraverso la riduzione modulo un polinomio irriducibile, fattorizzazione di polinomi, formula per il numero e metodi per la determinazione di polinomi irriducibili, radici di polinomi irriducibili, coniugati, teoria di Galois (automorfismo ed orbite di Frobenius, gruppo e corrispondenza di Galois), traccia, polinomio caratteristico, formula per il numero e metodi per la determinazione di polinomi primitivi. Successivamente si introducono e si esaminano sequenze ricorrenti lineari, loro periodicità, la sequenza risposta impulsiva, il polinomio caratteristico associato ad una sequenza e la sequenza di periodo massimo. Infine, si studiano i registri a scorrimento che generano uno dei segnali GPS. In particolare si esamina la correlazione tra due sequenze. Si mostra che ogni polinomio di grado n-1 a coefficienti nel campo di Galois di ordine 2 può essere rappresentato univocamente in n bit; la somma tra polinomi può essere eseguita come XOR bit-a-bit; la moltiplicazione per piccoli coefficienti richiede al massimo uno shift ed uno XOR. Si conclude con la dimostrazione di un importante risultato: è possibile inizializzare un registro in modo tale da fargli generare una sequenza di periodo massimo poco correlata con ogni traslazione di se stessa.

Alcuni metodi per la determinazione delle radici di un polinomio

Un problema classico in matematica, che presenta numerose applicazioni anche al di fuori di tale disciplina, è la ricerca delle radici di un polinomio. Per quanto riguarda i polinomi di grado minore o uguale a 4 ci sono delle formule per determinare le radici a partire dai coefficienti, mentre per il generico polinomio di grado maggiore o uguale a 5 formule simili non esistono. È possibile, però, determinare in modo approssimato le radici di un polinomio, o stimare il numero di radici reali di un polinomio reale in un dato intervallo, o ancora localizzare nel piano complesso gli zeri di un polinomio a coefficienti complessi.

L'effetto Gibbs

Nella tesi ho trattato l'effetto Gibbs,ovvero la presenza di forti oscillazioni nei polinomi di Fourier di funzioni con discontinuità di prima specie. Infine ho introdotto le somme di Fejér osservando come con questi polinomi trigonometrici si possa eliminare l'effetto Gibbs.

La base di Bernstein in spazi polinomiali generalizzati

Nella tesi si illustra il passaggio dagli spazi polinomiali agli spazi polinomiali generalizzati, gli spazi di Chebyshev estesi (spazi EC), e viene dato un metodo per costruirli a partire da opportuni sistemi di funzioni dette funzioni peso. Successivamente si tratta il problema dell'esistenza di un analogo della base di Bernstein negli spazi EC: si presenta, in analogia ad una particolare costruzione nel caso polinomiale, una dimostrazione costruttiva dell'esistenza di tale base. Infine viene studiato il problema delle lunghezze critiche di uno spazio EC: si tratta di determinare l'ampiezza dell'intervallo oltre la quale lo spazio considerato perde le proprietà di uno spazio EC, o non possiede più una base di Bernstein generalizzata; l'approccio adottato è di tipo sperimentale: nella tesi sono presentati i risultati ottenuti attraverso algoritmi di ricerca che analizzano le proprietà delle funzioni di transizione e ne traggono informazioni sullo spazio di studio.

La base di Bernstein in spazi polinomiali generalizzati a tratti

Le funzioni polinomiali possono essere utilizzate per approssimare le funzioni continue. Il vantaggio è che i polinomi, le loro derivate e primitive, possono essere rappresentati in maniera semplice attraverso i loro coefficienti ed esistono algoritmi stabili e veloci per valutarli. Inoltre gli spazi polinomiali godono di numerose proprietà importanti. In questo lavoro ci occuperemo di altri spazi funzionali, noti in letteratura come spazi di Chebyshev o polinomi generalizzati, per ragioni di riproducibilità. Infatti ciò che si ottiene attraverso i polinomi è soltanto una approssimazione che spesso risulta essere insufficiente. E' importante, quindi, considerare degli spazi in cui sia possibile avere una rappresentazione esatta di curve. Lo studio di questi spazi è possibile grazie alla potenza di elaborazione degli attuali calcolatori e al buon condizionamento di opportune basi di rappresentazione di questi spazi. Negli spazi polinomiali è la base di Bernstein a garantire quanto detto. Negli spazi di Chebyshev si definisce una nuova base equivalente. In questo lavoro andremo oltre gli spazi di Chebyshev ed approfondiremo gli spazi di Chebyshev a tratti, ovvero gli spazi formati dall'unione di più spazi del tipo precedente. Si dimostrerà inoltre l'esistenza di una base a tratti con le stesse proprietà della base di Bernstein per gli spazi polinomiali.

Codici ciclici e basi di Gröbner

Richiamo di elementi di algebra, tra cui: polinomi, ordini monomiali e base di Gröbner per ideali e sottomoduli con anche algoritmo FGLM. Descrizione dei codici, dei codici lineari, codifica e decodifica, matrice generatrice, matrice forma standard, matrice di controllo parità, codici ciclici con corrispondenza con ideali e polinomi generatori. Codice Reed-Solomon caso particolare di codice ciclico. Codici ciclici m-dimensionali e codifica sistematica con basi di Gröbner. Algoritmo di decodifica per Reed-Solomon con soluzione chiave e utilizzando basi di Gröbner sui sottomoduli.

Invarianti polinomiali sotto l'azione di gruppi finiti

Il teorema di Chevalley-Shephard-Todd è un importante risultato del 1954/1955 nella teoria degli invarianti polinomiali sotto l'azione del gruppo delle matrici invertibili. Lo scopo di questa tesi è presentare e dimostrare il teorema nella versione in cui l'anello dei polinomi ha come campo base R e di vedere alcuni esempi concreti di applicazione del teorema. Questa dimostrazione può essere generalizzata facilmente avendo come campo base un qualsiasi campo K di caratteristica 0.

I coefficienti binomiali.

In questa tesi si trattano alcune delle proprietà dei coefficienti binomiali, il cui nome deriva dal fatto che uno dei principali utilizzi di tali coefficienti è proprio nel Teorema binomiale di Newton, che permette di calcolare in modo esplicito lo sviluppo di un generico binomio con esponente naturale. I coefficienti binomiali si ricavano anche dal noto Triangolo di Tartaglia, che prende nome dal matematico Niccolò Fontana (1490-1557), il quale lo introdusse in Italia nel 1556 nella sua opera "General trattato di numeri et misure". Tuttavia, esso era già noto agli indiani e ai cinesi nel XIV secolo. Successivamente, in Francia e nel mondo anglosassone, tale triangolo prese anche il nome di Triangolo di Pascal, quando nel 1654 il matematico francese pubblicò il libro "Le triangle Aritmetique", interamente dedicato alle sue proprietà. I coefficienti binomiali, inoltre, trovano largo uso in calcolo combinatorio, ossia in quella branca della matematica che si occupa di contare i modi di raggruppare, secondo determinate regole, gli elementi di un insieme finito di oggetti. Dunque, per quanto la definizione stessa di coefficienti binomiali sia semplice, essendo un rapporto di interi fattoriali, in realtà essi trovano ampio utilizzo in vari ambiti e proprio per questo suscitano un notevole interesse ed hanno svariate applicazioni, giocando un ruolo fondamentale in parti della matematica come la combinatoria. In questa tesi, oltre alle proprietà più note, sono contenuti anche alcuni collegamenti tra i coefficienti binomiali e i polinomi di variabile naturale, nonché, nell'ultima parte, applicazioni alle differenze finite di progressioni geometriche.

Curve spline generalizzate di interpolazione locale

Questa tesi presenta un metodo generale per la costruzione di curve spline generalizzate di interpolazione locale. Costruiremo quest'ultime miscelando polinomi interpolanti generalizzati a blending function generalizzate. Verrano inoltre verificate sperimentalmente alcune delle proprietà di queste curve.

Il test di primalità aks

La tesi presenta l'algoritmo AKS, deterministico e polinomiale, scoperto dai matematici Agrawal, Kayal e Saxena nel 2002. Esso si basa su una generalizzazione del Piccolo Teorema di Fermat all'anello dei polinomi a coefficienti in Zp.

Risolubilità delle equazioni polinomiali

Scopo di questo elaborato è studiare la risolubilità per radicali di un polinomio a coefficienti in un campo di caratteristica zero attraverso lo studio del gruppo di Galois del suo campo di spezzamento. Dopo aver analizzato alcuni risultati su gruppi risolubili e gruppi semplici, vengono studiate le estensioni radicali e risolubili. Viene inoltre dimostrato su un campo K di caratteristica zero il Teorema di Galois, che caratterizza i polinomi risolubili per radicali f a coefficienti in K attraverso la risolubilità del gruppo di Galois G(L/K), dove L è il campo di spezzamento di f. La tesi contiene anche un'esposizione sintetica del metodo introdotto da Lagrange per la risoluzione di equazioni polinomiali di cui si conosca il gruppo di Galois.

La corrispondenza fra ideali e varietà algebriche, affini e proiettive

L’obiettivo di questa tesi è costruire una corrispondenza tra oggetti algebrici, gli ideali, e oggetti geometrici, le varietà algebriche, e studiarne il comportamento nel caso affine e proiettivo. Nel caso affine, lavorando in campi algebricamente chiusi, si descrive una corrispondenza biunivoca tra ideali radicali e varietà affini non vuote. Ciò permette di riformulare ogni affermazione sulle varietà affini in un’affermazione sugli ideali radicali, e viceversa; in particolare si descrivono le relazioni tra le operazioni su ideali e su varietà: alla somma degli ideali corrisponde l’intersezione di varietà, a prodotto e intersezione di ideali corrisponde l’unione di varietà, al quoziente di ideali corrisponde la chiusura di Zariski della differenza insiemistica delle varietà. Inoltre ad ogni ideale primo corrisponde una varietà irriducibile e agli ideali massimali corrispondono i punti dello spazio. Nel caso proiettivo invece, si considerano ideali omogenei e varietà proiettive, definite da polinomi omogenei. Restringendosi a campi algebricamente chiusi, si ha una corrispondenza biunivoca tra varietà proiettive non vuote e ideali radicali omogenei contenuti in un particolare ideale, (x_0,…,x_n). Con queste restrizioni la corrispondenza tra le operazioni algebriche e geometriche è la stessa studiata nel caso affine. Infine si introduce la chiusura proiettiva di una varietà affine, che è la più piccola varietà proiettiva che contiene una varietà affine data.

Corrispondenza ideali-varietà e criterio jacobiano per le singolarità

L'elaborato ha come soggetto le varietà algebriche affini. I primi due capitoli vanno ad analizzare nel dettaglio la corrispondenza fra gli ideali nell'anello dei polinomi e le varietà, che risulta biunivoca nel caso in cui si lavori in un campo algebricamente chiuso e ci si restringa agli ideali radicali. Il terzo e ultimo capitolo è dedicato allo studio di due concetti fondamentali per le varietà algebriche: la loro dimensione e i loro punti singolari. Vengono introdotte tre nozioni di dimensione di una varietà algebrica e se ne dimostra l'equivalenza. Per lo studio delle singolarità, si introduce il cosiddetto criterio jacobiano, basato sullo studio della matrice jacobiana ottenuta tramite le derivate parziali dei polinomi che definiscono la varietà.

L'aspetto geometrico delle identità algebriche: un esperimento nell'insegnamento della matematica

Un esperimento nell'insegnamento della matematica condotto attraverso l'aspetto geometrico delle identità algebriche.

Punti razionali di ordine finito su una curva ellittica

Questa tesi nasce dal voler approfondire lo studio delle curve piane di grado 3 iniziato nel corso di Geometria Proiettiva. In particolare si andrà a studiare la legge di gruppo che si può definire su tali curve e i punti razionali di ordine finito appartenenti alle curve ellittiche. Nel primo capitolo si parla di equazioni diofantee, dell’Ultimo Teorema di Fermat, dell'equazione e della formula di duplicazione di Bachet. Si parla inoltre dello stretto rapporto tra la geometria, l'algebra e la teoria dei numeri nella teoria delle curve ellittiche e come le curve ellittiche siano importanti nella crittografia. Nel secondo capitolo vengono enunciate alcune definizioni, proposizioni e teoremi, riguardanti polinomi e curve ellittiche. Nel terzo capitolo viene introdotta la forma normale di una cubica. Nel quarto capitolo viene descritta la legge di gruppo su una cubica piana non singolare e la costruzione geometrica che porta ad essa; si vede il caso particolare della legge di gruppo per una cubica razionale in forma normale ed inoltre si ricavano le formule esplicite per la somma di due punti appartenenti ad una cubica. Nel capitolo cinque si iniziano a studiare i punti di ordine finito per una curva ellittica con la legge di gruppo dove l'origine è un flesso: vengono descritti e studiati i punti di ordine 2 e quelli di ordine 3. Infine, nel sesto capitolo si studiano i punti razionali di ordine finito qualsiasi: viene introdotto il concetto di discriminante di una cubica e successivamente viene enunciato e dimostrato il teorema di Nagell-Lutz.