Concept icon
Concept

Combining the tuple bound with tapered precision

Choose theta=sqrt(M/(D p_t)). The generating-product estimate gives at most exp(13 sqrt(M p_t/D)) tuples, using sum_{h>=1}1/h^2<=2. Tapered recovery provides p_t=O_C(MD/u), so the number becomes exp(O_C(M/sqrt(u))). D cancels because p_t is linear in D; the tapered 1/u factor yields the 1/sqrt(u) saving. A looser bound proportional to MD would still cancel D but would give only exp(O_C(M)), without that saving. Here exp and ln use natural logarithms; changing a fixed logarithm base only changes constants in the asymptotic exponent.

0

1

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math