# Necklaces, Self-Reciprocal Polynomials, andq-Cycles

Authors: Umarin Pintoptang; Vichian Laohakosol; Suton Tadee
Journal: International Journal of Combinatorics
 (2014)

---

## Abstract

Letn≥2 be a positive integer and q a prime power. Consider necklaces consisting of n beads, each of which has one of the given q colors. A primitive Cn-orbit is an equivalence class of n necklaces closed under rotation. A Cn-orbit is self-complementary when it is closed under an assigned color matching. In the work of Miller (1978), it is shown that there is a 1-1 correspondence between the set of primitive, self-complementary Cn-orbits and that of self-reciprocal irreducible monic (srim) polynomials of degree n. Let N be a positive integer relatively prime to q. A q-cycle mod N is a finite sequence of nonnegative integers closed under multiplication by q. In the work of Wan (2003), it is shown that q-cycles mod N are closely related to monic irreducible divisors of xN-1∈Fq[x]. Here, we show that: (1) q-cycles can be used to obtain information about srim polynomials; (2) there are correspondences among certain q-cycles and Cn-orbits; (3) there are alternative proofs of Miller's results in the work of Miller (1978) based on the use of q-cycles.


---

## Body

## 1. Introduction

### 1.1. Necklaces

Letn∈N, n≥2, and let q be a prime power. Consider the set
(1)ηn,q=c0,c1,…,cn-1;ci∈0,1,…,q-1
of all necklaces (or seating arrangements) consisting of n beads, each of which is colored with one of q colors denoted by 0,1,…,q-1. Clearly, |η(n,q)|=qn. Partition the colors into [q/2] pairs with one extra color if q is odd. Two colors in the same pair are calledcomplementary, and if q is odd the extra color is calledself-complementary. The complement of color c is so arranged as the color q-1-c. Let
(2)Cn=e∶=r0,r,r2,…,rn-1
be the cyclic group of order n; the group Cn acts on η(n,q) via rk(k∈{0,1,…,n-1}) rotating each bead k-times. Let H={e,h} be the group which acts on η(n,q) via e, the identity, preserving each color and h replacing each color by its complement. Each equivalence class of elements in η(n,q) under the action of Cn is called a Cn-orbit. For a Cn-orbit O, the element h(O) is an equivalence class derived from O through the action h∈H. A Cn-orbit O is called aself-complementary if it is invariant under H; that is, O=h(O). The remaining Cn-orbits fall into pairs {O,h(O)} calledcomplementary pairs. A necklace in η(n,q) is calledprimitive if its Cn-orbit has cardinality n.


### 1.2. Self-Reciprocal, Irreducible, Monic Polynomials

LetFq denote the finite field of q elements. The reciprocal polynomial f* of
(3)fx=anxn+an-1xn-1+⋯+a1x+a0∈Fqx,an≠0
is defined by
(4)f*x=xnf1x=a0xn+a1xn-1+⋯+an-1x+an.
A polynomial f∈Fq[x] is calledself-reciprocal if f(x)=f*(x).The following characterization is well known.Proposition 1 (see [1, page 275]).
Letf∈Fq[x] be irreducible and monic of degree ≥2. Then f is self-reciprocal if and only if its set of roots (each of which is evidently nonzero) is closed under inversion (and so its degree must be even).We are interested here inself-reciprocal, irreducible, monic (srim) polynomials in Fq[x]. Since there is only one first degree srim-polynomial, namely, x+1, from now on we treat only srim-polynomials of even degree ≥2.Letα be a generator (primitive element) of the group Fqn* and let f(x)∈Fq[x] be an irreducible monic polynomial of degree n. It is well known [2, Theorem 2.14] that all distinct roots of f(x) are of the form
(5)αk,αqk,αq2k,…,αqn-1k
for some integer 0≤k≤qn-1. Let
(6)k=∑i=0n-1‍eiqi∶=e0,e1,…,en-1,0≤ei≤q-1i=0,1,…,n-1
be its base q expansion. For an irreducible, monic f(x)∈Fq[x] of degree n, we associate a Cn-orbit containing the necklace k∶=e0,e1,…,en-1.


