\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 $jn$, 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 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 $np_{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 .