A problem communicated by Laurens de Vries

A problem communicated by Laurens de Vries

In a recent letter, Netty van Gasteren wrote to me a theorem that Laurens de Vries had shown in Eindhoven, and for which he had seen a very complicated proof. I give the problem as stated:

To be proved

$$ \langle \sum j: 1 < j < n: b _ {j} \rangle = $$

$\left\langle {\sum j : 1 \leq j \leq n : b.j * \left\langle {\prod i : 1 \leq i \leq n \land i \neq j : 1 - \frac{b.i}{b.j}}\right\rangle - 1}\right\rangle$

$$ \langle \forall i, j: 1 \leq i < j \leq n: b. i \neq b. j \rangle $$

To simplify my calculations, I rephrased the theorem:

Let $W$ be a set of $n$ (by definition mutually different) numbers, and let $R$ satisfy

then

$$ R = \langle \sum x: x \in W: \frac {x ^ {n}}{\langle \pi y : y \in W - {x } : x - y \rangle} \rangle ; $$

$$ R = \langle \sum x: x \in W: x \rangle $$

Leaving the verification of the cases $n \leq 1$ to the reader, we focus our attention on $n \geq 2$ .

R is defined as the sum of n fractions, each with a numerator of degree n and a denominator of degree n-1 . Were we to reduce all of them to a common denominator, we would get the denominator

$$ \langle \pi_ {x, y}: x, y \in W \land x > y: x - y \rangle $$

of degree $n * (n - 1) / 2$ and a numerator of a degree 1 higher, but we first focus our attention to the sum of two of the fractions. For $p,q \in W \land p \neq q$ , we observe

$$ \begin{array}{l} \frac {p ^ {n}}{\langle \pi y : y \in W - {p ^ {3} : p - y }} + \frac {q ^ {n}}{\langle \pi y : y \in W - {q ^ {3} : q - y }} \ = {\mathrm {w i t h} P _ {x} = \langle \pi y: y \in W - {p, q }: x - y \rangle \ \frac {p ^ {n}}{(p - q) \times P . p} + \frac {q ^ {n}}{(q - p) \times P . q} \ = {\mathrm {r e d u c e t o c o m m o n d e n o m i n a t o r} } \ \frac {p ^ {n} * P _ {q} - q ^ {n} * P _ {p}}{(p - q) * P _ {p} * P _ {q}} \ \end{array} $$

Because $P$ is a polynomial in $x$ ,

the numerator of our last fraction has a factor p-q , and hence we can eliminate the factor p-q from both numerator and denominator. Since the other n-2 fractions have denominators that don't contain a factor p-q we conclude that R remains bounded when p approaches q , hence R can be written as a fraction from whose denominator the factor p-q has dis- appeared. Since p,q was an arbitrary pair of elements of W, we conclude that R can be written as a fraction with a denominator of degree 0 and hence a denominator of (at most) 1. For reasons of symmetry, we can conclude

(0) $R = c * \langle \sum x : x \in W : x \rangle$

for some value of $c$ ,which is "constant" in the sense that it does not depend on the values in $W$ . In order to determine the value of $c$ ,we con- sider

$$ \lim _ {p \to \infty} (R / p) $$

where the other values in $W$ are kept constant. $R/p$ is the sum of $n$ fractions, $n - 1$ have limit 0 , and one has the

limit 1 , hence R/p has limit 1 . (0) gives limit c , hence $c = 1$ ,and the theorem has been proved.

Remark I have used asymptotic techniques: values approaching 0 or $\infty$ . With the same techniques I derived

$$ \langle \sum x: x \in W: \frac {x ^ {n - 1}}{\langle \pi y : y \in W - {x : x - y }} \rangle = 1 $$

$$ \langle \sum x: x \in W: \frac {x ^ {n + 1}}{\langle \pi y : y \in W - {x : x - y }} > = $$

$$ \langle \sum x: x \in W: \langle \sum y: y \in W \land x \leq y: x \cdot y \rangle \rangle $$

For the last result I needed complex numbers, and I did not try higher exponents of $x$ (End of Remark.)

The above argument was constructed in the very early morning of 29 February 1996, during a mostly sleepless night at Seton Hospital.

Austin, 2 March 1996

prof. dr. Edsger W. Dgkstra Department of Computer Sciences The University of Texas at Austin Austin, TX 78712 - 1188 USA