4
$\begingroup$

Let's fix a positive integer $n$ and consider two positive composites $a,b \le n$. We can consider the prime factorizations $a=2^{a_2}3^{a_3}\cdots p^{a_p}$ and $b=2^{b_2}3^{b_3}\cdots p^{b_p}$, where $p$ is the largest prime $\le n.$

I am trying to sum $\displaystyle\sum\frac{1}{i}$, over positive integers $i$ such that:

  1. $i$ consists of no prime factor larger than $n$ (but $i$ may be larger than $n$); that is, $i$ is of the form $i=2^{i_2}\cdots p^{i_p}$.
  2. The $i_k$'s must satisfy both of the following conditions: $$(a_2-i_2)1_{\lbrace a_2-i_2>0\rbrace}+\cdots+(a_p-i_p)1_{\lbrace a_p-i_p>0\rbrace}\ge 2,\\(b_2-i_2)1_{\lbrace b_2-i_2>0\rbrace}+\cdots+(b_p-i_p)1_{\lbrace b_p-i_p>0\rbrace}\ge 2.$$ ($1_{\lbrace>0\rbrace}$ is a characteristic function which is $1$ when the difference is positive, $0$ otherwise.)

Is it possible to determine which $i$'s satisfy (i) and (ii)? If not, is there any chance of finding naive bounds for $\displaystyle\sum\frac{1}{i}$ over such $i$?

$\endgroup$
  • $\begingroup$ What type of expression are you looking to get? You can just list all possible $p$-tuples satisfying condition (ii) and write the result as a sum over these, giving an expression in terms of the $a_i$ and $b_i$ by writing all possible combinations. Each sum appearing in this expression can be calculated as it is a geometric series. From there, you can bound each term as you please. $\endgroup$ – hrt May 28 '18 at 7:20
  • $\begingroup$ For a particular $a$ and $b$, I can do this. But I am wondering if there's an expression that will work for any $a$ and $b$ rather than having to consider so many cases. $\endgroup$ – The Substitute May 28 '18 at 7:23
  • $\begingroup$ Well the sum over all $p$-tuples is the exact expression, I doubt that you would be able to simplify it much and keep an exact result. Now, if you are willing to estimate you could obtain upper and lower bounds that are much simpler probably. $\endgroup$ – hrt May 28 '18 at 7:33
  • $\begingroup$ The sum that satisfies $(i)$ equals to $\prod_{p < n, p \text{prime}}\frac{p}{p - 1}$, so it is a trivial bound when both $(i)$ and $(ii)$ are satisfied. $\endgroup$ – achille hui May 30 '18 at 7:53
  • $\begingroup$ What is the motivation for looking at this sum? Curious as to where this problem originated from. $\endgroup$ – none Jun 6 '18 at 3:00
2
+50
$\begingroup$

$\def\peq{\mathrel{\phantom{=}}{}}$Suppose $p_1 < \cdots < p_s$ are all prime numbers no greater than $n$ and$$ a = \prod_{k = 1}^s p_k^{a_k}, \quad b = \prod_{k = 1}^s p_k^{b_k}. $$ Define\begin{align*} A_0 &= \{(j_1, \cdots,j_s) \in \mathbb{N}^s \mid j_k \geqslant a_k\ (\forall 1 \leqslant k \leqslant s)\},\\ A_1 &= \{(j_1, \cdots,j_s) \in \mathbb{N}^s \mid \exists 1 \leqslant k_0 \leqslant s,\ j_{k_0} = a_{k_0} - 1,\ j_k \geqslant a_k\ (\forall k ≠ k_0)\},\\ B_0 &= \{(j_1, \cdots,j_s) \in \mathbb{N}^s \mid j_k \geqslant b_k\ (\forall 1 \leqslant k \leqslant s)\},\\ B_1 &= \{(j_1, \cdots,j_s) \in \mathbb{N}^s \mid \exists 1 \leqslant k_0 \leqslant s,\ j_{k_0} = b_{k_0} - 1,\ j_k \geqslant b_k\ (\forall k ≠ k_0)\}, \end{align*} and $A = \mathbb{N}^s \setminus (A_0 \cup A_1)$, $B = \mathbb{N}^s \setminus (B_0 \cup B_1)$. For $j = (j_1, \cdots, j_s) \in \mathbb{N}^s$, define $\displaystyle p^j = \prod_{k = 1}^s p_k^{j_k}$, then the sum to be found is\begin{align*} \sum_{j \in A \cap B} \frac{1}{p^j} &= \sum_{j \in \mathbb{N}^s} \frac{1}{p^j} - \sum_{j \in A^c \cup B^c} \frac{1}{p^j} = \prod_{k = 1}^s \frac{p_k}{p_k - 1} - \sum_{j \in A^c \cup B^c} \frac{1}{p^j}. \end{align*}

