Summer School 09/2021 Aims Exercises Participants Preparation Program Registration


Bring your own problem

1. Questions and problems

If you have any questions about or problems with anything related to the workshop, talk to us! Via, Slack, email, telephone, carrier pigeon, …

Do you need help with the Git/Github setup for your project? Would you like do discuss when to use another branch? When do you commit? After every line you changed?

For some problem areas, participants volunteered to help out, so you can also ask them. (Feel free to add your name here).

2. Work on your own Julia/Oscar code

If you are already working on Julia code, possibly even are using Oscar, e.g. for your thesis project, feel free to continue working on that, and just asking us for general help.

Although, if you are already that good at it, surely finishing a few exercises quickly won’t be a problem for you, so why not try? You might still learn something here or there.

Git and GitHub exercises

1. Exercise solutions in git

  1. Fork the repository and clone this to your computer.

  2. In the solutions directory in your local clone, create a subdirectory whose name is your GitHub username, and add solutions to some of the exercises to this directory, commit them, and push them to your fork.

  3. Optionally, if you want, create a pull request to merge the additions into the original repository.

(Note: Forks of public repositories are automatically public. With some effort, you can create a corresponding private repository, or one with restricted access if you want.)

2. git in the browser

  1. Go to the participants list in your web browser

  2. Follow the “Edit this page” link in the navigation sidebar (resp. at the very end of the page, if your browser window is narrow / you are using a mobile browser)

  3. Edit your entry in the participants list by adding your GitHub username (using the syntax already in use for some of the entries)

  4. Submit your change as a pull request.

Julia exercises

You may wish to consult the Julia documentation.

1. Hello

  1. Implement a hello world function hello_world() which prints “hello world”.

  2. Implement a hello function hello(name::String) which prints “hello x”, where x is the first argument.

2. Collatz conjecture

  1. Implement a function f(n::Int) which returns $n/2$ if $n$ is even and $3n + 1$ if $n$ is odd.

  2. Implement a function g(n::Int) which determines the smallest $k$ with $f^k(n) = 1$.

  3. Write a program which finds two numbers $> 100$ for which $g$ returns the same value.

3. Pascal triangle

Implement a function pascal_triangle(n) which prints the first $n$ rows of Pascal’s triangle. For example, pascal_triangle(5) should print

     1 1
    1 2 1
   1 3 3 1
  1 4 6 4 1

At the start, you might consider ignoring the proper layout of the triangle.

4. My permutation

Consider the following type, which defines a permutation:

  struct Permutation

Thus the permutation with images set to [1, 2, 3] is the identity on 3 letters and [2, 1, 3] is the transposition $(1, 2)$ on 3 letters.

  1. Fill in the stub below to write a function for multiplying two permutations. Permutations are applied from the right, so that $(1, 2)(2, 3) = (1, 3, 2)$.

    function *(x::Permutation, y::Permutation)

    Test your function by computing Permutation([2, 1, 3]) * Permutation([1, 3, 2]).

  2. Write a function apply that applies a Permutation to an Int. Make sure that the function has the right signature.

    function apply(p::Permutation, x::Int)

    Test your function:

    p = Permutation([2, 3, 4, 5, 1])
    println(apply(p, 1) == 2)
    println(apply(p, 5) == 1)
  3. Write another apply method that entry-wise applies a permutation to a tuple.

     function apply(p::Permutation, x::Tuple)

    Test your function

     p = Permutation([2, 3, 4, 5, 1])
     println(apply(p, (1, 5)) == (2, 1))
  4. Write an apply! function that modifies a given Vector of the right length by permuting its entries according to x[i] = x[p(i)], and returns it.

     function apply!(p::Permutation, x::Vector)

    Test your function:

     p = Permutation([2, 3, 4, 5, 1])
     x = ["a", "b", "c", "d", "e"]
     println(apply!(p, x))
     println(x == ["b", "c", "d", "e", "a"])
  5. Derive a method apply(p::Permutation, x::Vector) which does the same as apply! without changing the input.

     p = Permutation([2, 3, 4, 5, 1])
     x = ["a", "b", "c", "d", "e"]
     println(apply(p, x) == ["b", "c", "d", "e", "a"])
     println(x == ["a", "b", "c", "d", "e"])

