Projekt:Minkowski Gitterpunktsatz/Animationen

Die Animationen sind im Rahmen eines Studienprojektes im Bereich der Zahlentheorie bei Prof. Dr. Holger Brenner entstanden.

Alle Animationen basieren auf dem Gitterpunktsatz von Minkowski:

Satz 1

Es sei ${}\Gamma$ ein Gitter im ${}\mathbb {R} ^{n}$ mit Grundmasche ${}{\mathfrak {M}}$ . Es sei ${}T$ eine konvexe, kompakte, zentralsymmetrische Teilmenge in ${}\mathbb {R} ^{n}$ , die zusätzlich die Volumenbedingung

{}\operatorname {Vol} (T)\geq 2^{n}\operatorname {Vol} ({\mathfrak {M}})\,

erfülle. Dann enthält ${}T$ mindestens einen von ${}0$ verschiedenen Gitterpunkt.

Der Beweis zu diesem Satz beruht darauf, dass die Menge ${}T$ entlang verdoppelter Grundmaschen des Gitters in Teilmengen ${}T_{i}$ zerschnitten wird, welche dann in eine Grundmasche verschoben werden. Wenn sich in dieser nun mindestens zwei ${}T_{i}$ schneiden, was insbesondere garantiert ist, wenn ${}Vol(T)\geq 2^{n}Vol({\mathfrak {M}})$ ist, enthält ${}T$ mindestens einen Gitterpunkt, ansonsten nicht. Die folgenden Animationen zeigen einige Beispiele dafür im ${}\mathbb {R} ^{2}$ :

Ein Parallelogramm ohne innere Gitterpunkte
Eine Ellipse mit inneren Gitterpunkten
Ein Polygon mit inneren Gitterpunkten

Ein wichtiges Resultat des Gitterpunktsatzes ergibt sich in der Betrachtung von quadratischen Zahlbereichen:

Satz 2

Es sei ${}D\neq 0,1$ eine quadratfreie Zahl, sei ${}A_{D}$ der zugehörige quadratische Zahlbereich mit Diskriminante ${}\triangle$ . Es sei ${}{\mathfrak {a}}\neq 0$ ein Ideal.

Dann gibt es ein ${}f\in {\mathfrak {a}}$ , ${}f\neq 0$ , mit der Eigenschaft

${}{|N(f)|}\leq {\begin{cases}{\frac {2}{\pi }}{\sqrt {{|}\triangle {|}}}N({\mathfrak {a}})&{\text{ bei }}\,D<0,\\{\frac {1}{2}}{\sqrt {{|}\triangle {|}}}N({\mathfrak {a}})&{\text{ bei }}\,D>0\,.\end{cases}}\,$

Der gesamte Beweis des Satzes ist hier zu finden.

Für die Animationen ist relevant, wie das Gitter von einem Ideal eines Zahlbereiches dargestellt werden kann, insbesondere also zuerst, wie das Gitter eines Zahlbereiches aussieht. Der größte Unterschied ergibt sich dabei aus dem Rest von ${}D$ modulo 4:

Lemma 3

Es sei ${}D\neq 0,1$ eine quadratfreie Zahl und ${}A_{D}$ der zugehörige quadratische Zahlbereich.

Dann gilt

$A_{D}={\mathbb {Z} }[{\sqrt {D}}],{\text{ wenn }}D=2,3\mod 4$

und

$A_{D}={\mathbb {Z} }[{\frac {1+{\sqrt {D}}}{2}}],{\text{ wenn }}D=1\mod 4.$

Das Gitter von ${}A_{D}$ in ${}\mathbb {R} ^{2}$ wird also von ${}(1,0)$ und ${}(0,{\sqrt {D}})$ bzw. ${}({\frac {1}{2}},{\frac {\sqrt {D}}{2}})$ aufgespannt, eine Grundmasche würde sich entsprechend beispielsweise durch das Parallelogramm ergeben, welches von ${}(0,0)$ aus durch diese beiden Punkte aufgespannt wird. Ein Ideal ${}{\mathfrak {a}}$ kann in einem quadratischen Zahlbereich immer in der Form ${}(a,\alpha +\beta \omega )$ mit ${}a,\alpha ,\beta \in \mathbb {Z}$ dargestellt werden, das Gitter in ${}\mathbb {R} ^{2}$ wird dann über ${}(a,0)$ und ${}(\alpha ,\beta {\sqrt {D}})$ bzw. ${}(\alpha +{\frac {\beta }{2}},\beta {\frac {\sqrt {D}}{2}})$ aufgespannt.

