Documentation

ToCslib.Algebra.PolynomialGrowth

Polynomial growth against 2 ^ n #

Every fixed power, every constant multiple of a shifted power, and hence every natural-number polynomial is eventually dominated by 2 ^ n; the polynomial bound is stated against 2 ^ (n / 4) so that it can be fed to a machine-counting argument whose count at size 2 ^ (n / 4) must stay below 2 ^ (2 ^ n). These are Mathlib candidates and import nothing from PolyFun.

Any fixed power is eventually dominated by 2 ^ n.

A constant multiple of any fixed power of n + 1 is eventually dominated by 2 ^ n.

Polynomials are eventually dominated by 2 ^ (n / 4). The exponent n / 4 is the threshold fed to the machine count: fast enough to eventually exceed every polynomial description bound (this lemma), yet slow enough that the resulting machine count stays below 2 ^ (2 ^ n) (eventually_count_lt).