### 1.3.q-Cycles

LetN be a fixed positive integer relatively prime to q. Let a0,a1,…,al-1 be ldistinct numbers chosen from ZN∶={0,1,…,N-1}. If
(7)aiq≡ai+1mod⁡Ni=0,1,…,l-2a0ql≡al-1q≡a0mod⁡N,
then we say that a0,a1,…,al-1 forms a q-cyclemod⁡N with leading element a0, and call l thelength of this q-cycle. The notion of q-cycles was introduced by Wan in his book [3, page 203]. Since qoN(q)≡1mod⁡N, where oN(q) is the order of q in ZN*∶=ZN∖{0} (the multiplicative group of nonzero integers modulo N), it clearly follows that each q-cycle always has a unique length l which is the least positive integer l for which a≡aqlmod⁡N. The concept of q-cycles is important because of the following connections with irreducible polynomials in Fq[x] [3, Theorem 9.11].Letα be a primitive Nth root of unity (if the order of q in ZN* is m, then there exists a primitive Nth root of unity in Fqm). If a0,a1,…,al-1 is a q-cycle, then
(8)hx=x-αa0x-αa1⋯x-αal-1
is a monic irreducible factor of xN-1 in Fq[x].Conversely, ifh(x) is a monic irreducible factor of xN-1 in Fq[x], then all the roots of h(x) are powers of α whose exponents form a q-cycle.We henceforth refer to these two facts as the cycle-polynomial correspondence.


## 1.1. Necklaces

Letn∈N, n≥2, and let q be a prime power. Consider the set
(1)ηn,q=c0,c1,…,cn-1;ci∈0,1,…,q-1
of all necklaces (or seating arrangements) consisting of n beads, each of which is colored with one of q colors denoted by 0,1,…,q-1. Clearly, |η(n,q)|=qn. Partition the colors into [q/2] pairs with one extra color if q is odd. Two colors in the same pair are calledcomplementary, and if q is odd the extra color is calledself-complementary. The complement of color c is so arranged as the color q-1-c. Let
(2)Cn=e∶=r0,r,r2,…,rn-1
be the cyclic group of order n; the group Cn acts on η(n,q) via rk(k∈{0,1,…,n-1}) rotating each bead k-times. Let H={e,h} be the group which acts on η(n,q) via e, the identity, preserving each color and h replacing each color by its complement. Each equivalence class of elements in η(n,q) under the action of Cn is called a Cn-orbit. For a Cn-orbit O, the element h(O) is an equivalence class derived from O through the action h∈H. A Cn-orbit O is called aself-complementary if it is invariant under H; that is, O=h(O). The remaining Cn-orbits fall into pairs {O,h(O)} calledcomplementary pairs. A necklace in η(n,q) is calledprimitive if its Cn-orbit has cardinality n.


## 1.2. Self-Reciprocal, Irreducible, Monic Polynomials

LetFq denote the finite field of q elements. The reciprocal polynomial f* of
(3)fx=anxn+an-1xn-1+⋯+a1x+a0∈Fqx,an≠0
is defined by
(4)f*x=xnf1x=a0xn+a1xn-1+⋯+an-1x+an.
A polynomial f∈Fq[x] is calledself-reciprocal if f(x)=f*(x).The following characterization is well known.Proposition 1 (see [1, page 275]).
Letf∈Fq[x] be irreducible and monic of degree ≥2. Then f is self-reciprocal if and only if its set of roots (each of which is evidently nonzero) is closed under inversion (and so its degree must be even).We are interested here inself-reciprocal, irreducible, monic (srim) polynomials in Fq[x]. Since there is only one first degree srim-polynomial, namely, x+1, from now on we treat only srim-polynomials of even degree ≥2.Letα be a generator (primitive element) of the group Fqn* and let f(x)∈Fq[x] be an irreducible monic polynomial of degree n. It is well known [2, Theorem 2.14] that all distinct roots of f(x) are of the form
(5)αk,αqk,αq2k,…,αqn-1k
for some integer 0≤k≤qn-1. Let
(6)k=∑i=0n-1‍eiqi∶=e0,e1,…,en-1,0≤ei≤q-1i=0,1,…,n-1
be its base q expansion. For an irreducible, monic f(x)∈Fq[x] of degree n, we associate a Cn-orbit containing the necklace k∶=e0,e1,…,en-1.


