Skip to main content
added 404 characters in body
Source Link
Willie Wong
  • 39k
  • 4
  • 94
  • 176

For the concrete question you ask, the answer is yes.

Your set $A$ is in fact the set of all numbers between $0$ and $1$ with binary expansion that has no more than 3 bits equaling 1.

Let $\ell_+ = \lceil \log_2 n \rceil$ and $\ell_- = \lfloor \log_2 n \rfloor$. You can estimate

$$ n' \geq (\ell_- - 1) + \binom{\ell_- - 1}{2} + \binom{\ell_- - 1}{3} \approx \ell_-^3 $$

On the other hand, the sum inside either the upper/lower sum can be bounded above byis between

$$ \sum_{i = 1}^{\ell_+} 2^{-i} + \sum_{i = 1}^{\ell_+} \sum_{j = i+1}^{\ell_+} (2^{-i} + 2^{-j}) + \sum_{i = 1}^{\ell_+} \sum_{j = i+1}^{\ell_+}\sum_{k = j+1}^{\ell_+} (2^{-i} + 2^{-j} + 2^{-k}) $$

(which is the sum of all numbers in $A$ with no more than 3 bits equaling 1 and least significant bit at least $2^{-\ell_+}$. This sum is) and

$$ \sum_{i = 1}^{\ell_+} 2^{-i} + \sum_{i = 1}^{\ell_+} \sum_{j = i+1}^{\ell_+} (2^{-i} + 2^{-j}) + \sum_{i = 1}^{\ell_+} \sum_{j = i+1}^{\ell_+}\sum_{k = j+1}^{\ell_+} (2^{-i} + 2^{-j} + 2^{-k}) $$$$ \sum_{i = 1}^{\ell_+} (2^{-i} + 2^{-\ell_-}) + \sum_{i = 1}^{\ell_+} \sum_{j = i+1}^{\ell_+} (2^{-i} + 2^{-j}+ 2^{-\ell_-}) + \sum_{i = 1}^{\ell_+} \sum_{j = i+1}^{\ell_+}\sum_{k = j+1}^{\ell_+} (2^{-i} + 2^{-j} + 2^{-k}+ 2^{-\ell_-}) $$

and this(which is the sum of the same set of numbers of the first sum, increased by the width of the interval).

The first sum is easily evaluated to be $O(\ell_+^2)$ (here we take advantage of the fact that at least one level of the summation converges using geometric series). The second sum is $O(\ell_+^2) + O(\ell_+^3 2^{-\ell_-})$.

So this means that both the upper sum and the lower sum behave like $\frac{C}{\log_2(n)} \to 0$ as $n \to +\infty$.

