12
$\begingroup$

Let $\mu$ denote the Möbius function whereby $$\mu(k) = \begin{cases} 0 & \text{if $k$ has one or more repeated prime factors} \\ 1 & \text{if $k=1$} \\ (-1)^j & \text{if $k$ is a product of $j$ distinct primes}\end{cases}$$ for all $k \in \mathbb{N}$. I have previously noted a surprising connection between products of the form $$\prod_{k=1}^{n} k^{\mu(k)}$$ and harmonic numbers (see http://oeis.org/A130087). Letting $H_{n} = 1 + \frac{1}{2} + \cdots + \frac{1}{n}$ denote the $n^{\text{th}}$ harmonic number, I noted that the denominator (in lowest terms) of this product is equal to the denominator (in lowest terms) of $H_{n}^{2}n!$ for all $n < 897$. For example, letting $n = 11$, we have that $$1^{\mu(1)} \cdot 2^{\mu(2)} \cdot \cdots \cdot 11^{\mu(11)} = \frac{2}{77},$$ and $$H_{11}^{2}11! = \frac{28030126084}{77}.$$ This property does not hold for all $n \in \mathbb{N}$, and the first counterexample occurs in the case whereby $n = 897$. Letting $\text{den}(q)$ denote the denominator in lowest terms of $q \in \mathbb{Q}_{> 0}$, it is not obvious to me why the equality $$\text{den}\left(\prod_{k=1}^{n} k^{\mu(k)}\right) = \text{den}\left(H_{n}^{2}n!\right)$$ holds for the first several hundred natural numbers. So it seems natural to me to ask:

(1) Is there some simple number-theoretic explanation as to 'why' this equality holds for the first several hundred natural numbers?

(2) Is there some simple number-theoretic interpretation as to 'why' this equality does not hold in general (which specifically explains the counterexample in the case whereby $n = 897)$?

(3) Is there a natural combinatorial way of approaching this problem? Note that integers of the form $H_{n}n!$ are unsigned Stirling numbers of first kind, so it is plausible that there is a natural combinatorial interpretation of the expression $\text{den}\left(H_{n}^{2}n!\right)$.

$\endgroup$
2
  • 1
    $\begingroup$ Very interesting observation! $\endgroup$ Mar 18 '16 at 17:14
  • 1
    $\begingroup$ @John See the edit :) $\endgroup$ Mar 21 '16 at 10:01
6
+100
$\begingroup$

Let $k_p(n)$ be defined as the non-negative integer such that $p^{k_p(n)}≤n$ but $p^{k_p(n)+1}>n$. Furthermore let $\epsilon_p(n)$ be the exponent of $p$ in the prime factorisation of $n!$; it is well known that $\epsilon_p(n)=\sum_{k=1}^{\infty}\lfloor\frac{n}{p^k}\rfloor$. Define $\mathcal{P}_n:=\{p \text{ prime } : \frac{n}{2}<p≤n\}$.

We are going to show: $$ \bbox[border:2px solid red] { \text{den}\left(\left(H_n\right)^2\cdot n!\right)=\prod_{p\in\mathcal{P}_n}p } $$ For $n≥6$.

Firstly, we note that $$ (H_n)^2n!=\\ \frac{n!}{(\text{lcm}1,...,n)^2}\left(\sum_{k=1}^{n}\frac{\text{lcm}(1,...,n)}{k}\right)^2 $$ So lets calculate: $$ \frac{\text{lcm}(1,...,n)^2}{\text{gcd}\left(\text{lcm}(1,...,n)^2, n!\right)} $$ With the notation introduced above, we obtain $\text{lcm}(1,...,n)=\prod_{p\text{ prime}}p^{k_p(n)}$ and $n!=\prod_{p\text{ prime}}p^{\epsilon_p(n)}$ and thus: $$ \text{gcd}\left(\text{lcm}(1,...,n)^2, n!\right)=\prod_{p\text{ prime}}p^{\min\left(2 k_p(n)\ ,\ \epsilon_p(n)\right)} $$ Furthermore $\epsilon_p(n)=\sum_{k=1}^{k_p(n)}\lfloor\frac{n}{p^k}\rfloor$. We distinguish the following cases:

