The following is an old result of Erdős and Turán (American Mathematical Monthly, 1934):

Given a set of $2^n + 1$ distinct positive integers, all of its two-term sums cannot be composed of the same $n$ primes. (An integer $m$ is said to be composed of primes $p_1, p_2, \dots$ is every prime factor of $m$ is one of those primes. And in two-term sums we exclude sums of two copies of the same integer.)

Let $f(n)$ be the minimum number such that given $f(n)$ distinct positive integers, all its two-term sums cannot be composed of the same $n$ primes. Erdős and Turán conjecture that the upper bound $f(n) \le 2^n + 1$ can be greatly improved. For example, they conjecture that $f(n) = O(n^{1+ \epsilon})$ for every fixed $\epsilon > 0$.

Does anyone know if any progress has been made on this problem since? In particular is there any polynomial upper bound known?

Also I would be interested to know about lower bounds on $f(n)$.


This problem and generalizations of it are discussed in the following papers:

  1. P. Erdős, A. Sárközy, C. Stewart, On prime factors of subset sums. J. London Math. Soc. (2) 49 (1994), no. 2, 209–218.
  2. C. Stewart, On prime factors of integers which are sums or shifted products. Anatomy of integers, 275–287, CRM Proc. Lecture Notes, 46, Amer. Math. Soc., Providence, RI, 2008.
  3. C. Stewart, R. Tijdeman, On prime factors of sums of integers. II. Diophantine analysis (Kensington, 1985), 83–98, London Math. Soc. Lecture Note Ser., 109, Cambridge Univ. Press, Cambridge, 1986.

I am fairly sure that no improvement to the Erdos-Turan result is known. However, there is a very closely related problem where one considers two sets. First note we can reformulate the Erdos-Turan result as the estimate

$$w(\prod_{a,b \in S} (a+b)) \gg \log(|S|)$$

where $w$ denotes the number of prime factors of an integer. Now a natural generalization of the above is the inequality

$$w(\prod_{a \in A, b \in B, |A|=|B|=k} (a+b)) \gg \log(k)$$

This was conjectured by Erdos and Turan and proved by Gyory, Steward, and Tijdeman in 1986. In this more general setting it was proved by Erdos, Steward and Tijdeman in 1994 that this estimate is nearly optimal. More specifically,

$$w(\prod_{a \in A, b \in B, |A|=|B|=k} (a+b)) \geq (1/8+\epsilon) \log(k)^2 \log\log(k)$$ can't hold for any $\epsilon >0$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.