Background: The answer to a previous question I asked here specified a construction to achieve Pillai's bound on reciprocal sums of primitive sequences. A primitive sequence $1<a_1<\ldots<a_k\leq n$ is a sequence of integers no one of which divides any other. Pillai proved 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}}\quad(1).$$ The construction that achieves this bound is to take all numbers with exactly $k=[\log \log n]$ (not necessarily distinct) prime divisors. Call this set of numbers $A_n.$

Goal: We would like to remove bad terms from $A_n$ such that for the remaining subsequence $\{a_{i_s}\}$ the following holds:$$[a_{i_s},a_{i_s'}]\geq n+1,$$ whenever $i_s\neq i'_s$.Here, $[x,y]$ denotes the least common multiple of integers $x,y.$

The hope is that there aren't too many bad terms, i.e., that the remaining terms, when their reciprocals are summed, still satisfy a lower bound not much smaller than (1).

Consider $k=2$ for clarity. Note that the smallest LCM occurs if there is a common prime in the two numbers thus, $[pq,p'q']=[p'q,p'q']\geq p'qq',$ for example. If we remove $a_i$ which are divisible by primes $\leq n^{1/(k+1)}$ then our condition (1) is satisfied. Now compute the sum over bad $a_i$ that we need to subtract form the LHS of (1): $$B_2=\sum_{p\leq n^{1/3}} \frac{1}{p} \sum_{p\leq q\leq \sqrt{n/p}} \frac{1}{q}+ \sum_{p,q\leq n^{1/3}} \frac{1}{pq}\quad(2).$$ The second term in (2) is $(\log\log (n^{1/3}))^2=(\log \log n -\log 3)^2\leq (\log \log n)^2$ and is negligible compared to the RHS of (1).

The first term can be rewritten as $$\sum_{p\leq n^{1/3}} \frac{1}{p} \left[ \log\log(\sqrt{n/p})-\log\log p \right] $$ and after some manipulation becomes (if I'm right) $$ \log(\frac{1}{2}) \sum_{p\leq n^{1/3}} \frac{1}{p} +\log\log n\sum_{p\leq n^{1/3}} \frac{1}{p}-\frac{1}{\log n} \sum_{p\leq n^{1/3}} \frac{\log p}{p} - \sum_{p\leq n^{1/3}} \frac{\log \log p}{p}. $$ which turns out to be $\ll (\log\log n)^2.$ Thus $B_2 \ll (\log\log n)^2.$

Is this analysis correct? More importantly, as $n$ increases, so does $k$ and it seems hard to extend this analysis for $B_k$. Is there a more general and powerful result that can be used to conclude that perhaps $$B_k \ll (\log\log n)^{c}$$ for some absolute constant $c$?

In any case, the main goal is for $B_k$ to be shown to be strictly smaller than the RHS of (1) for $k=[\log \log n]$


Unfortunately, you have no chance whatsoever. Indeed, assume that $A$ is a subset of $\{1,\dots,n\}$ such that $[a',a'']\ge n+1$ for all $a'\ne a''$ in $A$. Then the numbers $ab: a\in A, 1\le b\le n/a$ are all different. Hence, taking the sum of their reciprocals, we obtain something like $$ \sum_{a\in A} a^{-1}\log(n/a)\le \log n $$ Now, let $a_0=ne^{-\sqrt{\log n}}$. Then $\sum_{a\in A,a\le a_0}a^{-1}\le \sqrt{\log n}$. On the other hand, $\sum_{a_0\le a\le n}a^{-1}\le\sqrt{\log n}$ as well. Thus, the trivial upper bound for the sum of the reciprocals under the new condition becomes $2\sqrt{\log n}$ or something like that.

  • $\begingroup$ :thanks. Can you explain your bound for $\sum_{a\in A} a^{-1} \log(n/a)=\log n \sum_{a\in A} a^{-1} -\sum_{a\in A} \frac{\log a}{a}$ ? $\endgroup$ – kodlu Jan 3 '16 at 13:59
  • 1
    $\begingroup$ @kodlu It is not the difference but the ratio that matters: as long as $a\le a_0$, the extra factor $\log(n/a)$ is at least $\sqrt{\log n}$ and even if you add the inverses of all numbers between $a_0$ and $n$, you still have at most $\sqrt{\log n}$ total. $\endgroup$ – fedja Jan 3 '16 at 18:19
  • 1
    $\begingroup$ @codlu Or, if you ask where that came from, I just summed over $b$ first on the left and summed up all reciprocals of the numbers between $1$ and $n$ on the right. $\endgroup$ – fedja Jan 3 '16 at 18:21
  • $\begingroup$ thanks again. I think I understand your first comment. I also understand how you obtained the LHS of the inequality. When I look at the RHS of the inequality, the way I expanded it, it seems like for certain sets $A$ with pairwise LCM at least $n+1$ the sum of reciprocals multiplying the first term I wrote can be as large as $\log n.$ How exactly can we be sure that the upper bound is only $\log n$ and not a larger power of $\log n$? So the term I can't lower bound is the sum with terms $\log a/a$. So I am unsure how to obtain the RHS of the inequality as $\log n$. $\endgroup$ – kodlu Jan 3 '16 at 23:07
  • 1
    $\begingroup$ @kodlu What do you mean? Each number between $1$ and $n$ can be represented in only one way as $ab$. And I have never said anything about the sum $\sum_a a^{-1}\log a$. In fact, I find the whole idea to split the logarithm $\log(n/a)$ into the difference $\log n-\log a$ rather misleading... $\endgroup$ – fedja Jan 4 '16 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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