Skip to main content
added 2 characters in body
Source Link
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763

I will show $\mu = \tfrac{1}{\log 4}$.


I first prove the upper bound $\mu \leq \tfrac{1}{\log 4}$. Fix a positive integer $r$. For $0 \leq k \leq r-1$, let $N_k$ be $2^{k/r} N$ rounded to the nearest integer, where $N$ is a large parameter. Considering the $N_{r-1}$ intervals present at time $N_{r-1}$, let $X_k$ be the number of them created between times $X_{k-1}$$N_{k-1}$ and $X_k$$N_k$; with $X_0$ the number created before time $0$$N_0$. Then $$X_0 \frac{\mu}{N_0} + X_1 \frac{\mu}{N_1} + \cdots + X_{r-1} \frac{\mu}{N_{r-1}} \leq 1.$$ Set $S_k=X_0+X_1+\cdots +X_k$; we can rewrite the above equation as $$\mu \left( S_0 \left(\frac{1}{N_0} - \frac{1}{N_1}\right) + S_1 \left(\frac{1}{N_1} - \frac{1}{N_2} \right) + \cdots + S_{r-2} \left(\frac{1}{N_{r-2}} - \frac{1}{N_{r-1}}\right) + S_{r-1} \frac{1}{N_{r-1}} \right) \leq 1.$$

Now, $S_k$ is the number of those intervals present at final time $N_{r-1}$ which were created before time $N_k$, so we have $S_k \geq N_k - (N_{r-1} - N_k)=2 N_k - N_{r-1}$. The coefficient $\tfrac{1}{N_k} - \tfrac{1}{N_{k+1}}$ on the left hand side is positive, so we have $$\mu \left( (2N_0-N_{r-1}) \left(\frac{1}{N_0} - \frac{1}{N_1}\right)+ (2N_1-N_{r-1}) \left(\frac{1}{N_1} - \frac{1}{N_2}\right)+\cdots+ (2N_{r-2}-N_{r-1}) \left(\frac{1}{N_{r-2}} - \frac{1}{N_{r-1}}\right)+\frac{N_{r-1}}{N_{r-1}} \right) \leq 1.$$

We gather terms with the same denominator to obtain $$\mu \left( \frac{2N_0-N_{r-1}}{N_0} + \frac{2 N_1 - 2 N_0}{N_1} + \cdots + \frac{2 N_{r-1} - 2 N_{r-2}}{N_{r-1}} \right) \leq 1$$ or $$\mu \left( 2r - \frac{N_{r-1}}{N_0} - \frac{2 N_0}{N_1} - \cdots - \frac{2 N_{r-2}}{N_{r-1}} \right) \leq 1.$$ Plugging in our optimized values: $$\mu \left( 2r - r 2^{(r-1)/r} \right) \leq 1$$ so $$\mu \leq \frac{1}{2r (1-2^{-1/r})}.$$

Finally, taking the limit as $r \to \infty$ gives $\mu \leq \tfrac{1}{\log 4}$ as promised.


Now, for the lower bound. Again, fix a positive integer $r$. Divide the circle into $r$ equal arcs; each arc will be subdivided into intervals. At any point in our process there will be some integer $k$ such that one arc is divided into some intervals of length $2^{-k/r}$ and some of length $2^{-(k+r)/r}$; the other $r-1$ arcs will contain intervals of only one length, namely $2^{-j/r}$ for $k<j<k+r$. (Obviously, I am ignoring rounding issues.) As time ticks on, we subdivide the intervals in the first arc until they are all split in half, then move to the next arc, and so on.

This achieves (again, ignoring rounding) $$\mu = 2^{-(k+r)/r} \left( \frac{2^{k/r}}{r} +\frac{2^{(k+1)/r}}{r} + \cdots \frac{2^{(k+r-1)/r}}{r} \right) = \frac{1}{2r(2^{1/r}-1)}.$$ Again, sending $r \to \infty$ achieves $\tfrac{1}{\log 4}$.


Here is a slicker, though less motivated way, to achieve the lower bound. We will number the points starting with $x_0$ at position $0$. For $n >0$, write $n = 2^q+r$ with $0 \leq r <2^q$ and put $x_n$ at $\log_2\left(\tfrac{2n+1}{2^{q+1}}\right)$. So the first few points are $0$, $\log_2(1+1/2)$, $\log_2(1+1/4)$, $\log_2(1+3/4)$, $\log_2(1+1/8)$, $\log_2(1+3/8)$, $\log_2(1+5/8)$, $\log_2(1+7/8)$, ... When point $x_n$ is inserted, the smallest interval will either be the one just to the right of $x_n$ or else the furthest right interval. Approximating $\log$ by its linearization, these have lengths roughly $\tfrac{2^{q+1}}{(2n+1) \log 2} \tfrac{1}{2^{q+1}}=\tfrac{1}{(2n+1) \log 2}$ and $\tfrac{1}{2 \log 2} \tfrac{1}{2^q}=\tfrac{1}{2^{q+1} \log 2}$ respectively.

Multiplying these by $n+1$ (the number of intervals) gives $\tfrac{n+1}{(2n+1) \log 2}$ and $\tfrac{n+1}{2^{q+1} \log 2}$. The former approaches $\tfrac{1}{\log 4}$ while the latter oscillates between $\tfrac{1}{\log 2}$ and $\tfrac{1}{\log 4}$.

I will show $\mu = \tfrac{1}{\log 4}$.


