# Inclusion Exclusion and lcm

I would like to show that for any positive integers $d_1, \dots, d_r$ one has $$\sum_{i=1}^r (-1)^{i+1}\biggl( \sum_{1\leq k_1 < \dots < k_i \leq r} \gcd(d_{k_1}, \dots , d_{k_i})\biggr) ~\leq~ \prod_{i=1}^r\biggl( \prod_{1\leq k_1 < \dots < k_i \leq r} \gcd(d_{k_1}, \dots , d_{k_i}) \biggl)^{(-1)^{i+1}}.$$ Note that the rhs of the upper inequality is exactly $\operatorname{lcm}(d_1,\dots,d_r)$. Also note that if we denote the lhs of the upper equation by $L(d_1, \dots, d_r)$, then one has that $$L(d_1, \dots, d_r) = L(d_1, \dots, d_{r-2}, d_{r-1}) + L(d_1, \dots, d_{r-2}, d_{r}) - L(d_1, \dots, d_{r-2}, \text{gcd}(d_{r-1},d_r)).$$

Thanks for the help!

-
I compute {1,1,2} as a counter-example. It looks like you want strict inequality $k_1<k_2<\cdots<k_i$. In this case, however, {1,2} is a counter-example to the claim "equality only if $d_1=\cdots=d_r$" (but the inequality doesn't seem to have a small counter-example). –  Douglas S. Stones Sep 25 '12 at 8:19

For any $r\geq 1$ and any positive integers $d_1, \dots d_r\in \mathbb Z_{>0}$ define $L(d_1,\dots , d_r)$ (think logarithmic lcm) to be \begin{equation*} L(d_1,\dots , d_r) ~:=~ \sum_{i=1}^r (-1)^{i+1}\Big(\sum_{1\leq k_1 < ... < k_i\leq r} \text{gcd}(d_{k_1}, \dots, d_{k_i}) \Big). \end{equation*} It is straightforward to check that $L$ is symmetric, homogeneous of degree 1 and that
\begin{equation*} (i) ~~~~~ L(d_1,\dots , d_r) = L(d_1,\dots , d_{r-1}) + L(d_1,\dots , d_{r-2}, d_n) - L(d_1,\dots , d_{r-2}, \text{gcd}( d_{r-1},d_r)). \end{equation*} Furthermore it follows directly from symmetry and property $(i)$ that \begin{equation*} (ii) ~~~~\text{if} ~~ d_r \big \vert d_i~~ \text{for some}~ 1\leq i \leq r-1 \text{, then} ~~L(d_1,\dots , d_r) = L(d_1,\dots , d_{r-1}). \end{equation*} The third property we want to establish is that \begin{eqnarray*} (iii) ~~~L(d_1,\dots , d_r) %&=& \sum_{i=1}^r (-1)^{i+1}\Big(\sum_{1\leq k_1 < ... < k_i\leq r} \text{gcd}(d_{k_1}, \dots, d_{k_i}) \Big) %\\ &\leq& \prod_{i=1}^r \Big(\prod_{1\leq k_1 < ... < k_i\leq r} \text{gcd}(d_{k_1}, \dots, d_{k_i}) \Big)^{(-1)^{i+1}} = \text{lcm}( d_1 ,\dots d_r), \end{eqnarray*} with equality if and only if for some $1\leq i \leq r$, $L(d_1,\dots , d_r)$ can be reduced to $L(d_i)$ in the sense of property $(ii)$, i.e. $d_j \big \vert d_i$ for all $j\neq i$.
To see this let $G$ be the cyclic group of order $\text{lcm}( d_1 ,\dots, d_r)$ and pick elements $c_1, \dots, c_r\in G$ of order $d_1, \dots, d_r$ respectively. One obviously has $$\# \Big ( \bigcup_{i=1}^r ~ \langle c_i \rangle \Big )~\leq ~ \# G. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(\star)$$ Since $G$ is cyclic one has $\# \big( \langle c_{k_1} \rangle \cap \dots \cap \langle c_{k_i} \rangle \big) = \text{gcd}(d_{k_1}, \dots, d_{k_i})$. Hence by the inclusion exclusion principal the left hand side of equation ($\star$) is equal to $L(d_1,\dots, d_r)$ and the right hand side is equal to $\text{lcm}( d_1 ,\dots, d_r)$. Observe that equality holds iff one of the $c_i$ has order $\text{lcm}( d_1 ,\dots, d_r)$, which proves the claim.