Decomposable disjoint-union circuits for primitive words

Statement and circuit model

A nonempty word is primitive if it is not a power $u^{d}$ with $d \ge2$. The empty word is excluded.

Write $\operatorname{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ël, and Salvati introduced a multivalued circuit framework for probabilistic language membership [1 Section 5]. Their construction for primitive words uses complementation, and [1 Section 6] 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.

1. A literal $i : a$ has domain $\{i\}$ and represents the one assignment sending $i$ to $a$.

2. 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.

3. A union gate has inputs with the same domain and pairwise disjoint represented sets. It represents their union, with that common domain.

These requirements are called decomposability, smoothness, and 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 $[\![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.

having size

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.

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

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 [2 Section 6].

From periods to independent grids

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

Set

Every shift $n/p$ preserves the residue of a position modulo $g$. Within residue class $r$, $0\le r<g$, write a position uniquely as $r+gt$, where $t\in\mathbb{Z}/R\mathbb{Z}$. Use the Chinese remainder bijection

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 failed if at least one line parallel to it is not constant. The set of failed axes is its mask. The preceding observations prove the following statement.

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

The constant-prefix recursion

For this section take any ordered finite set $I$ of axes, with integer side lengths $q_i \ge2$. Write

A 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

For $1\le t\le v$, $b\in A$, and $M\subseteq T$, let $\mathcal{S}(G,t,b,M)$ be the assignments on $G_{\ge 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.

Proof. The first vertex $x_0$ has all varying coordinates zero. Since $s\ge t\ge1$, 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 (3.1). $\square$

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

using $O(h4^{|U|})$ new gates and wires. All nonempty resulting states have domain $D_1 \cup\cdots\cup D_h$.

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 $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 (3.2) 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.

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.

Proof. We first build the constant assignment of letter $b$ on every interval $\{x_i,\ldots,x_{j-1}\}$, $0 \le i \le j \le 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 \ge1$, $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 \le 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 3.2 bounds the cost of one core by $O(v^4m)$. There are $O_A(v)$ choices of $s,b,a$, so all cores cost $O_A(v^{24m})$.

For each $t,s,b,a,N$ the branch in (5) is one product with at most three inputs. The number of choices is $O_A(v^{2m})$. Attach each to the union for its unique output mask $F(x_s) \cup N$. There are at most $O_A(v^{2m})$ 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^{22m})$. Absent states and branches decrease these counts. Together with the constant intervals this proves the bound. □

Proof. For fixed varying axes $T$, there are $V/v_T$ subgrids, one for each choice of their fixed coordinates. Summing Lemma 4.1 over every subgrid gives

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. □

Proof of Theorem 1.1. For $n \ge2$ apply Proposition 4.2 to each of the $g$ grids from (2), with $q_p=p$. Their total size is

Combine their exact masks by Lemma 3.2, 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 2.1 and 2.2, the chosen output represents precisely $\operatorname{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 \le gR\prod_{p\in P}(1+4p)$. As $1+4p\le5p$ and $R\le n$, this proves both (1.1) and $O_A(n^25^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)! \le n$. For $k \ge4$, at least $k/2$ factors in this factorial are at least $k/2$, whence

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 \le\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 \le r < g$ and $0 \le t < R$ and computing the residues in (2); no search over assignments is involved. Together with Proposition 4.2, 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. □

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.

Proof. For a word of length $n$, let

This is an additive subgroup of $\mathbb{Z}$ containing $n\mathbb{Z}$, so $H=m\mathbb{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$. □

Call $d$ in Lemma 5.1 the order of $w$.

Proof. Fix $d\mid n$ and put $m=n/d$. A word has order $d$ exactly when it is $u^d$ for $u\in\operatorname{Prim}_A(m)$. Take the circuit of Theorem 1.1 for length $m$. For every literal $i:a$, replace it by the product of the $d$ literals

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

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 5.1. Finally,

where the last inequality follows by comparing the terms from $d=2$ onwards with $\int_{1}^{\infty}x^{-2}\,\mathrm{d}x$. 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)$. □

References

Email address: [email protected]

Email address: [email protected]

Email address: [email protected]

Email address: [email protected]