\input amstex
\openup.8\jot
\magnification=1200
\def\nspace{\lineskip=1pt\baselineskip=12pt\lineskiplimit=0pt}
\def\halfspace{\lineskip=1pt\baselineskip=15pt\lineskiplimit=0pt}
\def\dspace{\lineskip=2pt\baselineskip=18pt\lineskiplimit=0pt}
\def\tspace{\lineskip=2pt\baselineskip=30pt\lineskiplimit=0pt}

\def\rightwaveyarrow{\sim\!\!\sim\!\!\sim\kern-6.25pt
     \hbox{\lower.1pt\hbox{$\succ$}}}
\def\downwaveyarrow{\hbox{
     $\wr$\hbox{\kern-3pt\lower4.75pt\hbox{$\wr$}}\hbox{\kern-2.5pt
     \lower9.75pt\hbox{$\wr$}}
     \hbox{\kern-8.5pt\lower 14.5pt
     \hbox{$\curlyvee$}}}}
\def\upwaveyarrow{\hbox{
     $\curlywedge$\kern-4.60pt\lower4.0pt\hbox{$\wr$}
     \kern-6.0pt\lower11.0pt\hbox{$\wr$}
     \kern-6.0pt\lower17.5pt\hbox{$\wr$}}}


\def\bak{{\kern-1.1em }}
\def\bakk{{\kern-1.6em}}
\def\bakg{{\kern-.385em}}
\def\bakf{{\kern-.8em}}
\def\card{{\rm card\ }}
\def\shalf{{\textstyle {1\over 2}}}
%Greek letters
\def\alp{\alpha}		\def\Alp{\Alpha}
\def\bet{\beta}		
\def\gam{\gamma}		\def\Gam{\Gamma}
\def\del{\delta}		\def\Del{\Delta}
\def\eps{\varepsilon}		
\def\zet{\zeta}
\def\tet{\theta}		\def\Tet{\Theta}
\def\iot{\iota}
\def\kap{\kappa}
\def\lam{\lambda}		\def\Lam{\Lambda}
\def\sig{\sigma}		\def\Sig{\Sigma}
\def\ups{\upsilon}              \def\Ups{\Upsilon}
\def\vphi{\varphi}
\def\ome{\omega}		\def\Ome{\Omega}

%Caligraphic roman letters (Script)
\def\calA{{\Cal A}}            \def\calN{{\cal N}}
\def\calB{{\Cal B}}            \def\calO{{\cal O}}
\def\calC{{\Cal C}}            \def\calP{{\Cal P}}
\def\calD{{\cal D}}            \def\calQ{{\cal Q}}
\def\calE{{\cal E}}            \def\calR{{\cal R}}
\def\calF{{\cal F}}            \def\calS{{\Cal S}}
\def\calG{{\cal G}}            \def\calT{{\cal T}}
\def\calH{{\cal H}}            \def\calU{{\cal U}}
\def\calI{{\Cal I}}            \def\calV{{\cal V}}
\def\calJ{{\Cal J}}            \def\calW{{\cal W}}
\def\calK{{\cal K}}            \def\calX{{\cal X}}
\def\calL{{\Cal L}}            \def\calY{{\cal Y}}
\def\calM{{\Cal M}}            \def\calZ{{\cal Z}}

%Bold roman letters
\def\bfa{{\bold a}}		\def\bfA{{\bf A}}
\def\bfb{{\bold b}}		\def\bfB{{\bf B}}
\def\bfc{{\bold c}}		\def\bfC{{\bf C}}
\def\bfd{{\bf d}}		\def\bfD{{\bf D}}
\def\bfe{{\bf e}}		\def\bfE{{\bf E}}
\def\bff{{\bf f}}		\def\bfF{{\bf F}}
\def\bfg{{\bold g}}		\def\bfG{{\bf G}}
\def\bfh{{\bold h}}		\def\bfH{{\bf H}}
\def\bfi{{\bf i}}		\def\bfI{{\bf I}}
\def\bfj{{\bf j}}		\def\bfJ{{\bf J}}
\def\bfk{{\bold k}}		\def\bfK{{\bf K}}
\def\bfl{{\bf l}}		\def\bfL{{\bf L}}
\def\bfm{{\bold m}}		\def\bfM{{\bf M}}
\def\bfn{{\bold n}}		\def\bfN{{\bf N}}
\def\bfo{{\bf o}}		\def\bfO{{\bf O}}
\def\bfp{{\bold p}}		\def\bfP{{\bf P}}
\def\bfq{{\bf q}}		\def\bfQ{{\bf Q}}
\def\bfr{{\bf r}}		\def\bfR{{\bf R}}
\def\bfs{{\bf s}}		\def\bfS{{\bf S}}
\def\bft{{\bf t}}		\def\bfT{{\bf T}}
\def\bfu{{\bold u}}		\def\bfU{{\bf U}}
\def\bfv{{\bold v}}		\def\bfV{{\bf V}}
\def\bfw{{\bf w}}		\def\bfW{{\bf W}}
\def\bfx{{\bold x}}		\def\bfX{{\bf X}}
\def\bfy{{\bold y}}		\def\bfY{{\bf Y}}
\def\bfz{{\bold z}}		\def\bfZ{{\bf Z}}

