Binary Necklaces
A binary necklace is a rotation class of binary words: moving the starting position around the circle does not change the necklace. The binary words of length n correspond to all subsets of a cyclically ordered n-element set, so they represent its power set. Rotation classes partition these words, and the adjacent-XOR map defined below partitions the necklaces into connected components of a functional graph. Collecting the subsets represented by each component gives a partition of the entire power set. Components can then be grouped by directed-graph isomorphism type. Every component contains a cycle, which generates a periodic space-time diagram that can be rendered geometrically as a tessellation.
| Calculator and Tessellator | Calculates certain properties of a given binary word and generates a tessellation (2024) |
| Properties of Bitloops (digital | print) | First interpretation (2020) |
| Bitloops (html) | Last revision that was not AI-assisted (2025) |
| GenAI Research | Papers by ChatGPT Astra on the theory and applications of power set partitions (2026) |
| Contents: |
| Binary Necklaces |
| Adjacent XOR |
| Primitive Roots and Spatial Periods |
| Power Sets |
| Dynamical Components |
| Symmetry |
| Graphs |
| Space-Time Diagrams and Tessellations |
| Appendix |
Binary Necklaces
A bit is either zero or one. A binary word is a finite sequence of bits. The bits are written like letters in a word. The letter n denotes the length of the word, which here is always a positive integer.
00001011 and 01010101 are binary words, each with n = 8 bits.
The positions in a binary word are ordered and can be indexed. Let J = {i1, i2, ..., in} be the set of positions. A word is a function w: J → {0, 1}, written w(i1) w(i2) ... w(in).
Given the binary word 01, w(i1) = 0 and w(i2) = 1.
A binary necklace has n cyclically ordered bits and no distinguished starting position. For comparison, the seasons have a cyclic order without a distinguished first season. A necklace can be drawn as a ring or represented by a binary word, with the understanding that rotating the word gives the same necklace. Reflection is not identified with rotation. Binary words are written as sequences of bits without enclosing punctuation. A necklace is specified by a representative word; the surrounding text distinguishes the word from its rotation class.
100001 is a binary word. It represents a necklace whose other representatives are the rotations of that word.
Potentially multiple binary words may represent the same necklace.
The binary words 1000, 0100, 0010 and 0001 all represent the same necklace.
A rotation class, or orbit under cyclic rotation, is the set of all words representing one binary necklace. The necklace is this entire equivalence class. Words in the same class are rotations of each other.
The necklace represented by 100 has the rotation class {100, 010, 001}.
The necklace represented by 1010 has the rotation class {1010, 0101}. The words 1010 and 0101 are rotations of each other.
The necklace 11111 has a rotation class with only one word.
A permutation of a binary word alters the indices of its bits. Let α be a permutation that follows this rule:
α(i1) = i2, α(i2) = i3, ..., α(in-1) = in, α(in) = i1.
α is a cycle (or n-cycle), which rotates the indices by one position. αm rotates each index by m positions. α1 = α.
| α(1101) = 1110 |
| α(1110) = 0111 |
| α2(0111) = 1101 |
| α-1(1101) = 1011 |
Two binary words a and b are related by a one-position rotation if α(a) = b or α(b) = a.
0100 and 0010 differ by a one-position rotation.
1000 and 0010 do not differ by a one-position rotation.
Adjacent XOR
A unary bitwise operation takes one binary word and produces another. The unary operation bitwise NOT takes one binary word and changes each zero to a one, and each one to a zero. The resulting binary word is the complement of the original, and vice versa.
| NOT | 0011 | |
| = | 1100 |
0011 is the complement of 1100, and 1100 is the complement of 0011.
Necklaces can also be complements of each other. If so, then members of their respective rotation classes form complement pairs.
| Necklace representative | Rotation class | ||
| 100 | 100 | 010 | 001 |
| 011 | 011 | 101 | 110 |
| ↑ | ↑ | ↑ | |
| complement pairs | |||
A binary bitwise operation takes two binary words and produces another. Bitwise XOR does this by adding bits, where 0 + 0 = 0, 0 + 1 = 1, and 1 + 1 = 0. This kind of addition is called addition modulo 2.
| 0101 | ||
| XOR | 0011 | |
| = | 0110 |
The adjacent-XOR map, also called the binary Ducci map, sends a word w to D(w) = w XOR α(w). Each output bit is the sum modulo two of neighboring input bits. Rotation commutes with this map, so rotating w only rotates its image. The map therefore induces a well-defined map on necklaces, also denoted D. Given a necklace P, take a representative and its one-position rotation and apply XOR. Let Q be the necklace represented by the resulting word. Then Q = D(P) is the image of P.
Let P be the necklace represented by 1000, and take two of its representative words a = 1000 and b = 0100.
| 1000 | ||
| XOR | 0100 | |
| = | 1100 |
Then the image D(P) is the necklace represented by 1100.
A preimage of Q is a necklace P with D(P) = Q. Taking preimages is a relation, not an inverse function: a necklace can have no preimages, one preimage, or two distinct preimages.
Successive images of a necklace can be displayed using representative words, with each arrow indicating one application of the induced map.
0001 → 0011 → 0101 → 1111 → 0000 → 0000 → ...
A necklace has a preimage if and only if its Hamming weight, the number of ones in a representative, is even.
The necklace represented by 11 has a single necklace preimage, represented by 01. The necklace represented by 01 has no preimage.
A necklace and its complement generate the same image.
11110 is the image of 01010 and 10101.
A necklace is self-complementary if complementing every bit gives a rotation of the original word. Equivalently, its rotation class is closed under bitwise complementation.
The necklace represented by 1100 is self-complementary. Its rotation class is {1100, 1001, 0011, 0110}.
The shortest repeating representative of a self-complementary necklace has even length and can be split into complementary halves. The full displayed word need not have complementary halves if that shortest block is repeated an even number of times.
The necklace represented by 1101100100 is self-complementary. The words 11011 and 00100 are complements.
Some necklaces are fixed points of the induced adjacent-XOR map: their images are rotations of themselves. Six examples are listed below with the tessellations derived from their periodic space-time diagrams. Reversing or repeating any of these representatives also gives a fixed necklace.
| n | tiling | necklace representative |
| 1 | png | 0 |
| 3 | png | 011 |
| 7 | png | 0011101 |
| 15 | png | 000111101011001 |
| 21 | png | 000011111010100110001 |
| 63 | png | 000001000011000101001111010001110010010110111011001101010111111 |
Primitive Roots and Spatial Periods
A binary word can be written uniquely as uk, meaning k concatenated copies of a shortest nonempty word u. This word u is its primitive root; it is not itself a proper power. For a necklace, the corresponding primitive necklace is the rotation class of u. Its length d is the least spatial period, and d divides n. Every necklace has exactly one such primitive necklace.
0001 is the primitive root of the word 0001000100010001. The block 00010001 also repeats, but it is not primitive.
1100 is not the primitive root of 11001100110011, because it does not repeat a whole number of times to form that word.
000111011 is its own primitive root.
The primitive necklace can be represented by any rotation of its primitive root. When displaying a word and its root together, matching their starting positions makes the repetition easier to see.
The word 001001 has primitive root 001. The words 010 and 100 represent the same primitive necklace, although they are not the literal primitive root of that displayed word. For example, 010 is the primitive root of 010010. The distinct words 001001 and 010010 represent the same necklace.
Another way to display a necklace is to repeat a representative indefinitely in both directions. The resulting periodic binary sequence has a least positive spatial period; choosing a different starting position changes its primitive word by a rotation.
... 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 ...
... 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...
... 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
The least spatial period is defined by the entire periodic sequence. A finite excerpt may not determine it uniquely, even if a short block appears twice. Repeating a fixed primitive necklace produces necklaces of arbitrarily large lengths that are multiples of its period.
For ease of reference, a word or necklace may be represented by its primitive root when the ambient length n is specified or understood. The root is repeated to recover that length.
At width eight, successive necklace images can be displayed using primitive
representatives:
00001111 → 0001 → 0011 → 01 → 1 → 0.
Power Sets
The notation P(S) denotes the power set of a set S: the set of all subsets of S. Calligraphic lettering is customary for a family of sets.
Let S = {x, y} for the next four examples.
P(S) = {∅, {x}, {y}, {x, y}}, where ∅ denotes the empty set.
Give the elements of S a cyclic ordering and choose a bijection f: S → J assigning each element a position. This ordering supplies the rotation used throughout the construction.
f(x) = i1, f(y) = i2
The bits of a binary word are also indexed by J, so each element in S is assigned a position in a binary word.
The first position, i1, corresponds to x; the second, i2, corresponds to y.
By this correspondence, a binary word is the characteristic vector of a subset of S: a bit is one exactly when its corresponding element belongs to the subset. Write Vn = {0, 1}n for the set of length-n words. The correspondence is a bijection between P(S) and Vn, so both have 2n elements.
| P(S) | V2 |
| ∅ | 00 |
| {x} | 10 |
| {y} | 01 |
| {x, y} | 11 |
V1 = {0, 1} represents the power set of a one-element set, the smallest width considered here.
Vn can be partitioned in a few ways. It can be partitioned by complement pairs of binary words, because every binary word has one and only one complement, which is not itself. Vn can be partitioned by rotation classes, because each binary word belongs to one and only one rotation class. Vn can also be partitioned according to the length of each binary word’s primitive root.
For n > 1, another partition of Vn separates the constant words, the nonconstant proper powers, and the primitive words. Let p be the primitive root of a word x. Put x in A if length(p) = 1, in C if length(p) = n, and in B otherwise.
| V4 = | {0000, 1111, 0101, 1010, 0011, 0110, 1100, 1001, 0001, 0010, 0100, 1000, 1110, 1101, 1011, 0111} |
| A = | {0000, 1111} |
| B = | {0101, 1010} |
| C = | {0011, 0110, 1100, 1001, 0001, 0010, 0100, 1000, 1110, 1101, 1011, 0111} |
For 0101, p = 01, and for 1010, p = 10. In either case, length(p) equals two. Two is greater than one and less than n, so 0101, 1010 ∈ B.
A = {0, 1} for any n, where binary words are represented by their respective primitive roots.
This partition gives the usual necklace-counting proof of the base-two case of Fermat's little theorem:
Theorem. For any prime number n, 2n - 2 is divisible by n.
Proof. The set Vn has 2n elements. Since n is prime and n must be divisible by the number of bits in p, length(p) = 1 or n, so B is empty. A has two elements, so C has 2n - 2 elements. Every binary word in C belongs to a rotation class with n binary words, so the number of binary words in C is divisible by n. Therefore 2n - 2 is divisible by n. ∎
Let A = {a, b, c, d} be a subset of Vn, equipped with the operation bitwise XOR. Let a be the binary word with all zeros and b be the binary word with all ones. Let c and d be any other pair of complementary binary words. Then A is a Klein four-group, where a is the identity element.
Dynamical Components
The functional digraph of the induced map has one vertex for each necklace and one directed edge P → D(P). A component means a weakly connected component: connectivity is tested after forgetting edge directions. It contains the image of each of its vertices and every preimage of each vertex. Starting from any necklace, repeatedly taking images and all preimages recovers its entire component.
At width one, D(0) = 0 and D(1) = 0. The preimages of 0 are 0 and 1, while 1 has no preimage. These two necklaces form the width-one component.
The set of necklaces is the quotient set Vn/⟨α⟩. It is distinct from Vn: each of its elements represents a whole rotation class of words.
Grouping necklaces by their components gives another partition of the words in Vn: take the union of the rotation classes in each component. Every word belongs to one necklace and every necklace to one component. Thus the partition into rotation classes refines the partition into these component basins.
V3 has eight binary words, which are partitioned into four rotation classes, which are partitioned into two components.
Every component of a finite functional digraph contains exactly one directed cycle, with rooted trees feeding into it. Here the cycle is a sequence of necklaces whose successive images follow the sequence. The image of the final necklace is the first; a fixed necklace is a cycle of length one.
The first cycle with multiple necklaces has representatives 00011 → 10010 → 11110 → 00011.
The second cycle with multiple necklaces has representatives 000101 → 111100 → 000101.
Each cycle vertex is the root of an incoming rooted tree, whose edges point toward the cycle. Its two necklace preimages are its predecessor on the cycle and one transient predecessor. The cycle edge is not counted as a tree edge. Vertices with no preimages are the leaves.
V4 is partitioned by a single component. The cycle of that component has a single root, so the component has only one tree. Using primitive representatives, one path from a leaf to the root is 0001 → 0011 → 01 → 1 → 0; reading backward gives successive preimages. 0011 also has the preimage 1110. 0001 and 1110 are the two leaves of the tree.
Trees vary in how many levels of successive preimages they have.
The component that comprises V8 has nine levels of preimages, including the root.
Restrict n to only powers of two. The component that comprises Vn has n + 1 levels of preimages, including the root.
These incoming trees are level-regular: vertices at the same depth have the same number of children. Their branching is related to whether the preimage necklaces coincide under complementation. A branching sequence records the number of preimages at successive depths, with the convention at the cycle root specified below.
Write the branching sequence as (b0, b1, ..., bh), where h is the tree depth and the root has depth zero. For internal depths, bj counts the children of a vertex at depth j. By convention, b0 = 2 counts both the incoming cycle edge and the one incoming tree edge. At the leaves, bh = 0. This sequence is a local encoding of the level-regular tree, with the cycle edge included only at the root.
| The branching sequence of the unique tree in ... | ||
| ... V1 is (2, 0). | ||
| ... V2 is (2, 1, 0). | ||
| ... V4 is (2, 1, 1, 2, 0). | ||
| ... V8 is (2, 1, 1, 2, 1, 2, 2, 2, 0). | ||
| ... V16 is (2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 0). | ||
For shorthand, the branching sequence may be written as a word over the alphabet {0, 1, 2}.
The branching sequence of the unique tree at width 16 is 21121222122222220.
Symmetry
A binary word is a palindrome if reversing the order of its bits leaves it unchanged. Otherwise it is non-palindromic. Two distinct words form a reversal pair when each is the reverse of the other.
100010 and 010001 are non-palindromic and form a reversal pair. The word 100001 is a palindrome.
A necklace is achiral if reversing a representative gives a rotation of that representative. Its rotation class is then closed under reversal. A palindromic representative is sufficient, but is not necessary at even length: the necklace represented by 01 is achiral although neither word 01 nor 10 is a palindrome.
The necklace represented by 11010 is achiral. Its rotation class contains one palindrome and two reversal pairs: {11010, 01101, 10110, 01011, 10101}.
Every necklace of length five is achiral. A set of primitive representatives is {0, 1, 00001, 11110, 11100, 00011, 01101, 10010}.
A necklace is chiral if its reversal is a distinct necklace. A chiral necklace X has a reflected partner Y, whose words are the reversals of the words in X. Identifying rotation and reflection together would instead give a binary bracelet; necklaces here identify rotations only.
The rotation classes of the words 1001110 and 0111001 are displayed below with reverse pairs aligned vertically.
| {1001110, 0011101, 0111010, 1110100, 1101001, 1010011, 0100111} |
| {0111001, 1011100, 0101110, 0010111, 1001011, 1100101, 1110010} |
Reversal induces an involution on the necklace functional graph and sends components to components. A component is reflection-invariant if reversal preserves its vertex set; otherwise it has a distinct reflected partner. A reflection-invariant component can contain chiral necklaces, so its symmetry is not determined by requiring every vertex to be achiral. A reflected pair consists of two distinct components.
The necklaces represented by 0001101 and 1110010 form one component at width seven. Reversing them gives its distinct reflected partner.
Geometrically, a necklace is achiral exactly when its circular arrangement has a reflection axis. Depending on the length and arrangement, the axis may pass through positions or between them.
Graphs
A component is a directed graph whose vertices are necklaces and whose edges point from each necklace to its image under adjacent XOR. Its directed cycle is a subgraph. The order of a graph is its number of vertices. Two components are isomorphic if a bijection between their vertices preserves the directed edges. For the level-regular components here, the cycle length and branching sequence determine the directed-graph isomorphism type.
Graph types are named Gx-y, where x is the cycle length and y is the branching sequence written as a word. These are identifiers used here, not universal graph notation. The same isomorphism type can occur at several widths.
At width one there is one graph type, called G1-20. This type occurs at every odd width.
G1-21120 appears in V4, V12 and V20.
Width five is the first width with two graph types. They are named G1-20 and G3-20.
Three components in V11 are isomorphic. Their graph has cycle length 31 and branching sequence (2, 0).
Let x and y be nonnegative integers with x < y. Repetition embeds the unique component at width 2x as a subgraph of the unique component at width 2y.
There are 2,097,152 binary words of length 21. They form 99,880 rotation classes, partitioned into 20 reflection-invariant components and 398 reflected pairs, giving 816 components in total. These components fall into six directed-graph isomorphism types. All six have branching sequence (2, 0), and their cycle lengths are 1, 3, 7, 9, 21, and 63.
Isomorphic components need not have the same behavior under reflection.
The component containing the necklace represented by 000000001 is reflection-invariant, while the component containing the necklace represented by 000001011 has a distinct reflected partner. Both have cycle length 7 and branching sequence (2, 0).
The component containing the necklace represented by 0000000001 is reflection-invariant, while the component containing the necklace represented by 0000001011 has a distinct reflected partner. Both have cycle length 6 and branching sequence (2, 2, 0).
Isomorphic components need not represent the same number of words. Their necklaces can have different spatial periods and therefore different rotation-class sizes. The number of represented words is the component's mass.
At width 12 there are two isomorphic components with six necklaces each. Each has a one-vertex cycle. One component has mass 16 and the other mass 48; their cycle necklaces have primitive representatives 0 and 011, respectively.
Space-Time Diagrams and Tessellations
A space-time diagram records successive states as rows, with position running horizontally and iteration vertically; repetition is not part of its definition. A necklace cycle gives a periodic example for the binary Ducci map. Choose a representative word on the cycle and apply adjacent XOR to obtain successive rows. Here the evolution runs upward: align neighboring bits so that their sum modulo two appears above and between them. Returning to the same necklace may rotate the row, so one circuit of the cycle can correspond to a vertical shift combined with a horizontal shift.
| 0 | 1 | 0 | 0 | 1 | |||||
| 1 | 0 | 0 | 0 | 1 | |||||
| 0 | 1 | 1 | 1 | 1 |
Continue the evolution upward and repeat the rows horizontally. The adjacent-XOR map commutes with repetition: if A = uk denotes k concatenated copies of u, then D(A) = D(u)k. The image D(u) need not itself be primitive. This rule lets the cycle define a repeating diagram on the plane.
| 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | ||||||||||
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | ||||||||||
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | ||||||||||
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | ||||||||||
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | ||||||||||
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
A cycle supplies a repeating region of the space-time diagram; its period lattice may include a horizontal shift after one circuit of the necklace cycle. The same information can be rendered geometrically as a tessellation, or tiling: a covering of the plane by tiles without gaps or overlapping interiors. The tessellations constructed here are periodic, although periodicity is not required of tessellations in general. In the rendering below, zeros and ones are replaced by lines and triangles: lines connect the positions of ones, and inverted triangles are filled.
See how the tessellation below corresponds to the zeros and ones in the space-time diagram above.
Appendix
From this question on StackExchange.
Binary words are vectors in the vector space Vn = F2n. Rotation and adjacent XOR are linear transformations. The first two matrices below represent those maps for n = 6. The third matrix, S, selects a preimage whose first bit is zero on the even-parity image of D; it is not an inverse of D on the whole word space. Each displayed matrix has n rows and columns.
The adjacent-XOR matrix is D = I + R, where R is the matrix of the cyclic rotation α and I is the identity matrix. The entries are added modulo two.
These matrices act on words. Commutation with rotation makes adjacent XOR well defined on necklaces as well. Its image consists exactly of the even-weight words, and its kernel consists of the all-zero and all-one words. Every even-weight target has two word preimages, which are complements; these may represent one necklace or two distinct necklaces. The displayed preimage-selection matrix chooses one of them on that image. On an odd-weight target there is no preimage, so its output cannot be interpreted as one.
