Elementare Zahlentheorie: Blatt 8

Aufgabe 1

Standardmäßig gibt es in Sage nur eine symbolische Variable. Wir legen also zunächst zwei neue Variablen x1 und x2 an (die von Sage als x_1 bzw. x_2 ausgegeben und per LaTeX in \(x_1\) bzw. \(x_2\) übersetzt wird, wenn man die Option Typeset bei Sage aktiviert).

# Setze x = (x1, x2)
x = x1, x2 = var("x_1 x_2")
# und entsprechend u = (u1, u2).
u = u1, u2 = (sin(pi/2*x1)/cos(pi/2*x2), sin(pi/2*x2)/cos(pi/2*x1))
# Die Jacobideterminante ist also
D = jacobian(u, x).det(); D

was Sage als \[ \frac{1}{4} , \pi^{2} - \frac{\pi^{2} \sin\left(\frac{1}{2} , \pi x_{1}\right)^{2} \sin\left(\frac{1}{2} , \pi x_{2}\right)^{2}}{4 , \cos\left(\frac{1}{2} , \pi x_{1}\right)^{2} \cos\left(\frac{1}{2} , \pi x_{2}\right)^{2}} \] ausgibt. Andererseits ist \[ 1-u_1^2u_2^2=1-\frac{\sin\left(\frac12,πx_1\right)^2\sin\left(\frac12,πx_2\right)^2}{\cos\left(\frac12,πx_1\right)^2\cos\left(\frac12,πx_2\right)^2} \] Also ist

(D / (1-u1^2*u2^2)).full_simplify()

das gesuchte Ergebnis \(\frac14\pi^2\).

Aufgabe 4

Zur Veranschaulichung und zum Testen wählen wir zunächst einen primitiven Vektor

b = vector([132, 162, 43, 72, 25, 341])
# Sicherstellen, das der Vektor primitiv ist
assert(gcd(b) == 1)

Nun der Code, der zu einem solchen Vektor eine in \(\mathrm{GL}(n,\mathbb{Z})\) invertierbare Matrix konstruiert:

def unimodular_matrix_with_column(column):
    # Erweitere die Einheitsmatrix über ℤ um die gegebene Spalte.
    #
    # Spalten kann man in Sage nicht zu einer Matrix hinzufügen, daher fügen
    # wir den gegebenen Vektor als Zeile ein und transponieren das Ergebnis.
    M = matrix.identity(ZZ, len(column)).insert_row(0, column).transpose()

    # Solange die erste Spalte nicht `n` nur einen von Null verschiedenen
    # Eintrag hat:
    while sum(M.column(0)[1:]) != 0:
        # Sortiere die Matrix nach der 1. Spalte (ändert höchstens das
        # Vorzeichen der Determinante)
        M = matrix(sorted(M.rows(), reverse=True))

        i = m = -1
        for j in range(len(M.rows())-1, -1, -1):
            r = M.row(j)

            # Finde die Zeile mit dem kleinsten positiven Eintrag
            if r[0] == 0:
                continue
            if i == -1:
                i = j
                m = r[0]

            # Reduziere nun den 1. Eintrag der darüber liegenden Zeilen modulo m
            if j != i and M.row(j)[0] >= m:
                M.add_multiple_of_row(j, i, -(M.row(j)[0]//m))
                # Dies ändert die Determinante nicht, M (ohne die 1. Spalte)
                # ist also in jedem Schritt in GL(n,ℤ).

    # Das Ergebnis ist die Inverse der konstruierten Matrix ohne die 1. Spalte.
    return M.matrix_from_columns([1..len(column)]).inverse()

Testen wir das ganze:

A = gcd_matrix(b)
assert(abs(det(A)) == 1)
assert(A.column(0) == b)
A

Damit erhalten wir in diesem Fall \[ A = \begin{pmatrix} 132 & 0 & 5 & 0 & 58 \\ 43 & 1 & 1 & 0 & 19 \\ 75 & 0 & 3 & 1 & 33 \\ 25 & 0 & 1 & 0 & 11 \\ 341 & 0 & 13 & 0 & 150 \end{pmatrix} \]

Aufgabe 5

Zunächst einmal ist klar, dass die gesuchte Zahl der Koeffizient von \(x^{10000\cdot 100}\) in der Potenzreihenentwicklung von \[ \frac1{(1-x^1)(1-x^2)(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})(1-x^{100})(1-x^{200})} \] um \(0\) ist. Diesen berechnet man geschickterweise über das (Cauchy-)Produkt der Reihen \[ \sum_{i=0}^\infty x^i,\quad \sum_{i=0}^\infty x^{2i},\quad \sum_{i=0}^\infty x^{5i},\quad\ldots,\quad \sum_{i=0}^\infty x^{200i}. \] Das ist zu viel Aufwand, um es per Hand zu machen. Per Computer kann man das aber leicht erledigen:

denominations = [1, 2, 5, 10, 20, 50, 100, 200]

def count_combinations(value, denom=denominations):
    """Berechne die Anzahl der Möglichkeiten, `value` als
    ℤ_{≥0}-Linearkombination der Werte aus `denom` zu schreiben."""

    c = [0]*(value+1)
    c[0] = 1

    for k in denom:
        for i in [0..value-k]:
            c[k+i] += c[i]

    return c[value]

Das gesuchte Ergebnis \(99\,341\,140\,660\,285\,639\,188\,927\,260\,001\) erhalten wir nun durch

count_combinations(10000*100)

Das Problem, eine Zahl als \(\mathbb{Z}_{\ge 0}\)-Linearkombination von gegebenen Zahlen mit möglichst kleiner Koeffizientensumme zu schreiben heißt auch change-making problem.