\def\bfalp{{\underline \alp}}
\def\bfeta{{\boldsymbol \eta}}
\def\bflam{{\boldsymbol \lam}}  \def\bfLam{{\boldsymbol \Lam}}
\def\bfxi{{\boldsymbol \xi}}
\def\bfphi{{\boldsymbol \phi}} \def\bfPhi{{\boldsymbol \Phi}}
\def\bfPsi{{\boldsymbol \Psi}}
\def\bfUps{{\boldsymbol \Ups}}
\def\bfalppi{{{\bfalp \bfp}^i}}

%roman letters with a tilde
\def\Atil{{\tilde A}}          \def\atil{{\tilde a}}
\def\Btil{{\tilde B}}          \def\btil{{\tilde b}}
\def\Ctil{{\tilde C}}          \def\ctil{{\tilde c}}
\def\Dtil{{\tilde D}}          \def\dtil{{\tilde d}}
\def\Etil{{\tilde E}}          \def\etil{{\tilde e}}
\def\Ftil{{\tilde F}}          \def\ftil{{\tilde f}}
\def\Gtil{{\tilde G}}          \def\gtil{{\tilde g}}
\def\Htil{{\tilde H}}          \def\htil{{\tilde h}}
\def\Itil{{\tilde I}}          \def\itil{{\tilde i}}
\def\Jtil{{\tilde J}}          \def\jtil{{\tilde j}}
\def\Ktil{{\tilde K}}          \def\ktil{{\tilde k}}
\def\Ltil{{\tilde L}}          \def\ltil{{\tilde l}}
\def\Mtil{{\tilde M}}          \def\mtil{{\tilde m}}
\def\Ntil{{\tilde N}}          \def\ntil{{\tilde n}}
\def\Otil{{\tilde O}}          \def\otil{{\tilde o}}
\def\Ptil{{\tilde P}}          \def\ptil{{\tilde p}}
\def\Qtil{{\tilde Q}}          \def\qtil{{\tilde q}}
\def\Rtil{{\tilde R}}  	       \def\rtil{{\tilde r}}
\def\Stil{{\tilde S}}	       \def\stil{{\tilde s}}
\def\Ttil{{\tilde T}}          \def\ttil{{\tilde t}}
\def\Util{{\tilde U}}          \def\util{{\tilde u}}
\def\Vtil{{\tilde V}}          \def\vtil{{\tilde v}}
\def\Wtil{{\tilde W}}          \def\wtil{{\tilde w}}
\def\Xtil{{\tilde X}}          \def\xtil{{\tilde x}}
\def\Ytil{{\tilde Y}}          \def\ytil{{\tilde y}}
\def\Ztil{{\tilde Z}}          \def\ztil{{\tilde z}}

%roman letters with an overline 
\def\abar{{\overline a}}	\def\Abar{{\overline A}}
\def\bbar{{\overline b}}	\def\Bbar{{\overline B}}
\def\cbar{{\overline c}}	\def\Cbar{{\overline C}}
\def\dbar{{\overline d}}	\def\Dbar{{\overline D}}
\def\ebar{{\overline e}}	\def\Ebar{{\overline E}}
\def\fbar{{\overline f}}	\def\Fbar{{\overline F}}
\def\gbar{{\overline g}}	\def\Gbar{{\overline G}}
\def\hhbar{{\overline h}}	\def\Hbar{{\overline H}}
\def\ibar{{\overline i}}	\def\Ibar{{\overline I}}
\def\jbar{{\overline j}}	\def\Jbar{{\overline J}}
\def\kbar{{\overline k}}	\def\Kbar{{\overline K}}
\def\lbar{{\overline l}}	\def\Lbar{{\overline L}}
\def\mbar{{\overline m}}	\def\Mbar{{\overline M}}
\def\nbar{{\overline n}}	\def\Nbar{{\overline N}}
\def\obar{{\overline o}}	\def\Obar{{\overline O}}
\def\pbar{{\overline p}}	\def\Pbar{{\overline P}}
\def\qbar{{\overline q}}	\def\Qbar{{\overline Q}}
\def\rbar{{\overline r}}	\def\Rbar{{\overline R}}
\def\sbar{{\overline s}} 	\def\Sbar{{\overline S}}
\def\tbar{{\overline t}}	\def\Tbar{{\overline T}}
\def\ubar{{\overline u}}	\def\Ubar{{\overline U}}
\def\vbar{{\overline v}}	\def\Vbar{{\overline V}}
\def\wbar{{\overline w}}	\def\Wbar{{\overline W}}
\def\xbar{{\overline x}}	\def\Xbar{{\overline X}}
\def\ybar{{\overline y}}	\def\Ybar{{\overline Y}}
\def\zbar{{\overline z}}      	\def\Zbar{{\overline Z}}

