Let $n > 1$. For an integer $k$ with $0 \leq k \leq 2^n-2$ the cyclotomic class $C_k$ of $2$ modulo $2^n-1$ is the set given by $$C_k = \{k, k\cdot 2, k \cdot 2^2 , \ldots, k\cdot 2^{n-1} \pmod {2^n-1}\},$$ where the entries are reduced modulo $2^n-1$. Note that either $C_k = C_i$ or their intersection is empty. A set $\{a_1, \ldots, a_m\}$ of integers in $[0, 2^n-1]$ is called a complete set of representatives of the classes if $C_{a_j} \neq C_{a_i}$ whenever $i \neq j$ and $$ \bigcup_{i=1}^m C_{a_i} = \{0, 1, \ldots, 2^n-1\}. $$

I am interested in, given $n$, efficiently computing the corresponding complete set of representatives of the cyclotomic classes. Any ideas? I'm hoping to be able to compute this for large enough $n$. Thanks!


You can use simple enumeration. This will be about as fast as you can achieve, for a modulus of the form $2^n-1$.

Namely, for each possible $k$, you check whether $C_k$ is a new set (distinct from the ones you already know about). If it is, you add it to the set; if it isn't; you skip it and move onto the next $k$.

This gives an algorithm like the following:

  1. Set $S := \emptyset$ and $A := \emptyset$. ($A$ holds the set of representatives; $S$ holds the set of elements covered by one of the corresponding cyclotomic classes.)

  2. For each $k=1,2,\dots,2^n-1$:

    • If $k \notin S$, add $k$ to $A$ and set $S := S \cup C_k$.

The running time of this algorithm will be $\Theta(2^n)$.

This is also within a $\Theta(n)$ factor of optimal. In particular, any algorithm must have running time at least $\Theta(2^n/n)$. The reason is that, for a modulus of the form $2^n-1$, the output size of any correct algorithm must be $\Theta(2^n/n)$: there are $\Theta(2^n/n)$ distinct cyclotomic classes. Therefore, no algorithm can run faster than $\Theta(2^n/n)$ time, since it will take at least $\Theta(2^n/n)$ time to print/construct the desired output.

Why is the output size $\Theta(2^n/n)$. Well, for the specific modulus $2^n-1$, it is guaranteed that each cyclotomic class has size $n$. (Proof: $2^n \equiv 1 \pmod{2^n-1}$, so no cyclotomic class can have size larger than $n$. Also $2^j < 2^n-1$ when $j<n$, so $2^j \not\equiv 1 \pmod{2^n-1}$ when $j<n$. Therefore each cyclotomic class has size exactly $n$.) This result is specific to the particular kind of modulus you are focusing on.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.