How many rearrangements must fail to alter the value of a sum before you conclude that none do?

Question

This will not be altogether unrelated to this earlier question.

For which classes $C$ of bijections from $\{1,2,3,\ldots\}$ to itself is it the case that for all sequences $\{a_i\}_{i=1}^\infty$ of real numbers, if $\displaystyle f\mapsto \lim_{n \to\infty} \sum_{i=1}^n a_{f(i)}$ remains the same for all $f\in C$ then it remains the same for all bijections $f$ from $\{1,2,3,\ldots\}$ to itself?

Thus if you have a conditionally convergent series, then at least one of the rearrangements that change the value of the sum is within $C$.

Answer 1

Update. A research collaboration growing out of this question and some of its answers has now resulted in the following article, providing an account of the rearrangement number:

A. Blass, J. Brendle, W. Brian, J. D. Hamkins, M. Hardy, and P. B. Larson, The rearrangement number, manuscript under review.

Abstract. How many permutations of the natural numbers are needed so that every conditionally convergent series of real numbers can be rearranged to no longer converge to the same sum? We show that the minimum number of permutations needed for this purpose, which we call the rearrangement number, is uncountable, but whether it equals the cardinal of the continuum is independent of the usual axioms of set theory. We compare the rearrangement number with several natural variants, for example one obtained by requiring the rearranged series to still converge but to a new, finite limit. We also compare the rearrangement number with several well-studied cardinal characteristics of the continuum. We present some new forcing constructions designed to add permutations that rearrange series from the ground model in particular ways, thereby obtaining consistency results going beyond those that follow from comparisons with familiar cardinal characteristics. Finally we deal briefly with some variants concerning rearrangements by a special sort of permutations and with rearranging some divergent series to become (conditionally) convergent.

---

Original answer. $\newcommand\N{\mathbb{N}}\newcommand\P{\mathbb{P}}$This is a great question. Let me focus on the title question, namely, the question of how many functions one might need to ensure your rearrangement property. There are a few things one can say.

Theorem. No countable family of functions suffice to ensure your rearrangement property. Specifically, for any countably many permutations $f_n:\N\to\N$, there is a series $\sum_k a_k$ of real numbers, such that $\sum_k a_{f_n(k)}=0$ for every $f_n$, but $\sum_k a_k=0$ is only conditionally convergent.

Proof. Indeed, I claim further that for any given series $\sum_k b_k$, we may create a new series $\sum_k a_k$ by padding the original series with zeros, but maintaining the order of the nonzero terms, in such a way that for every function $f_n$, the nonzero terms of $\sum_k a_{f_n(k)}$ appear in exactly the same order as the original series $\sum_k b_k$, except for at most $n$ values. So all these series have the same sum, even though the original series may be only conditionally convergent.

So fix any series $\sum_k b_k$, and any countably many permutations $f_n:\N\to\N$. We may start by defining $a_0=b_0$. At stage $n$, we will have specified finitely many $a_k$, in such a way that the nonzero entries specified so far include $b_0, b_1,\ldots,b_n$, in that order, but we have padded with a possibly very large number of zeroes in between, and furthermore such that for every $m<n$, the nonzero values of $a_{f_m(k)}$ that have been specified also agree with $b_0,\ldots,b_n$, in that order (except for $m$ values at most), but with the zeroes possibly inserted differently.

At step $n$, consider the functions $f_m$ for $m\leq n$, and find some index $k_n$ that is sufficiently large so that $k_n$ and $f_m(k_n)$ are larger than any index we have yet used, for all $m\leq n$. Let $a_{k_n}=b_n$, and pad the sequence with zeros $a_k=0$ at all the other indices up to $k_n$. Since we add the new term $b_n$ such a far distance out, the rearranged non-zero terms $a_{f_m(k)}$ maintain the same order of $\sum_n b_n$ as far as we have yet specified them (except possibly for the errors that we present before stage $m$, when the function $f_m$ began to be considered).

It follows that all the particular rearrangements $\sum_k a_{f_n(k)}$ using functions $f_n$ have the same value as $\sum_k a_k$, which agrees with $\sum_k b_k$. But if $\sum_k b_k$ is only conditionally convergent, then of course there is some other rearrangement with a different sum. QED

I take this theorem to suggest a new cardinal characteristic of the continuum. Specifically, let us define $\kappa$ to be the size of the smallest family $\cal C$ of permutations that have your desired rearrangement property. So $\kappa$ is the answer to the title question of "how many?" because fewer than $\kappa$ are insufficient, by definition, but there is a family of $\kappa$ many permutations that work. So far, we've proved that $\kappa$ is uncountable, and clearly it is at most continuum.

Corollary. If the continuum hypothesis holds, then $\kappa=\frak{c}$ is the continuum.

