6
$\begingroup$

Find distinct positive real numbers $x_1$ , $x_2$ , ... of least supremum such that, for each positive integer $n$, any two of 0, $x_1$ , $x_2$ ,..., $x_n$ differ by $1/n$ or more.

Note that the hurdle term $1/n$ is optimal in the sense that any replacement for it would need to stay below a constant multiple of it to allow a finite supremum. By a nonconstructive proof, there is a unique solution minimal with respect to the lexicographic ordering of real sequences; so a constructed solution (while eluding me) doesn't seem impossible. Although I haven't seen this problem anywhere, it looks too simple not to have been posed before. Any pointers would be welcome.

$\endgroup$
4
  • 1
    $\begingroup$ I'd tag this number theory, specifically, discrepancy theory. $\endgroup$ Jul 8, 2010 at 13:18
  • $\begingroup$ An interesting approach, which is as near optimal as I can imagine, is to place the x_k "out of order", by starting with k in j*2^n, fixing j and letting n increase. Then x_2^n get placed at 1/2^n, x_(3*2^n) at 1 + 1/(3*2^n), etc. This reduces the problem to finding large gaps for odd indices. I find x_5 "fits" at 1/2 + 1/5, x_7 at 1/2 + 1/5 + 1/7, x_9 at 1/4 + 1/9, 1/11 at 1 + 1/3 + 1/11, and so on. Note that x_(4k+1) "fits" between x_2k and x_k, and x_(4k+3) can often be judiciously placed. I predict a sup of < 3/2. Gerhard "Ask Me About System Design" Paseman, 2010.07.08 $\endgroup$ Jul 8, 2010 at 16:33
  • $\begingroup$ Also, there is placing x_2n at x_n - 1/2n and x_(2n+1) at x_n + 1/(2n+1), with x_0 at 0. Thus we know the supremum is less than 34/21. Gerhard "Ask Me About System Design" Paseman, 2010.07.08 $\endgroup$ Jul 8, 2010 at 17:14
  • $\begingroup$ I've seen this problem before in a finite bounded case: place $x_1, x_2, \cdots$ sequentially in the interval $[0,1]$. Can you place infinitely many $x_i$ in the unit interval? The answer is no; you can only place 16. So if you're looking for the optimal bound, there's a decent condition to start with. I think the reference is Zeitz's Art and Craft of Problem Solving. $\endgroup$
    – dvitek
    Sep 4, 2010 at 13:44

4 Answers 4

0
$\begingroup$

@Gerhard: Thank you for your interest. (Because my MO identity was lost, I have to reply as a new user.) What makes the problem hard is that, even if you have a minimal-supremum sequence of n points, adding the (n + 1)th point may bump up the supremum by 1/(n + 1); whereas, if you had chosen the first n points just a whisker less optimally, you might have been able to fit in an extra point or two before you are forced to bump up: The best (n + k)th sequence is not always the best k-th extension of the best n-th sequence. What makes the problem tantalizing is that approaching stepwise with egyptian fractions, as you have outlined, can probably get very near indeed to the optimum. However, while the best sequence for each finitized problem is rational, my guess is that the best infinite sequence isn't rational. ........... John Bentin

$\endgroup$
1
  • $\begingroup$ Yes, but I think you can use the finite problem to hone in on the infinite problem. At the very least, you can show for some n what the first n entries must be in the optimal sequence. I am updating my answer to suggest how to do this. Gerhard "Ask Me About System Design" Paseman, 2010.07.11 $\endgroup$ Jul 11, 2010 at 18:32
0
$\begingroup$

I have enough musings to post them as an answer, rather than fill up comment space.

First : Use a simple recursive construction to get an upper bound on the supremum. This places x_1 at 1, x_2n at x_n - 1/2n, and x_(2n+1) at x_n + 1/(2n+1). This gives an upper bound of sum{i positive integer} 1/(2^i - 1) which is some number less than 169/105. Of course, you need to prove this construction works.

