Balanced finite-monoid reduction circuit ($\text{size }O(n),\text{depth }O(\log n)$)

A fixed finite monoid operation has a constant-size Boolean truth-table Boolean circuit on its constant-bit encodings. Reduce $n$ elements in a balanced binary tree to get linear size and logarithmic depth. Associativity ensures that tree grouping does not change the product. MOD3 uses addition in the three-element residue group, with input-position signs handled at the leaves.