Impressum

Der Computeralgebra-Rundbrief wird herausgegeben von der Fachgruppe Computeralgebra der GI in Kooperation mit der DMV und der GAMM(verantwortlicher Redakteur: Prof. Dr. Michael Cuntz, car@mathematik.de)

Der Computeralgebra-Rundbrief erscheint halbjährlich, Redaktionsschluss 15.02. und 15.09. ISSN 0933-5994. Mitglieder der Fachgruppe Computeralgebraerhalten je ein Exemplar dieses Rundbriefs im Rahmen ihrer Mitgliedschaft. Fachgruppe Computeralgebra im Internet:http://www.fachgruppe-computeralgebra.de.

Konferenzankündigungen, Mitteilungen, einzurichtende Links, Manuskripte und Anzeigenwünsche bitte an den verantwortlichen Redakteur.

GI (Gesellschaft fürInformatik e.V.)WissenschaftszentrumAhrstr. 4553175 BonnTelefon 0228-302-145Telefax 0228-302-167gs@gi-ev.dehttp://www.gi-ev.de

DMV (Deutsche Mathematiker-Vereinigung e.V.)Mohrenstraße 3910117 BerlinTelefon 030-20377-306Telefax 030-20377-307dmv@wias-berlin.dehttp://www.dmv.mathematik.de

GAMM (Gesellschaft für AngewandteMathematik und Mechanik e.V.)Technische Universität DresdenInstitut für Statik und Dynamik derTragwerke01062 DresdenTelefon 0351-463-33448Telefax 0351-463-37086GAMM@mailbox.tu-dresden.dehttp://www.gamm-ev.de

Computeralgebra-Rundbrief

Nr. 55 Oktober 2014

InhaltsverzeichnisImpressum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2Inhalt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3Mitteilungen der Sprecher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Tagungen der Fachgruppe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5Themen und Anwendungen der Computeralgebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6Hintertüren und Schwächen im kryptographischen Standard SP 800-90A (M. Fischlin) . . . . . . . . . . . 6GTPack - ein Mathematica Paket für Gruppentheorie in der Festkörperphysik (M. Geilhufe, W. Hergert) . . 11Superstringtheorie und elliptische Kurven (J. Keitel) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15Computeralgebra in der Schule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193D-Grafik in der Schule mit Computeralgebra (J.-H. Müller, U. Schürmann) . . . . . . . . . . . . . . . . 19Neues über Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22The SYMBOLICDATA Project (H.-G. Gräbe, S. Johanning, A. Nareike) . . . . . . . . . . . . . . . . . . . 22Shared Memory Concurrency for GAP (R. Behrends) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27The GAP package SingularInterface

(M. Barakat, M. Horn, F. Lübeck, O. Motsak, M. Neunhöffer, H. Schönemann) . . . . . . . . . . . . . 29Berichte über Arbeitsgruppen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33Arbeitsgruppe in Osnabrück (Brenner, Bruns, Römer, Spindler) . . . . . . . . . . . . . . . . . . . . . . . 33Promotionen in der Computeralgebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34Berichte von Konferenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36Hinweise auf Konferenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Fachgruppenleitung Computeralgebra 2014-2017 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

Mitteilungen der Sprecher

Liebe Mitglieder der Fachgruppe Computeralgebra,

die Herbstsitzung der Fachgruppenleitung fand am 26. September 2014 an der Leibniz Universität Han-nover statt.

Zu den Neuerungen innerhalb der Fachgruppe zählt der Rundbrief 55, den Sie in den Händen halten.Neu daran ist aber nicht nur der Inhalt, sondern, wie auch schon beim Rundbrief 54, die Herstellung.Seit dem Frühjahr geben wir den Rundbrief bei einer neuen Druckerei in Auftrag. Der Vorteil liegtbei gleichbleibender Qualität in einer deutlichen Kostenersparnis. Wir danken Thomas Hahn, der denWechsel energisch vorangetrieben hat. Dies gibt uns einen größeren Spielraum bei der Förderung jungerMitglieder und anderen Aktivitäten.

Die Umstellung der Mitgliederverwaltung von der DMV auf die GI, über die schon im Rundbrief 54berichtet wurde, ist nun erfolgreich abgeschlossen. Die Fachgruppenleitung dankt den Geschäftsstellender DMV und der GI ganz herzlich für ihren Einsatz und die reibungslose Durchführung.

Die Mitgliederzahl der Fachgruppe liegt zur Zeit etwas unter 400. Damit sie bald über 400 liegt, wä-re es hilfreich, wenn Sie potentielle Interessenten auf die Mitgliedschaft in der Fachgruppe aufmerksammachen könnten. Die Ermöglichung einer kostenfreien, befristeten Mitgliedschaft für Studierende undDoktoranden wurde auf dem letzten Fachgruppenleitungstreffen angedacht. Über die weitere Entwick-lung halten wir sie auf dem Laufenden.

Innerhalb der GI gibt es zwei Neuigkeiten. Thomas Wilke (Christian-Albrechts-Universität zu Kiel)wurde Anfang des Jahres zum Sprecher des Fachbereichs Grundlagen der Informatik der GI, dem unsereFachgruppe angehört, gewählt. Herr Wilke nahm an der Computeralgebra-Tagung im Mai teil, wo ihnMitglieder der Fachgruppe kennenlernen konnten. Auf Initiative von Herrn Wilke findet Anfang 2015 einTreffen der Sprecher der Fachgruppen im Fachbereich Grundlagen der Informatik zwecks Vernetzungder Fachgruppen statt.

In der GI wird aktuell auch die Einrichtung einer neuen Fachgruppe „NumSim“ diskutiert. DieseFachgruppe soll sich mit den Themen Numerische Simulation und High Performance Computing be-schäftigen. Die Arbeitsschwerpunkte können unter anderem die Entwicklung und Parallelisierung nume-rischer Algorithmen und die Anwendung neuer Architekturen sowie Hardware sein. Weitere Informatio-nen erhalten Sie von Patrick Diehl (me@diehlpk.de) oder unter der Mailingliste

https://mail.gi-ev.de/mailman/listinfo/numsim

Zum Schluß bitten wir wie immer alle Mitglieder der Fachgruppe, die Rundbrief-Redaktion mit In-formationen, Themenvorschlägen, Beiträgen, Berichte über Promotionen und Habilitationen, Hinweisenauf Bücher, auf Programmpakete und auf Tagungen etc. zu unterstützen.

Da das vorliegende Heft relativ umfangreich ist, wollen wir diese Mitteilungen nicht weiter in dieLänge ziehen und Sie herzlich zum Weiterblättern einladen.

Florian Heß Gregor Kemper

4

Tagungen der Fachgruppe

Tagung in Kassel, 2014

Tagung der Fachgruppe Computeralgebra in Kassel,15. – 17.05.2014

http://www.fachgruppe-computeralgebra.de/tagung-kassel-2014/

Von 15. bis 17. Mai 2014 fand die sechste Tagung derFachgruppe in Kassel statt. Auch diese Ausgabe der er-folgreichen Konferenzreihe war mit fast 50 Teilnehmerngut besucht.Es gab fünf einstündige Hauptvorträge: Severin Neu-mann (Passau), der Gewinner des Nachwuchspreisesvon 2012, eröffnete die Tagung mit einem Vortrag überparallele und verteilte Algorithmen zur Berechnungvon Gröbnerbasen. Jens Zumbrägel (Dresden) berichte-te über neue Algorithmen für das diskrete Logarithmus-Problem in Körpern kleiner Charakteristik, und Betti-na Eick (Braunschweig) gab einen Überblick über denStand der Forschung in der algorithmischen Gruppen-theorie. Am Abschlusstag zeigte Jan Steffen Müller(Oldenburg) einen Querschnitt durch die Theorie dio-phantischer Gleichungen und diskutierte den Einsatzvon Computeralgebra und geometrischen Methoden beiLösbarkeitsfragen. Raymond Hemmecke (München) re-ferierte über algebraische Methoden in der ganzzahligenOptimierung.

Das Programm wurde durch 20 eingereichte Beiträ-ge, zwei Software-Präsentationen und eine Diskussions-runde über die Fachgruppe und ihre aktuellen Aktivi-

täten vervollständigt. Alle Vortragenden nahmen Rück-sicht auf die heterogene Zusammensetzung des Publi-kums und begannen ihre Präsentationen mit einer all-gemeinverständlichen Einführung in die Thematik. Die-se weitgehende Zugänglichkeit der Beiträge auch fürNicht-Spezialisten wurde allgemein begrüßt.Beim gemeinsamen Abendessen, das am Freitag imRistorante La Piazza stattfand, diskutierten die anwe-senden Mitglieder der Fachgruppenleitung – unterstütztdurch Werner Bley – über die Vortragsbeiträge, umden Nachwuchs-Preisträger auszuwählen, was aufgrundder hohen Qualität zahlreicher Präsentationen schwer-fiel. Schließlich setzte sich Christian Eder (Kaiserslau-tern) mit seinem schönen Vortrag über signatur-basierteGröbnerbasis-Algorithmen durch. Herr Eder hat 2012bei Gerhard Pfister promoviert und danach im Team vonJean-Charles Faugère gearbeitet. Wie gewohnt war mitder Auszeichnung ein Preisgeld von 500 Euro verbun-den und die Einladung, bei der nächsten Tagung derFachgruppe einen Hauptvortrag zu halten.Die Fachgruppe dankt dem Fachbereich Grundlagen derInformatik der GI für das Stiften des Preisgeldes sowieden Sponsoren Additive, Maplesoft und Springer-Verlagfür ihre großzügige Unterstützung. Besonders herzlicherDank gebührt Wolfram Koepf und seinem Team für dieexzellente Organisation der Tagung.

Eva Zerz (Aachen)

5

Themen und Anwendungen der Computeralgebra

Hintertüren und Schwächen imkryptographischen Standard SP 800-90A1

M. Fischlin(TU Darmstadt)

marc.fischlin@cryptoplexity.de

NIST SP 800-90A January 2012

ii

NIST Special Publication 800-90A

Recommendation for Random Number Generation Using Deterministic

Random Bit Generators

Elaine Barker and John Kelsey

Computer Security Division Information Technology Laboratory

C O M P U T E R S E C U R I T Y

January 2012

U.S. Department of Commerce John Bryson, Secretary

National Institute of Standards and Technology Patrick Gallagher, Director Under Secretary of Commerce for Standards and Technology

Die durch Edward Snowden angestoßenen Enthül-lungen liefern seit Juni 2013 immer mehr bemerkens-werte Details darüber, welche Methoden Geheimdienstezur Sammlung und Verwertung von personenbezogenenDaten anwenden. Im vorliegenden Artikel diskutierenwir speziell den Fall des kryptographischen StandardsSP 800-90, bei dem der amerikanische GeheimdienstNSA (National Security Agency) gemäß eines Artikelsder New York Times vorsätzlich Schwächen eingebauthatte. Wir erläutern anhand der mathematischen Details,wie diese Hintertür aussieht und wie die Schwächen ein-zuordnen sind.

Kryptographische StandardsTechnische Standards dienen der Vereinheitlichung vonNormen und Verfahren und sollen dadurch die Inter-operabilität fördern. Auch in der Kryptographie gibtes zahlreiche Standards und Standardisierungsorganisa-tionen. Eine wichtige Institution ist hier neben der In-ternational Organization for Standardization (ISO) undder International Electrotechnical Commission (IEC)das amerikanische National Institute of Standards andTechnology (NIST). NIST setzt mit seiner Reihe „Spe-cial Publications (800 series)“ Standards speziell fürThemen zur Informationssicherheit (siehe [10]). So be-schreiben beispielsweise die Standards SP 800-56A bisSP 800-56C, wie zwei Teilnehmer basierend auf demDiskreten Logarithmus- oder dem Faktorisierungspro-blem einen gemeinsamen kryptographischen Schlüsselaushandeln können.

Die von NIST zunächst nur für die Vereinigten Staa-ten entwickelten Standards etablieren sich auch oft zuinternationalen de-facto-Standards und werden teilwei-se in ISO/IEC-Standards übernommen. Dabei ist be-merkenswert, dass die Standards im Bereich der IT-Sicherheit oft ein weiteres Attribut zugewiesen bekom-men, nämlich, dass standardisierte Verfahren auch be-sondere Sicherheitsgarantien mit sich bringen. Die Er-fahrung hat allerdings gezeigt, dass diese Annahme imAllgemeinen zu optimistisch ist. Dies gilt um so mehr,als wir heute wissen, dass Geheimdienste absichtlichschwache Standards vorgeschlagen haben. Wir betrach-ten hier mit dem Standard SP 800-90 der NIST einensolchen Fall.

Schwächen im Standard SP 800-90Der Standard SP 800-90 beschäftigt sich mit der Erzeu-gung von sogenannten Pseudozufallszahlen, also quasizufälligen Werten. Dieses Konzept wird ausführlicher

1 Dieser Artikel erschien in den DMV-Mitteilungen 2014-0012, S. 18-22. Wiederabdruck mit freundlicher Genehmigung der DeutschenMathematiker-Vereinigung.

6

in Abschnitt diskutiert. Der NIST-Standard SP 800-90bzw. der ergänzende Standard SP 800-90A diskutiertMöglichkeiten, wie man solche Pseudozufallswerte aufvermeintliche sichere Weise genererieren kann. Teiledes NIST-Standards finden sich auch im ISO/IEC Stan-dard 18031:2011 [8] wieder.

Was war passiert?Schon kurz nach Veröffentlichung der ersten Versiondes Standards SP 800-90 im Jahr 2006 – die VersionSP 800-90A ergänzte den ursprünglichen Standard unddie aktuelle Version datiert auf Januar 2012 – wurdeKritik am Standard öffentlich. Wissenschaftliche Arbei-ten [15, 2, 17] aus den Jahren 2006 und 2007 zeig-ten, dass eines der vorgeschlagenen Verfahren, der Pseu-dozufallsgenerator Dual_EC_DRBG, nicht die gewohn-ten Sicherheitsstandards erfüllte. Schon damals ließenKommentatoren wie Bruce Schneier anklingen, dasses sich dabei um absichtlich implementierte Schwä-chen handeln könnte [14]. Tatsächlich bestätigt der ak-tuelle Standard SP 800-90A die Mitarbeit der NSA ander Erstellung, wobei die Zusammenarbeit mit den IT-Sicherheitsexperten der NSA an solchen Standards perse nicht ungewöhnlich ist. Erst im Jahr 2013 wurde imRahmen der Enthüllungen um Edward Snowden durcheinen Artikel der New York Times [12] bestätigt, dassdie NSA Schwächen absichtlich eingebaut hat.

Inzwischen rät NIST selbst explizit von der Verwen-dung des Generators ab [11]. In einigen kommerziel-len Produkten wurde der Generator implementiert, aberbis auf zwei Ausnahmen, dem BSAFE-Toolkit und demData Protection Manager der Firma RSA, nicht als derstandardmäßig verwendete Generator eingesetzt, son-dern nur als Option [3]. Der Generator sollte natürlichnicht mehr verwendet werden. RSA selbst empfiehlt in-zwischen, in dem betroffenen Produkt auf einen ande-ren Generator umzusteigen [4]. Bemerkenswert ist, dassbeide Empfehlungen, sowohl die von NIST als auch dievon RSA, erst nach der Veröffentlichung des Artikelsder New York Times im September 2013 herausgegebenwurden, obwohl die ersten Kritiken an der kryptographi-schen Sicherheit des Dual_EC_DRBG bereits 2006 und2007 veröffentlicht wurden.

Hintergrund: PseudozufallsgeneratorenZufallswerte sind essenziell für die Sicherheit krypto-

graphischer Verfahren. Sie treten an zahlreichen Stel-len in Verfahren auf, angefangen mit der Erzeugungder geheimen Schlüssel, über die Wahl von Initialisie-rungsvektoren für Verschlüsselungen, bis hin zur Ge-nerierung von unvorhersagbaren Fragen in Challenge-Response-Verfahren zur Authentisierung. KlassischeRechner können aber in der Regel keine „echten“ Zu-fallswerte erzeugen, da sie deterministisch arbeiten, al-so ihre Ergebnisse eindeutig vorherbestimmt sind. Diefolgende Aussage, die dem Mathematiker und Informa-tiker John von Neumann zugeordnet wird, fasst diesesDilemma pointiert zusammen:

Anyone who considers arithmetical methodsof producing random digits is, of course, in astate of sin. (John von Neumann)

Der Entropie-Begriff von Shannon [16], den er inseiner wegweisenden Arbeit von 1948 über Informati-onstheorie einführte, bestätigt diese Sichtweise. Für eine(diskrete) Zufallsvariable X ist die Shannon-Entropiedefiniert als

H(X) := �X

x

Prob[X = x] · log2 Prob[X = x],

wobei x die möglichen Werte von X durchläuft. Intuitivgibt die Shannon-Entropie an, wieviele Bits man durch-schnittlich benötigt, um den Ausgang einer Stichprobevon X zu kommunizieren. Die Shannon-Entropie ist ge-nau dann maximal, wenn X uniform verteilt ist.

Für jede Zufallsvariable und jede mathematischeFunktion C (die der Leser hier als einen deterministi-schen Computer ansehen kann) gilt

H(X) � H(C(X)),

wobei C(X) die Zufallsvariable beschreibt, die zuersteine Stichprobe von X wählt und dann C anwendet.Folglich kann kein (deterministischer) Computer imSinne der Shannon-Entropie „zusätzlichen Zufall“ er-zeugen, auch wenn man ihm „etwas Zufall“ in Form vonX zur Verfügung stellt.

Die Kryptographie löst das Dilemma, indem siedie Anforderung an die Zufallswerte abschwächt, undlediglich pseudozufällige Werte verlangt. Pseudozufäl-lige Werte erreichen zwar keine maximale Shannon-Entropie, sehen aber dennoch für alle praktischen Zwe-cke wie echt zufällig aus. In der Kryptographie wirddies formal in die Theorie sogenannter Pseudozufalls-generatoren eingebettet. Ein Pseudozufallsgenerator Gist ein deterministischer (und effizienter) Algorithmus,der eine kurze, echt zufällige Eingabe – üblicherweiseals binäre Zeichenkette r aus der Menge {0, 1}⇤ allerendlichen Bitfolgen kodiert – in eine längere Ausgabetransformiert, sodass diese Ausgabe „wie zufällig“ aus-sieht. Letzteres wird mit Hilfe des Begriffs der Unun-terscheidbarkeit formalisiert, soll hier aber nicht weiterausgeführt werden. Eine Einführung gibt das Buch vonGoldreich [6].

In der Notation der Entropie verlangt man, dass einPseudozufallsgenerator maximale Pseudo-Entropie [7]besitzt. Eine Zufallsvariable X hat Pseudo-Entropie

HHILL(X) � k,

wenn sie ununterscheidbar (im obigen Sinne) von ei-ner Zufallsvariablen Y mit Shannon-Entropie H(Y ) �k ist. Folglich hat ein Pseudozufallsgenerator, derfür n-Bit-Eingaben längere `(n)-Bit-Ausgaben erzeugt,Pseudo-Entropie `(n), während die Shannon-Entropiemaximal n sein kann. Für die meisten kryptographi-schen Anwendungen genügt nachweislich eine hohePseudo-Entropie, um Sicherheit zu gewährleisten.

Ob sichere Pseudozufallsgeneratoren existieren,lässt sich mit gegenwärtigen Methoden nicht nach-weisen. Man kann solche Generatoren aber unter sehrschwachen kryptographischen Annahmen ableiten [7],

7

unter anderem auch unter gängigen Sicherheitsannah-men wie der Schwierigkeit, die diskrete Exponentiati-on effizient zu invertieren (dem sogenannten Diskreten-Logarithmus-Problem). Daher gilt es im Augenblick alsvernünftig, die Existenz solcher Generatoren anzuneh-men. Gleichzeitig muss man aber besondere Vorsichtwalten lassen, wenn man einen Generator entwickelt.

Wie setzen moderne Computer nun solche Pseudo-zufallsgeneratoren ein? Üblicherweise wird der Compu-ter mit einem kurzen, möglichst zufälligen Wert initia-lisiert, beispielsweise durch Messungen von rauschan-fälligen Komponenten während des Starts, oder durch„zufällige“ Eingaben des Anwenders. Bei Bedarf er-zeugt der Generator aus seinem Startwert hinreichendviele Pseudozufallsbits, gibt einen Teil als Ausgabe aus,und aktualisiert gleichzeitig seinen Startwert mit einemanderen Teil der generierten Bits. Die tatsächlichen Ver-fahren variieren dieses Schema auf vielfältige Weise.

Der Generator Dual_EC_DRBGDer Standard SP 800-90 beschreibt verschiedene, ver-meintlich sichere Pseudozufallsgeneratoren. Eine Vari-ante ist der Generator Dual_EC_DRBG, der auf ellipti-schen Kurven beruht.

Elliptische Kurven werden wegen ihrer guten Si-cherheitseigenschaften – kurze Schlüssel und Resistenzgegen bekannte Diskrete Logarithmus-Verfahren – ver-stärkt in der Kryptographie eingesetzt. Im vorliegendenFall wurden im Standard eine Primzahl p sowie die Kon-stanten a und b spezifiziert (z. B. ist p = 2256 � 2224 +2192 + 296 + 1), die eine elliptische Kurve definieren.Die Kurvenpunkte

Ea,b(Fp) =�(x, y) 2 F2

p | y2 = x3 + ax+ b ,

bilden zusammen mit einer entsprechend definiertenAddition eine Gruppe, die für die Werte hier sogar vonprimer Ordnung ist. Die x-Koordinaten von Kurven-punkten können nach Wahl von p mit 256 Bits darge-stellt werden. Der Standard spezifiziert zusätzlich zweiPunkte P = (xP , yP ) und Q = (xQ, yQ), die beideverschieden vom „Punkt im Unendlichen“ O, dem neu-tralen Element der Gruppe, sind. Der Punkt P ist einErzeuger der additiven Gruppe.

Der Dual_EC_DRBG wird mit einem zufälligenStartwert s0 aus Fp initialisiert. Bei Bedarf generiertdas Verfahren 240 Pseudozufallsbits, indem es ausge-hend vom aktuellen Wert si 2 Fp den Kurvenpunkt siPberechnet und si+1 als die x-Koordinate x-coord(siP )des Punktes für die nächste Iteration speichert. Ebensoberechnet das Verfahren den Kurvenpunkt si+1Q undgibt nun die untersten 240 Bits der 256 Bits der x-Koordinate des Punktes (in einer üblichen Binärdarstel-lung) als Pseudozufallsbits aus. Benötigt man mehr Bits,wiederholt man das Verfahren hinreichend oft.

Das Design des Generators beruht auf dem soge-nannten Diffie-Hellman-Entscheidungsproblem. Beimbekannten Schlüsselaustauschverfahren von Diffie undHellman [5] erzeugen die zwei Teilnehmer Alice undBob einen gemeinsamen geheimen Schlüssel in einer el-liptischen Kurve mit Erzeuger P , indem Alice für zufäl-

liges q einen Punkt Q = qP berechnet und Q an Bobsendet, und Bob R = rP für zufälliges r berechnet, undmit R antwortet. Alice kann nun lokal S = qR = (qr)Pberechnen, und Bob ebenfalls S = rQ = r(qP ) =(qr)P , sodass S der gemeinsame Schlüssel wird.

Das klassische Diffie-Hellman-Berechnungsproblem,auf dessen Sicherheit das Diffie-Hellman-Verfahren be-ruht, besagt nun, dass es für einen Angreifer schwie-rig ist, ebenfalls den Schlüssel S aus den ausge-tauschten Daten P,Q,R zu berechnen. Das DH-Entscheidungsproblem fordert nun sogar, dass man denSchlüssel S nicht einmal von einem unabhängig ge-wählten Kurvenpunkt unterscheiden kann: Gegeben vierKurvenpunkte (P,Q,R, S) entscheide man, ob S einunabhängiger und uniform verteilter Punkt ist, oder obS = rQ für R = rP gilt. Beide Probleme, das Berech-nungsproblem und das Entscheidungsproblem, gelten inder Kryptographie als schwierig, und das DH-Verfahrensomit als sicher. Weitere Informationen zu den beidenProblemen findet man in [1].

Im Fall des Generators Dual_EC_DRBG spieltsi+1Q die Rolle der Schlüssels S, der wie zufällig aus-sieht, selbst wenn man P,Q und sogar den in der nächs-ten Iteration des Generators berechneten Wert R =si+1P kennen würde. In diesem Sinne ist das grund-sätzliche Design-Prinzip des Generators plausibel, auchwenn jede Iteration durch zwei Multiplikationen in derelliptischen Kurve wesentlich langsamer als andere be-kannte Generatoren ist. Dass der Generator dennochSchwächen hat, liegt an den Details, wie wir im folgen-den Abschnitt diskutieren.

Schwächen im Generator Dual_EC_DRBGBereits kurz nach Erscheinen des Standards haben dieersten Analysen [15, 2] gezeigt, dass die Ausgaben desDual_EC_DRBG nicht die übliche kryptographische Si-cherheit bieten. Diese Analysen nutzen aus, dass diePunkte der elliptischen Kurve bei Projektion auf die un-tersten 240 Bits der x-Koordinate eben nicht uniformsind: Ein nicht zu vernachlässigender Anteil der Men-ge der Zeichenketten aus 240 Bits kann nicht von sol-chen Punkten getroffen werden. Dieser Schritt, die ein-fache Projektion auf die untersten Bits, schleust alsoSchwächen ein, obwohl die Kurvenpunkte uniform ver-teilt sind. Es ist bemerkenswert, dass hier schon vor Ver-öffentlichung des Standards bessere Verfahren zur Glät-tung der Verteilung bekannt waren (beispielsweise in[7]).

Die Autoren von [15, 2] zeigen, dass sie wegender einfachen Projektion auf die Bits die Ausgabedes Dual_EC_DRBG mit einem Vorteil von ca. 0,1 %gegenüber echt zufälligen Werten erkennen können.Indem sie mehrere Ausgaben untersuchen, lässt sichdieser Vorteil sogar auf einige Prozentpunkte stei-gern. Anders ausgedrückt: Die Pseudo-Entropie desDual_EC_DRBG ist nicht maximal. Zwar gelten Gene-ratoren mit solchen verzerrten Ausgaben in der Krypto-graphie nicht als sicher, dennoch war nicht bekannt, wieman diese Schwäche des Dual_EC_DRBG unmittelbarhätte ausnutzen können, um beispielsweise große Tei-

8

le eines geheimen Schlüssels verlässlich zu berechnen.Wie dies gehen könnte, zeigte die Arbeit von Shumovund Ferguson [17]. Die beiden Autoren bestätigen, dassman bei geschickter Wahl der Punkte P und Q – was fürdie Entwickler des Standards durchaus möglich gewe-sen wäre – die Ausgaben des Generators mit geringemAufwand vorhersagen kann.

Die deterministische Chip-Sicht: Ein G5 inunterschiedlich einfallendem Licht(Sammlung Günter M. Ziegler. Foto: Christoph Eyrich)

Der Angriff von Shumov und Ferguson basiert auffolgender Beobachtung. Da P ein Erzeuger, Q 6= Ound die Ordnung der elliptischen Kurve prim ist, gibtes ein ganzzahliges e mit P = eQ. Shumov und Fer-guson gehen nun davon aus, dass der Angreifer denWert e kennt. Der Angreifer betrachtet dann eine Aus-gabe r 2 {0, 1}240 einer Iteration des Generators, die erbeispielsweise als Teil eines Initialisierungsvektors ei-ner Verschlüsselung oder als Frage in einer Challenge-Response-Authentisierung lernen kann. Er berechnet al-le möglichen 216 = 65.536 Bitfolgen der Länge 256, dieauf r enden. Für jeden dieser Werte testet der Angrei-

fer, ob diese Bitfolge der x-Koordinate eines Punktesauf der elliptischen Kurve entspricht, indem er prüft, obz = x3+ax+ b mod p ein quadratischer Rest in Fp ist.Jedes solche x gibt maximal zwei mögliche Werte füry. Der Gesamtaufwand dafür ist so gering, dass er mitjedem herkömmlichen Rechner zu bewerkstelligen ist.

Der Angreifer erhält so eine Menge von maximal2 ·216 Kurvenpunkten R1, R2, R3, . . . , wobei der „rich-tige“ Punkt si+1Q darin enthalten sein muss. Mit Hilfeder Kenntnis von e kann der Angreifer dann die Punk-te eR1, eR2, eR3, . . . berechnen, sodass darunter auchder Punkt si+1P = si+1(eQ) = e(si+1Q) sein muss.Folglich kennt der Angreifer eine beschränkte Mengevon Punkten, deren x-Koordinate auch den übernächs-ten Zustandswert si+2 = x-coord(si+1P ) des Gene-rators enthält. Würde er den Punkt eindeutig kennen,könnte der Angreifer alle folgenden Ausgaben des Ge-nerators dann exakt vorhersagen! Dazu muss er aber nunlediglich einige weitere Ausgaben des Generators beob-achten, um die Menge der potenziellen Kandidaten aufein Element zu reduzieren. Folglich ist der Generator beiKenntnis von e mit P = eQ vollkommen unsicher.

Der Angriff von Shumov und Ferguson istnicht überraschend, wenn man bedenkt, dassdas DH-Berechnungsproblem und auch das DH-Entscheidungsproblem bei bekanntem e mit P = Qebeide leicht zu lösen sind: Gegeben P,Q = qP,R undeben e, das multiplikative Inverse zu q modulo der be-kannten Gruppenordnung, kann man leicht den Schlüs-sel S = rQ = (rq)P für R = rP berechnen, indemman einfach q aus e berechnet und S = qR bildet.In diesem Sinne „spielt“ der Angreifer dann quasi dieRolle von Alice im DH-Schlüsselaustausch. Nur wennQ nachweislich so bestimmt worden wäre, dass nie-mand effizient e berechen kann, wäre die Sicherheitdes Dual_EC_DRBG gewährleistet. Dass dies nicht derFall war, hat die Veröffentlichung der New York Timesgezeigt.

Wie geht es weiter?Mehr als fünf Jahre nach Bekanntwerden der Schwä-chen, aber erst nach Bestätigung durch die New York Ti-mes, dass die NSA die Spezifikation beeinflusst hat, ra-ten inzwischen sowohl NIST als auch Firmen wie RSAvon der Verwendung des Generators Dual_EC_DRBGab. Man kann daher hoffen, dass in Zukunft keine An-griffe über diese Schwachstelle erfolgen werden.

In einem im Dezember 2013 erschienenen Artikelder Nachrichtenagentur Reuters [9] wurde behauptet,dass die Firma RSA für die Verwendung des schwachenGenerators Dual_EC_DRBG in ihrem BSAFE-Produktvon der NSA bezahlt wurde. Die Firma bestritt dieseVorwürfe umgehend [13]. Eine Klärung steht noch aus.

NIST hat inzwischen den Standard SP 800-90A aufden Status eines „Draft“ zurückgesetzt und im Zeitraumvon September 2013 bis November 2013 um Kommen-tierung gebeten. Das weitere Vorgehen der NIST ist zumZeitpunkt, zu dem dieser Artikel verfasst wurde, nichtbekannt.

9

FazitDie Rolle der NSA bei der Erstellung des StandardsSP 800-90, als auch die weiteren bekannt gewordenenMaßnahmen der Geheimdienste, sind natürlich äußerstbedenklich. Im Fall des Dual_EC_DRBG wurden dieeingebauten Schwächen unmittelbar entdeckt. Dennochblieb der Generator Teil des Standards und wurde auchin Produkten verwendet. Diese Tatsache zeigt – unab-hängig davon, ob Standards bewusst oder unbewussteingebaute Schwächen beinhalten – das Problem heuti-ger Sicherheitsstandards. Sie beruhen in der Regel zwarauf bekannten Sicherheitsprinzipien, fallen aber in ih-ren Sicherheitsbetrachtungen gegenüber Analysen, wiesie in akademischen Veröffentlichungen heute üblichsind, stark ab. Solche wissenschaftlichen Betrachtungenschließen in der Regel sogenannte Reduktionsbeweiseoder ausführliche kryptanalytische Techniken ein, wäh-rend die Sicherheitskriterien von Standards im Allge-meinen vage bleiben. Trotzdem genießen standardisier-te Verfahren einen verblüffenden Vertrauensvorschussbezüglich ihrer Sicherheit, und werden bedenkenlos inProdukten verwendet. Hier sind allerdings nicht nur dieEntwickler von Standards und die Firmen gefordert,sondern auch Kryptographen, um gemeinsam die Si-cherheitsgarantien von kryptographischen Standards zuverbessern.

Literatur[1] Dan Boneh. The decision Diffie-Hellman problem.

volume 1423 of Lecture Notes in Computer Science,pages 48–63. Springer, 1998.

[2] Daniel R. L. Brown and Kristian Gjøsteen. A se-curity analysis of the NIST SP 800-90 elliptic cur-ve random number generator. In CRYPTO, volume4622 of Lecture Notes in Computer Science, pages466–481. Springer, 2007.

[3] Computer Emergency Response Team (CERT). Du-al_EC_DRBG output using untrusted curve con-stants may be predictable. Vulnerability NoteVU#274923, November 2013.

[4] Computer Emergency Response Team (CERT). Du-al_EC_DRBG output using untrusted curve con-stants may be predictable. RSA Security, Inc. In-formation to Vulnerability Note VU#274923, Sep-tember 2013.

[5] Whitfield Diffie and Martin E. Hellman. New direc-tions in cryptography. IEEE Transactions on Infor-mation Theory, 22(6):644–654, 1976.

[6] Oded Goldreich. Pseudorandom Generators: A Pri-mer. ULECT series. AMS, 2010.

[7] Johan Håstad, Russell Impagliazzo, Leonid A. Le-vin, and Michael Luby. A pseudorandom genera-tor from any one-way function. SIAM J. Comput.,28(4):1364–1396, 1999.

[8] International Organization for Standardization.Iso/iec 18031:2011: Information technology – secu-rity techniques – random bit generation, 2011.

[9] Joseph Menn. Exclusive: Secret contract tied NSAand security industry pioneer. Reuters, Dezember2013.

[10] National Institute of Standards and Tech-nology. Special publications (800 series).http://csrc.nist.gov/publications/PubsSPs.html, 2013.

[11] National Institute of Standards and Technology.Supplemental ITL bulletin for September 2013,September 2013.

[12] Nicole Perlroth. Government announces steps torestore confidence on encryption standards. NewYork Times, September 2013.

[13] RSA, The Security Division of EMC. RSAresponse to media claims regarding NSA re-lationship. https://blogs.rsa.com/news-media-2/rsa-response/, Dezember2013.

[14] Bruce Schneier. The strange story of Du-al_EC_DRBG. www.schneier.com/blog,November 2007.

[15] Berry Schoenmakers and Andrey Sidorenko.Cryptanalysis of the dual elliptic curve pseudoran-dom generator. IACR Cryptology ePrint Archive,190, 2006.

[16] Claude Shannon. A mathematical theory ofcommunication. Bell System Technical Journal,27(3):379–423, 1948.

[17] Dan Shumow and Niels Ferguson. On the possibi-lity of a back door in the NIST SP 800-90 Dual ECPRNG. Crypto Rump Session, 2007.

10

GTPack - ein Mathematica Paket fürGruppentheorie in der FestkörperphysikM. Geilhufe, W. Hergert(Max-Planck-Institut für Mikrostrukturphysik,Martin-Luther-Universität Halle-Wittenberg)

geilhufe@mpi-halle.mpg.dewolfram.hergert@physik.uni-halle.de

EinleitungDie Anwendung gruppentheoretischer Algorithmen inder Festkörperphysik führt oft zu Rechnungen, die sichleicht automatisieren lassen. Dies ist auf rein numeri-schen Wege möglich und so teilweise in ab initio Pro-grammen zur Berechnung der elektronischen Strukturvon Festkörpern integriert [1]. Computeralgebrasystemehaben den Vorteil, dass sich gruppentheoretische Über-legungen mit einer analytischen Behandlung physika-lischer Modellsysteme verbinden lassen. Die Entwick-lung von GTPack zielt darauf ab, ein Paket zu program-mieren, welches insbesondere die Behandlung von Pro-blemen der Elektronenstruktur von Festkörpern oder derPhotonik erlaubt. Die Implementierung sollte dabei so-weit als möglich der in der Physik verwendeten Lite-ratur und Notation [2, 3, 4] folgen. Der Schwerpunktder Entwicklung liegt daher etwas anders als bei großenPaketen wie CrystGAP oder CARAT [5, 6]. Da im Rah-men des Physikstudiums in Halle begleitende Mathema-tica-Kurse zur theoretischen Physik angeboten werden,haben wir uns entschieden, Mathematica als Grundlagevon GTPack zu wählen.

GrundlagenIm Rahmen der Quantentheorie des Festkörpers istes das Ziel, geeignete Approximationen für die Lö-sung der Vielteilchen-Schrödinger-Gleichung zu fin-den. Im Festkörper wechselwirken ca. 1013 Elektronenüber die Coulombwechselwirkung. Die Schrödinger-gleichung als Grundgleichung der Quantentheorie kannfür ein solches Ensemble weder analytisch noch nume-risch gelöst werden. Näherungen gestatten es, das Pro-blem auf die Bewegung eines Elektrons in einem effek-tiven Potential aller anderen Teilchen zurückzuführen.Das effektive Potential wird dabei wesentlich durch dieAnordnung der Atome im Festkörper bestimmt. Damitübertragen sich die Symmetrieeigenschaften des Kris-talls auf den Lösungsraum der effektiven Schrödinger-gleichung. Physikalische Messgrößen wie Leitfähigkeitoder Magnetisierung lassen sich aus der Lösung berech-nen.

Aufgrund der hohen Symmetrie von Kristallen,stellt die Verwendung gruppentheoretischer Methodenzum einen eine Vereinfachung des numerischen Auf-wandes dar (z. B. durch Entwicklung der Lösung ineinen Satz symmetrieangepasster Basisfunktionen) zumanderen erlaubt sie die Vorhersage von bestimmten Ei-genschaften der Lösung (z. B. Entartung von Energieei-genwerten, d.h. verschiedene quantenmechanische Zu-stände gehören zur gleichen Energie) ohne numerischeAuswertung.

GTPack besitzt einen modularen Aufbau und istin verschiedene Pakete untergliedert. Die BasispaketeBasic.m und RepresentationTheory.m umfassen grund-legende Algorithmen der Gruppen- und Darstellungs-theorie. Dabei werden alle Ausgaben algorithmisch be-rechnet, GTPack greift nicht auf Tabellen zurück. Bei-spielsweise werden Charaktertafeln nach der Methodevon Burnside berechnet [7], Matrizen irreduzibler Dar-stellungen können nach dem Algorithmus von Flod-mark und Blokker [8] konstruiert werden oder Clebsch-Gordan-Koeffizienten nach der Methode von Van denBroek und Cornwell [9].

Das Paket Install.m enthält die nötigen Module umPunktgruppen zu generieren. Hierbei ist es wichtig zuerwähnen, dass alle Gruppenelemente sowohl symbo-lisch (z. B. C3z als dreizählige Drehung um die z-Achse), als Matrix, als Quaternion oder als Satz vonEuler-Winkeln dargestellt werden können. Je nach An-wendung können Drehmatrizen im R3 oder R2, Spin-Drehmatrizen aus der Gruppe U(2) (für die Verwen-dung von Doppelgruppen) oder Permutationsmatrizengewählt werden. Generatoren der 32 kristallographi-schen Punktgruppen sind in GTPack gespeichert underleichtern das Installieren einer Punktgruppe.

In Symbols.m werden die Definitionen von Sym-bolen, zum Beispiel die Bezeichungen der Punktgrup-pen und Punktgruppenelemente, wie sie in der Phy-sik üblich sind, zusammengefasst. Eine Reihe vonHilfsfunktionen befinden sich in Auxiliary.m. Hier-bei haben wir unter anderem grundlegende Befehleder Quaternionen-Algebra eingeführt, sowie kartesi-sche und reelle Darstellungen der Kugelflächenfunk-tionen implementiert. Die Pakete Lattice.m und Cry-stalStructure.m stellen Algorithmen zur Bereitstellungvon Strukturinformationen im direkten und reziprokenRaum zur Verfügung, wie sie unter anderem für die Be-

11

rechnung von elektronischen Bandstrukturen benötigtwerden. Die Pakete TightBinding.m, ElectronicStruc-ture.m, Pseudopotential.m sind Anwendungspakete diesich mit der Diskussion der elektronischen Strukturvon Festkörpern beschäftigen, während Photonics.m dieUntersuchung der Eigenschaften photonischer Kristal-le gestattet. Die Datensätze TB_Handbook.parm undPseudoPotential.parm enthalten Parametersät-ze, die das Aufstellen von Modellen zur Berechnung derelektronischen Struktur erleichtern. GTPack.strucstellt Raumgruppeninformationen bereit. Die Datensät-ze können nach den Erfordernissen des Nutzers erwei-tert werden.

Abbildung 1: Referenzseite zum BefehlGTInstallGroup GTPack

GTPack verfügt über ein Hilfesystem, welches indas Documentation Center von Mathematica integriertist. Wesentliche Befehle des Paketes, die Punkt- undDoppelgruppen sowie alle Elemente der Punkt- undDoppelgruppen sind von einer Palette abrufbar. Die Re-ferenzseiten, Leitseiten und Tutorials sind im Mathema-tica-Stil abgefasst (siehe Abb. 1)

BeispieleDie Arbeit mit dem Paket soll an zwei einfachen Bei-spielen erläutert werden. Dabei wird noch einmal deut-lich, dass alle Befehlsnamen direkten Bezug zur Auf-gabe haben. Zur Unterscheidung von den Standardbe-fehlen von Mathematica tragen Befehle des Pakets denPräfix GT und Optionen den Präfix GO.

KristallfeldaufspaltungAbb. 2 zeigt ein Atom in unterschiedlicher kristallo-graphischer Umgebung. Die oktaedrische Koordination

entspricht einer Situation, wie sie z. B. im Bariumtitanat(BaTiO3) auftritt.

Abbildung 2: Ein Zentralatom innerhalb einesoktaedrischen, kubischen und eines tetraedrischenKristallfeldes.

Aufgabe ist es nun festzustellen, wie die Entartungvon Energienivaus des Zentralatoms durch das elek-trostatische Feld der es umgebenden Atome aufgeho-ben wird. Dabei beschränken wir uns auf ein einzigesElektron und vernachlässigen Schwingungen der Atome(zeitunabhängiges Potential). Es sei H0 der zum Zen-tralatom gehörige Hamilton-Operator. Die Schrödinger-Gleichung des atomaren Problems lautet in diesem Fall

H0 lm(~r) = El0 lm(~r). (1)

lm ist die Wellenfunktion des Elektrons im 2l+1-fachentartetem Energieniveau El (�l m l). Ange-nommen die Lösung von Gleichung (1) sei bekannt, sokönnen wir im Rahmen der linearen Störungstheorie dieLösung für den Hamilton-Operator H = H0 + VKr er-mitteln. Dabei ist VKr das Kristallfeldpotential, welchesdurch die das Zentralatom umgebenden Atome zustandekommt.

Das Kristallfeldpotential lässt sich in reelle Kugel-flächenfunktionen Sm

l entwickeln,

VKr(r, ✓,� ) =

1X

l=0

lX

m=�l

Aml rlSm

l (✓,� ). (2)

Aufgrund der Symmetrie des Systems kann Gleichung(2) stark vereinfacht werden. Angenommen es gibt gTransformationen T einer Gruppe G, welche den Ha-miltonoperator H = H0+Vkr invariant lassen. Das heißt,nach Anwendung des Projektionsoperators der Einsdar-stellung �1 auf das Kristallfeldpotential muss gelten

P�1VKr =1

g

X

T2GP(T )VKr = VKr. (3)

Da die Kugelflächenfunktion Sml zu bestimmten l eine

Basis in einem 2l+1-dimensionalen Vektorraum bilden,muss gelten

P(T )Sml =

X

m0

Sm0l Dl

m0m(T ). (4)

Wir können somit ein lineares Gleichungssystem für dieKoeffizienten Am

l formulieren,

Aml =

1

g

X

T2G

X

m0

Am0l Dl

m0m(T ). (5)

Mit Hilfe des Befehls GTCrystalField in GTPackist es möglich, dieses Gleichungssystem für beliebige

12

Symmetrie zu lösen und das Kristallfeldpotential zu for-mulieren. Alternativ zur Entwicklung nach reellen Ku-gelflächenfunktionen, können komplexe Kugelflächen-funktionen verwendet werden, oder das Ergebnis in so-genannten Operatoräquivalenten [10] ausgedrückt wer-den.

vcr =GTCrystalField @Ohgroup, 4, GOHarmonics Æ "Real"D ê.Y@l_, m_D -> GTTesseralHarmonicY @l, m, q, fD

A@0, 0D2 p

+17r4 A@4, 0D 21 I3 - 30 Cos@qD2 + 35 Cos@qD4M

16 p+

105 I-1 + Cos@qD2M2 Cos@4 fD16 p

A00 = Table@GTCrystalFieldParameter @0, 0,Rlist@@iDD, qlist@@iDDD, 8i, 1, 3<D;

A40 = Table@GTCrystalFieldParameter @4, 0,Rlist@@iDD, qlist@@iDDD, 8i, 1, 3<D;

Die folgende Tabelle beinhaltet die Werte für die Kristallfeldparameter A0

0 und A40.

TableFormA8A00, A40<,TableHeadings Æ

99"A00", "A40"=, 8"Oktaeder", "Würfel",

"Tetraeder"<=EOktaeder Würfel Tetraeder

A00 12 p q

R16 p q

R8 p q

R

A40 7 p q

3 R5- 56 p q

27 R5- 28 p q

27 R5

Amat =Table@Integrate@Sin@qD GTTesseralHarmonicY @2, m1, q, fD

vcr GTTesseralHarmonicY @2, m2, q, fD,8q, 0, p<, 8f, 0, 2 p<D, 8m1, -2, 2<, 8m2, -2, 2<D;

rule = : q r4

R5Æ 6 Dq@octD, q

RÆ e@octD ê 6>;

Eigenwerte des Oktaeders:

Expand@Eigenvalues@AmatDD ê.A@l_, m_D -> GTCrystalFieldParameter @l, m,

Rlist@@1DD, qlist@@1DDDê. rule

8-4 Dq@octD + e@octD,-4 Dq@octD + e@octD, -4 Dq@octD + e@octD,6 Dq@octD + e@octD, 6 Dq@octD + e@octD<

Abbildung 3: Berechnung der Kristallfeldaufspaltungmit GTPack.

Die Punktgruppe für Oktaeder und Würfel in Abb. 2ist Oh, die Punktgruppe des Tetraeders Td. Das Kristall-feld hat für die Punktgruppen Oh und Td die Form

Vcr = A00S

00(✓,� ) +A0

4r4

S04(✓,� ) +

r5

7S44(✓,� )

!

In linearer Näherung kann die Änderung des 2l+1-fachentarteten Energieeigenwerte El

0 über die Eigenwerteder Matrix alm0m berechnet werden,

alm0m =

Zd~r� lm0(~r)Vcr�lm(~r). (6)

D2

Oktaeder

Eg

T2g

6Dq[oct]

4Dq[oct]

Wurfel

Eg

T2g

8

9

· 6Dq[oct]

8

9

· 4Dq[oct]

Tetraeder

E

T2

4

9

· 6Dq[oct]

4

9

· 4Dq[oct]

Abbildung 4: Aufspaltung eines d-Niveaus innerhalbeines Kristallfeldes mit oktaedrischer, kubischer undtetraedrischer Symmetrie.

Das Ergebnis für d-Elektronen (l = 2) ist in Abb.4 dargestellt. Dabei haben wir für die Berechnung derKristallfeldparameter Am

l ein einfaches Punktladungs-modell verwendet, wie es in dem Befehl GTCrystal-FieldParameters implementiert ist. Die Ladungen derAtome sind in der Liste qlist und deren Positionenin der Liste Rlist gegeben. Der Übersichtlichkeit hal-ber haben wir den Parameter Dq[oct] eingeführt [4].

