arxiv: 2603.15830 · v2 · submitted 2026-03-16 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

Necklaces, subset sums, and cyclic permutations

Robert Dougherty-Bliss , Sergi Elizalde

Authors on Pith no claims yet

Pith reviewed 2026-05-15 09:42 UTC · model grok-4.3

classification 🧮 math.CO

keywords necklacessubset sumsgenerating functionsbinary necklacescyclic permutationsq-ary necklacesunimodal permutationsperiodicity

0 comments

The pith

Generating functions equate k-subset sums congruent to r mod n with counts of binary necklaces having k ones and matching periodicity, under explicit conditions on n, k, r.

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

The paper generalizes the known equality for odd n between subsets with sums divisible by n and binary necklaces of length n. It introduces a residue parameter r and a size parameter k so that the count of k-element subsets summing to r modulo n equals the count of binary necklaces of length n with exactly k ones obeying periodicity conditions determined by r. The authors supply the precise conditions on n, k, and r under which these equalities hold and prove them by matching suitable generating functions. The case r=1 resolves a conjecture linking the subsets to unimodal one-cycle permutations, while some of the formulas extend to q-ary necklaces.

Core claim

The authors establish that the number of subsets of size k from {1, 2, ..., n} whose sum is congruent to r modulo n equals the number of binary necklaces of length n with exactly k ones that satisfy periodicity conditions tied to r, and they specify the precise conditions on n, k, r under which this holds. This is proved by equating appropriate generating functions. The case r=1 resolves a conjecture connecting such subsets to unimodal permutations consisting of a single cycle. Extensions to q-ary necklaces are also provided for some formulas.

What carries the argument

Generating functions that track subset size k, sum modulo n, and the periodicity constraints on binary necklaces.

Load-bearing premise

The equalities hold precisely when the stated conditions on n, k, r are met, and that generating functions accurately encode the subset sums and the periodicity conditions on the necklaces.

What would settle it

For any small triple (n, k, r) satisfying the stated conditions, enumerate the k-subsets summing to r mod n and count the corresponding necklaces; a mismatch in the two numbers would show the claimed equality fails.

Figures

Figures reproduced from arXiv: 2603.15830 by Robert Dougherty-Bliss, Sergi Elizalde.

read the original abstract

It is a well known that, for odd $n$, the number of subsets of $\{1,2,\dots,n\}$ the sum of whose elements is divisible by $n$ equals the number of binary necklaces of length $n$. In this paper generalize this result in two directions. On the one hand, we introduce a parameter $r$ so that requiring the subset sums to be congruent to $r$ modulo $n$ translates into imposing some periodicity conditions on the necklaces. On the other hand, we refine these relations by the size $k$ of the subset, showing that it matches the number of ones in the necklace. We describe the precise conditions on $n$, $k$ and $r$ for which the equalities hold. We also extend some of our formulas to $q$-ary necklaces. The classical results correspond to the case $r=0$. When $r=1$, our identity is related to a conjecture of Baker et al. connecting subsets the sum of whose elements is congruent to $1$ modulo $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.

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 generalizes the subset-sum mod n equals necklace count identity by adding a parameter r for periodicity conditions, refines by subset size k, extends formulas to q-ary necklaces, and proves the Baker et al. conjecture for r=1 via generating functions.

read the letter

The core advance here is a clean generalization of the classical result for odd n: subsets of {1..n} with sum ≡ r mod n match binary necklaces of length n that satisfy periodicity tied to r, with the match also holding when refined by subset size k (which equals the number of 1s). They state the exact conditions on n, k, r where the equality holds, recover the r=0 case, and extend some of the generating-function identities to q-ary necklaces. For r=1 they prove the Baker conjecture linking sum ≡1 mod n subsets to single-cycle unimodal permutations. All of this is done with generating functions that directly track the sum congruences and the cyclic constraints. The approach is standard but applied carefully enough to give precise conditions and settle the conjecture without apparent gaps. The generating-function encoding looks reliable for this type of enumeration. The main limitation is the absence of bijective proofs, which the authors flag as open; that leaves the combinatorial reason for the match still opaque. The results are narrow in scope, focused on this family of identities, so they will mainly interest people already working on necklaces or subset-sum problems in enumerative combinatorics. A reader who wants explicit generating functions for refined cyclic counts will find usable formulas. The paper is worth sending to referees because it proves an open conjecture with a direct method and states its conditions clearly.

Referee Report

0 major / 3 minor

Summary. The paper generalizes the classical identity (for odd n) equating the number of subsets of {1,2,...,n} whose elements sum to 0 mod n with the number of binary necklaces of length n. It introduces a parameter r so that the number of k-subsets with sum ≡ r mod n equals the number of binary necklaces of length n with exactly k ones that satisfy periodicity conditions induced by r. Precise conditions on n, k, r are derived under which the equalities hold. The r=1 case proves the Baker et al. conjecture relating such subsets to unimodal cyclic permutations, via generating functions. Some formulas are extended to q-ary necklaces; bijective proofs are left as open problems.

Significance. If the generating-function derivations hold, the work supplies a uniform proof technique for these refined necklace-subset-sum identities, including a proof of the Baker et al. conjecture, and provides explicit conditions plus a q-ary extension. The direct encoding of both modular sum conditions and cyclic periodicity in the generating functions is a clear technical strength.

minor comments (3)