5. Vector vs Tuple

  1. Observe the difference in timings for the following two ways of calculating the millionth Fibonacci number (modulo 2^64).

    F(a::Tuple{Int, Int}) = (a[2], a[1]+a[2])
    F(a::Vector{Int})     = [a[2], a[1]+a[2]]
    function G(a, n)
      for i in 1:n
        a = F(a)
      return a
    @time G((0,1), 10^6)
    @time G([0,1], 10^6)
  2. Write a function H that accepts an input n::Int and returns a Tuple{Bool, Int} where the first return indicates whether n is a square and the second return is the positive square root if it exists or zero otherwise. You should have

    @assert H(0) == (true, 0)
    @assert H(1) == (true, 1)
    @assert H(2) == (false, 0)
    @assert H(3) == (false, 0)
    @assert H(4) == (true, 2)
    @assert H(-1) == (false, 0)

    Try to change H to return a vector and observe what happens to the type of the return.

6. Methods and functions

  1. What arguments does pushfirst! expect?


  2. Without using Oscar, list all functions that accept a Vector argument.


  3. After using Oscar, list all functions that accept an FmpzPolyRing.

  4. List all functions that accept both an fmpz_mat and an fmpz.

  5. Find the source code for the method computing the power fmpz(2)^10.

    @which, @less, @edit

7. Caching

Write a function cached(f) that takes a function/callable object f and returns a new function which returns the same values as f but caches the return value for any input value. Test it with various functions:

  g = cached(+)
  println(g(1, 1) == 1 + 1)

To check the caching, try the following function:

  h = function(s)
    return s

  g = cached(h)
  @time g(1) # this should take 1 second
  @time g(1) # this should take almost no time
  @time g(2) # this should take 1 second

Oscar exercises: Number theory and algebra

Exercises 1-8 provide opportunities to get to know Oscar and its functionality. On the other hand, exercises 9-12 are about implementing functionality on your own using basic functionality provided by Oscar.

You may wish to consult the Oscar documentation.

1. Vandermonde matrices

  1. Create the polynomial ring $R = \mathbf{Q}[x_1,\dotsc,x_5]$.


  2. Create the Vandermonde matrix \(V = (x_i^j)_{1 \leq i \leq 5, 0 \leq j \leq 4} \in R^{5 \times 5}.\)


  3. Compute and factorize the determinant $\det(V)$.

    det, factor

  4. Pick 10 random elements $p \in \mathbf{Q}^5$ and verify that $\det(V)(p) = \det(V(p))$.

    rand (e.g. rand(QQ, -2:2)), evaluate, map_entries.

2. Invariants of number fields

  1. Define the number field $K = \mathbf{Q}(\sqrt[3]{65})$.


  2. Determine the ring of integers $\mathcal{O}_K$ and its discriminant.

    ring_of_integers, discriminant

  3. Determine the class group $\mathrm{Cl}_K$.


  4. Determine the set $S$ of prime ideals of $\mathcal{O}_K$ lying over $2$. Are these ideals ramified?

    prime_decomposition, prime_ideals_over, isramified

  5. How large is the subgroup of $\mathrm{Cl}_K$ generated by the classes of the ideals in $S$?


3. Galois groups

  1. Determine the Galois group of $f = x^3 + x + 1 \in \mathbf{Z}[x]$.

    galois_group, number_field

  2. Find a polynomial of degree $6$ with the same Galois groups as $f$.

    normal_closure, defining_polynomial, isisomorphic

  3. Determine the Galois groups of $1000$ random monic, irreducible polynomials in $\mathbf{Z}[x]$ of degree $3$ and coefficients bounded in absolute value by $10$. What is the distribution?

    rand, setcoeff!, isirreducible

  4. For all transitive groups of order $4$, find a monic irreducible polynomial of degree $4$ of $\mathbf{Z}[x]$ with that Galois group (random monic polynomials with coefficients in absolute value bounded by $10$ will do).

    transitive_group_identification, number_transitive_groups, count

4. Abelian extensions

  1. Define the number field $K = \mathbf{Q}(\sqrt{2})$.


  2. Find a normal extension $L/K$ such that $\operatorname{Gal}(L/K)$ is non-cyclic of order $4$.

    automorphism_group, iscyclic, order

  3. Find all normal extension $L/K$ with $\operatorname{Gal}(L/K) \cong C_2 \times C_2$ such that $L/\mathbf{Q}$ is normal and the absolute discriminant of $L$ is bounded by $10^{10}$.


  4. Determine a defining polynomial for one of the fields $L$ found in part 3. What is $\operatorname{Gal}(L/\mathbf{Q})$?

    absolute_simple_field, galois_group, describe