I first prove the upper bound $\mu \leq \tfrac{1}{\log 4}$. Fix a positive integer $r$. For $0 \leq k \leq r-1$, let $N_k$ be $2^{k/r} N$ rounded to the nearest integer, where $N$ is a large parameter. Considering the $N_{r-1}$ intervals present at time $N_{r-1}$, let $X_k$ be the number of them created between times $X_{k-1}$ and $X_k$; with $X_0$ the number created before time $0$. Then $$X_0 \frac{\mu}{N_0} + X_1 \frac{\mu}{N_1} + \cdots + X_{r-1} \frac{\mu}{N_{r-1}} \leq 1.$$ Set $S_k=X_0+X_1+\cdots +X_k$; we can rewrite the above equation as $$\mu \left( S_0 \left(\frac{1}{N_0} - \frac{1}{N_1}\right) + S_1 \left(\frac{1}{N_1} - \frac{1}{N_2} \right) + \cdots + S_{r-2} \left(\frac{1}{N_{r-2}} - \frac{1}{N_{r-1}}\right) + S_{r-1} \frac{1}{N_{r-1}} \right) \leq 1.$$

Now, $S_k$ is the number of those intervals present at final time $N_{r-1}$ which were created before time $N_k$, so we have $S_k \geq N_k - (N_{r-1} - N_k)=2 N_k - N_{r-1}$. The coefficient $\tfrac{1}{N_k} - \tfrac{1}{N_{k+1}}$ on the left hand side is positive, so we have $$\mu \left( (2N_0-N_{r-1}) \left(\frac{1}{N_0} - \frac{1}{N_1}\right)+ (2N_1-N_{r-1}) \left(\frac{1}{N_1} - \frac{1}{N_2}\right)+\cdots+ (2N_{r-2}-N_{r-1}) \left(\frac{1}{N_{r-2}} - \frac{1}{N_{r-1}}\right)+\frac{N_{r-1}}{N_{r-1}} \right) \leq 1.$$

We gather terms with the same denominator to obtain $$\mu \left( \frac{2N_0-N_{r-1}}{N_0} + \frac{2 N_1 - 2 N_0}{N_1} + \cdots + \frac{2 N_{r-1} - 2 N_{r-2}}{N_{r-1}} \right) \leq 1$$ or $$\mu \left( 2r - \frac{N_{r-1}}{N_0} - \frac{2 N_0}{N_1} - \cdots - \frac{2 N_{r-2}}{N_{r-1}} \right) \leq 1.$$ Plugging in our optimized values: $$\mu \left( 2r - r 2^{(r-1)/r} \right) \leq 1$$ so $$\mu \leq \frac{1}{2r (1-2^{-1/r})}.$$

Finally, taking the limit as $r \to \infty$ gives $\mu \leq \tfrac{1}{\log 4}$ as promised.


Now, for the lower bound. Again, fix a positive integer $r$. Divide the circle into $r$ equal arcs; each arc will be subdivided into intervals. At any point in our process there will be some integer $k$ such that one arc is divided into some intervals of length $2^{-k/r}$ and some of length $2^{-(k+r)/r}$; the other $r-1$ arcs will contain intervals of only one length, namely $2^{-j/r}$ for $k<j<k+r$. (Obviously, I am ignoring rounding issues.) As time ticks on, we subdivide the intervals in the first arc until they are all split in half, then move to the next arc, and so on.

This achieves (again, ignoring rounding) $$\mu = 2^{-(k+r)/r} \left( \frac{2^{k/r}}{r} +\frac{2^{(k+1)/r}}{r} + \cdots \frac{2^{(k+r-1)/r}}{r} \right) = \frac{1}{2r(2^{1/r}-1)}.$$ Again, sending $r \to \infty$ achieves $\tfrac{1}{\log 4}$.


Here is a slicker, though less motivated way, to achieve the lower bound. We will number the points starting with $x_0$ at position $0$. For $n >0$, write $n = 2^q+r$ with $0 \leq r <2^q$ and put $x_n$ at $\log_2\left(\tfrac{2n+1}{2^{q+1}}\right)$. So the first few points are $0$, $\log_2(1+1/2)$, $\log_2(1+1/4)$, $\log_2(1+3/4)$, $\log_2(1+1/8)$, $\log_2(1+3/8)$, $\log_2(1+5/8)$, $\log_2(1+7/8)$, ... When point $x_n$ is inserted, the smallest interval will either be the one just to the right of $x_n$ or else the furthest right interval. Approximating $\log$ by its linearization, these have lengths roughly $\tfrac{2^{q+1}}{(2n+1) \log 2} \tfrac{1}{2^{q+1}}=\tfrac{1}{(2n+1) \log 2}$ and $\tfrac{1}{2 \log 2} \tfrac{1}{2^q}=\tfrac{1}{2^{q+1} \log 2}$ respectively.

Multiplying these by $n+1$ (the number of intervals) gives $\tfrac{n+1}{(2n+1) \log 2}$ and $\tfrac{n+1}{2^{q+1} \log 2}$. The former approaches $\tfrac{1}{\log 4}$ while the latter oscillates between $\tfrac{1}{\log 2}$ and $\tfrac{1}{\log 4}$.

I will show $\mu = \tfrac{1}{\log 4}$.


I first prove the upper bound $\mu \leq \tfrac{1}{\log 4}$. Fix a positive integer $r$. For $0 \leq k \leq r-1$, let $N_k$ be $2^{k/r} N$ rounded to the nearest integer, where $N$ is a large parameter. Considering the $N_{r-1}$ intervals present at time $N_{r-1}$, let $X_k$ be the number of them created between times $N_{k-1}$ and $N_k$; with $X_0$ the number created before time $N_0$. Then $$X_0 \frac{\mu}{N_0} + X_1 \frac{\mu}{N_1} + \cdots + X_{r-1} \frac{\mu}{N_{r-1}} \leq 1.$$ Set $S_k=X_0+X_1+\cdots +X_k$; we can rewrite the above equation as $$\mu \left( S_0 \left(\frac{1}{N_0} - \frac{1}{N_1}\right) + S_1 \left(\frac{1}{N_1} - \frac{1}{N_2} \right) + \cdots + S_{r-2} \left(\frac{1}{N_{r-2}} - \frac{1}{N_{r-1}}\right) + S_{r-1} \frac{1}{N_{r-1}} \right) \leq 1.$$

