Is this sufficient condition for infinite number generation from a finite seed also a necessary one?

322 Views Asked by At

Given an initial finite set of natural numbers (the seed). Use the following rule to add numbers to the set. If $a,b,a+b \in S \rightarrow ab \in S$. Where $S$ is the is set. For example take the initial seed $\{2,3,5\}$.

$2,3,5 \in S \rightarrow 6 \in S \quad$ So now the new set is $\{2,3,5,6\}$

$3,3,6 \in S \rightarrow 9 \in S \quad$ So now the new set is $\{2,3,5,6,9\}$

$3,6,9 \in S \rightarrow 18 \in S \quad$ So now the new set is $\{2,3,5,6,9,18\}$

$9,9,18 \in S \rightarrow 81 \in S \quad$ So now the new set is $\{2,3,5,6,9,18,81\}$

This seven-element set ends the generation, no new numbers can be added.

Now let's look at a second example where the initial seed is $\{2,3,4,5\}$

$2,3,5 \in S \rightarrow 6 \in S \quad$ So now the new set is $\{2,3,4,5,6\}$

$2,4,6 \in S \rightarrow 8 \in S \quad$ So now the new set is $\{2,3,4,5,6,8\}$

There is enough at this point to show that the set will be infinite.

Let $x \in \Bbb{N}\space|\space x\gt 1$. If there is the pattern of elements $x,2x,3x,4x$ in $S$ then the rule will produce infinite numbers. (In this example we have $2,4,6,8$.)

$x,x,2x \in S \rightarrow x^2 \in S$

$x,2x,3x \in S \rightarrow 2x^2 \in S$

$x,3x,4x \in S \rightarrow 3x^2 \in S$

$2x,2x,4x \in S \rightarrow 4x^2 \in S$

This means the new set will now contain $x^2, 2x^2, 3x^2, 4x^2$. This is inductive.

This condition of having $x,2x,3x,4x$ in the set is sufficient to show that there is an infinite number of numbers that will be generated.

My question is this a necessary condition to produce an infinite set? In other words does there exist a finite seed that can generate infinite sets without any subset (from the seed or generated sets) of the form ${x,2x,3x,4x}$?

(@Ingix showed that the previous version of the question wasn't explicit enough the new formulation was made because of his critique)

I want to address potential confusion about sets and cardinality to people in the future who are reading this problem. I had this confusion and so did one other person in the comments. When we are determining the size of a set (some finite size, or infinite) only the number of unique items gets counted. This subtle fact about sets is important to this problem because if we had the seed $\{0\}$. What we could do is $0,0,0 \in S \rightarrow 0 \in S$. Then our new set is $\{0,0\}$. This new set is just an inefficient way of writing the same set we had previously because both sets have the same number of unique items. Adding another $0$ doesn't change any of the properties of the set including the size. So you cannot create a set with infinite size just from the seed $\{0\}$

1

There are 1 best solutions below

1
On BEST ANSWER

Quick summary: No, the set generated by the seed $\{22, 66, 88, 198, 220, 264, 286, 352\}$ is infinite and does not contain $\{z, 2z, 3z, 4z\}$ as subset for any positive integer $z$.


Let's prove this is indeed the case. For any positive integer $x$, we will define the set $A(x):=\{1x, 3x, 4x, 9x, 10x, 12x, 13x, 16x\}$. The generative rule applied to this set gives us $$\begin{array}{|r|r|r|r|} \hline a & b & a+b & a\times b \\ \hline 1x & 3x & 4x & 3x^2 \\ 1x & 9x & 10x & 9x^2 \\ 1x & 12x & 13x & 12x^2 \\ 3x & 9x & 12x & 27x^2 \\ 3x & 10x & 13x & 30x^2 \\ 3x & 13x & 16x & 39x^2 \\ 4x & 9x & 13x & 36x^2 \\ 4x & 12x & 16x & 48x^2 \\ \hline \end{array}$$

As it turns out, the rightmost column corresponds precisely to set $A(3x^2)$. Thus, if we start with the seed of the form $A(x)$ for any $x$, repeated applications of the generative rule will produce an infinite set. Moreover, if we start with $x_0$ large enough and define $A_n:=A(3^{2^n-1}x_0^{2^n})$ for non-negative integers $n$, this infinite set $S$ will be precisely of the form $$S = \bigcup_{i=0}^\infty A_i$$

We will show that $x_0=22$ suffices and the corresponding set $S$ is indeed closed under the generative rule.

Since $3x^2 > 16x$ for $x\geq 6$, the greatest element of $A_i$ is always strictly smaller than the smallest element of $A_{i+1}$ and so any element belonging to $S$ is member of exactly one $A_i$.

Now, consider any two elements $a\leq b$ of $S$. If $b\in A_i = A(x)$ for some $x$, we have $b\leq 16x$ and the sum $a+b\leq 2\times 16x=32x$. However, $32x<3x^2$ for $x\geq 11$, so $a+b$ cannot belong to $A(y)$ for any $y>x$ and thus must belong to $A(x)$. On the other hand, if $a+b$ and $b$ both lie in $A(x)$, their difference (= $a$) cannot be smaller than $x$ and thus $a\in A(x)$ too. However, if $a$, $b$ and $a+b$ all belong to $A(x)$, then $a\times b\in A(3x^2) = A_{i+1}\subset S$.

Last but not least, we would like to show that the set $S$ does not contain a subset of the form $\{z,2z,3z,4z\}$ for any integer $z$. If $z\in A(x)$ for some $x$, we have $z\leq 16x$ so $4z\leq 4\times 16x=64x$ and $64x<3x^2$ for $x\geq 22$. Thus, all four elements $z, 2z, 3z, 4z$ must belong to the same $A(x)$ and it is trivial to check no such quadruplet exists in any $A(x)$.


Note that there is nothing special about this particular set $\{1,3,4,9,10,12,13,16\}$; we could have started with any set which avoids the $\{z,2z,3z,4z\}$ pattern and which gets mapped to (a multiple of) itself by the generative rule. Any such set can be scaled up sufficiently to make it work as a seed for an infinite set, while maintaining the pattern-avoidance property (e.g. multiplying all elements of such set by anything greater than its maximum element is certainly sufficient).