Note that $A^c = A_0 \cup A_1$, $B^c = B_0 \cup B_1$, $A_0 \cap A_1 = \varnothing$, $B_0 \cap B_1 = \varnothing$, thus\begin{align*} \sum_{j \in A^c \cup B^c} \frac{1}{p^j} &= \sum_{j \in A^c} \frac{1}{p^j} + \sum_{j \in B^c} \frac{1}{p^j} - \sum_{j \in A^c \cap B^c} \frac{1}{p^j}\\ &= \sum_{j \in A_0} \frac{1}{p^j} + \sum_{j \in A_1} \frac{1}{p^j} + \sum_{j \in B_0} \frac{1}{p^j} + \sum_{j \in B_1} \frac{1}{p^j} - \sum_{j \in A^c \cap B^c} \frac{1}{p^j}. \end{align*} For the first four sums,$$ \sum_{j \in A_0} \frac{1}{p^j} = \prod_{k = 1}^s \sum_{m = a_k}^∞ \frac{1}{p_k^m} = \prod_{k = 1}^s \frac{1}{(p_k - 1) p_k^{a_k - 1}} = \frac{1}{a} \prod_{k = 1}^s \frac{p_k}{p_k - 1}, $$\begin{align*} \sum_{j \in A_1} \frac{1}{p^j} &= \sum_{a_k \geqslant 1} \frac{1}{p_k^{a_k - 1}} \prod_{l ≠ k} \sum_{m = a_l}^∞ \frac{1}{p_l^m} = \sum_{a_k \geqslant 1} \frac{1}{p_k^{a_k - 1}} \prod_{l ≠ k} \frac{1}{(p_l - 1) p_l^{a_l - 1}}\\ &= \sum_{a_k \geqslant 1} (p_k - 1) \prod_{l = 1}^s \frac{1}{(p_l - 1) p_l^{a_l - 1}} = \frac{1}{a} \left( \sum_{a_k \geqslant 1} (p_k - 1) \right) \left( \prod_{k = 1}^s \frac{p_k}{p_k - 1} \right), \end{align*} and analogously,$$ \sum_{j \in B_0} \frac{1}{p^j} = \frac{1}{b} \prod_{k = 1}^s \frac{p_k}{p_k - 1},\quad \sum_{j \in B_1} \frac{1}{p^j} = \frac{1}{b} \left( \sum_{b_k \geqslant 1} (p_k - 1) \right) \left( \prod_{k = 1}^s \frac{p_k}{p_k - 1} \right). $$