## 1.3.q-Cycles

LetN be a fixed positive integer relatively prime to q. Let a0,a1,…,al-1 be ldistinct numbers chosen from ZN∶={0,1,…,N-1}. If
(7)aiq≡ai+1mod⁡Ni=0,1,…,l-2a0ql≡al-1q≡a0mod⁡N,
then we say that a0,a1,…,al-1 forms a q-cyclemod⁡N with leading element a0, and call l thelength of this q-cycle. The notion of q-cycles was introduced by Wan in his book [3, page 203]. Since qoN(q)≡1mod⁡N, where oN(q) is the order of q in ZN*∶=ZN∖{0} (the multiplicative group of nonzero integers modulo N), it clearly follows that each q-cycle always has a unique length l which is the least positive integer l for which a≡aqlmod⁡N. The concept of q-cycles is important because of the following connections with irreducible polynomials in Fq[x] [3, Theorem 9.11].Letα be a primitive Nth root of unity (if the order of q in ZN* is m, then there exists a primitive Nth root of unity in Fqm). If a0,a1,…,al-1 is a q-cycle, then
(8)hx=x-αa0x-αa1⋯x-αal-1
is a monic irreducible factor of xN-1 in Fq[x].Conversely, ifh(x) is a monic irreducible factor of xN-1 in Fq[x], then all the roots of h(x) are powers of α whose exponents form a q-cycle.We henceforth refer to these two facts as the cycle-polynomial correspondence.


## 2. Connection betweenq-Cycles and Irreducible Polynomials

We start with a basic result.Lemma 2.
LetN=N1>N2>⋯>Nd=1 be all the (positive integer) divisors of N. (i)
Ifb∈ZN is such that gcd(b,N)=Nr for some r∈{1,…,d}, then each q-cycle mod⁡N with leading element b has length oN/Nr(q).(ii)
The polynomialf∈Fq[x] constructed via (8) from a q-cycle with leading element b, gcd(b,N)=Nr(r∈{1,…,d}), is a monic irreducible polynomial with f(0)≠0, and deg⁡(f)=oN/Nr(q).(iii)
Each irreducible polynomialf∈Fq[x] with f(0)≠0, and deg⁡(f)=oNr(q) is an irreducible factor of xN-1 arising, through (8), from a q-cycle with leading element b, gcd(b,N)=N/Nr.Proof.
(i) Note from the definition ofq-cycle that a q-cycle mod⁡N, with leading element b and gcd(b,N)=Nr, has length l if and only if N/Nr divides ql-1 but does not divide q-1,q2-1,…,ql-1-1 (if l=1, only the first divisibility needs to be considered). This defining condition of l is indeed the meaning of oN/Nr(q).
(ii)-(iii) From part (i), eachq-cycle mod⁡N with leading element b, gcd(b,N)=Nr, has length oN/Nr(q). Through the cycle-polynomial correspondence, such a q-cycle gives rise to a monic irreducible f∈Fq[x], f(0)≠0, of degree oN/Nr(q) and conversely.By Lemma2(i), a q-cycle mod⁡qm+1 with leading element b=1 has length oqm+1(q). Since q2m≡1mod⁡qm+1, we have oqm+1q∣2m. From the observation that oqm+1(q)>m, we immediately obtain oqm+1(q)=2m, and hence, a q-cycle mod⁡qm+1 with leading element b=1 has length 2m.The caseN=qm+1 is of particular interest for it shows that q-cycles are closely related to srim-polynomials.Theorem 3.
Letm∈N. Then each q-cycle mod⁡qm+1 of length 2m gives rise through the cycle-polynomial correspondence to a srim-polynomial in Fq[x] of degree 2m and conversely.Proof.
Let(a=a0,…,a2m-1) be a q-cycle mod⁡qm+1 of length 2m. By Lemma 2, this q-cycle gives rise, through (8), to a monic irreducible polynomial in Fq[x] of degree 2m and conversely. There remains only to check that such polynomial is self-reciprocal, that is, to check that, for α being a primitive (qm+1)th root of unity, the set {αa,αqa,…,αaq2m-1} is closed under inversion. Let gcd(a,qm+1)=g. Putting a=gb, where b∈N, is such that gcd(b,qm+1)=1. Since αb is also a primitive (qm+1)th root of unity, it suffices to treat only the case a=g. The assertion that the set {αa,αqa,…,αaq2m-1} is closed under inversion is immediate from αqm=α-1 and the observation that α-gqj=αgqm+j for j∈{0,1,…,m-1}.


