Suppose I have to put $N$ points $x\_1, x\_2, \ldots, x\_N$ on the circle $S^1$ of length 1 so as to achieve the largest minimum separation (packing radius). The optimal solution is the equally spaced arrangement $x\_k = k/N \bmod 1$, which achieves $\min\_{i<j}\|x\_i-x\_j\| = 1/N$.


However, suppose I didn't know in advance the number of points $N$ I needed to put down, and I had to put the points down one by one. I am not allowed to move points that are already placed, and I want to a process that, when compared to the optimum for fixed $N$, does not do much worse asymptotically. More precisely:



> 
> **Problem**: what is the sequence $x\_i$, $i=1,2,\ldots$, that maximizes $\mu=\lim\inf\_N \min\_{1\le i<j\le N} \|x\_i-x\_j\|/(1/N)$?
> 
> 
> 


First example: greedy process. Put the first point at 0, the second at 1/2, and each subsequent one so as to bisect the largest empty interval. This gives $\mu=1/2$: when we add the $(2^k+1)$th point, the smallest separation is $1/2^{k+1}$.


Second example: Let $x\_k = k\phi \bmod 1$, where $\phi = (\sqrt{5}-1)/2\approx 0.618$ is the inverse golden ratio. This process achieves $\mu = \phi$.



> 
> **Conjecture**: $\mu = \phi$ is optimal.
> 
> 
> 


I think I know how to prove that among linear sequences $x\_k = k\alpha$, that $\alpha=\phi$ (or any quadratic irrational whose continued fraction expansion is eventually all ones) is optimal, and I can start to imagine how to treat polynomial sequences, but I would like to know whether it's true that no sequence can do better than $x\_k = k \phi$.


**Motivation**: the motivation for this problem is from phyllotaxis (the arrangement of leaves and other plant parts along the growth a plant), where the golden angle and Fibonacci spirals are commonly observed. Many researchers from D'arcy Thompson to Adil Mughal and Denis Weaire have proposed mechanism associated with packing problems that result in the appearance of the golden angle and Fibonacci spirals. From a mathematical perspective, the optimization problem I propose here seems to be the neatest and most succinct that has this pattern as a solution.


**UPDATE**: Christian Remling's answer, which I have accepted, provides convincing evidence that my conjecture is in fact wrong, which is very exciting. His answer gives an alternative process, which might be able to give the real optimal $\mu$. I added an answer heuristically analyzing Christian's process and arguing that $\mu=1/\log(4)\approx 0.721$ might be the optimal asymptotic separation that can be achieved with this process.



Sequential addition of points on a circle, optimizing asymptotic packing radius
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}$.


