Representing positive rationals as a finite sum of distinct rationals with numerator 1

68 Views Asked by At

A question I have been thinking about is: for every positive rational $p/q$, does there exist distinct positive integers $a_1, a_2, \dots, a_n$ (for some $n \geq 2$) such that $$\frac{p}{q} = \sum_{i = 1}^{n} \frac{1}{a_i}?$$

I've convinced myself that the answer is yes by the following argument: First, note the identity $$\frac{1}{a} = \frac{1}{a + 1} + \frac{1}{a(a + 1)}$$ which demonstrates that the answer is yes for $p = 1$ and $q \geq 2$. In general, though, we can first write $$\frac{p}{q} = \underbrace{\frac{1}{q} + \frac{1}{q} + \dots + \frac{1}{q}}_{p \text{ copies}}$$ and apply the above identity to each $1/q$. For the first copy of $1/q$, we apply the identity once, such that $$\frac{1}{q} = \frac{1}{q + 1} + \frac{1}{q(q + 1)}.$$ For the second copy of $1/q$, we cannot just apply the identity once since the denominators would coincide with the ones obtained from the first copy, when we want the denominators to all be distinct. To resolve this, we now apply the identity twice recursively: $$\frac{1}{q} = \frac{1}{q + 1} + \frac{1}{q(q + 1)} = \left(\frac{1}{q + 2} + \frac{1}{(q + 1)(q + 2)}\right) + \left(\frac{1}{q(q + 1) + 1} + \frac{1}{q(q + 1)(q(q + 1) + 1)}\right)$$ which now represents $1/q$ as a sum of four distinct summands, each distinct from the two obtained from the first copy of $1/q$. Similarly, for the third copy of $1/q$, we apply the identity three times to represent $1/q$ as a sum of eight distinct summands, and so on. Once we have done this to all copies of $1/q$, we see if there are any duplicate denominators. If so, we repeat the process described above to eliminate duplicates. For example, if $q = 1$, the first copy of $1/q$ becomes $1/2 + 1/2$, so we apply the identity again to one of these $1/2$'s. We repeat this process as many times as necessary so that all summands are distinct. The identity guarantees that all these summands have numerator 1, so we are done.

While this is not rigorous at all, I'm fairly certain this establishes that every positive rational has a satisfying representation, and in fact that there are infinitely many satisfying representations, since we can always apply the identity again to any of the summands. But, since applying the identity $k$ times yields $2^k$ summands, the method above yields a representation with at least $2 + 4 + \dots + 2^p = 2^{p + 1} - 2$ summands! From a computational perspective, this lower bound makes this method rather impractical. Naturally, it is desirable to have as few summands as possible, which brings me to my question.

Question: Given $p/q$, what is the smallest positive integer $k \geq 2$ such that $p/q$ has a satisfying representation as the sum of exactly $k$ rationals with numerator 1? How might we find such a representation with minimal length?

(A second question to think about is whether there is a polynomial-time algorithm (in terms of $p$ and $q$) which computes some satisfying representation.)