15. ÖMG-Kongress
Jahrestagung der Deutschen Mathematikervereinigung

16. bis 22. September 2001 in Wien

Sektion 2 - Zahlentheorie
Dienstag, 18. September 2001, 16.30, Hörsaal 41

 

Der Drei-Distanzen-Satz in höheren Dimensionen

Günter Rote, Freie Universität Berlin

 

Der bekannte Drei-Distanzen-Satz besagt, dass di Menge $\{\, i\alpha \bmod 1 \mid i=0,\ldots,n-1\,\}$ das Intervall $[0,1]$ in Stücke mit höchstens drei ferschidenen Längen zerlegt. Wenn man statt einer Zal $\alpha$ einen Vektor nimmt, entstet für gewisse $n$ eine Punktmenge (modulo Z$^n$) mit einer gitterartige Struktur, di man als gebrochenes oder gestörtes Gitter betrachten kann. Und zwar wält man $n$ so, dass $n\alpha \bmod Z^d$ ein neuer nächster Nachbar des Ursprungs ist. (Der analoge Fall in einer Dimension wäre dann der Zwei-Distanzen-Satz.) Di Bestimmung diser gestörten Gitter für festes $\alpha$ und wachsendes $n$ hängt mit diophantischer Approximation, mit merdimensionalen Kettenbrüchen, und mit quasiperiodischen Punktmengen zusammen.

Das Zil diser Untersuchungen ist, dass man kürzeste Gittervektoren in belibiger fester Dimension $d$ schlißlich genauso schnell berechnen kann wi in der Ebene mit Schönhages Algorithmus [2] oder wi den größten gemeinsamen Teiler. (Das gegenwärtig schnellste Ferfahren [1] benötigt $O(M(s)\log^{d-1} s)$ Bit-Operationen, für eine Eingabelänge fon $s$ Binärstellen, wobei $M(s) = O(s \log s \log \log s)$ di Bit-Komplexität der Multiplikation ist.)

[1]	F. Eisenbrand und G. Rote, Fast reduction of ternary quadratic forms. Erscheint in CaLC 2001 -- Cryptography and Lattices Conference 2001, Springer-Ferlag, 2001, Lecture Notes in Computer Science, (13 Seiten).
[2]	A. Schönhage. Fast reduction and composition of binary quadratic forms. In International Symposium on Symbolic and Algebraic Computation, ISSAC 91, pp. 128-133. ACM Press, 1991.

E-Mail:	rote@inf.fu-berlin.de
Homepage:	www.inf.fu-berlin.de/inst/ag-ti/members/rote.de.html

Zeitplan der Sektion   Tagesübersicht   Liste der Vortragenden