16
$\begingroup$

Which bijections $f:\{1,2,3,\ldots\}\to\{1,2,3,\ldots\}$ have the property that for every sequence $\{a_n\}_{n=1}^\infty$, $$ \lim_{n\to\infty} \sum_{k=1}^n a_k = \lim_{n\to\infty} \sum_{k=1}^n a_{f(k)}, $$ where "$=$" is construed as meaning that if either limit exists then so does the other and in that case then they are equal?

It is clear that there are uncountably many of these.

Might it just be that $\{f(n)/n : n=1,2,3,\ldots\}$ is bounded away from both $0$ and $\infty$?

These bijections form a group. Can anything of interest be said about them as a group?

PS: Here's another moderately wild guess (the one above appears to be wrong): Might it be just the bijections whose every orbit is finite?

$\endgroup$
  • 1
    $\begingroup$ @Gary The question is asking for a condition on the permutations that work for all sequences, not the other way around. $\endgroup$ – Ted Aug 4 '15 at 3:57
  • 1
    $\begingroup$ OK, got it, I misread and jumped in too quickly to comment. $\endgroup$ – Gary. Aug 4 '15 at 4:03
  • 1
    $\begingroup$ BTW, the proof that there are uncountably many that I had in mind is this. Consder bijections that, for each odd number, either map it to itself or interchange it with its successor, an even number. There are uncountably many of those, since there's a countably infinite sequence of binary choices. And those bijections never change the value of the sum of a conditionally convergent series. ${}\qquad{}$ $\endgroup$ – Michael Hardy Aug 4 '15 at 4:05
  • 2
    $\begingroup$ $\{f(n)/n\}$ can be arbitrarily large/small: consider the bijection that interchanges $(2n-1)!$ and $(2n)!$ and fixes every other integer. - In general, I believe it's true that if you choose an increasing sequence $1 = N_1 < N_2 < \cdots$ of positive integers, then any bijection which is just the union of infinitely many bijections on the sets $[N_j,N_{j+1})\cap\Bbb Z$ has this property. $\endgroup$ – Greg Martin Aug 4 '15 at 4:57
  • 2
    $\begingroup$ @GregMartin: I think you misunderstood Michael. He was hypothesizing that any bijection with that set bounded away from $0$ and $\infty$ works, not about there being a constant that bounds that set for every bijection that works. $\endgroup$ – user21820 Aug 4 '15 at 7:25
5
$\begingroup$

The hypothesis is wrong.

Let $f$ be the following sequence:

$1,2 ; 3,5,4,6; 7,9,11,8,10,12; \cdots$

where each block has two more numbers than the previous block and goes through the odd numbers in order before the even ones.

Clearly $f(n) \in n + O(\sqrt{n})$ as $n \to \infty$.

Now consider the following series:

$\frac{1}{1} - \frac{1}{1} \quad + \quad \frac{1}{2} - \frac{1}{2} + \frac{1}{2} - \frac{1}{2} \quad + \quad \frac{1}{3} - \frac{1}{3} + \frac{1}{3} - \frac{1}{3} + \frac{1}{3} - \frac{1}{3} \quad + \quad \cdots$

split into blocks in the same manner where each block has an alternating sum of the same reciprocal of the block index. Clearly this series converges to $0$. However after applying $f$ to the sequence in the series we get:

$\frac{1}{1} - \frac{1}{1} \quad + \quad \frac{1}{2} + \frac{1}{2} - \frac{1}{2} - \frac{1}{2} \quad + \quad \frac{1}{3} + \frac{1}{3} + \frac{1}{3} - \frac{1}{3} - \frac{1}{3} - \frac{1}{3} \quad + \quad \cdots$

which clearly does not converge.

Also, it is easy to see that we can insert arbitrarily large blocks of identity function between the blocks in the permutation, and corresponding blocks of zeros in the series, and the behaviour is exactly the same. This means that there is a counterexample where $f(n) \in n + o(n)$ as $n \to \infty$, equivalently where $\lim_{n\to\infty} \frac{f(n)}{n}$ exists.

$\endgroup$
1
$\begingroup$

My guessed interpretation of the second hypothesis is wrong too. (The original second hypothesis was already invalided by the first counter-example.)

Let $f$ be the following sequence:

$1;3,2;5,6,4;8,9,10,7;\cdots$

where each block has one more number than the previous block and is essentially a cyclic shift of elements at those positions. So $f$ has infinite order.

Then rearranging a series using $f$ does not change the existence and value of its limit because the magnitude of the discrepancy between partial sums is always at most the sum of magnitude of two terms with eventually increasing indices. If one converges, the other must hence converge since the terms go individually to zero.

$\endgroup$
1
$\begingroup$