case 1: $\lfloor\frac{n}{p^{k_p(n)}}\rfloor≥2$ $$ \epsilon_p(n)=\sum_{k=1}^{k_p(n)}\lfloor\frac{n}{p^k}\rfloor≥\sum_{k=1}^{k_p(n)}2=2k_p(n) $$

case 2: $\lfloor\frac{n}{p^{k_p(n)}}\rfloor=1$ and $k_p(n)≥3$ $$ \epsilon_p(n)=\sum_{k=1}^{k_p(n)}\lfloor\frac{n}{p^k}\rfloor≥\sum_{k=1}^{k_p(n)}\lfloor\frac{p^{k_p(n)}}{p^k}\rfloor=\sum_{k=0}^{k_p(n)-1}p^k\overset{AM-GM}{≥}k_p(n)\left[\prod_{k=0}^{k_p(n)-1}p^k\right]^{\frac{1}{k_p(n)}}=k_p(n)\cdot p^{\frac{k_p(n)-1}{2}}≥2k_p(n) $$

case 3: $\lfloor\frac{n}{p^{k_p(n)}}\rfloor=1$ and $k_p(n)=2$ $$ \epsilon_p(n)=\lfloor\frac{n}{p}\rfloor+1 $$ Since $\lfloor\frac{n}{p^2}\rfloor=1$ we have $p^2≤n<2p^2$. Thus, if $p≥3$ we have $\frac{n}{p}≥p≥3\implies \lfloor\frac{n}{p}\rfloor≥3\implies \epsilon_p(n)≥4=2k_p(n)$ and if $p=2$, we simply calculate the cases where $n<8$; we see that the formula holds whenever $n\neq4$ and $n\neq5$.

case 4: $\lfloor\frac{n}{p^{k_p(n)}}\rfloor=1$ and $k_p(n)=1$ $$ \epsilon_p(n)=\lfloor\frac{n}{p}\rfloor=1<2=2k_p(n) $$ Here we have the only case where $\epsilon_p(n)<2k_p(n)$; so this inequality is true iff $p≤n<2p \iff p\in\mathcal{P}_n$

If we combine the four cases, we see that: $$ \text{gcd}\left(\text{lcm}(1,...,n)^2, n!\right)=\prod_{p\text{ prime}}p^{\min\left(2 k_p(n)\ ,\ \epsilon_p(n)\right)}=\left(\prod_{p\notin\mathcal{P}_n\ ,\ p\text{ prime}}p^{2k_p(n)}\right)\cdot\left(\prod_{p\in\mathcal{P}_n}p\right) $$ And thus: $$ \text{den}\left(\frac{n!}{\text{lcm}(1,...,n)^2}\right)=\frac{\text{lcm}(1,...,n)^2}{\text{gcd}\left(\text{lcm}(1,...,n)^2, n!\right)}=\frac{\prod_{p\text{ prime}}p^{2k_p(n)}}{\left(\prod_{p\notin\mathcal{P}_n\ ,\ p\text{ prime}}p^{2k_p(n)}\right)\cdot\left(\prod_{p\in\mathcal{P}_n}p\right)}=\frac{\left(\prod_{p\in\mathcal{P}_n}p^2\right)}{\left(\prod_{p\in\mathcal{P}_n}p\right)}=\prod_{p\in\mathcal{P}_n}p $$ Furthermore, we see that for $p\in\mathcal{P}_n$ the only summand in $\sum_{k=1}^n\frac{\text{lcm}(1,...,n)}{k}$ which isn't divisible by $p$ is the one with $p$ in the denominator i.e. $\frac{\text{lcm}(1,...,n)}{p}$ so the sum isn't divisible by $p$. Therefore we obtain: $$ \text{den}\left((H_n)^2n!\right)=\text{den}\left(\frac{n!}{\text{lcm}(1,...,n)^2}\right)=\prod_{p\in\mathcal{P}_n}p $$ Whenever $n\neq4,5$.

This isn't an inherently combinatorial identity, as you wished, but it breaks it down quite a bit. However, I fail to see how to justify your observations with this identity, but it sheds new light on what we really have to prove:

If $p\in\mathcal{P}_n$ then the prime $p$ appears only once in the factors of the numbers $\{1,...,n\}$. As $\mu(p)=-1$ it appears in the denominator of $\prod_{k=1}^{n}k^{\mu(k)}$. As it can't be cancelled out, we can see that $$\prod_{p\in\mathcal{P}_n}p\ |\ \text{den}\left(\prod_{k=1}^{n}k^{\mu(k)}\right)$$ In order to have equality, we would need to have that every prime not in $\mathcal{P}_n$ appears more ore equally often in the numerator than in the denominator. For $n=897$ this fails for $p=23$; it appears one time more often in the denominator than in the numerator and we then have $$\prod_{p\in\mathcal{P}_{897}}p=23\cdot\text{den}\left(\prod_{k=1}^{897}k^{\mu(k)}\right)$$ I doubt that I will come up with an explanation and characterization for the cases of equality, but I will continue to work on it.

Edit: Some further results:

We're going to find an expression for $h_p(n)$, the exponent of $p$ in the denominator of $\prod_{k=1}^n k^{\mu(k)}$ in lowest terms (negative if it's in the numerator and $0$ if it is cancelled out). We have: $$ h_p(n)=\sum_{k\leq n\ ,\ p|k}-\mu(k)=\sum_{k\leq \frac{n}{p}}-\mu(pk)=\sum_{k\leq \frac{n}{p}}\mu(k)+\sum_{k\leq \frac{n}{p}\ ,\ p|k}-\mu(k)=M\left(\frac{n}{p}\right)+h_p\left(\lfloor\frac{n}{p}\rfloor\right) $$ Where $M$ is the Mertens function defined to be $M(x):=\sum_{1\leq k\leq x}\mu(k)$. So inductively we obtain: $$ h_p(n)=\sum_{k=1}^{\infty}M\left(\frac{n}{p^k}\right) $$ In a nice analogy to $\epsilon_p(n)$. This gives us a family of counter examples to your observation:

Let $m\geq 6$ (our formula for the harmonic denominator needs to be true) be such that $M(m)\geq 0$ (I think there are infinitely many such $m$) and let $p\in\mathcal{P}_m$, which exists due to Bertrand's postulate. Let $n=pm+r$ such that $0\leq r <p$. So we verify that $\lfloor\frac{n}{p}\rfloor=m$ and $\lfloor\frac{n}{p^2}\rfloor=1$ (because $r<p\leq p(2p-m)\implies \frac{n}{p^2}=\frac{mp+r}{p^2}<2$) and therefore: $$ h_p(n)=M(m)+M(1)\geq M(1)=1 $$ But $2p\leq p^2\leq pm\leq n$ an thus $p\notin \mathcal{P}_n$ and we obtain that $$ \prod_{p\in\mathcal{P}_{n}}p<\text{den}\left(\prod_{k=1}^{n}k^{\mu(k)}\right) $$ So $n$ is a counter example. This also suggests $n=897$ to be the first one: the smallest $m>5$ with $M(m)\geq 0$ is $m=39$ and the smallest prime of $\mathcal{P}_{39}$ is $23$. With $r=0$ we obtain $n=897$ and from there on we find many counter examples.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer! Please note that it is not in general true that $\text{den}(H_{n}) = \text{lcm}(1, 2, \ldots, n)$. For example, $\text{den}(H_{25}) = 8923714800$, but $\text{lcm}(1, 2, \ldots, 25) = 26771144400$. However, it does appear to be true that $\text{den}\left(H_{n}^{2} \cdot n!\right)$ is equal to $\frac{\text{lcm}^{2}(1, 2, \ldots, n)}{\text{gcd}(\text{lcm}^{2}(1, 2, \ldots, n), n!)}$ for $n \in \mathbb{N}$, although it is not obvious to me how to prove this. $\endgroup$ Apr 3 '16 at 18:43
  • $\begingroup$ @John M. Campbell: you're totally right, I fixed it now. I got a bit tempted by simple cases... :) $\endgroup$ Apr 4 '16 at 11:10

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.