Now, $S_k$ is the number of those intervals present at final time $N_{r-1}$ which were created before time $N_k$, so we have $S_k \geq N_k - (N_{r-1} - N_k)=2 N_k - N_{r-1}$. The coefficient $\tfrac{1}{N_k} - \tfrac{1}{N_{k+1}}$ on the left hand side is positive, so we have $$\mu \left( (2N_0-N_{r-1}) \left(\frac{1}{N_0} - \frac{1}{N_1}\right)+ (2N_1-N_{r-1}) \left(\frac{1}{N_1} - \frac{1}{N_2}\right)+\cdots+ (2N_{r-2}-N_{r-1}) \left(\frac{1}{N_{r-2}} - \frac{1}{N_{r-1}}\right)+\frac{N_{r-1}}{N_{r-1}} \right) \leq 1.$$

We gather terms with the same denominator to obtain $$\mu \left( \frac{2N_0-N_{r-1}}{N_0} + \frac{2 N_1 - 2 N_0}{N_1} + \cdots + \frac{2 N_{r-1} - 2 N_{r-2}}{N_{r-1}} \right) \leq 1$$ or $$\mu \left( 2r - \frac{N_{r-1}}{N_0} - \frac{2 N_0}{N_1} - \cdots - \frac{2 N_{r-2}}{N_{r-1}} \right) \leq 1.$$ Plugging in our optimized values: $$\mu \left( 2r - r 2^{(r-1)/r} \right) \leq 1$$ so $$\mu \leq \frac{1}{2r (1-2^{-1/r})}.$$

Finally, taking the limit as $r \to \infty$ gives $\mu \leq \tfrac{1}{\log 4}$ as promised.


Now, for the lower bound. Again, fix a positive integer $r$. Divide the circle into $r$ equal arcs; each arc will be subdivided into intervals. At any point in our process there will be some integer $k$ such that one arc is divided into some intervals of length $2^{-k/r}$ and some of length $2^{-(k+r)/r}$; the other $r-1$ arcs will contain intervals of only one length, namely $2^{-j/r}$ for $k<j<k+r$. (Obviously, I am ignoring rounding issues.) As time ticks on, we subdivide the intervals in the first arc until they are all split in half, then move to the next arc, and so on.

This achieves (again, ignoring rounding) $$\mu = 2^{-(k+r)/r} \left( \frac{2^{k/r}}{r} +\frac{2^{(k+1)/r}}{r} + \cdots \frac{2^{(k+r-1)/r}}{r} \right) = \frac{1}{2r(2^{1/r}-1)}.$$ Again, sending $r \to \infty$ achieves $\tfrac{1}{\log 4}$.


Here is a slicker, though less motivated way, to achieve the lower bound. We will number the points starting with $x_0$ at position $0$. For $n >0$, write $n = 2^q+r$ with $0 \leq r <2^q$ and put $x_n$ at $\log_2\left(\tfrac{2n+1}{2^{q+1}}\right)$. So the first few points are $0$, $\log_2(1+1/2)$, $\log_2(1+1/4)$, $\log_2(1+3/4)$, $\log_2(1+1/8)$, $\log_2(1+3/8)$, $\log_2(1+5/8)$, $\log_2(1+7/8)$, ... When point $x_n$ is inserted, the smallest interval will either be the one just to the right of $x_n$ or else the furthest right interval. Approximating $\log$ by its linearization, these have lengths roughly $\tfrac{2^{q+1}}{(2n+1) \log 2} \tfrac{1}{2^{q+1}}=\tfrac{1}{(2n+1) \log 2}$ and $\tfrac{1}{2 \log 2} \tfrac{1}{2^q}=\tfrac{1}{2^{q+1} \log 2}$ respectively.

Multiplying these by $n+1$ (the number of intervals) gives $\tfrac{n+1}{(2n+1) \log 2}$ and $\tfrac{n+1}{2^{q+1} \log 2}$. The former approaches $\tfrac{1}{\log 4}$ while the latter oscillates between $\tfrac{1}{\log 2}$ and $\tfrac{1}{\log 4}$.

added 335 characters in body
Source Link
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763

I will show $\mu = \tfrac{1}{\log 4}$.


I first prove the upper bound $\mu \leq \tfrac{1}{\log 4}$. Fix a positive integer $r$. For $0 \leq k \leq r-1$, let $N_k$ be $2^{k/r} N$ rounded to the nearest integer, where $N$ is a large parameter. Considering the $N_{r-1}$ intervals present at time $N_{r-1}$, let $X_k$ be the number of them created between times $X_{k-1}$ and $X_k$; with $X_0$ the number created before time $0$. Then $$X_0 \frac{\mu}{N_0} + X_1 \frac{\mu}{N_1} + \cdots + X_{r-1} \frac{\mu}{N_{r-1}} \leq 1.\quad (\ast)$$$$X_0 \frac{\mu}{N_0} + X_1 \frac{\mu}{N_1} + \cdots + X_{r-1} \frac{\mu}{N_{r-1}} \leq 1.$$ Set $S_k=X_0+X_1+\cdots +X_k$; we can rewrite the above equation as $$\mu \left( S_0 \left(\frac{1}{N_0} - \frac{1}{N_1}\right) + S_1 \left(\frac{1}{N_1} - \frac{1}{N_2} \right) + \cdots + S_{r-2} \left(\frac{1}{N_{r-2}} - \frac{1}{N_{r-1}}\right) + S_{r-1} \frac{1}{N_{r-1}} \right) \leq 1.$$

