Partitions of the odd integers

Question

Understanding the nature of the odd integers is a necessity to prepare oneself to work on the unsolved problems in number theory, such as the Collatz $3n+1$ problem. I hope to demonstrate how the odd integers can be represented as a sequence of sets which fit together like a glove with infinite fingers. First, some definitions are required.

Define a sequence $(A_k)$ of ordered sets by:

$$ A_0 = \{3, 7, 11\} $$ $$ A_1 = \{1, 9, 17\} $$ $$ A_2 = \{13,29,45\} $$ $$ A_3 = \{5, 37, 69\} $$ and $$ A_{k+2} = A_k + 4 ( A_k – A_{k-2}) \forall k>1, $$

Note that the operations implied are matrix addition, subtraction and scalar multiplication on the $1 \times 3$ matrices formed from sets $A_k.$

For example, when $k=2$ we have: $$ A_2 = \{13,29,45\}, \mbox{ in matrix form is }\begin{pmatrix}13 \\29 \\45\end{pmatrix} $$ $$ A_0 = \{3, 7, 11\}, \mbox{ in matrix form is }\begin{pmatrix}3\\ 7\\ 11\end{pmatrix} $$

By definition: $$A_4 = A_2 + 4 ( A_2 - A_0) $$ $$ A_4 = \begin{pmatrix}13\\ 29\\ 45\end{pmatrix} + 4\left(\begin{pmatrix}13\\ 29\\ 45\end{pmatrix} - \begin{pmatrix}3\\ 7\\ 11\end{pmatrix}\right)$$ $$ A_4 = \begin{pmatrix}13\\ 29\\ 45\end{pmatrix} + 4\begin{pmatrix}10\\ 22\\ 34\end{pmatrix} $$ $$ A_4 = \begin{pmatrix}13\\ 29\\ 45\end{pmatrix} + \begin{pmatrix}40\\ 88\\ 136\end{pmatrix} $$ $$ A_4 = \begin{pmatrix}53\\ 117\\ 181\end{pmatrix} $$

Converting back to set notation gives: $$ A_4 = \{53, 117, 181\} $$

The next step is to extend the finite sets $\,A_k\,$ to infinite sets $\,M_k\,$ as follows:

Define: $$ M_k = \left\{p \in \mathcal{N}, p \equiv 1 \pmod 2 : \exists a \in A_k, p\equiv a\pmod {3\left(2^{k+2}\right)} \right\} $$

By definition of $M_0$: if $(a \in A_0)$, then $$ a + 12i \in M_0, \forall i \in \mathcal{N},$$

By definition of $M_k$: if $ (a \in A_k)$ then $$ a+3i(2^{k+2}) \in M_k, \forall i \in \mathcal{N}. $$

Assertion: $$ \forall n \in \mathcal{N}, n\equiv 1\pmod 2,\,\exists k \in \mathcal{N}, k\geq0 \text { such that } n \in M_k $$

Since this analysis was developed informally, is there a better way to express the assertion in order to search for prior solutions?

Answer 1

Answer: The goal is to establish that all odd integers map to one of the sets $A_k$ or $M_k$, or to find an equivalent problem statements. Note that while $A_k \subset {M_k}\,$, showing where the patterns of mappings shift from $A_k$ to $M_k$ is useful to find an equivalent problem statement.

(PART I)

The initial sixteen mappings between the odd integers and the elements of $A_k$ and $M_k$ are given below. The arrangement into 4 maps per row is intentional as this will establish a pattern that will be useful later.

$$ 1 \in A_1; 3 \in A_0; 5 \in A_3; 7 \in A_0 $$ $$ 9 \in A_1; 11 \in A_0; 13 \in A_2; 15 \in M_0; $$ $$ 17 \in A_1; 19 \in M_0; 21 \in A_5; 23 \in M_0; $$ $$ 25 \in M_1; 27 \in M_0; 29 \in A_2; 31 \in M_0; $$ and so on for all odd integers.

Note that first, second and fourth elements of each above row map to elements of sets with the same value of $\,k\,$ repeatedly (and continue infinitely), while the mappings from the third elements vary.

(PART II)

It remains to show that the third of every four odd natural numbers is in $M_k$ for some K>1; These elements form the set: $$ T = \{p\in N, p \equiv 5 \pmod 8\} $$

