Mackey functor undergrad research

I recently finished an Undergraduate Research program run by the University of Sheffield mathematics department.

My subject was the highly abstract concept of “Mackey functors”. These are a niche but important part of many advanced mathematical concepts, including stable homotopy theory, and representation theory.

Their invention was motivated by trying to create a formal mathematical object which could find morphisms between different properties between a group and it’s subgroups. For instance, we may want to find a map between the order of a group’s subgroups. We may write a sketch to demonstrate what these mappings between subgroups should look like:

How do we formalise this into a concrete mathematical idea?

Category theory

In order to have any hope in defining such an object, we must explore a bit of category theory. But don’t worry, the initial definition is not actually too hard to understand!

A category \mathcal{C} is comprised of two types of things, a collection of objects (\text{Obj}(\mathcal{C})), and a collection of “morphisms” between these objects (\text{Hom}_{\mathcal{C}}(A, B)).

These are subject to two criteria, or axioms:

  1. For each object in A in \mathcal{C}, there must exist an \textbf{identity} mophism \operatorname{id}_A such that f \circ \operatorname{id}_A = f = \operatorname{id}_A \circ f for all compatible morphisms f.
  2. \textbf{Composition} must be well-defined. That is, where we have morphisms f in \operatorname{Hom}_{\mathcal{C}}(A, B) and g in \operatorname{Hom}_{\mathcal{C}}(B, C), we can find g \circ f in \operatorname{Hom}_{\mathcal{C}}(A, C).

Some examples of categories include:

  • \mathbf{Set} – the category of sets. Contains all sets and all possible set mappings between these sets.
  • \mathbf{Ab} – the category of abelian groups. All abelian groups and all homomorphisms between these abelian groups.
  • \mathbf{Grp} – the category of groups. All groups and all homomorphisms between these groups.
  • \mathbf{Cat} – the category of all small categories. Morphisms are “functors” (maps between categories).
  • \mathbf{Graph} – the category of graphs. All possible graphs and all graph homomorphisms between them.

Definition by a function and axioms

One of the ways to define a Mackey functor is to use a function and then axiomatically enforce the existence of morphisms which go “up” subgroups and morphisms which go “down” subgroups. As the previously presented diagram suggests, we want our object to contain a morphisms to and from each pair of subgroups.

Consider a group G. A G-Mackey functor \underline{M} is a function from the subgroups of G to abelian groups in the \mathbf{category} of abelian groups, \mathbf{Ab}.

    \[\underline{M}: \{\text{subgroups of}~ G\} \to \mathbf{Ab}\]

The category \mathbf{Ab} must contain the following morphisms…

    \[\text{Transfer} \colon ~~~ \text{tr}_{K}^{H} \colon \underline{M}(K) \to \underline{M}(H)\]

    \[\text{Restriction}\colon ~~~ \text{res}_{K}^{H} \colon \underline{M}(H) \to \underline{M}(K)\]

    \[\text{Conjugation}\colon ~~~ \text{c}_{g} \colon \underline{M}(H) \to \underline{M}(^{g}H)\]

for all subgroups K \leq H of G and all elements g \in G. The morphisms are subject to the following axioms:

    \[\begin{enumerate}\item $\text{tr}_{H}^{H}, \text{res}_{H}^{H}, \text{c}_{h} : \underline{M}(H) \to \underline{M}(H)$ are identity morphisms.\bigskip\item $\text{res}_{J}^{K}\text{res}_{K}^{H} = \text{res}_{J}^{H}$\bigskip\item $\text{tr}_{K}^{H}\text{tr}_{J}^{K} = \text{tr}_{J}^{H}$\bigskip\item $\text{c}_{g}\text{c}_{h} = \text{c}_{gh}$ for all $g, h \in G$.\bigskip\item $\text{res}_{^{g}K}^{^{g}H} \text{c}_g = \text{c}_{g} \text{res}_{K}^{H}$\bigskip\item $\text{tr}_{^{g}K}^{^{g}H} \text{c}_g = \text{c}_{g} \text{tr}_{K}^{H}$\bigskip\item $\text{res}_{J}^{H} \text{tr}_{K}^{H} = \sum_{x \in [J\setminus H / K]} \text{tr}_{J \cap ^{x}K}^{J} \text{c}_{x} \text{res}_{J^{x} \cap K}^{K}$ for all subgroups $J, K \le H$.\end{enumerate}\]