Of theNow, $N_k$$S_k$ is the number of those intervals present at time $N_k$, at most $N_{r-1} - N_k$ can be destroyed byfinal time $N_{r-1}$. So at least $2 N_k-N_{r-1}$ of them survive until which were created before time $N_{r-1}$. This means that $$X_0+X_1+\cdots + X_k \geq 2 N_k - N_{r-1} \quad (\dagger),$$ with equality for$N_k$, so we have $k=r-1$$S_k \geq N_k - (N_{r-1} - N_k)=2 N_k - N_{r-1}$.

The The coefficient of $\mu$$\tfrac{1}{N_k} - \tfrac{1}{N_{k+1}}$ on the left hand side of $(\ast)$ is linear in the $X_i$positive, so it is minimized if we take the $X_i$ at a vertex of the polytope cut out by $(\dagger)$ and $X_i \geq 0$. A little thought shows we want the vertex where $(\dagger)$ is equality for all $k$, so $X_0 = 2 N_0 - N_{r-1}$ and $X_k = 2 N_k - 2 N_{k-1}$ for $1 \leq k \leq r-1$. We deducehave $$\mu \left( \frac{2N_0-N_{r-1}}{N_0} + \frac{2 N_1 - 2 N_0}{N_1} + \cdots + \frac{2 N_{r-1} - 2 N_{r-2}}{N_{r-1}} \right) \leq 1.$$$$\mu \left( (2N_0-N_{r-1}) \left(\frac{1}{N_0} - \frac{1}{N_1}\right)+ (2N_1-N_{r-1}) \left(\frac{1}{N_1} - \frac{1}{N_2}\right)+\cdots+ (2N_{r-2}-N_{r-1}) \left(\frac{1}{N_{r-2}} - \frac{1}{N_{r-1}}\right)+\frac{N_{r-1}}{N_{r-1}} \right) \leq 1.$$

We pluggather terms with the same denominator to obtain $$\mu \left( \frac{2N_0-N_{r-1}}{N_0} + \frac{2 N_1 - 2 N_0}{N_1} + \cdots + \frac{2 N_{r-1} - 2 N_{r-2}}{N_{r-1}} \right) \leq 1$$ or $$\mu \left( 2r - \frac{N_{r-1}}{N_0} - \frac{2 N_0}{N_1} - \cdots - \frac{2 N_{r-2}}{N_{r-1}} \right) \leq 1.$$ Plugging in our optimized values: $$\mu \left( 2r - r 2^{(r-1)/r} \right) \leq 1$$ so $$\mu \leq \frac{1}{2r (1-2^{-1/r})}.$$

Finally, taking the limit as $r \to \infty$ gives $\mu \leq \tfrac{1}{\log 4}$ as promised.


Now, for the lower bound. Again, fix a positive integer $r$. Divide the circle into $r$ equal arcs; each arc will be subdivided into intervals. At any point in our process there will be some integer $k$ such that one arc is divided into some intervals of length $2^{-k/r}$ and some of length $2^{-(k+r)/r}$; the other $r-1$ arcs will contain intervals of only one length, namely $2^{-j/r}$ for $k<j<k+r$. (Obviously, I am ignoring rounding issues.) As time ticks on, we subdivide the intervals in the first arc until they are all split in half, then move to the next arc, and so on.

This achieves (again, ignoring rounding) $$\mu = 2^{-(k+r)/r} \left( \frac{2^{k/r}}{r} +\frac{2^{(k+1)/r}}{r} + \cdots \frac{2^{(k+r-1)/r}}{r} \right) = \frac{1}{2r(2^{1/r}-1)}.$$ Again, sending $r \to \infty$ achieves $\tfrac{1}{\log 4}$.


Here is a slicker, though less motivated way, to achieve the lower bound. We will number the points starting with $x_0$ at position $0$. For $n >0$, write $n = 2^q+r$ with $0 \leq r <2^q$ and put $x_n$ at $\log_2\left(\tfrac{2n+1}{2^{q+1}}\right)$. So the first few points are $0$, $\log_2(1+1/2)$, $\log_2(1+1/4)$, $\log_2(1+3/4)$, $\log_2(1+1/8)$, $\log_2(1+3/8)$, $\log_2(1+5/8)$, $\log_2(1+7/8)$, ... When point $x_n$ is inserted, the smallest interval will either be the one just to the right of $x_n$ or else the furthest right interval. Approximating $\log$ by its linearization, these have lengths roughly $\tfrac{2^{q+1}}{(2n+1) \log 2} \tfrac{1}{2^{q+1}}=\tfrac{1}{(2n+1) \log 2}$ and $\tfrac{1}{2 \log 2} \tfrac{1}{2^q}=\tfrac{1}{2^{q+1} \log 2}$ respectively.

Multiplying these by $n+1$ (the number of intervals) gives $\tfrac{n+1}{(2n+1) \log 2}$ and $\tfrac{n+1}{2^{q+1} \log 2}$. The former approaches $\tfrac{1}{\log 4}$ while the latter oscillates between $\tfrac{1}{\log 2}$ and $\tfrac{1}{\log 4}$.

I will show $\mu = \tfrac{1}{\log 4}$.


I first prove the upper bound $\mu \leq \tfrac{1}{\log 4}$. Fix a positive integer $r$. For $0 \leq k \leq r-1$, let $N_k$ be $2^{k/r} N$ rounded to the nearest integer, where $N$ is a large parameter. Considering the $N_{r-1}$ intervals present at time $N_{r-1}$, let $X_k$ be the number of them created between times $X_{k-1}$ and $X_k$; with $X_0$ the number created before time $0$. Then $$X_0 \frac{\mu}{N_0} + X_1 \frac{\mu}{N_1} + \cdots + X_{r-1} \frac{\mu}{N_{r-1}} \leq 1.\quad (\ast)$$

