14
$\begingroup$

Background

An Egyptian fraction is a finite sum of distinct unit fractions, in which each denominator is not bigger than the next one. In other words, it is a representation of $a/b$ such that $$\frac{a}{b} = \sum_{n=1}^{N} \frac{1}{c_{n}} \tag{1}\label{1} $$ with $c_{1} < c_{2} < \dotsb < c_{N-1} < c_{N} \in \mathbb{N}^{+}$. For instance, we have $$ \frac{80}{99} = \frac{1}{2} + \frac{1}{4} + \frac{1}{18} + \frac{1}{396} . \tag{2}\label{2}$$

I'm currently exploring the idea of an Egyptian product (*). It is a representation of a fraction $a/b$ with $b>a$ such that $$\frac{a}{b} = \prod_{k=1}^{K} \left(1-\frac{1}{a_{k}} \right) , \tag{3}\label{3}$$ where $a_{1} < a_{2} < \dotsb < a_{K-1} < a_{K} \in \mathbb{N}^{+}$. If we take the previous fraction again as an example, we find: $$ \frac{80}{99} = \left(1-\frac{1}{9} \right) \left( 1-\frac{1}{11} \right). \tag{4}\label{4}$$

An Egyptian product for all rationals

I've asked about this concept before on MSE. User Jon Bentin pointed out that every fraction $0 < \frac{a}{b} < 1 $ can be represented by an Egyptian product. This is true because for every $m$ and $n$, it holds that $$\frac m{m+n}=\prod_{k=1}^n\left(1-\frac1{m+k}\right). \tag{5}\label{5} $$

In the case of our running example $80/99$, this would yield an Egyptian product consisting of 19 terms.

Questions

  1. Has this notion of an Egyptian product been described in the mathematical literature before? I am especially interested in the question of how to obtain the shortest Egyptian fraction representation for a rational number — i.e., minimizing the value of $K$ in equation \eqref{3}.
  2. Is the Egyptian product a new and "interesting" representation in the sense that they can't be reduced to finding Egyptian fraction sums (or perhaps a particular type thereof) somehow?

Note

(*) Sometimes, a particular type of Egyptian fraction — the Engel expansion — is also called an Egyptian product. The concept of an Egyptian product I have in mind is different.

$\endgroup$
1

1 Answer 1

5
$\begingroup$

I will approach the question of how to obtain the shortest Egyptian Product representation for a rational number from an algorithmic perspective, connecting it to existing problems, and demonstrate a tighter construction than previously discussed.

If you tweak your definition to allow the Egyptian Product to contain duplicate fractions, there is an nice construction for representing any rational between $0$ and $1$ of the form $\frac{m}{n}$ as a Duplicated Egyptian Product with $O(\log{n})$ fractions. We can then perform deduplication on the result of this construction to obtain small Egyptian Products that fit your definition. In the worst case these Egyptian Products will have $O(n)$ fractions, but empirically it seems to result in $O(\log{n})$ fractions on average (a tighter analysis can be performed here). For describing this construction, I will start with the case of rationals of the form $\frac{1}{n}$ since the bound there is more straightforward, then extend it to all positive rationals between $0$ and $1$, and then describe the deduplication procedure.

A short Duplicated Egyptian Product for $\frac{1}{n}$ can be found via the shortest binary addition chain for $n$. In this chain, doubling steps correspond to multiplying by $\frac{1}{2}$, and incrementing steps (from $k$ to $k + 1$) correspond to multiplying by $\frac{k}{k + 1}$.

For example, consider the minimal binary addition chain for $23$: $$1, 2, 4, 5, 10, 11, 22, 23.$$ As a Duplicated Egyptian Product, this is: $$\frac{1}{2} \times \frac{1}{2} \times \frac{4}{5} \times \frac{1}{2} \times \frac{10}{11} \times \frac{1}{2} \times \frac{22}{23}.$$

This is asymptotically optimal as $n$ increases given that at least $O(\log{n})$ terms are required to make the product small enough. Deduplication will later blow this up to $O(n)$.

We can extend this idea to all positive positive rationals: $\frac{m}{n}$ (with $0 < m < n$) by considering the shortest binary addition chain starting at $m$ and ending at $n$. In this case, to achieve a logarithmic upper bound on the fractions, we will need to perform additional transformations on the resulting Duplicated Egyptian Product.

For example, consider the rational $\frac{6}{17}$. The minimal binary addition chain from $6$ to $17$ is: $$6, 7, 8, 16, 17.$$ As an Deduplicated Egyptian Product, this is: $$\frac{1}{2} \times \frac{6}{7} \times \frac{7}{8} \times \frac{16}{17}.$$ Here were can observe that $\frac{6}{7} \times \frac{7}{8} = \frac{3}{4}$ and can simplify our product to just $3$ terms.

Whenever we have consecutive fractions of the form $\frac{2 a}{2 a + 1}$ and $\frac{2 a + 1}{2 a + 2}$, we can combine them into a single fraction of the form $\frac{a}{a + 1}$. By repeatedly applying this rule, we can significantly reduce the number of terms in the product.

This is particularly useful in cases where $m$ and $n$ are chosen such that the binary addition chain between them contains many consecutive fractions. This simplification, when applied repeatedly, can reduce the number of terms in the Duplicated Egyptian Product from $O(n)$ to $O(\log{n})$. For the extreme case, consider the Duplicated Egyptian Product of $\frac{m + 1}{2 m}$. The minimal binary addition chain from $m + 1$ to $2 m$ requires $O(m)$ terms, but the resulting Duplicated Egyptian Product from the simplification procedure has $O(\log{m})$ fractions.

As a final example, the minimal binary addition chain from $23$ to $82$ requires $20$ terms, but through repeated application of the consecutive fraction simplification, we can reduce our Duplicated Egyptian Product to just $5$ fractions: $$\frac{1}{2} \times \frac{3}{4} \times \frac{4}{5} \times \frac{23}{24} \times \frac{40}{41}.$$

I have no proof that this procedure is optimal for producing Duplicated Egyptian Products (though no counterexamples yet). Additionally, it is certainly possible to perform a more detailed analysis and achieve a tighter bound which depends on both $m$ and $n$.

Finally, to perform deduplication, we will scan through the fractions in the Duplicated Egyptian Product in ascending order, and whenever we encounter a duplicate fraction $\frac{a}{a + 1}$, we can replace one copy of it with two fractions: $\frac{2a}{2a + 1}$ and $\frac{2a + 1}{2a + 2}$. This is the reverse of our simplification procedure, but it is not strictly undoing what simplification did. Simplification often produces unique fractions in our Duplicated Egyptian Product (from my observations), so little to no deduplication is required in most cases.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. Just to be clear: the Egyptian product for $1/23$ requires itself as well in your approach as one of the terms in the expansion: $1-1/23 = 22/23$ ? $\endgroup$
    – Max Muller
    Nov 1, 2023 at 13:49
  • $\begingroup$ Yes, that is correct. $\endgroup$ Nov 1, 2023 at 15:49
  • $\begingroup$ Do all addition chains work? Doesn't it have to be only adding 1 and doubling? $\endgroup$ Nov 6, 2023 at 18:25

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.