Documentation

Complexitylib.Algebraic.MassProduction.UhligTheorem

Uhlig's sharp mass-production theorem #

This module turns the exact two-copy recursion into the classical 2 ^ o(n / log n) statement. The asymptotic hypothesis is expressed by ordinary natural-number inequalities, and synthesis data is passed explicitly rather than through typeclass instances.

The finite recursive theorem and its asymptotic estimates live in focused supporting modules. This module assembles them into the sharp theorem, parameterized by a sharp one-copy synthesis family. The separate Lupanov module discharges that premise.

Conditional sharp Uhlig theorem #

Uhlig's theorem, reduced exactly to sharp one-copy synthesis. Any explicit synthesis family with normalized coefficient one remains sharp for every copy budget 2 ^ depth(n) with depth(n) * log_2(n) = o(n).