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