Omega(n log n) Boolean Circuit Lower Bound for Integer Multiplication

Omega(n log n) Boolean Circuit Lower Bound for Integer Multiplication

Definitions and mathematical statement

An input consists of two nonnegative integers $a,b<2^n$, each encoded by $n$ bits. The circuit must output all $2n$ bits of the exact product $ab$. Let $C_{\mathrm{mult}}(n)$ be the minimum gate count among acyclic circuits whose gates are arbitrary two-input Boolean functions, with unrestricted depth and fan-out. The target is \[ \exists c>0\ \exists N\ \forall n\ge N, \qquad C_{\mathrm{mult}}(n)\ge c n\log_2n. \] There is no uniform construction requirement on the circuit family. Restricting gates, wiring geometry, depth, or coefficient sizes would change the model and cannot establish this unrestricted lower bound by itself.

Formulation and concept references: [S1].

Short English statement

Must every Boolean circuit that multiplies two n-bit integers use at least a constant times n log n gates, even with unrestricted depth and wiring?

Research attempt

Current frontier.

The selected model permits every binary Boolean gate and unlimited fan-out. Afshani--Freksen--Kamma--Larsen prove an $\Omega(n\log n)$ lower bound for bounded-degree multiplication circuits conditional on the undirected $k$-pairs network-coding conjecture, and obtain a corresponding conditional bound for shifting [S1], [E1], Theorems 1--2. This is not an unconditional superlinear lower bound. The attempt below checks that their model restriction can be removed with only linear overhead, then tests whether elementary convolution or information-counting arguments can remove the remaining conjectural input.

Attack route.

Three routes suggest themselves. First, transfer the network-coding obstruction carefully to unrestricted fan-out. Second, embed carry-free convolution and use a lower bound there. Third, sum information requirements over the restrictions in which one input is a power of two. The first route succeeds conditionally. The second loses precisely a logarithmic packing factor. The third would need a direct-sum principle for gates shared by different input restrictions; that principle is not available and cannot be presumed.

Attempt.

Fan-out normalization lemma. A circuit with $s$ binary gates, $2n$ inputs and $2n$ designated outputs can be replaced by a bounded-in-degree, bounded-out-degree circuit with $O(s+n)$ gates computing the same function. Count wire occurrences into gates and outputs, rather than distinct signal values. There are at most $2s+2n$ such occurrences. For any signal used $r>2$ times, distribute it through a binary tree of copying gates. A copying gate is the permitted binary Boolean function $(x,y)\mapsto x$, with its input signal supplied to the first slot; the unused second slot can use the same signal. Counting parallel occurrences changes the degree bound only by an absolute factor. The number of added gates is at most a constant times $r$. Summing over all signals gives at most $C(2s+2n)$ additional gates. Original input nodes are treated in the same way. The construction is acyclic and requires neither uniformity nor bounded depth.

Apply Theorem 1 of [E1] to the normalized circuit. Under its undirected $k$-pairs conjecture, \[ C'(s+n)\ge c_0 n\log_2n. \] Therefore $s\ge(c_0/C')n\log_2n-n\ge c_1n\log_2n$ for all sufficiently large $n$. This proves the exact printed target conditionally, including its unrestricted fan-out convention. In particular, bounded-degree terminology in the cited theorem is not a fatal mismatch, but the network-coding hypothesis remains indispensable to this deduction.

To identify that hypothesis precisely, take a finite undirected capacitated network with designated source--sink pairs. The conjecture equates its optimal simultaneous network-coding rate with the maximum concurrent multicommodity-flow rate. The cited proof needs the resulting domination of the coding rate of a directed acyclic network by the flow rate after forgetting directions [E1], Conjecture 1 and Section 2. A circuit gives a coding network, not automatically a routing of independent commodities. Replacing the former by the latter without this input would simply assume the difficult step.

An unconditional baseline. For $n\ge2$, there are $2n$ distinct nonconstant output-bit functions, none an input-bit function. For each $0\le k\le2n-2$, choose $i,j<n$ with $i+j=k$ and inputs $a=2^i,b=2^j$. Their product has only bit $k$ set, distinguishing that output from every other output. The highest bit is nonzero on $(a,b)=(2^n-1,2^n-1)$ since $(2^n-1)^2\ge2^{2n-1}$. No product-bit function equals any $a$-input bit because setting $b=0$ kills all product bits, and similarly with $a,b$ reversed. Every output must therefore be furnished by a distinct gate. Hence \[ C_{\mathrm{mult}}(n)\ge2n\qquad(n\ge2). \] This only counts required output functions. It provides no logarithmic factor.

Carry-free packing stress calculation. Let $x_i,y_i\in\{0,1\}$ for $0\le i<t$, choose $B=2^b>t$, and encode \[ a=\sum_{i=0}^{t-1}x_iB^i,\qquad b'=\sum_{i=0}^{t-1}y_iB^i. \] Every coefficient of their formal product is at most $t$, so ordinary integer multiplication has no carries between these base-$B$ blocks and exposes the Boolean convolution counts. But its bit length is $n=\Theta(t\log t)$. Even an $\Omega(t\log t)$ convolution lower bound transferred through this encoding gives only $\Omega(n)$, not $\Omega(n\log n)$. Avoiding carries is not cost-free. A claimed proof that identifies $t$ with $n$ after choosing $b\asymp\log t$ has lost the central factor.

Finally, restrictions $b'=2^j$ force the circuit to perform different shifts. They are mutually exclusive input cases, not independent simultaneous messages. A single gate can behave differently under every such restriction. Summing a linear lower bound over all $j$ without charging shared gates only once would be an invalid direct-sum argument. The conditional network-coding proof is precisely a way to make a nontrivial simultaneous information comparison rather than this naïve summation.

Stress test.

The copying argument counts gate inputs and designated outputs, so arbitrary fan-out has not been silently reintroduced at no charge. Constant factors in degree and size are independent of $n$. The argument uses the source theorem as an external theorem with its full hypothesis; it does not reprove or verify the network-coding conjecture. The linear bound assumes outputs are wires carrying input or gate values, as in the stated circuit model, not free arbitrary Boolean postprocessing. Its small exceptional case $n=1$ is irrelevant to the asymptotic target. The accompanying script checks carry-free packing on exhaustive short bit strings, but those identities cannot prove a circuit lower bound.

Outcome.

Outcome: Conditional reduction. The known network-coding conditional theorem implies the exact unrestricted-fan-out target after an explicit $O(s+n)$ normalization. An unconditional $2n$ baseline and two failed routes to the extra logarithm were also established. There is no new unconditional superlinear bound: the missing input is the cited coding-to-routing principle, or a different argument that controls shared Boolean computation without it.

Sources

• S1 P. Afshani, C. B. Freksen, L. Kamma and K. G. Larsen, Lower Bounds for Multiplication via Network Coding, ICALP 2019, 10:1–10:12. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.10. Catalogue formulation source.
• E1 Peyman Afshani, Casper Benjamin Freksen, Lior Kamma and Kasper Green Larsen, Lower Bounds for Multiplication via Network Coding, arXiv:1902.10935v1; ICALP 2019, LIPIcs 132, article 10. Conjecture 1, Theorems 1--2, and Section 2 specify the conditional bridge used here. https://arxiv.org/html/1902.10935v1. Research reference; consulted 27 September 2026.