Most of these rules are actually quite simple ideas. Most of them mathematicians are very familiar with, such as the idea that conjugation has to play well. For instance, if we reduce from H to K, then reduce again from K to J, we would expect that to be the same thing as reducing from H to J (this is what the second axiom is saying).

The axiom that doesn’t make sense is the notorious double coset formula – the last one. The story of why this axiom is included is quite interesting. It was originally included because it was a property that many examples of Mackey functor-like objects were exhibiting. It was then observed later on in a clever reformulation of the Mackey functor where it’s inclusion becomes undeniable.

Example: the constant Mackey functor

Let’s consider the constant C_4-Mackey functor.

We must define a mapping from each of the subgroups of C_4 to an abelian group. By definition, the constant Mackey functor assigns the same abelian group (we can call it A), to each of the subgroups.

We can then determine the restriction and transfer morphisms.

Restriction

The restriction morphism is \text{res}_{K}^{H} \colon A \to A, so in this case, we simply define it as the inclusion map. As the domain of this function is a subset of the codomain, we can define a map which takes every element in the domain to the same element in the codomain. We can denote this as:

    \[\text{res}_{K}^{H} \colon \underline{M}(H) \xhookrightarrow{} \underline{M}(K)\]

Transfer / Conjugation

The transfer map is a bit more interesting. In the case of the constant Mackey functor, it happens that it is defined as so:

For a transfer \text{tr}_{K}^{H} we define it as multiplying an element a \in A by the index of K in H ([H : K). This is quite similar to what we were doing in the original example I gave of what a Mackey functor does – it’s revealed the change in size as we move up subgroups.

In this case conjugation is also just the identity morphism. All these groups are normal so conjugation does nothing to them.

You maybe wondering how we decided these functions are the transfer and restriction morphism. It all comes down to the axioms. We define this Mackey functor to take all subgroups to the same abelian group (hence “constant”), and then we look at the axioms. The restriction, transfer and conjugation we choose must satisfy the axioms, and the axiom that imposes the most limitation on what these can be is the double coset formula. By taking the double coset formula, we can cleverly choose subgroups so that the formula simplifies down and reveals some information about the morphism we are looking at. It is via this method that the correct function actually pops out.

Taking it further

This definition of a Mackey functor using a functor is nice enough, but you may have noticed that it’s a Mackey functor, not function. Let’s look at what a functor is

Functors

A functor is a mapping between categories. Given two categories \mathcal{C} and \mathcal{D}, a functor creates an association from every object A in \text{Obj}(\mathcal{C}), to a corresponding object F(A) in \text{Obj}(\mathcal{D}), and similarly, for the morphisms f in \text{Hom}(\mathcal{C}), it provides a morphism F(f) in \text{Hom}(\mathcal{D}).

These maps are subject to maintaining proper composition. The functor must map composed morphisms in \mathcal{C} to the composition of the mapping of the individual morphisms, i.e.: F(g \circ f) = F(g) \circ F(f). This can be represented by the following commutative diagram:

A commutative diagram illustrating the concept of functors in category theory, showing the relationships between objects A, B, and C as well as their corresponding mappings through a functor F.

Okay so with functors, we can map from a category to a category. So instead of mapping from the subgroups of G to the category of abelian groups, and then axiomatically enforcing the existence of the morphisms we want, it would be nice to find a special category in which we can make a sensible assignment from each morphism in said category to restriction, transfer and conjugation.

That category turns out to be \text{Span}(\mathbf{SpanGSet}). Using this object, we can create a full definition of a Mackey functor in just a few lines:

A Mackey functor is a functor

    \[\underline{F} \colon \text{Span}(\mathbf{FinGSet}) \to \mathbf{Ab}\]


which preserves products.

Thanks for reading!

Wacky Factorials

We all know the definition of the factorial ! as n! = n(n-1)(n-2) \cdots 2*1 but there are even more definitions of factorials that mathematicians have invented.

Double Factorial

The double factorial looks like this n!!. It can be used to easily denote the product of the odd or even numbers less than or equal to n

    \[n!! =\left{\begin{matrix}n(n-2)(n-4) \cdots, \textrm{even n}\\n(n-2)(n-4)\cdots*1 , \textrm{odd n}\end{matrix}\right.\]

Subfactorial

The subfactorial has a really intuitive practical application. Imagine you have n tokens in defined positions in an array. You take all the tokens out and want to place every token back into the array so that none of the tokens end up in the position they were just in. This is called derangement.

For instance, {1, 2, 3},
You can arrange this set in the following ways: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].

Only two of these sets satisfies the above criteria, {2, 3, 1} and {3, 1, 2}

Therefore we say !3 = 2

Primorial

The Primorial is denoted n# and is the product of primes less than and equal to n.

n# = \prod_{P\leq n}^{}P

Primorials are used in the search for large prime numbers. Each primorial has more distinct prime factors than any number smaller than it.

Superfactorial (Sloane)

The more common definition of the Superfactorial. It is defined as such:

sf(n) = \prod_{k=1}^{n}k!

For example: sf(4) = 4!*3!*2!*1! = 288

You can look at it another way by expanding the factorials: sf(4) = 4*3^{2}*2^{3}*1^{4}

And so:

sf(n) = \prod_{k=1}^{n}k^{n-k+1}

Superfactorial (Pickover)

Another definition of the Superfactorial uses tetration.

    \[n\$ = _{}^{n!}\textrm{n!}\]

It grows insanely fast.

    \[4\$ = 24^{24\cdots^{24}}\]

Exponential Factorial

Annoyingly also denoted

    \[n\$\]

the exponential factorial is like a normal factorial but exponentiated instead of multiplied:

    \[4\$ = n^{n-1^{n-2}\cdots^{1}}\]

Hyperfactorial

Finally the hyperfactorial is defined like this:

H(n) = n^{n}(n-1)^{n-1} \cdots 2^{2} * 1^{1}

Or:
H(n)=\prod_{k=1}^{n}k^{k}

And hence is very similar to the Sloane definition of the superfactorial:

H(4) = 4^{4}*3^{3}*2^{2}*1^{1}

Fractal Flow

Fractal Flow is my largest programming project so far; here’s a little about it:

Early days

I started Fractal Flow on January 12th 2022, after a few months of learning and tinkering with the Windows Presentation Foundation in my Computer Science class. The application was to be my coursework, which makes up 20% of the AQA A-level Computer Science grade.

January was not usually the month in which my college starts pupils on the NEA (Non-Examination Assessment), however my teacher had offered that I start early due to my prior knowledge in programming. I snatched the offer, hoping I could turn this opportunity to spend hours of my time programming into something more than just my A-level coursework – I wanted to create a piece of professional software that could persist as a gem in my portfolio for years to come.

What is it?

Fractal Flow is a fractal generator. Its job is to generate and export images of fractals, geometric shapes which contain a high level of detail when zooming in and often contain entire versions of themselves.

One of the most famous fractals is the Mandelbrot Set, first visualised by Benoit Mandelbrot in 1980. This infinitely detailed object is constructed over the complex plane with the formula z^2 + c, a deceptively simple operation for the immense complexity which is generated.

Mandelbrot set zoom

z^2 + c is but one of an infinite set of formulae that can be chosen to create fractals on the complex plane. These unlimited possibilities is what Fractal Flow is designed to explore. The software is fully focused on creating fractals from any formula the user can come up with – doing so with incredible performance.

Mission

From the beginning I was laser focussed on creating a product that was not only intuitive and visually attractive, but also competently engineered behind the scenes. The first step to achieving this was abandoning what was expected of me: using WinForms. I taught myself WPF (Windows Presentation Foundation) and furthermore how to use it with a professional approach. MVVM (Model View View Model) allowed for a proper separation between the user interface and the business logic and thus opened the door to code reusability.

The MVVM approach to applications
Designing the UI

I was not happy with leaving my app with a bog-standard UI. Noticing that all the fractal generators I had tried had very tired visuals, I set about changing the expectation for how such software could look by creating a sleek, modern user interface.

This was my first time using the brilliant website Figma. I had a lot of fun designing the pages and selecting iconography and typefaces.

Rendering Kernel

The crown jewel of the application is the rendering technique I developed for it. Rather than running the computationally intense tasks in C# on the CPU, Fractal Flow hands rendering to the GPU. This allows for an enormous increase in performance (over 1000x faster in my tests).

The GPU is faster than the CPU in this field because it allows the concurrent execution of hundreds of calculations simultaneously. The colour of each pixel in these fractal images are completely independent of the other pixels in the image, so they can be treated as completely different processes to each other. This makes parallelisation really easy as each pixel can be sent as a separate job to the GPU.

To harness the power of the GPU in WPF, I used a library which provided access to OpenCL (Open Computing Language). This allowed me to provided a small piece of C code called a kernel that is to be run on the GPU. I could specify how many of these kernels are sent to the GPU and an array of arguments to be distributed between them.

This is where the clever part comes in. From the iterative formula the user specifies to generate their fractal, a line of C code representing that operation is generated. This is then implanted into the kernel to create a new program, specifically programmed to render the fractal. This approach is called metaprogramming, a technique where code writes itself.

I used this approach for technical limitations (my understanding was that using the complex number libraries in the OpenCL library kernel was unsupported so I resorted to a series of macros for my complex operations), and also because I believed that it would reap even greater computational performance over the CPU.

Diagram of render pipeline
Proprietary Formula Parser

I created my own mathematical formula parser for this application. This was not a necessary step – reinventing the wheel for such a common process is not good practice. Regardless I made a homemade parser because: 1. It was a valuable learning process and 2. It would give me marks in my NEA 3. It allowed me total control over how the parser worked.

Developing this algorithm taught me about Dijkstra‘s Shunting Yard Algorithm (yes the same Dijkstra who invented the route finding algorithm), which converted an expression in infix notation to the Reverse Polish Notation required for execution by computers.

I also made sure my algorithm allowed for relatively natural expression. For instance it accepted notation such as “5z“, the terse form of “5 \times z“. I realised I could summarise token adjacency behaviour in a table:

Current State

I left Fractal Flow in a state I was relatively happy with, however there were still many features I envisioned for the application that have not made it to the application yet. For instance I initially wanted the application to be able to produce zooming videos, and have a multitude of different colouring algorithms as found in other fractal generators.

It was investigating colouring algorithms where I found a large problem with the code of Fractal Flow – an issue so large that it led to a downfall in motivation to develop the project. The problem was that many colouring algorithms require information *other* than simply the number of iterations each pixels took before it triggered the bail, such as the distance the iteration that triggered the bail “jumped” from the prior position. Implementing the inclusion of this information would require a large redesign of the render pipeline and considerable thought over how to architect a memory-efficient system.

I learnt an important lesson in discovering this flaw: to always research thoroughly absolutely everything my system might be implementing on top of what I already know it must.

There are also a few areas of the program that are unnecessary or artificially shoe-horned into the designed, with the purpose of hitting more targets on the NEA mark scheme. For example the formula parser discussed earlier, and the use of an SQL database to store fractal definition objects (I think simply storing them in files would be more reasonable).

Fractal Flow is currently over 10000 lines with over 20 classes.


GitHub README

FractalFlow

WIP – This is my A-level (Junior/Senior year equivalent) Computer Science coursework as submitted. REMEBER TO MAKE BRANCH IF WORKING ON FURTHER

Fractal Flow is a next generation application for rendering fractal images over the complex plane, with a focus on generating custom user-defined fractals.

<p align=“center”> <img src=“https://github.com/ProgramPhantom/FractalFlow/assets/49105496/bea77f82-704e-496d-a2e5-73ba33bd892d” /> </p>

Mission:

Fractal Flow aims to streamline and accelerate the process of exploring new fractal objects – beyond the Mandelbrot set. Fractal Flow combines a blazing fast rendering kernel with a UI whioh empowers rapid iteration and generation of ideas.

Architecture:

Implementation detail:

  • Fractal Flow uses a meta-programming approach to achieve superior performance. The application generates an OpenCL Kernel specifically for the formula specified, which is ran on the GPU.
  • The application currently also includes a renderer for the CPU, however it is highly unoptimised and unfeasibly slow, and thus will no longer be maintained.

Examples

User Interface

Tan

Features

  • CPU & GPU rendering capabilities
  • Create a custom fractal by specifying a formula
  • Natural math expression achieved through proprietary formula parser
  • Two types of fractal colouring algorithm
  • Specify iterations, bail value and region on the complex plane
  • Save and load proprietary .frac fractal definition file
  • Save fractal image as .png
  • Random colours button
  • Console Window
  • Fractal definition objects saved in SQL database

Started 12th Jan 2022

Song of the article

Differential Equations

What is a Differential Equation? (DE)

A differential equation is an equation which contains the derivative of one or more of the variables.

They are incredibly useful because they allow models to describe the rate of change of values rather than the size of the values.

First order Differential Equations

Some first order differential equations can simply be solved by separating variables and integrating. This is a normal maths technique so I will be skipping over it.


Linear first order differential equations are in the form:

To solve these, you can observe how an application of the product rule would have produced the expression on the left side.

For instance, take the linear first order differential equation:

Observe that by applying the product rule to the expression

Gives the same expression as on the left of the above equation, taking into account the need for implicit differentiation.

After spotting this, integrating both sides with respect to x will yield a solution, but don’t forget a + c on one of the sides!

DONE! Don’t forget to apply the division of x to the c as well.

Integration Factor

Sometimes the equation will not immediately be susceptible to the reversed product rule attack, but we can change the equation to force it to.

First, a particular expression must be found called the Integrating Factor (IF). This can be found using the formula:

Multiply the entire equation by this expression and the trick described earlier will always work.

Second Order Differential Equations

Second order differential equations are differential equations which contain a second derivative.

Homogeneous

Here is how to solve differential equations in the form:

This is called a homogeneous equation because it is equal to zero.

The first step in solving these equations is to form the Auxiliary Equation (A.E).

There are three scenarios to follow depending on the solutions to this quadratic:

Scenario 1: Distinct Real Solutions

In the case where the quadratic has two distinct real solutions, use the equation:

Scenario 2: Repeated Real Solution
Scenario 3: Imaginary Solutions

Where the roots are the form of:

These expressions are called the Complementary Function (C.F.).


Select the correct equation and sub in the roots and you have the General Solution (G.S).

Non-homogeneous

You need to add an extra step if the differential equation is not equal to 0, rather a function of x.

The first step is to get the Complementary Function like usual.

You then have to find the Particular Integral (P.I.) which satisfies the differential equation. First, observe the form of the function of x on the right side of the equation. Depending on it’s form, select on of the following forms of expression.

Form of f(x)Form of P.I.
kλ
ax+bλx + μ
ax2 + bx + cλx2 + μx + ν
mcos(ωx)λsin(ωx) + μcos(ωx)
msin(ωx)λsin(ωx) + μcos(ωx)
msin(ωx) + ncos(ωx)λsin(ωx) + μcos(ωx)

Once one of these equations has been found, set it equal to y and find the first and second derivative.

Then sub these three expression into the formula. Compare coefficients to find the values of the unknowns.

You have now found the Particular Integral! Simply add this to the Complimentary Function to find the complete general solution!

y = Complimentary Function + Particular Integral

Song of the article