Cyclic Equalizability Characterized by Parikh Vectors

arXiv:2604.19504 · math.CO, cs.CR · Submitted 2026-04-21 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: We're looking at the paper: "Cyclic Equalizability Characterized by Parikh Vectors".

Elias: The gist: Two words over an arbitrary finite alphabet are cyclically equalizable if and only if they have the same Parikh vector.

Nadia: First, who's behind it and why it matters.

Paper summary: Nadia: So wrapping up this discussion on "Cyclic Equalizability Characterized by Parikh Vectors," the main thing the authors establish is a complete characterization for two words over arbitrary finite alphabets, proving that cyclic equalizability is exactly equivalent to having the same Parikh vector >

Elias: They started with a simple binary case and showed that this generalizes it, solving their question for larger alphabets like the ternary alphabet as a special instance of their main result >

Priya: What does this mean practically? If two sequences have the same multiset of symbols, they can be made indistinguishable under random cuts after adding extra cards in a card-based system >

Nadia: That’s right. It means for security protocols based on these words, if you want to ensure that information erasure is always possible by just inserting extra elements without revealing the existing ones, all you need to check is if the underlying multisets match >

Elias: The authors used this characterization to show that for two words over arbitrary finite alphabets, cyclic equalizability coincides exactly with Abelian equivalence >

Priya: It seems like a strong result because it moves us from a complex operation definition to a simple count comparison, which is much more tractable for analysis and perhaps even implementation >

Nadia: It definitely does. The focus here isn't on inventing new operations but on precisely defining the boundaries of when these transformations are possible using well-defined counting measures >

Conclusion: Nadia: So this paper, "Cyclic Equalizability Characterized by Parikh Vectors," essentially takes something abstract—this idea of words being transformable into cyclic shifts through insertions—and gives it a very concrete mathematical handle.

Elias: Right, so they’re proving that this property, which Shinagawa and Nuida first looked at for binary words, applies to any alphabet if and only if the words have the exact same Parikh vector.

Priya: I'm thinking about what that means for real data structures; it sounds like instead of needing complex string matching or complicated transformations to check this equality, you just count the symbols in each word.

Nadia: Exactly. It simplifies a lot because checking those counts is straightforward, and it works for any alphabet size, not just binary ones.

Elias: And they showed that this result actually covers the case where all your letters are different—that’s a pretty broad characterization for words over arbitrary finite alphabets.

Priya: So if we have two sequences of symbols, you can determine if they're cyclically equalizable just by comparing their symbol counts, and it works regardless of how big the alphabet is.

Nadia: That’s the core idea—it connects a structural property of word manipulation to a simple frequency count across any alphabet.

Elias: It really generalizes what was known before, specifically solving that question for ternary alphabets as just one instance of this main theorem.

Priya: For someone just listening, the big takeaway is that you can simplify this kind of sequence comparison down to basic counting measures.

Nadia: And it has some serious implications for things like card-based cryptography we touched on earlier—it means if those underlying multisets match, you can achieve a specific type of information erasure.

Elias: It moves the analysis from complex word operations to analyzing just the multiset itself, which is much more computationally accessible.

Priya: It suggests that for security protocols built on these sequences, ensuring indistinguishability after adding extra elements boils down to checking those basic card types.

Nadia: So they’ve tied this concept of cyclic equalizability directly to Abelian equivalence in a very clean way, which is a big step for the field.

Massachusetts Institute of Technology · Department of Computer Engineering, Faculty of Engineering, Chulalongkorn University

math.CO, cs.CR

Submitted: 2026-04-21

Updated: 2026-10-19

Comments: This paper has appeared at ICTAC 2026

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 81/100

The gist: The gist: Two words over an arbitrary finite alphabet are cyclically equalizable if and only if they have the same Parikh vector.

Key concepts

Cyclic Equalizability: This is a property of word collections where, by inserting identical letters at fixed positions across all words, the resulting sequences can be rearranged into cyclic shifts of each other. It is relevant in card-based cryptography for analyzing sequences without revealing existing cards.
Parikh Vector: The Parikh vector is a way to describe a word by counting how many times each unique letter appears. For example, if a word has three 'a's and two 'b's, its Parikh vector would be (3, 2) for the letters in alphabetical order. Two words are cyclically equalizable if their Parikh vectors are identical.
Abelian Equivalence: The paper establishes that cyclic equalizability is exactly the same as Abelian equivalence for two words over any finite alphabet. This means two words can be transformed into each other through a sequence of operations that involve cyclic shifts and insertions, provided they have the same underlying character counts (Parikh vectors).
Hamming Weight: The Hamming weight is a specific measure used when dealing with binary words (words made of only 0s and 1s). In this context, it represents the total number of '1's in a word. The paper uses this as the known characterization for cyclic equalizability specifically when the alphabet size is two.

Summary

The gist: Two words over an arbitrary finite alphabet are cyclically equalizable if and only if they have the same Parikh vector.

Introduction and Motivation

