Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.