Die Idee des Beweises ist nun, dass man eine Menge, die die Bedingungen des Gitterpunktsatzes (konvex, kompakt, zentralsymmetrisch, Volumen größer als das der Grundmasche) definiert, welche dementsprechend einen Gitterpunkt enthält, für die dann die gewünschte Normabschätzung aus Satz 2 vorliegt. Für ${}D<0$ wählt man dafür einen Kreis um den Nullpunkt mit Radius ${}{\sqrt {{\frac {2}{\pi }}{\sqrt {|\triangle |}}N({\mathfrak {a}})}}$ und für ${}D>0$ wählt man ein Quadrat mit den Eckpunkten ${}(\pm {\sqrt {c}},\pm {\sqrt {c}})$ mit ${}c={\frac {1}{2}}{\sqrt {|\triangle |}}N({\mathfrak {a}})$ .

Um die Unterschiede zwischen zum einen dem orthogonalen Gitter für ${}D=2,3\mod 4$ und dem schiefen Gitter für ${}D=1\mod 4$ sowie den unterschiedlichen Formen, die im Beweis genutzt werden, darzustellen, werden in den folgenden Animationen für das Ideal jeweils die Parameter ${}a=2,\alpha =1$ und ${}\beta =1$ verwendet. Der Code ist zudem so ausgelegt, dass die Parameter ${}D,a,\alpha$ und ${}\beta$ einfach in Zeile 167 (def construct(...)) verändert werden können und so andere Zahlbereiche und Ideale ausprobiert werden können, zudem werden Ideale - wenn möglich - vereinfacht. Gegebenenfalls muss das Fenster in Zeile 163 allerdings mit angepasst werden.

Python-Skript

from manim import config
from manim import *
import numpy as np

def generate_lattice(D: int, N: int = 4):
    """
    Erzeugen aller nur von der Wahl des Zahlbereichs abhängigen Werte (Determinante, Basis, Punkte und Gitter des Zahlbereichs)
    """

    # Berechnen von Basis und Diskriminante
    if D == 0:
        raise ValueError("D darf nicht 0 sein.")
    if D == 1:
        raise ValueError("D darf nicht 1 sein.")
    if D % 4 in (2, 3):
        # erzeugt ein orthogonales Gitter
        basis = np.array([[1, 0, 0], [0, np.sqrt(abs(D)), 0]])
        disc = 4*D
    elif D % 4 == 1:
        # erzeugt ein schiefes Gitter
        basis = np.array([[1, 0, 0], [0.5, np.sqrt(abs(D)) / 2, 0]])
        disc = D
    else:
        # Wenn D % 4 == 0 gilt, kann D nicht quadratfrei sein und wird dementsprechend ausgeschlossen
        raise ValueError("Unerwarteter D-Wert")

    # Erzeugen des Gitters von A_D
    lines1 = VGroup(*[
        Line(
            start=(-N*2)*basis[1] + k*basis[0],
            end=(N*2)*basis[1] + k*basis[0],
            stroke_opacity=0.3,
            color=GREEN
        )
        for k in range(-N, N+1)
    ])
    lines2 = VGroup(*[
        Line(
            start=(-N*2)*basis[0] + k*basis[1],
            end=(N*2)*basis[0] + k*basis[1],
            stroke_opacity=0.3,
            color=GREEN
        )
        for k in range(-N, N+1)
    ])

    # Alle Gitterpunkte
    points = [
        m * basis[0] + n * basis[1]
        for m in range(-N, N + 1)
        for n in range(-N, N + 1)
    ]
    

    return disc, points, basis, lines1, lines2

def ggT(a,b):
    if a == 0:
        return b
    if b == 0:
        return a 
    if a==b:
        return a
    divider = 1
    for i in range(1, min(abs(a),abs(b))+1):
        if a % i == 0 and b % i == 0:
            divider = i
    return divider

