Elementare Zahlentheorie: Blatt 8
2016-06-14Aufgabe 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.