7
$\begingroup$

Let $\mathbb{N}$ denote the set of positive integers. If $A\subseteq \mathbb{N}$ is finite, we say that $A$ is reciprocally summable to $1$ ("rs1") if $\sum_{a\in A} \frac{1}{a} = 1$.

If $A\subseteq \mathbb{N}$ is finite and $\sum_{a\in A} \frac{1}{a} < 1$, is there a finite rs1 set $A'$ with $A\subseteq A'$?

$\endgroup$
4
  • 3
    $\begingroup$ I believe yes, because for any finite extension E to bring the sum up to 1, if it over shoots, replace E by an allowed scaling factor, and try again. There should be some algorithms in the literature on Egyptian fractions. Gerhard "Go Sum Like An Egyptian" Paseman, 2019.08.18. $\endgroup$ Commented Aug 18, 2019 at 20:09
  • 1
    $\begingroup$ Let $N=1+\max A$ and $r=1-\sum_{a\in A}\frac{1}{a}$. Then the Main Theorem of this paper by Croot implies that we can find $A'$ so that $\max A'<e^{r+o(1)}N$. $\endgroup$ Commented Aug 18, 2019 at 22:56
  • 1
    $\begingroup$ I wondered if it can be interesting to create different variants of the problem, for different definitions involving multiplicative functions $f(n)$ for the sums $\sum_{a\in A}\frac{1}{f(a)}$, for example I imagine write $f(n)=\operatorname{rad}(n)$, the product of distinct primes dividing $n>1$ (see the Wikipedia Radical of an integer) instead of your $f(n)=n$ in the denominators. If you think that it has a good mathematical content, feel free to study it. I hope don't disturb. $\endgroup$
    – user142929
    Commented Aug 28, 2019 at 8:28
  • $\begingroup$ @user142929 Thanks for your ideas - you don't disturb at all. If you want to contact me about this, use twitter.com/dominiczypen and write me a direct message $\endgroup$ Commented Aug 28, 2019 at 14:44

1 Answer 1

12
$\begingroup$

Yes, several algorithms for Egyptian fractions suggested by Gerhard Paseman works.

We want to represent the number $r=1-\sum_{a\in A}$ as a sum of distinct Egyptian fractions with denominators not in $A$. This may be done by many ways, for example we may use

Lemma. For any positive integers $a,n$ the number $1/a$ is representable as a sum of distinct Egyptian fractions with denominators greater than $n$.

Proof. Start with $1/a=1/a$. If it does not work (i.e., $a\leqslant n$), replace $1/a$ to $1/(a+1)+1/(a^2+a)$. After that do the same with both $1/(a+1),1/(a^2+a)$. We get four fractions which sum up to $1/a$, then eight fractions and so on. Stop when we get, say, $2^k$ fractions which are all less than $1/n$. They are all distinct (unless $a=1$, in this case use $1=1/2+1/3+1/6$), that proves Lemma. Why distinct? Assume that two of them coincide, choose the first step when this happens, say $b+1=c^2+c$ where $b,c$ were denominators on the previous step. Then the total number of steps is less than $c$, and $b=c^2+c-1$ was obtained from $c^2+c-2$, this guy in turn from $c^2+c-3$ and so on. Thus initial number $a$ was not less than $c^2$ and could not generate $c$. Lemma is proved.

Now start with the representation $r=1/N+\ldots+1/N$ for large $N>\max(A)$. Then perform the replacement algorithm: while two fractions $1/a,1/a$ in the representation are equal, replace one of them using lemma by a sum with denominators greater than anything already used. After finitely many steps we remove all repetitions.

$\endgroup$
4
  • $\begingroup$ No need to analyse a splitting algorithm (where it is not at all clear that the algorithm terminates). Fibonacci (!) proved that the greedy algorithm terminates. $\endgroup$ Commented Aug 19, 2019 at 6:06
  • 1
    $\begingroup$ @GregMartin yes, but I think we should add few words to Fibonacci's greedy algorithm termination theorem, because we have initial restrictions. $\endgroup$ Commented Aug 19, 2019 at 10:04
  • $\begingroup$ The greedy algorithm with denominators restricted to be larger than $x$ terminates by the exact same proof of Fibonacci. (Use all the smallest allowed denominators until there's a denominator that's too small to be used; then the greedy algorithm reduces the numerator of the remaining fraction by at least 1 each time.) It's still far simpler than a splitting-based algorithm—and note that your assertion that it terminates is not justified. $\endgroup$ Commented Aug 19, 2019 at 16:57
  • $\begingroup$ @GregMartin last objection is not clear for me. The number of repetitions decreases after each step, thus it obviously terminates. $\endgroup$ Commented Aug 19, 2019 at 17:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .