Proof for bijection of a function between positive integers and nonprime positive integers.

Question

Exercise 4.39 on Concrete Mathematics mentioned a function $S(m)$:

Let $S(m)$ be the smallest positive integer $n$ for which there exists an increasing sequence of integers $$ m = a_1 < a_2 < \cdots < a_t = n$$ such that $a_1a_2...a_t$ is a perfect square.

...

We have: $$ \begin{array}{c|cc} m & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ \hline S(m) & 1 &6&8&4&10&12&14&15&9&18&22&20 \end{array}$$

This exercise proved that $S(i)≠S(j)$ for different $i$, $j$ and left a remark that "the sequence $S(1),\ S(2),\ S(3),\ ...$ contains every nonprime positive integer exactly once" in the appendix "Answers to Exercises" but gave no cue or reference to it. I have no idea about it's proof.

Answer 1

Very interesting question!

Let us first prove that S(m) can not be prime. This follows from the fact that such a sequence can not end in a prime, as the product would only be divisible once by this prime.

To prove it is a bijection from all integers greater than $1$ to all composite numbers, we give the inverse. The inverse $S^{-1}(n)$ is the greatest possible $m$ such that such a sequence exists. Note that this is well-defined for composite numbers as you can take the sequence to be all primes dividing into $n$ an odd number of times.

To prove this gives an inverse, we need to show $S^{-1}(S(m))=m$ holds for all $m$. This is because, if a sequence ending with $S(m)$ exists with a higher starting number than $m$, then taking the symmetric difference with the sequence starting with $m$ and ending with $S(m)$ gives a sequence starting with $m$ and with lower ending number than $S(m)$.

Answer 2

For a composite positive integer $n$, define $T(n)$ to be the largest positive integer $m$ for which there exists an increasing sequence of integers $ m = a_1 < a_2 < \cdots < a_t = n$ such that $a_1a_2\cdots a_t$ is a perfect square. (Trivially $T(n)=n$ if $n$ is a perfect square; if $n$ is not a perfect square, then $n$ factors as $n=ab$ with $a<b$, in which case $T(n) \ge a$ and, in particular, is well-defined.)

The proof that $S$ is one-to-one can be quickly adapted to show that $T=S^{-1}$ (give it a try!). This is enough to show that the sequence $S(1), S(2), S(3),\dots$ contains every nonprime positive integer exactly once.

Answer 3

Let $n$ be a composite number. Then there are sequences $a_1<a_2<\cdots <a_r = n$ such that $a_1a_2\cdots a_s$ is a square. For instance, if $n = ab$ with $a<b<n$ (which is possible since $n$ is composite), we have $a\cdot b \cdot n = n^2$.

Since there are sequences, and they all have starting points less than or equal to $n$, there is a highest starting point, say $m$. Let $m = b_1<b_2<\cdots b_s = n$ be one such sequence.

Clearly $S(m)\leq n$, as the sequence $b_i$ shows. I claim we have equality. Assume for contradiction that $S(m) < n$. Let $m = c_1\cdot c_2\cdots c_s = S(m)$ be a sequence such that $c_1c_2\cdots c_s$ is a square. Then $$ b_1b_2\cdots b_s\cdot c_1c_2\cdots c_t $$ is a square. It remains a square if we take away all the terms that appear twice. $m = b_1 = c_1$ appears twice, so the smallest factor in the stripped-down product is larger than $m$. And the largest factor is still $n$, since $b_s = n$ but $c_t<n$.

What we end up with is a sequence of distinct integers which if we multiply them together we get a square, the largest of them is $n$ and the smallest is larger than $m$, contradicting the definition of $m$.

This shows that $S(m) = n$.