We study the circuit cost of selecting $k$ objects satisfying orthogonality, zero XOR, or modular zero SUM. Our main lower bounds in nonuniform $\mathsf{AC}^0$ use a common framework of depth-zero projections from colored subgraph isomorphism. The projections use dimension, row count, or bit width $O(k\log n)$ and preserve circuit size, depth, and gate orientation. OV inputs satisfy pairwise distinctness within each array. Our direct XOR bounds require odd $k$, while SUM admits both parities. Stronger lower bounds for suitable source patterns transfer through the same framework to all three targets.

For every fixed depth $d$ and sufficiently large fixed $k$, we prove unconditional lower bounds $n^{\Omega(k)}$ for OV and $(n/k)^{\Omega(k)}$ for XOR and SUM, with an absolute constant in the exponent independent of $d$ and $k$; only the threshold on $n$ may depend on $(d,k)$. For $k\to\infty$ with $k=n^{o(1)}$, combining our projections with Beame's small-clique lower bound yields $n^{\Omega_d(\min\{\sqrt{k},\log n\})}$ at every fixed depth $d$. We strengthen the exponent to $\Omega(k)$ at depth two in both orientations and at depth three with a top disjunction. The depth-three result allows unrestricted bottom fan-in and literal polarity; its proof bounds the probability that a planted copy forms a minterm of an arbitrary fixed CNF over a random background.

We show that a pattern-uniform strengthening of the Li--Razborov--Rossman lower bound would give $n^{\Omega_d(k)}$ in the same growing-$k$ regime for depth three with a top conjunction and every fixed depth $d\ge4$. This is our only conditional main result; no running-time hypothesis is used. Supplementary results cover general budgets (dimension, row count, bit width), an odd-to-even XOR lift under explicit arithmetic conditions, and upper bounds. At SUM bit-width $m=\Theta(k\log(\mathrm{e} n/k))$ with a sufficiently large constant factor, a top-disjunction depth-three upper bound of size $(n/k)^{O(k)}$ matches our $(n/k)^{\Omega(k)}$ lower bound up to constants in the exponent, for sufficiently large $k$ and $n\ge k^C$ with a suitable constant $C>1$.

Streamlined the main body to focus on core results; simplified symbols and resolved conflicting notations; improved and simplified proof details.

We prove lower bounds for $k$-$\mathrm{OV}$, $k$-$\mathrm{XOR}$, and $k$-$\mathrm{SUM}$ in nonuniform $\mathrm{AC}^0$, tracking how the circuit-size exponent scales with $k$ and using no running-time hypothesis. Our framework gives depth-zero projections from colored subgraph isomorphism to the three targets at dimension, row count, or bit width $O(k \log n)$, without increasing depth or size, and preserving gate orientation. For every fixed depth and every sufficiently large fixed $k$, we obtain unconditional bounds $n^{\Omega(k)}$ for $k$-$\mathrm{OV}$ and $(n/k)^{\Omega(k)}$ for $k$-$\mathrm{XOR}$ and $k$-$\mathrm{SUM}$, with an absolute exponent-rate constant independent of both $k$ and the depth, while the onset threshold may depend on $(d,k)$. For growing $k = n^{o(1)}$, we obtain, for every fixed depth $d$, the unconditional floor $n^{\Omega_d(\min\{\sqrt{k},\log n\})}$. This strengthens to $n^{\Omega(k)}$ at depth two for both top-gate orientations, i.e., top conjunction and top disjunction, and at depth three for top-disjunction circuits $\mathrm{OR} \circ \mathrm{AND} \circ \mathrm{OR}$, with no restriction on bottom fan-in or literal polarity. The depth-three argument rests on a minterm bound for a single CNF: a fixed CNF is very unlikely to become true for the first time exactly when a randomly planted copy is completed, with no circuit-correctness hypothesis. Assuming a pattern-uniform strengthening of the Li–Razborov–Rossman source lower bound, the same projections complete the $k = n^{o(1)}$ frontier with $n^{\Omega_d(k)}$ for the missing top-conjunction depth-three orientation and for every fixed depth $d \geq 4$. The interface of our projection framework does not depend on which source lower bound is used, so new lower bounds for suitable source families or improved source exponents pass directly to all three targets. All direct $k$-$\mathrm{XOR}$ bounds stated above concern odd $k$; a black-box odd-to-even lift transfers any such lower bound through a supplied admissible parameter decomposition. The $k$-$\mathrm{SUM}$ projection works for both parities. At the bit width $m = \Theta(k \log(\mathrm{e}n/k))$ used by our projection, a block-carry $\Sigma_3$ upper bound of size $(n/k)^{O(k)}$ matches the top-disjunction depth-three lower bound $(n/k)^{\Omega(k)}$ up to constants in the exponent. The remaining upper-versus-lower-bound gaps concern depth two, top-conjunction depth three, and other width regimes.

(Fixed ECCC webpage display issues)

This version adds an unconditional depth-three lower bound result for top-disjunction (OR-AND-OR) circuits with an exponent linear in growing $k$; adds worked toy instances that display the projection to each of the three targets; and revises the presentation throughout, correcting typos, simplifying overloaded notations and terminologies, and adding pointers to the formal definitions and statements.

We prove lower bounds for $k$-$\mathsf{OV}$, $k$-$\mathsf{XOR}$, and $k$-$\mathsf{SUM}$ in nonuniform $\mathsf{AC}^0$, tracking how the circuit-size exponent scales with $k$ and using no running-time hypothesis. Our framework gives depth-zero projections from colored subgraph isomorphism to the three targets at dimension, row count, or bit width $O(k \log n)$, without increasing depth or size, and preserving gate orientation. For every fixed depth and every sufficiently large fixed $k$, we obtain unconditional bounds $n^{\Omega(k)}$ for $k$-$\mathsf{OV}$ and $(n/k)^{\Omega(k)}$ for $k$-$\mathsf{XOR}$ and $k$-$\mathsf{SUM}$, with an absolute exponent-rate constant independent of both $k$ and the depth, while the onset threshold may depend on $(d,k)$. For growing $k = n^{o(1)}$, we obtain, for every fixed depth $d$, the unconditional floor $n^{\Omega_d(\min\{\sqrt{k},\log n\})}$. This strengthens to $n^{\Omega(k)}$ at depth two for both top-gate orientations, i.e., top conjunction and top disjunction, and at depth three for top-disjunction circuits $\mathsf{OR} \circ \mathsf{AND} \circ \mathsf{OR}$, with no restriction on bottom fan-in or literal polarity. The depth-three argument rests on a minterm bound for a single CNF: a fixed CNF is very unlikely to become true for the first time exactly when a randomly planted copy is completed, with no circuit-correctness hypothesis. Assuming a pattern-uniform strengthening of the Li–Razborov–Rossman source lower bound, the same projections complete the $k = n^{o(1)}$ frontier with $n^{\Omega_d(k)}$ for the missing top-conjunction depth-three orientation and for every fixed depth $d \geq 4$. The interface of our projection framework does not depend on which source lower bound is used, so new lower bounds for suitable source families or improved source exponents pass directly to all three targets. All direct $k$-$\mathsf{XOR}$ bounds stated above concern odd $k$; a black-box odd-to-even lift transfers any such lower bound through a supplied admissible parameter decomposition. The $k$-$\mathsf{SUM}$ projection works for both parities. At the bit width $m = \Theta(k \log(\mathrm{e}n/k))$ used by our projection, a block-carry $\Sigma_3$ upper bound of size $(n/k)^{O(k)}$ matches the top-disjunction depth-three lower bound $(n/k)^{\Omega(k)}$ up to constants in the exponent. The remaining upper-versus-lower-bound gaps concern depth two, top-conjunction depth three, and other width regimes.

This version adds an unconditional depth-three lower bound result for top-disjunction (OR-AND-OR) circuits with an exponent linear in growing $k$; adds worked toy instances that display the projection to each of the three targets; and revises the presentation throughout, correcting typos, simplifying overloaded notations and terminologies, and adding pointers to the formal definitions and statements.

We prove lower bounds for $k$-OV, $k$-XOR, and $k$-SUM in nonuniform AC$^0$, tracking how the circuit-size exponent scales with $k$ and using no running-time hypothesis. Our framework gives depth-zero projections from colored subgraph isomorphism to the three targets at dimension, row count, or bit width $O(k\log n)$, without increasing depth or size, and preserving gate orientation. For every fixed depth and every sufficiently large fixed $k$, we obtain unconditional bounds $n^{\Omega(k)}$ for $k$-OV and $(n/k)^{\Omega(k)}$ for $k$-XOR and $k$-SUM, with an absolute exponent-rate constant independent of both $k$ and the depth, while the onset threshold may depend on $(d,k)$. For growing $k = n^{o(1)}$, we obtain, for every fixed depth $d$, the unconditional floor $n^{\Omega_d(\min\{\sqrt{k},\log n\})}$. This strengthens to $n^{\Omega(k)}$ at depth two for both top-gate orientations, i.e., top conjunction and top disjunction. Assuming a pattern-uniform strengthening of the Li--Razborov--Rossman source lower bound, the same projections complete the subpolynomial frontier with $n^{\Omega_d(k)}$ at depth three for both orientations and for every fixed depth $d \geq 4$. All direct $k$-XOR bounds stated above concern odd $k$; a black-box odd-to-even lift transfers any such lower bound through a supplied admissible parameter decomposition. The $k$-SUM projection works for both parities. At the bit width $m = \Theta(k\log(en/k))$ used by our projection, a block-carry $\Sigma_3$ upper bound of size $(n/k)^{O(k)}$ matches the fixed-$k$ specialization of the top-disjunction depth-three lower bound $(n/k)^{\Omega(k)}$ up to constants in the exponent. The remaining upper-versus-lower-bound gaps concern depth two, top-conjunction depth three, and other width regimes.