5. Determinantal variety

  1. Define the polynomial ring $R = {\mathbf{F}}{_4}[x_{ij} \mid 1 \leq i \leq 3, 1 \leq j \leq 3]$.

    PolynomialRing, FiniteField, GF

  2. Define the matrix $M = (x_{ij})_{1 \leq i \leq 3, 1 \leq j \leq 3} \in R^{3 \times 3}$.


  3. Determine the defining ideal of the determinantal variety $V$ of size $3 \times 3$ and rank 1, which is defined as the vanishing set of the $2$-minors of $M$.

    minors, ideal

  4. What is the dimension of $V$?


  5. Determine $\lvert V(\mathbf{F}_4) \rvert$, where $V(\mathbf{F}_4) \subseteq \mathbf{F}_4^9$.

    AbstractAlgebra.ProductIterator, evaluate, all

6. Gröbner bases

  1. Define the polynomial ring $R = \mathbf{Q}[x, y, z]$.


  2. Define the ideal $I = \langle xy + z, yz − x, zx − y \rangle$.


  3. Determine $\dim(I)$.


  4. Compute a Gröbner basis of $I$ with respect to the lexicographical ordering.


  5. Is $I$ a prime ideal?


  6. Find a prime ideal containing $I$.


7. Integral lattices

  1. Define the $\mathbf{Z}$-lattice $L$ with Gram matrix \(\begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 68 \end{pmatrix}.\)

    Zlattice, matrix

  2. Determine generators $S$ for the automorphism group of $L$ and its order.

    automorphism_group_generators, automorphism_group_order

  3. Define the matrix group $G = \langle S \rangle \subseteq \operatorname{GL}_3(\mathbf{Q})$.


  4. Find an isomorphic matrix group $H$ over a finite field.


  5. Can you find out which group this is?


  6. Find representatives for the isometry classes in the genus of $L$.


  7. Use the mass formula to show that the result of part 6 is correct ($\operatorname{mass}(L) = \sum_{L’} 1/\lvert \operatorname{Aut}(L’) \rvert$, where the sum runs over a set of genus representatives of $L$).


8. Lattices from number fields

  1. Create the number field $K$ with defining polynomial $x^3 - 54x - 150 \in \mathbf{Q}[x]$.


  2. Determine the $\mathbf{Z}$-lattice $L = (\mathcal{O}_K, q)$, where $q$ is the quadratic form associated to the trace pairing.

    Zlattice, basis, trace

  3. What is the signature of $L$? What is the signature of $K$?


  4. Consider the fields $K_1$ and $K_2$ defined by $x^3 - 36x - 78$ and $x^3 - 18x - 6$ respectively. For $K_1$ and $K_2$ construct lattices $L_1$ and $L_2$. Are the fields $K_i$ isomorphic to $K$? Are the lattices $L_i$ in the same genus as $L$? Are the lattices $L_i$ isometric to $L$?

    genus, isisometric, isisomorphic

9. Product of rings

The goal of this exercise is to implement $R \times S$, the product of two commutative rings $R$ and $S$.

  mutable struct ProdRing{S, T} <: AbstractAlgebra.Ring
  mutable struct ProdRingElem{U, V} <: AbstractAlgebra.RingElem

Implement enough functionality to make the following work:

  R = product_ring(ZZ, QQ)
  a = R(ZZ(2), QQ(1, 2))
  M = matrix(R, 2, 2, [1, a, 0, 1])
  M * M
  Rx, x = R["x"]
  f = (a * x)^2

Assuming that both rings are Euclidean and support the divrem function, implement divrem also for product rings. Try to make the following work:


As an example for a ring implementation, consider the implementation of $\mathbf{Z}[i]$ here.

10. Skew-polynomial rings

Let $S = R[X]$ be the set of all polynomials $\sum_{i} a_i X^i$ and $f$ a ring endomorphism of $R$. We define $X \cdot r = f(r)\cdot X$ for $r \in R$. With the ordinary additional of polynomials, this yields a skew-polynomial ring, which we want to implement.

  mutable struct SkewPolyRing{S, T} <: NCRing

  mutable struct SkewPolyRingElem{U} <: NCRingElement

The goal is to make the following work:

  F, a = FiniteField(3, 2, "a")
  S, x = skew_polynomial_ring(F, a -> a^3, "x")
  f = F(2) * x
  g = f * F(3)
  M = matrix(S, 2, 2, [1, f, 0, 1])
  M * M

As an example for a ring implementation, consider the implementation of $\mathbf{Z}[i]$ here.

