\documentclass[11pt,letterpaper]{amsart}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage{lmodern,microtype,amsmath,amssymb,amsthm,mathtools}
\usepackage{enumitem,booktabs}
\usepackage[hidelinks]{hyperref}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\eps}{\varepsilon}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\dist}{dist}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\dom}{dom}
\newcommand{\sem}[1]{\left[\!\left[#1\right]\!\right]}
\newcommand{\Fail}{\mathop{\rm Fail}}
\newcommand{\Prim}{\mathop{\rm Prim}}
\newcommand{\size}[1]{\lvert #1\rvert}

\title[Circuits for primitive words]{Decomposable disjoint-union circuits for primitive words}
\author{Will Howe}
\email{howew@purdue.edu}
\author{Grant Huffman}
\email{huffma97@purdue.edu}
\author{Jensen Kohlmeyer}
\email{jenwin@purdue.edu}
\author{Liam Kruer}
\email{kruerl@purdue.edu}
\thanks{Prepared with AI assistance from OpenAI Codex in mathematical exploration,
checking, and manuscript preparation.}
\date{November 7, 2026}
\keywords{Primitive words, decomposable circuits, disjoint unions, knowledge compilation}

\begin{document}
\begin{abstract}
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
continuations gives the size bound. This resolves the primitive-word
instance of the circuit question posed by Amarilli, Monet, Rapha\"el, and
Salvati. It does not determine whether primitive words form a context-free
or a poly-slicewise-unambiguous language. The same circuit bound holds for
any union of exact power orders at a fixed length.
\end{abstract}
\maketitle

\section{Statement and circuit model}

A nonempty word is \emph{primitive} if it is not a power $u^d$ with $d\geq2$.
The empty word is excluded. Write $\Prim_A(n)\subseteq A^n$ for the primitive
words of length $n$, and let $\omega(n)$ be the number of distinct prime
divisors of the positive integer $n$, with $\omega(1)=0$.

Amarilli, Monet, Rapha\"el, and Salvati introduced a multivalued circuit
framework for probabilistic language membership \cite[Section~5]{AMRS26}.
Their construction for primitive words uses complementation, and
\cite[Section~6]{AMRS26} asks whether complementation can be avoided for
this language. We use their circuit model, with the conventions made
explicit below. Their quadratic arithmetic algorithm for probabilistic
membership is already available; the result here concerns the form and
size of a representation.

Fix a finite set $U$ of positions. An assignment on $D\subseteq U$ is a
function $D\to A$. A circuit is a finite directed acyclic graph, with a
designated output, built from the following gates.
\begin{enumerate}[label=(\roman*),leftmargin=*]
\item A literal $i:a$ has domain $\{i\}$ and represents the one assignment
      sending $i$ to $a$.
\item A product gate has inputs with pairwise disjoint domains. Its domain
      is their union, and its assignments are all unions of one assignment
      from each input.
\item A union gate has inputs with the same domain and pairwise disjoint
      represented sets. It represents their union, with that common domain.
\end{enumerate}
These requirements are called \emph{decomposability}, \emph{smoothness}, and
\emph{disjointness}, respectively. We allow the nullary product, of domain
$\varnothing$, representing the unique empty assignment, and the nullary
union, of domain $\varnothing$, representing no assignment. The domain of
every other gate is the union of its input domains. Thus the nullary union
alone cannot represent the empty set on a prescribed nonempty domain.
We denote the set represented by a gate $c$ by $\sem c$. The size of a
circuit is its number of gates plus its number of wires. Fan-out is
unrestricted, so a constructed gate may be shared by several later gates.
Positions may be relabeled by any bijection without changing these
properties or the size.

\begin{theorem}\label{thm:main}
Fix a finite alphabet $A$, with $|A|\geq2$. For each integer $n\geq1$ there
is a smooth decomposable disjoint-union circuit with domain
$\{0,\ldots,n-1\}$ representing exactly $\Prim_A(n)$ and having size
\[
 O_A\!\left(n^2 5^{\omega(n)}\right).
\]
One algorithm constructs these circuits in $n^{2+o(1)}$ bit operations
as a function of $n$. The empty slice is represented by a nullary union.
\end{theorem}

Here and below $A$ is fixed, so constants may depend on $|A|$. Construction
time is measured in the represented length $n$, or equivalently with $n$
given in unary. A stronger intermediate bound will be
\begin{equation}\label{eq:strongbound}
 O_A\!\left(n\prod_{p\mid n,\ p\text{ prime}}(1+4p)\right).
\end{equation}
Products in this model may combine interlaced position sets. The theorem
does not provide a context-free grammar or a family of polynomial-size
unambiguous context-free grammars for the slices. These language-theoretic
questions are separate from the circuit question; see also the discussion
of primitive words in \cite[Section~6]{AMRSfull}.

\section{From periods to independent grids}

We identify positions of a length-$n$ word with $\Z/n\Z$. For a divisor
$d\mid n$, a word is invariant under shift $d$ if
$w(j+d)=w(j)$ for all positions $j$.

\begin{lemma}\label{lem:primeperiod}
Let $n\geq2$, and let $P$ be its set of distinct prime divisors. A word
$w\in A^n$ is primitive if and only if it fails to be invariant under
shift $n/p$ for every $p\in P$.
\end{lemma}
\begin{proof}
If $w=u^d$ with $d\geq2$, then $d\mid n$. Choose a prime $p\mid d$ and
write $w=(u^{d/p})^p$. It is invariant under shift $n/p$. Conversely, the
orbits of shift $n/p$ are the sets
$\{i,i+n/p,\ldots,i+(p-1)n/p\}$ for $0\leq i<n/p$. Invariance therefore
says precisely that $w$ is the $p$th power of its prefix of length $n/p$.
\end{proof}

Set
\[
 R=\prod_{p\in P}p,\qquad g=n/R,\qquad k=|P|.
\]
Every shift $n/p$ preserves the residue of a position modulo $g$.
Within residue class $r$, $0\leq r<g$, write a position uniquely as
$r+gt$, where $t\in\Z/R\Z$. Use the Chinese remainder bijection
\begin{equation}\label{eq:crt}
 \Z/R\Z\longrightarrow\prod_{p\in P}\Z/p\Z,
 \qquad t\longmapsto(t\bmod p)_{p\in P}.
\end{equation}
Shift $n/p$ adds $R/p$ to $t$. In these coordinates it fixes every
coordinate other than $p$, and adds the nonzero residue $R/p\bmod p$ in
coordinate $p$. Repeated addition visits all $p$ values of that coordinate.
Thus the $g$ residue classes form $g$ independent copies of a rectangular
grid with side lengths $p\in P$.

For a labeled grid, call an axis \emph{failed} if at least one line parallel
to it is not constant. The set of failed axes is its \emph{mask}.
The preceding observations prove the following statement.

\begin{lemma}\label{lem:gridperiod}
The word fails shift $n/p$ exactly when axis $p$ fails in at least one of
the $g$ grids. Its primitive-word condition is therefore that the union
of the masks of the $g$ grids is $P$.
\end{lemma}

We next construct circuits for each exact grid mask. Exactness will make
all unions in the construction disjoint.

\section{The constant-prefix recursion}

For this section take any ordered finite set $I$ of axes, with integer
side lengths $q_i\geq2$. Write
\[
 X=\prod_{i\in I}\{0,\ldots,q_i-1\},\qquad
 V=|X|=\prod_{i\in I}q_i.
\]
A \emph{subgrid} fixes the coordinates outside some $T\subseteq I$ and
varies all the coordinates in $T$. Its varying axes are $T$, its size is
$v_T=\prod_{i\in T}q_i$, and its vertices inherit lexicographic order
from the ordered axes. In particular, a subgrid with no varying axes
has a single vertex.

Let $G=(x_0,\ldots,x_{v-1})$ be an ordered subgrid with varying axes $T$.
For a labeling $f:G\to A$ define
\[
 \Fail_G(f)=\left\{i\in T:
  \begin{array}{l}
  \text{there exist $x,y\in G$ equal in every coordinate except $i$,}\\[-2pt]
  \text{with $f(x)\ne f(y)$}
  \end{array}\right\}.
\]
For $1\leq t\leq v$, $b\in A$, and $M\subseteq T$, let
$\mathcal S(G,t,b,M)$ be the assignments on
$G_{\geq t}=\{x_t,\ldots,x_{v-1}\}$ whose extension by the value $b$ on
$x_0,\ldots,x_{t-1}$ has mask exactly $M$. Let
$\mathcal B(G,M)$ be the assignments on all of $G$ with mask exactly $M$.
The constant prefix is a condition on the represented assignments, and
its positions are outside their domain.

We will represent every nonempty one of these sets by a gate. If a state
is empty, we record that fact and create no gate for it. A proposed
product involving an empty state is omitted, and unions range only over
nonempty inputs. This convention respects the structural definition of
domain above. Feasibility is determined during the same recursion,
without examining all assignments.

\begin{lemma}[first differing vertex]\label{lem:first}
Let $1\leq t\leq v$, and complete a prefix of $t$ copies of $b$ to a
nonconstant labeling of $G$. Let $x_s$ be its first vertex whose label
$a$ differs from $b$. Put
\[
 F=F(x_s)=\{i\in T:(x_s)_i\ne0\},\qquad U=T\setminus F.
\]
Then $s\geq t$, $F$ is nonempty, and every axis in $F$ fails. Partition
$G$ into subgrids $H$ by fixing all coordinates in $F$, so that each $H$
has varying axes $U$. The following hold.
\begin{enumerate}[label=(\roman*),leftmargin=*]
\item In the subgrid $H_*$ containing $x_s$, that vertex is first, and
      no earlier vertex of $G$ lies in $H_*$.
\item In every other $H$, the vertices preceding $x_s$ in $G$ form an
      initial segment of $H$, all labeled $b$.
\item For $i\in U$, axis $i$ fails in $G$ if and only if it fails in at
      least one of these subgrids.
\end{enumerate}
Consequently, for every such completed labeling $f$,
\begin{equation}\label{eq:maskidentity}
 \Fail_G(f)=F\cup\bigcup_H\Fail_H(f|_H).
\end{equation}
\end{lemma}
\begin{proof}
The first vertex $x_0$ has all varying coordinates zero. Since $s\geq
t\geq1$, we have $x_s\ne x_0$ and hence $F\ne\varnothing$. For each
$i\in F$, reset coordinate $i$ of $x_s$ to zero, keeping all others fixed.
The resulting vertex precedes $x_s$ in lexicographic order, so its label
is $b$, whereas the label of $x_s$ is $a$. The two vertices share an
$i$-axis line, and that line is nonconstant.

Every coordinate of $x_s$ in $U$ is zero. After the $F$ coordinates are
fixed to those of $x_s$, it is therefore the first vertex of $H_*$.
Lexicographic order on any other $H$ is the restriction of the order on
$G$. Intersecting an initial segment of $G$ with $H$ gives an initial
segment of $H$, proving (ii). Finally, any line in an axis $i\in U$
has fixed $F$ coordinates. It is contained in one $H$, and the $i$-lines
of all the $H$ are exactly the $i$-lines of $G$. This proves (iii) and
\eqref{eq:maskidentity}.
\end{proof}

We spell out the use of exact masks in combining subgrids.

\begin{lemma}[combining exact masks]\label{lem:combine}
Suppose $D_1,\ldots,D_h$ are pairwise disjoint position sets. For each
$j$ suppose gates on domain $D_j$ represent pairwise disjoint families
$\mathcal L_{j,N}$ indexed by $N\subseteq U$, with empty families
recorded as absent. There is a smooth decomposable disjoint-union
construction representing, for every $M\subseteq U$,
\begin{equation}\label{eq:combine}
 \bigcup_{N_1\cup\cdots\cup N_h=M}
 \mathcal L_{1,N_1}\times\cdots\times\mathcal L_{h,N_h}
\end{equation}
using $O(h4^{|U|})$ new gates and wires. All nonempty resulting states
have domain $D_1\cup\cdots\cup D_h$.
\end{lemma}
\begin{proof}
Start with the nullary product at mask $\varnothing$ and no state at any
other mask. After processing $j$ domains, keep one state $E_{j,M}$ for
each nonempty family with accumulated mask $M$. For every nonempty pair
$E_{j-1,B}$ and $\mathcal L_{j,N}$, form their product and attach it to
the union for $E_{j,B\cup N}$. These products are decomposable. For a
fixed resulting mask, all products have domain $D_1\cup\cdots\cup D_j$.
An assignment on this domain determines its restrictions to the first
$j-1$ domains and to $D_j$. Pairwise disjointness of the state families
then determines both $B$ and $N$ uniquely. Thus the union is disjoint.
Induction proves \eqref{eq:combine} and pairwise disjointness across its
different masks. At each step there are at most $4^{|U|}$ mask pairs,
so the claimed bound counts both gates and wires. Empty states are
recognized by the absence of a nonempty pair.
\end{proof}

\begin{proposition}\label{prop:recursion}
For every subgrid $G$ and every admissible $t,b,M$, the nonempty sets
$\mathcal S(G,t,b,M)$ and $\mathcal B(G,M)$ admit circuits of the specified
type. All these circuits can be constructed simultaneously by induction
on the number of varying axes.
\end{proposition}
\begin{proof}
Suppose the construction is available on subgrids with fewer than
$|T|$ varying axes. For each $b$ the constant completion contributes the
single all-$b$ assignment on $G_{\geq t}$ to
$\mathcal S(G,t,b,\varnothing)$. It is represented by a product of
literals; when the domain is empty this is the nullary product.

For a nonconstant completion, fix its first differing index $s\geq t$
and its letter $a\ne b$. Use $F,U$, and the subgrids $H$ of
Lemma~\ref{lem:first}. They have fewer varying axes because $F$ is
nonempty. For $H\ne H_*$ let
\[
 r_H=|H\cap\{x_0,\ldots,x_{s-1}\}|.
\]
If $r_H=0$, use the states $\mathcal B(H,N)$ on all of $H$. If
$r_H\geq1$, use $\mathcal S(H,r_H,b,N)$ on the remaining suffix of $H$.
For $H_*$ use $\mathcal S(H_*,1,a,N)$. In every case the prescribed
prefix lies outside the state's domain. These remaining domains
partition $G_{>s}=\{x_{s+1},\ldots,x_{v-1}\}$.

Apply Lemma~\ref{lem:combine} to these states. Denote the gate of
accumulated mask $N\subseteq U$, if nonempty, by $K_{G,s,b,a,N}$.
It has domain $G_{>s}$. To obtain a branch for the original suffix,
multiply it by the assignment $b$ on
$\{x_t,\ldots,x_{s-1}\}$ and by the literal $x_s:a$. The three
domains are disjoint, and their union is $G_{\geq t}$. By
\eqref{eq:maskidentity}, this branch contributes precisely to
\begin{equation}\label{eq:branchmask}
 \mathcal S(G,t,b,F\cup N).
\end{equation}
For each required mask take the union of these branches and the
constant branch, if appropriate. Their domains agree. Two nonconstant
branches are disjoint because their completed labelings have different
first differing positions or different letters at that position. For
fixed $s,a$, masks $N$ are exact and pairwise disjoint; moreover
$F\cup N=M$ determines $N=M\setminus F$. The constant branch is disjoint
from every nonconstant branch. Lemma~\ref{lem:first} shows that every
completion occurs in the prescribed branch, so these gates represent
exactly the claimed sets.

Finally, form $\mathcal B(G,M)$ by the disjoint union, over $b\in A$,
of the literal $x_0:b$ times the state
$\mathcal S(G,1,b,M)$, omitting absent states. The two factors have
disjoint domains. The resulting branches all have domain $G$, and their
first letters make them pairwise disjoint.

When $T=\varnothing$, $G$ is a singleton. The only possible mask is
$\varnothing$; its states at $t=1$ are nullary products, and
$\mathcal B(G,\varnothing)$ is the disjoint union of the literals at
its one position. No nonconstant branch occurs. This supplies the base
case, including all empty-domain states used above.
\end{proof}

\section{Sharing and the size bound}

The induction alone gives a circuit construction. The following count
depends on sharing a continuation across all compatible prefix lengths.

\begin{lemma}\label{lem:localcost}
Let $G$ have $v$ vertices and $m$ varying axes. Besides gates already
constructed on its proper subgrids, all its states in
Proposition~\ref{prop:recursion} require $O_A(v^2 4^m)$ gates and wires.
\end{lemma}
\begin{proof}
We first build the constant assignment of letter $b$ on every interval
$\{x_i,\ldots,x_{j-1}\}$, $0\leq i\leq j\leq v$. For fixed $i,b$,
start with the nullary product and append one literal at a time. Each
extension uses a binary decomposable product. This costs $O_A(v^2)$
gates and wires in total. Literals can be shared wherever they recur.

For fixed $s\geq1$, $b$, and $a\ne b$, the partition into $H$, all
numbers $r_H$, and the distinguished state with letter $a$ depend only
on $G,s,b,a$. They do not depend on $t\leq s$. The core gates
$K_{G,s,b,a,N}$ are therefore built once and shared for every such $t$.
There are at most $v$ subgrids in this partition, and at most $m$
remaining axes. Lemma~\ref{lem:combine} bounds the cost of one core by
$O(v4^m)$. There are $O_A(v)$ choices of $s,b,a$, so all cores cost
$O_A(v^2 4^m)$.

For each $t,s,b,a,N$ the branch in \eqref{eq:branchmask} is one product
with at most three inputs. The number of choices is
$O_A(v^2 2^m)$. Attach each to the union for its unique output mask
$F(x_s)\cup N$. There are at most $O_A(v2^m)$ suffix states and
$O_A(2^m)$ full-grid states, and the latter have at most $|A|$ inputs
each. Counting their wires as well as their gates adds
$O_A(v^2 2^m)$. Absent states and branches decrease these counts.
Together with the constant intervals this proves the bound.
\end{proof}

\begin{proposition}\label{prop:gridcost}
All exact-mask circuits for the full grid $X$ can be constructed
simultaneously with size
\begin{equation}\label{eq:gridcost}
 O_A\!\left(V\prod_{i\in I}(1+4q_i)\right).
\end{equation}
The number of bit operations is this bound times a polynomial in
$|I|+\log(V+1)$.
\end{proposition}
\begin{proof}
For fixed varying axes $T$, there are $V/v_T$ subgrids, one for each
choice of their fixed coordinates. Summing Lemma~\ref{lem:localcost}
over every subgrid gives
\begin{align*}
 \sum_{T\subseteq I}\frac{V}{v_T}\,O_A(v_T^2 4^{|T|})
 &=O_A\!\left(V\sum_{T\subseteq I}\prod_{i\in T}(4q_i)\right)\\
 &=O_A\!\left(V\prod_{i\in I}(1+4q_i)\right).
\end{align*}
Build subgrids in increasing order of $|T|$, then cores, suffix states,
and full-grid states, as in the proofs. This is a topological construction.
Represent a subgrid by its varying-axis set and fixed coordinates, a
vertex by its coordinate tuple, and a mask by a bit vector. All indices
have polynomial length in $|I|+\log(V+1)$. For each possible differing
vertex one may scan all $v_T$ vertices to obtain the partition and the
prefix lengths $r_H$; over all vertices this takes
$O(v_T^2)$ coordinate operations. Every remaining loop has one iteration
per state, mask pair, or wire counted above. Feasibility flags are
propagated by conjunction at products and disjunction at unions. Thus
all indexing, arithmetic, and feasibility work fit within the stated
polynomial factor.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
For $n\geq2$ apply Proposition~\ref{prop:gridcost} to each of the $g$
grids from \eqref{eq:crt}, with $q_p=p$. Their total size is
\[
 O_A\!\left(gR\prod_{p\in P}(1+4p)\right)
 =O_A\!\left(n\prod_{p\in P}(1+4p)\right).
\]
Combine their exact masks by Lemma~\ref{lem:combine}, at additional
cost $O(g4^k)$, and choose the output with mask $P$. The grid position
sets are disjoint, so all products remain decomposable. By
Lemmas~\ref{lem:primeperiod} and~\ref{lem:gridperiod}, the chosen output
represents precisely $\Prim_A(n)$. This output is nonempty: for distinct
$a,b\in A$, the word $a^{n-1}b$ is primitive, because the number of
occurrences of $b$ in a $d$th power would be divisible by $d$.
The additional cost is absorbed by the displayed bound. Indeed,
$g4^k\leq gR\prod_{p\in P}(1+4p)$. As $1+4p\leq5p$ and $R\leq n$,
this proves both \eqref{eq:strongbound} and $O_A(n^2 5^k)$.

For completeness, $5^{\omega(n)}=n^{o(1)}$ follows without a prime
number estimate. If the $k$ distinct primes are increasing, the $j$th
is at least $j+1$, so $(k+1)!\leq n$. For $k\geq4$, at least $k/2$
factors in this factorial are at least $k/2$, whence
\[
 \log n\geq\frac{k}{2}\log(k/2).
\]
It follows that $k=o(\log n)$: when $k$ is large the ratio
$k/\log n$ is at most $2/\log(k/2)$, and bounded values of $k$ also
give a vanishing ratio. Thus $5^k=n^{o(1)}$. Also $k\leq\log_2 n$, so
any fixed polynomial in $k+\log n$ is $n^{o(1)}$.

Trial division finds the distinct primes of $n$ within the stated time.
The position relabeling can be tabulated by enumerating
$0\leq r<g$ and $0\leq t<R$ and computing the residues in
\eqref{eq:crt}; no search over assignments is involved. Together with
Proposition~\ref{prop:gridcost}, these facts give construction time
$n^{2+o(1)}$ in the bit model. For $n=1$, use the disjoint union of the
$|A|$ literals at its sole position. For $n=0$, use the nullary union.
\end{proof}

\section{Exact power orders}

We finish with a consequence for the exact order of a word. The usual
uniqueness of a primitive root can be proved directly in the cyclic
notation used here.

\begin{lemma}\label{lem:root}
Every nonempty word $w$ has a unique expression $w=u^d$ with $u$
primitive and $d\geq1$.
\end{lemma}
\begin{proof}
For a word of length $n$, let
\[
 H=\{h\in\Z:w(j+h)=w(j)\text{ for every }j\in\Z/n\Z\}.
\]
This is an additive subgroup of $\Z$ containing $n\Z$, so $H=m\Z$
for a positive divisor $m$ of $n$. The word is the $(n/m)$th power of
its prefix $u$ of length $m$. If $u$ were a proper power, its shorter
block length would belong to $H$, contrary to minimality of $m$.

If also $w=v^e$ with $v$ primitive, then $|v|\in H$ and hence
$m\mid |v|$. Invariance under shift $m$ says that the prefix $v$ is
itself a power of the prefix of length $m$. Primitivity forces
$|v|=m$, so $v=u$ and $e=n/m$.
\end{proof}

Call $d$ in Lemma~\ref{lem:root} the \emph{order} of $w$.

\begin{corollary}\label{cor:orders}
Fix $A$ as in Theorem~\ref{thm:main}. For any $n\geq1$ and any set
$D$ of positive divisors of $n$, the length-$n$ words whose orders belong
to $D$ have a smooth decomposable disjoint-union circuit of size
$O_A(n^2 5^{\omega(n)})$, constructible in $n^{2+o(1)}$ bit operations.
This includes a circuit for each individual exact order.
\end{corollary}
\begin{proof}
Fix $d\mid n$ and put $m=n/d$. A word has order $d$ exactly when it is
$u^d$ for $u\in\Prim_A(m)$. Take the circuit of
Theorem~\ref{thm:main} for length $m$. For every literal $i:a$, replace
it by the product of the $d$ literals
\[
 i:a,\ (i+m):a,\ \ldots,\ (i+(d-1)m):a.
\]
For distinct source positions $i$, the corresponding position sets are
disjoint. Consequently every original product stays decomposable,
and equal original domains give equal expanded domains. The expansion
of an assignment is injective: restriction to the first $m$ positions
recovers it. Disjoint unions therefore remain disjoint. The output
represents exactly the words of order $d$.

Share equal source literals before replacing them. There are at most
$|A|m$ of them, so the replacements add $O_A(n)$ gates and wires.
The circuit for this order has size
\[
 O_A\!\left((n/d)^2 5^{\omega(n/d)}+n\right).
\]
Construct such circuits separately for $d\in D$ and take the union
of their outputs. All domains are the same, and the outputs are
pairwise disjoint by Lemma~\ref{lem:root}. Finally,
\[
 \sum_{d\mid n}(n/d)^2 5^{\omega(n/d)}
 \leq n^2 5^{\omega(n)}\sum_{d=1}^{\infty}d^{-2}
 \leq 2n^2 5^{\omega(n)},
\]
where the last inequality follows by comparing the terms from $d=2$
onwards with $\int_1^\infty x^{-2}\,dx$. Also $n$ times the number of
divisors of $n$ is at most $n^2$. These estimates give the size bound.
The same summation, with the polynomial indexing factors already
bounded uniformly in $\log n$, proves the construction-time bound.
If $D$ is empty, a constant assignment on the full domain multiplied
by a nullary union gives the required empty output with size $O(n)$.
\end{proof}

\begin{thebibliography}{9}
\raggedright

\bibitem{AMRS26}
Antoine Amarilli, Mika\"el Monet, Paul Rapha\"el, and Sylvain Salvati,
\emph{On the complexity of language membership for probabilistic words},
in \emph{43rd International Symposium on Theoretical Aspects of Computer
Science (STACS 2026)}, Leibniz International Proceedings in Informatics
\textbf{364} (2026), article 5, 5:1--5:21.
\href{https://doi.org/10.4230/LIPIcs.STACS.2026.5}{doi:10.4230/LIPIcs.STACS.2026.5}.

\bibitem{AMRSfull}
Antoine Amarilli, Mika\"el Monet, Paul Rapha\"el, and Sylvain Salvati,
\emph{On the complexity of language membership for probabilistic words},
full version, arXiv:2510.08127v2, 22 June 2026.
\url{https://arxiv.org/abs/2510.08127v2}.

\end{thebibliography}
\end{document}