|
|
en.wikipedia.org/wiki/Egyptian_fraction
math.stackexchange.com/questions/109655/how-t … -finitely-many-solut
| For any rational number $\frac{p}{q}$ there is only finitely many positive integer solutions to $\sum_{n=1}^{N} \frac{1}{x_i} = \frac{p}{q}$ |
We can assume $p,q>0$, otherwise the statement is trivial.
When $N=1$ the statement is obvious, there can be only one or zero solutions to $\frac{1}{x_1} = \frac{p}{q}$.
Assume the claim is true for $N-1$. The smallest number among $x_i$ cannot exceed $Nq$, otherwise all summands would be smaller than $\frac{1}{Nq}$, and
$\sum_{n=1}^{N} \frac{1}{x_n} < \sum_{n=1}^{N} \frac{1}{Nq} = \frac{1}{q} \leq \frac{p}{q}$
Therefore one of $x_i$ is at most $Nq$ – there is a finite number of possibilities for the smallest number.
$\{(x_1, \dots, x_N): \frac{1}{x_1} + \dots + \frac{1}{x_N} = \frac{p}{q}\}=$
$\bigcup_i \bigcup_{x_i=1}^{Nq} \{(x_1, \dots, x_N): \frac{1}{x_1} + \dots + \frac{1}{x_N} = \frac{p}{q}\}=$
$\bigcup_i \bigcup_{x_i=1}^{Nq} \{(x_1, \dots, x_N): \frac{1}{x_1} + \dots + \frac{1}{x_{i-1}} + \frac{1}{x_{i+1}} + \dots + \frac{1}{x_N} = \frac{p}{q} - \frac{1}{x_i}\}$
By inductive hypothesis (with $\frac{p}{q} - \frac{1}{x_i}$), every set here is finite, and a finite union of finite sets is finite. The proof is finished.
Note that this proof gives you a (very slow) algorithm that finds all solutions. Below is a generalization, based on more abstract tools.
Consider ${\mathbb N}^k$ with partial order $(a_1, \dots, a_N) \leq (b_1, \dots, b_N)$ iff $a_i \leq b_i$ for all $i$.
Let $f \colon {\mathbb N}^k \to \mathbb R$ be a strictly decreasing function. The set $f^{-1}(1)$ is an antichain, because $f$ is strictly decreasing. The problem is solved when we use
Dickson's lemma: Any antichain in ${\mathbb N}^k$ is finite.
and of course set $f(x_1, \dots, x_N) = \sum_{i=1}^{N} \frac{1}{x_N}$, but the point is you can have any strictly decreasing function.
Proof of Dickson's lemma is similar to the previous proof. If the antichain is empty, we are finished; otherwise it contains some element $(x_1, \dots, x_N)$; any other element in the antichain must fulfil $y_i < x_i$ at some coordinate $i$, and there are finitely many possibilities; we use induction as previously.
Dickson's lemma says that ${\mathbb N}^k$ is a well-quasi-ordering; more abstractly, you can show that product of two wqos is a wqo. The theory of wqos is very rich. Robertson-Seymour theorem, whose proof was finished in 2004 and spans about 500 pages, says that graphs under a suitable order form a wqo. |
|
