Magma at ISSAC (Montreal, 13-14 July 1995)
--------------
MAGMA AT ISSAC
--------------
CONFERENCE AND WORKSHOP PROGRAM
The Computational Algebra Group at the University of Sydney
and Centre Interuniversitaire en Calcul Mathematique Algebrique
(CICMA) of Quebec are pleased to announce that a two-day
conference will be held on July 13 and 14, immediately following
the 1995 ISSAC meeting at Concordia University, Montreal on the
application of Magma and associated packages (Cayley, KANT, PARI)
to problem solving in advanced areas of mathematics and computer
science.
------------------------------------------------------------------
WEDNESDAY, July 12, 1995
---Magma Workshop I---
This workshop is designed for newcomers to Magma, including those
familiar with Magma's precursor Cayley. After the workshop, the
participants should have sufficient confidence to experiment
with the system themselves, and will have sufficient Magma back-
ground for the conference.
18.30 Catherine Playoust: Surfing the Lava Flow
19.10 Catherine Playoust: Language Features in Magma
19.50 John Cannon: Groups and their Actions
20.30 Close
--------------------------------------------------------------------
THURSDAY, July 13, 1995
---General Talks I---
9.00 An Introduction to Structural Computation in Algebra
John Cannon, University of Sydney
9.55 Coffee
10.25 Codes from Designs and Finite Geometries
Jenny Key, Clemson University
11.20 Examples and Explorations in Finite Groups
Mike Slattery, Marquette University
12.15 Lunch
---Applications I: Group Theory---
13.30 Computational Approaches to Finitely Presented Groups
George Havas, University of Queensland
14.30 TBA
Kazuhiro Yokoyama, RISC Linz and Fujitsu Laboratories
15.00 Problems from the participants
15.30 Coffee
---Applications II: Mathematics Education---
16.00 Using Magma in an Abstract Algebra Course
Catherine Playoust, University of Sydney
16.45 Various Research Applications for Cayley
Nigel Boston, University of Illinois
17.15 Discussion
17.30 Close of session
-----------------------------------------------------------------
---Magma Workshop II---
This workshop is designed for those with some Magma experience,
including those who attended the Wednesday night tutorial.
18.00 Wieb Bosma: Finite Fields
18.40 Catherine Playoust: Power Series and the Real and Complex
Fields
19.20 John Cannon: Linear Algebra and Module Theory
20.00 Close
--------------------------------------------------------------------
FRIDAY, July 14, 1995
---General Talks II---
9.00 Rings, Fields and their Relationships in Magma
Wieb Bosma, University of Sydney
9.55 Coffee
10.25 Number Fields in KANT
Michael Pohst, Technische Universitaet, Berlin
11.20 Groups in Combinatorial Searching
Greg Butler, Concordia University
12.15 Lunch
---Applications III: Number Theory---
13.30 Totally Real Sym(5) Sextic Fields with Minimal Discriminant
David Ford, Concordia University
14.00 The Hilbert Class Field: An Explicit Example
Mario Daberkow, Technische Universitaet, Berlin
14.30 Problems from the participants
15.00 Coffee
---Applications IV: General---
15.30 Using Representation Theory to Optimize Linear Transforms for
VLSI Implementations
Torsten Minkwitz, Universitaet Karlsruhe
16.00 Calculation of Torsion Groups of Elliptic Curves over Q
Darrin Doud, University of Illinois
16.30 Problems from the participants
17.00 Close
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
CONFERENCE ABSTRACTS
Wieb Bosma: Rings, Fields and their Relationships in Magma
One of the distinguishing characteristics of Magma is its em-
phasis on computation with structures and maps between them. I
will illustrate this by showing how, in a very natural `mathemat-
ical' manner, many of the rings and fields that are of computa-
tional interest can be created and manipulated. I will outline
why and how Magma stores relationships between related rings, how
our view of algebraic structures allows the user to specify
homomorphisms between structures, and the importance of `multiple
views' of one object.
-----------------------------------------------------------------
Greg Butler: Groups in Combinatorial Searching
We will consider the role of groups in two contexts:
a) Regular subgroups of 2^{2n} Sp(2n,2) and Tonchev's constr-
uction of block designs from difference sets
b) Conjugacy classes of the automorphism group of the football
pool graph, and orbit graphs.
-----------------------------------------------------------------
Nigel Boston: Various Research Applications for Cayley
In the fall of 1991, I taught a course on computational group
theory at the University of Illinois. The course consisted of the
students and myself exploring solved and unsolved problems (pick-
ing up tools from Cayley and group theory as we went). We
answered one of the unsolved problems, leading to a joint paper.
In this talk I shall discuss the means by which Cayley helped us
make this breakthrough and then (as time permits) describe how we
have since then, separately and jointly, applied Cayley to a
variety of research problems in group theory and algebraic number
theory.
-----------------------------------------------------------------
John Cannon: An Introduction to Structural Computation in Algebra
Structural computation presents a number of unique challenges
to the designer of a Computer Algebra system. The issues include,
how is a structure specified, how do we test membership of ele-
ments, can we find a canonical form for the structure, etc.
Developments in the field of algebraic algorithms have given us
the theoretical means of answering such questions in the case of
quite a number of different families of algebraic structures.
This talk will outline some of the central issues in computation
involving structures and illustrate how the Magma language pro-
vides the user with a calculus for working with structures.
-----------------------------------------------------------------
Darrin Doud: Calculation of Torsion Groups of Elliptic Curves
over Q
The method used by most Computer Algebra Systems to calculate the
torsion subgroup of an elliptic curve over the rational numbers
is, in many cases, extremely slow. An alternative algorithm is
described, which is often much faster. This algorithm has been
implemented in the GP-PARI system, and we will compare its per-
formance with the performance of the algorithm included in GP-
PARI.
-----------------------------------------------------------------
David Ford, Michael Pohst, Istvan Gaal and Mario Daberkow:
Totally Real Sym(5) Sextic Fields with Minimal Discriminant
The enumeration of primitive algebraic number fields of degree 6
and higher is quite time-consuming --- ``probably out of our com-
putational capabilities,'' to quote Martinet. For degree 6, ex-
amples of minimal-discriminant fields are known for all possible
signatures for all alternating Galois groups. The most costly
case, Alt(6), was confirmed by a three-CPU-week search. It is
clear that sextic fields with group PGL(2,5) (in its degree 5
representation) are a more difficult proposition. Many more po-
lynomials must be examined, and the key screening criterion for
alternating fields --- square discriminant --- is not available.
Instead, mod p factorizations must be computed, to exclude exam-
ples with impossible cycle types. It is critical that this pro-
cess be administered efficiently, and this we will discuss in de-
tail. The search for the totally real Sym(5) sextic field(s) of
minimum discriminant is expected to conclude in the summer of
1995, after approximately 1.75 CPU-years of computation on a net-
work of thirty processors at the Technische Universitaet Berlin.
-----------------------------------------------------------------
George Havas: Computational Approaches to Finitely Presented Groups
Methods used to compute with fp-groups may be conveniently
described under three headings: Todd-Coxeter or coset enumeration
based methods; Knuth-Bendix or term-rewriting methods; and quo-
tient group methods. I will report on improved strategies for
coset enumeration and I will discuss new algorithms for computing
the structure of finitely presented abelian groups. In both of
these cases substantial advances have been made recently, ad-
vances which are incorporated into algorithms and procedures
available in Magma. I will present examples of research problems
that can be solved using using Magma.
----------------------------------------------------------------
Jenny Key: Codes from Designs and Finite Geometries
The talk will include some applications to hermitian unitals,
oval designs, Hadamard designs, and designs from finite geometr-
ies.
-----------------------------------------------------------------
Torsten Minkwitz: Using Representation Theory to Optimize Linear
Transforms for VLSI Implementations
Most linear transforms used in digital signal processing are
defined over the real or complex numbers. For implementations,
calculations are done by floating point arithmetic. While that is
sufficient for traditional sequential machines or a digital sig-
nal processor, it is unfeasible for VLSI implementations. Here
one would like to do fixpoint arithmetic to save chip space. To
find a good way to do this, representation theory of finite
groups can often be utilized. Several of the most used transforms
have been shown to decompose a permutation representation of some
finite group G into their irreducible subrepresentations. There-
fore, one can perform most of the calculations in the splitting
field of G. This is a finite extension of the rationals. There-
fore fixpoint arithmetic can be used.
-----------------------------------------------------------------
John Cannon and Catherine Playoust: Using Magma in an Abstract
Algebra Course
Many students in Pure Mathematics have difficulty in approaching
Abstract Algebra. They find the concepts difficult, and they
lack sophistication in proofs. Faster progress can be made if
they are able to learn empirically, by constructing and manipu-
lating examples of the algebraic structures under consideration.
A computer algebra system such as Magma provides the best facili-
ty for working with examples of non-trivial size and complexity.
The talk will report on recent work by John Cannon and Catherine
Playoust in developing Magma tutorial material for a Pass-level
Rings and Fields course.
-----------------------------------------------------------------
Michael Pohst: Computing with relative extensions in KANT
We present new and improved methods for computations with rela-
tive extensions of algebraic number fields. Major topics include
the calculation of relative normal forms, relative integral
bases, the detection of subfields and embeddings of subfields.
Potential applications like the arithmetical construction of
class fields are also discussed. Special emphasis is put on the
realization of extensions in KANT/MAGMA.
-----------------------------------------------------------------
Mike Slattery: Examples and Explorations in Finite Groups
This talk will present several instances of using Magma to solve
problems and compute examples involving finite groups. We'll
look at matrix groups, permutation groups, and solvable groups
given by power-conjugate presentations.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
WORKSHOP ABSTRACTS
Catherine Playoust: Surfing the Lava Flow
This session will introduce the main techniques for constructing
algebraic structures (magmas) in the Magma System, together with
elements of such structures. Recent additions to Magma will be
given particular attention, and the cross-category similarities
will be emphasized. There will also be an overview of the help
system and documentation.
-----------------------------------------------------------------
Catherine Playoust: Language Features in Magma
Magma has a full programming language, including user-defined
functions and procedures. It also has sophisticated means of con-
structing and manipulating aggregate objects such as sequences
and sets. This tutorial session will explain the use of these
more advanced language features. Many of the illustrations will
be drawn from combinatorics and number theory.
-----------------------------------------------------------------
John Cannon: Groups and their Actions
Magma contains an extensive range of facilities for computing with
groups. Further, it contains a number of features that support
computation with group actions. Group theoretic computation in
Magma will be introduced by examining the construction of permut-
ation groups and their actions.
-----------------------------------------------------------------
Wieb Bosma: Finite Fields
Finite fields play an important role in many algorithms in compu-
tational algebra. This talk will contain a survey of the finite
field facilities in Magma, some applications, and a description
of various internal representations. Moreover, it will outline
how Magma deals with `relations' between algebraic structures.
The talk will also briefly touch upon other rings, such as the
integers, residue class rings and polynomial rings.
-----------------------------------------------------------------
Catherine Playoust: Power Series and the Real and Complex Fields
The new PARI system modules in Magma include those for the real
and complex fields, power series and Laurent series rings, and
p-adic fields. In each of these, it is inherently necessary to
approximate the elements. This talk will outline how the notion
of precision enters into the model of these rings in Magma.
Several of the examples will illustrate Magma's new wealth of
analytical functions.
-----------------------------------------------------------------
John Cannon: Linear Algebra and Module Theory
This session will outline some of Magma's facilities for module
theory. They will then be demonstrated in the context of linear
error-correcting codes. The session will conclude with examples
involving directed and undirected graphs.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
CONFERENCE ANNOUNCEMENT AND CALL FOR CONTRIBUTIONS
--------------
MAGMA at ISSAC
--------------
Applications of Computer Algebra to Advanced Algebra
Number Theory and Geometry
July 13 and 14, 1995
The Computational Algebra Group at the University of Sydney
and Centre Interuniversitaire en Calcul Mathematique Algebrique
(CICMA) of Quebec are pleased to announce that a two-day
conference will be held on July 13 and 14, immediately following
the 1995 ISSAC meeting at Concordia University, Montreal on the
application of Magma and associated packages (Cayley, KANT, PARI)
to problem solving in advanced areas of mathematics and computer
science. The areas of interest include, but are not restricted
to, coding theory, cohomology, combinatorial searching, design
theory, discrete signal processing, finite geometry, group
theory, knot theory, module theory, number theory, representation
theory, ring theory, and (algebraic) topology. No prior knowledge
of any particular package will be assumed.
BACKGROUND
Magma is a new Computer Algebra system designed around the
algebraic notions of structure and morphism. The objects
definable in the system correspond to standard mathematical
objects with a semantics that obeys normal mathematical
conventions. The syntax of the language follows standard
mathematical notation within the constraints imposed by keyboard
design. Because the Magma language is directly based on algebraic
concepts, algebraic algorithms map into the language with minimal
programming effort.
Magma is designed to support computation in algebra, number
theory, geometry and algebraic combinatorics. This aim is
achieved through the provision of extensive machinery for groups,
rings, modules, algebras, geometric structures and finite
incidence structures (designs, codes, graphs). The library of
intrinsic functions includes versions of a number of packages
written by specialists in various branches of algebra and number
theory. Noteworthy among these are the number field package KANT
V4 (developed by Michael Pohst and associates in Berlin), and the
general number theory package PARI (developed by Henri Cohen and
associates in Bordeaux).
Magma has been developed by the Computational Algebra Group at
the University of Sydney and the first version was shipped at the
end of 1993. Since then, the scope and functionality of the
system have been greatly expanded.
CONFERENCE THEMES
The meeting is intended to examine the prospects opened up by
the availability of algorithms and software capable of
investigating advanced problems in abstract algebra, number
theory and geometry. Specifically, the conference will provide:
o An overview of recent algorithm and language development in
Magma and associated systems.
o Case studies of problems investigated using Magma and
associated systems.
o The prospects for experimental investigations opened up by
recent developments in algorithms and systems.
o The identification of areas where further development of
computational facilities would be immediately beneficial.
o The use of advanced Computer Algebra systems in
undergraduate and graduate teaching.
BIRDS-OF-A-FEATHER SESSIONS
The afternoons will be organized around "birds-of-a-feather"
sessions devoted to specific areas. Participants will be
encouraged to present both case studies and new problems in these
sessions. The following themes have been suggested:
o Number theory
o Ring theory and module theory
o Group theory
o Group representations
o Designs, codes and finite geometries
o Algebraic combinatorics
o Computer algebra in the classroom
Suggestions for additional B-O-F themes are sought from intending
participants.
MAGMA TUTORIAL
A hands-on introduction to the system will be given over the
two evenings of Wednesday, July 12 and Thursday July 13. The
tutorial will be led by Catherine Playoust, author of "An
Introduction to Magma".
DEMONSTRATION VERSION OF MAGMA
Registered conference participants will be able to obtain a
demonstration version of Magma, subject to its availability on
the participant's choice of platform.
-----------------------------------------------------------------------
REGISTRATION FORM
Please complete this form and return it by email to gregb@cs.concordia.ca
by July 10, 1995.
Family name (Mr, Ms, Dr, Prof):_______________________________________
Given names:__________________________________________________________
Nametag:______________________________________________________________
Postal address:_______________________________________________________
_______________________________________________________
_______________________________________________________
_______________________________________________________
_______________________________________________________
Email address:________________________________________________________
Phone number:_________________________________________________________
Fax number:___________________________________________________________
_
|_| Yes, I do plan to attend the Magma tutorial on Wed and Thurs evenings
My previous experience with the Magma language is_____________________
______________________________________________________________________
_
|_| Yes, I wish to contribute a short paper to a B-O-F session:
Title of B-O-F session:_______________________________________________
Title of paper:_______________________________________________________
______________________________________________________________________
_
|_| Yes, I would like to present a problem for discussion at a BOF session:
Title of B-O-F session:_______________________________________________
Outline of problem:___________________________________________________
______________________________________________________________________
A description of the problem must be received by the organizers on or
before July 10, 1995.
_
|_| Yes, I would like to organize a B-O-F session on the topic:
______________________________________________________________________
Registration fee (CAD 50): $__________
Please note that student registration is free.
Please provide a letter from your department stating that
you are a student.
Arrival date________________Departure date________________
TOTAL payment enclosed: $__________
Please make cheques or bank drafts payable to Concordia University.
Please mail the completed form to:
Greg Butler
Department of Computer Science
Concordia University
Montreal Quebec Canada HG 1M8