Cyclic Equalizability Characterized by Parikh Vectors

Sarit Pasiphol; Sarunyu Thongjarast; Suthee Ruangwises

arxiv: 2604.19504 · v1 · submitted 2026-04-21 · 🧮 math.CO · cs.CR

Cyclic Equalizability Characterized by Parikh Vectors

Sarunyu Thongjarast , Sarit Pasiphol , Suthee Ruangwises This is my paper

Pith reviewed 2026-05-10 02:27 UTC · model grok-4.3

classification 🧮 math.CO cs.CR

keywords cyclic equalizabilityParikh vectorcyclic shiftsword insertionscombinatorics on wordscard-based cryptographyfinite alphabet

0 comments

The pith

Two words are cyclically equalizable if and only if they have the same Parikh vector.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that two words over any finite alphabet become cyclically equalizable precisely when they contain exactly the same number of each letter. This means insertions of identical letters at identical positions can turn them into cyclic shifts of one another if and only if their letter frequencies match. The result generalizes the known binary case, where equal length and the same number of ones were required, to arbitrary alphabets and unequal lengths. A reader cares because the property appears in card-based cryptography, and the characterization replaces trial insertions with a simple frequency check.

Core claim

We prove that, for any finite alphabet and any two words over it, the words can be transformed into cyclic shifts of each other by inserting identical letters at identical positions if and only if the words contain exactly the same number of occurrences of each letter.

What carries the argument

The Parikh vector of a word, the tuple of occurrence counts for each letter, which serves as the exact invariant preserved by the allowed insertions and cyclic shifts.

If this is right

The binary result follows immediately by restricting the Parikh vector to a single entry.
Cyclic equalizability is independent of the original word lengths.
Verification requires only comparing letter counts rather than searching for insertion sequences.
The same condition applies uniformly to every finite alphabet.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same frequency condition may serve as a necessary invariant for related equalization tasks that combine insertions with other word operations.
In cryptographic protocols the check can be performed in linear time before attempting any insertions.
The characterization supplies a concrete test that could be used to decide membership for collections of more than two words.

Load-bearing premise

Cyclic equalizability is defined to permit the insertion of identical letters at the same positions in every word.

What would settle it

Either two words with unequal Parikh vectors that still become cyclic shifts after some common insertions, or two words with equal Parikh vectors that cannot be aligned to cyclic shifts by any common insertions.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper settles the open problem by showing two words over any finite alphabet are cyclically equalizable if and only if they share the same Parikh vector.

read the letter

The core result is a clean if-and-only-if statement that extends the 2025 binary case to arbitrary alphabets. Necessity follows immediately: any common insertions add the same letter counts to both words, and cyclic shifts leave the Parikh vector unchanged, so matching vectors are required. Sufficiency comes from an explicit construction that places insertion strings into the gaps to force the padded versions to be rotations of each other, using the shared counts to align the positions correctly. That construction appears to handle the general case without extra restrictions on the alphabet size or word lengths. The paper does this work directly and without unnecessary machinery, which is the main strength. The argument stays grounded in standard combinatorial invariants rather than introducing new parameters or fitted quantities. One limitation is the restriction to exactly two words; the definition and proof do not address collections of three or more, so the scope stays narrow. Edge cases such as the empty word or unary alphabets are presumably covered by the same construction, but a referee would still want to see them written out. The citation pattern is appropriate, pointing back to the 2025 source that posed the question. Readers working in combinatorics on words or in the card-based cryptography applications that motivated the notion will find this useful as a quick test. It is not reshaping larger areas of the field, but it closes a stated gap with a verifiable claim. The work shows clear thinking and honest engagement with the prior result. I would bring it to a reading group for the proof details and would send it to peer review so the construction can be checked line by line.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that two words over an arbitrary finite alphabet are cyclically equalizable if and only if they have the same Parikh vector. Necessity follows because cyclic shifts preserve Parikh vectors and identical insertions add the same letter counts to both words. Sufficiency is shown by an explicit construction that, given matching Parikh vectors, chooses insertion strings for the length+1 gaps between letters so that the padded words become cyclic shifts of each other.

Significance. If the result holds, it supplies a complete, constructive characterization that resolves the open problem posed by Shinagawa and Nuida for the two-word case over general alphabets. The explicit construction is a notable strength, as it yields a direct method rather than a non-constructive existence argument and relies only on the standard Parikh-vector invariant without additional parameters. The work therefore strengthens the combinatorial toolkit available for applications such as card-based cryptography.