<< GroupTheory`

Ohgroup = GTInstallGroup@"Oh"D;The standard representation has changed to OH3Lcharactertable = GTCharacterTable @Ohgroup,

GOIrepNotation Æ "Mulliken"D;C1 C2 C3 C4 C5 C6 C7 C8 C9 C10

A1g 1 1 1 1 1 1 1 1 1 1

T1g 3 -1 -1 -1 1 -1 1 0 0 3

T2g 3 -1 -1 1 -1 1 -1 0 0 3

T1u 3 -1 1 -1 -1 1 1 0 0 -3T2u 3 -1 1 1 1 -1 -1 0 0 -3A1u 1 1 -1 -1 1 1 -1 -1 1 -1Eu 2 2 -2 0 0 0 0 1 -1 -2A2u 1 1 -1 1 -1 -1 1 -1 1 -1A2g 1 1 1 -1 -1 -1 -1 1 1 1

Eg 2 2 2 0 0 0 0 -1 -1 2

cp = GTAngularMomentumChars @charactertable@@1DD,1D;

cd = GTAngularMomentumChars @charactertable@@1DD,2D;

cf = GTAngularMomentumChars @charactertable@@1DD,3D;

GTIrep@cp, charactertableD;T1u

GTIrep@cd, charactertableD;T2g≈Eg

GTIrep@cf, charactertableD;T1u≈T2u≈A1u

Abbildung 5: Qualitative Analyse der Aufspaltung vonEnergieniveaus in kubischen Kristallfeldern.

Alternativ lässt sich eine qualitative Überlegungdes Problems anstellen. Nach Installation der Grup-pe Oh mit GTInstallGroup wird die Charaktertafelmit GTCharacterTable erzeugt und dabei die Be-zeichnung der irreduziblen Darstellungen nach Mulli-ken per Option ausgewählt. Die Wellenfunktionen des

13

Zentralatoms sind ohne das Kristallfeld Basisfunktio-nen zu irreduziblen Darstellungen der Gruppe O(3).Diese irreduziblen Darstellungen sind allerdings redu-zibel in kubischer Symmetrie (Oh). Mit GTAngular-MomentumChars werden die Charaktere der (2l+ 1)-dimensionalen Darstellungen für die s, p, d Wellenfunk-tionen mit den Drehimpulsquantenzahlen l = 1, 2, 3bestimmt. Die Darstellungsmatrizen entsprechen geradeden Matrizen Dl

m0m aus der vorhergehenden Diskussi-on. Die Ausreduktion erfolgt mit GTIrep. Die fünfdi-mensionale Darstellung (auch fünffache Entartung desEnergieniveaus) der d-Elektronen spaltet somit in einezweidimensionale und eine dreidimensionale Darstel-lung (T2g�Eg) auf. Die siebendimensionale Darstellungder f -Elektronen zerfällt in zwei dreidimensionale Dar-stellungen und eine eindimensionale Darstellung. DerOutput von GTIrep entspricht dabei der in der Physiküblichen Mullikennotation.

Elektronenstruktur von GraphenIm Jahre 2010 erhielten Gleim und Novoselov den No-belpreis für ihre Untersuchungen an Graphen, einerzweidimensionalen Kohlenstoffmodifikation mit bie-nenwabenartiger Struktur. Spezielle elektronische Ei-genschaften dieses Materials können in einem Tight-Binding Modell [11] gut erklärt werden. In diesem Mo-dell sind die Elektronen stark an den Atomen lokalisiert.Durch diese Annahme kann die Schrödinger-Gleichungin Matrix-Form formuliert werden. Matrizen für solcheTight-Binding Modelle lassen sich mit GTPack auto-matisch erzeugen.

Out[20]=

-4 -2 2 4

-4

-2

2

4

Honeycomb Lattice

AtomsC1

C2

Abbildung 6: Struktur von Graphen. Die 2Kohlenstoffatome in der Basis sind mit C1 und C2bezeichnet

Abb. 6 zeigt die Struktur von Graphen. Mit denBefehlen GTCluster, GTShells (s. Abb. 7) wirddie Struktur aufgebaut und es werden die Nach-barschaftsverhältnisse analysiert. Die Liste hcp ent-hält dabei die Strukturinformationen, die aus derDatenbank GTPack.struc geladen werden. Aus-gehend von der Strukturinformation und Informa-tionen über die pro Atom zu berücksichtigendenOrbitale (ham[[1,1]] in Abb. 7) kann man dieSchrödinger-Gleichung in Matrixform gewinnen.

cl = GTCluster@hcp, 6, GOLattice Æ 8a -> 1<D;bas = hcp@@7DD ê. 8a Æ 1<;shells = 82, 2<;85 atoms

lat = GTShells@cl, bas, shells, GOVerbose Æ True,GOTbLattice Æ 88"C1,C1", 82<<, 8"C2,C2", 82<<,8"C1,C2", 81<<<,GOPosition Æ "Relative"D;

Basis dist Atoms dist Atoms

C1 1 88C2, 3<< 3 88C1, 6<<C2 1 88C1, 3<< 3 88C2, 6<<

In[94]:= bas = 88"C1", 80, 1<<, 8"C2", 80, 1<<<;hamc = GTTbHamiltonian@bas, latD;

In[95]:= GTHamiltonianPlot@hamc, basD

Out[95]=

s px pz py s px pz pyspxpzpyspxpzpy

In[110]:= ham = 88hamc@@3, 3DD, hamc@@3, 7DD<,8hamc@@7, 3DD, hamc@@7, 7DD<<;ham@@1, 1DD

Out[111]= 2 I2 Cos@3 p hD CosA 3 p xE + CosA2 3 p xEM HpppL1C1,C1 + Hpp0LC1

Abbildung 7: Aufstellung des tight-bindingHamiltonians für Graphen.

GTHamiltonianPlot zeigt die Struktur der entste-henden Matrix aus der die Energieeigenwerte berech-net werden. Man erkennt, dass die pz-Orbitale ent-koppeln und diese Energiewerte aus einem 2 ⇥ 2-Eigenwertproblem berechnet werden können. DiesesEigenwertproblem liefert 2 Energiebänder E(k), die inAbb. 8 dargestellt sind. In analoger Weise können dieanderen 6 Bänder generiert werden.

ky

E(~k)

kx

Abbildung 8: Bandstruktur E(k) von Graphen inAbhängigkeit vom Vektor k = (k

x

, ky

) in derBRILLOUIN Zone. Die Bänder zeigen linearesVerhalten an den 6 Dirac-Punkten.

ZusammenfassungGTPack stellt ein Paket dar, welches gruppenthoreti-sche Algorithmen mit der Analyse von Modellsystemender Festkörperphysik verbindet. Damit kann die Anwen-dung von Gruppentheorie in der Physik in der Lehre

14

besser demonstriert werden. Weiterhin können Ergeb-nisse, die mit komplexen ab initio Codes, basierend aufder Dichtefunktionaltheorie, erzielt werden, analysiertund interpretiert werden.

Literatur

[1] J. Hafner, Materials simulations using VASP—aquantum perspective to materials science. Compu-ter Physics Communications, 177:6–13, 2007.

[2] J.F. Cornwell, Group Theory in Physics. AcademicPress, 1984.

[3] M. S. Dresselhaus, G. Dresselhaus und A. Jorio,Group Theory - Application to the Physics of Con-densed Matter. Springer-Verlag, 2008.

[4] W. Haberditzl, Quantenchemie. 4. Komplexverbin-dungen. Hüthig, 1979.

[5] The GAP Group, GAP – Groups, Algorithms, andProgramming, Version 4.7.4. 2014.

[6] J. Opgenorth, W. Plesken und T. Schulz, Crystallo-graphic Algorithms and Tables. Acta Crystallogra-phica Section A, 54:517–531, 1998.

[7] M. El-Batanouny und F. Wooten, Symmetry andCondensed Matter Physics: A Computational Ap-proach. Cambridge University Press, 2008.

[8] S. Flodmark und E. Blokker, A computer programfor calculation of irreducible representations of fini-te groups. International Journal of Quantum Che-mistry, 1:703–711, 1967.

[9] P. M. van Den Broek und J. F. Cornwell, Clebsch-Gordan coefficients of symmetry groups. physicastatus solidi (b), 90:211–224, 1978.

[10] H. A. Buckmaster, R. Chatterjee, und Y. H. Shing,The application of tensor operators in the analysisof EPR and ENDOR spectra. physica status solidi(a), 13:9–50, 1972.

[11] A. V. Podolskiy und P. Vogl, Compact expressi-on for the angular dependence of tight-binding Ha-miltonian matrix elements. Phys. Rev. B, 69:23301,2004.

Superstringtheorie und elliptische KurvenJ. Keitel(Max-Planck-Institut für Physik)

jkeitel@mpp.mpg.de

Zusammenfassung

Seit der Entdeckung der Stringtheorie wer-den durch diese regelmäßig Querverbindungenzwischen Themengebieten der reinen Mathe-matik und physikalischen Fragestellungen ent-deckt. In diesem Beitrag diskutieren wir Aspek-te elliptischer Kurven, die relevant für das Stu-dium von Stringkompaktifizierungen sind.

Physikalische MotivationTrotz des überwältigenden Erfolgs des Standardmo-dells in der Beschreibung der elektroschwachen undder starken Wechselwirkung existiert bis heute keineexperimentell überprüfte Theorie, die das Standardmo-dell mit Einsteins allgemeiner Relativitätstheorie ver-eint. Dies ist unter anderem der großen Disparanz

der relevanten physikalischen Skalen geschuldet: Quan-teneffekte in Gravitationstheorien werden relevant inProzessen, die bei Energien nahe der Planckenergievon EP lanck ⇡ 1019 GeV stattfinden, während mo-derne Teilchenbeschleuniger Schwerpunktenergien vonELHC ⇡ 104 GeV erreichen. Dennoch gibt es einenKandidaten, der Eichtheorien, die Bausteine des Stan-dardmodells, mit der allgemeinen Relevativitätstheorievereint: Die Superstringtheorie.

Im Rahmen der Superstringtheorie wird das Kon-zept des nulldimensionalen Punktteilchens ersetztdurch ausgedehnte eindimensionale Objekte, sogenann-te Strings. Bei Energien, die deutlich kleiner sind als dieStringskala, reproduzieren solche Strings dann das Teil-chenspektrum von Eichtheorien und Gravitation. Ausinternen Konsistenzgründen müssen diese Strings je-doch in einer Welt mit zehn Raumzeitdimensionen exis-tieren. Um dies in Verbindung mit unseren Beobach-tungen zu bringen, ist es daher notwendig, sechs die-

15

ser Dimensionen mathematisch kompakt zu machen undihnen eine Größe zu geben, die bisher experimentellnoch nicht beobachtet worden sein kann. Da die Su-perstringtheorie in zehn Dimensionen nur einen dimen-sionsbehafteten Parameter aufweist, ist es die Geome-trie der kompakten Extradimensionen, die physikalischeObservablen in vier Dimensionen, wie zum BeispielNaturkonstanten, festlegt. Eine entscheidende Aufgabeim Studium solcher Stringkompaktifizierungen ist es da-her, Verbindungen zwischen geometrischen Größen undphysikalischen Observablen herzustellen.

X

Abbildung 1: Visualisierung einer elliptischen Kurveüber C: Ein 2-Torus mit einem markierten Punkt.

Im Folgenden beschäftigen wir uns mit einer be-stimmten Klasse von Stringkompaktifizierungen, soge-nannten F-Theorie-Kompaktifizierungen [1]. Diese fü-gen den sechs kompakten Dimensionen noch zwei wei-tere unphysikalische Dimensionen in Form einer el-liptischen Kurve hinzu. Intuitiv entspricht eine ellipti-sche Kurve über den komplexen Zahlen einem 2-Torusmit einem markierten Punkt, siehe Abbildung 1. Un-ser Ziel ist es, die Mordell-Weil-Gruppe der elliptischenKurve zu bestimmen, da diese die Anzahl der U(1)-Eichgruppen, also Wechselwirkungen, die der elektro-magnetischen Kraft ähnlich sind, bestimmt. Bevor wirunser Vorgehen genau beschreiben, führen wir jedochkurz ein paar wohlbekannte Eigenschaften elliptischerKurven ein. Alle unsere Rechnungen wurden mittels Sa-ge [2] durchgeführt und wir werden daher im Laufe die-ses Artikels immer wieder Bezug darauf nehmen.

Elliptische KurvenPer Definition ist eine elliptische Kurve über einem Kör-per K eine glatte projektive Kurve von Geschlecht 1 miteinem Punkt O, dessen Koordinaten in K liegen. So-lange char(K) 62{ 2, 3} lässt sich jede solche Kurve inWeierstrassform

E : y2z = x3 + fxz2 + gz3 (7)

darstellen. Hierbei sind (x : y : z) die homogenen Koor-dinaten des projektiven Raumes CP2 und f , g liegen inK. Elliptische Kurven haben die besondere Eigenschaft,dass ihre Punkte mit Koeffizienten in K eine abelscheGruppe bilden, die Mordell-Weil-Gruppe MW(E).

Sage [2] enthält Funktionen, um elliptische Kurveneinfach zu manipulieren. Eine elliptische Kurve über Klässt sich durch

sage: E = EllipticCurve(K, [f, g])

erstellen. Gegeben E kann man nun Punkte auf E durchAngabe ihrer Koeffizienten definierensage: pt = E(pt_x, pt_y, pt_z)

und diese Punkte dann bezüglich der Gruppenwirkungaddieren. Sage wählt automatisch den Punkt bei unend-lich, (0 : 1 : 0), als neutrales Element der Gruppen-struktur:sage: zero = E(0, 1, 0)sage: zero + zero(0 : 1 : 0)

Für elliptische Kurven, deren Darstellung in Weier-strassform bekannt ist, kann man weiterhin herausfin-den, welches der Rang der Untergruppe der Mordell-Weil-Gruppe ist, die eine gegebene Menge von Punktenerzeugt.

Elliptische FaserungenFür unsere F-Theorie-Kompaktifizierungen betrachtenwir Mannigfaltigkeiten M8, die eine Faserung

E ! M8⇡�! M6 (8)

aufweisen, wobei E eine elliptische Kurve definiert undM6 die Basismannigfaltigkeit ist, auf der die sechs Ex-tradimensionen des Superstrings kompaktifiziert wer-den. Bildlich gesehen wird also an jeden Punkt in M6eine elliptische Kurve E gefügt, deren komplexe Struk-tur über M6 variieren kann. Weiterhin fordern wir,dass M8 eine Calabi-Yau-Mannigfaltigkeit ist und daherc1(TM8) = 0 gilt. Damit E eine elliptische Kurve ist,muss M8 einen globalen Schnitt besitzen, der das neu-trale Element der Faser bestimmt. Besitzt M8 weitereSchnitte, so definieren diese zusätzliche rationale Punk-te in der Faser, die die Mordell-Weil-Gruppe MW(E)erzeugen.

Im Folgenden interessieren wir uns für Calabi-Yau-Mannigfaltigkeiten M8 ⇢ Y10, die als Hyperflächen intorischen Varietäten Y10 konstruiert werden können. Dietorischen Varietäten Y10 weisen dann selbst eine Fase-rung

Y4 ! Y10 ! M6 (9)

auf. Insbesondere ist die elliptische Kurve E ⇢ Y4 eineHyperfläche in der Mannigfaltigkeit Y4, die selbst einetorische Varietät ist.

Elliptische Kurven in torischenVarietäten

Als Nächstes betrachten wir daher elliptische Kurven,die als Hyperflächen in torischen Varietäten dargestelltwerden. Eine Einführung in torische Geometrie findetsich beispielsweise in [3, 4]. Um gewisse Regularitätsei-genschaften der elliptischen Faserungen zu garantieren,betrachten wir nur torische Varietäten, die Gorensteinund Fano sind [5]. Bis auf Isomorphismen stehen die-se in eindeutiger Korrespondenz zu reflexiven Polyto-pen. Als Polytop bezeichnen wir hier die konvexe Hülle

16

endlich vieler Punkte. Weiterhin ist ein n-dimensionalesPolytop P im Gitter Zn reflexiv, wenn das dazu dualePolygon

P ⇤ = {y 2 Rn|hy, xi � �1 8x 2 P} (10)

wieder ein Gitterpolytop ist, also nur Eckpunkte in Zn

hat. Da für zwei Polytope P und P 0

vol(P ) < vol(P 0) $ vol(P ⇤) > vol(P 0⇤) (11)

gilt und das Volumen eines Gitterpolytops durch dasGitter nach unten beschränkt ist, gibt es in jeder Dimen-sion eine obere Schranke für das Volumen reflexiver Git-terpolytope. Insbesondere bedeutet dies, dass es in jederDimension nur endlich viele reflexive Polytope gibt.

Abbildung 2: Die 16 reflexiven Polygone. Gitterpunkte,deren zugehörige Divisoren eine generische elliptischeKurve einmal schneiden, sind rot markiert.

In zwei Dimensionen existieren bis auf Gitteriso-morphismen 16 verschiedene reflexive Polygone und inSage lassen sich diese und die dazu gehörigen torischenFlächen leicht konstruieren [2, 6]. Beispielsweise er-stelltsage: F5 = ReflexivePolytope(2, 5)sage: X5 = CPRFanoToricVariety(....: Delta_polar=F5)

sage: X02-d CPR-Fano toric varietycovered by 3 affine patchessage: X5.anticanonical_hypersurface(....: monomial_points=’all’)Closed subscheme of 2-d CPR-Fanotoric variety covered by 5 affinepatches defined by:a1*z0^2*z1^2*z4^3+ a5*z0^2*z1*z2*z4^2+ a7*z0*z1^2*z3*z4^2+ a4*z0^2*z2^2*z4+ a6*z0*z1*z2*z3*z4+ a0*z1^2*z3^2*z4+ a3*z0*z2^2*z3+ a2*z1*z2*z3^2

die generische elliptische Kurve in der torischen Varie-tät dP2, die in unserer Notation CP2 aufgeblasen anzwei Punkten entspricht. Divisoren von Y4, die E ein-mal schneiden, werden zu Schnitten der Faserung M8.In dem Fall von dP2 sind das die Divisoren V (z0),V (z1) and V (z4). Für jeden solchen Divisor lässt sichder Schnittpunkt mit E ausrechnen. Zum Beispiel gilt

E \ V (z0) :

✓0 : 1 : 1 : 1 : �a2

a0

◆. (12)

Für eine generische Wahl von Koeffizienten ai gilt ai 6=0 und der Ausdruck ist daher wohldefiniert.

Um nun die Gruppe zu bestimmen, die von denSchnittpunkten von V (z0), V (z1) und V (z4) mit E er-zeugt wird, ist es hilfreich, die Kurve in Weierstrassform(7) zu bringen. Obwohl dies allgemein immer mög-lich ist, kann es in der Praxis kompliziert sein, die ent-sprechende Transformation explizit zu bestimmen. Indem Fall der 16 torischen Gorenstein-Fano-Varietätenmit komplexer Dimension 2 lässt sich dieses Problemjedoch lösen [7]. Zunächst beobachtet man, dass die16 Hyperflächengleichungen Spezialfälle von Hyperflä-chengleichungen in CP2, CP112 und CP1 ⇥ CP1 sind.Insbesondere lässt sich das obige Beispiel in CP2 ein-betten nachdem man die Aufblasung, die einen von CP2

zu dP2 führt, rückgängig macht. Dies geschieht durchdie Abbildung

(z0 : z1 : z2 : z3 : z4) 7! (1 : 1 : z2 : z3 : z4) , (13)

die die obige Gleichung abbildet auf

p = a1z34 + a5z2z

24 + a7z3z

24 + a4z

22z4

+ a6z2z3z4 + a0z23z4 + a3z

22z3 + a2z2z

23 . (14)

Dies definiert offensichtlich eine nicht-generische Ku-bik in CP2.

Da für Hyperflächen in CP2, CP112 und CP1⇥CP1

Transformationen in Weierstrassform in der Literaturbekannt sind, sind wir nun in der Lage, die Weierstrass-form beliebiger elliptisch gefaserter Hyperflächen aus-zurechnen. Insbesondere ist diese Funktionalität bereitsin Sage implementiert:sage: WeierstrassForm(p)

gibt eine Liste mit den Weierstrasskoeffizienten f und gzurück. Weiterhin lässt sich durchsage: WeierstrassForm(p,....: transformation=True)

17

auch die explizite Abbildung der homogenen Koordina-ten (z0 : . . . zn) auf Punkte in Weierstrassform berech-nen. Ist die elliptische Kurve in Weierstrassform samtder durch die Schnitte erzeugten Punkte gegeben, lässtsich die von den Punkten aufgespannte Gruppe ermit-teln.

Es ist wichtig anzumerken, dass es für bestimmteFaserungen zusätzliche Schnitte geben kann, die nichtdurch Divisoren der obigen Form definiert sind. Mitdem hier vorgestellten Ansatz ermittelt man jedoch eineUntergruppe der Mordell-Weil-Gruppe, in [8] die tori-sche Mordell-Weil-Gruppe genannt, die jede Faserungmit der entsprechenden generischen Faser hat.

Ergebnisse und AusblickMittels der in den vorherigen Abschnitten diskutier-ten Methode lassen sich die Untergruppen der Mordell-Weil-Gruppen, die von torischen Divisoren erzeugt wer-den, für generische elliptische Fasern in den 16 zwei-dimensionalen Gorenstein-Fano-Varietäten bestimmen.Es finden sich [8]

Z ,Z� Z ,Z� Z� Z , (15)

sowie folgende Gruppen mit Torsion:

Z2 ,Z3 ,Z� Z2 . (16)

Weiterhin gibt es zwei Varietäten, in denen die Mordell-Weil-Gruppe der generischen elliptischen Kurve trivialist und drei weitere Fälle, in denen die generische Faserzwar eine Kurve von Geschlecht 1 ist, aber die Faserungkeine globalen Schnitte besitzt.

Abgesehen von den verschiedenen physikalischenSzenarien, die in derartigen Stringkompaktifizierungenuntersucht werden können, gibt es eine offensichtlicheVerallgemeinerung der hier besprochenen Arbeit: An-statt elliptische Kurven zu untersuchen, die Hyperflä-chen in torischen Varietäten sind, kann man allgemeinerelliptische Kurven betrachten, die vollständige Durch-schnitte in höherdimensionalen torischen Räumen sind.

Da die Anzahl reflexiver Polytope rapide mit der Di-mension anwächst (es gibt 4319 dreidimensionale und⇠ 5 ·108 vierdimensionale reflexive Polytope), erforderteine solche Verallgemeinerung die Automatisierung derhier vorgestellten Rechnungen. Weiterhin stellt sich her-aus, dass der hier vorgestellte Ansatz zum Ermitteln derWeierstrassform in höheren Dimensionen nicht mehr al-le Fälle abdeckt und daher einen neuen Algorithmus er-forderlich macht [9].

Literatur

[1] C. Vafa, Evidence for F theory, Nucl.Phys. B469(1996) 403–418, [hep-th/9602022].

[2] W. Stein et. al., Sage Mathematics Software (Ver-sion 6.3). The Sage Development Team, 2014.http://www.sagemath.org.

[3] W. Fulton, Introduction to toric varieties. No. 131.Princeton University Press, 1993.

[4] D. A. Cox, J. B. Little, and H. K. Schenck, Toricvarieties. American Mathematical Soc., 2011.

[5] V. V. Batyrev, Dual polyhedra and mirror symmetryfor calabi–yau hypersurfaces in toric varieties, in J.Alg. Geom, Citeseer, 1994.

[6] V. Braun and A. Novoseltsev, Toric varieties mo-dule of Sage. The Sage Development Team, 2014.http://www.sagemath.org.

[7] V. Braun, Toric Elliptic Fibrations and F-TheoryCompactifications, JHEP 1301 (2013) 016,[arXiv:1110.4883].

[8] V. Braun, T. W. Grimm, and J. Keitel, Geome-tric Engineering in Toric F-Theory and GUTswith U(1) Gauge Factors, JHEP 1312 (2013) 069,[arXiv:1306.0577].

[9] V. Braun, T. W. Grimm, and J. Keitel, Work in pro-gress.

18

Computeralgebra in der Schule

3D-Grafik in der Schule mitComputeralgebraJ.-H. Müller, U. Schürmann(Rivius-Gymnasium der Stadt Attendorn,Westfälische Wilhelms-Universität Münster)

jan.mueller@math.uni-dortmund.deschuermann.uwe@uni-muenster.de

ZusammenfassungDreidimensionale Computergrafik, wie sie

in Animationsfilmen oder ComputerspielenEinsatz findet, ist heute für viele Schülerinnenund Schüler ein alltägliches Phänomen. Dabeiberuht sie u.a. auf grundlegenden Konzeptender Analytischen Geometrie, was sie für denMathematikunterricht in der Sekundarstufe IIinteressant macht.Im Artikel wird anhand von ersten unterrichtli-chen Erfahrungen gezeigt, wie dreidimensiona-le Computergrafik mit einem Computeralgebra-system (CAS) gewinnbringend für AnalytischeGeometrie genutzt werden kann.

Vorbemerkungen und technischeVoraussetzungen

Eine Gefahr von anwendungsorientiertem Mathematik-unterricht besteht darin, dass die Bearbeitung inter-essanter Probleme in realistischen Kontexten mitunterviel kontextspezifisches Wissen voraussetzt und zusätz-liche mathematische Verfahren verlangt, die ansonstenim Unterricht nicht thematisiert würden. Ein realitäts-bezogener Mathematikunterricht erfordert demnach vonder Lehrkraft die geplanten Inhalte didaktisch so zu re-duzieren, dass das Verhältnis von echtem Realitätsbe-zug und unterrichtlichen Rahmenbedingungen wie cur-ricularen Vorgaben, Zeitkontingent und mathematischenFähigkeiten der Lerngruppe gewahrt bleibt.

Deshalb werden im Folgenden nur solche Unter-richtsbeispiele vorgestellt, die auch Lehrpersonen undLernende ohne explizite Kenntnisse von dreidimensio-naler Computergrafik oder gar Programmierung nutzenkönnen. Die Beispiele können am Computer von denLernenden selbst visualisiert werden, wodurch deutlichwird, dass es sich bei den vorgestellten Beispielen umechte Anwendungen aus der Computergrafik handelt.

Die im Artikel vorgestellten Unterrichtsbeispieleberuhen auf dem CAS Maxima1. Es ist kostenlos und

kann auf verschiedenen Betriebssystemen genutzt wer-den. Somit bietet es den Vorteil, dass Schülerinnenund Schüler Unterrichtsmaterialien auf dem heimischenComputer nutzen können. Durch einfache Maxima-Dateivorlagen, wie sie auch in diesem Artikel zu fin-den sind, kann zudem der Aufwand der Bedienung desProgramms für die Lerngruppe deutlich verringert wer-den. Im Folgenden wird Maxima hauptsächlich als drei-dimensionales Zeichenwerkzeug genutzt. Darüber hin-aus sollte Maxima natürlich auch in seiner eigentli-chen Funktion als CAS Verwendung finden, z. B. wennSchnittprobleme zwischen Objekten thematisiert wer-den und dazu lineare Gleichungssysteme gelöst werdenmüssen.

Unterrichtsbeispiele

Abbildung 1: Haus in zwei Verschiedenen Ansichten

Beschreibung von ObjektenDie grundlegende Idee der 3D-Grafik ist die mathema-tische Beschreibung realer Objekte im Raum. Eine ers-te Übung könnte deshalb darin bestehen, Lernende zu-nächst geradlinig begrenzte reale Objekte mit Koordi-naten beschreiben und anschließend zeichnen zu lassen.Abbildung 1 zeigt ein Haus in zwei verschiedenen An-sichten. Hierbei müssen die Lernenden Abschätzungenzu Längen- und Größenverhältnissen anstellen und ent-scheiden, welche Teilaspekte eines Objektes zunächst

1Download: http://maxima.sourceforge.net/. Eine Einführung in das Erstellen von Grafiken mit Maxima findet sich z. B.hier: http://www.austromath.at/daten/maxima/zusatz/Grafiken_mit_Maxima.pdf (Zugriff am 18.02.14).

19

außer Acht gelassen werden können. Auf diese Wei-se gewinnen sie dreidimensionale Koordinaten, die alsEckpunkte des Hauses gezeichnet werden. Um ein bes-seres Abbild des Hauses zu erhalten, müssen anschlie-ßend Punkte miteinander verbunden und Flächen ggf.eingefärbt werden.

Abbildung 2 zeigt einen ersten Versuch mithilfe vonMaxima die Seitenwand des Hauses, die in Abbildung 1im linken Bild zu sehen ist, mit Punkten zu beschrei-ben. Im Maxima-Code wird zunächst mit load(draw)ein Grafik-Paket geladen, mit dem Grafiken flexiblergestaltet werden können als mit den Standardbefehlenvon Maxima. Mit dem Befehl wxdraw3d wird eine 3D-Grafik als Zusammenstellung aus verschiedenen 3D-Grafikobjekten erstellt. Im vorliegenden Fall sind dieserstens eine Reihe von Punkten für die Seitenwand,zweitens eine Reihe von Punkten für das große Fens-ter und drittens eine Reihe von Punkten für das kleineFenster (jeweils mit geschätzten Maßzahlen in Meter).Es werden weiterhin verschiedene Optionen angegeben.So sorgt z. B. POINTS_JOINED=TRUE dafür, dass diePunkte miteinander verbunden werden. Um tatsächlichein geschlossenes Vieleck zu erzeugen muss der erstePunkt am Ende noch einmal angegeben werden.

Abbildung 2: Seitenwand des Hauses durch Punkte

Die Wände des Hauses können natürlich ebenso gutmithilfe von Ausschnitten aus Ebenen in Parameterformbeschrieben werden, wie Abbildung 3 mithilfe des Be-fehls PARAMETRIC_SURFACE zeigt.

Für die einzelnen Flächen werde die Parameter s undt entsprechend eingeschränkt: s liegt im gegebenen Bei-spiel zwischen 0 und 4 und t zwischen 0 und 6. Für die x-, y- und z-Koordinaten der Fläche werden Terme ange-geben. Im Unterricht kann es z. B. gewinnbringend sein,die Lerngruppe mit der Syntax aus Abbildung 3 zu kon-frontieren und einen Zusammenhang etwa zu folgenderDarstellung der zur Seitenwand gehörenden Ebene inParameterform herstellen zu lassen:

e1 : x =

0

@000

1

A+ s ·0

@100

1

A+ t ·0

@001

1

A ;

0 s 4, 0 t 6.

Ebenso gut kann den Schülerinnen und Schülern die Artder mathematischen Modellierung der Seitenwand hin-gegen völlig freigestellt werden. Erfahrungen aus dem

Unterricht zeigen, dass es für Schülerinnen und Schüleranspruchsvoll ist, geeignete dreidimensionale mathema-tische Beschreibungen zu finden und diese in die Syntaxvon Maxima zu übersetzen. Der Einsatz von Arbeits-vorlagen und Hinweisen zur Syntax ist deshalb zu emp-fehlen. Die beiden gezeigten Beispiele stehen natürlichnur paradigmatisch für eine Vielzahl an Möglichkeiten,wie die gestellte Aufgabe gelöst werden kann. Uns er-scheint es deshalb wichtig, Lernenden Hilfen aber keineLösungen anhand zu geben. Der Mehrwert dieses An-satzes entsteht durch einen anschließenden Austauschim Unterricht über die gewählten Methoden und der Ab-wägung ihrer jeweiligen Vor- und Nachteile.

Abbildung 3: Seitenwand des Hauses durch Ebenen

Licht und SchattenUm das geometrisches Objekt auf unserem Bildschirmmöglichst realistisch aussehen zu lassen, ist es noch einweiter Weg. Zu diskutieren wäre, was noch alles getanwerden muss, um eine möglichst realistische Darstel-lung zu erreichen. Neben der Erweiterung unserer Sei-tenwand auf ein komplettes räumliches Modell bietensich eine Vielzahl an Fragestellungen an, die eine kon-textuelle Einbettung der üblichen curricularen Vorgabender Analytischen Geometrie ermöglichen. Die folgen-den Fragestellungen zeigen, dass unser Beispiel hierfürgeeignet ist.

3D in 2DUnabhängig von unserem Beispiel zeigte sich in Un-terrichtssituationen, wie konsterniert viele Schülerinnenund Schüler auf die Frage reagieren, wie die dreidi-mensionale Wirkung von Objekten bei der Darstellungauf einer eigentlich zweidimensionalen Bildschirmflä-che zustande kommt. In diesem Zusammenhang könnensich Bezüge zum Kunstunterricht ergeben. So führt bei-spielsweise die Zentralperspektive mittels eines zu defi-nierenden Fluchtpunktes auf das Erstellen von Geraden-gleichungen im Raum und das Ermitteln von Schnitt-punkten mit einer zu definierenden „Bildschirmebe-ne“. Und im Zusammenhang mit der Parallelperspek-tive kann zudem die Eigenschaft linearer Abhängigkeit

20

von Richtungsvektoren der Geradengleichungen thema-tisiert werden.

SchattenwurfNach der Thematisierung von Geraden- und Ebe-nengleichungen werden im Unterricht üblicherweiseSchnittprobleme behandelt. Definiert man eine Licht-quelle im Raum, so kann analysiert werden, welchenSchatten das Haus in der Ebene wirft. In diesem Kon-text ergeben sich Schnittprobleme auf natürliche Art-und Weise. Wegen der hierfür zu lösenden Gleichungs-systeme wird das CAS zunehmend bedeutsam.

Einfärbung der SeitenwändeDa die Lichtquelle die Seitenwände des Hauses unter-schiedlich direkt beleuchtet, ist es ebenso naheliegendzu fragen, wie die Seitenwände (etwa in Graustufen)eingefärbt werden sollten. Qualitativ ist klar, dass ei-ne Seitenwand, die der Lichtquelle zugewandt ist hellereinzufärben ist als eine Seitenwand, die der Lichtquelleweniger stark zugewandt ist. Als Maß der „Zugewandt-heit“ können Winkel genutzt werden, die z. B. zwischenNormalenvektoren zu einer Seitenwand und einer Ver-bindung der Seitenwand zur Lichtquelle ermittelt wer-den.

DynamikEin Haus möchte man sich natürlich von allen Seitenanschauen, vergrößern, verkleinern oder in die eine oderandere Richtung verschieben können (etwa so, wie Ar-chitekten am Computer vorgehen, wenn sie ein Gebäu-de entwerfen). Anhand dieser Problemstellung könnenMatrizen und die Matrix-Vektor-Multiplikation einge-führt werden. Mit den Matrizeneinträgen können Schü-lerinnen und Schüler experimentieren und bekommendie Wirkung jeder Veränderung vom Programm veran-schaulicht.

Ausblick und Grenzen des AnsatzesWie sich gezeigt hat, lassen sich einige interessante An-wendungen aus der Computergrafik mithilfe eines CASim Unterricht realisieren. Die hier vorgestellten Bei-spiele sind durchaus erweiterbar, z. B. indem der Kon-text Computergrafik ergänzt wird durch rechenminimie-rende Verfahren oder mathematischen Problemen, wiesie sich bei der Programmierung von Computerspielenstellen (vgl. Schürmann 2014 b). Es können somit vie-le Begriffe und Verfahren der Analytischen Geometrieanwendungsorientiert eingeführt bzw. vertieft werden.Ebenso lohnt sich ein Blick auf digitale Bildbearbeitung(viele Anregungen bietet der ISTRON-Band 9) oder dasRGB-Farbmodell, welches für die Darstellung von Far-ben auf Computerbildschirmen verwendet wird. Auchdieser Kontext kann im Sinne der Analytischen Geo-metrie gedeutet werden (vgl. Schürmann 2014 a). BeideKontexte, Computergrafik und Farbmodelle, bauen eineBrücke zum Kunstunterricht, wo perspektivische Zeich-nungen und Farbmodelle ebenfalls von Bedeutung sind.Ein fächerverbindender Unterricht wird damit möglich.

Literatur[1] Meyer, Jörg und Oldenburg, Reinhard (Hrsg.)

(2006): Materialien für einen realitätsbezoge-nen Mathematikunterricht. Istron-SchriftenreiheBand 9: Computeranwendungen, Berlin, Hildes-heim, Franzbecker-Verlag.

[2] Schürmann, Uwe (2014 a): Abbildungsmatrizen imKontext von Farbtransformationen in Vektorgrafi-ken. PM 55/56, S. 43 – 47.

[3] Schürmann, Uwe (2014 b): 3D-Computerspiele undAnalytische Geometrie. Maaß, Jürgen und Hans-Stefan Siller (Hrsg): Neue Materialien für einen rea-litätsbezogenen Mathematikunterricht 2, ISTRON-Schriftenreihe, S. 115 - 130.

mathemas ordinate +www.ordinate.de

% 0431 23745-00/ ) -01 , info@ordinate.de ‹ Software for mathematical people !

+ Mathematische Software u. Consulting, MathType, Optica,

ExtendSim, KaleidaGraph, Intel-Software, Fortran, NSBasic,

@Risk, Chemistry, Satellitensteuerung u.a.

Fast 30 Jahre Erfahrung mit Software-Distribution !mathemas ordinate, Dipl. Math.Carsten Herrmann, M. Sc.

Königsbergerstr. 97, 24161 Altenholz

∞ + μ < ♥

1 2

1 22

1

2e

xx

xx(

)

Neues über Systeme

The SYMBOLICDATA Project – from DataStore to Computer Algebra Social NetworkH.-G. Gräbe, S. Johanning, A. Nareike(Universität Leipzig)

graebe@informatik.uni-leipzig.denareike@informatik.uni-leipzig.desimonjohanning@googlemail.com

IntroductionA powerful digital research infrastructure becomes in-creasingly important in today’s networked and inter-linked world. This includes digital support for dissem-ination of new papers, the refereeing process, confer-ence submissions, and scientific communication withincommunities. Services such as MathSciNet, arXiv.org,EasyChair.org, or bibsonomy.org have been establishedand their usefulness is acknowledged by the larger sci-entific community. For mathematics in the large the vi-sion of a 21st Century Global Library for MathematicsResearch (GDML) [2] matured during the last years.

Smaller academic communities, e. g. the ComputerAlgebra (CA) community, are challenged to organizetheir intracommunity communication infrastructure in asimilar way. Infrastructural efforts are rarely acknowl-edged by the reputational processes of science, however,and are hence left to the casual engagement of volun-teers unless led by leading-edge scientists of the com-munity.

Open Source culture offers plenty of experience ofhow to substitute centrally organized projects by decen-tralized networked structures and indeed the new focusof SYMBOLICDATA version 3 is that of an intercommu-nity project, providing not only reliable access to datafor testing and benchmarking purposes but also techni-cal support for interlinking between different CA sub-communities.

In this paper we explain the technological basics ofan RDF based semantic web of mathematics and discusssocial interlinking to the vision in large of an emergingGDML.

RDF BasicsWe refer to [6] for an overview of the goal, aims, con-cepts, infrastructure and history of the SYMBOLICDATAproject, in particular for a more detailed motivation touse RDF concepts and Linked Data principles. The useof such principles and notations for the metadata of ourdata store is one of the core advances with version 3

of SYMBOLICDATA. In this section we give a briefoverview of such concepts.

RDF is a data model which stores information astriples

s p o .

which are considered a sentence with subject s, predi-cate p and object o. Subjects and predicates are URIs(Uniform Resource Identifiers) while objects (or ‘val-ues’) can be a URI or a literal (a string in quotes). Thereare shortcut notations of RDF, e. g. RDF-XML, JSON,or Turtle, and plenty of tools and parsers for the differentformats.

As an example we consider the resource at

http://symbolicdata.org/XMLResources/IntPS/Czapor-86c.xml

that represents the XML record about the polynomialsystem

x2 + y z a+ x d+ g

y2 + x z b+ y e+ h

z2 + x y c+ z f + k

known as the Czapor-86c example. Such a polyno-mial system can be interpreted differently as polynomialideal in different polynomial rings (see below).

We are going to store properties of the interpretationof that polynomial system as ideal

I ⇢ Q[x, y, z, a, b, c, d, e, f, g, h, k]

(an ideal configuration, associated with that record) asnew RDF subject. First, a new URI has to be assigned tosuch a new subject (using a sound naming scheme, notdiscussed here):

<http://symbolicdata.org/Data/Ideal/Czapor-86c.Flat>

or sdideal:Czapor-86c.Flat for short.Now we can assign metainformation to that subject.

Some of these properties can be extracted directly fromthe XML resource, others have to be calculated. Here isthe record in Turtle notation:

22

sdideal:Czapor-86c.Flat a sd:Ideal ;rdfs:comment "Flat variant of Czapor-86c" ;

sd:hasDegreeList "3,3,3" ;sd:hasLengthsList "4,4,4" ;sd:relatedPolynomialSystem

sdpol:Czapor-86c ;sd:hasVariables

"x,y,z,a,b,c,d,e,f,g,h,k" .

This record contains 8 triples in Turtle shortcut notation.Since all triples share the same subject (the first line),Turtle compacts the notation by separating property–value pairs to the same subject with a semicolon. Thesd:, sdp:, sdideal:, sdpol: and sdxml: pre-fixes are abbreviations for name-space prefixes1.

The configuration above refers to the PolynomialSystem sdpol:Czapor-86c, described by the RDFrecord

sdpol:Czapor-86ca sd:IntegerPolynomialSystem ;sd:createdAt "1999-03-26" ;sd:createdBy sdp:Graebe_HG ;sd:relatedXMLResource

sdxml:Czapor-86c.xml .

In other words, the Czapor-86c.Flat configuration is de-rived from the ‘true’ Czapor-86c example, the ideal

I 0 ⇢ S0 = Q(a, b, c, d, e, f, g, h, k)[x, y, z]

generated by the same polynomials in a different poly-nomial ring S0. Geometrically the latter represents acomplete intersection of three (generic affine) quadricsover the field of rational functions in the given parame-ters. There is also a record on that configuration:

sdideal:Czapor-86c a sd:Ideal ;sd:createdAt "1999-03-26" ;sd:createdBy sdp:Graebe_HG ;sd:hasDegreeList "2,2,2" ;sd:hasLengthsList "4,4,4" ;sd:hasDegree "8"^^xsd:integer ;sd:hasDimension "0"^^xsd:integer ;sd:hasParameters "a,b,c,d,e,f,g,h,k" ;sd:parameterize sdideal:Czapor-86c.Flat ;sd:hasVariables "x,y,z" .

Czapor-86c is derived from the Czapor-86c.Flat con-figuration by parameterization with respect to the givenparameters (see below for details). Note that the degreelists of Czapor-86c.Flat and Czapor-86c are different.The record contains some more metainformation: S0/I 0

is zero dimensional and has degree 8.To operate on RDF data the databases (called RDF

Graphs) have to be uploaded into an RDF triple store.SYMBOLICDATA uses the Virtuoso triple store [18] thatprovides also a SPARQL endpoint [14] to query thedata, see [6] or our wiki [16] for more background in-formation.

Modelling Polynomial SystemsRDF provides language tools to express metainforma-tion in an interoperably searchable way that have to beapplied in a domain-specific way to model topics from

CA subcommunities. We explain such aspects of SYM-BOLICDATA modelling again on the topic of Polyno-mial Systems. Similar considerations are required tomodel any other part of the SYMBOLICDATA databaseand the SYMBOLICDATA wiki [16] gives details aboutmodelling other data (Free Algebras, G-Algebras, Ge-ometry Proof Schemes etc.).

Polynomial Systems XML resources store lists ofpolynomials in distributive normal form with integercoefficients together with a complete list of variables(and, for modular systems, the modular base domainGF (p)). Hence even modular polynomial systems canbe semantically considered as set F = {f1, . . . , fs} ofpolynomials in S = Z[x1, . . . , xn] in the indeterminatesx1, . . . , xn listed in the record.

Polynomial Systems Solving considers polynomialsystems in different contexts. We have already shownhow to construct the Czapor-86c ideal from the Czapor-86c.Flat resource. This is an example for a stan-dard kind of interpretation where we divide indetermi-nates x1, . . . , xn into disjoint subsets u1, . . . , uk andz1, . . . , zm and consider the ideal

I 0 ✓ S0 = R(u1, . . . , uk)[z1, . . . , zm]

generated by the images of f1, . . . , fs in S0 over the basecoefficient field R. Here u1, . . . , uk are considered asparameters and z1, . . . , zm as variables. R is usuallythe field Q of rationals or a modular field GF (p) (othersettings are possible). S has the universal property thatthe canonical map on the indeterminates extends to aring homomorphism S ! S0 in a unique way. We callsuch an interpretation of a Polynomial System resourceas ideal generators in a polynomial rings S0 (ideal) con-figuration. (Such configurations can be derived not onlyfrom Polynomial System resources but from other con-figurations as well.)

While SYMBOLICDATA version 2 would store eachnew configuration as a new resource, version 3 foresees(polynomial-time) transformations to express their rela-tion to the basic resource.

For example, the sd:homogenize transformationderives a new configuration by homogenization (with re-spect to standard grading). Given the configuration F inS0 and a new variable h we generate the homogenizedpolynomials F h = {fh

1 , . . . , fhs } in

S00 = R(u1, . . . , uk)[z1, . . . , zm, h]

and the ideal I 00 generated by F h in S00. There is a nat-ural ring homomorphism � : S00 ! S0 mapping h ! 1and the polynomials fh

1 , . . . , fhs are called the pull-back

polynomials of f1, . . . , fs with respect to �. Note thatthe pull-back ideal ��1(I 0) contains the pull-back poly-nomials but is not necessarily generated by them.

The transformations sd:flatten, sd:parame-terize and sd:substitute are defined by similarconcepts. Compared to former SYMBOLICDATA ver-sions the only restriction is that semantic-aware tools(that ‘know’ what a polynomial is) are required to gen-erate configurations from given basic ones. We believe

1Note that for more clarity we use a sloppy notation here that is not fully compliant with the RDF notational standards.

23

this is not a real restriction since for serious computa-tions on Polynomial Systems semantic-aware tools arerequired in any case. Such tools also have to provide aPolynomial Systems parser to input the basic XML ex-amples. With your favorite CA software being awareof polynomial semantics it should be easy to implementthe transformation modes required to obtain the differ-ent configurations. As a proof-of-concept, A. Nareikecompiled the sdsage package [10] to be integrated withthe Sagemath system [12].

Navigation within thePolynomial Systems Data

Special semantic knowledge is also required for naviga-tion and identification of data. This topic is particularlyimportant for intercommunity communication since onecannot expect researchers to be familiar with commonpractices of the different subcommunity. For a case-in-point let us again turn to Polynomial Systems Solving.

It is one of the challenges to check whether a Poly-nomial System configuration obtained from an externalsource is contained in the database, since the ‘same’configuration may be given by polynomials with differ-ent variable sets and in different term orders. Thus fornavigational purposes fingerprints of Polynomial Sys-tem configurations are required that are independentof variable names and term orders. For a polynomial0 6= f 2 S0 = R(u1, . . . , uk)[z1, . . . , zm], invariantsmay be derived from the set T (f) of terms. Every suchpolynomial has a distributive normal representation

f =X

↵2Nm

c↵ · z↵, c↵ 2 R(u1, . . . , uk),

z↵ = z↵11 · . . . · z↵m

m ,

and T (f) = {z↵ : c↵ 6= 0} is independent of theterm order (but not of the variable names). There aretwo invariants that are well-defined for f regardless ofvariable names and orders – the number |T (f)| of terms(the length of the polynomial f ) and the pattern of thetotal degrees (deg(z↵) : c↵ 6= 0) of the terms inT (f). In particular, for 0 6= f the maximum degreedeg(f) = max(deg(z↵) : c↵ 6= 0) is well-defined.

We use ordered lists of polynomial lengths and ofmaximum degrees as fingerprints of configurations andprovide them precompiled as part of the metadata fora given configuration. Such a fingerprint can easily becomputed by almost all semantic-aware tools. Whileconfigurations with different fingerprints are definitelydistinct, there can be different examples with the samefingerprint. Although such fingerprints could be refinedthere was no need so far, since the examples with equalfingerprints are rare and can easily be inspected by hand.

Knowledge Frames and Social FramingThe SYMBOLICDATA project can be seen as part of theworldwide efforts towards a World Digital Mathemat-ical Library (WDML). The most viable contributions

on that way are the EuDML project [3], funded by theEuropean Union during 2010–2013, and the WDMLproject [19], triggered by the US National ResearchCouncil and heavily supported by the IMU – the Inter-national Mathematical Union – and the Alfred P. SloanFoundation. There are other activities on the way in thatdirection, in particular by Wolfram Research Inc., devel-oping Wolfram Alpha as one of the most mature onlineresources of structured mathematical knowledge.

One of the big challenges within these projects is thequestion “How to structure and represent mathematicalknowledge?” Such a question is not only (and proba-bly not even in the first plan) a question about math-ematics but also about mathematicians, their commonefforts, social relations, and the way how they organisecommon work. Minsky’s well established concept ofknowledge frames as “artificial intelligence data struc-ture used to divide knowledge into substructures by rep-resenting ‘stereotyped situations’” [4] suggests that such“stereotyped situations”, in our case different researchcontexts with complex social structures and interrela-tions, play an important role in the way how knowledgestructures emerge and evolve. A. and M. Kohlhase [8]emphasized the importance of such practices for mathe-maticians and formalized them in the (slightly different)notions of theory graphs and framing (the latter consid-ered as ‘reframing’ in a Minsky inspired terminology[7]).

Computer Algebra at the border of mathematicsand computer science played an important and specialrole during any computer triggered technological break-through in mathematics in the last decades. It is a firstclass challenge to the CA community to organize thechanges towards a GDML for their own community andto contribute to the changes at large.

The setting of (not only) the SYMBOLICDATAProject to address the needs of the CA community andtheir severe subcommunities – considered as a “majorsocial frame” with many intimately related “smaller so-cial frames” – is a first class playground

• to study and explore own cooperate contexts andpractices under the special aspects and formalizationrequirements of modern semantic web technologies,

• to develop and communicate best practices along theIMU recommendations [11],

• and to advance towards a better understanding oftheir requirements and consequences,

since we have researchers well educated both in mathe-matics and computer science and the scientific CA com-munity is small enough to allow for social relations in aless institutionalized way.

Towards CASN — a Computer AlgebraSocial Network

Such a challenge meets other visions of the SYMBOL-ICDATA Project, in particluar to collect not only bench-mark and testing data but also valuable background in-

24

formation about the records in the database, e. g. in-formation about papers, people, history, systems, con-cerned with the examples in our collection. RDF is par-ticularly suited for this, for it provides both the conceptof typeless URIs within a typed world to point to re-sources of different types in a uniform way and it allowslinking to foreign URIs in other databases to build up asemantic network with many nodes where the node atsymbolicdata.org is only one in the multitude ofnodes of such a (distributed) Computer Algebra SocialNetwork.

There are plenty of activities towards such an ‘e-science world’, in particular by the Association of Ger-man Libraries [5], by the Zentralblatt Mathematik [13],by the MKM community [9] and others.

As explained in the introduction it is a great chal-lenge to small scientific communities to adopt such de-velopments for its own scientific communication pro-cesses and to join forces with other scientific commu-nities to get own requirements publicly recognised. Afirst step in such a direction is a more detailed descrip-tion of ongoing scientific processes using standard RDFterminology.

SYMBOLICDATA started such efforts within the CAscientific community, collecting and presenting

• information about scientific activities of people – asof Sept. 2014 the SYMBOLICDATA People databasecontains foaf:Person entries of 708 people fromthe CA scientific community that can be explored viathe SYMBOLICDATA SPARQL endpoint [14] – it ismirrored at [15],

• information about upcoming conferences – the in-formation is extracted via SPARQL query to [15]from http://symbolicdata.org/casn/UpcomingConferences/ and displayed in theWordpress based site of the German Fachgruppe[20],

• information about past conferences and conferencereports with references to the SYMBOLICDATA Peo-ple database about speakers and organizers,

• information about German CA working groups andthe SPP 1489 projects with references to the SYM-BOLICDATA People database,

• keyword enriched information about scientific pub-lications in the CA-Rundbrief of the German Fach-gruppe using the dcterms ontology – the informa-tion is displayed in the Wordpress based site of theGerman Fachgruppe [20],

• and semantic annotations to news in the blog ofthe German Fachgruppe as instances of RDF typesioc:BlogPost and bibo:Document attachedto the blog post URL.

A particularly interesting project was started in cooper-ation with Zentralblatt Mathematik (ZBMath) towards abetter author disambiguation. During the last years ZB-Math spent much effort for better author disambiguation

primarily using language processing technology to re-trieve data tracks of people from their stock of abstracts,see [13]. The SYMBOLICDATA references within ourPeople database offer additional insight into people ac-tivities (and – if properly recognised by the community– allows for active support and influence on a processthat touches both vivid personal and scientific interestsof the community), and we started to align SYMBOLIC-DATA People URIs with ZBMath URIs in the ZBMathPerson Matches table at http://symbolicdata.org/Data/ZBMathPeople/.

Despite the importance of the ongoing ’Big Data’harvesting processes for the moment this and other ac-tivities suffer from little attention of a broader CA au-dience. In our talk at the CICM-14 conference [6] weasked: “How turn passive users (listed in the SYMBOL-ICDATA People database) into active ones?” A first hur-dle is authentication. Nowadays there are three differentways to solve that problem:1. The ‘classical one’: Set up a local database with

user/password; users have to administer plenty ofsuch application/user/password records (of coursebest using RDF technology).

2. The ‘Google one’: Use the (OAuth based) authenti-cation service of one of the ’big players’. Your ad-vantage: one password fits all, but who knows whatthe guys are tracking . . .

3. The WebID approach: Use your browser certificateand a FOAF profile managed by your own to provideaccess.You register with SYMBOLICDATA your FOAF pro-file, we will take the challenge stored there and offerit mixed up with our challenge to your browser. Ifthe browser (with your certificate, imported into thebrowser from your source) returns the correct answerwe know that’s you sitting in front of it.

We started to set up such an infrastructure along theFOAF standards as ’proof of concept’:• The SYMBOLICDATA People database contains

’lightweight’ FOAF profiles.

• For any person interested to join activelythe CASN we generate a foaf:Personal-ProfileDocument that relates this ’lightweight’FOAF profile with your own FOAF profile asfoaf:primaryTopic.

• For a limited number of people from the GermanFachgruppe (yet as passive users) we created suchprofiles and use them to display information aboutthe different boards of the German Fachgruppe attheir website [20].

• You can take over your own profile at any convenientweb place under your control and extend it to meetthe authentication requirements and tell us about thatplace.We change your PersonalProfileDocument and youare ready actively to join the CASN process.

25

The vision of a Computer Algebra Social Network goesfar beyond that:• Maintain at your local site up-to-date information

about your working group and its people in a con-sistent RDF format as e. g. the AKSW team [1] doesat http://aksw.org/Team.html.

• Maintain your FOAF profile at a personal page con-taining all important public up-to-date informationabout your activities in a consistent RDF format as e.g. the AKSW team member Natanael Arndt does athttp://aksw.org/NatanaelArndt.html.

• Organize a regular harvesting process within thescientific community for such information to feedcommon pages at sites as e. g. http://www.computeralgebra.de, and to substitute part ofthe information centrally stored at SYMBOLICDATAtoday by decentrally managed one.

• Set up and run within the scientific community asemantic-aware Facebook-like Social Network andcontribute to it about all topics around Computer Al-gebra using tools that express your contributions inan RDF-based syntax.

The last point sounds quite visionary but it is in no wayutopic. The AKSW team provides a first prototype ofa tool that realizes the challenging concept of a Dis-tributed Semantic Social Network [17] to be running,in contrast to Facebook, on a multitude of independentnodes all over the world. Since the concept works alsowith a single node and can be extended later on, weset up such a node at symbolicdata.org for test-ing, see our CASN wiki page [16] for more information.Even if all this is very pre-alpha yet, the future is alreadyon the way. Don’t miss the train.

References[1] The Agile Knowledge Engineering and Seman-

tic Web Group at Leipzig University. http://aksw.org/About.html [2014-02-19]

[2] Developing a 21st Century Global Library forMathematics Research. Report of the Committeeon Planning a Global Library of the MathematicalSciences. The National Academies Press 2014.http://www.nap.edu/catalog.php?record_id=18619 [2014-09-24]

[3] EuDML – the European Digital Mathematical Li-brary. https://eudml.org/ [2014-09-23]

[4] Frame at Wikipedia. http://en.wikipedia.org/wiki/Frame_(artificial_intelligence) [2014-09-23]

[5] Gemeinsame Normdatei (GND). Informations-seite der Deutschen Nationalbibliothek. http://www.dnb.de/DE/Standardisierung/GND/gnd_node.html [2014-09-13]

[6] H.-G. Gräbe, A. Nareike, S. Johanning. TheSymbolicData Project — Towards a Computer

Algebra Social Network. In: Workshop andWork in Progress Papers at CICM 2014. CEUR-WS.org vol. 1186. http://ceur-ws.org/Vol-1186/#paper-21 [2014-09-13]

[7] S. Kaufman, M. Elliott, D. Shmueli: Frames,Framing and Reframing. In: G. and H.Burgess (eds.): Beyond Intractability. Con-flict Information Consortium, University ofColorado, Boulder. Posted: September 2003.http://www.beyondintractability.org/essay/framing [2014-09-23]

[8] A. and M. Kohlhase: Spreadsheet Interaction withFrames: Exploring a Mathematical Practice. In: In-telligent Computer Mathematics, Lecture Notes inComputer Science Volume 5625, 2009, pp 341–356.

[9] Mathematical Knowledge Management. The MKMinterest group. http://www.mkm-ig.org/[2014-09-13]

[10] A. Nareike. The SYMBOLICDATA sdsage pack-age. http://symbolicdata.org/wiki/PolynomialSystems.Sage [2014-02-28]

[11] J. Pitman, C. Lynch: Planning a 21st CenturyGlobal Library for Mathematics Research. Noticesof the AMS, August 2014.

[12] Sage – a free open-source mathematics softwaresystem. http://www.sagemath.org [2014-02-19]

[13] U. Schöneberg, W. Sperber. POS Tagging and itsApplications for Mathematics. In: Intelligent Com-puter Mathematics. Lecture Notes in Computer Sci-ence, Volume 8543, 2014, pp 213–223.

[14] The SYMBOLICDATA SPARQL Endpoint. http://symbolicdata.org:8890/sparql[2014-02-19]

[15] The CASN SPARQL Endpoint. http://symbolicdata.org:8891/sparql[2014-09-13]

[16] The SYMBOLICDATA Project Wiki. http://wiki.symbolicdata.org [2014-09-13]

[17] S. Tramp et al.: An Architecture of a Dis-tributed Semantic Social Network. In: Seman-tic Web Journal 2012, Special Issue on ThePersonal and Social Semantic Web.http://www.semantic-web-journal.net/sites/default/files/swj201_4.pdf[2014-09-23]

[18] Virtuoso Open-Source Edition. http://virtuoso.openlinksw.com/ [2014-02-19]

[19] World Digital Mathematics Library (WDML).http://www.mathunion.org/ceic/wdml/ [2014-09-23]

[20] Website of Fachgruppe Computeralgebra http://www.fachgruppe-computeralgebra.de/ [2014-03-06]

26

Shared Memory Concurrency for GAPReimer Behrends(TU Kaiserslautern)

behrends@mathematik.uni-kl.de

The GAP system [3], as it is introduced on the GAPWeb site, is an open-source system for computationaldiscrete algebra, with particular emphasis on compu-tational group theory. It provides a programming lan-guage, an extensive library of functions implementingalgebraic algorithms written in the GAP language aswell as large data libraries of algebraic objects. The ker-nel of the system is implemented in C, and the libraryis implemented in the GAP language. Both the kerneland the library were originally sequential and did notsupport parallelism.

In the 4-year long EPSRC project “HPC-GAP:High Performance Computational Algebra and Dis-crete Mathematics” (http://www-circa.mcs.st-and.ac.uk/hpcgap.php), started in Septem-ber 2009, a team of researchers at the University ofSt Andrews reengineered the GAP system to allow par-allel programming in it using both shared and distributedmemory approaches. In this article, we report on the re-sults of the HPC-GAP project with respect to paralleliz-ing execution on multicore systems with shared mem-ory. The concurrency model that we employ aims atmaking concurrency facilities available to GAP users,while preserving the existing codebase (hundreds ofthousands of lines of code and data) with as few changesas possible. To this end, the model preserves the appear-ance of sequentiality on a per-thread basis by contain-ing each thread within its own data space, while makingconcurrent interaction possible through selective shar-ing of data and by allowing the migration of objects be-tween data spaces.

Shared Memory: RegionsThe fundamental concept through which HPC-GAP reg-ulates concurrent interaction is that of a region. A regionis a data space in memory; each GAP object belongs toprecisely one region. Access to GAP objects is con-trolled through ownership of regions: in order to accessobjects within a region, a thread must first obtain exclu-sive or shared ownership of the region. As a rule, whena thread has exclusive ownership, it can read and modifyobjects within the region; when it has shared ownership,it can only read the objects. Violating these access rulesresults in a runtime error, thus disallowing access with-out ownership entirely.

This approach effectively makes data races – situa-tions where two threads concurrently modify the sameobject or where one thread modifies an object while an-other reads it – impossible, eliminating what is typicallythe major source of software defects in multi-threadedsystems. In this regard, our design differs from mostmainstream programming languages, which tend to notenforce this property (see, e.g., [2]).

Each thread has an associated thread-local region,of which it always has exclusive ownership. In partic-ular, objects in a thread’s thread-local region can neverbe accessed by other threads.

When using only a single thread, the thread’s be-havior is essentially indistinguishable from a sequentialsystem to the end user (though underlying libraries mayemploy concurrency). This design intentionally hidesthe complexities of parallelism from users who do nothave the necessary expertise in parallel programming.They can safely continue to use the system as though itwere sequential code while still benefiting from any par-allelized libraries and packages that others have written.By having their actions compartmentalized within themain thread’s region, their code will not interfere withany parallelized code and the parallelized code will notinterfere with their code.

In addition, code that requires concurrent interactioncan also create one or more shared regions. In order toobtain exclusive or shared ownership of a shared region,a thread must first acquire the read-write lock associ-ated with the region (a read lock for shared ownership, awrite lock for exclusive ownership). Shared regions aretypically created through the ShareObj(obj) func-tion, which creates a new shared region and moves objinside.

Threads can claim shared or exclusive ownership toa region through a new control structure, the atomicstatement. An atomic statement takes one or morearguments, optionally preceded by a readonly orreadwrite descriptor. The thread then gains shared(readonly) or exclusive (readwrite) ownershipfor the duration of the atomic statement. Example:

atomic readonly obj, readwrite obj2 do# Thread has shared ownership of the region# containing <obj> and exclusive ownership# of the region containing <obj2>. Ownership# of both regions will be relinquished when# control flow reaches the "od" keyword at# the end of the code block.

od;

27

For convenience, constant data (esp. large tables) canbe stored in a special read-only region. All threads havepermanent shared ownership of the read-only region,meaning that they can access the data in it as though itwere a shared region for which they hold a read lock, butwithout the extra overhead and inconvenience of havingto aquire one each time. The MakeReadOnly(obj)primitive puts obj in the read-only region.

Finally, HPC-GAP knows a public region, to whichall threads have constant read and write access. This isthe one exception to the rule that one has to have ex-clusive ownership in order to modify objects within aregion. As a consequence, only objects that expose ex-clusively atomic operations to GAP (i.e., operations thatcannot create data races) can be stored in the public re-gion. The public region therefore only holds certain spe-cial kinds of objects (such as those needed by the variousHPC-GAP synchronization primitives) as well as certaintypes of immutable objects. Functions, for example, arealways contained in the public region1, so that the samefunction can be called by multiple threads.

Objects can be migrated or copied between re-gions. Migration, unlike copying, is an inexpensiveoperation in that it simply changes the region mem-bership descriptor of an object. Migration can be per-formed through the MigrateObj(obj, target)function, which migrates objects between arbitrary re-gions, or the AdoptObj(obj) function, which mi-grates an object to the current thread-local region.

Multi-threadingIn order to use multiple threads, GAP programmersare encouraged to use the task library, which providesconvenient abstractions over low-level thread manage-ment2. The task library uses the concept of futures [3]similar to mainstream programming languages such asC# and Java.

The primary interface provided consists of theRunTask() and TaskResult() functions:

task := RunTask(f, x1, ..., xn);result := TaskResult(task);

RunTask() takes a function f and zero ormore values xi as its arguments. It then evaluatesf(x1, . . . , xn) asynchronously in a different thread.RunTask() finishes immediately (i.e. while f is stillbeing executed in parallel), returning a task descriptoras a result. The TaskResult() function takes a taskdescriptor as its sole argument, waits until that task hascompleted and returns the result of the underlying eval-uation of f(x1, . . . , xn).

The task library provides additional primitives (suchas waiting for the first of a set of tasks to finish, hav-ing the execution of tasks triggered by a condition,or the cancellation of tasks). But RunTask() andTaskResult() are the core primitives in that they al-low the concurrent execution of arbitrary computations

with an interface that is only slightly more complex thana regular function call.

Note that the evaluation of f(x1, . . . , xn) is per-formed in a separate thread; in order to make this pos-sible, any thread-local arguments are implicitly copiedto the new thread; likewise, the result (if thread-local)is copied back to the thread-local region of the threadperforming the TaskResult() call.

Example: Parallel MatrixMultiplication

Figure 1 uses the standard parallel matrix multiplicationalgorithm to illustrate the above concepts.

1 ParMatrixMultiplyRow := function(m1, m2, i)2 local result, j, k, n, s;3 result := [];4 atomic readonly m1, readonly m2 do5 n := Length(m1);6 for j in [1..n] do7 s := 0;8 for k in [1..n] do9 s := s + m1[i][k] * m2[k][j];10 od;11 result[j] := s;12 od;13 od;14 return result;15 end;1617 ParMatrixMultiply := function(m1, m2)18 local tasks, result;19 ShareObj(m1);20 ShareObj(m2);21 atomic readonly m1, readonly m2 do22 tasks :=23 List([1..Length(m1)],24 i -> RunTask(ParMatrixMultiplyRow,25 m1, m2, i));26 result := List(tasks, TaskResult);27 od;28 atomic readwrite m1, readwrite m2 do29 AdoptObj(m1);30 AdoptObj(m2);31 od;32 return result;33 end;

Figure 1: Parallel matrix multiplication.

The ParMatrixMultiply() function in lines 17–33 performs the actual multiplication. It takes twosquare matrices as its arguments. The ShareObj()primitives in lines 19–20 create new shared regions forthese matrices and migrate them inside. The atomicconstruct in lines 21–27 then acquires read locks for thetwo shared regions, granting the current thread sharedownership. The substance of the work occurs in lines22–25, where one task is started for each row vector inm1. This is done through the standard List() func-tion, which takes two arguments, a list and a function,and applies the function to each element in the list. Thisfunction performs a RunTask() call; thus, the resultof List() is a list of task descriptors. The secondList() invocation in line 26 then maps each of thetask descriptors to their results, returning a list of the

1Obviously, this holds only for the function’s code, which never changes, not any data that it operates on.2Of course, low-level thread and concurrency primitives are also available for advanced concurrency constructs.

28

row vectors of the product of the matrices. In lines 28–31, the two arguments are migrated back to the currentthread’s thread-local region; the AdoptObj() calls ef-fectively undo the Shareobj() calls in lines 19–20.

The actual multiplication operation for each rowvector takes place in the ParMatrixMultiplyRowfunction in lines 1–15. This is the basic matrix multipli-cation algorithm for a given row vector. The only differ-ence compared to the sequential version is the atomicstatement in lines 4–13, which gives the task temporaryshared ownership of the matrix regions. Note that thisis necessary even though the main thread had alreadydone the same: the tasks have no knowledge of whatthe main thread is currently doing and thus have to alsoclaim shared ownership on their own. Because all tasksrequire only read access to the matrices, shared owner-ship is sufficient and all tasks can execute in parallel (aslong as the hardware permits).

ConclusionA public beta release of HPC-GAP is planned for thenear future. If you would like access to the current pre-release version, please contact the author or the GAPGroup.

References[1] GAP – Groups, Algorithms, and Programming, Ver-

sion 4.7.5; 2014 http://www.gap-system.org

[2] Hansen, P. B. Java’s Insecure Parallelism. SIG-PLAN Notices, v.34 n.4, p.38–45, April 1999.

[3] Friedman, D. P. and Wise, D. S. The Impact of Ap-plicative Programming on Multiprocessing. 1976International Conference on Parallel Processing,p.263–272.

The GAP package SingularInterfaceM. Barakat, M. Horn, F. Lübeck, O. Motsak, M. Neunhöffer, H. Schönemann(TU Kaiserslautern, JLU Gießen, RWTH Aachen University, TU Kaiserslautern,triAGENS GmbH, TU Kaiserslautern)

barakat@mathematik.uni-kl.de, max.horn@math.uni-giessen.de,frank.luebeck@math.rwth-aachen.de, motsak@mathematik.uni-kl.de,max@9hoeffer.de, hannes@mathematik.uni-kl.de

What is SingularInterface?The GAP package SingularInterface is a highlyefficient and robust unidirectional low-level interface toSINGULAR [2, 3]. It is the outcome of an intensive col-laboration between core developers of both systems.

The goal of this interface is to map all of SINGU-LAR’s powerful functionality into GAP. To achieve thisit automatically wraps all SINGULAR datatypes and ex-ports all of SINGULAR’s interface procedures to GAP.1Furthermore, all procedures of any contributed librarycan be loaded on demand.2

This package is a rather “faithful” image of SINGU-LAR; it does not make an extensive attempt for a betterintegration of SINGULAR into the GAP ecosystem. Thisis intentionally left to other packages, which are free torealize this in different ways.

The development of SingularInterface hasreached a �-phase and is already actively used in someresearch projects. We hope to attract more users in thenear future, whose feedback will be crucial for a suc-cessful further development.

How to get it?To download and install SingularInterface

please follow the instructions on

http://gap-system.github.io/SingularInterface/

If you are reading this article, say, more than one yearin the future, and have a recent GAP installation, thenhopefully you already have a working version of thispackage.

To check that the package has been successfully in-stalled, start GAP and type:

gap> LoadPackage( "SingularInterface" );true

To see all imported procedures type:

gap> SI_<press TAB twice>

The SINGULAR library “standard.lib” is loadedby default. To see all imported SINGULAR library pro-cedures type:

gap> SIL_<press TAB twice>

To load any other library, e.g. “matrix.lib”, type:

gap> SI_LIB( "matrix.lib" );true

1With the prefix “SI_” prepended to their names.2They appear in GAP with the prefix “SIL_” prepended to their names.

29

GoalsThe motivation behind developing Singular-Interface is the increasing interest of various re-search projects in combining the strength of both sys-tems: GAP users get access to SINGULAR’s polynomialarithmetic and highly optimized Gröbner basis engine.

SINGULAR users gain a second front end language forthis engine – in addition to the current SINGULAR lan-guage – with an advanced object model primarily de-signed for modeling higher mathematical structures, aswell as access to GAP as an expert system for groupand representation theory.

An exampleHere is a short example in SINGULAR 4.0.1 demonstrating some basic procedures. On the left you see the SIN-GULAR code, on the right the corresponding GAP code. SINGULAR uses “=” for assignments and suppresses anyoutput while GAP uses “:=” for assignments and triggers the so-called View-method, which gives a very brief de-scription of the object (unless suppressed by a trailing “;;”). Basically, SINGULAR’s print procedure is mappedto the so-called Display-method in GAP. The current version of SingularInterface is 2014.09.23.

Start by loading SingularInterface in GAP.> // standard.lib is automatically preloaded> // this example needs no further libraries

gap> LoadPackage( "SingularInterface" );true

Define the ring R := Q[x0, x1, x2, x3] (with the monomial ordering degrevlex):> ring R=0,(x0,x1,x2,x3),dp;

> short=0;

> option(redTail);

gap> R := SI_ring( 0, "x0..3", [["dp",4]] );<singular ring, 4 indeterminates>gap> ## short=0 is the default, disable by:gap> ## Singular( "short=1" );gap> SI_option( "redTail" );true

Define the polynomial (x1 + x3)2:

> poly p=(x1+x3)^2; p;x1^2+2*x1*x3+x3^2

gap> AssignGeneratorVariables( R );#I Assigned the global variables#I [ x0, x1, x2, x3 ]gap> p := (x1+x3)^2;x1^2+2*x1*x3+x3^2gap> IsSingularPoly( p );true

Define the ideal I := hx20 � x1x3, x0x1 � x2x3iCR:> ideal I=x0^2-x1*x3,x0*x1-x2*x3;

> print(I);x0^2-x1*x3,x0*x1-x2*x3

gap> I := SI_ideal([x0^2-x1*x3, x0*x1-x2*x3]);<singular ideal, 2 gens>gap> Display( I );x0^2-x1*x3,x0*x1-x2*x3

The corresponding matrix i:> def i=matrix(I);

> print(i);x0^2-x1*x3,x0*x1-x2*x3

gap> i := SI_matrix( I );<singular matrix, 1x2>gap> Display( i );x0^2-x1*x3,x0*x1-x2*x3

The sum I + I means the sum of ideals:> J=I+I;

> print(J);x0^2-x1*x3,x0*x1-x2*x3

gap> J := I + I;<singular ideal, 2 gens>gap> Display( J );x0^2-x1*x3,x0*x1-x2*x3

Whereas i+ i means the sum of matrices:> print(i+i);2*x0^2-2*x1*x3,2*x0*x1-2*x2*x3

gap> Display( i + i );2*x0^2-2*x1*x3,2*x0*x1-2*x2*x3

The squared ideal I2 CR:> def I2=I^2;

> print(I2);x0^4-2*x0^2*x1*x3+x1^2*x3^2,x0^3*x1-x0*x1^2*x3-x0^2*x2*x3+x1*x2*x3^2,x0^2*x1^2-2*x0*x1*x2*x3+x2^2*x3^2

gap> I2 := I^2;<singular ideal, 3 gens>gap> Display( I2 );x0^4-2*x0^2*x1*x3+x1^2*x3^2,x0^3*x1-x0*x1^2*x3-x0^2*x2*x3+x1*x2*x3^2,x0^2*x1^2-2*x0*x1*x2*x3+x2^2*x3^2

30

The Gröbner basis of the ideal I is returned as a new different (but mathematically equal) ideal G:> def G=std(I);

> print(G);x0*x1-x2*x3x0^2-x1*x3x1^2*x3-x0*x2*x3

gap> G := SI_std( I );<singular ideal, 3 gens>gap> Display( G );x0*x1-x2*x3,x0^2-x1*x3,x1^2*x3-x0*x2*x3

The syzygies of the generators of G are the columns of the SINGULAR datatype module3:> def S=syz(G); S;S[1]=x0*gen(1)-x1*gen(2)-gen(3)S[2]=x1*x3*gen(1)-x2*x3*gen(2)-x0*gen(3)> print(S);x0, x1*x3,-x1,-x2*x3,-1, -x0

gap> S := SI_syz( G );<singular module, 2 vectors in free module ofrank 3>gap> Display( S );x0, x1*x3,-x1,-x2*x3,-1, -x0

To access the second column of S use:> S[2];x1*x3*gen(1)-x2*x3*gen(2)-x0*gen(3)> print(S[2]);[x1*x3,-x2*x3,-x0]

gap> S[2];<singular vector, 3 entries>gap> Display( S[2] );[x1*x3,-x2*x3,-x0]

To access the first entry of the second column of S use:> S[2][1];x1*x3> p-S[2][1];x1^2+x1*x3+x3^2

gap> S[2][1];x1*x3gap> p - S[2][1];x1^2+x1*x3+x3^2

To create a matrix use:> matrix m[3][2]=x0,x3, x1,x2, x3,x0;

> print(m);x0,x3,x1,x2,x3,x0

gap> m := SI_matrix(R,3,2,"x0,x3,x1,x2,x3,x0");<singular matrix, 3x2>gap> Display( m );x0,x3,x1,x2,x3,x0

To extract the (2,1)-entry from the matrix use:> m[2,1];x1

gap> m[[2,1]];x1

The sum of the module S and the matrix m is their augmentation:

> print(S+m);x0, x1*x3, x0,x3,-x1,-x2*x3,x1,x2,-1, -x0, x3,x0

gap> S + m;<singular module, 4 vectors in free module ofrank 3>gap> Display( S + m );x0, x1*x3, x0,x3,-x1,-x2*x3,x1,x2,-1, -x0, x3,x0

The developmentHow does it work?SingularInterface aims to be a comprehensivebridge between GAP and SINGULAR with as little over-head as possible, both in terms of speed and memory.To achieve this goal, some key design decisions werecrucial:

(1) Avoid converting data between the two systems,as conversions are expensive.

(2) Automate generating function bindings as muchas possible.

(3) We stay relatively low-level with the interface,mostly refraining from trying to change SINGU-LAR behaviour to be more GAP like (with oneexception, see below).

Regarding (1), on the GAP side we use “wrapperobjects” around SINGULAR objects. That is, tiny GAPobjects which essentially consist of a pointer to the ac-tual SINGULAR object (such as a polynomial) plus somemeta information (types, attributes). With the excep-tions of small integers and strings, we never automat-ically convert SINGULAR objects into “native” GAP

3The datatype module in SINGULAR 4.0.1 is in first approximation a specialized sparse data structure for column oriented matriceswith compressed columns, where each column has the datatype vector. For more details see the SingularInterface manual [1].

31

objects. Indeed, in most cases that would be point-less, as for further operations with the object, we wouldhave to convert it back into a SINGULAR object any-way. So when you have a SINGULAR polynomial pand call SI_deg(p), in the background, Singular-Interface extracts the pointer to the SINGULAR ob-ject from it, then invokes the SINGULAR interpreter Ccode for deg, and returns the result to the user (sincethe result is a small integer, it is not wrapped).

Of course when necessary, you can still convert fromand to “native” GAP objects (although this is one of theareas where there is still work to be done, in order tocover all possible SINGULAR coefficient ring types).

A major complicating factor for this approach is thatGAP and SINGULAR use very different memory man-agement systems (GAP uses a so-called “generationalmoving garbage collector”, in which objects changetheir position in memory over time, while SINGULARuse a more traditional “malloc” system plus referencecounting, and expects objects to stay at a fixed positionin memory). With some clever tricks, aided by a fewsmall but helpful changes on the SINGULAR side, thisnow works extremely well.

Regarding (2), here is one example: From the datastructures the SINGULAR interpreter uses to lookupfunction names (such as transpose), the build sys-tem of SingularInterface automatically gener-ates bindings for all SINGULAR functions in GAP(SI_transpose). Thus when the SINGULAR teamadds a new function, SingularInterface automat-ically supports it (after recompiling). This also coversSINGULAR library functions. Finally, in addition to in-terpreter and library functions, we also provide directaccess to select SINGULAR C++ kernel functions suchas p_Mult_mm (with _SI_ prepended) which can beused by experts to further optimize their code. This,too, is automatically generated and can thus easily beextended to expose more functionality, if requested.

Regarding (3), we mostly expose the SINGULAR in-terface faithfully and with no changes (as opposed totrying to make it “more GAP like”, or trying to fix per-ceived design flaws etc.). We plan to eventually add ahigh-level layer built atop the existing interface whichchanges some of this; however, this may well be in aseparate package. But providing this raw access hasmultiple advantages: It allows others to build alterna-tive high-level front ends (as everybody will have a dif-ferent idea about how to do that), and it also frees usfrom making complicated decisions on what is “right”and “wrong”. Finally, it has the added benefit that theSINGULAR manual can be used as a reference manualfor SingularInterface. There is one major ex-ception: We try to hide the SINGULAR concept of a“global” or “active” ring from users as much as possible.In SINGULAR, the result of a command like var(1)

implicitly depends on the “active” ring. Working withmultiple rings thus becomes rather tedious. To avoidthis, in SingularInterface, each GAP wrapperobject for “ring dependent” SINGULAR objects (such aspolynomials, ideals, modules, but not integers or ringsthemselves) carries a reference to the ring it belongs to.The user does not need to worry about “active” ringsat all. As a side effect, a few SINGULAR functionsneed to be called with one additional parameter, namelythe ring they refer to. For example, var(1) becomesSI_var(r,1), where r is the (now explicit) SINGU-LAR ring we refer to.

Note that all of this bypasses the SINGULAR lan-guage. However, to guarantee complete access to SIN-GULAR, one can still send arbitrary commands to theSINGULAR interpreter as a string passed to the functionSingular(). For details, we refer the reader to theSingularInterface manual (which is still work inprogress).

ActivityThe development of SingularInterface startedin May 2011. The project was generously supportedby the University of St Andrews, the University ofKaiserslautern, and DFG priority program SPP-1489.The C/C++ code was contributed by Max Horn, FrankLübeck, and Max Neunhöffer. To keep the interfaceslick and efficient Hans Schönemann and OleksandrMotsak made several changes and improvements on theside of SINGULAR. The homalg project [4] heavilyuses SINGULAR through its own IO-based interface.It was thus a natural candidate which helped to testand stabilize some parts of SingularInterfacethrough its extensive test suite.

OutlookWhile SingularInterface can already be used(and is used) for research work, there is still quite a lotto be done before we can call it a complete product. Weneed to add some more functionality, expand the man-ual, and add many test cases. Maybe the most urgent isto make convenient the construction of all types of ringssupported by SINGULAR.4

For this, we would appreciate your help. For ex-ample, if you experience any issue with Singular-Interface, please report it using our issue tracker atGitHub5. The same holds if you feel that some function-ality is missing or not as easy to access as it should be.We cannot guarantee to fulfil every wish, but it helps usto prioritize our efforts.

Beyond this, we also welcome contributions to thecode, the manual or the test suite. Ideally in the form ofpull requests6.

A future challenge would be to port Singular-Interface to HPC-GAP7 once the future multi-threaded SINGULAR is available.

4At the moment, they are accessible via the function Singular().5https://github.com/gap-system/SingularInterface/issues6https://github.com/gap-system/SingularInterface/pulls7HPC-GAP stands for “High Performance Computing GAP” and adds parallelization support to GAP(cf. article of R. Behrends, p. 27

in this issue of the CAR).

32

References

[1] M. Barakat, M. Horn, F. Lübeck, O. Motsak,M. Neunhöffer, H. Schönemann, Singular-Interface – A GAP interface to SINGU-LAR, (http://gap-system.github.io/SingularInterface/), 2011–2014.

[2] W. Decker, G.-M. Greuel, G. Pfister, and H. Schöne-mann, SINGULAR 3-1-6 — A computer algebra sys-

tem for polynomial computations, (http://www.singular.uni-kl.de), 2013.

[3] The GAP Group, GAP – Groups, Algorithms,and Programming, Version 4.7.5, (http://www.gap-system.org), 2014.

[4] The homalg project authors, The homalg project– Algorithmic Homological Algebra, (http://homalg.math.rwth-aachen.de/),2003–2014.

Berichte über Arbeitsgruppen

Arbeitsgruppe Algebra und diskrete Mathematik an der Universität Osnabrück

Winfried Bruns (Osnabrück)

Die Arbeitsgruppe Algebra und diskrete Mathematikdes Instituts für Mathematik der Universität Osnabrückbesteht zurzeit aus vier Professoren (H. Brenner, W.Bruns, T. Römer, H. Spindler), vier Postdocs und sie-ben Doktoranden. Die Professur von Bruns, der am30.09.2014 in den Ruhestand tritt, wird ab April 2015durch eine Juniorprofessur (M. Juhnke-Kubitzke) er-setzt.

Die Arbeitsgruppe war 2009–2012 Bestandteil desuniversitätseigenen Graduiertenkollegs „Kombinatori-sche Strukturen in Algebra und Topologie“ und ist seitOktober 2013 am Osnabrücker DFG-GRK „Kombina-torische Methoden in der Geometrie“ beteiligt. Das seit1997 bestehende Normaliz-Projekt wird aktuell durchdas DFG-SPP „Experimentelle Methoden in Algebra,Geometrie und Zahlentheorie“ gefördert.

Zu den langjährigen Kooperationspartnern gehörenMathematiker in Ann Arbor, Bukarest, Essen, Genua,Hanoi, Lexington, San Francisco, Salt Lake City, Shef-field und Tokio.

Das zentrale Forschungsgebiet der Arbeitsgruppe istdie kommutative Algebra unter Einbeziehung der alge-braischen Geometrie, algebraische Aspekte der Kom-binatorik und der Darstellungstheorie. Über viele Jah-re sind Beiträge zu determinantiellen Ringen und Idea-len, affinen Monoiden und Monoid-Algebren, homo-logischen Invarianten graduierter Ringe, Hilbert-Kunz-Theorie, Tight closure, Grothendieck-Topologien, tropi-scher Geometrie und Arrangements von Hyperebenenhervorgegangen.

Die gegenwärtig und in den letzten Jahren bearbei-teten Themen sind insbesondere die (Nicht-) Lokalisie-rung von Tight Closure, Irrationalität von Hilbert-Kunz-Multiplizitäten, arithmetische und geometrische Defor-

mationen von Vektorbündeln, symmetrische Asympto-tik von Moduln, Gröbner-Basen und Initial-Ideale bzw.-Algebren determinantieller Ideale bzw. Algebren, Rela-tionen von Minoren, Stanley- und Hilbert-Zerlegungen,algebraische Aspekte von Hyperebenen-Arrangements,generische tropische Varietäten.

Für die Computeralgebra ist das Projekt Normalizsicherlich am interessantesten. Für ein normales affi-nes Monoid berechnet Normaliz die Hilbert-Basis, dieHilbert-Reihe zu einer Z-Graduierung sowie zusätzlicheDaten, die bei der Berechnung von Hilbert-Basen undHilbert-Reihen notwendig sind oder sich nebenbei erge-ben. Dazu gehören insbesondere Triangulierungen undStanley-Zerlegungen.

Ein normales affines Monoid entsteht als Durch-schnitt eines rationalen Kegels mit einem Gitter. Des-halb ist es nichts anderes als die Lösungsmenge eineshomogenen Systems linearer diophantischer Unglei-chungen, Gleichungen und Kongruenzen. Die Hilbert-Basis ist das eindeutig bestimmte minimale Erzeugen-densystem (bezüglich der Addition).

Seit Version 2.11 berechnet Normaliz aber auch Lö-sungen von entsprechenden inhomogenen Systemen, al-so Gitterpunkte in rationalen Polyedern. Die Erweite-rung NmzIntegrate berechnet Hilbert-Reihen zu poly-nomialen Gewichtsfunktionen und Integrale von Poly-nomen über Polytope.

Normaliz ist in C++ geschrieben, nutzt GMP fürGroßzahl-Arithmetik und OpenMP für Parallelisierung.Es steht als ausführbares Programm für die gängigenBetriebssysteme zur Verfügung und ist über sein Biblio-theks-Interface in CoCoA, polymake, GAP, Regina undals optionales Paket in Sage eingebunden. Außerdemgibt es Interfaces zu Macaulay 2 und Singular.

33

Promotionen in der Computeralgebra

Patrick Njionou Sadjang: Moments of Classical Orthogo-nal PolynomialsBetreuer: Wolfram Koepf (Kassel)Zweitgutachter: Mama Foupouagnigni (Yaounde, Came-roon)Oktober 2013http://nbn-resolving.de/urn:nbn:de:hebis:34-2013102244291Abstract: In this work simple formulas for the moments forall families of classical orthogonal polynomials of the Askey-Wilson scheme (Koekoek, Lesky and Swarttouw: Hypergeo-metric orthogonal polynomials and their q-analogues, Sprin-ger, Berlin, 2010) are developed. Furthermore, the generatingfunctions or exponential generating functions for those mo-ments are given. In order to obtain those moments, we havestated the inversion formulas for all those families, also, wehave developed many connection formulas between specificpolynomial bases.

Thomas Bächler: Counting Solutions of Algebraic Sys-tems via Triangular DecompositionBetreuer: Wilhelm Plesken (Aachen)Zweitgutachter: Eva Zerz (Aachen)Juli 2014http://darwin.bth.rwth-aachen.de/opus3/volltexte/2014/5104/Zusammenfassung: Das Ziel dieser Dissertation ist die al-gorithmische Analyse von Lösungsmengen polynomiellerGleichungs- und Ungleichungssysteme. Um ein Maß für dieGröße einer solchen Menge anzugeben, wird das Zählpoly-nom definiert, welches als Verallgemeinerung der Kardinali-tät einer endlichen Menge verwendet wird. Die Berechnungdes Zählpolynoms erfordert die Zerlegung der Lösungsmen-ge in paarweise disjunkte Teilmengen, die durch eine spe-zielle Art polynomieller Dreieckssysteme, genannt einfacheSysteme, gegeben sind. Diese einfachen Systeme haben auchfür sich gesehen interessante Eigenschaften, welche eben-falls studiert werden. Insbesondere kann man sie wegen ih-rer Dreiecksstruktur iterativ lösen und so eine klare Beschrei-bung ihrer Lösungsmenge erhalten. Einfache Systeme undZählpolynome werden verwendet, um algebraische Varietä-ten und konstruierbare Mengen zu studieren. Schließlich wirddas Zählpolynom benutzt, um die Anzahl der Lösungen be-stimmter polynomieller Systeme über endlichen Körpern zubestimmen.

Dreieckssysteme werden häufig verwendet, um Glei-chungssysteme iterativ zu lösen. Da beliebige nicht-lineareSysteme im Allgemeinen nicht in Dreieckssysteme überführtwerden können, ist es nötig, die Lösungsmengen in kleinereTeilmengen zu zerlegen, welche durch Dreieckssysteme ge-geben sind. Eine solche Zerlegung heißt Dreieckszerlegung.

In den 1930ern hat Joseph Miller Thomas eine Methodezur Zerlegung in einfache Systeme eingeführt. Diese Metho-de unterscheidet verschiedene Fälle exakt durch die Einfüh-rung von Ungleichungen. Dies hat den Nebeneffekt, dass dieursprüngliche Menge in paarweise disjunkte Teilmengen zer-legt wird. Seine Methode ist sehr elementar und benötigt kei-ne fortgeschrittenen Kenntnisse der Theorie von Ringen undIdealen.

Die Thomas-Zerlegung ist die einzige bekannte Methodezur Berechnung des Zählpolynoms der Lösungsmenge einesbeliebigen Polynomsystems. Falls eine Menge endlich ist, soentspricht ihr Zählpolynom ihrer Kardinalität. Für eine un-

endliche Menge kodiert das Zählpolynom Informationen überdie Faserungsstruktur der Menge, die durch die Wahl und dieReihenfolge der Unbestimmten festgelegt wird. Es hilft da-bei, die Gleichheit von Mengen zu entscheiden und enthältInformationen über die Lösungsmenge, wie zum Beispiel ih-re Dimension. In einigen Fällen kann es benutzt werden, umdie Anzahl der Lösungen eines polynomiellen Systems übereinem endlichen Körper zu zählen.

In dieser Dissertation wird das Zählpolynom axiomatischdefiniert und seine wichtigsten Eigenschaften werden disku-tiert. Eine Verallgemeinerung des Zählpolynoms wird ange-geben, genannt der Zählbaum. Ein neuer Algorithmus zurBerechnung der Thomas-Zerlegung über beliebigen Körpernwird präsentiert. Insbesondere ist dieser Algorithmus der ers-te, der diese Zerlegung über Körpern positiver Charakteristikberechnen kann. Eine Implementierung dieses Algorithmusim Computeralgebrasystem Maple wird bereitgestellt, wel-che die Zerlegung über endlichen Körpern und über endlicherzeugten Erweiterungen der rationalen Zahlen durchführenkann.

Das Verhalten von Zählpolynomen und Zählbäumen un-ter Transformationen des zugrundeliegenden Polynomsys-tems wird analysiert. Eine Verbindung zwischen einfachenSystemen und Einbettungen affiner oder projektiver Varie-täten in den affinen respektive den projektiven Raum wirdhergestellt, indem jedem einfachen System ein Ideal zuge-ordnet wird. Diese Verbindung wird für den Fall normalertorischer Varietäten ausführlich diskutiert. Schließlich wer-den die Thomas-Zerlegung und Zählpolynome auf das Stu-dium rationaler Abbildungen und auf die Bestimmung derAnzahl von Lösungen bestimmter Gleichungs- und Unglei-chungssysteme über endlichen Körpern angewendet.

Daniel Duviol Tcheutia: On Connection, Linearizationand Duplication Coefficients of Classical Orthogonal Po-lynomialsBetreuer: Wolfram Koepf (Kassel)Zweitgutachter: Mama Fouopouagnini (Yaounde, Came-roon)Juli 2014http://nbn-resolving.de/urn:nbn:de:hebis:34-2014071645714Abstract: In this work, we have mainly achieved thefollowing:

1. we provide a review of the main methods used for thecomputation of the connection and linearization coef-ficients between orthogonal polynomials of a conti-nuous variable, moreover using a new approach, theduplication problem of these polynomial families issolved;

2. we review the main methods used for the computationof the connection and linearization coefficients of or-thogonal polynomials of a discrete variable, we solvethe duplication and linearization problem of all ortho-gonal polynomials of a discrete variable;

3. we propose a method to generate the connection, linea-rization and duplication coefficients for q-orthogonalpolynomials;

4. we propose a unified method to obtain these coeffi-cients in a generic way for orthogonal polynomials onquadratic and q-quadratic lattices.

34

Our algorithmic approach to compute linearization, connecti-on and duplication coefficients is based on the one used byKoepf and Schmersau and on the NaViMa algorithm. Ourmain technique is to use explicit formulas for structural iden-tities of classical orthogonal polynomial systems. We findour results by an application of computer algebra. The ma-jor algorithmic tools for our development are Zeilberger’s al-gorithm, q-Zeilberger’s algorithm, the Petkovšek-van-Hoeijalgorithm, the q-Petkovšek-van-Hoeij algorithm, and Algo-rithm 2.2, p. 20 of Koepf’s book Hypergeometric Summationand its q-analogue.

Anen Lakhal: Elimination in Ore AlgebrasBetreuer: Wolfram Koepf (Kassel)Zweitgutachter: Werner Seiler (Kassel)Juli 2014http://nbn-resolving.de/urn:nbn:de:hebis:34-2014080845851Zusammenfassung: Viele spezielle Funktionen sind Lösun-gen linearer Differenzen- und Differentialgleichungssystememit polynomialen Koeffizienten. Für eine gegebene Funktionerzeugen diese Gleichungen, betrachtet als Operatorpolyno-me, ein Linksideal in einer nicht-kommutativen Algebra, ge-nannt Ore-Algebra. Dieses Ideal zusammen mit endlich vie-len Anfangswerten charakterisiert die Funktion eindeutig undauf dieses Objekt sind Gröbner-Basen-Techniken anwendbar.Viele Fragestellungen in Bezug auf spezielle Funktionen, diesich durch obige Ideale beschreiben lassen, können durch Eli-mination geeigneter nicht-kommutativer Variablen in diesemIdeal gelöst werden.

Diese Dissertation liefert einen Forschungsbeitrag zu fol-genden Themen:

1. Es wird ein Überblick über den theoretischen alge-braischen Hintergrund gegeben sowie über algorithmi-sche Aspekte verschiedener Methoden, die Gröbner-Eliminationsverfahren in Ore-Algebren verwenden,um Probleme bezüglich spezieller Funktionen zu lö-sen.

2. Es werden in ausführlicher Weise Algorithmen präsen-tiert, die auf Gröbner-Eliminationsverfahren basierenund die das „Creative telescoping“-Verfahren für Sum-men und Integrale spezieller Funktionen durchführen.

3. Alle beschriebenen Algorithmen werden untersuchtund anhand erklärender Beispiele in dem Computeral-gebrasystem Maple miteinander verglichen. Das Zieldieser Untersuchung war herauszufinden, inwieweitnicht-kommutative Gröbner-Eliminationsverfahren ef-fizient angewendet werden können, um „Creative te-lescoping“ durchzuführen.

Ulrich Thiel: On restricted rational Cherednik algebrasBetreuer: Gunter Malle (Kaiserslautern)Zweitgutachter: Raphaël Rouquier (Los Angeles)Juli 2014dr.hut-verlag.de/978-3-8439-1674-5.htmlZusammenfassung: The aim of this thesis is to shed somelight on the representation theory of restricted rational Che-rednik algebras - primarily for exceptional complex reflectiongroups for which almost no results exist so far. The centraltopics are specific problems posed by Gordon concerning thestructure of the Verma modules and the simple modules of re-stricted rational Cherednik algebras, and Martino’s conjecturewhich relates Calogero-Moser families defined by the blockstructure of these algebras with Rouquier families defined bythe block structure of Hecke algebras.We give - for the first time - explicit results about the blockstructure, the dimensions of the simple modules, the decom-position matrices of the Verma modules, and the structure ofthe simple modules as graded modules for the underlying re-flection group - and thus the answers to Gordon’s questions -for generic parameters for around half of the 34 exceptionalcomplex reflection groups. While we can confirm in this waythe generic part of Martino’s conjecture for all these groups,it turns out as a surprise that the conjecture is wrong for thegroup G25. This is the first and only counter-example to thisconjecture so far, and there is no abstract theoretical explana-tion for the failure yet.Due to the exceptional nature of exceptional complex reflec-tion groups the approach taken in this thesis differs from theexisting literature in so far as it is computational and expe-rimental. This thesis is the first approach to computationsin rational Cherednik algebras and their modules, and eventhough we make use of the powerful computer algebra sys-tem Magma, we still have to introduce several new computa-tional methods along with their implementation to deal withthese problems. This includes for example a new Las Vegasalgorithm for computing the head of a local module and forcomputing the decomposition matrix of a constituent-closedfamily of local modules. These computational aspects cul-minated in the development of a Cherednik Algebra Mag-ma Package (CHAMP for short) which provides a user-friendly and flexible way to perform basic computation in(restricted) rational Cherednik algebras and Verma modu-les in arbitrary characteristic (CHAMP is freely available athttp://thielul.github.io/CHAMP/).The hope is that the results presented here - along withCHAMP itself - will lead to new theoretical insight, whichis hard to gain when the situation for the exceptional groupsis not understood.

35

Berichte von Konferenzen

1. Experimentelle Methoden in der AlgebraLeibniz University Hannover, Germany,24.03.2014 – 26.03.2014www.icm.tu-bs.de/ag_algebra/Workshop-NTH

Vom 24.-26. März 2014 fand an LU Hannover eine Ta-gung zum Thema ’Experimentelle Methoden in der Alge-bra’ statt. Organisiert wurde die Tagung von Bettina Eick(Braunschweig) und Anne Frühbis-Krüger (Hannover). Die11 Hauptvortragenden der Konferenz deckten ein breitesSpektrum innerhalb der Computeralgebra ab. So gab es Vor-träge zur algorithmischen Gruppentheorie, zur Darstellungs-theorie, zur Kohomologietheorie und zur algebraischen Geo-metrie. Die Konferenz bildete damit ein vielfältiges Pro-gramm. Ein Fortführung ist im März 2015 an der TU Braun-schweig geplant.

Bettina Eick (Braunschweig)

2. 20th Conference on Applications of ComputerAlgebra (ACA 2014)New York, USA, 9.-12. Julifaculty.fordham.edu/rlewis/aca2014/

Vom 9. bis zum 12. Juli fand die 20. Conference on Appli-cations of Computer Algebra in New York statt. Sie wurdeorganisiert von Robert H. Lewis (General Chair), Tony Shas-ka, Ilias Kotsireas (Program Chairs) und Eugenio Roanes-Lozano, Stanly Steinberg, Michael Wester, José Luis GalánGarcía (Advisory Committee).Das Treffen fand in entspannter Atmosphäre am Bronx Cam-pus der Fordham University statt, wo auch die meisten Teil-nehmer untergebracht waren.Eröffnet wurde die zwanzigste Auflage der ACA-Konferenzserie mit einem Plenarvortrag von Wen-shin Lee(University of Antwerp) zum Thema “From Computer Al-gebra to Signal Processing”. Danach verteilte sich das Ge-schehen auf drei bis vier parallel laufende Special Sessions.Stark vertreten war diesmal die algorithmische Behandlungvon Differential- und Differenzengleichungen mit den Spe-cial Sessions AADIOS: Algebraic and Algorithmic Aspectsof Differential and Integral Operators und ComputationalDifferential and Difference Algebra. Die weiteren der insge-samt elf Special Sessions waren:

• Computer Algebra Aspects of Finite Rings and Their Ap-plications

• Computer Algebra in Coding Theory and Cryptography• Integration: Implementation and Applications• Computer Algebra in Education• Algorithms and Applications in the Geometry of Alge-

braic Curves and Surfaces

• Innovative Applications and Emerging Challenges• Arithmetic Geometry• Group Actions in Algebra and Geometry• Computer Algebra in Algebraic Topology and its Appli-

cations• Gröbner Bases and Applications.

Beim Bankett am Freitag Abend gab Michael Webster, einMitbegründer der traditionsreichen ACA-Konferenzserie,humorvolle persönliche Tipps zur Konferenzorganisationund unterhielt die Gäste mit Anekdoten aus zwanzig JahrenACA.Die nächste ACA-Konferenz wird vom 20. bis 23. Ju-li 2015 in Kalamata, Griechenland stattfinden (http://www.singacom.uva.es/ACA2015). Vorschläge fürSpecial Sessions können bis zum 16. Januar 2015 eingereichtwerden.

Michael Wibmer (Aachen)

3. 39th International Symposium on Symbolicand Algebraic Computation (ISSAC 2014)Kobe, Japan, 23.7.2014 – 25.7.2014www.issac-symposium.org/2014

Vom 23. bis 25. Juli dieses Jahres fand in Kobe die jährlicheISSAC-Tagung statt. Die organisatorische Leitung teiltensich Kosaku Nagasaka (Kobe University) und Franz Wink-ler (Johannes Kepler Universität, Linz). Den Posten des Pro-gram Committee Chair hatte Agnes Szanto (North CarolinaState University, Raleigh) inne. Unterstützt wurde die Kon-ferenz von einer Reihe von Sponsoren. Darunter befandensich Wolfram und Maplesoft, die vor dem KonferenzbeginnWorkshops rund um ihre Produkte anboten (teilweise nur aufjapanisch).Ebenfalls vor offiziellem Konferenzbeginn fand ein Tutori-entag statt. Besonders hervorzuheben ist hier der Vortragvon François Le Gall (University of Tokyo) mit dem Ti-tel “Algebraic Complexity Theory and Matrix Multiplicati-on”. Der Vortragende veranschaulichte dem Publikum, wieer es schaffte, die obere Schranke des Exponenten ! bei derMatrix-Multiplikation von ! < 2.3729 auf ! < 2.3728639zu reduzieren. Die dazugehörige Publikation ist auch imTagungsbericht der ISSAC 2014 erschienen. Neben diesemHighlight wurden den Konferenzteilnehmern u.a. auch Me-thoden präsentiert, wie man Computeralgebrasysteme aufmobilen Plattformen entwickeln kann (“How to develop amobile computer algebra system” von Mitsushi Fujimoto,Fukuoka University of Education).Die folgenden Tage waren mit einem abwechslungsreichenProgramm gefüllt. Nachdem man morgens auf dem Weg zurUniversität einen Teil des Berges Rokko bestiegen hatte, be-gann der Tag mit einem exzellenten Vortrag eines eingela-denen Wissenschaftlers: Norioki Arai (National Institute ofInformatics) referierte in humorvoller Weise über die auto-matisierte Lösbarbeit von standardisierten Mathematikauf-gaben, David Stoutemyer (University of Hawaii) hielt einenprovokativen Vortrag über Computeralgebra mit Gleitkom-mazahlen und Bernd Sturmfels berichtete über sogenann-te Maximum-Likelihood-Verfahren für Matrizen mit Ein-schränkungen bezüglich dem Rang. Es folgten mehr als 50interessante Vorträge mit einer vielseitigen Auswahl an ab-gedeckten Forschungsbereichen; von schneller Multiplikati-on über Lineare Algebra bis hin zu Differential- und Diffe-renzengleichungen.Besonders zu loben ist auch das gewählte Konzept des Kon-ferenzdinners, das in einem Restaurant in der Nähe des Ha-fens stattfand. Dort gab es viele Stehtische, aber nur eine

36

begrenzte Anzahl an Sitzplätzen. Dadurch wurde die Mög-lichkeit geschaffen, eine Vielzahl an Teilnehmern kennenzu-lernen und mit ihnen ins Gespräch zu kommen. Das Buffetwar facettenreich, und die Preisverleihungen trugen zur all-gemeinen guten Stimmung bei.

Beim Business Meeting wurden folgende Beschlüsse ge-fasst: ISSAC 2016 findet an der Wilfried Laurier Universityin Waterloo (Kanada) statt. Arne Storjohann (University ofWaterloo) wird Mitglied im Steering Committee. Des Weite-ren wurde der Beschluss von Wolfram verkündet, in Zukunftnicht mehr als Sponsor der ISSAC-Konferenz aufzutreten.

Die nächste ISSAC-Tagung findet an der University of Bathin England statt. Die Einladung, wissenschaftliche Arbeitendafür einzureichen, ist bereits versendet.

Albert Heinle (Waterloo)

4. International Congress of Mathematical Soft-ware 2014

Hanyang University, Seoul, Korea, 05.08.2014 –09.08.2014

voronoi.hanyang.ac.kr/icms2014/

om 5.-9. August 2014 fand die ICMS (International Con-gress of Mathematical Software) in Seoul (Korea) als Sa-tellitentagung zum ICM Congress statt. Hauptorganisatorender Tagung waren Hoon Hong, Chee Yap und Deok-SooKim. Auf der Tagung wurden 5 Invited Lectures von Jona-than Borwein, Bruno Buchberger, Andrew Sommese, Koki-chi Sugihara und Lloyd N. Trefethen vorgestellt. Dazu gab es17 Special Sessions aus diversen Gebieten der Mathematik,zum Beispiel zu den Themen Computational Group Theory,Coding Theory, Computational Topology, Geometry, Curvesand Surfaces oder Groebner Bases. Insgesamt war es einesehr interessante, breit angelegte Tagung, in der auch vieleGebiete der Computeralgebra angesprochen wurden. Die Ta-gung wurde auch wegen der schönen und interessanten Um-gebung in Seoul von den Teilnehmern sehr gut aufgenom-men.

Bettina Eick (Braunschweig)

5. First GAP DaysAachen, 25.08.2014 – 29.08.2014gapdays2014.coxeter.de

The first GAP Days took place during the last week ofAugust at the RWTH Aachen University. Besides GAPusers, package authors and core developers, also main de-velopers of NORMALIZ, polymake, and SINGULAR at-tended the meeting and made substantial contributions tostabilize and improve the existing GAP interface packagesNormalizInterface, PolymakeInterface, andSingularInterface.

PolymakeInterface is already distributed with GAP.During the meeting it was added to the polymake’s exten-sive test suite to guarantee future compatibility. A �-versionof NormalizInterface will soon be available. The firstpublic release of SingularInterface is now availableat

http://gap-system.github.io/SingularInterface/

See also the article

“The GAP package SingularInterface”

in this issue of the CAR. The further development of HPC-GAP was another major issue and considerable progress hasbeen achieved. The list of participants on the homepage con-tains links to the slides of the talks, where also the feedbackof the participants on their work during the meeting has beencollected.

GAP Days are meetings where developers and users withGAP programming experience are invited to influence thefuture development of GAP by initiating and contributing todiscussions and coding sprints. As enough GAP experts arearound for technical support, the meetings also offer goodopportunities for people to work on their own packages.

The meetings are also suitable for advertising recent deve-lopments in core GAP and packages via short talks. Howe-ver, the focus of such meetings is on code development, withtalks only playing a minor role.

Mohamed Barakat, Max Horn, Frank Lübeck (Kaiserslau-tern, Gießen, Aachen)

Hinweise auf Konferenzen

1. Seventh de Brún Workshop on HomologicalPerturbation TheoryNUI Galway, Ireland, 01.12.2014 – 05.12.2014hamilton.nuigalway.ie/HPT

The workshop aims to bring together those interested in ho-mological perturbation theory, its applications, and relatedtopics in geometry, topology and computer science.

2. Polymake workshop at TU BerlinTU Berlin, 05.12.2014www.polymake.org/doku.php/workshop1214

A workshop for users of polymake and friends of polyhe-dral geometry in general. The format will be slightly diffe-rent this time, as we are featuring two plenary lectures byMatthias Beck (SFSU) and David Bremner (U Brunswick).In addition we will provide a number of tutorials on variousaspects of polymake. This includes our regular help desk

where you can discuss your individual ideas, suggestions,questions, complaints.

3. 12th International Conference on Artificial In-telligence and Symbolic Computation AISC2014

University of Sevilla, Spain, 11.12.2014 –13.12.2014

www.glc.us.es/aisc2014

As usual the conference welcomes papers with a strong AIcomponent that make use of symbolic computation in a widesense (not excluding but not restricted to computer algebra).However, AISC 2014 aims at extending the scope of this se-ries of conferences to computing in AI thus covering newareas.

37

4. CoGrAl2015 - Computations in Groups andAlgebrasFriedrich Schiller University Jena, 16.02.2015 –19.02.2015cogral2015.uni-jena.de

The aim of the workshop is to shed some light on variousrecent aspects of finite group theory, with a particular viewtowards algorithms and computations. More specifically, wewill focus on the following topics: Cohomology of finite-dimensional algebras, Structure of p-groups and fusion sys-tems, Block theory of finite groups.

5. ALCOMA15 - Algebraic combinatorics andapplicationsKloster Banz close to Bamberg, 15.03.2015 –20.03.2015alcoma15.uni-bayreuth.de

ALCOMA15 is a meeting of COST Action IC1104[http://www.network-coding.eu/]. The intention is to bringtogether representatives of research groups that work in par-ticular in the field of constructive theory of designs and co-des, or on closely related topics. A special focus is on q-analogues of designs and random network coding. This con-ference is dedicated to the memory of our friend and col-league Axel Kohnert. The proceedings of the conference willbe published as a dedicated volume of the journal Ädvancesin Mathematics of Communications"

6. Experimentelle Methoden in der Algebra undZahlentheorieNiedersächsische Technische Hochschule,26.05.2015 – 29.05.2015www.icm.tu-bs.de/ag_algebra/Workshop-NTH

This workshop organized by Bettina Eick (Braunschweig),Anne Frühbis-Krüger (Hannover), and Claus Fieker (Kai-serslautern) is located on the boundary between group theo-ry, ring theory, number theory and algebraic geometry withinthe framework of computational algebra. Its aim is to bringtogether researchers from all these areas and to facilitate dis-cussions among them.

7. MEGA-2015: Effective Methods in AlgebraicGeometryUniversity of Trento, Italy, 15.06.2015 –19.06.2015mega2015.science.unitn.it

MEGA is the acronym for Effective Methods in AlgebraicGeometry (and its equivalent in many other languages). Thisseries of biennial international conferences, with a traditiondating back to 1990, is devoted to computational and app-lication aspects of Algebraic Geometry and related topics.<br/> The conference will comprise invited talks, regularcontributed talks, presentations of computations, and a pos-ter session; the latter three are subject to a competitive sub-mission process.

8. Theory and applications of syzygiesSaarbruecken, 01.07.2015 – 03.07.2015www.math.uni-sb.de/ag-schreyer/conference

This is a conference organized by Christian Bopp, DanielErman, Michael Hahn, Hannah Markwig, and Fabio Tantur-ri on the occasion of Frank-Olaf Schreyer’s 60th birthday.

9. ISSAC 2015

Bath, England, 7.07.2015 – 9.07.2015

www.issac-conference.org/2015

The International Symposium on Symbolic and AlgebraicComputation (ISSAC) is the premier conference for researchin symbolic computation and computer algebra. ISSAC 2015will be the 40th meeting in the series, which started in 1966and has been held annually since 1981. The conference pres-ents a range of invited speakers, tutorials, poster sessions,software demonstrations and vendor exhibits with a center-piece of contributed research papers.

10. ACA 2015 - 21th Conference on Applicationsof Computer Algebra

Kalamata, Greece, 20.07.2015 – 23.07.2015

www.singacom.uva.es/ACA2015

The ACA meetings are organized as a series of Special Ses-sions. The Special Sessions proposals for the ACA 2015Conference should be submitted to the Program Chair ofthe Conference, Edgar Martinez-Moro (edgar@maf.uva.es).Deadline for Special Sessions proposals: January 16, 2015

11. CASC 2015 –17th International Workshop onComputer Algebra in Scientific Computing

Aachen, 14.09.2015 –18.09.2015

The methods of Scientific Computing play an important ro-le in the natural sciences and engineering. Significance andimpact of computer algebra methods and computer algebrasystems for scientific computing has increased considerablyover the last decade.Nowadays, computer algebra systems such as CoCoA, Ma-caulay, Magma, Maple, Mathematica, Maxima, Reduce, Sin-gular and others enable their users to exploit their powerfulfacilities in symbolic manipulation, numerical computationand visualization.The ongoing development of computer algebra systems, in-cluding their integration and adaptation to modern softwareenvironments, puts them to the forefront in scientific com-puting and enables the practical solution of many complexapplied problems in the domains of natural sciences and en-gineering.The topics addressed in the workshop cover all the basic are-as of scientific computing as they benefit from the applicati-on of computer algebra methods and software.The 17th International Workshop on Computer Algebra inScientific Computing (CASC 2015) will be held in Aachen,Germany, from September 14 to 18, 2015. The Local Arran-gement Chairs are Eva Zerz and Viktor Levandovskyy.

12. Jahrestagung der DMV

Hamburg, 21.09.2015 – 25.09.2015

www.math.uni-hamburg.de/DMV2015

The 2015 annual meeting of the Deutschen Mathematiker-Vereinigung (DMV) will be hosted by the Department ofMathematics of the University of Hamburg. The organiserscollaborate with the Dansk Matematisk Forening during thecomposition of the scientific programme; Danish-Germanresearch collaboration in mathematics is one of the specialthemes of this meeting.

38

Fachgruppenleitung Computeralgebra 2014-2017

Sprecher:Prof. Dr. Florian HeßCarl-von Ossietzky Universität OldenburgInstitut für Mathematik, 26111 Oldenburg0441-798-2906, -3004 (Fax)florian.hess@uni-oldenburg.dehttp://www.staff.uni-oldenburg.de/florian.hess

Stellvertretender Sprecher:Prof. Dr. Gregor KemperZentrum Mathematik – M11Technische Universität MünchenBoltzmannstr. 3, 85748 Garching089-289-17454, -17457 (Fax)kemper@ma.tum.dehttp://www-m11.ma.tum.de/~kemper

Fachexperte Redaktion Rundbrief:Prof. Dr. Michael CuntzInstitut für Algebra, Zahlentheorie und Diskrete Math.Leibniz Universität HannoverWelfengarten 1, 30167 Hannover0511-762-4252cuntz@math.uni-hannover.dehttp://www.iazd.uni-hannover.de/~cuntz

Fachreferentin Themen und Anwendungen:Prof. Dr. Bettina EickInstitut Computational MathematicsFachbereich Mathematik und InformatikTechnische Universität BraunschweigBraunschweig0531-391-7525, -7414 (Fax)beick@tu-bs.dehttp://www.icm.tu-bs.de/~beick/

Fachreferent CA-Systeme und -Bibliotheken:Prof. Dr. Claus FiekerFachbereich MathematikTechnische Universität KaiserslauternGottlieb-Daimler-Straße, 67663 Kaiserslautern0631-205-2392, -4427 (Fax)fieker@mathematik.uni-kl.dehttp://www.mathematik.uni-kl.de/~fieker

Fachreferentin Publikationen und Promotionen:Prof. Dr. Anne Frühbis-KrügerInstitut für Algebraische GeometrieWelfengarten 1, 30167 Hannover0511-762-3592fruehbis-krueger@math.uni-hannover.dehttp://www.iag.uni-hannover.de/~anne

Fachexperte Physik:Dr. Thomas HahnMax-Planck-Institut für PhysikFöhringer Ring 6, 80805 München089-32354-300, -304 (Fax)hahn@feynarts.dehttp://wwwth.mppmu.mpg.de/members/hahn

Fachreferentin Computational Engineering,Vertreterin der GAMM:Dr.-Ing. Sandra KlingeLehrstuhl für Mechanik - MaterialtheorieRuhr-Universität BochumUniversitätsstr. 150, 44780 Bochum0234-32-26552, -14154 (Fax)sandra.klinge@rub.dewww.am.bi.ruhr-uni-bochum.de/Mitarbeiter/Ilic

Fachreferent Schwerpunktprogramm 1489:Prof. Dr. Jürgen KlünersMathematisches Institut der Universität PaderbornWarburger Str. 100, 33098 Paderborn05251-60-2646, -3516 (Fax)klueners@math.uni-paderborn.dehttp://www2.math.uni-paderborn.de/people/

juergen-klueners.html

Vertreter der DMV:Prof. Dr. Wolfram KoepfInstitut für MathematikUniversität KasselHeinrich-Plett-Str. 40, 34132 Kassel0561-804-4207, -4646 (Fax)koepf@mathematik.uni-kassel.dehttp://www.mathematik.uni-kassel.de/~koepf

Fachreferent Themen und Anwendungen:Prof. Dr. Martin KreuzerFakultät für Informatik und MathematikUniversität PassauInnstr. 33, 94030 Passau0851-509-3120, -3122 (Fax)martin.kreuzer@uni-passau.dehttp://www.fim.uni-passau.de/~kreuzer

Vertreter der GI:Prof. Dr. Ernst W. MayrLehrstuhl für Effiziente AlgorithmenFakultät für InformatikTechnische Universität MünchenBoltzmannstraße 3, 85748 Garching089-289-17706, -17707 (Fax)mayr@in.tum.dehttp://www.in.tum.de/~mayr/

Fachreferent Schule und Didaktik:OStR Jan Hendrik MüllerRivius-Gymnasium der Stadt AttendornWestwall 48, 57439 Attendorn02722-5953 (Sekretariat)jan.mueller@math.uni-dortmund.dewww.mathebeimueller.de

Fachreferentin CA an der Hochschule:Prof. Dr. Eva ZerzLehrstuhl D für MathematikRWTH AachenPontdriesch 14/16, 52062 Aachen0241-80-94544, -92108 (Fax)eva.zerz@math.rwth-aachen.dehttp://www.math.rwth-aachen.de/~Eva.Zerz/