Next, note that$$ \sum_{j \in A^c \cap B^c} \frac{1}{p^j} = \sum_{j \in A_0 \cap B_0} \frac{1}{p^j} + \sum_{j \in A_1 \cap B_0} \frac{1}{p^j} + \sum_{j \in A_0 \cap B_1} \frac{1}{p^j} + \sum_{j \in A_1 \cap B_1} \frac{1}{p^j}. $$ Define $c_k = \max(a_k, b_k)$ for $1 \leqslant k \leqslant s$, then$$ \sum_{j \in A_0 \cap B_0} \frac{1}{p^j} = \prod_{k = 1}^s \sum_{m = c_k}^∞ \frac{1}{p_k^m} = \prod_{k = 1}^s \frac{1}{(p_k - 1) p_k^{c_k - 1}} - \frac{1}{[a, b]} \prod_{k = 1}^s \frac{p_k}{p_k - 1}, $$\begin{align*} \sum_{j \in A_1 \cap B_0} \frac{1}{p^j} &= \sum_{a_k - b_k \geqslant 1} \frac{1}{p_k^{a_k - 1}} \prod_{l ≠ k} \sum_{m = c_l}^∞ \frac{1}{p_l^m} = \sum_{a_k - b_k \geqslant 1} \frac{1}{p_k^{a_k - 1}} \prod_{l ≠ k} \frac{1}{(p_l - 1) p_l^{c_l - 1}}\\ &= \left( \sum_{a_k - b_k \geqslant 1} (p_k - 1) p_k^{c_k - a_k} \right) \left( \prod_{k = 1}^s \frac{1}{(p_k - 1) p_k^{c_k - 1}} \right)\\ &= \frac{1}{[a, b]} \left( \sum_{a_k - b_k \geqslant 1} (p_k - 1) p_k^{c_k - a_k} \right) \left( \prod_{k = 1}^s \frac{p_k}{p_k - 1} \right)\\ &= \frac{1}{[a, b]} \left( \sum_{a_k - b_k \geqslant 1} (p_k - 1) \right) \left( \prod_{k = 1}^s \frac{p_k}{p_k - 1} \right), \end{align*} $$ \sum_{j \in A_0 \cap B_1} \frac{1}{p^j} = \frac{1}{[a, b]} \left( \sum_{b_k - a_k \geqslant 1} (p_k - 1) \right) \left( \prod_{k = 1}^s \frac{p_k}{p_k - 1} \right). $$ Since there exists no $k$ such that $a_k - b_k \geqslant 1$ and $b_k - a_k \geqslant 1$, then\begin{align*} \sum_{j \in A_1 \cap B_1} \frac{1}{p^j} &= \sum_{\substack{a_{k_1} - b_{k_1} \geqslant 1\\b_{k_2} - a_{k_2} \geqslant 1}} \frac{1}{p_{k_1}^{a_{k_1} - 1} p_{k_2}^{b_{k_2} - 1}} \prod_{l ≠ k_1, k_2} \sum_{m = c_l}^∞ \frac{1}{p_l^m}\\ &= \sum_{\substack{a_{k_1} - b_{k_1} \geqslant 1\\b_{k_2} - a_{k_2} \geqslant 1}} \frac{1}{p_{k_1}^{a_{k_1} - 1} p_{k_2}^{b_{k_2} - 1}} \prod_{l ≠ k_1, k_2} \frac{1}{(p_l - 1) p_l^{c_l - 1}}\\ &= \Biggl( \sum_{\substack{a_{k_1} - b_{k_1} \geqslant 1\\b_{k_2} - a_{k_2} \geqslant 1}} (p_{k_1} - 1)(p_{k_2} - 1) p_{k_1}^{c_{k_1} - a_{k_1}} p_{k_2}^{c_{k_2} - b_{k_2}} \Biggr) \left( \prod_{k = 1}^s \frac{1}{(p_k - 1) p_k^{c_k - 1}} \right)\\ &= \frac{1}{[a, b]} \Biggl( \sum_{\substack{a_{k_1} - b_{k_1} \geqslant 1\\b_{k_2} - a_{k_2} \geqslant 1}} (p_{k_1} - 1)(p_{k_2} - 1) \Biggr) \left( \prod_{k = 1}^s \frac{p_k}{p_k - 1} \right)\\ &= \frac{1}{[a, b]} \left( \sum_{a_k - b_k \geqslant 1} (p_k - 1) \right) \left( \sum_{b_k - a_k \geqslant 1} (p_k - 1) \right) \left( \prod_{k = 1}^s \frac{p_k}{p_k - 1} \right). \end{align*} Therefore, after combining terms,\begin{align*} \sum_{j \in A \cap B} \frac{1}{p^j} &= \prod_{k = 1}^s \frac{p_k}{p_k - 1}\\ &\peq -\left( \frac{1}{a} \left( \sum_{a_k \geqslant 1} (p_k - 1) + 1 \right) + \frac{1}{b} \left( \sum_{b_k \geqslant 1} (p_k - 1) + 1 \right) \right) \left( \prod_{k = 1}^s \frac{p_k}{p_k - 1} \right)\\ &\peq + \frac{1}{[a, b]} \left( \sum_{a_k - b_k \geqslant 1} (p_k - 1) + 1 \right) \left( \sum_{b_k - a_k \geqslant 1} (p_k - 1) + 1 \right) \left( \prod_{k = 1}^s \frac{p_k}{p_k - 1} \right). \end{align*}

$\endgroup$
  • $\begingroup$ Thank you. By $[a,b]$, do you mean the lcm? $\endgroup$ – The Substitute May 31 '18 at 6:06
  • $\begingroup$ @TheSubstitute Yes. $\endgroup$ – Saad May 31 '18 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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