## 3. Connection between Necklaces andq-Cycles

We start with a characterization of primitive necklaces. In the proof of our next theorem, we make use of a 1-1 correspondence between a necklace(d0,d1,…,dn-1) and a base q representation of the form d0+d1q+⋯+dn-1qn-1.Theorem 4.
Letc0,c1,…,cn-1 be a primitive necklace in a Cn-orbit. Then this Cn-orbit is self-complementary if and only if there exists s∈{0,1,…,n-1} such that
(9)cs+jmod⁡n+cjmod⁡n=q-1∀j∈0,1,…,n-1.Proof.
TheCn-orbit containing a primitive necklace c0,c1,…,cn-1 is of the form
(10)O=c0,c1,…,cn-1,c1,c2,…,cn-1,c0,c2,c3,…,cn-1,c0,c1,…,cn-1,c0,c1,…,cn-2,
where all the necklaces in O are distinct. From the 1-1 correspondence mentioned above, the base q representations of the elements in O are
(11)L0~c0+c1q+⋯+cn-1qn-1,L1~c1+c2q+⋯+cn-1qn-2+c0qn-1,L2~c2+c3q+⋯+c0qn-2+c1qn-1,…,Ln-1~cn-1+c0q+c1q2+⋯+cn-2qn-1.
From the definition, O is self-complementary if and only if
(12)L0,L1,…,Ln-1=hL0,hL1,…,hLn-1,
where
(13)hL0~q-1-c0+q-1-c1q+⋯+q-1-cn-1qn-1hL1~q-1-c1+q-1-c2q+⋯+q-1-cn-1qn-2+q-1-c0qn-1hL2~q-1-c2+q-1-c3q+⋯+q-1-c0qn-2+q-1-c1qn-1⋮hLn-1~q-1-cn-1+q-1-c0q+q-1-c1q2+⋯+q-1-cn-2qn-1.
If O is self-complementary, then there exists s∈{0,1,…,n-1} such that Ls=h(L0); that is,
(14)cs+cs+1q+⋯+cs+n-s-1qn-s-1+c0qn-s+c1qn-s+1+⋯+cs-1qn-s+s-1=(q-1-c0)+(q-1-c1)q+⋯+q-1-cn-1qn-1,
yielding
(15)cs=q-1-c0,cs+1=q-1-c1,…,cs+n-s-1=q-1-cn-s-1,c0=q-1-cn-s,c1=q-1-cn-s-1,…,cs-1=q-1-cn-1,
which is (9). On the other hand, if (9) holds, reversing the above steps and appealing to the action of rk, we see that O is self-complementary.By the proof of Lemma2(i), a q-cycle mod⁡qn-1 with leading element b=1 has length n. The case N=qn-1 shows that q-cycles are related to Cn-orbits containing a primitive necklace.Leta0,a1,…,an-1 be a q-cycle mod⁡qn-1 of length n. Then a0,a1,…,an-1 are n distinct numbers in {0,1,…,qn-2} satisfying
(16)aiq≡ai+1mod⁡qn-1i=0,1,…,n-2(a0qn)≡an-1q≡a0mod⁡qn-1.
Writing with respect to base q representation, we have
(17)a0∶=e0+e1q+⋯+en-1qn-1,0≤ei≤q-1i=0,1,…,n-1,
and associate with a0 the necklace e0,e1,…,en-1. Working mod⁡qn-1, we get
(18)a1=qa0=e0q+e1q2+⋯+en-2qn-1+en-1,
showing that the necklace associated with a1 is en-1,e0,e1,…,en-2. Proceeding in the same manner, we see that the necklace associated with aj(j=0,1,…,n-1) is
(19)en-jmod⁡n,en-j+1mod⁡n,…,en-j-1mod⁡n.
Since a0,a1,…,an-1 are distinct, the necklaces associated with each ai are distinct, and so the necklace e0,e1,…,en-1 is primitive. The above steps can evidently be reversed and we have thus proved.Theorem 5.
Forn∈N, there is a 1-1 correspondence between the set of q-cycles mod⁡qn-1 of length n and the set of Cn-orbits containing a primitive necklace.We proceed next to consider self-complemantary orbits andq-cycles. Let b0,b1,…,b2m-1 be a q-cycle mod⁡qm+1 of length 2m so that
(20)biq≡bi+1mod⁡qm+1i=0,1,…,2m-2.
By Theorem 3, the polynomial
(21)h(x)=x-βb0x-βb1⋯x-βb2m-1
is a srim-polynomial of degree 2m over Fq, where β is a primitive (qm+1)th root of unity. Let α be a primitive (q2m-1)th root of unity. Then we may take
(22)β=αqm-1.
Writing b0∈Zqm+1 with respect to base q representation, we get
(23)b0=f0+f1q+⋯+fm-1qm-1orb0=qm.
Now working mod⁡q2m-1, we have either
(24)qm-1b0≡f0qm+f1qm+1+⋯+fm-1q2m-1-f0-f1q-⋯-fm-1qm-1mod⁡q2m-1≡q-f0+q-1-f1q+⋯+q-1-fm-1qm-1+(f0-1)qm+f1qm+1+⋯+fm-1q2m-1mod⁡q2m-1,
provided f0≠0 (if f0=0, the above congruences can be adjusted accordingly), or
(25)qm-1b0=qm-1qm≡q-1qm+q-1qm+1+⋯+(q-1)q2m-1mod⁡q2m-1.
Letting
(26)a0∶=e0+e1q+⋯+em-1qm-1+emqm+em+1qm+1+⋯+e2m-1q2m-1
be the right-hand expression in (24) or (25), we see that
(27)q-1=e0+em=e1+em+1=⋯=em-1+e2m-1;
that is, the relation (9) holds with n=2m, r=m+1. Proceeding in the same manner, we see that the digits in (qm-1)bj∶=aj also satisfy the relation (9). Theorem 4 shows then that (a0,a1,…,a2m-1) represents a primitive necklace in a self-complementary C2m-orbit.Conversely, given a self-complementaryC2m-orbit containing a primitive necklace a0,a1,…,a2m-1 whose first element is of the form (26), being self-complementary, we may assume without loss of generality that the digits in the first element are so arranged that the relations in (27) hold. Reversing the arguments, we get a q-cycle mod⁡qm+1 of length 2m of the form b0,b1,…,b2m-1, where (qm-1)bj=aj(j=0,1,…,2m-1). We have thus proved.Theorem 6.
Form∈N, there is a 1-1 correspondence between the set of q-cycles mod⁡qm+1 of length 2m and the set of self-complementary C2m-orbits containing a primitive necklace.An immediate consequence of Theorem6 is the following result of Miller [4] mentioned in the introduction.Corollary 7.
Form∈N, there is a 1-1 correspondence between the set of self-complementary C2m-orbits containing a primitive necklace and the set of srim polynomials of degree 2m.Proof.
From the cycle-polynomial correspondence, eachq-cycle mod⁡qm+1 of length 2m gives rise, through (21), to a srim-polynomial of degree 2m and conversely. The corollary follows at once from Theorem 6.



---

*Source: 593749-2014-11-09.xml*