Cyclic Equalizability Characterized by Parikh Vectors Sarunyu Thongjarast∗1 , Sarit Pasiphol†2 , and Suthee Ruangwises‡2 1
arXiv:2604.19504v1 [math.CO] 21 Apr 2026
2
Massachusetts Institute of Technology, Cambridge, MA, USA Department of Computer Engineering, Faculty of Engineering, Chulalongkorn University, Bangkok, Thailand
Abstract Cyclic equalizability is a notion introduced by Shinagawa and Nuida in 2025, in the study of card-based cryptography. Informally, a collection of words is cyclically equalizable if, by inserting the same letters at the same positions in all words, they can be transformed into words that are cyclic shifts of one another. Shinagawa and Nuida showed that two binary words of equal length are cyclically equalizable if and only if they have the same Hamming weight. They also posed the problem of characterizing cyclic equalizability over larger alphabets. In this paper, we completely characterize cyclic equalizability for two words over an arbitrary finite alphabet by proving that two words are cyclically equalizable if and only if they have the same Parikh vector. Keywords: combinatorics on words, cyclic equalizability, Parikh vector, Abelian equivalence, card-based cryptography
1
Introduction
Card-based cryptography is a research area that studies how to perform secure computation using a deck of physical cards. Since the seminal five-card trick of den Boer [1] in 1990, this field has developed a rich theory connecting combinatorics, algebra, and computation [2, 7]. In recent years, new connections have emerged between card-based protocols and combinatorics on words, suggesting that structural properties of words can play a fundamental role in understanding such protocols. A central operation in card-based cryptography is the random cut, which cyclically shifts a sequence of face-down cards by an unknown offset. As a result, sequences that differ only by a cyclic shift become indistinguishable. This naturally leads to the notion of cyclic equivalence (also known as conjugacy) of words, which has been extensively studied in combinatorics on words [3, 4, 5]. Motivated by this observation, Shinagawa and Nuida [9] introduced the notion of cyclic equalizability in 2025. Informally, a collection of words is cyclically equalizable if, by inserting the same letters at the same positions in all words, they can be transformed into words that are cyclic shifts of one another. This notion arises naturally in the analysis of ∗
[email protected] [email protected] ‡ [email protected] †
1
card-based protocols, where inserting letters corresponds to inserting additional cards to the sequence without revealing the existing cards. For binary words of equal length, Shinagawa and Nuida showed that cyclic equalizability admits a simple characterization: two words are cyclically equalizable if and only if they have the same Hamming weight. They also posed several open problems, including characterizing cyclic equalizability for words over larger alphabets such as {0, 1, 2} (and more generally, over arbitrary finite alphabets). In combinatorics on words, the Parikh vector of a word records the number of occurrences of each letter. Two words are said to be Abelian equivalent if they have the same Parikh vector, i.e. if they are permutations of each other. Related notions have been studied in combinatorics on words, including conjugacy and other structural properties of words under insertion operations [6], and subword counting in circular words (conjugacy classes) [8].
1.1
Our Contribution
In this paper, we completely characterize cyclic equalizability for two words over an arbitrary finite alphabet. In particular, we prove that two words over a finite alphabet are cyclically equalizable if and only if they have the same Parikh vector. As an immediate consequence, we obtain a new interpretation of cyclic equalizability in terms of Abelian equivalence. Our result strictly generalizes the binary case of Shinagawa and Nuida [9], and resolves their question for the ternary alphabet as a special case. Also, the result has implications for card-based cryptography: it characterizes when two encodings can be made indistinguishable under random cuts by inserting additional cards.
2
Preliminaries
Let Σ be a finite alphabet. A word over Σ is a finite sequence of letters from Σ. The set of all words over Σ is denoted by Σ∗ , and the empty word is denoted by ε. For a word w ∈ Σ∗ , its length is denoted by |w|. If w = a0 a1 · · · an−1 , where ai ∈ Σ, then |w| = n.
2.1
Parikh Vectors and Abelian Equivalence
For a letter a ∈ Σ, let |w|a denote the number of occurrences of a in a word w. The Parikh vector of a word w ∈ Σ∗ is the vector Ψ(w) = (|w|a )a∈Σ . Two words u, v ∈ Σ∗ are said to be Abelian equivalent if Ψ(u) = Ψ(v), i.e. if they contain the same number of occurrences of each letter. Equivalently, two words are Abelian equivalent if one is a permutation of the other.
2.2
Cyclic Equivalence
Let w = a0 a1 · · · an−1 ∈ Σn with n ≥ 1. For an integer r ∈ Zn , the cyclic shift of w by r positions is the word w(r) = ar ar+1 · · · an−1 a0 a1 · · · ar−1 , 2
where the indices are taken modulo n. Two words u, v ∈ Σ∗ of equal length are said to be cyclically equivalent (or conjugate), denoted by u ∼ v, if v = u(r) for some integer r. We also call such r an offset of u and v.
2.3
Simultaneous Insertion
Let k ≥ 2 and let w1 , . . . , wk ∈ Σn be words of equal length n. A simultaneous insertion is an operation that transforms each word wi = ai,0 ai,1 · · · ai,n−1 into the word u0 ai,0 u1 ai,1 · · · un−1 ai,n−1 un , where each uj is a word in Σ∗ . In other words, we insert the same strings at the same positions in all words. For example, if k = 3, w1 = 121, w2 = 334, w3 = 135, and we insert u0 = 14, u1 = 5, u2 = ε (an empty string), u3 = 56, then w1 , w2 , and w3 become 14152156,
14353456,
and
14153556,
respectively, where the bold underlined letters indicate the inserted letters.
2.4
Cyclic Equalizability
We now define the central notion studied in this paper. Let k ≥ 2 and let w1 , . . . , wk ∈ Σ∗ be words of equal length. We say these words are cyclically equalizable if there exist words w1′ , . . . , wk′ ∈ Σ∗ such that 1. Each wi′ is obtained from wi by a simultaneous insertion, and 2. The words w1′ , . . . , wk′ are cyclically equivalent. For example, the words 123 and 132 are cyclically equalizable, since they can be transformed into 1213 and 1312, where the bold underlined letters indicate the inserted letters. The transformed words are cyclically equivalent. Similarly, the words 12344 and 42431 are cyclically equalizable, since they can be transformed into cyclically equivalent words 123124424
and
424123124,
where the inserted letters are again shown in bold and underlined.
3
Known Properties of Cyclic Equalizability
In this section, we review basic properties of cyclic equalizability established by Shinagawa and Nuida [9]. The following theorem shows that cyclic equalizability is invariant under simultaneous insertions. 3
Theorem 1 ([9, Theorem 1]). Let w1 , . . . , wk ∈ Σ∗ be words of equal length, and let w1′ , . . . , wk′ be the words obtained from them by a simultaneous insertion. Then, w1 , . . . , wk are cyclically equalizable if and only if w1′ , . . . , wk′ are cyclically equalizable. The next theorem gives a complete characterization of cyclic equalizability for two binary words. Theorem 2 ([9, Theorem 2]). Let u, v ∈ {0, 1}∗ be binary words of equal length. Then, u and v are cyclically equalizable if and only if |u|1 = |v|1 .
4
Cyclic Equalizability of Two Words
In this section, we prove a complete characterization of cyclic equalizability for two words over an arbitrary finite alphabet. Theorem 3. Let Σ be a finite alphabet and let u, v ∈ Σ∗ be words of equal length. Then, u and v are cyclically equalizable if and only if they have the same Parikh vector. We first prove the necessity. Suppose u and v are cyclically equalizable. Simultaneous insertions add the same letters to both words at each step, and hence preserve Abelian equivalence. Since cyclically equivalent words are Abelian equivalent, it follows that the original words u and v are also Abelian equivalent. It remains to prove the sufficiency, namely that if two words u, v ∈ Σ∗ have the same Parikh vector, then they are cyclically equalizable.
4.1
Reduction to Distinct Letters and Normalization
We begin with a sequence of reductions that simplify the problem so that it suffices to prove when u = 0 1 · · · (n−1) and v = π(0) π(1) · · · π(n−1) for an arbitrary permutation π ∈ Sn . Lemma 1. It suffices to prove the statement for words in which all letters are pairwise distinct. Proof. Suppose u and v are words of size n with the same Parikh vector. For each letter x ∈ Σ appearing k ≥ 2 times in u (and hence also in v), replace its occurrences by k distinct letters x1 , . . . , xk arbitrarily. Perform this replacement in both u and v for every letter appearing multiple times. For instance, u = acbcac and v = cbaacc become ũ = a1 c1 bc2 a2 c3
and ṽ = c1 ba1 a2 c2 c3 .
This yields two new words ũ, ṽ of length n over a larger alphabet, in which all letters are pairwise distinct. By construction, ũ and ṽ are permutations of each other. If ũ and ṽ are cyclically equalizable, then identifying all letters a1 , . . . , ak back to a shows that u and v are cyclically equalizable. Therefore, it suffices to consider only the case where all letters are distinct. By Lemma 1, we may assume that u and v consist of n distinct letters. Relabel the alphabet so that the letters of u are 0, 1, . . . , n − 1 in this order. Since v is a permutation of the same letters, it can be written as π(0)π(1) · · · π(n − 1) for some permutation π ∈ Sn . Since cyclic equalizability is invariant under relabeling of the alphabet, we obtain the following normalization. 4
Corollary 1. It suffices to consider the case where u = 0 1 · · · (n − 1)
and
v = π(0) π(1) · · · π(n − 1)
for an arbitrary permutation π ∈ Sn .
4.2
Useful Lemmas
We present two lemmas that will be used in our construction in the next two subsections. The first lemma shows that cyclic equivalence is preserved under reading a word with a step size that is coprime with the length. Definition 1. Let w = a0 a1 · · · an−1 ∈ Σn and let p be an integer such that gcd(p, n) = 1, define the reading with step size p of w to be the word Rp (w) = a0 ap a2p · · · a(n−1)p , where the indices are taken modulo n. Lemma 2. Let u, v ∈ Σn and let p be an integer such that gcd(p, n) = 1. If Rp (u) and Rp (v) are cyclically equivalent with offset d, then u and v are cyclically equivalent with offset dp. Proof. Let u = a0 a1 · · · an−1 and v = b0 b1 · · · bn−1 . Define a map φ : Zn → Zn by φ(i) = ip (mod n) for every i ∈ Zn . Since gcd(n, p) = 1, the map φ is a permutation of Zn . We have Rp (u) = aφ(0) aφ(1) · · · aφ(n−1)
and
Rp (v) = bφ(0) bφ(1) · · · bφ(n−1) .
Suppose Rp (u) and Rp (v) are cyclically equivalent with offset d. Then, bφ(i) = aφ(i+d) for every i ∈ Zn . Since φ(i + d) ≡ (i + d)p ≡ ip + dp ≡ φ(i) + dp
(mod n),
it follows that bφ(i) = aφ(i)+dp for every i ∈ Zn , where the indices are taken modulo n. Since φ is a permutation of Zn , this implies bj = aj+dp for every j ∈ Zn . Hence, u and v are cyclically equivalent with offset dp. The next lemma shows that cyclic equivalence is preserved under columnwise interleaving, provided that all component words have the same length and offset. Definition 2. Let w1 , . . . , wm ∈ Σn be words of equal length n, where wi = wi,0 wi,1 · · · wi,n−1 for each i = 1, 2, . . . , m. Define the columnwise interleaved word of w1 , . . . , wm to be the word I(w1 , · · · , wm ) = w1,0 w2,0 · · · wm,0 w1,1 w2,1 · · · wm,1 · · · w1,n−1 w2,n−1 · · · wm,n−1 . Lemma 3. Let u1 , . . . , um , v1 , . . . , vm ∈ Σn be words of equal length n, where ui = ui,0 ui,1 · · · ui,n−1 and vi = vi,0 vi,1 · · · vi,n−1 for each i = 1, 2, . . . , m. Suppose for every i ∈ {1, . . . , m}, the word vi is a cyclic shift of ui by the same offset δ, i.e. vi,j = ui,j+δ for all j ∈ Zn , where j + δ is taken modulo n. Then, the words U = I(u1 , · · · , um ) and V = I(v1 , · · · , vm ) are cyclically equivalent. 5
Proof. Let U = a0 a1 · · · amn−1 and V = b0 b1 · · · bmn−1 . Under the linear indexing, the letter ui,j (resp. vi,j ) occurs in U (resp. V ) at position mj + (i − 1), i.e. amj+(i−1) = ui,j and bmj+(i−1) = vi,j for every i ∈ {1, . . . , m} and j ∈ Zn . By assumption, vi,j = ui,j+δ for every i, j. Therefore, the letter at position mj + (i − 1) in V is equal to the letter at position m(j + δ) + (i − 1) (mod mn) in U . Since m(j + δ) + (i − 1) ≡ mj + (i − 1) + mδ
(mod mn),
it follows that at = bt+mδ for every t ∈ Zmn , where the indices are taken modulo mn. Hence, U and V are cyclically equivalent.
4.3
Construction for Single-Cycle Case
Recall that u = 0 1 · · · (n − 1) and v = π(0) π(1) · · · π(n − 1). We first consider the case where π ∈ Sn consists of a single cycle. Thus, for each t ∈ Zn , there exists a unique k ∈ Zn such that t = π k (0). We will construct words u′ = u′0 u′1 · · · u′n2 −1 and v ′ = v0′ v1′ · · · vn′ 2 −1 such that 1. u′ and v ′ can be obtained from u and v, respectively, by a simultaneous insertion, and 2. u′ and v ′ are cyclically equivalent with offset n + 1. At a high level, we partition u′ and v ′ into n blocks of n consecutive positions. We perform insertions so that the i-th position of u and v is placed in Block i of u′ and v ′ , for each i ∈ Zn . See Example 1 for an illustration of this construction. 4.3.1
Blocks and Groups
Let p = n + 1. Since gcd(p, n2 ) = 1, we may consider the reading with step size p on words of length n2 . We divide the positions of u′ and v ′ into n consecutive blocks of size n according to their original order, and into n consecutive groups of size n according to their reading order with step size p. Definition 3. We partition the positions in Zn2 into n blocks and n groups. For t, g ∈ Zn : • Block t consists of positions tn, tn + 1, . . . , tn + (n − 1). • Group g consists of positions φ(gn), φ(gn + 1), . . . , φ(gn + n − 1), where φ(i) = ip (mod n2 ) for all i ∈ Zn2 and p = n + 1. Next, we show that each pair of a block and a group uniquely determines a position. Lemma 4. For each t, g ∈ Zn , there exists a unique position in Zn2 , denoted by f (t, g), that lies in Block t and Group g. Moreover, f is a bijection from Z2n to Zn2 . 6
Proof. For any t, g ∈ Zn , let i ≡ t − g (mod n), where i ∈ Zn . We have φ(gn + i) ≡ (gn + i)(n + 1) ≡ gn2 + (g + i)n + i ≡ (g + i)n + i
(mod n2 ).
Therefore,
φ(gn + i) ≡g+i≡t n
(mod n),
so φ(gn + i) lies in Block t. By construction, it also lies in Group g, so such a position exists. For uniqueness, suppose φ(gn + i′ ) also lies in Block t, where i′ ∈ Zn . Then, g + i′ ≡ t (mod n), which implies i′ ≡ t − g ≡ i (mod n) and thus i′ = i. Therefore, the position is unique. Hence, f (t, g) is well-defined. Since blocks partition Zn2 and groups partition Zn2 , distinct pairs (t, g) correspond to distinct positions, so f is injective. As |Z2n | = |Zn2 | = n2 , it follows that f is a bijection. 4.3.2
Filling Strategy
We construct words u′ and v ′ from u and v by a simultaneous insertion so that u′ and v ′ are cyclically equivalent with offset p. For each position i ∈ Zn2 , the letters u′i and vi′ either correspond to original letters uj and vj for some j ∈ Zn , or arise from the inserted letters. We call i a distinguished position in the former case, and a non-distinguished position in the latter case. We first designate exactly n distinguished positions. This determines the letters u′i and vi′ at all distinguished positions. The remaining positions are filled so as to ensure that u′ and v ′ are cyclically equivalent with offset p. 4.3.3
Filling Distinguished Positions
For each k ∈ Zn , we designate f (π k (0), k) to be a distinguished position. At this position, we set the letters u′f (πk (0), k) = π k (0)
and
vf′ (πk (0), k) = π k+1 (0).
Since π 0 (0), π 1 (0), . . . , π n−1 (0) are pairwise distinct, there is exactly one distinguished position in each block (and also exactly one in each group). 4.3.4
Filling Non-Distinguished Positions
We now fill the remaining positions by following the reading order φ(0), φ(1), . . . , φ(n2 − 1), skipping the distinguished positions already filled. ′ For convenience, define ai := u′φ(i) and bi := vφ(i) . Note that the letters a0 and b0 are already filled, since φ(0) = 0 = f (0, 0) is a distinguished position. For each i = 1, 2, . . . , n2 − 1, if φ(i) is a non-distinguished position, we set ai = bi−1
and
bi = bi−1 .
Lemma 5. The words Rp (u′ ) and Rp (v ′ ) are cyclically equivalent with offset 1. 7
Proof. Note that Rp (u′ ) = a0 , a1 , · · · , an2 −1 and Rp (v ′ ) = b0 , b1 , · · · , bn2 −1 . We claim that bi = ai+1 for every i ∈ Zn2 , where the indices are taken modulo n2 . First, if φ(i + 1) is a non-distinguished position, then by construction ai+1 = bi , so the claim holds. Now suppose φ(i + 1) is distinguished. Let it belong to Block t and Group g. By construction, we have t = π g (0) and φ(i + 1) = f (t, g) = f (π g (0), g). Also, ai+1 = u′φ(i+1) = π g (0). Case 1: g > 0. Consider the maximum value j such that j < i + 1 and φ(j) is distinguished. Since each group contains exactly one distinguished index, φ(j) must be in Group g − 1. Also, all of φ(j + 1), φ(j + 2), . . . , φ(i) must be non-distinguished. ′ By construction, we have φ(j) = f (π g−1 (0), g−1) and bj = vφ(j) = π g (0). Furthermore, since φ(j +1), φ(j +2), . . . , φ(i) are non-distinguished, we have bi = bi−1 = · · · = bj = π g (0). Hence, ai+1 = bi . Case 2: g = 0. We have φ(i + 1) = 0, so i = n2 − 1 and ai+1 = 0. Consider the maximum value j ∈ Zn2 such that φ(j) is distinguished. Since each group contains exactly one distinguished index, φ(j) must be in Group n − 1. Also, all of φ(j + 1), φ(j + 2), . . . , φ(n2 − 1) must be non-distinguished. ′ By construction, we have φ(j) = f (π n−1 (0), n − 1) and bj = vφ(j) = π n (0) = 0. Furthermore, since φ(j + 1), φ(j + 2), . . . , φ(n2 − 1) are non-distinguished, we have bi = bn2 −1 = bn2 −2 = · · · = bj = 0. Hence, ai+1 = bi . Therefore, Rp (u′ ) and Rp (v ′ ) are cyclically equivalent with offset 1. From Lemma 2, we can conclude that u′ and v ′ are cyclically equivalent with offset p. Lemma 6. The words u′ and v ′ can be obtained from u and v, respectively, by a simultaneous insertion. Proof. For each Block t, let k be the unique integer in Zn such that t = π k (0). Then, the distinguished position in Block t is f (t, k), and at that position we have u′f (t,k) = t
vf′ (t,k) = π(t).
and
Also, if i ∈ Zn2 is a non-distinguished position, then u′i = vi′ . Therefore, if we keep only the distinguished positions, and delete all other positions, from u′ we obtain 0 1 · · · (n − 1) = u, while from v ′ we obtain π(0) π(1) · · · π(n − 1) = v. Since the same letters are deleted in both words, u′ and v ′ can be obtained from u and v, respectively, by a simultaneous insertion. From Lemmas 2, 5 and 6, we now obtain the desired conclusion for the single-cycle case. Theorem 4. If π ∈ Sn consists of a single cycle, then the words u = 0 1 · · · (n − 1)
and
v = π(0) π(1) · · · π(n − 1)
are cyclically equalizable. 8
Example 1. Let n = 5, u = 01234, and v = 30421. We have π(0) = 3, π(1) = 0, π(2) = 4, π(3) = 2, and π(4) = 1, so π = (0 3 2 4 1) is a single cycle. Also, we have φ(i) = 6i (mod 25). Thus, the sequence φ(0), φ(1), . . . , φ(24) is 0, 6, 12, 18, 24, 5, 11, 17, 23, 4, 10, 16, 22, 3, 9, 15, 21, 2, 8, 14, 20, 1, 7, 13, 19, which is the order of reading with step size p = 6. The distinguished positions are f (0, 0) = 0,
f (3, 1) = 17,
f (2, 2) = 10,
f (4, 3) = 21,
f (1, 4) = 7.
Table 1 shows the words Rp (u′ ) and Rp (v ′ ), which are the reading with step size p = 6 of u′ and v ′ , respectively. The positions are divided into five groups of size five. The distinguished positions are shown in bold underlined. One can see that Rp (v ′ ) is a cyclic shift of Rp (u′ ) by one position. Table 2 shows the words u′ and v ′ written in their original order, divided into five blocks of size five. Again, the distinguished positions are shown in bold underlined. Deleting all non-bold entries yields u from u′ and v from v ′ . Table 1: The reading with step size p = 6 of u′ and v ′ , divided into five groups Group 0 (i = 0, 1, . . . , 4) φ(i) 0 6 12 18 24 ai = u′φ(i) 0 3 3 3 3 ′ bi = vφ(i) 3 3 3 3 3 Group 1 (i = 5, 6, . . . , 9) φ(i) 5 11 17 23 4 ai = u′φ(i) 3 3 3 2 2 ′ bi = vφ(i) 3 3 2 2 2 Group 2 (i = 10, 11, . . . , 14) φ(i) 10 16 22 3 9 ai = u′φ(i) 2 4 4 4 4 ′ bi = vφ(i) 4 4 4 4 4 Group 3 (i = 15, 16, . . . , 19) φ(i) 15 21 2 8 14 ai = u′φ(i) 4 4 1 1 1 ′ bi = vφ(i) 4 1 1 1 1 Group 4 (i = 20, 21, . . . , 24) φ(i) 20 1 7 13 19 ai = u′φ(i) 1 1 1 0 0 ′ bi = vφ(i) 1 1 0 0 0
Table 2: The original order of u′ and v ′ , divided into five blocks Block 0 Block 1 Block 2 Block 3 Block 4 i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 u′i 0 1 1 4 2 3 3 1 1 4 2 3 3 0 1 4 4 3 3 0 1 4 4 2 3 vi′ 3 1 1 4 2 3 3 0 1 4 4 3 3 0 1 4 4 2 3 0 1 1 4 2 3
9
4.4
Construction for Multiple-Cycle Case
We now consider the general case where πP ∈ Sn decomposes into m disjoint cycles c1 , . . . , cm of lengths ℓ1 , . . . , ℓm , respectively, where m s=1 ℓs = n. We will apply a modified version of the single-cycle construction to each cycle independently, and then combine the results using columnwise interleaving. 4.4.1
Processing Each Cycle
For each cycle cs (1 ≤ s ≤ m), we will construct words u[s] and v [s] , each of length n2 . We maintain the same block and group structures, as well as the same reading step size p = n + 1, as defined in the single-cycle case. Let π 0 (xs ), π 1 (xs ), . . . , π ℓs −1 (xs ) be the elements of cs , where xs is an element of cs with the minimum value. We assign distinguished positions in u[s] and v [s] similarly to the single-cycle case, but for only ℓs positions. For each k ∈ Zℓs , consider the unique index f (π k (xs ), k). We set the letters [s]
uf (πk (xs ), k) = π k (xs )
and
[s]
vf (πk (xs ), k) = π k+1 (xs ).
These are distinguished positions in u[s] and v [s] . Note that there is at most one distinguished position in each block (and exactly one in each of Groups 0, 1, . . . , ℓs − 1, and none in the remaining groups). Once the ℓs distinguished positions are filled, we fill the remaining n2 − ℓs positions in the same way as the single-cycle case. [s] [s] [s] [s] For convenience, define ai := uφ(i) and bi := vφ(i) . Let q be an index such that [s]
[s]
φ(q) = f (xs , 0). Then, φ(q) is a distinguished position, with aq = xs and bq = π(xs ) already filled. We now fill the remaining positions by following the reading order φ(q + 1), φ(q + 2), . . . , φ(n2 − 1), φ(0), φ(1), . . . , φ(q − 1), skipping the distinguished positions already filled. Specifically, for each i = q + 1, q + 2, . . . , n2 − 1, 0, 1, . . . , q − 1, if φ(i) is a non-distinguished position, we set [s]
[s]
ai = bi−1
and
[s]
[s]
bi = bi−1 .
We have filled both distinguished and non-distinguished positions and obtain sequences u[s] and v [s] of length n2 . Lemma 7. For each cycle cs , the words Rp (u[s] ) and Rp (v [s] ) are cyclically equivalent with offset 1. Proof. The proof is very similar to that of Lemma 5, with the cycle π 0 (0), π 1 (0), . . . , π n−1 (0) [s] [s] [s] replaced by π 0 (xs ), π 1 (xs ), . . . , π ℓs −1 (xs ). First, write Rp (u[s] ) = a0 , a1 , · · · , an2 −1 and [s]
[s]
[s]
[s]
[s]
Rp (v [s] ) = b0 , b1 , · · · , bn2 −1 . We claim that bi = ai+1 for every i ∈ Zn2 , where the indices are taken modulo n2 . [s] [s] If φ(i + 1) is a non-distinguished position, then ai+1 = bi by construction. Now suppose φ(i + 1) is distinguished. Let it belong to Block t and Group g. Then, t = π g (xs ) [s] [s] and φ(i + 1) = f (t, g) = f (π g (xs ), g). Also, ai+1 = uφ(i+1) = π g (xs ). Case 1: g > 0. Consider the maximum j such that j < i + 1 and φ(j) is distinguished. By the same argument as in Case 1 of the proof of Lemma 5, φ(j) is in Group g − 1 and 10
[s]
[s]
[s]
[s]
bj = vφ(j) = π g (xs ). Since φ(j + 1), φ(j + 2), . . . , φ(i) are non-distinguished, we have [s]
[s]
[s]
bi = bi−1 = · · · = bj = π g (xs ). Hence, ai+1 = bi . [s]
Case 2: g = 0. We have φ(i + 1) = φ(q), so i = q − 1 and ai+1 = xs . Consider the maximum j ∈ Zn2 such that φ(j) is distinguished. By the same argument as in Case 2 of [s] [s] the proof of Lemma 5, φ(j) is in Group ℓs − 1 and bj = vφ(j) = xs . Since φ(j + 1), φ(j + [s]
[s]
[s]
2), . . . , φ(n2 −1), φ(0), φ(1), . . . , φ(q−1) are non-distinguished, we have bi = bq−1 = bq−2 = [s]
[s]
[s]
[s]
[s]
[s]
· · · = b0 = bn2 −1 = bn2 −2 = · · · = bj = xs . Hence, ai+1 = bi . Therefore, Rp (u[s] ) and Rp (v [s] ) are cyclically equivalent with offset 1. 4.4.2
Combining All Cycles
After processing all cycles, we obtain m pairs of cyclically equivalent words (u[1] , v [1] ), . . . , (u[m] , v [m] ), all of the same length n2 and with the same offset p. We now apply columnwise interleaving to combine them: u′ = I(u[1] , . . . , u[m] )
and
v ′ = I(v [1] , . . . , v [m] ).
Since all pairs (u[s] , v [s] ) have the same cyclic offset p, Lemma 3 implies that u′ and v ′ are cyclically equivalent. Lemma 8. The words u′ and v ′ can be obtained from u and v, respectively, by a simultaneous insertion. Proof. For each block t, there is a unique cycle cs and a unique integer k ∈ Zℓs such that t = π k (xs ). Therefore, the only sequences having a distinguished position in Block t are u[s] and v [s] . In both sequences, the distinguished position in Block t is f (t, k), and at that position we have [s] [s] uf (t,k) = t and vf (t,k) = π(t). Columnwise interleaving preserves the relative order of positions within each component word, and thus preserves the order of blocks. Also, non-distinguished positions contain the same letters in u′ and v ′ . Therefore, if we keep only the distinguished positions, and delete all other positions, from u′ we obtain 0 1 · · · (n − 1) = u, while from v ′ we obtain π(0) π(1) · · · π(n − 1) = v. Since the same letters are deleted in both words, u′ and v ′ can be obtained from u and v, respectively, by a simultaneous insertion. From Lemmas 2, 3, 7 and 8, we now obtain the desired conclusion for the general case. Theorem 5. For any π ∈ Sn , the words u = 0 1 · · · (n − 1)
and
v = π(0) π(1) · · · π(n − 1)
are cyclically equalizable. 11
Example 2. Let n = 5, u = 01234, and v = 34021. We have π(0) = 3, π(1) = 4, π(2) = 0, π(3) = 2, and π(4) = 1, so π = (0 3 2)(1 4) consists of two cycles. The distinguished positions in u[1] and v [1] are f (0, 0) = 0,
f (3, 1) = 17,
f (2, 2) = 10,
and the distinguished positions in u[2] and v [2] are f (1, 0) = 6,
f (4, 1) = 23.
Table 3 shows the words Rp (u[1] ), Rp (v [1] ), Rp (u[2] ), Rp (v [2] ), which are the reading with step size p = 6 of u[1] , v [1] , u[2] , v [2] , respectively. The distinguished positions are shown in bold underlined. One can see that Rp (v [1] ) (resp. Rp (v [2] )) is a cyclic shift of Rp (u[1] ) (resp. Rp (u[2] )) by one position. Table 4 shows the words u[1] , v [1] , u[2] , v [2] written in their original order. Again, the distinguished positions are shown in bold underlined. Table 3: The reading with step size p = 6 of u[1] , v [1] , u[2] , v [2] Group 0 (i = 0, 1, . . . , 4) φ(i) 0 6 12 18 24 [1] [1] ai = uφ(i) 0 3 3 3 3
Group 0 (i = 0, 1, . . . , 4) φ(i) 0 6 12 18 24 [2] [2] ai = uφ(i) 1 1 4 4 4
[1]
[1]
bi = vφ(i) 1 4 4 4 4 Group 1 (i = 5, 6, . . . , 9) φ(i) 5 11 17 23 4 [2] [2] ai = uφ(i) 4 4 4 4 1
[1]
[1]
bi = vφ(i) 4 4 4 1 1 Group 2 (i = 10, 11, . . . , 14) φ(i) 10 16 22 3 9 [2] [2] ai = uφ(i) 1 1 1 1 1
[1]
[1]
bi = vφ(i) 1 1 1 1 1 Group 3 (i = 15, 16, . . . , 19) φ(i) 15 21 2 8 14 [2] [2] ai = uφ(i) 1 1 1 1 1
[1]
[1]
bi = vφ(i) 1 1 1 1 1 Group 4 (i = 20, 21, . . . , 24) φ(i) 20 1 7 13 19 [2] [2] ai = uφ(i) 1 1 1 1 1
[1]
[1]
bi = vφ(i) 3 3 3 3 3 Group 1 (i = 5, 6, . . . , 9) φ(i) 5 11 17 23 4 [1] [1] ai = uφ(i) 3 3 3 2 2 bi = vφ(i) 3 3 2 2 2 Group 2 (i = 10, 11, . . . , 14) φ(i) 10 16 22 3 9 [1] [1] ai = uφ(i) 2 0 0 0 0 bi = vφ(i) 0 0 0 0 0 Group 3 (i = 15, 16, . . . , 19) φ(i) 15 21 2 8 14 [1] [1] ai = uφ(i) 0 0 0 0 0 bi = vφ(i) 0 0 0 0 0 Group 4 (i = 20, 21, . . . , 24) φ(i) 20 1 7 13 19 [1] [1] ai = uφ(i) 0 0 0 0 0 bi = vφ(i)
0
0
0
0
0
[2]
[2]
[2]
[2]
[2]
[2]
[2]
[2]
[2]
[2]
bi = vφ(i)
12
1
1
1
1
1
Table 4: The original order of u[1] , v [1] , u[2] , v [2] Block 0 Block 1 Block 2 Block 3 Block 4 i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 [1] ui 0 0 0 0 2 3 3 0 0 0 2 3 3 0 0 0 0 3 3 0 0 0 0 2 3 [1] vi 3 0 0 0 2 3 3 0 0 0 0 3 3 0 0 0 0 2 3 0 0 0 0 2 3 Block 0 Block 1 Block 2 Block 3 Block 4 i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 [2] ui 1 1 1 1 1 4 1 1 1 1 1 4 4 1 1 1 1 4 4 1 1 1 1 4 4 [2] vi 1 1 1 1 1 4 4 1 1 1 1 4 4 1 1 1 1 4 4 1 1 1 1 1 4
Finally, we construct columnwise interleaved words u′ = I(u[1] , u[2] ) and v ′ = I(v [1] , v [2] ), each of length 50, that are cyclically equivalent to each other. Deleting all non-bold entries yields u from u′ and v from v ′ . u′ = 01 01 01 01 21 | 34 31 01 01 01 | 21 34 34 01 01 | 01 01 34 34 01 | 01 01 01 24 34, v ′ = 31 01 01 01 21 | 34 34 01 01 01 | 01 34 34 01 01 | 01 01 24 34 01 | 01 01 01 21 34.
5
Consequences and Interpretations
In this section, we discuss immediate consequences of our main theorem and its connections to existing notions in combinatorics on words.
5.1
Algorithmic Implications
The main theorem yields a simple decision procedure for cyclic equalizability: checking whether the Parikh vectors of two words are equal can be done in O(n) time, where n is the length of the words. Moreover, the proof of the main theorem provides a constructive method to transform two Abelian equivalent words into cyclically equivalent words via simultaneous insertions. This yields an explicit algorithm for finding such insertions in O(mn2 ) time, where m is the number of cycles in π.
5.2
Relation to Circular Words
Cyclic equalizability can be viewed as a bridge between Abelian equivalence and cyclic equivalence. Our result shows that, for any two Abelian equivalent words, there exist superwords obtained by inserting letters at the same positions such that the resulting words are conjugate. This provides a link between these two classical notions.
6
Applications to Card-Based Cryptography
We briefly discuss implications of our result for card-based cryptography. In this setting, a sequence of face-down cards can be modeled as a word over a finite alphabet, where each letter represents a type of card. A fundamental operation in many protocols is the random
13
cut, which cyclically shifts the sequence by an unknown offset. Because of this operation, two sequences that differ only by a cyclic shift can be made indistinguishable to all players. Cyclic equalizability was introduced by Shinagawa and Nuida to capture this phenomenon. In their framework, inserting letters corresponds to inserting additional cards into the sequence without revealing the existing cards. Our characterization simplifies the analysis of such protocols. In particular, our main theorem shows that two sequences can be made indistinguishable under random cuts, after inserting additional cards, if and only if they have the same multiset of card types. Our result can also be interpreted as a statement about information erasure. Let S ⊆ Σn be a set of possible inputs, and suppose a sequence of face-down cards X = (x1 , . . . , xn ) ∈ S is given, but its exact value is unknown. A protocol achieves information erasure if, after inserting additional cards and applying a random cut, the distribution of the revealed output does not depend on the choice of X ∈ S. Our result implies that information erasure is always achievable in the case |S| = 2, since any two sequences with the same multiset of cards can be made cyclically indistinguishable by suitable insertions.
7
Open Problems
While this paper provides a complete characterization of cyclic equalizability for two words over arbitrary finite alphabets, several natural questions remain open. • Cyclic equalizability for multiple words. The most immediate open problem is to characterize cyclic equalizability for k ≥ 3 words. In contrast to the two-word case, it is not clear whether equality of Parikh vectors is sufficient when more than two words are involved. Determining necessary and sufficient conditions in this setting remains an important direction for future work. • Minimal insertion length. Given two cyclically equalizable words, what is the minimum number of letters that must be inserted to obtain cyclically equivalent words? Establishing tight bounds or efficient algorithms for this quantity would strengthen the constructive aspect of cyclic equalizability. • Restricted insertions. One may consider variants of cyclic equalizability where insertions are restricted to a fixed subset of the alphabet. Understanding how such restrictions affect the characterization is an interesting problem. Several of these questions were also raised by Shinagawa and Nuida [9], particularly for binary words.
8
Conclusion
In this paper, we studied cyclic equalizability, a notion introduced in the context of cardbased cryptography, from the perspective of combinatorics on words. We established a complete characterization for two words over arbitrary finite alphabets, showing that cyclic equalizability coincides exactly with Abelian equivalence. This result generalizes the previously known characterization for binary words and resolves, as a special case, the question of cyclic equalizability over larger alphabets such as the ternary alphabet. 14
Beyond its theoretical interest, this characterization has implications for the analysis of card-based cryptographic protocols, where cyclic equalizability models the indistinguishability of sequences under card insertions and random cuts. Our result shows that, in the two-sequence case, this indistinguishability is completely determined by the multiset of cards. Acknowledgement The authors would like to thank Kazumasa Shinagawa, Pakawut Jiradilok, Teetat Thamronglak, Weerawat Wongmanit, and Jirapat Tabtimthai for valuable discussions on this research. This work was supported by the 111th Anniversary Engineering Research Catalyst Fund Towards U Top 100.
References [1] B. den Boer. More Efficient Match-Making and Satisfiability: the Five Card Trick. In Proceedings of the Workshop on the Theory and Application of of Cryptographic Techniques (EUROCRYPT ’89), pp. 208–217 (1990). [2] A. Koch and S. Walzer. Foundations for Actively Secure Card-Based Cryptography. In Proceedings of the 10th International Conference on Fun with Algorithms (FUN), pp. 17:1–17:23 (2020). [3] M. Lothaire. Algebraic Combinatorics on Words. Cambridge University Press (2011). [4] M. Lothaire. Applied Combinatorics on Words. Cambridge University Press (2005). [5] M. Lothaire. Combinatorics on Words, 2nd Edition. Cambridge University Press (1997). [6] K. Mahalingam and H. Ravi. Operation Insertion on the Conjugacy and Commutativity of Words. In Proceedings of the 8th International Conference on the Theory and Practice of Natural Computing (TPNC), pp. 70–81 (2019). [7] T. Mizuki and H. Shizuya. A formalization of card-based cryptographic protocols via abstract machine. International Journal of Information Security, 13(1): 15–23 (2014). [8] G. Poovanandran, J. Simpson, and W.C. Teh. Counting subwords in circular words and their Parikh matrices. Theoretical Computer Science, 985: 114344 (2024). [9] K. Shinagawa and K. Nuida. Cyclic Equalizability of Words and Its Application to Card-Based Cryptography. In Proceedings of the 25th International Symposium on Fundamentals of Computation Theory (FCT), pp. 406–419 (2025).
15