Technical Summary: A Boolean Polynomial Operator for the Collatz 3n + 1 Problem

Problem Statement

The paper addresses the Collatz $3n+1$ problem, a longstanding question in number theory concerning whether the map $C(k)$, defined as $k/2$ for even $k$ and $3k+1$ for odd $k$, eventually reaches 1 for every positive integer input. The author reformulates this problem by consolidating the divisions by 2 into a single step, leading to the map $O(k) = 2^{v_2(k)} + 3k$, where $v_2(k)$ is the exponent of the highest power of 2 dividing $k$. The objective is to express this operator $O$ as a transformation on sequences of Boolean polynomials, thereby analyzing the problem through the lens of algebraic structures over the field $\mathbb{F}_2$.

Methodology

The paper constructs a framework where integers are represented as sequences of elements in a Boolean algebra $R = \mathbb{F}_2[x_1, \dots, x_n]/I$, where $I$ is the ideal generated by $x_i^2 - x_i$. An integer $k$ corresponds to a sequence $y = (y(i))_{i=1}^\infty$ representing its binary expansion.

The core methodology involves defining the operator $O$ through a series of Boolean operations:

1. Addition and Carries: The paper defines an Add operation on sequences $u$ and $v$ which produces a sum sequence and a corresponding "carry sequence" $c(u, v)$. The carry sequence is defined recursively based on the standard logic of binary addition.
2. Component Maps:
   • PlusPowerTwo(y): Represents the addition of $2^{v_2(k)}$ to $3k$. This is constructed using the sequence defined by PlusPowerTwo(y) = (y(j)P(y; j -1))_{j=1}^\infty, where $P(y; j) = \prod_{i=1}^j (1 + y(i))$. This term facilitates the carry logic required to add $2^{v_2(k)}$ to the sequence.
   • Shift1(y): Represents the multiplication by 2 (a left shift in binary).
3. Composition: The map $O(y)$ is defined as the result of adding PlusPowerTwo(y) to Shift1(y). This composition involves two layers of carry sequences:
   • $\gamma(y)$: The carry sequence resulting from adding $y$ and PlusPowerTwo(y).
   • $\delta(y)$: The carry sequence resulting from adding the intermediate sum and Shift1(y).

The paper aims to derive explicit polynomial formulas for the terms of the resulting sequence $O(y)$ in terms of the input sequence $y$.

Key Contributions and Results

1. Explicit Formula for the Operator

The primary result (Theorem 1) provides an explicit formula for the $i$-th term of the operator output $O(y)(i)$:
$$O(y)(i) = \delta(y; i) + \gamma(y; i) + y(i)P(y; i - 1) + y(i) + y(i - 1)$$
This reduces the problem of iterating the Collatz map to calculating the carry sequences $\gamma$ and $\delta$.

2. Formula for the First Carry Sequence ($\gamma$)

The paper derives an explicit formula for $\gamma(y; j+1)$, the carry sequence associated with adding $y$ and $2^{v_2(k)}$.

• Theorem 2 states that $\gamma(y; j+1)$ can be expressed as a sum involving products of the input sequence terms and the polynomial $P$. Specifically, it is a sum over $k$ of terms involving $P(y; j-2k-2)$ and a product term $U$ defined over the sequence $y$.
• The proof utilizes induction and the property that $y(i)(1+y(i)) = 0$ in the Boolean ring to simplify recursive definitions.

3. Formula for the Second Carry Sequence ($\delta$)

The derivation for $\delta(y)$, the carry sequence for the final addition, is more complex.

• Lemma 1 establishes a crucial orthogonality property: $\gamma(y; j)\delta(y; j) = 0$. This implies that the two carry sequences cannot be simultaneously active at the same index.
• Lemma 2 decomposes $\delta(y; j+1)$ into two components, $\delta_1$ and $\delta_2$, based on the recursive definition of the carry sequence.
• Theorem 3 provides an explicit formula for $\delta_2$ using the term $V_2$, which involves products of $y$ terms with alternating parity constraints.
• Theorem 4 provides a comprehensive explicit formula for $\delta_1$ (and by extension $\delta$) by characterizing the subsets of indices that contribute non-zero terms. This involves defining "skip-1 sets" and "block sequences" of subsets of indices. The formula expresses the sum over specific subsets $S$ as a combination of the polynomials $P$, $V_1$, and $U$.

4. Structural Definitions

The paper introduces several combinatorial definitions to manage the complexity of the carry sequences:

• Block Sequences: Decomposing subsets of indices into contiguous intervals (blocks).
• Skip-1 Sets: Sets where the gaps between blocks are of length 1.
• Lead Sets: Specific subsets derived from the block structure that determine the non-zero contributions to the carry sums.

Significance and Claims

The paper claims to provide a "reformulation" of the Collatz map that expresses it as an operator on sequences of Boolean polynomials. By deriving explicit formulas for the carry sequences $\gamma$ and $\delta$, the author translates the arithmetic dynamics of the $3n+1$ problem into the algebraic structure of Boolean polynomials.

The significance lies in the explicit nature of these formulas. Rather than simulating the map numerically, the paper offers a closed-form algebraic representation of the iteration step $O(k)$. The author notes in the "Further Work" section that the next logical step is to analyze the carry sequences for the specific combinations of PlusPowerTwo and Shift1 to potentially uncover patterns or invariants within the Boolean framework. The paper does not claim to solve the Collatz conjecture but rather to establish a new algebraic language for describing the map's behavior.