Observe that the pattern of how T maps to $A_k$ or $M_k$ is similar to the initial pattern for the odd integers:

$$ 5\in A_3; 13\in A_2; 21\in A_5; 29 \in A_4 $$ $$ 37 \in A_3; 45 \in A_2; 53 \in A_4; 61 \in A_2 $$ $$ 69 \in A_3; 77 \in A_2; 85 \in A_7; 93 \in M_2 $$ $$ 101 \in M_3; 109 \in M_2; 117 \in A_4; 125 \in M_2 $$

The similarity to part I is in the pattern of the subscripts. The pattern is as follows, take k=0 for part I, and k=2 for the set T;

$$ A_{k+1}; A_k; A_{k+3}; A_k $$ $$ A_{k+1}; A_k; A_{k+2}; M_k $$ $$ A_{k+1}; M_k; A_{k+5}; M_k $$ $$ M_{k+1}; M_k; A_{k+4}; M_k $$

While the pattern of the third element would eventually reveal itself by continuing to map odd integers as in Part I, the above observation provides a shortcut. The ninth element of Part I and T each map to the third element of their respective sets $A_{k+1}$. At the same time, the value of the eleventh element of Part I and T both map to their respective sets $A_{k+3}$, signaling it is time to introduce a new set with the next level of pattern based on k=4.

(PART III)

This section will formally define a sequence of sets which describe the above observations:

DEFINITION:

$$ S_k = \{p \in \mathcal{N}, p \equiv {f \left(k\right)} \pmod {2^{k+1}}, \forall k \in \mathcal{N}, k\equiv 0\pmod 2 \}$$ $$ \text { where } \{f \left(k\right) = \sum_{i=0}^k \,4^i \} $$

Recall that the question is whether the sequence of sets $M_k$ cover (aka partition) the odd integers. The sequence of sets $S_k$ introduced in this answer are equivalent to generating the sets $M_k$ by the recursion formula in the question. To see this relationship, subsets of the sets $\,S_k\,$ may be constructed. To more formally define them:

$$ S_{k,0} = \{p \in \mathcal{N}, p \equiv {f \left(k\right)} \pmod {2^{k+3}}\}\, , \forall k \in \mathcal{N}, k\equiv 0\pmod 2 $$ $$ S_{k,1} = \{p \in \mathcal{N}, p \equiv {\left(f \left(k\right) + 2^{k+1}\right)} \pmod {2^{k+3}}\}\, , \forall k \in \mathcal{N}, k\equiv 0\pmod 2 $$ $$ S_{k,2} = \{p \in \mathcal{N}, p \equiv {\left(f \left(k\right) + 2^{k+2}\right)} \pmod {2^{k+3}}\}\, , \forall k \in \mathcal{N}, k\equiv 0\pmod 2 $$ $$ S_{k,3} = \{p \in \mathcal{N}, p \equiv {\left(f \left(k\right) + \left(3\times 2^{k+1}\right)\right)} \pmod {2^{k+3}}\}\, , \forall k \in \mathcal{N}, k\equiv 0\pmod 2 $$ $$ \text { where } \{f \left(k\right) = \sum_{i=0}^k \,4^i \} $$

Next, observe that: $$ S_{k,0}\, \equiv M_{k+1} \forall k \in \mathcal{N}, k \equiv 1\pmod 2 .$$ $$ \left(S_{k,1} \cup S_{k,3} \right)\, \equiv M_k \forall k \in \mathcal{N}, k \equiv 1\pmod 2 .$$

So, the sequence $\,\left(S_k\right)\,$ generates the sets $\,\left(M_k\right)\,$.

Thus, to prove the assertion: $$ \forall n \in \mathcal{N}, n\equiv 1\pmod 2,\,\exists k \in \mathcal{N}, k\geq0 \text { such that } n \in M_k, $$

one could equivalently show:

$$ \forall n \in \mathcal{N}, n\equiv 1\pmod 2,\, \exists k \in \mathcal{N}, k \equiv 0 \pmod 2 \text { such that } n \in \left(M_k \cup {M_{k+1}} \cup {\left(S_{k,2}\right)}\right) $$.

(APPENDIX - CHARTS)

