Cayley Graphs and Pretty Things

More on this site:

Blog (from latest)

DUCTF 2023: Encrypted Mail Writeup [Crypto, 3 solves]

Cayley Graphs and Pretty Things

SEETF 2023 Author Writeup

Drawing with Nothing: Exploiting aliasing and moire patterns to draw for you

Visual Proof of Schreier Refinement Theorem and Jordan-Hölder Theorem

Visualising Homomorphisms

Social Engineering to Solve A Crypto Challenge

Greyhats 2022 Finals Writeup

SEETF 2022 Author Writeup

CTFSG 2022 Author Writeup and The Making Of

A Surprising Place $e$ Appears In

Renumbering Dice

An Elementary Solution to the Basel Problem

RARCTF 2021: Mini-A3S Writeup (Crypto 1500)

RARCTF 2021: Randompad Writeup (Crypto 700)

RARCTF 2021: A3S Writeup (Crypto 800)

Abusing LOAD_FAST in Python 3 VM

Magnifying the Micro with Moiré Patterns

CDDC 2020: A Kind Of Crypto

A Quadratic Recurrence Relation that Computes $\pi$

The Most Inefficient Way to Compute $\pi$

Art (from latest)

Interference

Twenty Five

Fire Gyroid

Ripples

AES-128 Diffusion

Lotus Tessellation

Simple Ostrich

MT19937

Heart Tessellation

Julia Orbit Traps

Anagrams

Spiral Glow Cube

Linearly Transformed Cosines with Textures

Differentiating Fluid

Dot Splash

Foggy Glass

Lacy Julia Fractal

Gold Agate

Paint

Colourful Bubbles

Categories > Archive<br>2. Projects > Categories > Archive<br>},-->

Cayley Graphs and Pretty Things

A fun approachable introduction to Cayley Graphs (and a little bit of group theory), and a writeup to this little web widget I made

📅 15 Jul 2023 - JuliaPoo ^-^<br>📚 Word Count: 4143

🏷️ Tags:

#group-theory

#rotation-groups

#direct-products

#semidirect-products

I recently made a little web-widget to plot Cayley Graphs of over 6000 finite groups because they look pretty.

And they are pretty, right? Above is the plot of the cayley graph of a very well-known group $A_5$. For all such diagrams in this post, feel free to zoom, pan and rotate the plots.

Wait what are Cayley Graphs?

In short, Cayley Graphs are graphs, and by that I mean a bunch of vertices connected by lines, that encode, rather inefficiently, the abstract structure of a Group.

A Group on the other hand is, informally, a non-empty set whose elements are 'symmetrically related' to each other. Groups are very fundamental objects in Mathematics and appear everywhere in Mathematics. The symmetries of a particular group are somewhat reflected in the symmetries of its cayley graph.

While a group's cayley graph encodes the entire structure of a group, it does so rather inefficiently and it's often easier to study groups abstractly. However, I think they are pretty, and there are a few group-theoretic concepts that present themselves naturally in cayley graphs.

This post will cover some intuition about Groups, and discuss informally some classes of groups to appreciate cayley graphs, and you can also try plotting other groups in my web-widget. In particular, this post will cover Rotation Groups, Direct and Semi-direct products. I'm particularly proud of the discussion on semi-direct products as it's, to my knowledge, a new way to introduce the subject.

What are groups?

Here's a description of a group:

A group $G$ is a non-empty set of elements and a binary operation $\cdot$ such that for any $a,b,c \in G$ the following holds

Associativity: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$

Identity: There exists an element $e \in G$ such that $a \cdot e = e \cdot a = a$. In other words, $e$ doesn't do anything when multiplied with another element.

Inverse: There exists an element denoted as $a^{-1}$ such that $a \cdot a^{-1} = a^{-1} \cdot a = e$. In other words, $a^{-1}$ reverses what $a$ does, since $a^{-1} \cdot a \cdot b = e \cdot b = b$.

Where a binary operation is simply some operation that takes in two elements of $G$ and spits out another element of $G$.<br>Note that we do not require $a \cdot b = b \cdot a$. This property of being able to “flip” the order of arguments is called Abelian.

If a group $G$ has a finite number of elements, I'll call it a finite group. Otherwise, it's an infinite group.

For brevity I would sometimes omit the $\cdot$, so $a \cdot b$ might be written as simply $ab$.

This description can apply to a whole bunch of things. A classic example is the integers $\mathbb{Z}$ with the binary operation $+$. For any integers $a,b,c$, we have:

$(a + b) + c = a + (b + c)$

$0 + a = a + 0 = a$

$a + (-a) = (-a) + a = 0$

Of course, in this example, $\mathbb{Z}$ is abelian as $a + b = b + a$. There are however groups where this doesn't hold. If you've played Zelda Tears of the Kingdom, you'd have encountered such a group when rotating an object.

In Zelda Tears of the kingdom, you can only rotate vertically and horizontally by 45°. Here's a tip for rotating around the third axis: Rotate all four directions, in order, for a 45° rotation

→↓←↑ = ↺<br>→↑←↓ = ↻

This happens because of some pretty neat math

1/🧵 pic.twitter.com/H64RnTcCnf<br>— chessapig (@chessapigbay)...