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
Updated 2026-11-08
Tags
Math