DLOGTIME uniform iterated addition threshold circuits

Two-word addition has the following constant-depth Boolean construction. For $d$-bit words $a,b$, put $g_j=a_j\wedge b_j$ and $p_j=a_j\vee b_j$. The carry entering bit $k>0$ is $c_k={\bigvee }_{0\le j<k}(g_j\wedge {\bigwedge }_{j<t<k}{p}_t),c_0=0.$ A carry is generated by two ones, propagated through positions with at least one one, and killed by two zeros; this proves the formula. The output bit is the XOR of $a_k,b_k,c_k$, computed by its constant-size Boolean truth table, with the final carry appended. These formulas have constant depth and polynomial size, and predecessor tests use equality and order on their bit-position addresses.

For $m\ge 2$, let $\mathrm{\ell }=\lceil {\log }_{2}m\rceil$, let $b$ be the least power of two at least $\mathrm{\ell }$, and put $B=2^b$. Then $m\le B\le m^2$. Split each input into consecutive $b$-bit blocks and pad the last block with zeros. For block $q$, define $S_q={\sum }_{i=0}^{m-1}{\sum }_{r=0}^{b-1}{2}^r{x}_{i,qb+r}\mathrm{.}$ Its upper bound is $C=m(B-1)$, polynomial in $mw$.

To compute all bits of $S_q$, pad the row domain to a power of two $M_0\ge m$ with $M_0<2m$. Create a rectangular set of distinct copy gates $(i,r,t)$ with $0\le i<M_0$, $0\le r<b$, and $0\le t<B$. Gates with $i\ge m$ or $t\ge 2^r$ are zero; otherwise they copy $x_{i,qb+r}$. There are $D=M_{0}bB$ slots, a power of two polynomial in $mw$, and exactly $S_q$ slots are true. For each $1\le h\le D$, feed these slots and $D+1$ distinct constant slots to a MAJ gate, with exactly $D-h+1$ constant slots equal to one. Its odd fan-in is $2D+1$, so under either convention for majority it tests $S_q+(D-h+1)\ge D+1$, equivalently $S_q\ge h$. Write this output as $T_{q,h}$ and set $T_{q,0}=1$, $T_{q,D+1}=0$. Then $E_{q,h}=T_{q,h}\wedge \mathrm{\neg }{T}_{q,h+1}$ tests $S_q=h$, and bit $u$ of $S_q$ is the OR of $E_{q,h}$ over the indices $h$ having bit $u$ equal to one. The depth is constant and the size polynomial.

Write $S_q=r_q+B{v}_q$. Since $r_q<B$ and $v_q<m\le B$, form two words: $R$ has block $q$ equal to $r_q$, and $V$ has block $q+1$ equal to $v_q$ and block zero zero. These bits are direct selections from the bits computed in step 2.1. The blocks do not overlap within either word, and ${\sum }_{i=0}^{m-1}{x}_i={\sum }_q{S}_q{B}^q=R+V\mathrm{.}$ Apply step 1.1 once to $R,V$. This is a constant number of constant-depth stages of polynomial total size.

We verify uniformity explicitly. Use fixed-length tuples with a constant number of $O(\log (mw+2))$-bit fields for gate type, block, row, within-block bit, copy, threshold, output-bit and constant-slot indices. All predecessor predicates in step 1.1 and step 1.2 and step 2.1 and step 3.1 use equality, order, the bit predicate on $h$, $t<2^r$, the constant-slot test $u<D-h+1$, and $j=qb+r$. Since $b$ is a power of two, the last relation is a shift and concatenation. The exponent of the power of two $D=M_{0}bB$ is the sum of the corresponding bit-length exponents. Testing $t<2^r$ compares $r$ with the highest nonzero bit position of $t$. Determine the field widths and $b$ from the binary dimensions and perform these tests by a constant number of linear scans, additions, subtractions, shifts and comparisons of $O(\log (mw+2))$-bit words. Each gate-type or predecessor query takes $O(\log (mw+2))$ time on the random-access uniformity machine; no general multiplication of two varying address fields is used. Dimensions and coordinate domains are padded to powers of two, and positions outside the actual input bounds are constant zero. For $m=1$, copy the input word. Finally ${\sum }_i{x}_i<m{2}^w\le 2^{w+\lceil {\log }_{2}m\rceil }$, so the retained output width is exactly the one in the Statement.