%roman letters with a hat
\def\ahat{\widehat a}		\def\Ahat{\widehat A}
\def\bhat{\widehat b}		\def\Bhat{\widehat B}
\def\chat{\widehat c}		\def\Chat{\widehat C}
\def\dhat{\widehat d}		\def\Dhat{\widehat D}
\def\ehat{\widehat e}		\def\Ehat{\widehat E}
\def\fhat{\widehat f}		\def\Fhat{\widehat F}
\def\ghat{\widehat g}		\def\Ghat{\widehat G}
\def\hhat{\widehat h}		\def\Hhat{\widehat H}
\def\ihat{\widehat i}		\def\Ihat{\widehat I}
\def\jhat{\widehat j}		\def\Jhat{\widehat J}
\def\khat{\widehat k}		\def\Khat{\widehat K}
\def\lhat{\widehat l}		\def\Lhat{\widehat L}
\def\mhat{\widehat m}		\def\Mhat{\widehat M}
\def\nhat{\widehat n}		\def\Nhat{\widehat N}
\def\ohat{\widehat o}		\def\Ohat{\widehat O}
\def\phat{\widehat p}		\def\Phat{\widehat P}
\def\qhat{\widehat q}		\def\Qhat{\widehat Q}
\def\rhat{\widehat r}		\def\Rhat{\widehat R}
\def\shat{\widehat s}		\def\Shat{\widehat S}
\def\that{\widehat t}		\def\That{\widehat T}
\def\uhat{\widehat u}		\def\Uhat{\widehat U}
\def\vhat{\widehat v}		\def\Vhat{\widehat V}
\def\what{\widehat w}		\def\What{\widehat W}
\def\xhat{\widehat x}		\def\Xhat{\widehat X}
\def\yhat{\widehat y}		\def\Yhat{\widehat Y}
\def\zhat{\widehat z}		\def\Zhat{\widehat Z}

%Special fonts
\font\smc=cmcsc10
\font\titlefont=cmr10 scaled\magstep2
\font\boldtitlefont=cmb10 scaled\magstep2
\font\namfont=cmr12
\font\teneuf=eufm10 \font\seveneuf=eufm7 \font\fiveeuf=eufm5
\font\tenmsy=msbm10 \font\sevenmsy=msbm7 \font\fivemsy=msbm5
\font\tenmsx=msam10 \font\sixmsx=msam6 \font\fivemsx=msam5
\textfont7=\teneuf \scriptfont7=\seveneuf
\scriptscriptfont7=\fiveeuf
\textfont8=\tenmsy \scriptfont8=\sevenmsy
\scriptscriptfont8=\fivemsy
\textfont9=\tenmsx \scriptfont9=\sixmsx
\scriptscriptfont9=\fivemsx
\def\gr{\fam7 \teneuf}
\def\db{\fam8 \tenmsy}
\def\sym{\fam9 \tenmsx}

