Necklaces, subset sums, and cyclic permutations

Robert Dougherty-Bliss, Sergi Elizalde · 2026

Read Necklaces, subset sums, and cyclic permutations by Robert Dougherty-Bliss, Sergi Elizalde (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-15830.txt.

Introduction

Dougherty-Bliss and Elizalde link subset sums to binary necklaces and cyclic permutations. For odd n, subsets of 1 to n with sums divisible by n match binary necklaces in count. Their work widens that classic match in two ways. A new parameter r shifts the target residue class. Necklaces then gain matching periodicity conditions. A size split k matches the count of ones in each necklace. Generating functions prove a related Baker conjecture for r equal to 1. Bijective proofs stay open for most cases.

Catalog record

CREATORRobert Dougherty-Bliss, Sergi Elizalde
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44212
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.15830

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Necklaces, subset sums, and cyclic permutations Robert Dougherty-Bliss, Sergi Elizalde Abstract It is a well known that, for odd n n , the number of subsets of { 1 , 2 , … , n } \{1,2,\dots,n\} the sum of whose elements is divisible by n n equals the number of binary necklaces of length n n . In this paper generalize this result in two directions. On the one hand, we introduce a parameter r r so that requiring the subset sums to be congruent to r r modulo n n translates into imposing some periodicity conditions on the necklaces. On the other hand, we refine these relations by the size k k of the subset, showing that it matches the number of ones in the necklace. We describe the precise conditions on n n , k k and r r for which the equalities hold. The classical results correspond to the case r = 0 r=0 . When r = 1 r=1 , our identity is related to a conjecture of Baker et al. connecting subsets the sum of whose elements is congruent to 1 1 modulo n n and unimodal permutations which consist of one cycle. We prove this conjecture using generating functions. Finding bijective proofs of most of our identities remains an open problem. 1 Introduction As shown by Stanley [ 14 , Exer. 1.105] , the number of subsets of [n]\coloneqq\{1,2,\dots,n\} the sum of whose elements is divisible by n is equal to \frac{1}{n}\sum_{\begin{subarray}{c}d\mid n\\ d\text{ odd}\end{subarray}}\phi(d)2^{n/d}, (1) where \phi is Euler’s totient function. It is well known that, when n is odd, this formula also counts (binary) necklaces of length n , which are equivalence classes of binary words under rotation. Stanley posed the challenge of finding a bijective proof of this fact, which was eventually done by Chan in [ 6 ] . A similar formula, as well as another instance of a connection between subset sums and necklaces, appeared recently in work of Baker, Chen, Li, and Qian [ 4 ] . They were studying the Gleason polynomials G_{n}(c) , recursively defined by the formula \prod_{d\mid n}G_{k}(c)=\underbrace{(((c^{2}+c)^{2}+c)^{2}+\cdots+c)^{2}+c}_{n-1\text{ iterates}}. Buff et al. [ 5 ] had proved that, for any positive integer n , the number of real roots of G_{n}(c) is equal to the number of irreducible factors of G_{n}(c) when considered as a polynomial over the two-element finite field, by showing that both sets are enumerated by \frac{1}{2n}\sum_{\begin{subarray}{c}d\mid n\\ d\text{ odd}\end{subarray}}\mu(d)2^{n/d}, (2) where \mu is the Möbius function. Baker et al. gave an explicit bijection between these sets, using several intermediate objects, all of which are counted by equation ( 2 ). One of such objects are primitive necklaces, which are necklaces all of whose rotations are different. It is known that equation ( 2 ) counts primitive necklaces of length n with an odd number of ones. Another such object are V-shaped permutations of [n] (i.e., permutations with a unique local minimum) which are cycles, also known [ 3 ] to be enumerated by equation ( 2 ). Baker et al. [ 4 ] noticed that, according to [ 12 , A000048] , there is yet another object counted by equation ( 2 ): subsets of [n-1] whose elements sum to 1\bmod n . They conjectured that the following refinement holds. Conjecture 1.1 ( [ 4 ] ) . The number of cyclic V-shaped permutations of [n] whose minimum is at position k equals the number of (k-1) -element subsets of [n-1] whose elements sum to 1\bmod n . Our first main result (Theorem 3.1 below) is a proof of this conjecture. We also show, by applying a bijection from [ 3 , 16 ] , that the connection that was observed in [ 4 ] between primitive necklaces and subsets that sum to 1\bmod n admits a natural refinement where the number of ones in the necklace corresponds to the size of the subset. The analogous refinement also applies to the equality from [ 14 , Exer. 1.105] involving arbitrary necklaces and subsets whose sum is divisible by n . In fact, as we will see in Theorem 4.6 , both of these results are special cases of a more general framework relating necklaces whose period satisfies certain divisibility conditions, and subsets whose sum is congruent to a fixed value modulo n . The remainder of this paper is structured as follows. In Section 2 we give the necessary background on necklaces, permutations, and subset sums, and we introduce some notation. We also describe, in Section 2.4 , the classical connection between subsets of [n] whose sum is divisible by n and necklaces of length n , when n is odd, as well as a recent refinement by the size of the subset, which can be viewed as inspiration for our work. In Section 3 we prove Conjecture 1.1 , and then we use known bijections between permutations and necklaces to deduce a connection between subsets of [n] whose sum is equal to 1\bmod n and primitive necklaces of length n . In Section 4 , we put the two connections described above under the same umbrella, proving a more general result that relates subsets of [n] whose sum is equal to 1\bmod n and necklaces whose co-period (defined in Section 2.1 ) divides r . As in the previous cases, the size of the subset k corresponds to the number of ones in the necklace. In Theorem 4.7 , we describe the precise conditions on n , r , and k for which the equality holds. In Section 5 , we list several open questions that our work raises, mostly about finding bijective proofs of several equalities relating necklaces, subset sums, and permutations. 2 Definitions and background 2.1 Necklaces Two binary words u,v of length n are conjugate if they are cyclic rotations of each other, that is, there exist words r and s such that u=rs and v=sr . A binary necklace of length n is a conjugacy class of binary words of length n ; we write (u) to denote the conjugacy class of the word u . Throughout the paper, we will use the term necklace to refer to a binary necklace, i.e., over the alphabet \{0,1\} . A word u is primitive if it is not the power of another word, i.e., it is not of the form u=v^{j} for j\geq 2 . If u=v^{j} and v is primitive, we call j the co-period of u . A necklace is primitive if it is the conjugacy class of a primitive word. A Lyndon word is a primitive word that is lexicographically smaller than all the other words in its conjugacy class. Lyndon words are in one-to-one correspondence with primitive necklaces, since each conjugacy class of primitive words has a unique lexicographically smallest element. Definition 1 . For any integers 0\leq k\leq n and 0\leq r<n , define the following sets: • N(n,k) is the set of binary necklaces of length n with k ones. • L(n,k) is the set of necklaces in N(n,k) that are primitive; equivalently, the set of binary Lyndon words of length n with k ones. • N_{r}(n,k) is the set

Read the complete text