3

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?

kodlu
  • 10,131
  • 2
  • 34
  • 53

1 Answers1

7

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

Fedor Petrov
  • 102,548
  • 2
    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). – alpoge Dec 01 '15 at 15:33
  • 1
    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". – alpoge Dec 01 '15 at 15:41
  • 2
    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. – Fedor Petrov Dec 01 '15 at 16:26
  • @FedorPetrov: Thanks, I will need to digest some of that. – kodlu Dec 01 '15 at 19:39
  • @alpoge: Thank you, I will need to think about what you're saying. Do you mind writing a detailed answer? – kodlu Dec 01 '15 at 19:42
  • @FedorPetrov:can you clarify the reference to Abel transform? – kodlu Dec 04 '15 at 03:23
  • 1
    @kodlu it is explained in the answer: expand $1/m=\sum_{v\geq m} 1/(v(v+1))$ and change order of summation – Fedor Petrov Dec 04 '15 at 08:21
  • @alpoge is the absolute constant $C$ in Selberg's result known? Are bounds on it known? – kodlu Sep 09 '16 at 08:25
  • 1
    @kodlu Yeah sure! Check out http://mathoverflow.net/questions/35927/asymptotic-density-of-k-almost-primes . 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.) – alpoge Sep 10 '16 at 19:52