Recently there was this question talking about an averaging procedure on finite multisets of integers.

After seeing that question, I thought about the same procedure but with integers replaced by $2$-adic integers. More precisely:

Let $(a_1, \dots, a_n)$ be an $n$-tuple of elements of $\Bbb Z_2$.

At each step, we choose two indices $i, j$ such that $a_i \equiv a_j\mod 2$, and replace both $a_i$ and $a_j$ with their average $\frac{a_i + a_j}2$.

Is it true that, for any given initial values and any possible choice of indices, the resulting sequence of $n$-tuples will eventually be constant (i.e. does not change any more after a finite number of steps)?

For $n = 2$ it's clear. For $n = 3$ it's also easy to see that we eventually arrive at $(a, a, b)$ where $a \not\equiv b \mod 2$, and then must remain constant thereafter.

I haven't find a proof for the case $n = 4$. I originally thought about using compactness of $\Bbb Z_2$ together with some kind of continuity/open covering argument, but it doesn't seem to work.

On the other hand, I also have difficulty constructing a counterexample. The first idea was to construct a cyclic and non-constant sequence, but I soon realize that this is impossible:

  • The resulting sequence cannot be cyclic and non-constant.

    Because each operation is $\Bbb Q$-linear. If there were a valid cyclic and non-constant sequence, then by taking a $\Bbb Q$-basis of $\Bbb Q_2$, we would get a valid cyclic and non-constant sequence in $\Bbb Q$, which then gives a cyclic and non-constant sequence in $\Bbb Z$, by clearing the denominators.

    The last is impossible, since the sum of squares of all $a_i$ decreases in each step.

  • As corollary, there cannot be a sequence of steps which turns a tuple to one of its permutations, as repeating this sequence would eventually turn the tuple to itself.

    This justifies our usage of tuples instead of multisets, as the question remains equivalent.


Here is an example of a sequence that is not eventually constant, with $n=4$.

Start with a multiset $\{0,\alpha,\alpha,1\}$, with $\alpha\in \mathbb{Z}_2$ to be chosen later. Since the sum of the four numbers is odd (so will remain odd), after $n$ steps we will have a multiset of the form $\{a_n,a_n,b_n,c_n\}$, with $a_n \equiv b_n\not\equiv c_n$ mod $2$. We will always choose to replace both $a_n$ and $b_n$ with $(a_n+b_n)/2$. Define a binary sequence (depending on $\alpha$) by $r_n = a_n$ mod $2$. Then the first $n$ terms $r_0,\ldots,r_{n-1}$ determine and are determined by the value of $\alpha$ mod $2^n$ (it is clear that $\alpha$ mod $2^n$ determines $r_0,\ldots,r_{n-1}$, and it isn't too hard to see that one can recursively solve for $\alpha$ mod $2^n$ given $r_0,\ldots,r_{n-1}$). It follows that there is a bijection between infinite binary sequences $r_0,r_1,\ldots$ and elements $\alpha\in\mathbb{Z}_2$.

Choose an infinite binary sequence $r_0,r_1,\ldots$ that is not eventually constant. This determines a value $\alpha\in\mathbb{Z}_2$ so that the sequence obtained by starting with $\{0,\alpha,\alpha,1\}$ is not eventually constant. As an example, I took $r_n=n$ mod $2$, and using a computer I solved for $$ \alpha \equiv 2 + 2^{2} + 2^{3} + 2^{5} + 2^{12} + 2^{13} + 2^{17} + 2^{18} + 2^{21} + 2^{24} \mod 2^{25}. $$ The sequence of exponents does not show up in OEIS.


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.