Of the $N_k$ intervals present at time $N_k$, at most $N_{r-1} - N_k$ can be destroyed by time $N_{r-1}$. So at least $2 N_k-N_{r-1}$ of them survive until time $N_{r-1}$. This means that $$X_0+X_1+\cdots + X_k \geq 2 N_k - N_{r-1} \quad (\dagger),$$ with equality for $k=r-1$.

The coefficient of $\mu$ on the left hand side of $(\ast)$ is linear in the $X_i$, so it is minimized if we take the $X_i$ at a vertex of the polytope cut out by $(\dagger)$ and $X_i \geq 0$. A little thought shows we want the vertex where $(\dagger)$ is equality for all $k$, so $X_0 = 2 N_0 - N_{r-1}$ and $X_k = 2 N_k - 2 N_{k-1}$ for $1 \leq k \leq r-1$. We deduce $$\mu \left( \frac{2N_0-N_{r-1}}{N_0} + \frac{2 N_1 - 2 N_0}{N_1} + \cdots + \frac{2 N_{r-1} - 2 N_{r-2}}{N_{r-1}} \right) \leq 1.$$

We plug in our optimized values: $$\mu \left( 2r - r 2^{(r-1)/r} \right) \leq 1$$ so $$\mu \leq \frac{1}{2r (1-2^{-1/r})}.$$

Finally, taking the limit as $r \to \infty$ gives $\mu \leq \tfrac{1}{\log 4}$ as promised.


Now, for the lower bound. Again, fix a positive integer $r$. Divide the circle into $r$ equal arcs; each arc will be subdivided into intervals. At any point in our process there will be some integer $k$ such that one arc is divided into some intervals of length $2^{-k/r}$ and some of length $2^{-(k+r)/r}$; the other $r-1$ arcs will contain intervals of only one length, namely $2^{-j/r}$ for $k<j<k+r$. (Obviously, I am ignoring rounding issues.) As time ticks on, we subdivide the intervals in the first arc until they are all split in half, then move to the next arc, and so on.

This achieves (again, ignoring rounding) $$\mu = 2^{-(k+r)/r} \left( \frac{2^{k/r}}{r} +\frac{2^{(k+1)/r}}{r} + \cdots \frac{2^{(k+r-1)/r}}{r} \right) = \frac{1}{2r(2^{1/r}-1)}.$$ Again, sending $r \to \infty$ achieves $\tfrac{1}{\log 4}$.


Here is a slicker, though less motivated way, to achieve the lower bound. We will number the points starting with $x_0$ at position $0$. For $n >0$, write $n = 2^q+r$ with $0 \leq r <2^q$ and put $x_n$ at $\log_2\left(\tfrac{2n+1}{2^{q+1}}\right)$. So the first few points are $0$, $\log_2(1+1/2)$, $\log_2(1+1/4)$, $\log_2(1+3/4)$, $\log_2(1+1/8)$, $\log_2(1+3/8)$, $\log_2(1+5/8)$, $\log_2(1+7/8)$, ... When point $x_n$ is inserted, the smallest interval will either be the one just to the right of $x_n$ or else the furthest right interval. Approximating $\log$ by its linearization, these have lengths roughly $\tfrac{2^{q+1}}{(2n+1) \log 2} \tfrac{1}{2^{q+1}}=\tfrac{1}{(2n+1) \log 2}$ and $\tfrac{1}{2 \log 2} \tfrac{1}{2^q}=\tfrac{1}{2^{q+1} \log 2}$ respectively.

Multiplying these by $n+1$ (the number of intervals) gives $\tfrac{n+1}{(2n+1) \log 2}$ and $\tfrac{n+1}{2^{q+1} \log 2}$. The former approaches $\tfrac{1}{\log 4}$ while the latter oscillates between $\tfrac{1}{\log 2}$ and $\tfrac{1}{\log 4}$.

I will show $\mu = \tfrac{1}{\log 4}$.


I first prove the upper bound $\mu \leq \tfrac{1}{\log 4}$. Fix a positive integer $r$. For $0 \leq k \leq r-1$, let $N_k$ be $2^{k/r} N$ rounded to the nearest integer, where $N$ is a large parameter. Considering the $N_{r-1}$ intervals present at time $N_{r-1}$, let $X_k$ be the number of them created between times $X_{k-1}$ and $X_k$; with $X_0$ the number created before time $0$. Then $$X_0 \frac{\mu}{N_0} + X_1 \frac{\mu}{N_1} + \cdots + X_{r-1} \frac{\mu}{N_{r-1}} \leq 1.$$ Set $S_k=X_0+X_1+\cdots +X_k$; we can rewrite the above equation as $$\mu \left( S_0 \left(\frac{1}{N_0} - \frac{1}{N_1}\right) + S_1 \left(\frac{1}{N_1} - \frac{1}{N_2} \right) + \cdots + S_{r-2} \left(\frac{1}{N_{r-2}} - \frac{1}{N_{r-1}}\right) + S_{r-1} \frac{1}{N_{r-1}} \right) \leq 1.$$

Now, $S_k$ is the number of those intervals present at final time $N_{r-1}$ which were created before time $N_k$, so we have $S_k \geq N_k - (N_{r-1} - N_k)=2 N_k - N_{r-1}$. The coefficient $\tfrac{1}{N_k} - \tfrac{1}{N_{k+1}}$ on the left hand side is positive, so we have $$\mu \left( (2N_0-N_{r-1}) \left(\frac{1}{N_0} - \frac{1}{N_1}\right)+ (2N_1-N_{r-1}) \left(\frac{1}{N_1} - \frac{1}{N_2}\right)+\cdots+ (2N_{r-2}-N_{r-1}) \left(\frac{1}{N_{r-2}} - \frac{1}{N_{r-1}}\right)+\frac{N_{r-1}}{N_{r-1}} \right) \leq 1.$$

