Less than that, with the appropriate compression scheme (sparse encoding).
> But then I got completely lost in the math to show why this guarantees anything.
You get guarantees on _relative_ error:
- 100 to 110 is a 10% error
- 1000 to 1010 is a 1% error
Depending on your logarithmic base, you can detect errors up to a certain relative %-tage.