Second: viewed as a tree with node n branching to children x_(2n) and x_(2n+1), note that you can prune and graft the tree, reshaping it as needed. Specifically, start by exchanging branches at nodes 11 and 7. (This works because 1/2 + 1/5 + 2/7 < 2* 1/2 = 1.) You may find that repruning smaller branches leads more quickly to a near optimal bound. Even with the one graft made, the upper bound is reduced to less than 1147/759.

Third: start determining optimal placements for the first n terms for small n, which meet the conditions and stay below the bounds established above. A computer simulation should quickly run through placements for n up to 12 which stay below the lower bound. For example, by hand one sees that x_1 < x_2 < x_n for n < 80 already leads to non optimal placements, so that combined with some analysis should prove that x_2 < x_1 in an optimal placement.

This approach should lead you quickly to the first four decimal digits of the supremum.

UPDATE 07.11 : I have what I think are two tools to tackle the problem. The first tool is the bounded width branch: Given n, form the branch suggested above starting with x_n "representing" 1/n, placing x_2n at x_n - 1/2n and x_2n+1 at x_n + 1/(2n+1), and continuing recursively. The actual tool is the lemma that this branch meets the criteria for extending the sequence and does so using up at most 2/n space, and actually at most 1/n + 1/(2n+1) + 1/(4n+3) + ... .

Formally the lemma should read: Let for j in S be the subsequence described above, where n in S is given and for k in S one has both 2k and 2k+1 in S, and no other integers or objects are in S otherwise. This subsequence can be part of a sequence that satisfies the spacing criterion given in the problem, and max(x_i - x_j) for i,j coming from S is less than 2/n.

The second tool is that, given any starting sequence, there is a way to extend it using bounded width branches to get a solution. Formally: Let for m <= M be a finite subsequence which satisfies the spacing criterion given. Then there are M+1 bounded width branches that can be grafted on to the sequence, given a complete sequence that also satisfies the spacing requirements.

Proof sketch: start with x_M, and place x_2M and x_2M+1 adjacent to it. Then go backwards up to x_M+1, placing bounded width branches in the space next to the smallest undecorated leaf. The spacing requirements guarantee that the branches will fit without needing to move any of the first M x_i . Also, show that the branches aren't close enough to each other to conflict with the spacing requirement.

So for any suitable sequence of length M, one can extend it to a complete suitable sequence at a cost of at most 2/(M+1). Now with this estimate, one can go through the first few finite sequences and weed out those that are provably nonoptimal.

END UPDATE 07.11

Gerhard "Ask Me About System Design" Paseman, 2010.07.08

$\endgroup$
2
  • $\begingroup$ @Gerhard: Thanks for your continuing interest. Your previous reply stimulated me to look further. I still think that the optimal sequence is irrational, and that you can't be on the optimal track if you are getting rational terms. I conjecture now that the first term and minimal supremum are both ln 4 (approximately 1.3829436112); I haven't started to look at the second and later terms. My argument won't fit into this box. If you email me at Yahoo's UK domain, with my name unpunctuated, I will be able to let you have some more details. $\endgroup$ Jul 12, 2010 at 21:36
  • $\begingroup$ I attempted an email to @yahoo.uk. If that did not work, point out this comment to Will Jagy and ask him to forward your email address to me. I will then respond with my email. Gerhard "Ain't this E-Mail Stuff Fun?" Paseman, 2010.07.13 $\endgroup$ Jul 14, 2010 at 0:23
0
$\begingroup$

