The *derived subgroup* G' of a group G is defined as the group *generated* by all *commutators* [a,b] := a^-1b^-1ab, where a,b ∈ G. In general, not all elements of the derived subgroup of a group are actually commutators themselves. Find a group G of smallest possible order such that the set of all commutators of elements of G does not *form* a group!

Commutators can be computed by the operation `Comm`

, and the derived subgroup can be computed by the operation `DerivedSubgroup`

. The function `Cartesian`

and the operations `Set`

and `AsList`

can be helpful in this context as well. If you are lazy but patient, you may simply use `CommutatorLength`

. Otherwise, this exercise requires writing a couple of lines of **GAP** code. The wanted group has order greater than 50, but less than 100.

For a solution, see Section 2.1.

Is there a finite group which has an automorphism which is not inner, but which nevertheless fixes all conjugacy classes setwise? -- If so, then find an example of least possible order!

This exercise is slightly more difficult than that given in Section 1.1. Useful functions and operations are `AllGroups`

, `AutomorphismGroup`

, `IsInnerAutomorphism`

, `IsConjugate`

, `Image`

and `AsList`

. It is a good exercise to try to find a way to write down the group and the automorphism in a nice and human-readable form. One possible way to achieve this is to determine a "nice" permutation representation of the group, and to choose an automorphism with the desired property which fixes all but one of the generators.

For a solution, see Section 2.2.

Write a **GAP** function which draws the Ulam spiral and saves the picture in a file!

The arguments of the function should be the size (width / height) of the picture to be drawn and the name of the output file.

This is more or less just an easy programming exercise, which does not require particular mathematical knowledge. Use the function `NullMat`

to create a zero matrix over the field with two elements, and use this matrix as a grid to draw the spiral. The **RCWA** package [Koh07b] provides a function `SaveAsBitmapPicture`

, which can be used to produce a picture file from the matrix.

For a solution, see Section 2.3.

The automorphisms of a finite projective plane are determined by the permutations of the set of points which move lines to lines. Thus, labelling the points with integers 1, 2, dots, n, the automorphism group can be described as a subgroup of the symmetric group S_n.

The smallest projective plane has 7 points and 7 lines. Any point is incident with 3 lines, and any line is incident with 3 points. We label the points with integers 1, 2, dots, 7. Then the lines are given by the sets g_1 := {1,2,3}, g_2 := {1,4,7}, g_3 := {1,5,6}, g_4 := {2,4,6}, g_5 := {2,5,7}, g_6 := {3,4,5} and g_7 := {3,6,7} of points which are incident with them.

Compute the automorphism group of the smallest projective plane!

A useful function in this context is `SubgroupProperty`

. The actual determination of the group can be done in one statement. Can you figure out the isomorphism type of the group by theoretical means?

For a solution, see Section 2.4.

What happens when you enter the command `Centre(AlternatingGroup(100));`

in **GAP**? Are you satisfied with the performance, given that the centre of a nonabelian simple group is always trivial and that **GAP** knows that the alternating group of degree 100 is simple?

Probably not. -- Thus improve the performance radically by implementing a method for `Centre`

for simple groups, which returns either the group itself or the trivial subgroup, depending on whether the group is abelian or not!

Methods are installed with `InstallMethod`

. The exercise is easy -- basically all you need to do is to look up in the documentation how this function is used. If your solution is correct, then `Centre(AlternatingGroup(100));`

returns the trivial subgroup immediately, and `Centre(`

still computes the centre of a non-simple group `G`)`G` using methods implemented in the **GAP** Library.

For a solution, see Section 2.5.

Given a positive integer n, let rad(n) denote the product of distinct prime divisors of n. The abc conjecture states that for any ϵ > 0 there is a constant K_ϵ such that for any triple (a,b,c) of coprime positive integers satisfying the equation a + b = c we have c < K_ϵ rad(abc)^1 + ϵ.

A triple (a,b,c) of coprime integers satisfying a + b = c is called an *abc triple* if rad(abc) is less than c. An abc triple (a,b,c) is called a *good* abc triple if it satisfies even ln(c)/ln( rad(abc)) > 1.4. The left-hand side of the inequality is sometimes called the *ratio* of the abc triple.

It can be shown easily that there are infinitely many abc triples, but if the abc conjecture holds, there are only finitely many good abc triples.

Write a **GAP** function which finds all good abc triples (a,b,c) with given radical rad(abc) and with c less than a given bound!

