The OSCAR project
The OSCAR project
If you have any questions about or problems with anything related to the workshop, talk to us! Via gather.town, 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).
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.
Fork the repository https://github.com/oscar-system/Summerschool21Exercises.jl and clone this to your computer.
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.
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.)
Go to the participants list in your web browser
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)
Edit your entry in the participants list by adding your GitHub username (using the syntax already in use for some of the entries)
Submit your change as a pull request.
You may wish to consult the Julia documentation.
Implement a hello world function hello_world() which prints “hello world”.
Implement a hello function hello(name::String) which prints “hello x”, where x is the first argument.
Implement a function f(n::Int) which returns $n/2$ if $n$ is even and $3n + 1$ if $n$ is odd.
Implement a function g(n::Int) which determines the smallest $k$ with $f^k(n) = 1$.
Write a program which finds two numbers $> 100$ for which $g$ returns the same value.
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
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.
Consider the following type, which defines a permutation:
struct Permutation
images::Vector{Int}
end
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.
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)
end
Test your function by computing Permutation([2, 1, 3]) * Permutation([1, 3, 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)
end
Test your function:
p = Permutation([2, 3, 4, 5, 1])
println(apply(p, 1) == 2)
println(apply(p, 5) == 1)
Write another apply method that entry-wise applies a permutation to a tuple.
function apply(p::Permutation, x::Tuple)
end
Test your function
p = Permutation([2, 3, 4, 5, 1])
println(apply(p, (1, 5)) == (2, 1))
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)
end
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"])
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"])
Vector vs TupleObserve 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)
end
return a
end
@time G((0,1), 10^6)
@time G([0,1], 10^6)
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.
pushfirst! expect?
using Oscar, list all functions that accept a Vector argument.
After using Oscar, list all functions that accept an FmpzPolyRing.
List all functions that accept both an fmpz_mat and an fmpz.
fmpz(2)^10.
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)
sleep(1)
return s
end
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
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.
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
first::S
second::T
end
mutable struct ProdRingElem{U, V} <: AbstractAlgebra.RingElem
first::U
second::V
parent
end
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:
hnf(M)
As an example for a ring implementation, consider the implementation of $\mathbf{Z}[i]$ here.
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
poly_ring::S
f::T
end
mutable struct SkewPolyRingElem{U} <: NCRingElement
poly::U
parent
end
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.
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
end
We will represent elements $a + b \sqrt 2$ using the following type:
mutable struct ZZSqrt2Elem
a::fmpz
b::fmpz
parent
end
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])
hnf(M)
As an example for a ring implementation, consider the implementation of $\mathbf{Z}[i]$ here.
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.
Implement a function
function inverse_via_lifting(A, p)
end
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.
Implement a function
function inverse_via_crt(A, startp)
end
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.
Compare both functions on random matrices of different sizes.
Can you do the same for matrices over $\mathbf{F}_q[x]$ by replacing primes with irreducible polynomials?
You may wish to consult the Oscar documentation.
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)$.
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]
end
Determine the group orders.
How many of the groups are abelian / perfect / simple / solvable?
Can you give an interpretation what these groups describe?
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.
Write a function that computes integral matrices from rational ones, as sketched in the hint.
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.\]Usually groups are given by generators. Develop an algorithm that solves the problem from part 1. without running over all group elements.
Does this method work also for (finitely generated) infinite groups?
FPGroup $G$ via the Smith normal form of the matrix of abelianized relators. Apply it to the group $H$ defined above.
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.
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.
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?
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?
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.
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?
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.
Implement a check whether a given pc-presentation is consistent.
The consistency theorem is stated for $p$-groups only. How would a consistency theorem for general polycyclic presentations look like?
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$.
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$.)
Write a function that creates the generalized Fibonacci groups $G_n(m, k)$ as a finitely presented group.
Use the theorem mentioned in the talk to prove that $G_9(1, 2)$ and $G_9(3, 4)$ are infinite.