The goal of this blog is to explain circle group without complex mathematical definitions. However, this approach is not rigorous, it serves more like a intuition of understanding the geometry of a circle group. Before diving into the blog, may you need some pre-readings like Exploring circle STARKs or Yet another circle STARK tutorial
What we care most about a group
A group \(G\) is a set equipped with a binary operation \( \cdot\), denoted as (𝐺,⋅), the set satisfies the closure, associativity properties, and it has identity element and inverse elements.
FRI is working on a cyclic group. A cyclic group is a group that can be generated by a single element, called a generator. This means that every element in the group can be generated by applying the group operation on the generator multiple times.
Now we see circle group is used as the cyclic group in STARK, to understand its structure, the main points are
- what are the elements in this group looks like?
- what is the generator?
- what is the group operation?
Conclusion :
- what are the elements in this group looks like?
They are points on a unit circle.
- what is the generator?
It is a point on a unit circle.
- what is the group operation?
It is a rotation applying on the points!
Understanding the last claim: “group operation is basically a rotation on circle point” can make it much easier to understand the concepts of twin coset, standard coset, but I am not going to talk about these concepts, rather, how come the group operation is a rotation.
Rotation as a group operation
working with circle group, one needs to think about working on the points lying on a circle (group elements are points, instead of a single integer number modules by a prime , the coordinates of the points satisfy \(x^2+y^2=1\)). Taking a subgroup of the circle group with 8 elements as example, they are distributed evenly on the unit circle like this:
let’s “decompose” the information in this circle:
for 8 points distributed on a circle evenly, that means the angle gap between each point would be \(\frac{2\pi}{8}=\frac{\pi}{4}\), namely \(45^\circ\), if we give index of each point and the point with angle \(0^\circ\) to be index = 0, the other points can be generated by rotating the point with index =1 by \(45^\circ\) each time.
Comparing it to a group by integers module a prime, the generator of the group can generate other elements by applying the group operation “multiplication” on itself multiple times. Here in circle group, the elements in the group is generated by applying rotation as the group operation to the point with index=1 multiple times. Straightforward, it is cyclic.
For a circle group with \(2^N\) number of points, the group generator will be point with angle \(\frac{2\pi}{2^N}\), in comparison with \(2^N\) root of unity.
The math behind taking group operation as rotation
The first point of view: Polar form, in complexity analysis
we can also explain “how we can see the group operation as rotation” from the group operation equation itself.
the group operation is defined as:
\((x_0, y_0) \cdot (x_1, y_1) := (x_0 \cdot x_1 – y_0 \cdot y_1, x_0 \cdot y_1 + y_0 \cdot x_1)\)
This is basically the same as multiplying two complex numbers:
\(A=x_0+y_0i\)
\(B=x_1+y_1i\)
\(A \cdot B=\underbrace{x_0 \cdot x_1 – y_0 \cdot y_1 }_{\text{x coordinate}}+ \underbrace{(x_0 \cdot y_1 + y_0 \cdot x_1)}_{\text{y coordinate}}i\)
A Complex number \( A=x_0+y_0i \) can also be represented in Polar Form, using magnitude \( |A| \) (the distance from the origin, in circle group it is 1 as unit circle) and angle \( \theta \) (the angle between \( A \) and the positive real axis).
These are given by:
- \( |A| = \sqrt{x^2 + y^2} \) (the magnitude)
- \( \theta = \tan^{-1} \left( \frac{y}{x} \right) \) (the angle)
Using these, we can rewrite \( A \) as:
\(A = |A| (\cos \theta + i \sin \theta)\)
Then using Euler’s Formula, we can transform this trigonometric form to its exponential form:
Euler’s formula tells us that:
\(e^{i \theta} = \cos \theta + i \sin \theta\)
now we can converting \( A \) to its exponential Form:
\(A = |A| (\cos \theta + i \sin \theta) = |A| e^{i \theta}\)
In this form, \( |A| \) is the magnitude or modulus of the complex number. in circle group it is 1. \( e^{i \theta} \) represents the direction or angle \( \theta \) in the complex plane.
Now we can use concrete match equation to represent our intuition of multiplication of points on circle is actually rotation:
Multiplication of complex numbers:
\( A = |A| e^{i \theta_A} \)
\( B = |B| e^{i \theta_B} \)
then
\(A \cdot B = |A| |B| e^{i (\theta_A + \theta_B)}\)
which means, rotate \(A\) with and angle \( \theta_B\)
You may also interesting the proof for Euler’s formula, intuitive way and by using Taylor Series.
The second point of view: Trigonometry
if we see each point on the unit circle has coordinates as
\((cos\theta, sin\theta)\)
for two points:
\((cos\alpha, sin\alpha)\), \((cos\beta, sin\beta)\)
following the rule in trigonometry
\((cos(\alpha+\beta),sin(\theta+\beta))=(cos\alpha \cdot cos\beta – sin\alpha \cdot sin\beta, cos\alpha sin\beta+sin\alpha\cdot cos\beta)\)
it is exactly the group operation rule.
what next and notes
In next post, I will explain circle FFT, and another post about how to generate twin coset, by rotations.
Note:
- circle group is a cyclic group, but circle domain in circle STARK is not a cyclic group, it is a coset of a circle group, a standard position coset.
- the standard position coset is a special twin coset.
- To make FFT work, we need to use coset of circle group, this is to satisfy the 2 to 1 mapping of FFT. Explain this later.