3
$\begingroup$

A primitive sequence $1<a_1<\ldots<a_k\leq n$ is a sequence of integers no one of which divides any other, investigated by Erdos, Behrend and others, over the last 80 years. In fact, $\max k=\lfloor \frac{n+1}{2}\rfloor,$ which can be shown by taking exactly one member from each chain in the divisibility poset, namely $$C_x=\{x,2x,2^2x,\ldots\} \subset \{1,\ldots,n\}$$as $x$ ranges over the odd integers in $\{1,\ldots,n\}$. The easy examples of such sets, e.g., the numbers in $\{1,\ldots,n\}\cap [\lceil \frac{n}{2} \rceil,n]$ have the following property $$\sum_{i:a_i\leq n} \frac{1}{a_i} \leq c$$ for some absolute constant $c$ as $n$ increases.

However, Erdos states that S. Pillai observed that there is a constant $c'$ such that for every $n$ there is a finite primitive sequence all whose terms are upper bounded by $n$ such that $$\sum_{i:a_i\leq n} \frac{1}{a_i} > c' \frac{\log n}{\sqrt{\log \log n}}.$$

Are there any results on what such sequences may look like?

Edit: Is the value of the constant $c'$ or bounds on it known?

$\endgroup$
7
$\begingroup$

Fix $k$ and consider the set $E_k$ of all numbers with exactly $k$ prime factors (counted with multiplicity). They definitely form a primitive sequence. Already for $k=1$ sum of reciprocals is unbounded. I think, for $k=[\log \log n]$ we should obtain lower bound like $\log n/\sqrt{\log\log n}$. It is natural to expect: randomly chosen number in $[1,n]$ has exactly $k$ prime factors with probability about $1/\sqrt{\log\log n}$ by Erdős-Kac theorem

Denote $k=[\log \log n]$. Then by result of Selberg cited by alpoge in the comments, $|E(k)\cap [1,x]|\geq C x/\sqrt{k}$ for all $x\in [\sqrt{n},n]$. It follows that $$ \sum_{m\in E(k)\cap [1,n]} m^{-1}\geq \sum_{m\in E(k),n\geq v\geq m} \frac1{v(v+1)}\geq \sum_{v=\sqrt{n}}^n \frac1{v(v+1)}|E(k)\cap [1,v]|\geq c\log(n)/\sqrt{k} $$ for some $c>0$.

$\endgroup$
  • 2
    $\begingroup$ Indeed the number of integers $n\leq x$ with exactly $k\leq 1.99\log\log{x}$ prime factors is $\sim \frac{x}{\log{x}} \frac{(\log\log{x})^k}{k!}$. Taking $k = \log\log{x} + O(1)$ and using Stirling gives the lower bound you claim (upon splitting the sum into dyadic intervals and applying the asymptotic). $\endgroup$ – alpoge Dec 1 '15 at 15:33
  • 1
    $\begingroup$ I always forget the constant! There should be a constant $f((k-1)/\log\log{x})$ in the asymptotic, too. This is proved in Selberg's "Note on a paper by L.G. Sathe". $\endgroup$ – alpoge Dec 1 '15 at 15:41
  • 2
    $\begingroup$ We need not "many numbers", but "large sum of reciprocals", it is slightly different thing. But since this works for all $x$, Abel transform works. $\endgroup$ – Fedor Petrov Dec 1 '15 at 16:26
  • 1
    $\begingroup$ @kodlu it is explained in the answer: expand $1/m=\sum_{v\geq m} 1/(v(v+1))$ and change order of summation $\endgroup$ – Fedor Petrov Dec 4 '15 at 8:21
  • 1
    $\begingroup$ @kodlu Yeah sure! Check out mathoverflow.net/questions/35927/… . Btw I see above I gave the count of n\leq X with k+1 prime factors, not k factors! (Of course what I said is not correct for k=1.) $\endgroup$ – alpoge Sep 10 '16 at 19:52

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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