We gather terms with the same denominator to obtain $$\mu \left( \frac{2N_0-N_{r-1}}{N_0} + \frac{2 N_1 - 2 N_0}{N_1} + \cdots + \frac{2 N_{r-1} - 2 N_{r-2}}{N_{r-1}} \right) \leq 1$$ or $$\mu \left( 2r - \frac{N_{r-1}}{N_0} - \frac{2 N_0}{N_1} - \cdots - \frac{2 N_{r-2}}{N_{r-1}} \right) \leq 1.$$ Plugging in our optimized values: $$\mu \left( 2r - r 2^{(r-1)/r} \right) \leq 1$$ so $$\mu \leq \frac{1}{2r (1-2^{-1/r})}.$$

Finally, taking the limit as $r \to \infty$ gives $\mu \leq \tfrac{1}{\log 4}$ as promised.


Now, for the lower bound. Again, fix a positive integer $r$. Divide the circle into $r$ equal arcs; each arc will be subdivided into intervals. At any point in our process there will be some integer $k$ such that one arc is divided into some intervals of length $2^{-k/r}$ and some of length $2^{-(k+r)/r}$; the other $r-1$ arcs will contain intervals of only one length, namely $2^{-j/r}$ for $k<j<k+r$. (Obviously, I am ignoring rounding issues.) As time ticks on, we subdivide the intervals in the first arc until they are all split in half, then move to the next arc, and so on.

This achieves (again, ignoring rounding) $$\mu = 2^{-(k+r)/r} \left( \frac{2^{k/r}}{r} +\frac{2^{(k+1)/r}}{r} + \cdots \frac{2^{(k+r-1)/r}}{r} \right) = \frac{1}{2r(2^{1/r}-1)}.$$ Again, sending $r \to \infty$ achieves $\tfrac{1}{\log 4}$.


Here is a slicker, though less motivated way, to achieve the lower bound. We will number the points starting with $x_0$ at position $0$. For $n >0$, write $n = 2^q+r$ with $0 \leq r <2^q$ and put $x_n$ at $\log_2\left(\tfrac{2n+1}{2^{q+1}}\right)$. So the first few points are $0$, $\log_2(1+1/2)$, $\log_2(1+1/4)$, $\log_2(1+3/4)$, $\log_2(1+1/8)$, $\log_2(1+3/8)$, $\log_2(1+5/8)$, $\log_2(1+7/8)$, ... When point $x_n$ is inserted, the smallest interval will either be the one just to the right of $x_n$ or else the furthest right interval. Approximating $\log$ by its linearization, these have lengths roughly $\tfrac{2^{q+1}}{(2n+1) \log 2} \tfrac{1}{2^{q+1}}=\tfrac{1}{(2n+1) \log 2}$ and $\tfrac{1}{2 \log 2} \tfrac{1}{2^q}=\tfrac{1}{2^{q+1} \log 2}$ respectively.

Multiplying these by $n+1$ (the number of intervals) gives $\tfrac{n+1}{(2n+1) \log 2}$ and $\tfrac{n+1}{2^{q+1} \log 2}$. The former approaches $\tfrac{1}{\log 4}$ while the latter oscillates between $\tfrac{1}{\log 2}$ and $\tfrac{1}{\log 4}$.

added 6 characters in body
Source Link
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763

I will show $\mu = \tfrac{1}{\log 4}$.


I first prove the upper bound $\mu \leq \tfrac{1}{\log 4}$. Fix a positive integer $r$. For $0 \leq k \leq r-1$, let $N_k$ be $2^{k/r} N$ rounded to the nearest integer, where $N$ is a large parameter. Considering the $N_{r-1}$ intervals present at time $N_{r-1}$, let $X_k$ be the number of them created between times $X_{k-1}$ and $X_k$; with $X_0$ the number created before time $0$. Then $$X_0 \frac{\mu}{N_0} + X_1 \frac{\mu}{N_1} + \cdots + X_{r-1} \frac{\mu}{N_{r-1}} \leq 1.\quad (\ast)$$

Of the $N_k$ intervals present at time $N_k$, at most $N_{r-1} - N_k$ can be destroyed by time $N_{r-1}$. So at least $2 N_k-N_{r-1}$ of them survive until time $N_{r-1}$. This means that $$X_0+X_1+\cdots + X_k \geq 2 N_k - N_{r-1} \quad (\dagger),$$ with equality for $k=r-1$.

The coefficient of $\mu$ on the left hand side of $(\ast)$ is linear in the $X_i$, so it is minimized if we take the $X_i$ at a vertex of the polytope cut out by $(\dagger)$ and $X_i \geq 0$. A little thought shows we want the vertex where $(\dagger)$ is equality for all $k$, so $X_0 = 2 N_0 - N_{r-1}$ and $X_k = 2 N_k - 2 N_{k-1}$ for $1 \leq k \leq r-1$. We deduce $$\mu \left( \frac{2N_0-N_{r-1}}{N_0} + \frac{2 N_1 - 2 N_0}{N_1} + \cdots + \frac{2 N_{r-1} - 2 N_{r-2}}{N_{r-1}} \right) \leq 1.$$

We plug in our optimized values: $$\mu \left( 2r - r 2^{(r-1)/r} \right) \leq 1$$ so $$\mu \leq \frac{1}{2r (1-2^{-1/r})}.$$

Finally, taking the limit as $r \to \infty$ gives $\mu \leq \tfrac{1}{\log 4}$ as promised.


Now, for the lower bound. Again, fix a positive integer $r$. Divide the circle into $r$ equal arcs; each arc will be subdivided into intervals. At any point in our process there will be some integer $k$ such that one arc is divided into some intervals of length $2^{-k/r}$ and some of length $2^{-(k+r)/r}$; the other $r-1$ arcs will contain intervals of only one length, namely $2^{-j/r}$ for $k<j<k+r$. (Obviously, I am ignoring rounding issues.) As time ticks on, we subdivide the intervals in the first arc until they are all split in half, then move to the next arc, and so on.

