Size of constant depth circuit for digital comparator?

Question

Is a lower bound of $\Omega(n^2)$ known for the size of any constant depth circuit expressing a digital comparator for two $n$-bit numbers?

Two $n$-bit binary numbers can be compared using a digital comparator circuit. The straightforward way to implement such a circuit is to compare the high-order bits; if they are the same then continue to compare the second most significant bits, and so on. This circuit has size (measured in the number of gates) that is roughly quadratic in $n$, with linear depth. By standard arguments, this can be folded up into an equivalent circuit of roughly the same size that has logarithmic depth (in $n$).

In fact, constant depth circuits of size $O(n^2)$ are sufficient for a digital comparator, if unbounded fan-in gates are allowed: see Heribert Vollmer's Introduction to Circuit Complexity (Exercise 1.4). Is a tight lower bound known?

Answer 1

Comparison can be implemented by subtracting twos-complement numbers and then testing whether the most significant bit is 0 or 1. Subtraction can be implemented as addition ($x-y = x + \overline{y} + 1$, where $\overline{y}$ is obtained by flipping all bits of $y$). Addition can be implemented using carry-lookahead methods.

If you put all this together, I think you get a comparison circuit that uses $O(n)$ gates and has constant depth.

In particular, let $g_i = a_i \land b_i$ ("generate"), $p_i = a_i \lor b_i$ ("propagate"), $q_i = p_{i+1} \lor \cdots \lor p_{n-1}$, $t_i = g_i \land q_i$, and $c_{n-1} = t_0 \lor \cdots \lor t_{n-2}$ ("carry"). This lets you compute the carry into the most significant bit in constant-depth and $O(n)$ gates. That's all you need for the results of the comparison (you don't need to compute the value of the other bits of the sum). The reason this requires fewer gates than a full addition or full subtraction is that we only need the carry into the most significant bit, not all the carry bits.

Double-check my reasoning -- I could have gone awry somewhere.