11. $\mathbf{Z}[\sqrt{2}]$ as an Euclidean ring

The aim of this exercise is to implement the ring $\mathbf{Z}[\sqrt{2}]$ together with its Euclidean structure, which is determined by the Euclidean function $v(a + b \sqrt 2) = \lvert a^2 - 2b^2 \rvert$. To satisfy the ring interface, we will use the following type for the parent:

  mutable struct ZZSqrt2

We will represent elements $a + b \sqrt 2$ using the following type:

  mutable struct ZZSqrt2Elem

Implement enough functions to make the following work

  R = ZZSqrt2()
  x = R(2, 3)
  y = R(0, 1)
  q, r = divrem(x, y)
  M = matrix(R, 2, 2, [1, 2, x, y])

As an example for a ring implementation, consider the implementation of $\mathbf{Z}[i]$ here.

12. Inverting integer matrices

The aim is to implement two methods to invert invertible integer matrices. The first method will be based on $p$-adic lifting and the second one on the Chinese remainder theorem.

  1. Implement a function

     function inverse_via_lifting(A, p)

    which given an invertible integer matrix, determines the inverse via $p$-adic lifting and inversion of matrices over $\mathbf{F}_p$.

    Hint: If $B$ is the inverse of $A$, write $B = B_0 + pB_1 + p^2 B_2 + \dotsb$ and reduce modulo $p$. There is no need to work with $p$-adic integers. It is sufficient to work in $\mathbf{Z}$ and $\mathbf{F}_p$. Helpful commands: change_base_ring, inv, lift, divexact.

  2. Implement a function

     function inverse_via_crt(A, startp)

    which given an invertible integer matrix, determines the inverse using the Chinese remainder theorem and inversion of matrices over $\mathbf{F}_p$ for various primes $p$.

    Helpful commands: change_base_ring, inv, lift, crt.

  3. Compare both functions on random matrices of different sizes.

  4. Can you do the same for matrices over $\mathbf{F}_q[x]$ by replacing primes with irreducible polynomials?

Oscar exercises: Group theory

You may wish to consult the Oscar documentation.

1. Fixed point free permutations

  1. Write a function $f$ which computes for small values of $n$, the number of fixed point free permutations on $n$ points. For example, $f(1)=0$, $f(2)=1$, $f(3)=2$, $f(4)=9$ and $f(30)=97581073836835777732377428235481$.

    symmetric_group, conjugacy_classes, number_moved_points

  2. Write a function which computes the proportion $x(n)$ of these permutations in the symmetric group on $n$ points, and the first decimal digits of $x(n)$ and $1/x(n)$.

  3. Do you have a conjecture what $\lim_{n \rightarrow\infty} x(n)$ is?

2. Shuffle groups

Inspect the groups returned by the following function, for small positive values of n.

  function shuffle_group(n::Int)
    out_perm = zeros(Int, 2*n)
    out_perm[1:2:(2*n-1)] = 1:n
    out_perm[2:2:(2*n)] = (n+1):(2*n)

    in_perm = zeros(Int, 2*n)
    in_perm[1:2:(2*n-1)] = (n+1):(2*n)
    in_perm[2:2:(2*n)] = 1:n

    sym = symmetric_group(2*n)
    return sub(sym, [sym(out_perm), sym(in_perm)])[1]
  1. Determine the group orders.

  2. How many of the groups are abelian / perfect / simple / solvable?

  3. Can you give an interpretation what these groups describe?

3. Matrix groups

Given a finite group $G$ of $n \times n$ matrices over QQ, find a matrix $T$ such that conjugation of $G$ with $T$ yields a group of matrices over ZZ.

Hint: More generally, let $R$ be a ring with quotient field $K$, and let $G$ be a matrix group over $K$. Let $m$ be an integer such that the entries of $m M$ are in $R$, for all $M \in G$, and consider the set $U = m R^n G$; then $U$ is a subset of $R^n$ and invariant under multiplication with elements of $G$. If we know that any finitely generated $R$-submodule of $R^n$ has an $R$-basis then we can compute the action of $G$ on $U$ w.r.t. such a basis.

  1. Write a function that computes integral matrices from rational ones, as sketched in the hint.

  2. Apply the function to the group generated by the matrices

    \[\begin{pmatrix} 25 & -6 & 3 \\ -5 & -4 & 15 \\ 7 & 42 & 5 \end{pmatrix} / 26, \quad \begin{pmatrix} 11 & 14 & 19 \\ 37 & -64 & -33 \\ -35 & 102 & 53 \end{pmatrix} / 26.\]
  3. Usually groups are given by generators. Develop an algorithm that solves the problem from part 1. without running over all group elements.

  4. Does this method work also for (finitely generated) infinite groups?

