Statement
Let , where 1 denotes a black bead and 0 a white bead. The necklace is primitive: the word is not a repetition of a word of length 1, 2, or 5.
Let be the limiting level-size generating function for Bulgarian Solitaire associated with the necklaces , as defined in Pham 2022, Theorem 1.2. Put
and
Theorem. We have the exact identity
Moreover, . Consequently the reduced denominator of has degree , although . This contradicts the exact reduced-denominator degree conjecture stated in the last paragraph before the orbit-size discussion in Section 6 of Pham's 2022 paper. It does not contradict the later common-denominator conjecture of Harris and Nguyen (2025); see below.
The proof is a finite, exactly reproducible computation combined with Pham's proven degree bounds. All computations use integers (and fractions only for the polynomial gcd check), not interpolation or floating point.
1. The finite-coefficient identity principle
Lemma. Let , with , , and . Let . If
and
then identically as rational functions.
Proof. The polynomial has degree at most the displayed maximum. Because , the assumed congruence implies . A polynomial of degree less than divisible by must be zero.
By Pham 2022, Theorem 1.2, the generating function of a primitive length-10 necklace has a representation with and , and . For our proposed and ,
Thus checking the first 26 coefficients of suffices for an identity at all degrees.
2. Exact coefficient enumeration
The first 26 coefficients, obtained by the exact reverse-Bulgarian-Solitaire enumeration implemented in verify.py, are:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 10 | 4 | 10 | 18 | 30 | 52 | 96 | 164 | 280 | 484 | 860 | 1512 | 2588 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 4476 | 7856 | 13796 | 23900 | 41288 | 72076 | 126220 | 219664 | 380628 | 662252 | 1157000 | 2016604 | 3502748 |
Define for . Direct integer arithmetic on these values gives
The first eight values of this expression are ; all values for are zero. That is, . The lemma proves exactly, so the proposed recurrence holds for every , not merely for the checked values. Finally, Euclidean division in gives , verified by the included program. The theorem follows.
3. Why the enumeration is exact
Here is the complete mathematical basis for the certificate in verify.py.
For a primitive necklace of length , let and be the periodic binary word obtained by repeating (subscripts on are taken modulo ). The cycle partitions for the necklace have parts
with zero parts omitted, for . This is the recurrent-cycle description used by Pham.
For an ordinary partition , an inverse Bulgarian Solitaire move is determined by choosing a distinct part size satisfying : delete one part of size , add one to every remaining part, and append parts of size 1. The resulting partition has length , and applying the forward Bulgarian Solitaire operation recovers . Different selected sizes give different preimages because their lengths differ. Every preimage arises this way.
The forward operation is deterministic. Therefore, outside the recurrent cycle, no partition can belong to two distinct reverse paths beginning at the cycle. To enumerate depth , start from the cycle partitions, enumerate all inverse moves, remove the cycle-to-cycle inverses, and repeat. Pham proves in Section 4 that these finite level sizes agree with the limiting coefficients through at least level . Thus choose for the main certificate.
For efficient exact enumeration, use zero-based indices and write the first entries of a partition as
A partition at a bounded reverse depth has outside a bounded exceptional prefix: each move deletes one entry and shifts the periodic tail by one position. Store precisely the exceptional prefix , periodic tail phase , and length offset . In particular, if and is far from the finite right boundary, then .
The condition for an inverse move at the -th position is precisely
If and , the -th and -st piles are equal, so select only the earlier occurrence. When the move at position is made, the updated head and length offset are exactly
After this update, remove all terminal prefix entries that equal their periodic-tail values. verify.py implements just these formulas with integer arithmetic, maintaining a counter of the number of actual partitions represented by each compressed state. Multiplicity cannot be discarded: two actual partitions with different distant boundaries can have the same compressed head.
To justify that no move near the finite boundary is overlooked, observe that after reverse moves every head entry satisfies away from the boundary (initially , and each move only shifts or increments an entry). Also : initially , and the legality inequality implies . Thus any eligible in the periodic region satisfies
The exceptional prefix also remains within the same bounded head. For , these indices are far below , so the finite boundary cannot affect a legal move or any stored head entry. The compressed enumeration is therefore identical, with multiplicity, to full reverse-partition enumeration through the depths needed for the certificate. Its first 16 levels have additionally been checked against a separately implemented full-partition enumerator in verify.py.
The only discarded inverses are the cycle-to-cycle edges when transitioning out of level zero. At subsequent depths a state with the same compressed key as a root need not be an actual cycle partition, so its multiplicity is retained. This distinction is necessary for correct counting.
4. What this does not disprove: the duality conjecture
The dual of , obtained by reversing and exchanging 0 and 1, is
Let , so , and write
A second, optional certificate (python verify.py --dual) computes 31 exact coefficients and proves, by the same lemma and Pham's degree bounds,
where
Here , so the dual's reduced denominator has degree 10. Since
both and can be written over the same denominator of degree 10. Thus our example is consistent with Harris and Nguyen 2025, Conjecture 1.1. That is a different and weaker statement than Pham's 2022 exact-degree conjecture.
5. Reproduction and source checks
python3 verify.py
python3 verify.py --dual --brute-depth 13
python3 -m unittest discover -s tests -vThe primary command recomputes all 26 coefficients, verifies the polynomial congruence, checks coprimality by the Euclidean algorithm, and compares against direct partition enumeration at small depth. The optional dual command checks all 31 coefficients of the dual identity. Tests also compare the enumerator against two generating functions explicitly published by Pham (the necklaces 1000 and 1110). All files require only Python's standard library.
References
- Nhung Pham, Limiting behavior in growth of Bulgarian Solitaire orbits, arXiv:2208.14496 (2022), Theorem 1.2, Sections 4 and 6. arXiv HTML · PDF. The conjecture addressed here is the unnumbered exact-degree conjecture in Section 6.
- A. J. Harris and Son Nguyen, Bulgarian Solitaire: A new representation for depth generating functions, Australasian Journal of Combinatorics 93(2) (2025), 224–273, Conjecture 1.1. Journal PDF.
This is a computationally assisted proof with an explicit finite certificate, not a claim about novelty or publication priority.