Summary of the impact

The School of Mathematics and Statistics at St Andrews is leading the development and implementation of new efficient algorithms for the GAP (Groups, Algorithms and Programming) free, open-source system for computational discrete algebra. Although it is primarily a research tool, GAP is widely used in education. Therefore lecturers, as well as students in class and beyond, benefit from a whole new range of educational possibilities, for example being able to investigate considerably larger abstract mathematical structures than hitherto. This new, hands-on approach is radically changing the way mathematics is taught in universities worldwide, and is deepening the learning and understanding. The pioneering work of St Andrews researchers has shaped GAP at all levels for 20 years, from discovering and incorporating state-of-the-art algorithms, to its unique design, which is an educational feature in its own right.

Underpinning research

GAP (Groups, Algorithms and Programming) is a worldwide collaborative effort in open source software. Over the decades it has grown into a large computer algebra system comprising over 0.6 million lines of code plus another 1.1 million in over 100 contributed packages. Its core functionality lies in computational group and semigroup theory. Since 1997 The University of St Andrews has been a leading centre of GAP development, currently one of four world-wide, and the only one in the UK. We host the source code repository for core system and some packages, mailing lists and archives, centralized testing services, issue tracker, release management, as well as the GAP website. In the following, we highlight a few characteristic examples of the many contributions to GAP by researchers in St Andrews.

Prof. Steve Linton (from 1994), Dr James Mitchell (from 2004), Prof. Edmund Robertson (retired 2008) and Prof. Nik Ruskuc (from 1995) have played pivotal roles in the invention of computational methods for semigroups (see for example [1, 2, 3]). This research activity has been ongoing at the University of St Andrews since 1997 and has led to efficient implementations in the GAP library as well as in GAP packages (e.g. Monoid and Citrus published in 2012 by Mitchell). Achieving this aim involved mathematical research of various flavours, including setting up underlying theory, the invention and analysis of algorithms and extending to the development of high quality and well-tested implementations with good documentation. Today, every time a user asks GAP a question about a semigroup, these algorithms run in the background, and it is only due to the ongoing efforts of researchers at St Andrews that one can work with semigroups in GAP at all.

Computing minimal polynomials is a fundamental problem for matrices. In 2008, Prof.Cheryl Praeger (University of Western Australia) and Dr Max Neunhöffer (University of St Andrews, from 2007) developed [4] and implemented (in the cvec GAP package by Neunhöffer) a new efficient algorithm for this over finite fields. For example, whenever GAP is asked to compute the order of a matrix, this algorithm is used. Such order computations play an important role for applications in coding theory, cryptography and group theory, which are standard subjects of university teaching.

Algorithms for matrix groups over finite fields have been a major research area for the past 20 years. Efficient implementations of algorithms to recognise such groups constructively have only been published in the past few years (e.g. the recog GAP package by Neunhöffer and Seress (Ohio State, Columbus, USA) was first published in 2009). Dr Max Neunhöffer and Dr Colva Roney-Dougal (from 2002) with J. Carlson (Georgia, Athens, USA), developed an important algorithm for matrix groups which fits into the framework of the recog package [5]. This is now used every time a GAP user works with a matrix group. Most of the work for this was done by members of staff at the University of St Andrews.

Since 2009, the EPSRC-funded HPCGAP project has been developing the GAP system into a parallel programming platform for discrete mathematics [6]. The GAP development within this project is done entirely by University of St Andrews staff (Dr Reimer Behrends (from 2009), Dr Vladimir Janjic (from 2010), Dr Alexander Konovalov (from 2007), Prof. Steve Linton and Dr Max Neunhöffer). Public alpha releases were published in 2011, 2012 and August 2013. This new parallel version maintains GAP's status as a state-of-the-art system and adapts it to modern hardware. Its advent enables lecturers to introduce students to the paradigm of parallel programming in discrete mathematics.

References to the research