(This explains why your numerical computation goes very slow. At $n = 10^{-170}$, $\log_2(n)$ is something like 800. In fact, I don't even know if there is a reasonable numerical method for this, since to get convergence to the 10th decimal place, you will need a floating point arithmetic with a 2^30 bit mantissa to avoid numerical errors, or alternatively invent a new way to do exact arithmetic with rational numbers with very large numerators and denominators.)

For the concrete question you ask, the answer is yes.

Your set $A$ is in fact the set of all numbers between $0$ and $1$ with binary expansion that has no more than 3 bits equaling 1.

Let $\ell_+ = \lceil \log_2 n \rceil$ and $\ell_- = \lfloor \log_2 n \rfloor$. You can estimate

$$ n' \geq (\ell_- - 1) + \binom{\ell_- - 1}{2} + \binom{\ell_- - 1}{3} \approx \ell_-^3 $$

On the other hand, the sum inside either the upper/lower sum can be bounded above by the sum of all numbers in $A$ with no more than 3 bits equaling 1 and least significant bit at least $2^{-\ell_+}$. This sum is

$$ \sum_{i = 1}^{\ell_+} 2^{-i} + \sum_{i = 1}^{\ell_+} \sum_{j = i+1}^{\ell_+} (2^{-i} + 2^{-j}) + \sum_{i = 1}^{\ell_+} \sum_{j = i+1}^{\ell_+}\sum_{k = j+1}^{\ell_+} (2^{-i} + 2^{-j} + 2^{-k}) $$

and this sum is easily evaluated to be $O(\ell_+^2)$ (here we take advantage of the fact that at least one level of the summation converges using geometric series).

So this means that both the upper sum and the lower sum behave like $\frac{C}{\log_2(n)} \to 0$ as $n \to +\infty$.

(This explains why your numerical computation goes very slow. At $n = 10^{-170}$, $\log_2(n)$ is something like 800. In fact, I don't even know if there is a reasonable numerical method for this, since to get convergence to the 10th decimal place, you will need a floating point arithmetic with a 2^30 bit mantissa to avoid numerical errors, or alternatively invent a new way to do exact arithmetic with rational numbers with very large numerators and denominators.)

For the concrete question you ask, the answer is yes.

Your set $A$ is in fact the set of all numbers between $0$ and $1$ with binary expansion that has no more than 3 bits equaling 1.

Let $\ell_+ = \lceil \log_2 n \rceil$ and $\ell_- = \lfloor \log_2 n \rfloor$. You can estimate

$$ n' \geq (\ell_- - 1) + \binom{\ell_- - 1}{2} + \binom{\ell_- - 1}{3} \approx \ell_-^3 $$

On the other hand, the sum inside either the upper/lower sum is between

$$ \sum_{i = 1}^{\ell_+} 2^{-i} + \sum_{i = 1}^{\ell_+} \sum_{j = i+1}^{\ell_+} (2^{-i} + 2^{-j}) + \sum_{i = 1}^{\ell_+} \sum_{j = i+1}^{\ell_+}\sum_{k = j+1}^{\ell_+} (2^{-i} + 2^{-j} + 2^{-k}) $$

(which is the sum of all numbers in $A$ with no more than 3 bits equaling 1 and least significant bit at least $2^{-\ell_+}$) and

$$ \sum_{i = 1}^{\ell_+} (2^{-i} + 2^{-\ell_-}) + \sum_{i = 1}^{\ell_+} \sum_{j = i+1}^{\ell_+} (2^{-i} + 2^{-j}+ 2^{-\ell_-}) + \sum_{i = 1}^{\ell_+} \sum_{j = i+1}^{\ell_+}\sum_{k = j+1}^{\ell_+} (2^{-i} + 2^{-j} + 2^{-k}+ 2^{-\ell_-}) $$

(which is the sum of the same set of numbers of the first sum, increased by the width of the interval).

The first sum is easily evaluated to be $O(\ell_+^2)$ (here we take advantage of the fact that at least one level of the summation converges using geometric series). The second sum is $O(\ell_+^2) + O(\ell_+^3 2^{-\ell_-})$.

So this means that both the upper sum and the lower sum behave like $\frac{C}{\log_2(n)} \to 0$ as $n \to +\infty$.

(This explains why your numerical computation goes very slow. At $n = 10^{-170}$, $\log_2(n)$ is something like 800. In fact, I don't even know if there is a reasonable numerical method for this, since to get convergence to the 10th decimal place, you will need a floating point arithmetic with a 2^30 bit mantissa to avoid numerical errors, or alternatively invent a new way to do exact arithmetic with rational numbers with very large numerators and denominators.)

Source Link
Willie Wong
  • 39k
  • 4
  • 94
  • 176

For the concrete question you ask, the answer is yes.

Your set $A$ is in fact the set of all numbers between $0$ and $1$ with binary expansion that has no more than 3 bits equaling 1.

Let $\ell_+ = \lceil \log_2 n \rceil$ and $\ell_- = \lfloor \log_2 n \rfloor$. You can estimate

$$ n' \geq (\ell_- - 1) + \binom{\ell_- - 1}{2} + \binom{\ell_- - 1}{3} \approx \ell_-^3 $$

On the other hand, the sum inside either the upper/lower sum can be bounded above by the sum of all numbers in $A$ with no more than 3 bits equaling 1 and least significant bit at least $2^{-\ell_+}$. This sum is

$$ \sum_{i = 1}^{\ell_+} 2^{-i} + \sum_{i = 1}^{\ell_+} \sum_{j = i+1}^{\ell_+} (2^{-i} + 2^{-j}) + \sum_{i = 1}^{\ell_+} \sum_{j = i+1}^{\ell_+}\sum_{k = j+1}^{\ell_+} (2^{-i} + 2^{-j} + 2^{-k}) $$

and this sum is easily evaluated to be $O(\ell_+^2)$ (here we take advantage of the fact that at least one level of the summation converges using geometric series).

So this means that both the upper sum and the lower sum behave like $\frac{C}{\log_2(n)} \to 0$ as $n \to +\infty$.

(This explains why your numerical computation goes very slow. At $n = 10^{-170}$, $\log_2(n)$ is something like 800. In fact, I don't even know if there is a reasonable numerical method for this, since to get convergence to the 10th decimal place, you will need a floating point arithmetic with a 2^30 bit mantissa to avoid numerical errors, or alternatively invent a new way to do exact arithmetic with rational numbers with very large numerators and denominators.)