def clean_ideal_points(points, N):
    """
    Löscht die Punkte, die entweder außerhalb des Sichtbereichs liegen oder doppelt vorkommen.
    """
    s = set()
    uniq = []

    for p in points:
        # schränkt die Punkte auf den Sichtbereich ein
        if not (-N/2 <= p[0] <= N/2 and -N/2 <= p[1] <= N/2):
            continue
        
        # löscht die Duplikate
        key = (round(p[0], 9), round(p[1], 9), round(p[2], 9))
        if key not in s:
            s.add(key)
            uniq.append(p)

    return uniq

def ideal(N: int, a: int, alpha: int, beta: int, D: int, basis: np.array =[[1,0,0],[0,1,0]]):
    """
    Erzeugen aller Werte, die von der Wahl des Ideals abhängen (Norm, Basis und Punkte des Ideals), 
    zudem wird geprüft, ob das Ideal ein Hauptideal ist. 
    Da hier nur mit quadratischen Zahlbereichen gearbeitet wird, wird jedes Ideal von maximal 2 Elementen erzeugt.
    """

    # Vorarbeiten für die Berechnungen
    if D % 4 == 1:
        norm_alphabeta = int(abs((alpha+0.5*beta)**2-(beta**2)*D/4))
    else:
        norm_alphabeta = int(abs(alpha**2-(beta**2)*D))

    x_fact = int(norm_alphabeta/ggT(alpha, beta)) # Das kleinste x>0, für das [x,0,0] im Ideal liegt

    is_principal_ideal = False
    if a % x_fact == 0: 
        # Wenn [a,0,0] im von [alpha,beta,0] erzeugten Ideal liegt, ist das Ideal ein Hauptideal
        is_principal_ideal = True
    
    if is_principal_ideal == False:
        if ggT(norm_alphabeta, int(a**2)) == 1:
            # In diesem Fall enthält das Ideal den gesamten Zahlbereich
            ideal_norm = 1
        else:
            ideal_norm = abs(a*beta)
    else:
        ideal_norm = norm_alphabeta

    # Bestimmen der Idealpunkte
    ideal_points = []
    for i in range(-2*N, 2*N+1):
        for j in range(-2*N, 2*N+1):
            ideal_points.append(i*a*basis[0]+j*a*basis[1])
            if D % 4 == 1:
                ideal_points.append((i*alpha+j*beta*(D-1)/4)*basis[0] + (i*beta+j*alpha+j*beta)*basis[1])
            else:
                ideal_points.append((i*alpha+j*beta*D)*basis[0] + (i*beta+j*alpha)*basis[1])
    
    # Bei von zwei Elementen erzeugten Idealen kann es sein,
    # dass nicht alle Punkte des Ideals durch das Multiplizieren mit den einzelnen Basiselementen
    # erfasst werden.
    ideal_helper = []
    for p in ideal_points:
        for n in range(1, int(max(ideal_norm, norm_alphabeta))+1):
            ideal_helper.append(p+[n*a,0,0])
    
    for p in ideal_helper:
        ideal_points.append(p)

    ideal_points = clean_ideal_points(ideal_points, N)

    """
    Berechnen der Idealbasis. 
    Für den Fall, dass a=0 gesetzt wird (also ein Hauptideal vorliegt),
    ist der erste Vektor zwar theoretisch ein Erzeuger von einem Teil des Ideals 
    (aber für das gesamte Ideal eben irrelevant),
    realistisch ist er aber dafür da, um die Grundmasche zu erzeugen.
    """
    ideal_basis = basis.copy()
    if ideal_norm == 1:
        ideal_basis = basis.copy()
    elif a != 0:
        ideal_basis[0] = basis[0]*a
        ideal_basis[1] = basis[0]*alpha+basis[1]*beta
    else:
        ideal_basis[0] = basis[0]*x_fact
        ideal_basis[1] = basis[0]*alpha+basis[1]*beta
    

    return ideal_basis, ideal_norm, ideal_points, is_principal_ideal

# Einstellen des Fensters
config.frame_width = 14