I'll now put forward my candidate solution to the problem. It clearly satisfies the hurdle condition, but I can't prove its optimality. To get a handle on the algorithm, let's represent $x_1$ , $x_2$ , … as hotel guests numbered accordingly. Recall Hilbert's hotel, where the unfortunate guests were ever being shunted from their room to a higher-numbered room. The hotel in this case, rather than having a countably infinite number of discrete rooms, is a continuum of “rooms”, represented by the points of a closed bounded real interval; [0 , 1.4] is big enough, as it turns out. The “guests”, numbered 1, 2, … , are movable tags, each assigned to a rational point in the interval. Unlike Hotel Hilbert, which is always full, this hotel starts empty apart from the proprietor who resides permanently at 0, and the guests arrive one by one in the order 1, 2, … . The proprietor operates the strict rule that, when there are a total of $m$ guests in the hotel, there must be a space of at least $1/m$ between the residents (including himself), for $m$ = 1, 2, … . Guest 1 is assigned to the point 1. Guest 2 is placed at 1/2. When guest 3 arrives, she is put at 1/3, while guests 1 and 2 are moved up by a distance 2/3 – 2/(3 + 1) = 1/6. When guest 4 comes, he is allotted to 1/2 + 1/6 + 1/4 = 11/12. The general rule is as follows. For $k$ = 1, 2, … , after $2^k$ guests have been accommodated, the next $2^k$ are put consecutively into the $2^k$ spaces between the proprietor and the first $2^k$ guests, in left-to-right order: An odd-numbered arrival, say guest $2n$ – $1$, is assigned to the point below her right-hand neighbour (guest $n$) that is 1/($2n$ – $1$) above her left-hand neighbour, while all the guests to her right are moved up by a distance 2/($2n$ – 1) – $1/n$; when the next, even-numbered, guest arrives (guest $2n$), he can just go to the midpoint of the next space up, at a distance 1/$2n$ above his left-hand neighbour (guest $n$), and mercifully no resident has to move until the next (odd-numbered) guest arrives. The result is that the guests, now identified with their limiting room positions, are each the sum of two parts: The first part is a sum of a finite number of distinct fractions of the form $1/n$, while the second is an infinite series whose terms are of the form 1/$n$($2n$ – 1), where $n$ is a positive integer. Generally an infinite number of terms of the latter type are absent; only in the case of $x_1$ is the series free of gaps, and then the first “sum” has only one term. Thus $x_1$ = 1 + ∑{1/$j$($2j$ – 1) : $j$ = 2, 3, …} = ln 4, and this is also the supremum of the sequence.

An alternative characterization, suggested by Gerhard Paseman, is as follows: For j from 2^(k-1)+1 to 2^k, you will arrange to place guest (2j-1) to the left of guest j and guest 2j to the right of guest j. Since space to the left of guest j has previously been guaranteed to be 1/j from his/her lefthand neighbor, guest (2j-1) needs more since it needs 1/(2j-1) space to his/her left and right. So add the difference delta_j = (2/(2j-1) – 1/j) to the left of guest j and shift guest j and every guest on the right of guest j by this difference delta_j. Since guest 2j does not need more than 1/j = (2/2j) space, no such adjustment is needed for guest 2j. This gives guest 1 infinitely many adjustments; 1 ends up at place 1 + sum(j > 1) delta_j = 1 + sum(j > 1) {2 [ 1/(2j-1) - 1/2j ] } = 2 ln(2).

$\endgroup$
2
  • 1
    $\begingroup$ More generally, then, point 0 goes at 0, point 1 goes at $2\ln(2)$, and after that point $n$ goes to $2\ln(2)$ times the fractional part of $\log_2(2n-1)$. Another way of getting spacing at least a fixed multiple of $1/n$ is just to take $n$ times the golden mean, mod 1. $\endgroup$
    – Tracy Hall
    Aug 4, 2010 at 19:05
  • $\begingroup$ Tracy: That's neat! Clearly your logarithmic sequence jumps the 1/n hurdle and has the same supremum as the algorithmic one. The sequences are very plausibly the same, but I can't prove it (perhaps missing something quite easy). Also, I still have got nowhere with a proof of minimality for your/my sequence. The golden sequence would need scaling up by sqrt 5 to clear the hurdle, acquiring that quantity as supremum, which is bigger than ln 4; so that sequence drops out of contention. Do you perchance have a reference for an article in this area? I would be most grateful for it. John $\endgroup$ Aug 6, 2010 at 7:52
0
$\begingroup$

Belated thanks to Kevin O'Bryant for his pointer to discrepancy theory. This led me eventually to a source where the problem is solved: See Theorem 6.7 in Harald Niederreiter's book Random Number Generation and Quasi Monte Carlo Methods (SIAM 1992). The logarithmic sequence described by Tracy Hall is due to Rusza and is indeed optimal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.