$X$ is an infinite subset of $\mathbb Z^{+}$ and $T=\{x+y\mid x,y \in X, x\neq y\}$. Prove the set of prime factors of numbers in $T$ is also infinite

Question

Let $X$ be an infinite subset of positive integers and $T=\{x+y\mid x,y \in X, x\neq y\}$. Prove the set of prime factors of numbers in $T$ is also infinite.

My thought was to borrow the idea from the proof that there are infinitely many prime numbers. Suppose the prime factors of $T$ is $\{p_1, p_2,\dots, p_z\}$ and let $x=p_1^{n_1} \cdot p_2^{n_2}\cdot \dots \cdot p_z^{n_z}$ and $y=p_1^{m_1} \cdot p_2^{m_2}\cdot \dots \cdot p_z^{m_z}$, prove that we can introduce a new prime factor when we sum $x+y$. But unfortunately I didn't get very far. I think I couldn't find a way to leverage the fact that $X$ is infinite.

Answer 1

Sorry for deferring the problem to such a deep result such as Thue’s Theorem, but if you don’t mind about that, this does the trick.

Suppose otherwise that every integer in $T$ has prime factors of at most $p$. Take $x_1,x_2\in X$, with $x_1<x_2$. It can be proved that there are finitely many $p$-smooth numbers at distance $x_2-x_1$, see here. Therefore, there can only be finitely many $x\in\mathbb Z$ with $x+x_1,x+x_2\in T$, contradiction since $X$ is infinite. $\blacksquare$

Answer 2

An elementary solution

Consider a counterexample to the required result with $P$, the set of prime factors of $T$, having minimal cardinality.

Lemma 1 Let $p\in P$ be odd. Then, for any natural number $n$, there are infinitely many elements of $X$ which are divisible by $p^n$.

Suppose that, for some $n$, only finitely many elements of $X$ are divisible by $p^n$. Then for some $i$ there are infinitely many elements of $X$ divisible by $p^i$ but not $p^{i+1}$. Restrict $X$ to these elements and then, by dividing every element of $X$ by $p^i$, we obtain a set where no element of $X$ is divisible by $p$.

There are only finitely many residue classes modulo $p$ and so at least one of these has infinitely many elements in $X$. Restrict $X$ to this class and let $x,y\in X$. Then $x+y\equiv 2x$ (mod $p$). Then $p$ can be dropped from $P$ and, by induction, we are finished.

Lemma 2 For any natural number $n$, either infinitely many elements of $X$ are divisible by $2^n$ or all elements are odd and congruent modulo $4$ .

As in Lemma 1, we can obtain a set where all elements are odd. Then infinitely many elements are congruent to at least one of $1$ and $3$ modulo $4$. Restrict $X$ to an infinite set of congruent elements.

Main proof

Let $x$ be any element of $X$. For odd $p\in P$ let $p^n$ be the highest power dividing $x$. Delete from $X$ all elements other than $x$ which are not divisible by $p^{n+1}$ and note that this still leaves an infinite set. We can now divide all elements by $p^n$. Repeat for all such primes $p$.

We are left with an element $x$ not divisible by any odd prime in $P$ and all other elements in $ X$ divisible by every odd prime in $P$. Furthermore, the same is true for the prime $2$ unless all the elements are odd and congruent modulo $4$.

Now consider $x+y$ for all $y\in X-x$. These sums are either not divisible by any prime in $P$ or are powers of $2$ which are not divisible by $4$. This contradiction completes the proof.