minor comments (2)

[§2] The definition of the insertion mechanism (positions and allowed strings) is referenced to the 2025 source but could be restated briefly in §2 for self-contained reading.
[§4] In the sufficiency construction, the alignment of insertion strings with letter counts is described informally; a short pseudocode or enumerated step list would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review and for recommending acceptance of the manuscript. Their summary accurately captures both the necessity and sufficiency directions of our characterization, as well as the constructive nature of the proof and its relevance to the open problem of Shinagawa and Nuida.

Circularity Check

0 steps flagged

No significant circularity in the characterization

full rationale

The paper's derivation is self-contained against the given definitions. Necessity follows directly from the fact that identical insertions add the same Parikh increments to both words and cyclic shifts preserve Parikh vectors exactly, so equalizability requires the originals to match. Sufficiency is shown by an explicit construction that, for any two words sharing a Parikh vector, selects insertion letters and positions (in the length+1 gaps) to produce padded strings that are rotations of each other; this construction is algorithmic and uses only the shared letter counts without additional fitted parameters or constraints. The prior definition of cyclic equalizability is cited from Shinagawa and Nuida (different authors, 2025) solely to introduce the notion being characterized; no uniqueness theorems, ansatzes, or self-citations are load-bearing. No step renames a known result or reduces the claimed equivalence to a tautology by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard definitions of words, cyclic shifts, insertions, and Parikh vectors from prior literature; no new free parameters or invented entities are introduced in the abstract.

axioms (1)

standard math Standard definitions of words over finite alphabets, cyclic shifts, and Parikh vectors as used in combinatorics on words.
The characterization invokes these background notions without re-deriving them.

pith-pipeline@v0.9.0 · 5430 in / 1107 out tokens · 36528 ms · 2026-05-10T02:27:21.292810+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

[1]

den Boer

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 Tech- niques (EUROCRYPT ’89), pp. 208–217 (1990)

work page 1990
[2]

Koch and S

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)

work page 2020
[3]

Lothaire

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

work page 2011
[4]

Lothaire

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

work page 2005
[5]

Lothaire

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

work page 1997
[6]

Mahalingam and H

K. Mahalingam and H. Ravi. Operation Insertion on the Conjugacy and Commutativity of Words. InProceedings of the 8th International Conference on the Theory and Practice of Natural Computing (TPNC), pp. 70–81 (2019)

work page 2019
[7]

Mizuki and H

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)

work page 2014
[8]

Poovanandran, J

G. Poovanandran, J. Simpson, and W.C. Teh. Counting subwords in circular words and their Parikh matrices.Theoretical Computer Science, 985: 114344 (2024)

work page 2024
[9]

Shinagawa and K

K. Shinagawa and K. Nuida. Cyclic Equalizability of Words and Its Application to Card-Based Cryptography. InProceedings of the 25th International Symposium on Fun- damentals of Computation Theory (FCT), pp. 406–419 (2025). 15

work page 2025

[1] [1]

den Boer

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 Tech- niques (EUROCRYPT ’89), pp. 208–217 (1990)

work page 1990

[2] [2]

Koch and S

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)

work page 2020

[3] [3]

Lothaire

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

work page 2011

[4] [4]

Lothaire

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

work page 2005

[5] [5]

Lothaire

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

work page 1997

[6] [6]

Mahalingam and H

K. Mahalingam and H. Ravi. Operation Insertion on the Conjugacy and Commutativity of Words. InProceedings of the 8th International Conference on the Theory and Practice of Natural Computing (TPNC), pp. 70–81 (2019)

work page 2019

[7] [7]

Mizuki and H

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)

work page 2014

[8] [8]

Poovanandran, J

G. Poovanandran, J. Simpson, and W.C. Teh. Counting subwords in circular words and their Parikh matrices.Theoretical Computer Science, 985: 114344 (2024)

work page 2024

[9] [9]

Shinagawa and K

K. Shinagawa and K. Nuida. Cyclic Equalizability of Words and Its Application to Card-Based Cryptography. InProceedings of the 25th International Symposium on Fun- damentals of Computation Theory (FCT), pp. 406–419 (2025). 15

work page 2025