Cyclic equalizability is a notion introduced by Shinagawa and Nuida in 2025, in the study of card-based cryptography<ref:2604.19504#pg2>. 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<ref:2604.19504#pg3>. This notion arises naturally in the analysis of card-based protocols, where inserting letters corresponds to inserting additional cards to the sequence without revealing the existing cards<ref:2604.19504#pg4>. 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<ref:2604.19504#pg3>.

Characterization Theorem

The central contribution of this paper is the complete characterization of cyclic equalizability for two words over an arbitrary finite alphabet<ref:2604.19504#pg4>. Specifically, the authors prove that two words over a finite alphabet are cyclically equalizable if and only if they have the same Parikh vector<ref:2604.19504#pg4>. This result generalizes the binary case of Shinagawa and Nuida [9], and resolves their question for the ternary alphabet as a special case<ref:2604.19504#pg4>.

Reduction to Distinct Letters

The proof begins by reducing the problem to words where all letters are pairwise distinct<ref:2604.19504#pg5>. Lemma 1 shows that it suffices to prove the statement for words in which all letters are pairwise distinct<ref:2604.19504#pg5>. By relabeling the alphabet so that the letters of u are 0, 1,..., n − 1 in this order, and since v is a permutation of the same letters, it can be written as π(0)π(1)· · · π(n − 1) for some permutation π ∈ Sn<ref:2604.19504#pg5>. This leads to Corollary 1, which states that it suffices to consider the case where u = 0 1 · · · (n − 1) and v = π(0) π(1)· · · π(n − 1) for an arbitrary permutation π ∈ Sn<ref:2604.19504#pg6>.

Construction for Single-Cycle Case

The paper constructs words u′ and v′ from u and v by a simultaneous insertion such that they are cyclically equivalent with offset p=n+1<ref:2604.19504#pg8>. This construction involves partitioning the positions in Zn2 into n blocks and n groups<ref:2604.19504#pg8>. The core of the construction relies on defining a bijection f(t, g) that maps each pair of a block and a group to a unique position in Zn2<ref:2604.19504#pg8>. The filling strategy designates exactly n distinguished positions based on the permutation π<ref:2604.19504#pg9>.

General Case Construction

For the general case where π ∈ Sn decomposes into m disjoint cycles, a modified version of the single-cycle construction is applied to each cycle independently<ref:2604.19504#pg13>. The resulting words u[s] and v[s] for each cycle are then combined using columnwise interleaving to obtain u′ = I(u[1],..., u[m]) and v′ = I(v[1],..., v[m])<ref:2604.19504#pg13>. Lemma 3 implies that since all pairs (u[s], v[s]) have the same cyclic offset p, the resulting words u′ and v′ are cyclically equivalent<ref:2604.19504#pg13>.

Implications

The main theorem provides an algorithmic implication: checking whether the Parikh vectors of two words are equal can be done in O(n) time<ref:2604.19504#pg14>. Furthermore, the proof offers a constructive method to transform two Abelian equivalent words into cyclically equivalent words via simultaneous insertions in O(mn2) time<ref:2604.19504#pg14>. This result implies that for any two sequences with the same multiset of cards, information erasure is always achievable in the case S = 2<ref:2604.19504#pg15>.

Open Problems

Several open problems remain, including characterizing cyclic equalizability for k ≥ 3 words, determining the minimal insertion length required to obtain cyclically equivalent words, and understanding the effects of restricted insertions. The paper concludes by showing that cyclic equalizability coincides exactly with Abelian equivalence for two words over arbitrary finite alphabets.

Conclusion

In this paper, the authors establish 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. The characterization has implications for card-based cryptography, showing 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.

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).

[3] M. Lothaire. Algebraic Combinatorics on Words. Cambridge University Press (2011).

[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).

[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).

[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).

[5] M. Lothaire. Combinatorics on Words, 2nd Edition. Cambridge University Press (1997).

[4] M. Lothaire. Applied Combinatorics on Words. Cambridge University Press (2005).

--- Page 1 ---

Improvements for AI systems

textbfDefinite Decision Procedure for Indistinguishability Check: 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., This allows AI systems to rapidly determine if two sequences (e.g., card sequences or cryptographic encodings) can be made indistinguishable under random cuts by inserting additional cards, based solely on their letter counts.
textbfConstructive Transformation for Indistinguishability: The proof of the main theorem provides a constructive method to transform two Abelian equivalent words into cyclically equivalent words via simultaneous insertions., This enables AI systems to explicitly generate the necessary inserted cards or elements required to make two sequences indistinguishable under random cuts, with an explicit algorithm running in O(mn 2) time.
textbfEnhanced Cryptographic Analysis: The 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., AI systems analyzing card-based cryptographic protocols can leverage this to guarantee that two inputs with identical multisets of cards can be rendered indistinguishable by an adversary performing a random cut and subsequent card insertions.

Listen

Transcript

Key concepts

Summary

Improvements for AI systems

Related papers