Firstly I shall prove that indeed the rearrangements $R$ that preserve the convergence and value of every series form a group.$\def\nn{\mathbb{N}}$ Every rearrangement can of course be considered as a permutation on $\nn$. Every sequence is also just a function on $\nn$. We shall use $\sum^\infty x$ to denote the limit of the partial sums of $x$ if it exists and $null$ otherwise.

For any $f \in R$:

  $\sum^\infty a = \sum^\infty ( a \circ f )$ for any sequence $a$:

  For any sequence $a$:

    $\sum^\infty ( a \circ f^{-1} ) = \sum^\infty ( a \circ f^{-1} \circ f ) = \sum^\infty a$.

  Therefore $f^{-1} \in R$.

For any $f,g \in R$:

  $\sum^\infty a = \sum^\infty ( a \circ f )$ for any sequence $a$:

  $\sum^\infty a = \sum^\infty ( a \circ g )$ for any sequence $a$:

  For any sequence $a$:

    $\sum^\infty a = \sum^\infty ( a \circ f ) = \sum^\infty ( a \circ f \circ g )$.

  Therefore $f \circ g \in R$.

[Okay I did look at the paper (and I hate pay-walls for mathematics papers) and the collection that they say is not a group is the permutations that make a convergent series into another convergent one. The paper even mentions that the collection you are interested in is obviously a group.]

A sufficient condition for the rearrangement sequence to be sum-preserving is that there is a natural $k$ such that for any natural $n$ no more than $k$ numbers in $[1..n]$ are missing from the length-$n$ prefix of the sequence.

Clearly if the above condition holds, then the discrepancy between the partial sums of the original and rearranged series are bounded by the sum of magnitude of at most $2k$ terms. These terms have eventually increasing indices, because the numbers in $[1..n]$ that are not in the length-$n$ prefix will eventually appear in a longer prefix, and the numbers in the length-$n$ prefix that are not in $[1..n]$ are in $[1..m]$ for some $m > n$. Since the terms eventually go to zero, the sum of any $2k$ terms with eventually increasing indices must also go to zero.

This condition is far from necessary, because the following permutation is sum-preserving but has $\limsup_{n\to\infty} \frac{f(n)}{n} = \infty$ and $\liminf_{n\to\infty} \frac{f(n)}{n} = 0$:

$1;3,2;9,8,7,6,5,4;\cdots$

where the $k$-th block has $k!$ elements and is simply reversed. The reason is that for any $ε > 0$ there is some natural $k$ such that all the partial sums of any block beyond the $k$-th have magnitude less than $ε$, and hence also the partial sums of the block's reverse. This means that the rearranged series has the same sum by Cauchy convergence.

$\endgroup$
  • $\begingroup$ Here is a qualm I have about your argument: You say $\sum^\infty a = \sum^\infty ( a \circ f )$. But what if $\sum^\infty a$ is what you're calling "null"? Does the fact that $f$ preserves the convergence and value of every series mean it also preserves nullness? We know that if $\sum^\infty a$ converges then so does $\sum^\infty (a\circ f)$, and to the same limit, but does that in some way assure us that if $\sum^\infty$ has a lim sup strictly greater than its lim inf, then $\sum^\infty (a\circ f)$ does not converge? ${}\qquad{}$ $\endgroup$ – Michael Hardy Aug 5 '15 at 13:45
  • $\begingroup$ A traditional notation for intervals is $[k,\ell]$, and Donald Knuth has introduced a two-dot notation $[k\,.\,.\,\ell]$. But I would find it very surprising if Knuth condones writing $[k..\ell]$ with no spaces. The traditional three-dot ellipsis is $\text{blah blah}\ldots\text{blah blah}$ and not $\text{blah blah...blah blah}$, and when Knuth invented TeX he introduced \dots, which has proper spacing, and now we have \ldots, \cdots, \vdots, \ddots, etc. in LaTeX and MathJax. Is there a right way to${}\,\ldots$ groups.google.com/forum/#!topic/comp.text.tex/iJBW9jERgHI ${}\qquad{}$ $\endgroup$ – Michael Hardy Aug 5 '15 at 13:58
  • $\begingroup$ $\ldots\,{}$do this in MathJax and LaTeX? ${}\qquad{}$ $\endgroup$ – Michael Hardy Aug 5 '15 at 13:58
  • 1
    $\begingroup$ @MichaelHardy: I use $[a..b]$ to denote all the integers within the interval $[a,b]$. There is no conventional notation I am aware of. I don't care what Knuth thinks; edits are not for minor cosmetic changes and in fact spacing them out looks incredibly ugly. $\endgroup$ – user21820 Aug 5 '15 at 14:25
  • $\begingroup$ @MichaelHardy: Yes to your first question. That is the definition you gave for the collection; that it preserves convergence and their value, so if either converges the other must too. It is a trivial logical deduction that if either doesn't converge the other doesn't as well. $\endgroup$ – user21820 Aug 5 '15 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.