This conclusion is also consistent with the failure of the continuum hypothesis.

Theorem. It is relatively consistent with ZFC that no family of fewer than continuum many permutations has your rearrangement property, even when the continuum is large. Indeed, Martin's axiom implies $\kappa=\frak{c}$.

Proof. Assume that Martin's axiom holds, and that $\cal C$ is a family of fewer than the continuum many permutations $f:\N\to\N$. Fix any series $\sum_k b_k$, and let $\P$ be the partial order consisting of pairs $(s,F)$, where $s$ is a finite sequence of real numbers, whose nonzero values agree with a finite initial segment of those appearing in $\sum_k b_k$, but possibly padded with extra zeros, and $F$ is a finite subset of $\cal C$. The order is $(s,F)\leq (s',F')$ just in case $s\supseteq s'$ and $F\supseteq F'$, so that $(s,F)$ specifies more of the sequence and $F$ mentions more functions, and furthermore, for any $f\in F$, the nonzero portion of $s$ beyond $s'$ appears in the same order in $s$ as it does in the rearrangement of $s$ by $f$. In other words, once we add a function $f$ to $F$, then we will insist that all further extensions of $s$ respect $f$.

As a forcing notion, $\P$ has the countable chain condition, because any two conditions $(s,F)$, $(s,F')$ with the same first part are compatible, simply by using $(s,F\cup F')$, and there are only countably many ways to pad a finite initial segment of $\sum_n b_n$ with zeros. So Martin's axiom will apply to this forcing notion.

For each $m$, the collection of conditions $(s,F)$ for which $s$ includes the first $m$ terms of $\sum_k b_k$ is dense, since the construction in the main theorem above shows how to handle finitely many functions at once. Also, for any particular $f\in\cal C$, it is dense for it to be added to the second coordinate.

Since we have thus specified fewer than continuum many dense sets, by Martin's axiom there is a filter in $\P$ that meets all these dense sets. Such a filter amounts to a series $\sum_k a_k$, which agrees fully on its nonzero terms with the series $\sum_k b_k$, in the same order, and such that for every $f\in \cal C$, the rearrangement $\sum_k a_{f(k)}$ also agrees with $\sum_k b_k$ except on finitely many terms.

So all these rearrangements have the same sum as $\sum_k b_k$, even if this series is only conditionally convergent. QED

It remains to see whether a small family can ever suffice.

Question. Is it consistent with ZFC that $\kappa$ is less than the continuum?

That is, is it consistent with ZFC that a small family can suffice?

Answer 2

This is really a comment on Joel's answer, but apparently too long. Let P be the forcing which adds a permutation of $\mathbb{N}$ by finite pieces (so $P$ is forcing-equivalent to Cohen forcing). Force with a finite-support iteration of length $\omega_{1}$, using $P$ at each stage, over a ground model in which CH fails (producing, for example, the so-called dual Cohen model). The generic reals then ought to give a witness to the rearrangement number (the least cardinality of a set of permutations with the rearrangement property) being $\aleph_{1}$, while the continuum stays large.

