0

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

Community
  • 1
kodlu
  • 10,131
  • 2
  • 34
  • 53

1 Answers1

4

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.

fedja
  • 59,730
  • :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}$ ? – kodlu Jan 03 '16 at 13:59
  • 1
    @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. – fedja Jan 03 '16 at 18:19
  • 1
    @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. – fedja Jan 03 '16 at 18:21
  • 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$. – kodlu Jan 03 '16 at 23:07
  • 1
    @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... – fedja Jan 04 '16 at 01:19
  • now I see, thanks, it was very straightforward... – kodlu Jan 04 '16 at 01:32
  • please see a proposed answer strategy in http://mathoverflow.net/questions/227754/maximizing-sum-of-reciprocals-of-the-elements-of-a-subset-of-1-2-n-subject if you're interested. – kodlu Jan 18 '16 at 08:39