<s>[INST] Lower Bound on the Sum of Reciprocal of LCM While reading online, I encountered this post which the author claims that
\begin{align}
S(N, 1):=\sum_{1\le i, j \le N} \frac{1}{\text{lcm}(i, j)} \geq 3H_N-2
\end{align}
and $S(N, 1) \geq H_N^2$ where $H_N$ is the partial harmonic sum. 
The prove of the latter inequality is already given in the post. For the former, we see that
\begin{align}
S(N, 1) 
=&\ 2\sum^N_{j=2}\sum^{j-1}_{i=1}\frac{1}{\text{lcm}(i, j)} +H_N\\
\geq&\ 2\sum^N_{j=2} \frac{1}{\text{lcm}(1, j)}+H_N=\ 3H_N -2.
\end{align}
My question is whether there exists $C$, independent of $N$, such that the following bound holds
\begin{align}
s(N):=\sum_{N \leq i, j \leq 2N} \frac{1}{\text{lcm}(i, j)} \geq C \log N.
\end{align}
Actually, I know for a fact that this is true by $(1.7)$ in this paper but couldn't prove it. 
Another question: How does one show
\begin{align}
\sum_{N^2/4< k< N^2/3} (\#\left\{N/3<q<N/2 \big|\   q\mid k\right\})^2\sim  \sum_{N/3<q, q'<N/2} \frac{N^2}{\text{lcm}(q,q')}.
\end{align}
 I started by
\begin{align}
\sum_{N^2/4< k< N^2/3} (\#\left\{N/3<q<N/2 \big|\   q\mid k\right\})^2 =&\ \sum_{N^2/4< k< N^2/3}\left( \sum_{\substack{N/3<q<N/2\\ q\mid k}}1  \right)^2\\
=&\ \sum_{N^2/4< k< N^2/3} \sum_{\substack{N/3<q,\ q'<N/2\\ q\mid k,\ q'\mid k}} 1.
\end{align}
Here I know I should interchange the order of summation, but I don't know how to get the lcm to show up. 
Any help/suggestion is highly welcome. 
 [/INST] Sketch proof for 1: assume that there is $c>0$ absolute constant s.t for each $1 \leq a \leq N^{\frac{1}{4}}$ ($N$ high enough), there are at least $c\frac{N^2}{a^2}$ pairs $N \leq k,l \leq 2N$ with $gcd(k,l)=a$; then as $lcm(k,l)gcd(k,l)=kl$, 
$s(N):=\sum_{N \leq k, l \leq 2N} \frac{1}{\text{lcm}(k, l)} =\sum_{N \leq k, l \leq 2N} \frac{gcd(k,l)}{kl} \geq \frac{1}{4N^2}\sum_{N \leq k, l \leq 2N}gcd(k,l) \geq \frac{1}{4N^2}\sum_{1 \leq a \leq N^{\frac{1}{4}}}a(c\frac{N^2}{a^2}) \geq \frac{c}{16}\log N $
Let now $1 \leq a \leq N^{\frac{1}{4}}$, considering the first number $N \leq k(a) < N+a$ which is divisble by $a$, it follows that $k(a)+qa$ is divisble by $a$ and within our range as long as $(q+1)a \leq N$, so there are at least $[\frac{N}{a}-1]$ such, so at least $[\frac{N}{a}-1]^2$ pairs with gcd divisible by $a$; same reasoning give at most $[\frac{N}{a}+1]^2$ such pairs, so applying this with $2a,3a...2Na$ (since the gcd is at most $2N$ in our interval) we get that the number of pairs with gcd precisely $a$ is at least: $\begin{align}\frac{N^2}{a^2}(1-\frac{1}{4}-\frac{1}{9}-.. )- 2N(\log 2N+1) \geq \frac{N^2}{a^2}(1-(\frac{\pi^2}{6}-1))-2N(\log 2N+1) \end{align}$ $\geq \frac{N^2}{6a^2}-2N(\log 2N+1)$, and that is $ \geq \frac{N^2}{12a^2}$ for say $N \geq 40000$ since $a \leq N^{\frac{1}{4}}, \frac{N^2}{12a^2} \geq \frac{N^2}{12\sqrt N} \geq 2N(\log 2N+1)$, for $N$ large as noted so we are done.
For the second claim, note that switching the sum, each ${N^2/4< k< N^2/3}$ appears for a pair $(q,q')$ precisely when it is a multiple of the lcm of the pair and it is fairly clear that for any $m \geq 1$ in a ~$N^2$ interval there are ~$\frac{N^2}{m}$ multiples of it, so the claim follows
Edit: as requested a more detailed explanation of the estimate above for the number of pairs with gcd $a$:
because the number of multiples of $a$ between $N, 2N$ is between $\frac{N}{a}-1, \frac{N}{a}+1$, this means that we have at least $(\frac{N}{a}-1)^2=\frac{N^2}{a^2}-2\frac{N}{a}+1$ pairs with gcd a multiple of $a$, but if the gcd is not $a$, it means it is $2a, 3a,...2Na$ (this last is very crude and we can do much better but we do not need), but for $2a$ we have at most $(\frac{N}{2a}+1)^2=\frac{N^2}{4a^2}+2\frac{N}{2a}+1$ pairs with gcd that (actually less since some will have gcd $4a$ etc but we again use a rough estimate as that is enough); putting things together we get by subtracting all those cases with gcd $2a,3a...2Na$, the main term is $\frac{N^2}{a^2}(1-\frac{1}{4}-\frac{1}{9}-.. )$ which we estimate by $\frac{N^2}{6a^2}$ with a simple computation; the remainder is $(-2\frac{N}{a}+1)+(-2\frac{N}{2a}-1)+(-2\frac{N}{3a}-1)+...$ (at most $2N$ terms) and that clearly estimates by $-2N\log 2N - 2N$, so we get the estimate above and use that $a \leq N^{\frac{1}{4}}$ to conclude as noted for large enough $N$ since obviously $\frac{N^2}{12a^2} \geq \frac{N^2}{12\sqrt N}$ will dominate $2N\log 2N + 2N$, allowing us to keep another $\frac{N^2}{12a^2}$ from the main term
</s>