MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$.

share|cite|improve this question
up vote 5 down vote accepted

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$.

share|cite|improve this answer
Thanks very much for the references. – Matthew Kahle May 24 '13 at 16:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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