Any least common multiple is larger than n, then the sum of inverse is bounded

Given $k$ integers $a_1,a_2,\cdots,a_k$ satisfying: $1<a_1<a_2<\cdots<a_k\leq n$ and for any $i\neq j$, we have $\mathrm{lcm}(a_i,a_j)>n$. We want to show that $\sum\limits_{i=1}^{k} 1/a_i<3/2$.

The first idea is to show that $a_1>2k/3$. However, we have a counterexmple: $a_1=2,a_2=3,a_3=5,k=3,n=5$ and $a_1=2k/3$.

Then I write $a_i=2^{m_i}q_i$, where $m_i$ is a nonnegative integer and $q_i$ is a positive odd number. So $\mathrm{lcm}(a_i,a_j)>n,\forall i\neq j$ implies that $q_i\neq q_j,\forall i\neq j$. I don't know how to proceed the proof.

Solution 1:

Note the initial part of this answer is based on Ghartal's answer to a similar problem. First, for each $1 \leq i \leq k$, the number of positive integral multiples of $a_i$ not larger than $n$ is $\left\lfloor \frac{n}{a_i} \right\rfloor$. Next, if any $a_i$ were an integral multiple of an $a_j$ for some $i \neq j$, then $\operatorname{lcm}(a_i, a_j) = a_i \le n$, which contradicts $\operatorname{lcm}(a_i, a_j) \gt n$. Thus, each of the $\left\lfloor \frac{n}{a_i} \right\rfloor$ multiples of $a_i$ form a disjoint subset of the $n - 1$ integers from $2$ to $n$. Since the sum of the number of elements of disjoint subsets can at most be the number of elements of the set itself, therefore

$$\sum_{i=1}^{k} \left\lfloor \frac{n}{a_i} \right\rfloor \le n - 1 \tag{1}\label{eq1A}$$

For all real $x$, with $\{ x \}$ denoting the fractional part of $x$, since $\{ x \} \lt 1$, we also have

$$\sum_{i=1}^{k} \left\{ \frac{n}{a_i} \right\} \lt k \tag{2}\label{eq2A}$$

Next, using the technique from your last paragraph (which is also used in other posts like Prove that if 51 positive integers between 1 and 100 are chosen, then one of them must divide another.), write $a_i = 2^{m_i}q_i$ where $q_i$ is odd. Since there are $\left\lceil \frac{n}{2} \right\rceil$ possible values for $q_i$, if $k \gt \left\lceil \frac{n}{2} \right\rceil$, then the Pigeonhole principle states there must be an $i \neq j$ where $q_i = q_j$. However, if $m_i \lt m_j$ then $a_i \mid a_j$, else $a_j \mid a_i$. Since neither is allowed, we therefore have

$$k \le \left\lceil \frac{n}{2} \right\rceil \lt \frac{n}{2} + 1 \tag{3}\label{eq3A}$$

Adding \eqref{eq1A} and \eqref{eq2A}, along with using \eqref{eq3A} and that $\lfloor x \rfloor + \{ x \} = x$ for all real $x$, gives

$$\begin{equation}\begin{aligned} \sum_{i=1}^{k}\left(\left\lfloor \frac{n}{a_i} \right\rfloor + \left\{ \frac{n}{a_i} \right\}\right) & \lt (n - 1) + \left(\frac{n}{2} + 1\right) \\ \sum_{i=1}^k\frac{n}{a_i} & \lt n + \frac{n}{2} \\ n\left(\sum_{i=1}^k\frac{1}{a_i}\right) & \lt \frac{3n}{2} \\ \sum_{i=1}^k\frac{1}{a_i} & \lt \frac{3}{2} \end{aligned}\end{equation}\tag{4}\label{eq4A}$$