All mentioned publications have appeared in major mathematical peer reviewed journals or top international computer science conferences, and the research conducted at the University of St Andrews is clearly world-leading in terms of originality, significance and rigour.

The articles [1, 4, 5] indicate the quality of the underpinning research best. Their acceptance in major mathematical journals indicates theoretical depth whilst they at the same time led to an important improvement of the algorithms in GAP and practical computations.

Details of the impact

GAP is used in universities all over the world to teach courses in mathematics. From user feedback and continued, increasingly versatile use, we know that this is resulting in better teaching, more thorough understanding of the mathematics taught, and to improved learning opportunities for students. It helps students acquire key additional skills applicable to a broad range of chosen career paths. The reach and significance are considerable and below we elaborate on this widespread positive impact on the education of students.

GAP is used widely in teaching mathematics. In February 2012, we surveyed the GAP community via the GAP-Forum (a mailing list with 1055 members), about the use of GAP in teaching. From the replies from all over the world (including major universities in Europe, US, South America, Asia and Australia {2}); the results are summarised in our exposition below. Here is a typical statement {2} from a colleague in the academic community (in Montgomery, Alabama, USA):

"GAP has played such a large part in my research and my understanding of group theory. I am forever in debt to its many authors. I take every opportunity to share it with my students."

A professor at Colorado State University at Fort Collins in the USA writes {1}:

"I have been using GAP for many years in my undergraduate and graduate classes in algebra and combinatorics [...]. I have found the system an indispensible tool for illustrating phenomena that are beyond simple pencil-and-paper methods [...]. It also has been most useful as a laboratory environment for students to investigate algebraic structures [...]. [T]his first-hand investigation gives students a much better understanding of what these algebraic structures are, and how their elements behave, than they would get by the traditional examples presented in a board-lecture situation. This more concrete approach to abstract algebra has been received well by students, in particular by students whose major (or study aim) has not been graduate school in mathematics.''

Our user respondents mention at least 10 different mathematical areas in which they use GAP for teaching, in courses at all levels from second year up to PhD and beyond. For example, in the University of Porto, GAP has been used to teach number theory, computational algebra and cryptography to around 140 students per year since 2009 {2}. Furthermore, there are summer schools for graduate students and PDRs in which GAP was used for the practical exercises ({3}, {4}). For example, the summer school "Groups Actions Computations 2010" at the Harish-Chandra Research Institute in Allahabad (India) used GAP for the practical tutorials on computer algebra. In summary, we know from our survey that worldwide hundreds of students every year take part in university courses that use GAP. Some of these activities have been going on for many years (for example in Aachen for 15 years), while many only started in or after 2008, and the numbers have grown year on year. The real numbers are likely to be considerably higher than what our quick survey suggests, and certainly run into many thousands if uses through Sage are counted (see below).

GAP complements the traditional methods of teaching in many different ways. Some use it to pose computer exercises to their students, either to look at mathematical examples inaccessible to conventional methods, or to introduce mathematical programming (e.g. in Fort Collins, {5}). Others (e.g. Aachen, Braunschweig, Perth) use GAP to give the students access to large data collections, e.g. the library of finite groups. In many courses the lecturer uses GAP to show non-trivial computations in class. There are mathematical teaching publications relying on GAP (e.g. "Adventures in Group Theory: Rubik's Cube, Merlin's Machine and Other Mathematical Toys" by Joyner (2008), "Contemporary Abstract Algebra" by Gallian (2010) and "Representations of Groups: A Computational Approach" by Lux and Pahlings (2010)), and GAP is integrated into the Sage system, which itself is used extensively in teaching {6}. Sage is a system which endeavours to incorporate as much free mathematical software as possible to create a general purpose tool for mathematicians. This means that students are exposed to GAP throughout their entire higher education.

We now proceed to describe different ways in which using GAP is improving and broadening students' education.