class MinkowskiZB(Scene):
    # Hier wird sowohl der Zahlbereich, als auch das Ideal ausgewählt
    def construct(self, D=-3, a=2, alpha=1, beta=1):
        

        N=config.frame_width

        # Standartgitter vom Z^2, zur Orientierung        
        grid = NumberPlane(
            x_range=[-N, N, 1],
            y_range=[-N, N, 1],
            background_line_style={"stroke_color": GRAY, "stroke_opacity": 0.25}
        )
        self.add(grid)
        self.wait(0.4)
        

        # Generieren des Zahlbereichs
        disc, points, base_basis, lines1, lines2 = generate_lattice(D, N) 
        
        # Generieren des Ideals
        basis, ideal_norm, ideal_points, is_principal_ideal = ideal(N, a, alpha, beta, D, base_basis)
        # Definieren der Verschiebungsrichtungen
        ups,rights = [UP*basis[1][1]*2+RIGHT*basis[1][0]*2, RIGHT*basis[0][0]*2]

        # Gitter des Zahlbereichs einfügen
        self.add(lines1)
        self.wait(0.4)

        self.add(lines2)
        self.wait(0.4)

        # Punkte des Zahlbereiches einfügen
        lattice = VGroup(*[
            Dot(p, radius=0.07, color=BLUE)
            for p in points
        ])
        self.add(lattice)

        # Beschriften von x- und y-Achse des Standartgitters zur Orientierung
        labels_x = VGroup()
        labels_y = VGroup()
        for i in range(-N, N+1):
            label_x = MathTex(f"{i}", color=WHITE).scale(0.5).next_to([i-0.2, 0, 0], DOWN, buff=0.1)
            labels_x.add(label_x)
            if i != 0:
                label_y = MathTex(fr"{i}\sqrt{{{D}}}", color=WHITE).scale(0.5).next_to([0, i*np.sqrt(abs(D))-0.2, 0], LEFT, buff=0.1)
                labels_y.add(label_y)
        self.add(labels_x, labels_y)
        self.wait(0.4)

        # Hervorheben des Ideals
        ideal_lattice = VGroup(*[
            Dot(p, radius=0.08, color=YELLOW)
            for p in ideal_points
        ])
        self.add(ideal_lattice)
        self.wait(0.4)

        # Erzeugen der Legende
        if ideal_norm == 1:
            if D % 4 != 1:
                legend = VGroup(
                    MathTex(rf"ZB:\, A_{{{D}}}=\mathbb{{Z}}[\sqrt{{{D}}}]", color = BLUE),
                    MathTex(rf"Ideal:\, (1)", color = YELLOW)
                ).arrange(DOWN, aligned_edge=LEFT).to_corner(UL)
            else:
                legend = VGroup(
                    MathTex(rf"ZB:\, A_{{{D}}}=\mathbb{{Z}}[\omega],", color = BLUE),
                    MathTex(rf"\omega = \frac{{1+\sqrt{{{D}}}}}{{2}}", color = BLUE),
                    MathTex(rf"Ideal:\, (1)", color = YELLOW)
                ).arrange(DOWN, aligned_edge=LEFT).to_corner(UL)
        elif D % 4 != 1:
            if is_principal_ideal == True:
                legend = VGroup(
                    MathTex(rf"ZB:\, A_{{{D}}}=\mathbb{{Z}}[\sqrt{{{D}}}]", color = BLUE),
                    MathTex(rf"Ideal:\, ({alpha}+{beta}\sqrt{{{D}}})", color=YELLOW)
                ).arrange(DOWN, aligned_edge=LEFT).to_corner(UL)
            else:
                legend = VGroup(
                    MathTex(rf"ZB:\, A_{{{D}}}=\mathbb{{Z}}[\sqrt{{{D}}}]", color = BLUE),
                    MathTex(rf"Ideal:\, ({a}, {alpha}+{beta}\sqrt{{{D}}})", color=YELLOW)
                ).arrange(DOWN, aligned_edge=LEFT).to_corner(UL)
        else:
            if is_principal_ideal == True:
                legend = VGroup(
                    MathTex(rf"ZB:\, A_{{{D}}}=\mathbb{{Z}}[\omega],", color = BLUE),
                    MathTex(rf"\omega = \frac{{1+\sqrt{{{D}}}}}{{2}}", color=BLUE),
                    MathTex(rf"Ideal:\, ({alpha}+{beta}\omega)", color=YELLOW)

                ).arrange(DOWN, aligned_edge=LEFT).to_corner(UL)
            else:
                legend = VGroup(
                    MathTex(rf"ZB:\,  A_{{{D}}}=\mathbb{{Z}}[\omega],", color = BLUE),
                    MathTex(rf"\omega = \frac{{1+\sqrt{{{D}}}}}{{2}}", color=BLUE),
                    MathTex(rf"Ideal:\, ({a}, {alpha}+{beta}\omega)", color=YELLOW)
                ).arrange(DOWN).to_corner(UL)
          
        box = SurroundingRectangle(legend, buff=0.2, stroke_color=WHITE, 
                                   fill_color=BLACK, fill_opacity=1)
        self.add(box, legend)

        # Grundmasche einzeichnen
        masche = Polygon(*[
            ORIGIN,
            basis[0],
            basis[0]+basis[1],
            basis[1],
        ], color=RED, fill_opacity=0.05)
        self.add(masche)
        self.wait(1.5)
        
        # Verdoppeln der Grundmasche
        doppelmasche = Polygon(*[
            ORIGIN,
            basis[0]*2,
            (basis[0]+basis[1])*2,
            basis[1]*2,
        ], color=RED, fill_opacity=0.05)
        self.remove(masche)
        self.add(doppelmasche)
        self.wait(1.5)

        # Erzeugen der Form, die geshiftet wird
        if D < 0:
            form = Circle(radius=np.sqrt((2/np.pi)*np.sqrt(abs(disc))*ideal_norm))
        else:
            form = Square(side_length=2*np.sqrt(0.5*np.sqrt(abs(disc))*ideal_norm))
        self.add(form)
        # Hervorheben der Idealpunkte, die durch den Satz nachgewiesei eine wie gefordert kleine Norm haben
        intercepts = []
        if D < 0:
            for p in ideal_points:
                if np.sqrt(p[0]**2+p[1]**2) <= np.sqrt((2/np.pi)*np.sqrt(abs(disc))*ideal_norm):
                    intercepts.append(p)
        else:
            for p in ideal_points:
                if (abs(p[0]) <= np.sqrt(0.5*np.sqrt(abs(disc))*ideal_norm) and abs(p[1]) <= np.sqrt(0.5*np.sqrt(abs(disc))*ideal_norm)):
                    intercepts.append(p)
        intercept_points = VGroup(*[
            Dot(p, radius=0.09, color=RED)
            for p in intercepts
        ])
        self.add(intercept_points)


        # Zerschneiden
        pieces = VGroup()
        shifts = []
        for i in range(-4,4):
            for j in range(-4,4):
                mod = ups*i+rights*j
                piece = Intersection(Polygon(*[
                    ORIGIN+mod, basis[0]*2+mod, (basis[0]+basis[1])*2+mod, basis[1]*2+mod]),
                    form, color=BLUE, fill_opacity=0.2)
                pieces.add(piece)
                shifts.append(-mod)
        
        self.remove(form)
        self.add(pieces)
        self.wait(0.8)

        #  Verschieben in die Grundmasche
        self.play(*(p.animate.shift(s) for p, s in zip(pieces, shifts)), run_time = 2)
        self.wait(3)

Zahlbereich ${}A_{5}$
Zahlbereich ${}A_{3}$
Zahlbereich ${}A_{-3}$
Zahlbereich ${}A_{-5}$

Da die Zahlbereiche ${}A_{3}$ , ${}A_{5}$ und ${}A_{-3}$ alle faktoriell sind, wird in diesen jedes Ideal von nur einem Element erzeugt (und ist somit ein Hauptideal), so auch das hier verwendete: In ${}A_{5}$ und ${}A_{-3}$ ist das verwendete Ideal sogar der gesamte Zahlbereich, wodurch die Grundmasche des Ideals kleiner wird, die Aussage des Satzes - wie in der Animation sichtbar - aber natürlich bestehen bleibt.