%Euler Fraktur letters (German)
\def\grA{{\gr A}}	\def\gra{{\gr a}}
\def\grB{{\gr B}}	\def\grb{{\gr b}}
\def\grC{{\gr C}}	\def\grc{{\gr c}}
\def\grD{{\gr D}}	\def\grd{{\gr d}}
\def\grE{{\gr E}}	\def\gre{{\gr e}}
\def\grF{{\gr F}}	\def\grf{{\gr f}}
\def\grG{{\gr G}}	\def\grg{{\gr g}}
\def\grH{{\gr H}}	\def\grh{{\gr h}}
\def\grI{{\gr I}}	\def\gri{{\gr i}}
\def\grJ{{\gr J}}	\def\grj{{\gr j}}
\def\grK{{\gr K}}	\def\grk{{\gr k}}
\def\grL{{\gr L}}	\def\grl{{\gr l}}
\def\grM{{\gr M}}	\def\grm{{\gr m}}
\def\grN{{\gr N}}	\def\grn{{\gr n}}
\def\grO{{\gr O}}	\def\gro{{\gr o}}
\def\grP{{\gr P}}	\def\grp{{\gr p}}
\def\grQ{{\gr Q}}	\def\grq{{\gr q}}
\def\grR{{\gr R}}	\def\grr{{\gr r}}
\def\grS{{\gr S}}	\def\grs{{\gr s}}
\def\grT{{\gr T}}	\def\grt{{\gr t}}
\def\grU{{\gr U}}	\def\gru{{\gr u}}
\def\grV{{\gr V}}	\def\grv{{\gr v}}
\def\grW{{\gr W}}	\def\grw{{\gr w}}
\def\grX{{\gr X}}	\def\grx{{\gr x}}
\def\grY{{\gr Y}}	\def\gry{{\gr y}}
\def\grZ{{\gr Z}}	\def\grz{{\gr z}}
%Capital roman double letters
\def\dbA{{\db A}}        \def\dbN{{\db N}}
\def\dbB{{\db B}}        \def\dbO{{\db O}}
\def\dbC{{\db C}}        \def\dbP{{\db P}}
\def\dbD{{\db D}}        \def\dbQ{{\db Q}}
\def\dbE{{\db E}}        \def\dbR{{\db R}}
\def\dbF{{\db F}}        \def\dbS{{\db S}}
\def\dbG{{\db G}}        \def\dbT{{\db T}}
\def\dbH{{\db H}}        \def\dbU{{\db U}}
\def\dbI{{\db I}}        \def\dbV{{\db V}}
\def\dbJ{{\db J}}        \def\dbW{{\db W}}
\def\dbK{{\db K}}        \def\dbX{{\db X}}
\def\dbL{{\db L}}        \def\dbY{{\db Y}}
\def\dbM{{\db M}}        \def\dbZ{{\db Z}}

%Special definitions
\def\ttbacksl{{\tt\char'134}}
\def\leaderfill{\leaders\hbox to 1em
     {\hss.\hss}\hfill}
\def\Q.E.D.{\line{\null\hfill Q.E.D.}}
\def\q.e.d.{\line{\null\hfill q.e.d.}}
\def\nl{\hfil\break}
\def\upchi{\hbox{\raise 2pt\hbox{$\chi$}}}
\def\upvphi{\hbox{\raise 2pt\hbox{$\vphi$}}}
\def\upgam{\hbox{\raise 2pt\hbox{$\gam$}}}
\def\VVert{\Vert\kern-1pt\vert}
\def\noint{\mathop{-\kern-10.0pt\int}}
\def\tnoint{\mathop{-\kern-8.5pt\int}}
\def\all{\forall}
\def\colon{{:}\;}
\def\half{{1\over2}}
\def\downmapsto{\downarrow\raise4.75pt\hbox{\kern-7.70pt --}}
\def\bigdownmapsto{\Big\downarrow\raise9.5pt\hbox{\kern-6pt
     --}}
\outer\def\shalom{\bigskip\rightline\today\par\vfill\supereject\end}
\def\shvor{\discretionary{}{}{}}
\def\subsetarrow{\subset\kern-6.0pt\raise2.25pt\hbox{$\to$}}
\def\supsetarrow{\raise2.25pt\hbox{$\gets$}\kern-6.0pt\supset}
\def\arrowsim{\smash{\mathop{\to}\limits^{\lower1.5pt\hbox{$\scriptstyle
     \sim$}}}}
\def\dashright{\hbox{-\ -\ -\ -$\kern-3pt$
     \hbox{\lower.1pt\hbox{$\succ$}}}}
\mathchardef\twoheadedrightarrow="7910
\def\vrulecup{\kern1.28pt\cup\kern-4.0pt\vrule height 6.0pt}
\def\dotcup{\mathop{\cup\kern-5pt\cdot}}
\def\backupharpoon{\hbox{$\lower.25pt
     \hbox to 25pt{\hrulefill}\kern-5.25pt\smallsetminus$}}

\def\squarea{\mathchoice\sqr34\sqr34\sqr{2.1}3\sqr{1.5}3}
\def\squareb{\mathchoice\sqr54\sqr54\sqr{2.1}3\sqr{1.5}3}
\def\squarec{\mathchoice\sqr64\sqr64\sqr{2.1}3\sqr{1.5}3}
\def\squared{\mathchoice\sqr74\sqr74\sqr{2.1}3\sqr{1.5}3}
\def\squaree{\mathchoice\sqr84\sqr84\sqr{2.1}3\sqr{1.5}3}

\def\smalltype{\font \eightrm=cmr8 \font\eightbf=cmbx8 \let\rm=\eightrm \let\bf=\eightbf \baselineskip=12pt minus 1pt \rm }







%An AMSTEX file for a 5 page document.
\documentstyle{amsppt}
\loadbold
\topmatter
\title Maximal Sets of Integers with Distinct Divisors \endtitle
\leftheadtext { Maximal Sets of Integers with Distinct Divisors}
\author R. Balasubramanian  and  K. Soundararajan \endauthor
\affil Institute for Mathematical Sciences, 
Tharamani P. O., Madras 600 113, India. 
Department of Mathematics, Princeton University, 
Princeton, N. J. 08544, U.S.A. \endaffil
%\email skannan\@math.princeton.edu \endemail

\rightheadtext{R. Balasubramanian and K. Soundararajan}
\dedicatory Submitted: May 23, 1995; Accepted October 22, 1995
\enddedicatory
\subjclass Primary 11A05 \endsubjclass
\abstract A set of positive integers is said to have the {\sl
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{\H o}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)$.

\endabstract

\endtopmatter
\font\smcp=cmcsc8
\headline={\ifnum\pageno>1{\smcp the electronic journal of
combinatorics 2 (1995), \#R22     \hfill \folio}\fi}

\def\al{\alpha}
\def\be{\beta}
\head 1. Introduction \endhead
\noindent Let ${ S}$ denote a set of positive integers and 
$\tau:{ S}\to {\Bbb N}$ be defined so that $\tau(s)$ is a 
proper divisor of $s$ (that is, $\tau(s)$ divides $s$ and $\tau(s) < s$).
The ensemble $({ S}, \tau)$ is said to have the `{\sl distinct 
divisor property}' if $\tau$ is injective, that is, if the $\tau(s)$ are 
different for different values of $s$. We will also say that 
${S}$ has the distinct divisor property if there exists a $\tau$,
as above,  such that $({S}, \tau)$ has the distinct divisor property.

\par Let $c > 1$ denote a real number and $N$ a large natural
number.  Let ${ S}$ be a subset of $[N,cN]$ with the 
distinct divisor property such that, of all subsets of $[N,cN]$ 
having distinct divisors, ${ S}$ has maximal cardinality. 
If $c$ is fixed and $N$ tends to infinity then P. Erd{\H o}s 
and C. Pomerance, [1], have shown that 
$$|S| = (\delta(c) +o(1))N$$ 
where $\delta(c)$ is a continuous increasing function of $c$.  
As $c$ tends to $1$ they established that 
$$\delta (c) = c-1 +o(1).$$
\par In this note we are concerned with the behaviour of
$\delta(c)$ as $c$ tends to infinity.  Division by $2$
clearly invests the set of even integers in $[N, cN]$ with
the distinct divisor property; hence $\delta(c) \ge
(c-1)/2$.  Also, since a proper divisor of an integer less than
$cN$ is less than $cN/2$ clearly $\delta(c) \le c/2$. 
Erd{\H o}s and Pomerance conjectured that this latter upper 
bound is actually the truth for large $c$.  In other words they
conjectured that as $c$ tends to infinity
$$\delta(c) = \frac{c}{2} +o(1).$$
We prove this and more by finding 
the exact order of magnitude for $c/2 - \delta(c)$ as
$c \to \infty$. 
\proclaim{Theorem 1}  There exist positive absolute constants 
$D_1$ and $D_2$ such that
$$\frac{D_1}{c^{\beta} } \le \frac{c}{2} - \delta(c) \le
\frac{D_2}{c^{\beta}}, $$
where $\beta = \log 2/ \log (3/2) = 1.7095\ldots$.
\endproclaim
We realise Theorem 1 as the sum of the following two
Propositions, which are proved by two very different arguments.

\proclaim{Proposition 2}  Let $k$ denote the greatest integer
not exceeding $\log c/\log (3/2)$.  Suppose ${ S}$ is a
subset of the integers in $[N, cN]$  and that $({ S},
\tau)$ satisfies the distinct divisor property.  Then 
$$\frac{cN}{2} - |{ S}| \ge \frac{N}{2^{k+2} } + O(k).$$
\endproclaim

\proclaim{ Proposition 3} Suppose $c >2$.  There exists a
subset, ${ S}$, of integers in $[N, cN]$ and a map $\tau$
such that $({ S}, \tau)$ obeys the distinct divisor
property and with 
$$\frac{cN}{2} - |{ S}| \ll \frac{N}{c^{\beta}}.$$
\endproclaim

All implied constants are absolute; that is they are independent
of $c$ and $N$.  The restriction to $c >2$ in Proposition 3 is
obviously harmless.  The presence of the constant $\beta$ is
best explained by noting that it is  the minimum value of the function
$\log p_i/\log (p_{i+1}/p_i)$ (where  
$p_i$ denotes the $i$th smallest prime).  
\smallskip

\par We thank Professor A. Granville to whom our present
exposition is largely due.  An earlier version of this note
proved the weaker result $\delta(c)=c/2+o(1)$.  We are grateful
to the referee, Professor C. Pomerance, who, by simplifying our
earlier proof, helped clarify the situation and motivated us to
strengthen our result.  


\def\pr{\prime}
\head 2. Proof of Proposition 2 \endhead
\noindent  We partition the interval $(N,cN]$ into the sets
$B_1 \cup B_2 \cup \dots \cup B_{k+1}$ where

\noindent 
$B_j = ( (2/3)^jcN,(2/3)^{j-1}cN]$ for $j=1,2,\dots, k$, and
$B_{k+1}=(N,(2/3)^kcN]$. Similarly we partition 
$[1,cN/2]$, where the potential divisors lie, into 
intervals $A_1 \cup A_2 \cup \dots \cup A_{k+2}$, where
$A_i = ( (2/3)^icN/2,(2/3)^{i-1}cN/2]$ for $i=1,2,\dots, k$, 

\noindent with $A_{k+1}=(N/2,(2/3)^kcN/2]$ and $A_{k+2}=(1,N/2]$. Note that 
if $s\in B_j$ then any proper divisor of $s$ must lie in some interval
$A_i$ with $i\geq j$; moreover, if that divisor lies in $A_j$,
then it must be $s/2$, since any other proper divisor is
$\leq s/3\leq (2/3)^{j-1}cN/3=(2/3)^jcN/2$ and thus belongs
to $A_i$ for some $i>j$.

Now $[cN/2]-|S|=[cN/2]-|\tau(S)|$ counts the number of integers in 
$[1,cN/2]$ that do not 
belong to $\tau (S)$. We obtain a lower bound for this quantity by
only counting, for each $i$, those integers $n\in A_i$ which do not belong to 
$\tau (S)$, and which are divisible by $2^{i-1}$. Thus
$$
[cN/2]-|S| \geq \sum_{i=1}^{k+2} \left( \# \{ n\in A_i:\ 2^{i-1}|n\} -
\# \{ s\in S: \tau(s) \in A_i, \ 2^{i-1}|\tau (s) \} \right) .
$$
As we saw above, if $\tau(s) \in A_i$ then $s\in B_j$ for some $j\leq i$.
Suppose that $2^{i-1}$ divides $\tau (s)$. We claim that $2^j$ divides $s$,
which follows if $j=i$ since $2^{j-1}$ divides $\tau(s)=s/2$; and which
follows if $j<i$ since then $2^j$ divides $2^{i-1}$, which divides 
$\tau(s)$, which divides $s$. Therefore
$$
\sum_{i=1}^{k+2} \# \{ s\in S: \tau(s) \in A_i, \ 2^{i-1}|\tau (s) \}
\leq \sum_{j=1}^{k+1} \# \{ s \in B_j: \ 2^j|s \} 
$$
(noting that, since $\tau$ is injective, no value of $s$ gets 
counted twice in the argument above).
Now $\# \{ n\in A_i:\ 2^{i-1}|n\} = \# \{ n\in B_i:\ 2^i|n\} + O(1)$,
so substituting this into the two displays above, we get
$$
[cN/2]-|S| \geq \# \{ n\in A_{k+2}:\ 2^{k+1}|n\} +O(k) = N/2^{k+2}+O(k) .
$$



\head 3. Proof of Proposition 3 \endhead
\noindent  We wish to construct a `big' set $S$ of integers $s$
in $[N,cN]$ with the distinct divisors $\tau(s)$; since $\tau$ is
injective, this is equivalent to constructing a `big' set 
$R=\tau (S) \subset [1,cN/2]$, such that for each $n\in R$,
there exists some distinct proper multiple $\tau^{-1}(n)$, of $n$, 
in $[N,cN]$. In fact we shall select $\tau^{-1}(n) = np(n)$ for
some prime $p(n)$, which we choose as follows:\
For $n=[cN/2]$ let $p([cN/2])=2$. For 
$n=[cN/2]-1, [cN/2]-2, \dots, 1$ we define $p(n)$
to be the {\sl largest} prime $p$ for which
\smallskip
i) \ \ \ $N < np \le cN$,\  and

ii) \ \ $np\ne n'p(n')$ for any $n'>n$, with $n'\leq [cN/2]$,
\smallskip
\noindent provided such a prime $p$ exists, otherwise we let 
$p(n)=0$
(and then $n\not \in R$). We note that $|S|=|R|$ is exactly the
number of integers $n\leq cN/2$ for which $p(n)\ne 0$; and thus
$$
[cN/2] - |S| = \# \{ n\leq cN/2:\ p(n)=0\} . \eqno(1)
$$

For each prime $p_k$, we define the set of integers
$${\Cal I}_k = \{ p_1^{\al_1} p_2^{\al_2} \ldots p_{k}^{\al_k}
:\,\, \al_k \ge 1, \,\, \prod_{j=1}^{k} (p_{j+1}/p_j)^{\al_j} > c/2 \}.$$

\proclaim {Lemma} If $p(n)=0$ for some integer $n \le cN/2$,
then there exists $k$ such that $n \le N/p_k$, and ${\Cal I}_k$ 
contains a divisor $d$ of $n$.  
\endproclaim

We now complete the proof of Proposition 3, postponing the proof of the Lemma:

\demo {Proof of Proposition 3} Using the Lemma we have
$$
\# \{ n\leq cN/2:\ p(n)=0\} \leq
\sum_{k\geq 1} \sum_{d \in {\Cal I}_k} \# \{ n \le N/p_k:\, \, d | n \} \le \sum_{k\geq 1}  \frac{N}{p_k}
\sum_{d \in {\Cal I}_k} \frac{1}{d} .\eqno(2)
$$
By definition, we have that 
$$
\sum_{d \in {\Cal I}_k} \frac{1}{d} 
\le \sum_{\al_k \geq 1} \frac{1}{p_k^{\al_k}}
\sum_{\al_{k-1}\geq 0}\frac{1}{p_{k-1}^{\al_{k-1}}} 
\ldots \sum_{\al_2 \geq 0} \frac{1}{p_2^{\al_2}}
\sum_{\al_1\geq A_1} \frac{1}{2^{\al_1}} , \eqno(3)
$$
where $(3/2)^{A_1} 
> (c/2) / \prod_{j=2}^{k} (p_{j+1}/p_j)^{\al_j}
\geq (c/2) / (5/3)^{(\al_2 + \al_3 + \dots + \al_k)}$,
from  the definition of the set ${\Cal I}_k$,
since $p_{j+1}/p_j \leq 5/3$ when $j\geq 2$.
Therefore, setting 
$\gamma = 2^{\log (5/3)/\log (3/2)} \approx 2.39471$, we get 
$$\sum_{\al_1\geq A_1} \frac{1}{2^{\al_1}} 
\ll \frac{1}{2^{A_1}} \ll
c^{-\beta} \gamma^{\al_2 + \al_3 + \dots + \al_k}.$$
Substituting this into (3) gives
$$
\align
\sum_{d \in {\Cal I}_k} \frac{1}{d} &\ll c^{-\beta}
\sum_{\al_k \geq 1} \left( \frac{\gamma}{p_k}\right)^{\al_k}
\sum_{\al_{k-1}\geq 0} 
\left( \frac{\gamma}{p_{k-1}}\right)^{\al_{k-1}} 
\ldots \sum_{\al_2 \geq 0} \left( \frac{\gamma}{p_2}\right)^{\al_2}\\
&=  c^{-\beta}\frac{\gamma}{p_k} 
\prod_{i=2}^k \left( 1 - \frac{\gamma}{p_i} \right)^{-1} 
\ll  c^{-\beta}\frac{1}{p_k} 
\prod_{3\leq p\leq p_k} \left( 1 - \frac{1}{p} \right)^{-\gamma}
\ll c^{-\beta} \frac{(\log p_k)^\gamma}{p_k} ,\\
\endalign
$$
using Mertens' theorem that
$\prod_{p\le x} (1-1/p) \asymp 1/\log x$ (see [2] for example). 
Substituting this estimate into (2), and that estimate back 
into (1), gives
$$
cN/2 - |S| =
\# \{ n\leq N/2:\ p(n)=0\} \ll c^{-\beta} N 
\sum_{k\geq 1}  \frac{(\log p_k)^\gamma}{p_k^2} \ll  N/c^{\beta} .
$$
\enddemo









Finally we return to the

\demo {Proof of the Lemma}  We must have $n\leq N/2$ for, if
$cN/2\geq n>N/2$ then $p=2$ satisfies 
i) $N < 2n \le cN$, and
ii) \ $2n\ne n'p(n')$ for any $n'>n$, since 
$n'p(n')\geq 2 n'>2n$,
so that $p(n)\geq 2$.

Let $p_{k_0}$ be the least prime exceeding $N/n$;
by Bertrand's postulate $p_{k_0} \le 2N/n < cN/n$
 (since $c >2$),
and so  $N <np_{k_0} \le cN$. However $p(n)=0$, which means 
that 
$np_{k_0}$ cannot satisfy (ii) above; in other words, there 
must exist
an integer $n_1>n$ such that $np_{k_0}=n_1p_{k_1}$ 
(where we define
$k_1$ so that $p_{k_1}=p(n_1)$). We note that $p_{k_0}>p_{k_1}$
(since $n_1>n$ and $np_{k_0}=n_1p_{k_1}$), so that 
$p_{k_1}\leq N/n$ and thus $n \le N/p_{k_1}$. 

We now construct a useful sequence of integers 
$n_1,n_2,n_3,\dots , n_m\in R$
(for some $m$); we show how to determine $n_{j+1}$ from $n_j$:\

Let $k_j$ be defined by the relation $p_{k_j}=p(n_j)$. 

{}\qquad $\bullet$ \ If $n_jp_{k_j+1}>cN$ then let $m=j$, and the sequence is terminated. 

{}\qquad $\bullet$ \ If $n_jp_{k_j+1}\leq cN$ then there must exist
an integer $n_{j+1}>n_j$ for which $n_jp_{k_j+1}=n_{j+1}p(n_{j+1})$
(else $p(n_j)\geq p_{k_j+1}$ by definition). 
\smallskip

Since $n_{j+1}p_{k_{j+1}+1}>n_{j+1}p_{k_{j+1}}=n_jp_{k_j+1}$, we
see that $n_1p_{k_1+1}< n_2p_{k_2+1}< n_3p_{k_3+1} < \dots$ 
forms
an increasing sequence of integers, and so we will eventually 
find an integer $m$ for which $n_mp_{k_m+1}>cN$. 

We have seen that $n<n_1<n_2<\dots <n_m$, and thus
$p_{k_0}>p_{k_1}\geq p_{k_2}\geq p_{k_3}\geq \dots \geq p_{k_m}$
(since $n_{j+1}>n_j$ and $n_jp_{k_j+1}=n_{j+1}p_{k_{j+1}}$
imply that $p_{k_j+1}>p_{k_{j+1}}$, and thus $p_{k_j}\geq p_{k_{j+1}}$).
Now $n_{j+1}=(p_{k_j+1}/p_{k_{j+1}})n_j$; iterating this gives
$$ n_j =  \left({p_{k_{j-1}+1}\over p_{k_j}} \right)  
\left( {p_{k_{j-2}+1}\over p_{k_{j-1}}}  \right) \dots
\left({p_{k_1+1}\over p_{k_2}} \right) 
\left({p_{k_0}\over p_{k_1}} \right) n .\eqno(4)
$$
Define $d=p_1^{\al_1} p_2^{\al_2} \ldots p_{k}^{\al_k} =
p_{k_m} p_{k_{m-1}}\dots p_{k_2} p_{k_1}$ where $k=k_1$.
We show that $d$ divides $n$ by proving that 
$p_i^{\al_i}$ divides $n$ for each $i$: \ Let $j$  be
the largest integer for which $k_j=i$. Then 
$p_{k_j} p_{k_{j-1}} \dots p_{k_1} = p_i^{\al_i} 
p_{i+1}^{\al_{i+1}} \ldots p_{k}^{\al_k}$. Moreover
$i\leq k_{j-1} < k_{j-1}+1 \leq k_{j-2}+1\leq \dots \leq k_1+1\leq k_0$,
and so $p_i$ is coprime with $p_{k_{j-1}+1}p_{k_{j-2}+1}\dots p_{k_1+1}p_{k_0}$.
Now, $p_i^{\al_i}$ divides 
$p_{k_j} p_{k_{j-1}} \dots p_{k_1}$, which is a divisor of 
$(p_{k_{j-1}+1}p_{k_{j-2}+1}\dots p_{k_1+1}p_{k_0})n$ by (4), 
since $n_j$ is an integer; and so 
$p_i^{\al_i}$ divides $n$.

To complete the proof of the Lemma we need to show that 
$d\in {\Cal I}_k$, which
we do by taking (4) with $j=m$, multiplying it by
$p_{k_{m+1}}$ and rearranging, to get
$$ \prod_{i=1}^k \left( {p_{i+i}\over p_i} \right)^{\al_i} =
 \left({p_{k_m+1}\over p_{k_m}}\right)  
 \left({p_{k_{m-1}+1}\over p_{k_{m-1}}}\right)  \dots
 \left({p_{k_1+1}\over p_{k_1}}\right)  = { n_m p_{k_m+1}  \over n p_{k_0}  } 
> {cN\over 2N} ={c\over 2} ,
$$
using the fact that $p_{k_0}\leq 2N/n$, by Bertrand's postulate.
\enddemo 



\Refs
\frenchspacing
\item{[1]} P. Erd{\H o}s and C. Pomerance, {\it An analogue of 
Grimm's problem of finding distinct prime factors of 
consecutive integers.} Util. Math. {\bf 24} (1983), 45-65.

\item{[2]} G. H. Hardy and E. M. Wright, {\it An introduction
to the theory of numbers.}  Fourth edition; New York; Oxford
University Press, 1960.

\endRefs
%22 May 1995
\enddocument






.