This achieves (again, ignoring rounding) $$\mu = 2^{-(k+r)/r} \left( \frac{2^{k/r}}{r} +\frac{2^{(k+1)/r}}{r} + \cdots \frac{2^{(k+r-1)/r}}{r} \right) = \frac{1}{2r(2^{1/r}-1)}.$$ Again, sending $r \to \infty$ achieves $\tfrac{1}{\log 4}$.


Here is a slicker, though less motivated way, to achieve the lower bound. We will number the points starting with $x_0$ at position $0$. For $n >0$, write $n = 2^q+r$ with $0 \leq r <2^q$ and put $x_n$ at $\log_2\left(\tfrac{2n+1}{2^{q+1}}\right)$. So the first few points are $0$, $\log_2(1+1/2)$, $\log_2(1+1/4)$, $\log_2(1+3/4)$, $\log_2(1+1/8)$, $\log_2(1+3/8)$, $\log_2(1+5/8)$, $\log_2(1+7/8)$, ... When point $x_n$ is inserted, the smallest interval will either be the one just to the right of $x_n$ or else the furthest right interval. Approximating $\log$ by its linearization, these have lengths roughly $\tfrac{2^{q+1}}{(2n+1) \log 2} \tfrac{1}{2^{q+1}}=\tfrac{1}{(2n+1) \log 2}$ and $\tfrac{1}{2 \log 2} \tfrac{1}{2^q}=\tfrac{1}{2^{q+1} \log 2}$ respectively.

Multiplying these by $n+1$ (the number of intervals) gives $\tfrac{n+1}{2^{q+1} \log 2}$$\tfrac{n+1}{(2n+1) \log 2}$ and $\tfrac{n+1}{(2n+1) \log 2}$$\tfrac{n+1}{2^{q+1} \log 2}$. The former oscilates between $\tfrac{1}{\log 2}$ andapproaches $\tfrac{1}{\log 4}$, while the latter approachesoscillates between $\tfrac{1}{\log 2}$ and $\tfrac{1}{\log 4}$.

I will show $\mu = \tfrac{1}{\log 4}$.


I first prove the upper bound $\mu \leq \tfrac{1}{\log 4}$. Fix a positive integer $r$. For $0 \leq k \leq r-1$, let $N_k$ be $2^{k/r} N$ rounded to the nearest integer, where $N$ is a large parameter. Considering the $N_{r-1}$ intervals present at time $N_{r-1}$, let $X_k$ be the number of them created between times $X_{k-1}$ and $X_k$; with $X_0$ the number created before time $0$. Then $$X_0 \frac{\mu}{N_0} + X_1 \frac{\mu}{N_1} + \cdots + X_{r-1} \frac{\mu}{N_{r-1}} \leq 1.\quad (\ast)$$

Of the $N_k$ intervals present at time $N_k$, at most $N_{r-1} - N_k$ can be destroyed by time $N_{r-1}$. So at least $2 N_k-N_{r-1}$ of them survive until time $N_{r-1}$. This means that $$X_0+X_1+\cdots + X_k \geq 2 N_k - N_{r-1} \quad (\dagger),$$ with equality for $k=r-1$.

The coefficient of $\mu$ on the left hand side of $(\ast)$ is linear in the $X_i$, so it is minimized if we take the $X_i$ at a vertex of the polytope cut out by $(\dagger)$ and $X_i \geq 0$. A little thought shows we want the vertex where $(\dagger)$ is equality for all $k$, so $X_0 = 2 N_0 - N_{r-1}$ and $X_k = 2 N_k - 2 N_{k-1}$ for $1 \leq k \leq r-1$. We deduce $$\mu \left( \frac{2N_0-N_{r-1}}{N_0} + \frac{2 N_1 - 2 N_0}{N_1} + \cdots + \frac{2 N_{r-1} - 2 N_{r-2}}{N_{r-1}} \right) \leq 1.$$

We plug in our optimized values: $$\mu \left( 2r - r 2^{(r-1)/r} \right) \leq 1$$ so $$\mu \leq \frac{1}{2r (1-2^{-1/r})}.$$

Finally, taking the limit as $r \to \infty$ gives $\mu \leq \tfrac{1}{\log 4}$ as promised.


Now, for the lower bound. Again, fix a positive integer $r$. Divide the circle into $r$ equal arcs; each arc will be subdivided into intervals. At any point in our process there will be some integer $k$ such that one arc is divided into some intervals of length $2^{-k/r}$ and some of length $2^{-(k+r)/r}$; the other $r-1$ arcs will contain intervals of only one length, namely $2^{-j/r}$ for $k<j<k+r$. (Obviously, I am ignoring rounding issues.) As time ticks on, we subdivide the intervals in the first arc until they are all split in half, then move to the next arc, and so on.

This achieves (again, ignoring rounding) $$\mu = 2^{-(k+r)/r} \left( \frac{2^{k/r}}{r} +\frac{2^{(k+1)/r}}{r} + \cdots \frac{2^{(k+r-1)/r}}{r} \right) = \frac{1}{2r(2^{1/r}-1)}.$$ Again, sending $r \to \infty$ achieves $\tfrac{1}{\log 4}$.


