# Does the Harmonic Sequence do useful downsizing?

I can’t believe that I’m the first to follow this train of thought, since each step is obvious. Therefore, I am tagging this as a reference request. Someone please quote me chapter and verse where this thread has been dealt with before. Thanks.

Step 1. Suppose x > 1. Hmm, x might be really big, but we want to get a handle on x, to downsize x, without losing, so to speak, the essential properties of x. How can we do this?

Step 2. The Harmonic Sequence leaps to mind. Because of the divergence of the corresponding series (i.e., the Harmonic Series), if we start subtracting from x the terms of the Harmonic Sequence, it will be after only finitely many such subtractions that we exhaust x, not matter how big x was.

Step 3. Define H(n) to be the sum of the first n terms of the Harmonic Sequence, for each positive integer n. So, H(n) = 1/1 + 1/2 + … + 1/n.

Step 4. So, there is a unique positive integer n such that H(n) ≤ x < H(n + 1). Let us call that positive integer n the index of x, denoting it by index(x), and let us call the quantity x – H(n) the residue of x, denoting it by r(x).

Commentary. The residue of x might already by a useful quantity. Whether it is in fact so is what the title of this post is asking.

For example, is there a useful characterization of r(xy) in terms of r(x) and r(y), somewhat along the lines of characterizing the logarithm? Perhaps. Or perhaps to get non-trivial results, we must, as so often happens, enter into iteration. So, how can we continue the process, in a way that ties back to x in an essential way? Again, the answer is obvious.

Step 5. Consider the quantity H(n + 1) – x, where n is the index of x. Let’s call this the complementary residue of x, denoting it by c(x). It is obvious that 0 < c(x) <= H(n + 1). How can we best use c(x)? Again, the answer is obvious: take its reciprocal.

Step 6. For x > 1, define the sphinx of x to be 1/c(x), denoting it by sphinx(x). Note that for really large x, the sphinx of x will also be really large.

Step 7. For a given x > 1, set up the following 5-fold sequence:

pathx(1) = x

pathindex(1) = index(pathx(1))

pathr(1) = r(pathx(1))

pathc(1) = c(pathx(1))

pathsphinx(1) = 1/pathc(1)

For each positive integer n > 1:

pathx(n) = pathsphinx(n – 1)

pathindex(n) = index(pathx(n))

pathr(n) = r(pathx(n))

pathc(n) = c(pathx(n))

pathsphinx(n) = 1/pathc(n)

Step 8. For x > 1, define the distillation sequence of x to be the sequence {y(n)} of positive integers such that for each positive integer n, y(n) = pathindex(n).

The obvious question is then whethere, for a given x > 1, the distillation sequence of x characterizes x in any interesting or useful way. For example, x is algebraic fif its distillation sequence has such-and-such a property.

Regards,

Mike Jones

28.May.2011 (Beijing time)

Added by OP on May 30, 2011 (Beijing time)

My motivation for the original investigation along these lines was to solve the open problem of finding an explicit well-ordering for the set of real numbers. My strategy was simply that I would associate a unique sequence of positive integers with each real number, and then let the well-ordering of the set of positive integers induce a well-ordering on the set of real numbers. Since finding an explicit well-ordering for any non-empty connected subset of the reals is equivalent to finding an explicit well-ordering for the reals, it seemed apropos to deal with (1,infinity). So, this was the motivation for step 1, and the harvesting, so to speak, of the distillation sequence. However, it seems to me that this sequence is not unique for a given x > 1. However, the infinite matrix whose first row is the distillation sequence for x, whose second row is the distillation sequence for x + 1, and whose third row is the distillation sequence for x + 2, and so on MIGHT be uniquely defined by x. I call this matrix the Serengeti matrix for x. But we need a single unique sequence for x. Using the diagonal sequence of course suggests itself. I call this the Serengeti sequence for x. If the Serengeti sequence is unique to x, then that solves the problem, but I have not had the time/ability to determine this. But I thought that the partial results along the way, such as the distillation sequence possibly yielding useful information was of interest in its own right, but since high-rep users are balking at step 1, I guess I need to give a full account of my motivation, and so now you have it:-)