$$ S_k= $$ $$ \begin{array} {lllll} \\ S_{k,0}=M_{k+1} & S_{k,1} \subset M_k & S_{k,2} = \cup_{j=k+2}^\infty \left(M_j\right) & S_{k,3} \subset M_k \\ \hline \color{red}{f(k)} & f(k)+2^{k+1} & \color{red}{f(k+2)} & f(k+2)+2^{k+1}\\ f(k)+2^{k+3} & f(k)+2^{k+1}+2^{k+3} & f(k+2)+2^{k+3} & f(k+2)+2^{k+1}+2^{k+3}\\ f(k)+2^{k+4} & f(k)+2^{k+1}+2^{k+4} & \color{red}{f(k+4)} & f(k+2)+2^{k+1}+2^{k+4}\\ \vdots & \vdots & \vdots & \vdots \\ \end{array} $$

The chart above illustrates several points related to why the sets S_k from this answer are an improvement on the sets M_k from my question:

1. No recursive calculation is needed, just calculate f(k) directly.
2. $S_{k,0}$, $S_{k,1}$ and $S_{k,3}\,$ isolate all the members of $\,M_k\,$ into one or two columns of the table, if you are interested in working with a particular modulo set.
3. $S_{k,2}\,$ retains the linear nature of the pattern, but one can just stop reading it after the third entry and switch to the next tableau for f(k+2).
4. The red entries highlight that f(k+2) in the first row, third column is the pivot point for this process.

Answer 2

Hmm, I don't know whether I understand your problem correctly, as I have extremely difficulties to understand your basic definitions and the intent of/idea behind the $A$ and $M$ - perhaps the difficulties would disappear when also my flue disappears... but it seems to me it should be related to the following, so let's see. If I'm completely off feel free to ask me to delete this whole treatize.

First you look at the odd integers, the difference between all is two:
$ \qquad \begin{array} {l|rrrrrrr} A_{2,1}:& 1&3&5&7&9&11&13& ...\end{array} $
That set covers fully the (sub) set of odd integers.
Then you separate them into two subsets, each one with fixed difference of four:
$ \qquad \begin{array} {l|rrrrrrr} A_{4,1}:& 1&5&9&13& ... \\ \hline A_{4,3}:& 3&7&11&15& ... \\ \end{array} $
Of course this still covers the whole set of odd integers.

Next you leave one of the sets untouched and split the other one in two with distances of eight:
$ \qquad \begin{array} {l|rrrrrrr} A_{8,5}:& 5&13&21& 29& ... \\ A_{8,1}:& 1&9&17&25& ... \\ \hline A_{4,3}:& 3&7&11&15& ... \\ \end{array} $
Because you don't miss any number by simply separating you are still covering the whole set of odd integers.

We proceed in the same manner: one of the $A_{8,k}$ sets is left untouched, the other one is split into two with distances of 16:
$ \qquad \begin{array} {l|rrrrrrr} A_{16,5}:& 5&21&37&53& ... \\ A_{16,13}:& 13&29&46&61& ... \\ \hline A_{8,1}:& 1&9&17&25& ... \\ A_{4,3}:& 3&7&11&15& ... \\ \end{array} $
Because we only separated one partial set into two keeping all their elements we are still covering the whole set of odd integers.

---

As I understood your question I think this is now intended to proceed in the obvious way. It is clear that this gives an infinite partitioning of the odd numbers, and none is missing.

The only remaining interesting question is then how to define which of the two new subsets is kept untouched and which one shall be splitted (let us denote the subsets by their then leading number).
My own proposal (see pg 6 in my small treatize) for how to define the process of splitting by the leading numbers of the created subsets is to introduce a very simple rule. Let's define the sets/sequences
$ \qquad \begin{array} {l|rrrrrrr} L_{1}:& 1&5&21&85& ... \\ L_{3}:& 3&13&53&253& ... \\ \end{array} $
with the general terms
$$ \begin{array} {rlll} L_{1,k} &\underset{k \ge 1}{=} & \Large {4^k -1\over 4-1} & \qquad & L_{3,k} &\underset{k \ge 0}{=} & \Large {10 \cdot4^k -1\over 4-1} \end{array}$$ (The first splittings match your given ones, I think that will inherit also to the full scheme.)
Then if you use this proposal for the definition of the partitioning scheme for the subsets, then you can state the following nice scheme for the transfer-formulae for the Collatz transformation:

