Using multiplicative group of size 16 to demonstrate the concept of coset.
Start with STARK context:
suppose we have a trace \([1,2,3,4]\) , and we want to prove \(f(x)+1=f(gx)\)
\(g\) is the group generator for cyclic group of size 4, the same size of the trace.
generate group of size the same as the trace, namely 4
we will generate a group from a bigger multiplicative group of size 16, its group generator: \(w\) , this bigger group looks like:
\([w^0,w^1,w^2,w^3,w^4,w^5,w^6,w^7,w^8,w^9,w^{10}, w^{11},w^{12},w^{13},w^{14},w^{15}]\)
choose group generator for trace evaluation domain
to generate a group of size 4 out from this group of size 16, we can set the generator to be \(g=w^4\), and the trace evaluation domain becomes:
\([w^0,w^4,w^8,w^{12}]\)
our trace polynomial in this setting, satisfy
\(f(x)+1=f(w^4x)\) (as \(g=w^4\))
it will be interpolate to a polynomial
\(f(w^0)=1,f(w^4)=2,f(w^8)=3,f(w^{12})=4 \)
Expand the trace evaluation domain
now using blowup factor 2, we then need to get a domain of size 8, for this, we need to set \(g=w^2\), and the generated group looks like:
\([w^0,w^2,w^4,w^6,w^8,w^{10},w^{12},w^{14}]\)
you can see \([w^0,w^4,w^8,w^{12}]\) are still in this group. if we do quotient polynomial in this domain now, the vanishing polynomial can get 0 at the dominator, which should be avoid.
Get coset
so a coset (disjoint set) is needed to compute the quotient polynomial, to get a coset, just get one element that is outside of the group of size 8, multiply each of the group element, say we choose \(w^1\), and multiply each group element by \(w^1\), we get coset:
\([w^1,w^3,w^5,w^7,w^9,w^{11},w^{13},w^{15}]\)
This is the coset!
Some important facts:
Is coset a cyclic group?
No, you can check no element in the above coset can generate all the element just by doing multiply by itself. An element can be used as generator needs to be able to generate all the group element just by multiply itself many times!
How to describe the above coset of size 8?
you need the shift element \(w^1\), which is the element we choose outside of domain, and the group generator that generate a group of size 8, namely \(w^2\),
now you can represent every element in the coset by
\(w^1 * (w^2)^n\)
people sometimes call the shift point also as offset/initial index, and the group generator \(w^2\) as “step”, offset + step *n, you can have all the information of the coset.
in multiplicative group setting, a generator can also be called step. and offset is 0
how the polynomial we interpolate from the trace looks like in this coset?
first of all, the function to get the next row of the trace changed, as now our trace has size of 8, there are not the original trace anymore.
to go through these 8 points, you need \(f(w^2x)\), instead of \(f(w^4x)\), as the step here is \(g=w^2\), only use this step size you can go though 8 elements in this coset.
and now if we evaluate \(f(x)\) on coset, the values (namely the trace on the coset) we get are:
\([f(w^1),f(w^3),f(w^5),f(w^7),f(w^9),f(w^{11}),f(w^{13}),f(w^{15})]\),
you most certainly won’t be able to find \([1,2,3,4]\) anymore, as these \([1,2,3,4]\) are the evaluations of \(f(x)\) at \([w^0,w^4,w^8,w^{12}]\)
if you want to have the next reference in this setting, namely, you still want to define the following transition constraint,
\(f(x)+1=f(w^4x)\)
it will become much more complicated, the first thing to understand is that you are defining a constraint to restrict the values on \([w^0,w^4,w^8,w^{12}]\), but the trace you have now is on \\([w^1,w^3,w^5,w^7,w^9,w^{11},w^{13},w^{15}]\)
you need not only shifting, but also shrink the domain.
the solution is
\(f((g^2)*w^{-2}x^2)-f(x^2w^{-2})-1=0\) (\(g=w^2\)) now is the step of this coset
(this does not apply to circle stark, as the circle domain has more complicated structure, you need to consider the odd and even coset)
now when you set \(x\) to be the element of coset, namely \(x=[w^1,w^3,w^5,w^7,w^9,w^{11},w^{13},w^{15}]\), you can actually get the the evaluation
\(f(w^0)=1,f(w^4)=2,f(w^8)=3,f(w^{12})=4 \) that satisfies the original constraint
example:
\(x_1=w^1\)
\(f((g^2)*w^{-2}x_1^2)=f((w^4)*w^{-2}*w^2)=f(w^4)\)
\(x_2=w^3\)
\(f((g^2)*w^{-2}x_2^2)=f((w^4)*w^{-2}*w^6)=f(w^8)\)
\(f(x_1)+1=f(x_2)\)
Circle domain coset
a circle domain in stwo is represented as
CircleDomain { half_coset: Coset { initial_index: CirclePointIndex(268435456), initial: CirclePoint { x: M31(32768), y: M31(2147450879) }, step_size: CirclePointIndex(1073741824), step: CirclePoint { x: M31(2147483646), y: M31(0) }, log_size: 1 } }the circle domain is \(QG \cup Q^{-1}G\)
\(QG\) is a coset, \(Q \) is the offset, the generator of \(G\) is the step of the coset, so in the code, they would call
initial_index—->offset
step_size —-> generator of the multiplicative domain