-
@Mike Jones: Have never seen this before. Note that if $x$ is big, then $n$ is humongous, but at least an integer. The bigger $x$ is, the more precisely $n$ measures $x$, which sounds like the wrong direction. In Step 5, didn't you want to say $c(x) \le 1/(n+1)$? –  André Nicolas May 28 '11 at 4:51
@Mike Jones: I'm afraid I don't find any of these steps or concepts "obvious"; I don't see any reason why they would be useful or satisfy any nice properties. We could do the same thing with any divergent series - there's nothing special here about the harmonic series. Furthermore, as user6312 has pointed out, your process makes bigger numbers, not smaller ones. But at any rate, I highly doubt that anyone has investigated this before. –  Zev Chonoles May 28 '11 at 4:57
I don't understand Step 1. You want to compress a number so as to keep its "essential properties." What are these essential properties? The properties you want to preserve inform what kind of compression you do. –  Qiaochu Yuan May 28 '11 at 9:32
@Mike: I don't want to quash your enthusiasm here, but this is not how you go about creating useful mathematical concepts. There's no a priori reason that this transformation should have any reasonable properties or be useful in any application. –  Qiaochu Yuan May 28 '11 at 20:25
@Mike: there are no foolproof procedures, but there are better and worse ways to search the space of possible ideas for interesting ones. –  Qiaochu Yuan Aug 9 '11 at 20:36

I know of one application of some of your concepts.

A sum of distinct unit fractions is called an Egyptian fraction; for example $1/2+1/4+1/6$. $2=1+1$ is not such a sum, but we can easily write 2 as an Egyptian fraction: $2=1+1/2+1/3+1/6$.

In fact, any positive rational $x$ is representable as an Egyptian fraction. The argument to see that this is the case splits into two cases.

As observed by Fibonacci, if $x<1$, a greedy algorithm works ("repeatedly choose the unit fraction with the smallest denominator that is no larger than the remaining fraction to be expanded"). The point is that if $\displaystyle\frac1a< \frac pq<\frac1{a-1}$, then $pa-q<p$ and therefore the numerator of $\frac pq -\frac1a$ is strictly smaller than $p$, so the greedy algorithm terminates.

If $x>1$, let $n$ be the index of $x$. Then $0\le r(x)=x-H(n)<1$ and we are back in the previous case, because the fractions the greedy algorithm associates to $r(x)$ all have denominator larger than $n+1$ (by definition of index).

I am not sure who this argument is due to, but it is classic. You may find it in the Victor Klee - Stan Wagon book, "Old and New Unsolved Problems in Plane Geometry and Number Theory".

-

For understanding up through step (4), I suggest that you look into Euler's constant and the asymptotics of the harmonic numbers. Unfortunately, because $r(x)$ is not a continuous function, the asymptotic expansion might not be quite enough to calculate $r(x)$. We do know that because $H_n \sim \ln(n)$, then for $H_n \approx x$ we need $n \approx e^x$ and so $r(x)$ and $c(x)$ will be bounded by (approximately) $e^{-x}$. However, I don't think that the asymptotic expansion will give you enough accuracy to determine exactly what $n$ is (short of a horrible brute force computation).

Beyond step 4, everything looks completely unfamiliar, and somewhat unmotivated. I have never seen anything resembling the distillation sequence, and while there might be things that can be proved about it's behavior, I am skeptical, both that such behavior exists or that it has been studied. If nothing else, for every $x$, we can find $y<1$ such that, $c(x)=c(y)$, and because of this, the sequences will all agree, except at the first term. The one saving grace here is that $x-y$ will be rational.

The one observation I have is that, if you start with a rational number, all the numbers you deal with will also be rational, and so there might be something there. However the dynamics of these operations are going to be very messy.

As I commented in elsewhere, the algorithm is essentially the same as the algorithm to generate continued fraction expansions with integers replaced by harmonic numbers, although by using $c(x)$ instead of $r(x)$, you end up with minuses where normally you would have plusses, and you guarantee that the expansion will never terminate. Additionally, because the terms grow at least exponentially, repetition is impossible.

As such, I would advise to work with $r(x)$ instead of $c(x)$, allowing for the sequence to terminate, and maybe there is a way to throw logs in (e.g. take $-\ln(r(x))$ rather than $1/r(x)$) so that repetition becomes a possibility?

By making the first change, a natural first question is then "Does the sequence terminate for every rational $x$? If so, how does the length of termination depend on $x$? If not, characterize the $x$ such that the sequence terminates." A natural second question is "by terminating the sequence early, we get approximations to $x$. What can be said about the quality of these approximations?"

By making the second change, two natural questions are "When does the sequence terminate?" (this seems unlikely to have anything to do with rationality of $x$ anymore), and "Under what circumstances does the sequence repeat?"

-
Mike seems to be familiar with Euler's constant; it is implicitly mentioned in the commentary between steps 4 and 5. I agree that the question needs clarification. –  Dan Brumleve May 28 '11 at 6:33