Here is a slicker, though less motivated way, to achieve the lower bound. We will number the points starting with $x_0$ at position $0$. For $n >0$, write $n = 2^q+r$ with $0 \leq r <2^q$ and put $x_n$ at $\log_2\left(\tfrac{2n+1}{2^{q+1}}\right)$. So the first few points are $0$, $\log_2(1+1/2)$, $\log_2(1+1/4)$, $\log_2(1+3/4)$, $\log_2(1+1/8)$, $\log_2(1+3/8)$, $\log_2(1+5/8)$, $\log_2(1+7/8)$, ... When point $x_n$ is inserted, the smallest interval will either be the one just to the right of $x_n$ or else the furthest right interval. Approximating $\log$ by its linearization, these have lengths roughly $\tfrac{2^{q+1}}{(2n+1) \log 2} \tfrac{1}{2^{q+1}}=\tfrac{1}{(2n+1) \log 2}$ and $\tfrac{1}{2 \log 2} \tfrac{1}{2^q}=\tfrac{1}{2^{q+1} \log 2}$ respectively.

Multiplying these by $n+1$ (the number of intervals) gives $\tfrac{n+1}{2^{q+1} \log 2}$ and $\tfrac{n+1}{(2n+1) \log 2}$. The former oscilates between $\tfrac{1}{\log 2}$ and $\tfrac{1}{\log 4}$, the latter approaches $\tfrac{1}{\log 4}$.

I will show $\mu = \tfrac{1}{\log 4}$.


I first prove the upper bound $\mu \leq \tfrac{1}{\log 4}$. Fix a positive integer $r$. For $0 \leq k \leq r-1$, let $N_k$ be $2^{k/r} N$ rounded to the nearest integer, where $N$ is a large parameter. Considering the $N_{r-1}$ intervals present at time $N_{r-1}$, let $X_k$ be the number of them created between times $X_{k-1}$ and $X_k$; with $X_0$ the number created before time $0$. Then $$X_0 \frac{\mu}{N_0} + X_1 \frac{\mu}{N_1} + \cdots + X_{r-1} \frac{\mu}{N_{r-1}} \leq 1.\quad (\ast)$$

Of the $N_k$ intervals present at time $N_k$, at most $N_{r-1} - N_k$ can be destroyed by time $N_{r-1}$. So at least $2 N_k-N_{r-1}$ of them survive until time $N_{r-1}$. This means that $$X_0+X_1+\cdots + X_k \geq 2 N_k - N_{r-1} \quad (\dagger),$$ with equality for $k=r-1$.

The coefficient of $\mu$ on the left hand side of $(\ast)$ is linear in the $X_i$, so it is minimized if we take the $X_i$ at a vertex of the polytope cut out by $(\dagger)$ and $X_i \geq 0$. A little thought shows we want the vertex where $(\dagger)$ is equality for all $k$, so $X_0 = 2 N_0 - N_{r-1}$ and $X_k = 2 N_k - 2 N_{k-1}$ for $1 \leq k \leq r-1$. We deduce $$\mu \left( \frac{2N_0-N_{r-1}}{N_0} + \frac{2 N_1 - 2 N_0}{N_1} + \cdots + \frac{2 N_{r-1} - 2 N_{r-2}}{N_{r-1}} \right) \leq 1.$$

We plug in our optimized values: $$\mu \left( 2r - r 2^{(r-1)/r} \right) \leq 1$$ so $$\mu \leq \frac{1}{2r (1-2^{-1/r})}.$$

Finally, taking the limit as $r \to \infty$ gives $\mu \leq \tfrac{1}{\log 4}$ as promised.


Now, for the lower bound. Again, fix a positive integer $r$. Divide the circle into $r$ equal arcs; each arc will be subdivided into intervals. At any point in our process there will be some integer $k$ such that one arc is divided into some intervals of length $2^{-k/r}$ and some of length $2^{-(k+r)/r}$; the other $r-1$ arcs will contain intervals of only one length, namely $2^{-j/r}$ for $k<j<k+r$. (Obviously, I am ignoring rounding issues.) As time ticks on, we subdivide the intervals in the first arc until they are all split in half, then move to the next arc, and so on.

This achieves (again, ignoring rounding) $$\mu = 2^{-(k+r)/r} \left( \frac{2^{k/r}}{r} +\frac{2^{(k+1)/r}}{r} + \cdots \frac{2^{(k+r-1)/r}}{r} \right) = \frac{1}{2r(2^{1/r}-1)}.$$ Again, sending $r \to \infty$ achieves $\tfrac{1}{\log 4}$.


Here is a slicker, though less motivated way, to achieve the lower bound. We will number the points starting with $x_0$ at position $0$. For $n >0$, write $n = 2^q+r$ with $0 \leq r <2^q$ and put $x_n$ at $\log_2\left(\tfrac{2n+1}{2^{q+1}}\right)$. So the first few points are $0$, $\log_2(1+1/2)$, $\log_2(1+1/4)$, $\log_2(1+3/4)$, $\log_2(1+1/8)$, $\log_2(1+3/8)$, $\log_2(1+5/8)$, $\log_2(1+7/8)$, ... When point $x_n$ is inserted, the smallest interval will either be the one just to the right of $x_n$ or else the furthest right interval. Approximating $\log$ by its linearization, these have lengths roughly $\tfrac{2^{q+1}}{(2n+1) \log 2} \tfrac{1}{2^{q+1}}=\tfrac{1}{(2n+1) \log 2}$ and $\tfrac{1}{2 \log 2} \tfrac{1}{2^q}=\tfrac{1}{2^{q+1} \log 2}$ respectively.

Multiplying these by $n+1$ (the number of intervals) gives $\tfrac{n+1}{(2n+1) \log 2}$ and $\tfrac{n+1}{2^{q+1} \log 2}$. The former approaches $\tfrac{1}{\log 4}$ while the latter oscillates between $\tfrac{1}{\log 2}$ and $\tfrac{1}{\log 4}$.

added 71 characters in body
Source Link
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763
Loading
added 953 characters in body
Source Link
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763
Loading
added 890 characters in body
Source Link
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763
Loading
added 506 characters in body
Source Link
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763
Loading
added 506 characters in body
Source Link
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763
Loading
added 506 characters in body
Source Link
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763
Loading
Source Link
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763
Loading