- We present some PURE math that was APPLIED in a real way. I am more surprised by these things than I should be.
Recall that a summation &sum_{i=0}^{&infin} a_{i} Conditionally Cvgs if it cvg but &sum_{i=0}^{&infin} |a_{i}| does not cvg.
Recall the following theorem.
Cond Cvg Thm: Let &sum_{i=0}^{&infin} a_{i} be a cond. cvg sum. Let A &isin R. Then there exists a way to rearrange the summation such that it cvg to A.
What happens if instead of reals you have points in R^{d}? For this we need Steinitz's Lemma which we state below. For a nice proof and discussions of variants of it see Imre Barany's paper On the power of linear dependencies (Also available here in case it goes away from his website.)Steinitz's Lemma Let d be a natural number, B be the unit ball in R^{d}, and V be a finite subset of B such that &sum_{v&isin V} v = 0. Then there is an ordering v_{1}, v_{2}, ..., v_{n} of the elements of V such that
This can be used to show the following:v_{1} &isin dB
v_{1}+v_{2} &isin dB
v_{1}+v_{2}+v_{3} &isin dB
etc.
v_{1}+...+v_{n} &isin dB
End of Statement of Steinitz's Lemma
d-dim version of Cond Cvg Theorem If a_{1}, a_{2}, a_{3},... &isin R^{d} and &sum_{i=0}^{&infin} a_{i} conditionally cvgs then the set of points that this sum can be rearranged to converge to is an affine subspace of R^{d}.
This looks like a question and answer in pure math. But wait! there are applications of this sort of thing! And I don't mean applications to other parts of pure math! I don't even mean applications to complexity theory! There are applications to algorithms! Here are four references from Imre Barany's article. Only one was online (alas). If you find links to the other articles then send me link AND article and I will modify this post.
- A vector sum theorem and its application to improving flow shop guarantees. By I. Barany. Math. Oper. Res. Volume 6, 1981, 445-452. downloadhere or if it goes away or does not work then here
- Bibliography: Series of vectors and Riemann sums. By I. Halperin and T. Ando. Sapporo, Japan, 1989
- On approximate solutions of a scheduling problem. by S.V. Sevastyanov. Metody Diskr. Analiza Volume 32, 1978, 66-75. (In Russian).
- On some geometric methods in scheduling theory: a surey, Discrete Applied Math, Volume 55, 1994, 59-82.
--
Posted By GASARCH to Computational Complexity at 6/16/2009 08:57:00 AM