Integer multiplication complexity

Write two long numbers on paper. Ordinary long multiplication forms a row of partial products for each digit, so doubling their length roughly quadruples this work. Computers can combine digits much more efficiently. An algorithm now needs only about n log n bit operations for n-bit inputs. The open question is whether any general method can remove some of that logarithmic overhead.[1] [2] [4]

Two long binary numbers have to be multiplied exactly, with both inputs available before computation starts. Fast algorithms take $O(n\log n)$ bit steps. Is that logarithmic overhead unavoidable for every general method, once moving digits and writing the product are counted? The issue is a universal lower bound, not whether one implementation can be sped up.

Fix a deterministic machine M with a finite number of one-dimensional tapes, and let T_M(n) be its worst-case time to output the exact product of two n-bit binary integers. Optimality asks for T_M(n)=Ω(n log n) for every such multiplication machine, with constants allowed to depend on M. The achieved construction uses Gaussian resampling to reduce multiplication to multidimensional Fourier transforms whose dimensions are powers of two. Its precision analysis recovers exact integer coefficients despite approximate complex arithmetic.[1] [2] [3]

The fast upper bound is already proved. What is missing is a matching reason that every possible method must take that much work. Reading the inputs and writing an answer force a cost proportional to their length, but no stronger unconditional bound is known in the model used here. A 2025 reduction connects the missing bound to another unresolved data-rearrangement problem; it does not finish the proof.[2] [3]

The 2025 transposition reduction makes a concrete conditional advance. If transposing an r×r binary matrix requires Ω(r² log r) tape steps, the reduction implies an Ω(n log n) multiplication bound. The transposition premise is itself unproved in the unrestricted multitape model. Restrictions matter here: rearranging wires costs nothing in a Boolean circuit, so this particular reduction yields no circuit lower bound. Proving a bound for one restricted representation therefore leaves this target open.[3]

Multiplication is a basic ingredient in calculations involving very large integers and many digits of constants such as π. Knowing its true cost would clarify how far these arithmetic methods can improve. There is also a broader lesson: after inventing an extraordinarily efficient algorithm, researchers still have to show that an entirely different idea cannot do better.[2] [4]

Transpose the two-by-two array [a,b;c,d]: the output order changes from a,b,c,d to a,c,b,d while the bits’ values stay the same. On linear tapes, moving information to the right places takes work; in a circuit, the corresponding wires can simply be relabeled. Connecting this rearrangement task to multiplication isolates a possible source of arithmetic difficulty. The open optimality question is thus also a question about the power of the computational model, not just the number of arithmetic formulas.[3]