# Maximizing sum of reciprocals of the elements of a subset of {1,2,..,n} subject to LCM(a,a')>n

In an answer to a previous MO question here, MO user @fedja showed (by way of an upper bound) that if $A\subseteq \{1,\ldots,n\}$ has the property $LCM(a,a')\geq n+1$ for all $a\neq a' \in A$ then the biggest lower bound one can hope for is something like $$\sum_{a \in A} \frac{1}{a} \gg \sqrt{\log n}.$$ I am wondering if a lower bound approaching this can be proved. Based on the linked question and also this question where a set $\{a_i\}$ of primitive sequences ($1<a_1<\cdots<a_m<n$) none of whose terms divide another) are constructed attaining the bound $$\sum_{a_i} \frac{1}{a_i} \geq c \frac{\log n}{\sqrt{\log\log n}},$$ this may not be hopeless. Any positive constant power $0<\delta\leq \frac{1}{2}$ of $\log n$ would do the job.

The set of primitive sequences formed by taking all $k-$wise prime products in $\{1,\ldots,n\}$ for $k=[\log \log n]$ is quite substantial, and its intersection with the set of numbers satisfying the LCM condition may not be so sparse.

Any comments appreciated. The question here offers some more discussion in this general area, and links to other questions.

Possible strategy: I propose the following answer strategy (unrelated to primitive sequences) to obtain a lower bound. I would appreciate any comments, including proving this approach wrong.

Let $\varepsilon>0$ be small. Clearly $$\sum_{n^{1-\varepsilon}< a \leq n}\frac{1}{a} \asymp \varepsilon \log n$$ holds. Now consider $a\neq a' \in (n^{1-\varepsilon},n] \cap \mathbb{Z}\stackrel {\triangle}{=} A(n,\varepsilon).$ We want to satisfy $$lcm(a,a')=\frac{aa'}{gcd(a,a')}\geq \frac{n^{2(1-\varepsilon)}}{gcd(a,a')} >n, \quad \mathrm{or} \quad gcd(a,a')<n^{1-2\varepsilon}.$$ To this end, we now remove multiples of small primes from the set $A(n,\varepsilon).$ Since the original cardinality of this set is $n-n^{1-\varepsilon}$, using Mertens' second theorem to approximate the Euler product tells us that after the process of removing these primes we now have a set $B(n,\varepsilon)\subset A(n,\varepsilon)$ with $$\#B(n,\varepsilon) = n(1-n^{-\varepsilon}) \prod_{p\leq n^{1-2\varepsilon}}\left(1-\frac{1}{p}\right)\asymp n(1-n^{-\varepsilon})\frac{e^{-\gamma}+o(1)}{(1-2\varepsilon)\log n}.$$ Now, for any $\epsilon'>0,$ we can make $n$ large enough to make $n^{-\varepsilon}<\epsilon'$ This should mean that $$\#B(n,\varepsilon)\gg \frac{n}{\log n}.$$ Question: Can't this be used to obtain (since the remaining set is well distributed in some sense) $$\sum_{a \in B(n,\varepsilon)} \frac{1}{a} \gg \log \log n?$$

• @Gerry Myerson: it should be "lower bound", fixed, thanks. – kodlu Jan 18 '16 at 18:07