Recall that a summation &sumi=0&infin ai Conditionally Cvgs if it cvg but &sumi=0&infin |ai| does not cvg.
Recall the following theorem.
Cond Cvg Thm: Let &sumi=0&infin ai 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 Rd? 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 Rd, and V be a finite subset of B such that &sumv&isin V v = 0. Then there is an ordering v1, v2, ..., vn of the elements of V such thatThis can be used to show the following:v1 &isin dB
v1+v2 &isin dB
v1+v2+v3 &isin dB
etc.
v1+...+vn &isin dB
End of Statement of Steinitz's Lemma
d-dim version of Cond Cvg Theorem If a1, a2, a3,... &isin Rd and &sumi=0&infin ai conditionally cvgs then the set of points that this sum can be rearranged to converge to is an affine subspace of Rd.
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.
Very neat idea. You probably know that Hardy wrote whole monograph on Divergent Series.
ReplyDeleteYou seem to be oddly unaware that people are using "pure maths" every day in the design and analysis of algorithms. Weird.
ReplyDeleteYou have even chosen a not-particularly-exciting example.
I think the previous commenter is being unfair to Bill. Isn't it curious at first glance that this result has algorithmic applications?
ReplyDeleteThis is the thought Bill seems to be sharing. He's not using the term 'pure math' to set up a hierarchy or suggest that algorithmists are not using sophisticated mathematics.
On a related note, I want to express a personal wish for a more positive, respectful TCS blog-comments environment.
ReplyDeleteOf course there is room for constructive criticism and discussion of community trends; but there has been a persistent vein of anonymous sniping, especially in response to perceived insults to this or that subfield. Can we de-escalate?
Let's make our blogosphere an enjoyable place to be, rather than a source of even more stress in our academic lives. Thanks, Bill, for blogging in this spirit.
Thanks for the post Bill. As a matter of relevance to this blog, the corresponding ordering v_1, v_2, ... can also be found in poly(n) time.
ReplyDelete