4. Finitely presented groups

  1. Determine all groups (up to isomorphism) that are generated by three elements $x, y, z$ and such that the relations $xy = z$, $yz = x$ und $zx = y$ hold.

    free_group, gens or gen, quo, normal_subgroups

First lecture

1. Abelian quotients

  1. Define the group $H = \langle x, y \mid x^2 y^2 = 1, x^{-1} y^3 x^4 y = 1 \rangle$.

    free_group, gens or gen, quo

  2. Write a Julia function that computes the isomorphism type of the abelian quotient $G/G’$ of a given FPGroup $G$ via the Smith normal form of the matrix of abelianized relators. Apply it to the group $H$ defined above.

    abelianized (defined in the Julia module in the repository for exercises), relators, snf

  3. Test the function by comparing the results with the GAP function available in Oscar.

    Use GAP.Globals.AbelianInvariants(G.X). Note the difference between the diagonal of the Smith normal form and the result of the GAP function AbelianInvariants.

  4. In order to write down a group epimorphism from $G$ to $G/G’$ that maps the generators of $G$ to the corresponding integer vectors, one needs not only the Smith normal form but also a transformation matrix. Write a Julia function that computes the epimorphism.

  5. The entries in the transformation matrices that occur in the computation of the Smith normal form can get quite large. Make some experiments with random integer matrices whose entries have small absolute value. Consider also $n$ by $n$ diagonal matrices with diagonal entries $1, 2, \ldots, n$.

2. Collection

Hint: There is a github repository with a straightforward implementation of collection in pc groups. You can (fork and) clone it, add the Julia module to your Julia session, and then extend and improve the code.

  1. Implement the collection process in Julia. That is, define data structures representing an (uncollected) word and a collector object that contains the relators of a consistent pc-presentation.

    Test the implementation for various groups:

    • Try different collection strategies (collection to the left, from the right, from the left, as defined in the talk), by providing suitable findfirst_uncollected functions. How many steps are needed for various examples?

    • What are the steps when one applies collection for multiplying elements in abelian groups?

    • Try also some infinite groups, for example the infinite dihedral group.

    • How can the implementation be simplified for finite groups and for finite $p$-groups?

  2. The GAP system provides several implementations of collectors (written in C) for finite polycyclic groups. (And the GAP package Polycyclic deals also with collection for infinite polycyclic groups.) How can some of the tricks used in that code be used in the Julia implementation?

  3. Implement a new type of elements in polycyclic groups for which multiplication and inversion are based on collection in Julia, not on underlying group elements in GAP.

  4. The GAP help for “Pc Groups” (a chapter in the GAP Reference Manual) lists more rules for a power-conjugate presentation than the definition of a polycyclic presentation in the talk. Are the additional rules necessary?

Second lecture

1. Consistency algorithm

  1. Implement the consistency algorithm for $p$-groups. That is, write a Julia function that takes a perhaps inconsistent pc-presentation (via a collector object, see the exercises for the first lecture), and returns a consistent one.

  2. Implement a check whether a given pc-presentation is consistent.

  3. The consistency theorem is stated for $p$-groups only. How would a consistency theorem for general polycyclic presentations look like?

2. $p$-covering group

Write a function that takes a consistent pc-presentation of a $p$-group $G$ (via a collector object, see the exercises for the first lecture) and returns a consistent pc-presentation of the $p$-covering group of $G$.

Third lecture

1. Burnside groups

We know that the Burnside group $B(2,4)$ (the largest $2$-generator group of exponent $4$) is finite and has order $2^{12}$. Find a proof for this statement, by constructing a presentation for $B(2,4)$, with suitable $4$-th powers as relators.

(It is known that the minimal number of relators is $9$.)

2. Fibonacci groups

  1. Write a function that creates the generalized Fibonacci groups $G_n(m, k)$ as a finitely presented group.

  2. Use the theorem mentioned in the talk to prove that $G_9(1, 2)$ and $G_9(3, 4)$ are infinite.


    The GAP implementation of the p-quotient algorithm can be used. Consider the first steps of the $p$-central series of a suitable subgroup of $G_9(1, 2)$, for a suitable $p$.

Edit this page Contact Imprint Privacy policy © 2018-2024 The OSCAR Team