Can you find a new triple, which is not yet on Abderrahmane Nitaj's list of known good abc triples?

You can start by determining all positive integers less than the given bound all of whose prime factors divide the given radical. This can be done much more efficiently than by the Sieve of Eratosthenes, or even by looping over all integers in the range and factoring -- it is easy and very elementary to find out how. Then you can loop over all pairs of these integers, test whether they are coprime and compute the ratio if they are. To compute the ratio, you need the operation `Float`

which converts integers and rationals to floating point numbers, and the function `LOG_FLOAT`

which computes the natural logarithm of a floating point number.

For a solution, see Section 2.6.

**a)**Determine all undirected graphs with 6 vertices up to isomorphism! -- How many isomorphism types of such graphs are there?

The graphs should be represented as sets of edges, where the edges should be written as sets of two vertices, each.

Example: In this representation, the graphs

`[[1,2],[1,6],[2,3],[3,4],[4,5],[5,6]]`

and`[[1,5],[1,6],[2,4],[2,6],[3,4],[3,5]]`

are both isomorphic to the regular hexagon.**b)**Write a function

`GraphAutomorphismGroup(`

which computes the automorphism group of the graph`Gamma`,`n`)`Gamma`with`n`vertices. -- The automorphisms are precisely the permutations of the set of vertices which move edges to edges.Note that the cardinality

`n`of the set of vertices needs to be specified, as there may be isolated vertices.**c)**Find out which of the (up to conjugation in S_6) 16 transitive permutation groups of degree 6 occur as automorphism groups of graphs with 6 vertices! -- How do the corresponding graphs look like?

**ad a)**You can obtain the set of all graphs with n vertices in the suggested notation by

`Combinations(Combinations([1..n],2));`

. Then you need to find a suitable group action on this set such that two graphs are isomorphic if and only if they lie in the same orbit. Useful operations are`Orbits`

and`Representative`

.**ad b)**In principle you can implement a fancy algorithm here, but for our purposes a very basic one is perfectly sufficient. First find out how to check whether a given permutation of the vertices induces a graph automorphism. Then you can use

`SubgroupProperty`

to determine the group formed by all such permutations.**ad c)**Given Part a) and b), this is more or less straightforward. Useful functions / operations are

`AllTransitiveGroups`

,`NrMovedPoints`

and`TransitiveIdentification`

.

For a solution, see Section 2.7.

Answer the following questions using **GAP**:

**a)**In how many ways can 1 ∈ S_4 be written as a product of exactly 100 transpositions?

**b)**In how many ways can a horse cross the chess board from the upper left to the lower right corner with exactly 100 moves?

Construct a matrix x ∈ Z^n × n with ones at suitable positions and zeros everywhere else and compute powers. For Part a), choose n := 24, and for Part b), choose n := 8^2 = 64. Useful functions are e.g. `NullMat`

, `SymmetricGroup`

, `Combinations`

, `Cartesian`

and `Position`

.

For a solution, see Section 2.8.

By Fermat's little theorem, for any prime number p we have p|2^p-1-1. A prime number p is called a Wieferich prime if it satisfies even p^2|2^p-1-1.

Write a **GAP** function which checks whether a given positive integer is a Wieferich prime, and try to find as many Wieferich primes as you can!

Writing the **GAP** function is easy. Use `PowerModInt`

instead of first computing 2^p-1 and then reducing modulo p^2. Two Wieferich primes can be found easily, but finding a third one is at least hard.

For a solution, see Section 2.9.

Write a **GAP** function which, given a filename, returns a word distribution statistics. The function should return a list with entries of the form `[ "word", 237 ]`

for any word in the file, indicating the word and the number of times it occurs. A "word" in our sense is a sequence of letters with no non-letter characters in between, i.e. it does not need to be a dictionary word. Can you put your function into one line with no more than 80 characters?

You will probably need the operation `Collected`

. Further, the functions `StringFile`

and `WordsString`

from the **GAPDoc** package [LN06] will be useful.

For a solution, see Section 2.10.

A group G is called *metabelian* if it has an abelian normal subgroup N such that the quotient G/N is abelian as well. Further, a group is called a *p-group* if its order is a power of a prime.

Find a non-metabelian p-group of least possible order!

First determine conceivable orders of non-metabelian groups by means of theory. Then just run a *brute-force* search over the groups of the smallest few of these orders in the Small Groups Library [BEO07]. Useful functions / operations are `AllGroups`

