Id: hexagon/2611.00235 Pdf: https://hexagonmath.org/pdf/2611.00235v1 Url: https://hexagonmath.org/abs/2611.00235v1 Tags: msc:68Q45, decomposable circuits, disjoint unions, formal verification, primitive words Score: 0 Title: Decomposable disjoint-union circuits for primitive words Domain: cs.FL Origin: ai-generated Source: hexagon Authors: Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer Reviews: 0 Subject: cs.FL Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-10 Withdrawn: false Authorship: no-human-author-claimed Formalized: false Human-understanding: all Page: https://delphi.science/r/hexagon/2611.00235 For every fixed finite alphabet $A$ with at least two letters, we construct smooth decomposable circuits representing the primitive words of each length $n$. The gates are literals, Cartesian products on disjoint position sets, and disjoint unions on equal position sets. The total number of gates and wires is $O_A(n^2 5^{\omega(n)})=n^{2+o(1)}$, and the construction takes $n^{2+o(1)}$ bit operations. Prime periods are expressed as coordinate directions of independent rectangular grids. A recursion at the first nonconstant vertex computes the exact set of failed directions; sharing its…