Skip to main content
1 of 2
Mark Lewko
  • 13k
  • 1
  • 55
  • 87

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

Mark Lewko
  • 13k
  • 1
  • 55
  • 87