, `DerivedSubgroup`

and `IsAbelian`

. For a solution, see Section 2.11.

Let σ denote the sum-of-divisors function. Given a positive integer n, let H(n) := ∑_k=1^n 1/k be the nth harmonic number, and put B(n) := H(n) + ln(H(n)) ⋅ e^H(n).

Examples are σ(24) = 60 and B(24) ≈ 61.7575, as well as σ(60) = 168 and B(60) ≈ 170.977.

Can you find an integer n > 1 such that σ(n) is larger than B(n)?

In **GAP**, σ(n) can be computed by `Sigma(`

. Use the operation `n`)`Float`

to convert integers and rationals to floating point numbers, and use the functions `LOG_FLOAT`

and `EXP_FLOAT`

to compute logarithms and to evaluate the exponential function, respectively. Be prepared that finding an integer n > 1 such that σ(n) is larger than B(n) is not easy.

For a solution, see Section 2.12.

Pell's equation is any Diophantine equation of the form x^2 - ny^2 = 1, where n is a nonsquare integer.

Write a **GAP** function which takes an argument n and returns the smallest solution of the equation x^2 - ny^2 = 1 in positive integers!

This solution is called the *fundamental solution*. Your function should return for example the answer for n = 421 very quickly.

Useful functions in this context are `ContinuedFractionExpansionOfRoot`

and `ContinuedFractionApproximationOfRoot`

.

For a solution, see Section 2.13.

Obviously, the automorphism groups of both the trivial group and the cyclic group of order 2 are trivial, and have therefore odd order. Find the smallest group of order greater than 2 whose automorphism group has odd order!

First try to exclude the groups of even order by means of theory. Then run a *brute-force* search over the Small Groups Library [BEO07]. Useful functions / operations in this context are `AllGroups`

and `AutomorphismGroup`

.

For a solution, see Section 2.14.

Find an odd positive integer n such that n+2^k is composite for any positive integer k! -- Can you find the least possible such n?

First perform a *brute-force* search to find candidates. Then try to verify whether these candidates indeed have the desired property. A useful function in this context is `OrderMod`

. In addition, it may be worth to have a look at the **ResClasses** package [Koh07c], and there in particular at the function `ResidueClass`

. Finding a good candidate for the least possible number with the given property is reasonably easy, but the verification that it is indeed the smallest one is computationally difficult.

For a solution, see Section 2.15.

Write a **GAP** function which computes all rational points on the unit sphere x^2+y^2+z^2=1 which correspond to solutions of the diophantine equation a^2+b^2+c^2=d^2 with a, b and c not exceeding a given bound. Further, your function should draw a picture showing the projection of one octant of the sphere to the x-y-plane, where the rational points are marked by black pixels.

Just write a nested loop to determine the solutions. Note that the variables can be permuted, thus you can assume a ≥ b ≥ c and generate the solutions not satisfying this inequality by permuting a, b and c. This saves almost 5/6 of the time. Maybe a useful function in this context is `Arrangements`

. Create an empty grid over GF(2) by the function `NullMat`

, invert it (i.e. replace zeros by ones) and mark the solutions by zeros there. Finally, the **RCWA** package [Koh07b] provides a function `SaveAsBitmapPicture`

, which can be used to write the picture to a file.

For a solution, see Section 2.16.

Given a positive integer n, the *Aliquot sequence* n = a_1, a_2, a_3, a_4, dots starting at n is defined by a_i+1 = σ(a_i) - a_i, where σ denotes the sum-of-divisors function. We say that the Aliquot sequence starting at n *stops* if there is an index i such that a_i = 1, and we say that it *runs into a cycle* if there are distinct indices i and j such that a_i = a_j.

Find out whether all Aliquot sequences starting at integers n < 100 either stop or run into cycles! -- Can you do the same for all Aliquot sequences starting at integers n < 200 or n < 300? Do you see algorithmic problems, and of which kind are they?

In **GAP**, σ(n) can be computed by `Sigma(`

. Computing σ(n) requires factoring n. For this, the `n`)**GAP** Library method for the operation `Sigma`

calls the **GAP** Library function `FactorsInt`

directly. This works for small n, but for larger n, `FactorsInt`

will often give up and raise an error message which suggests to use the **FactInt** package [Koh07a]. If you have loaded **FactInt**, you may find this strange. However, this has nothing to do with **FactInt**, as this package does not get a chance to help with factoring. You can make `Sigma`

benefit from **FactInt** if you fetch the method for `Sigma`

from `lib/numtheor.gi`

, put it into a separate file, replace `FactorsInt`

by `Factors`

, increase the method rank to something like `SUM_FLAGS`

and read this file into **GAP**. Alternatively you can make the change directly in the **GAP** Library. Then you do not need to increase the method rank, but (as after every Library change) you need to rebuild the completion files. For this, start **GAP** with option -N and enter `CreateCompletionFiles();`

.

For a solution, see Section 2.17.

Hofstadter's Q sequence is defined by Q_1 = Q_2 = 1 and Q_n = Q_n-Q_n-1} + Q_n-Q_n-2} for n > 2.

**a)**Write a

**GAP**function which takes an integer argument l and computes the first l terms of the Q sequence.**b)**Write a

**GAP**function which plots the graph of the Q sequence.

**ad a)**The Q sequence is defined recursively. Ask yourself the question why a recursive implementation is not a particularly good idea in this case, anyway.

**ad b)**Use the function

`NullMat`

to create a zero matrix over the field with two elements, turn the zeros into ones if you prefer a black graph on a white background to a white graph on a black background, and use this matrix as a grid to draw the graph. The**RCWA**package [Koh07b] provides a function`SaveAsBitmapPicture`

, which can be used to produce a picture file from the matrix.

For a solution, see Section 2.18.

Have a look at the following function, which takes as arguments three nonnegative integers and which returns a positive integer:

f := function ( i, j, k ) if i = 0 then if j = 0 then if k = 0 then return 2; else return 2^f(i,j,k-1); fi; else return f(i,j-1,f(i,j-1,k)); fi; else return f(i-1,f(i-1,j,k),f(i-1,j,k)); fi; end;

Try to evaluate `f`

for small values of `i`

, `j`

and `k`

! -- How far can you get? Can you evaluate `f(1,1,1)`

or `f(2,2,2)`

, or can you perhaps write down these values as non-recursive expressions?

The function `f`

is still a computable function -- recall however that there are functions which grow faster than *any* computable function!

Some values this function takes: `f(0,0,0)`

is 2, `f(0,0,1)`

is 4, `f(0,0,2)`

and `f(0,1,0)`

are both 16, `f(0,0,3)`

is 65536, `f(0,0,4)`

and `f(0,1,1)`

are both 2^65536, `f(0,0,5)`

is 2^2^65536}, and already `f(1,1,1)`

is basically too large to be written down in a non-recursive way. The exercise asks just for some experimentation -- thus there is no solution given.

The *3n+1 conjecture*, also known as *Collatz conjecture*, asserts that iterated application of the *Collatz mapping*

to any given positive integer eventually yields 1. This problem has been posed by Lothar Collatz in the 1930's, and it is still open today.

Investigate Collatz' conjecture by means of computation with **GAP**, and try to find a proof or a counterexample!

The 3n+1 conjecture is generally believed to be true, but if it is false, this may be for two reasons: firstly, there may be unbounded sequences, and secondly, there may be sequences which run into cycles not containing 1. Jeffrey C. Lagarias has compiled a comprehensive annotated bibliography [Lag07] on this conjecture. The **GAP** package **RCWA** [Koh07b] provides a large variety of methods to compute with mappings like the Collatz mapping. We show just how to enter the Collatz mapping and how to compute the sequences we are interested in:

gap> T := RcwaMapping([[1,0,2],[3,1,2]]); <rcwa mapping of Z with modulus 2> gap> SetName(T,"T"); gap> Display(T); Rcwa mapping of Z with modulus 2 n mod 2 | n^T ------------------------------------+------------------------------------ 0 | n/2 1 | (3n + 1)/2 gap> Trajectory(T,15,[1]); [ 15, 23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1 ] gap> Trajectory(T,27,[1]); [ 27, 41, 62, 31, 47, 71, 107, 161, 242, 121, 182, 91, 137, 206, 103, 155, 233, 350, 175, 263, 395, 593, 890, 445, 668, 334, 167, 251, 377, 566, 283, 425, 638, 319, 479, 719, 1079, 1619, 2429, 3644, 1822, 911, 1367, 2051, 3077, 4616, 2308, 1154, 577, 866, 433, 650, 325, 488, 244, 122, 61, 92, 46, 23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1 ]

There is (of course!) no solution given for this exercise.

generated by GAPDoc2HTML