[Abstract] Abstract, first sentence: 'It is a well known that' is grammatically incorrect and should read 'It is well known that'.
[Main results] The precise conditions on n, k, r are stated in the text but would benefit from being collected into a single numbered theorem or corollary early in the paper for easier reference.
[q-ary extension] The extension to q-ary necklaces is mentioned but the precise range of q for which the formulas carry over is not stated explicitly; a short clarifying sentence would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive assessment, including the recommendation for minor revision. The referee's summary accurately describes our generalization of the necklace-subset sum identities, the introduction of the parameter r, the refinement by subset size k, the proof of the Baker et al. conjecture via generating functions, and the q-ary extension. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; direct generating-function proof

full rationale

The paper constructs bivariate generating functions whose coefficients simultaneously track subset-sum congruences modulo n and the number of 1s (or q-ary symbols). Equating these generating functions to the known necklace generating functions yields the stated identities under explicit arithmetic conditions on n, k, r. The r=0 case recovers the classical result by specialization; the r=1 case proves the external Baker et al. conjecture. No parameter is fitted to data, no target identity is presupposed in the construction, and no load-bearing step reduces to a self-citation or redefinition. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard combinatorial techniques without introducing new free parameters or entities.

axioms (1)

standard math Validity of generating function techniques for enumerating subsets and necklaces
Invoked to establish the equalities and prove the conjecture as described.

pith-pipeline@v0.9.0 · 5517 in / 1132 out tokens · 35411 ms · 2026-05-15T09:42:13.883343+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We prove this conjecture using generating functions... precise conditions on n, k and r... extend some of our formulas to q-ary necklaces.
IndisputableMonolith/Foundation/DimensionForcing.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 4.7... ν₂(n) < ν₂(k)... ν₂(k)−ν₂(r) ≥ 2

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

Tom M. Apostol. Arithmetical properties of generalized Ramanujan sums.Pa- cific J. Math., 41:281–293, 1972

work page 1972
[2]

Apostol.Introduction to Analytic Number Theory

Tom M. Apostol.Introduction to Analytic Number Theory. Undergraduate Texts in Mathematics. Springer-Verlag, New York-Heidelberg, 1976

work page 1976
[3]

Cyclic permutations realized by signed shifts

Kassie Archer and Sergi Elizalde. Cyclic permutations realized by signed shifts. J. Comb., 5(1):1–30, 2014

work page 2014
[4]

Necklaces, per- mutations, and periodic critical orbits for quadratic polynomials.European J

Matthew Baker, Andrea Chen, Sophie Li, and Matthew Qian. Necklaces, per- mutations, and periodic critical orbits for quadratic polynomials.European J. Combin., 134:Paper No. 104352, 2026

work page 2026
[5]

Factoring Gleason polynomials modulo 2.J

Xavier Buff, William Floyd, Sarah Koch, and Walter Parry. Factoring Gleason polynomials modulo 2.J. Th´ eor. Nombres Bordeaux, 34(3):787–812, 2022

work page 2022
[6]

A bijection between necklaces and multisets with divisible subset sum.Electron

Swee Hong Chan. A bijection between necklaces and multisets with divisible subset sum.Electron. J. Combin., 26(1):Paper No. 1.37, 18, 2019

work page 2019
[7]

Gessel, Antonio Restivo, and Christophe Reutenauer

Ira M. Gessel, Antonio Restivo, and Christophe Reutenauer. A bijection between words and multisets of necklaces.European J. Combin., 33(7):1537–1546, 2012

work page 2012
[8]

Gessel and Christophe Reutenauer

Ira M. Gessel and Christophe Reutenauer. Counting permutations with given cycle structure and descent set.J. Combin. Theory Ser. A, 64(2):189–215, 1993

work page 1993
[9]

On the number of necklaces whose co-periods divide a given integer.Ramanujan J., 61(4):1021–1035, 2023

Petros Hadjicostas. On the number of necklaces whose co-periods divide a given integer.Ramanujan J., 61(4):1021–1035, 2023

work page 2023
[10]

A bijection between necklaces and restricted multisets, 2025

Jiyou Li and Yanghongbo Zhou. A bijection between necklaces and restricted multisets, 2025. Preprint,https://arxiv.org/abs/2507.19940

work page arXiv 2025
[11]

Lothaire.Combinatorics on words

M. Lothaire.Combinatorics on words. Cambridge Mathematical Library. Cam- bridge University Press, Cambridge, 1997

work page 1997
[12]

Odlyzko and Richard P

Andrew M. Odlyzko and Richard P. Stanley. Enumeration of power sums modulo a prime.J. Number Theory, 10(2):263–272, 1978

work page 1978
[13]

The On-Line Encyclopedia of Integer Sequences, 2025

OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2025. Published electronically athttp://oeis.org. 25

work page 2025
[14]

Stanley.Enumerative Combinatorics

Richard P. Stanley.Enumerative Combinatorics. Volume 1, volume 49 ofCam- bridge Studies in Advanced Mathematics. Cambridge University Press, Cam- bridge, second edition, 2012

work page 2012
[15]

Stanley.Algebraic Combinatorics

Richard P. Stanley.Algebraic Combinatorics. Undergraduate Texts in Mathe- matics. Springer, New York, 2013

work page 2013
[16]

A study of Varshamov codes for asymmetric channels.Jet Prop

Richard P Stanley and Michael F Yoder. A study of Varshamov codes for asymmetric channels.Jet Prop. Lab. Tech. Rep, pages 32–1526, 1972

work page 1972
[17]

Permutations with ascending and descending blocks.Electron

Jacob Steinhardt. Permutations with ascending and descending blocks.Electron. J. Combin., 17(1):Research Paper 14, 28, 2010

work page 2010
[18]

The cycle enumerator of unimodal permutations.Ann

Jean-Yves Thibon. The cycle enumerator of unimodal permutations.Ann. Comb., 5(3-4):493–500, 2001. 26

work page 2001