Reasoning by analogy, this suggests that the rearrangement number is bounded above by $\operatorname{non}(M)$, the least cardinality of a nonmeager set of reals (which seems to be the same as the least cardinality of a nonmeager set of permutations, but I haven't thought it through in detail). Indeed, a nonmeager set of permutations has the rearrangement property, since for any series which is not absolutely convergent, comeagerly many permutations witness this.

Answer 3

This answer is an extended comment on the answers of Joel David Hamkins and Paul Larson. Let's say that the rearrangment number $\kappa$ is the smallest cardinality of a family of bijections that can change the value of any conditionally convergent sum. Our goal is to find the value of the rearrangement number in terms of other small cardinals.

Using a nice argument involving "padding with zeroes", Joel shows that $\kappa \geq \mathfrak{p}$. (At least, this is one way of summarizing his answer. The inequality $\kappa \geq \mathfrak{p}$ implies $\kappa$ is uncountable and also that MA proves $\kappa = \mathfrak{c}$, which are the two assertions in Joel's answer; see also Andreas Blass's comment on Joel's answer).

In this answer, I want to show how to take the "padding with zeroes" argument a bit further to show that

• $\kappa \geq \mathfrak{b}$
• by itself, Joel's "padding with zeroes" argument cannot prove anything stronger than $\kappa \geq \mathfrak{b}$.

(if you've forgotten what $\mathfrak{b}$ is, I'll define it below; for now just know that $\mathfrak{p} \leq \mathfrak{b}$ is always true and $\mathfrak{p} < \mathfrak{b}$ is consistent, so this inequality improves the former one).

First a few definitions:

• $A \subseteq \mathbb N$ is preserved by $f: \mathbb N \rightarrow \mathbb N$ if $f$ does not change the order of $A$, except possibly on a finite set. More precisely, $A$ is preserved by $f$ iff there is some cofinite subset $A'$ of $A$ such that $$x < y \qquad \Leftrightarrow \qquad f(x) < f(y)$$ for all $x,y \in A'$.

• If $A$ is not preserved by $f$, we say that $A$ is jumbled by $f$.

• A family $\mathcal B$ of bijections is jumbling if every infinite set is jumbled by some member of $\mathcal B$.

• The "jumbling number" $\mathfrak{j}$ is the smallest cardinality of a jumbling family.

This last definition is just a placeholder -- we'll show in a bit that $\mathfrak{j}$ is equal to another well-known cardinal, namely $\mathfrak{b}$. So what's the point of defining $\mathfrak{j}$ at all? Consider the following proposition and its proof:

Proposition: $\kappa \geq \mathfrak{j}$.

Proof: Suppose $\mathcal B$ is a family of bijections $\mathbb N \rightarrow \mathbb N$ and $|\mathcal B| < \mathfrak{j}$. By definition, there is an infinite set $A \subseteq \mathbb N$ that is preserved by every member of $\mathcal B$. Fix any conditionally convergent sequence $\langle b_n \rangle$. Define a new sequence $\langle a_n \rangle$ so that $a_n = 0$ if $n \notin A$, and otherwise $a_n = b_k$, where $n$ is the $k^{th}$ element of $A$. (In other words, pad the sequence $b_n$ with extra zeroes, putting the new zeroes precisely on the complement of $A$.)

Let $f \in \mathcal B$. Since no member of $\mathcal B$ jumbles $A$, the nonzero terms of $\langle b_n \rangle$, $\langle a_n \rangle$, and $\langle f(a_n) \rangle$ are all in the same order, except perhaps for finitely many terms. Thus $$\sum_{n \in \mathbb N}b_n = \sum_{n \in \mathbb N}a_n = \sum_{n \in \mathbb N}a_{f(n)}.$$ Therefore no $f \in \mathcal B$ can rearrange $\langle a_n \rangle$ sufficiently to change the value of its sum (even though such a rearrangement is clear possible, because $\langle b_n \rangle$ is only conditionally convergent). Since $\mathcal B$ was an arbitrary family of bijections with $|\mathcal B| < \mathfrak{j}$, this finishes the proof. QED

The proof of this proposition is nothing new: it is simply Joel's "padding with zeroes" argument in a slightly more abstract setting. The thing to notice is that $\mathfrak{j}$ is the largest cardinal number for which this argument succeeds: if $\lambda \geq \mathfrak{j}$, we cannot claim that $\lambda$ bijections will leave the nonzero terms of some sequence in the same order (modulo a finite set). Indeed, I defined the number $\mathfrak{j}$ simply to be the cardinal number at which the "padding with zeroes" argument stops working.

Now, as promised, we'll show that $\mathfrak{j}$ is just a more familiar number in disguise. Recall that $\mathfrak{b}$ is the smallest cardinality of an "unbounded" family $\mathcal F$ of functions $\mathbb N \rightarrow \mathbb N$. A "bound" for $\mathcal F$ means a function $h: \mathbb N \rightarrow \mathbb N$ such that, for every $f \in \mathcal F$, $h(n) > f(n)$ for all but finitely many $n$.

Theorem: $\mathfrak{j} = \mathfrak{b}$.

Proof:

Part I: $\mathfrak{b} \leq \mathfrak{j}$. Suppose $\lambda < \mathfrak{b}$; we will show that $\lambda < \mathfrak{j}$ as well. To this end, let $\mathcal B$ be a family of bijections $\mathbb N \rightarrow \mathbb N$ with $|\mathcal B| = \lambda$. We must show that $\mathcal B$ is not a jumbling family.

To each $b \in \mathcal B$, we associate a (recursively defined) function $f_b: \mathbb N \rightarrow \mathbb N$ as follows: $$f_b^0(n) = \max\{b(m) : m \leq f_b(n-1)\}+1,$$ $$f_b(n) = \max\{b^{-1}(m) : m \leq f_b^0(n)\}+1.$$ Because $|\mathcal B| = \lambda < \mathfrak{b}$, there is some $h: \mathbb N \rightarrow \mathbb N$ such that, for every $b \in \mathcal B$, $h(n) > f_b(n)$ for all but finitely many $n$.

Let $a_0 = 0$, let $$a_{n+1} = h(a_n)+n,$$ and let $A = \{a_n : n \in \mathbb N\}$. $A$ is clearly infinite, and I claim that $A$ is preserved by every element of $\mathcal B$ (which means that $\mathcal B$ is not a jumbling family).

Fix $b \in \mathcal B$ and fix $N$ such that $h(n) > f_b(n)$ for all $n \geq N$. We will show that for all $n \geq N$ we have $b(a_n) < b(a_{n+1})$, from which it follows that $A$ is preserved by $b$. If $n \geq N$, we have $a_n \geq n$ and $$a_{n+1} = h(a_n) + n > h(a_n) > f_b(a_n).$$ From the definition of $f_b$, it is clear that $a_{n+1} > f_b(a_n)$ implies $b(a_{n+1}) > b(a_n)$. Thus $b$ does not jumble $A$.

Part II: $\mathfrak{j} \leq \mathfrak{b}$. Fix an unbounded family $\mathcal F$ of functions $\mathbb N \rightarrow \mathbb N$. We will find a jumbling family $\mathcal B$ with $|\mathcal B| = |\mathcal F|$.

We may assume that every member of $\mathcal F$ is strictly increasing and strictly positive (if not, replace each $f \in \mathcal F$ with the function $g$ defined by $g(n) = \max\{f(0),\dots,f(n)\} + n + 1$). Thus each member of $\mathcal F$ naturally partitions $\mathbb N$ into nonempty intervals, namely $[0,f(0))$, $[f(0),f(1))$, $[f(1),f(2))$, etc. Let $b_f$ be the function that flips each of these intervals upside-down. That is, (setting $f(-1) = 0$ for convenience), if $f(m-1) \leq n < f(m)$, then $b_f(n) = f(m-1) + (f(m)-1) - n$.

Clearly $b_f$ is a bijection for every $f \in \mathcal F$. Let $\mathcal B = \{b_f : f \in \mathcal F\}$. We want to show that every infinite set is jumbled by some $b_f$.

Let $A$ be an infinite subset of $\mathbb N$. Let $h$ be the unique increasing enumeration of $A$. Since $\mathcal F$ is unbounded, there is some $f \in \mathcal F$ such that, for infinitely many values of $n$, we have $f(n) > h(n)+n$. By the pigeonhole principle, if $f(n) > h(n) + n$, then there are intervals of the form $[f(m-1),f(m))$ containing more than one member of $A$; in fact, the number of members of $A$ that do not have an interval to themselves is at least $n$. Since $f(n) > h(n)+n$ infinitely often, it follows that there are infinitely many intervals of the form $[f(m-1),f(m))$ containing multiple elements of $A$. Because each of these intervals is flipped upside-down by $b_f$, we see that $b_f$ jumbles $A$.

QED

Putting this together with Paul Larson's observation, we have what seems to me a decent range for $\kappa$:

Theorem: $\mathfrak{b} \leq \kappa \leq \operatorname{non}(M)$.

For the record, I can see no real reason to think that $\mathfrak{j} = \kappa$. In fact, I'll leave it as an exercise to show that the family $\mathcal B$ defined in Part II of my proof has the following property: for every $f \in \mathcal B$, if $\sum_{n \in \mathbb N}a_n$ converges, then $\sum_{n \in \mathbb N}a_{f(n)}$ converges also, and to the same value. In other words, we have a jumbling family that doesn't change the value of any sums!

Answer 4

For example, it is true if $C$ contains a representative of every equivalence class of bijections of $\mathbb N$, where $f \sim g$ if there exist $N,M$ such that $|f(i) - g(i)| < M$ for all $i > N$.

Answer 5

It is true if $C$ is the set of involutions $(i_1j_1)(i_2j_2)\cdots$ or even the set of all involutions with the added condition

$$i_1 \lt i_2 \lt \cdots\text{ and }j_1 \lt j_2 \lt \cdots \tag{$*$} $$

If a series is conditionally convergent, then its positive terms form a divergent series as do its negative terms. One can choose an involution which permutes the series to have runs of non-negative terms, each with sum greater than $1$ alternating with runs of negative terms each with sum less than $-1$.

This seems a little harder than I first thought so let me sketch some details. I'll build the involution a few transpositions at a time so at any stage there will be a finite partial permutation which fixes some terms and swaps some pairs of terms. The remaining terms will be termed available.

First find enough non-negative terms (in the given order) to add to a sum greater than $1$ and leave them as fixed points. If there are $j$ intervening negative terms, swap them with the next $j$ non-negative terms. These $j$ negative terms maintain their order. Any terms interspersed with these are negative as well and are left as fixed points. Now identify enough consecutive available negative terms, starting with the first such, to have a sum less than $-1$. If there are $j'$ intervening non-negative terms, swap them with the next $j'$ negative terms. Continue in this fashion.

Note that the involution constructed satisfies the added condition $(*)$.

There seems no harm in throwing in fixed-point free, at least if $(*)$ is dropped. Just swap previously fixed points of the same parity. With a litle more care one could probably have both $(*)$ and fixed-point free.