Skip to main content
MathOverflow

Return to Answer

clarify, and improve bound
Source Link
Emil Jeřábek
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

$\def\U#1{\underline{#1}}\def\O#1{\overline{#1}}$The bound $a_n=O(n)$ is true, in fact, we have $a_n\le\max\{16p,16q,\frac{32}3n\}$ or so$a_n\le\max\{8p,8q,\frac{16}3n\}$. The argument is quite elementary, but a bit tedious to write down properly, hence I will only sketch it, and rely on the reader to fill in the details.

Case 2: $a_n\bmod2$ is $\dots001001001\dots$ of period $3$. Carries from $0$th to $1$st bit happen at the positions of the $0$s in the period. (Here and below, the pattern shown is not necessarily aligned with the start of the sequence, hence strictly speaking the period is one of its cyclic shifts.)

This implies a bound on $a_n$ as follows. For a given $n$, let $k$ be the least integer such that $n<3\cdot 2^k$ and $p,q<2^{k+1}$. Thus, $2^k\le\max\{p,q,2n/3\}$. We know from above that up to $a_n$, there are at most three carries to the $(k+1)$th bit. The first of these will attain the value $2^{k+1}$, the other two may at most get to $2^{k+3}$. Thus, the most significant bit of $a_n$ is at position at most $k+3$. Actually, andtaking into account the relative position of the carries modulo 3, one can check that the most significant bit can only become at most $a_n<2^{k+4}\le\max\{32n/3,16p,16q\}$$k+2$. Thus, $a_n<2^{k+3}\le\max\{16n/3,8p,8q\}$.

$\def\U#1{\underline{#1}}\def\O#1{\overline{#1}}$The bound $a_n=O(n)$ is true, in fact, we have $a_n\le\max\{16p,16q,\frac{32}3n\}$ or so. The argument is quite elementary, but a bit tedious to write down properly, hence I will only sketch it, and rely on the reader to fill in the details.

Case 2: $a_n\bmod2$ is $\dots001001001\dots$ of period $3$. Carries from $0$th to $1$st bit happen at the positions of the $0$s in the period.

This implies a bound on $a_n$ as follows. For a given $n$, let $k$ be the least integer such that $n<3\cdot 2^k$ and $p,q<2^{k+1}$. Thus, $2^k\le\max\{p,q,2n/3\}$. We know from above that up to $a_n$, there are at most three carries to the $(k+1)$th bit. The first of these will attain the value $2^{k+1}$, the other two may at most get to $2^{k+3}$. Thus, the most significant bit of $a_n$ is at position at most $k+3$, and $a_n<2^{k+4}\le\max\{32n/3,16p,16q\}$.

$\def\U#1{\underline{#1}}\def\O#1{\overline{#1}}$The bound $a_n=O(n)$ is true, in fact, we have $a_n\le\max\{8p,8q,\frac{16}3n\}$. The argument is quite elementary, but a bit tedious to write down properly, hence I will only sketch it, and rely on the reader to fill in the details.

Case 2: $a_n\bmod2$ is $\dots001001001\dots$ of period $3$. Carries from $0$th to $1$st bit happen at the positions of the $0$s in the period. (Here and below, the pattern shown is not necessarily aligned with the start of the sequence, hence strictly speaking the period is one of its cyclic shifts.)

This implies a bound on $a_n$ as follows. For a given $n$, let $k$ be the least integer such that $n<3\cdot 2^k$ and $p,q<2^{k+1}$. Thus, $2^k\le\max\{p,q,2n/3\}$. We know from above that up to $a_n$, there are at most three carries to the $(k+1)$th bit. The first of these will attain the value $2^{k+1}$, the other two may at most get to $2^{k+3}$. Thus, the most significant bit of $a_n$ is at position at most $k+3$. Actually, taking into account the relative position of the carries modulo 3, one can check that the most significant bit can only become at most $k+2$. Thus, $a_n<2^{k+3}\le\max\{16n/3,8p,8q\}$.

Source Link
Emil Jeřábek
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

$\def\U#1{\underline{#1}}\def\O#1{\overline{#1}}$The bound $a_n=O(n)$ is true, in fact, we have $a_n\le\max\{16p,16q,\frac{32}3n\}$ or so. The argument is quite elementary, but a bit tedious to write down properly, hence I will only sketch it, and rely on the reader to fill in the details.

