Maximal Sets of Integers with Distinct Divisors

  • R. Balasubramanian
  • K. Soundararajan

Abstract

A set of positive integers is said to have the distinct divisor property if there is an injective map that sends every integer in the set to one of its proper divisors. In 1983, P. Erdős and C. Pomerance showed that for every $c>1$, a largest subset of $[N,cN]$ with the distinct divisor property has cardinality $\sim \delta(c)N$, for some constant $\delta(c)>0$. They conjectured that $\delta(c)\sim c/2$ as $c \to \infty$. We prove their conjecture. In fact we show that there exist positive absolute constants $D_1,D_2$ such that $D_1\le c^{\beta}(c/2-\delta(c))\le D_2$ where $\beta = \log 2/\log (3/2)$.

Published
1995-10-22
Article Number
R22