# 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!

-

Your formula is not clear: on which index is summed the first sum? why there are $k_i,\ldots,k_i$ as indexes in the second sum, but you use $k_i,\ldots,k_r$ inside the argument of the sum? what does it means $1=1,\ldots,r$? – enzotib Sep 23 '12 at 16:56
Thank you @enzotib, I have corrected it. – florek Sep 23 '12 at 19:02
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

## 1 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 30, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8655306696891785, "perplexity_flag": "middle"}