Rather than estimating $a_n$ directly, we will try to bound the position of the most significant bit of $\max_{m\le n}a_m$. Notice that $\oplus$ cannot raise this quantity, and ${}+1$ can raise it only by one bit, when it results in a power of $2$ larger than all the previously seen numbers. In this case the ${}+1$ operation involves carries all the way from the $0$th bit to the new most significant bit. Thus, the crucial thing is to investigate carries in the sequence.

For any $k\ge1$, the operations of $\oplus$ and ${}+1$ are well defined modulo $2^k$, hence we can look at the sequence $a_n\bmod2^k$. Since the sequence is uniquely reversible mod $2^k$ by $a_{n-1}=a_n\oplus(a_{n+1}-1)$, it must be periodic mod $2^k$.

When computing $a_n$, there is a carry from $(k-1)$th bit to $k$th bit iff $a_n\equiv0\pmod{2^k}$; for $k>1$, this holds iff there was a carry to the $(k-1)$th bit, and the $(k-1)$th bit of $a_n$ is $0$. Let us denote the $k$th bit of $a_n$ as $a_{n,k}\in\{0,1\}$.

Case 1: $a_n\bmod2$ (that is, $a_{n,0}$) is $\dots1111\dots$. Then there are no carries whatsoever, hence $a_n=O(1)$ and we are done.

Case 2: $a_n\bmod2$ is $\dots001001001\dots$ of period $3$. Carries from $0$th to $1$st bit happen at the positions of the $0$s in the period.

This again splits to two subcases:

Case 2a: $a_n\bmod4$ is $\dots122320122320\dots$ of period $6$. That is, the sequence of $a_{n,1}$ is $\dots\O{\U0}\U11\U1\U10\dots$, where underlines signify carries from the $0$th bit to the $1$st bit, and overlines carries from the $1$st bit to the $2$nd bit.

Case 2b: $a_n\bmod4$ is $\dots120300120300\dots$ of period $6$; that is, the sequence of $a_{n,1}$ is $\dots0\U1\O{\U0}1\O{\U0}\O{\U0}\dots$.

I claim that in Case 2a, for all $k\ge2$, the sequence $a_n$ has period $3\cdot2^{k-1}$ modulo $2^k$, and there is carry to the $k$th bit at exactly one position per period.

This is proved by induction on $k$. It holds for $k=2$. When going from $k$ to $k+1$, we see that the sequence $a_{n,k}$ is a $\oplus$-linear combination of:

  1. A solution of the homogeneous recurrence $b_n=b_{n-2}\oplus b_{n-1}$ modulo $2$. This is either $\dots00000\dots$, or (some shift of) $\dots011011011\dots$.

  2. One particular solution of $b_n=b_{n-2}\oplus b_{n-1}\oplus c_n$, where $c_n$ is the sequence of carries to the $k$th bit. By the induction hypothesis, $c_n$ is $3\cdot2^{k-1}$-periodic, and the period has the form $100\dots0$. Thus, one solution $b_n$ is given by the $3\cdot2^k$-periodic sequence consisting of $110110110\dots110$ for $3\cdot2^{k-1}$ positions, followed by $00\dots0$ for $3\cdot2^{k-1}$ positions.

Clearly, this makes $a_{n,k}$ (and thus $a_n\bmod2^{k+1}$) $3\cdot2^k$-periodic. Carries to the $(k+1)$th bit may happen only at the two positions in this period that correspond to carries to the $k$th bit; these two positions are at distance $3\cdot2^{k-1}$ apart, and they are occupied by two opposite bits: the sequence from 1. gives them the same value, whereas the sequence from 2. gives them opposite values. Thus, exactly one of them gives rise to a carry to the $(k+1)$th bit.

In Case 2b, a similar inductive argument establishes the following claim: for any $k\ge2$, $a_n\bmod2^k$ is $3\cdot2^{k-1}$-periodic, and there are exactly $3$ carries to the $k$th bit in each period. Two of these carries have the same position modulo $3$, whereas the third is at relative position $2$ modulo $3$ with respect to them.

This implies a bound on $a_n$ as follows. For a given $n$, let $k$ be the least integer such that $n<3\cdot 2^k$ and $p,q<2^{k+1}$. Thus, $2^k\le\max\{p,q,2n/3\}$. We know from above that up to $a_n$, there are at most three carries to the $(k+1)$th bit. The first of these will attain the value $2^{k+1}$, the other two may at most get to $2^{k+3}$. Thus, the most significant bit of $a_n$ is at position at most $k+3$, and $a_n<2^{k+4}\le\max\{32n/3,16p,16q\}$.