Prove that for any positive integers $k$ and $N$, \[\left(\frac{1}{N}\sum\limits_{n=1}^{N}(\omega (n))^k\right)^{\frac{1}{k}}\leq k+\sum\limits_{q\leq N}\frac{1}{q},\]where $\sum\limits_{q\leq N}\frac{1}{q}$ is the summation over of prime powers $q\leq N$ (including $q=1$). Note: For integer $n>1$, $\omega (n)$ denotes number of distinct prime factors of $n$, and $\omega (1)=0$.
Problem
Source: 2014 China TST 2 Day 1 Q1
Tags: floor function, inequalities, number theory proposed, number theory
23.03.2014 10:08
I apologize if this solution is a little unclear. I will probably clean it up in the morning. For an integer $a$, define $X_a$ to be the event where for an integer $n$, $X_a = 1$ if $a|n$ and $0$ otherwise. If we restrict $X_a$ to be on the integers from $1$ to $N$, remark that $E[X_a] \le \frac{1}{a}$ as there are $\lfloor \frac{N}{a} \rfloor$ integers below $n$ divisible by $a$. As a consequence of this, we have for distinct primes $a_1, a_2, ..., a_n$ that $E[X_{a_1}...X_{a_n}] = E[X_{a_1a_2...a_n}] \le \frac{1}{a_1...a_n}$. A simpler but still very useful fact about $X_a$ is that $X_a^c = X_a$ for any positive integer $c$, so $E[X_a^c] = E[X_a]$. Now we shall delve into the actual problem. Let $p_1, ..., p_m$ be the primes under $N$. Then it is clear that $\omega = X_{p_1} + X_{p_2} + ... + X_{p_m}$. Thus we can restate the problem as: \[ E \left ((X_{p_1} + ... + X_{p_m})^k \right ) \le \left ( k + \sum_{q \le N} \frac{1}{q} \right )^k \] where the summation ranges over all prime powers under $N$. We shall actually prove the stronger inequality where the summation ranges over all primes under $N$ instead. For simplicity we shall denote $X_{p_i}$ as simply $X_i$ from now on. First, expand the LHS using linearity of expectation and use the rule $E[X_i^c] = E[X_i]$. Then the left hand side will be a summation of terms of the form $E[X_{d_1}...X_{d_e}]$ for some $e$. One can count that the number of times such a term will show up is precisely equal to the number of ways to distribute $k$ objects into $e$ buckets with none of the buckets being empty with order still mattering. This can be achieved in $k! \cdot \dbinom{k-1}{e-1} = e \cdot (k-1)! \cdot \dbinom{k}{e}$ ways. Now we shall look at the RHS. When we expand $\left ( k + \sum_{q \le N} \frac{1}{q} \right )^k$ (but we shall keep the denominators "independent", i.e. we only combine two terms if their denominators are matching) let's count the numerator of the term with denominator $p_{d_1}...p_{d_e}$. It is straightforward to see it is: \[ \dbinom{k}{e} \cdot e! \cdot k^{k-e} \] Then if we can show $e! \cdot k^{k-e} \ge e \cdot (k-1)!$ then we will be done due to $E[X_{d_1}...X_{d_e}] \le \frac{1}{p_{d_1}...p_{d_e}}$ and the fact every term shows up more times on the RHS than the left. The LHS is strictly decreasing in $e$ while the RHS is increasing, so to prove it it suffices to check the case of $e=k$. But then we see equality holds, so the inequality holds for all $e$ and therefore the problem is proven.
25.11.2014 21:46
Well I was trying the problem and this is what I arrived at and I will be grateful to anyone who can say whether it is correct or not. I arrived at proving an inequality like this: $\frac{\sum_{i=1}^t {a_i}^k}{N} \le (k+ \frac{\sum_{i=1}^t a_i}{N})^k$. Can anyone tell whether there is anything wrong?
11.06.2022 23:41
We will prove that For integers $p,n\le N$, \[\left(\frac{1}{N}\sum\limits_{n=1}^{N}(\omega (n))^k\right)^{\frac{1}{k}}\leq k+\sum\limits_{p\leq N}\frac{1}{p},\]where $\sum\limits_{p\leq N}\frac{1}{p}$ is the summation over primes. Let $$ x_{p,n} = \left\{ \begin{array}{ll} 1 & \quad p \mid n \\ 0 & \quad \text{otherwise} \end{array} \right. $$ We can see that $\omega(n) = \sum\limits_{p\mid n} 1 = \sum\limits_{p\le N} x_{p,n}$ Therefore, \begin{align*} \frac 1N \sum\limits_{n=1}^N \omega(n)^k & = \frac 1N \sum_{n=1}^N \left(\sum_{p\le N} x_{p,t} \right)^k\\ & = \frac 1N \sum_{p_1, p_2, \cdots, p_k} \sum_{n=1}^N \prod_{p\in \{p_1,\cdots,p_k\}} x_{p,n}\\ & = \frac 1N \sum_{p_1,\cdots,p_k} \left\lfloor \frac{N}{\prod_{p\in \{p_1,\cdots,p_k\}} p} \right\rfloor \\ & \le \sum_{p_1,\cdots,p_k : \prod\limits_{p\in \{p_1,\cdots,p_k\}} p<N} \left(\frac{1}{\prod\limits_{p\in \{p_1,\cdots,p_k\}} p}\right) (*) \end{align*} Now, rewrite $$\left(k+\sum\limits_{p\le N} \frac 1p\right)^k =\left(c_1+c_2+\cdots+c_k+\sum\limits_{p\le N} \frac 1p\right)^k$$ Where $c_j=1\forall 1\le j\le k$ Now we compare their expansions. We define $g(p_1,\cdots,p_k)$ to be a $k$-tuple as follows: Suppose among $\{p_1,\cdots,p_k\}$, there are $t\le k$ distinct primes, call $m_1,\cdots,m_t$. Let $f\colon \{1,\cdots,k\}\to \{1,\cdots,t\}$ such that I pick $p_j=m_{f(j)}$ in the expansion of $(*)$. By our setup, $f$ is a surjection, so there exists $a_1,\cdots,a_t$ such that $a_j$ is the smallest positive integer such that $f(a_j)=j$. We pick $g(p_1,\cdots,p_k)=(s_1,\cdots,s_k)$ where $$ s_j = \left\{ \begin{array}{ll} \frac{1}{m_{f(j)}}=\frac{1}{m_r} & \quad \text{if } j=a_r \text{ for some integer }r \\ f(j) & \quad \text{otherwise} \end{array} \right. $$ I claim $g$ is injective. Suppose $g(p_1,\cdots,p_k)=g(q_1,\cdots,q_k)$. First note $\{p_1,\cdots,p_k\} = \{q_1,\cdots,q_k\}$ because every prime in $\{p_1,\cdots,p_k\}$ appears exactly once in $g(p_1,\cdots,p_k)$ and other primes do not appear. Secondly, the $a_j$ and $f$ for $p_1,\cdots,p_k, q_1,\cdots,q_k$ must be the same, as needed. Therefore, each $(p_1,\cdots,p_k)$ in $(*)$ maps to a unique combination of terms in the expansion of $\left(c_1+\cdots+c_k+\sum\limits_{p\le N} \frac 1p\right)^k$ with the same product, namely $(t_1,\cdots,t_k)$ where $t_j=s_j$ if $s_j$ is the reciprocal of a prime and $t_j=c_{s_j}$ otherwise. Since no $k$-tuple is counted twice, the conclusion follows.