$$ \begin{array} {rlll|rlllll} C & a &\to &b &C& a&\to &b \\ \hline 1 & 4k + 3 &\to& 6k+5 & 2 & 8k+1&\to & 6k+1 \\ 3 & 16k + 13 &\to& 6k+5 & 4 & 32k+5&\to & 6k+1 \\ 5 & 64k + 53 &\to& 6k+5 & 6 &128k+21&\to & 6k+1 \\ \vdots &&& &\vdots \end{array} \tag 1$$

which -for example- means, that the number $13$ transfers by $(13\cdot3+1)/2^3$ to $5$ as well as all other numbers $a_k$ of the scheme $a_k=16 \cdot k+13 $ transfer by $((13+16 \cdot k)\cdot3+1)/2^3=(40+48k)/8=6k+5$ to the expected $ b_k=6k+5$. For instance, let $k=2$ then $a_2=45$ and $(45 \cdot 3+1 )/ 2^3 = 136/8 = 17 = b_2 = 6 \cdot 2 + 5$

---

You can now sophisticate the table (1) making even better indexes by observing that the column $C$ provides the exponents of $2$ for the $8,16,32,64,... $ -coefficients (the distances in the explicite partitioning scheme above) and also can be used to index the constant residuals taken from the sets/sequences $L_1$ amd $L_3$, so that finally the numbers $a,b$ involved in a Collatz-transformation can be indexed like$a_{C,k} $ and $b_{C,k}$ .

(Additional remark: the scheme can simply be extended "downwards" to include the even numbers too without breaking the basic rules. Also it can be applied to the negative numbers (by using negative k$$), where we even find nontrivial cycles in the Collatz-transformation. Finally: this scheme has simple analogues in the generalized Collatz-maps, for instance 5x+1, 7x+1 and so on and it is interesting to see the $L$-sequences and $C$-tables there)

Answer 3

This is not an answer and shall be deleted later, it is just too long for a comment and I'm asking, whether I got the understanding of the S-sets correct. If I made errors, please feel free to correct them inline if possible

That's what I think to have understood, a bit simplified in notation Let $k=2j$ and $j \in N$ then we define sets $S_{k,m=1..4}$ by $$ \begin{array} {lll} S_{2j,0} &=& f (2j) & & \pmod {2^{2j+3}} \\ S_{2j,1} &=& f (2j) &+ 1 \cdot 2^{2j+1} & \pmod {2^{2j+3}} \\ S_{2j,2} &=& f (2j) &+ 2 \cdot 2^{2j+1} & \pmod {2^{2j+3}} \\ S_{2j,3} &=& f (2j) &+ 3 \cdot 2^{2j+1} & \pmod {2^{2j+3}} \end{array}$$ $$ \text { where } f \left(k\right) = \sum_{i=0}^k \,4^i = {4^{k+1}-1 \over 4-1} $$ With this I got numerically $$ \begin{array} {lll} S_{j,0} &\underset{j \ge 0}{=}& \{1,5, 21,85,...\} \\ S_{j,1} &\underset{j \ge 0}{=}& \{3,13, 53,213,...\} \\ S_{j,2} &\underset{j \ge 0}{=}& \{5,21, 85,341,...\} \\ S_{j,3} &\underset{j \ge 0}{=}& \{7,29,117,469,...\} \\ \end{array} $$

Of course, if this is correct so far, then it can be further simplified and straightened in that the $\pmod {2^{2j+3}}$ is not needed because the coefficients to be evaluated are always smaller than that modulus.

Answer: The modulus is needed to fully extend the partition for $S_{k,0}$, $S_{k,1}$ and $S_{k,3}$. It is only for $\,S_{k,2}\,$ that I subdivide further by setting $\,S_{k+2}\,$ = $\,S_{k,2}$.

And while I might have understood the sets $S_{j,0},S_{j,1}$ correctly (they would then be the $L$-sets in my scheme) I do not understand the function of the $S_{j,2},S_{j,3}$ and also I do not understand why we use only even $k$ (resp. $2j$ in my proposed notation) ?

ANSWER: I use only even k for S because each level corresponds to two levels of my original sets $A_k$ and $M_k$. Indeed:

$$S_{k,0} \equiv M_{k+1}$$ $$\left(S_{k,1} \cup S_{k,3}\right) \equiv M_k \, and $$ $$ S_{k,2} = S_{k+2}.$$