Using computers in class or for homework vastly increases the size of mathematical structures one is able to analyse. Interesting phenomena often occur only in examples that are beyond hand calculations, which means that, through the use of GAP, students can gain mathematical insights to which they did not have any access hitherto. For example in group theory, with pen and paper one can only practically compute with groups containing some dozens of elements, whereas with the right software handling groups with > 10⁹ elements is easy and convenient. Even if the size of the examples is not too large, the GAP system with its huge data-bases of interesting mathematical structures provides a plethora of examples from which a lecturer can simply select, or indeed quickly run through them automatically. Examples of such collections are: the library of small groups up to the order 2000 (SmallGroups package, published in 2002 by O'Brien (Auckland), Eick (Braunschweig) and Besche (Braunschweig)), the library of all semigroups with up to 10 elements (Smallsemi package, published in 2012 by Distler (PhD student at St Andrews at the publication time) and Mitchell) or the library of primitive groups up to degree 2500 (published in 2005 by Roney-Dougal with the GAP distribution).

This ready access to mathematical structures opens up the possibility of a more 'experimental' approach in abstract mathematics. Students can even conduct such experiments themselves, in a lab or at home -- all that is needed is a PC with a free GAP installation. This in turn leads to a more grounded familiarity with the contents, and, more importantly the students develop a different, more independent, attitude towards mathematics. By degrees they learn to come up with their own conjectures, to verify or disprove them; in a word, they begin "doing" mathematics, rather than simply "absorbing" it, which prepares them for independent creative thinking, problem solving and a career in research or industry.

In the course of this activity, students will be led naturally towards an efficient usage of computers and the need to write simple programs. This is clearly a valuable transferable skills in its own right, and can be developed into ability to write correct and efficient programs, and even mathematically prove their correctness.

Finally, computational methods in (discrete) mathematics can itself be a subject of study. The open source nature of GAP allows lecturers and students to examine GAP and its algorithms. In particular, students can develop new methods on their own, thereby expanding GAP and contributing to its capabilities. Further down the line, PhD students can become members of the development team, build their own packages, and base publications on these. This is not only good for their education in computational mathematics, but they benefit in a much broader way from gaining expertise in professional software development.

In summary, the use of GAP in mathematical teaching improves the education of thousands of students worldwide every year, making them the main beneficiaries. The lecturers themselves also benefit, because the deployment of new teaching methods can enrich their views on both their subject area and education. In particular they can lead their students towards creative mathematical thinking and problem solving. The society benefits from a stream of well qualified professionals who bring together mathematical knowledge, numerical- and analytic-problem solving skills, and broad computational expertise.

The impact is significant since these skill-sets are crucial for functioning of our society, and is far-reaching because GAP is freely available and GAP-based instruction takes place in dozens of leading universities worldwide.

St Andrews research work is crucial for GAP in all its aspects, and in particular for its educational applications. Each of the thousands of GAP installations worldwide incorporates years of research effort by St Andrews scientists.

Sources to corroborate the impact

{1} Statement from a professor at the Colorado State University at Fort Collins in the USA.

{2} Feedback from our survey on the GAP-Forum: 28 emails by colleagues from all over the world, available in a repository at St Andrews for auditing purposes.

{3}Summer school "Groups Actions Computations 2010" in Allahabad, India.
http://www.icts.res.in/program/details/177/. This supports the claim that GAP has been used in summer schools.

{4} Summer school on computational group theory in Kirchberg/Hunsrück. http://www.math.rwth-aachen.de/~Graduiertenkolleg/schools/2011/. This supports the claim that GAP has been used in summer schools.

{5} Alexander Hulpke with contributions by Kenneth Monks and Ellen Ziliak: "Abstract Algebra in GAP", 2008--2011. http://www.math.colostate.edu/~hulpke/CGT/howtogap.pdf
This shows that GAP has been used for teaching.

{6} The Sage Development Team: http://wiki.sagemath.org/Teaching_with_SAGE This page underpins the claim that GAP has been used in teaching through SAGE.