Given a real sequence $\left \{ x_n \right \}_{n=1}^{\infty}$ with $x_1^2 = 1$. Prove that for each integer $n \ge 2$, $$\sum_{i|n}\sum_{j|n}\frac{x_ix_j}{\textup{lcm} \left ( i,j \right )} \ge \prod_{\mbox{\tiny$\begin{array}{c} p \: \textup{is prime} \\ p|n \end{array}$} }\left ( 1-\frac{1}{p} \right ). $$
Problem
Source: 2018 CGMO Day 1 Problem 3
Tags: number theory, inequalities
ThE-dArK-lOrD
13.08.2018 13:53
In this solution, let $\varphi (n)$ denote the Euler's totient function. Note that the RHS is equal to $\varphi (n)/n$. We will write the expression in left hand side as linear combination of $\Big( \sum_{i\mid d}{x_i}\Big)^2$ where $d$ varies on the set of divisor of $n$. Let the coefficient of each term, as a variable of $d$, equal to $c_d$. Comparing the coefficient of $x_ix_j$, we get that the sufficient and necessary condition for $c_d$'s is $$\sum_{\mathrm{lcm} (i,j)\mid d\mid n}{c_d} =\frac{1}{\mathrm{lcm} (i,j)}.$$Note that we have $\sum_{\mathrm{lcm} (i,j)\mid d\mid n}{c_d} =\sum_{d\mid \frac{n}{\mathrm{lcm} (i,j)}}{c_{n/d}}.$ So we can simply let $c_{n/d}=\frac{\varphi (d)}{n}\implies c_d=\frac{\varphi (n/d)}{n}$. Hence, we get $$RHS=\sum_{d\mid n}{\left( \frac{\varphi (n/d)}{n}\Big( \sum_{i\mid d}{x_i}\Big)^2 \right)}\geqslant \frac{\varphi (n)}{n} x_1^2=LHS \qquad \blacksquare$$
Grim-the-Ripper
09.10.2018 10:23
Make the observation as in the post above that the RHS is equal to $ \frac{ \varphi (n)}{n} $. Now, let us recall that $ \sum_{d \mid n} \varphi(d) = n $, which upon replacing $ n $ with $ \gcd(i,j) $ gives $ \boxed{\sum_{d \mid \gcd(i,j)} \varphi(d) = \gcd(i,j)} $. With that in mind, we return to manipulating the expression on the LHS: $ \sum_{i|n}\sum_{j|n}\frac{x_ix_j}{\textup{lcm} \left ( i,j \right )} = \sum_{i|n}\sum_{j|n}\frac{x_{\frac{n}{i}}x_{\frac{n}{j}}}{n} \gcd (i,j) \\ (*) $ Recalling the boxed expression, in a bid to separate the variables, we are motivated to define $ \epsilon_i(r) $ as follows, $ \epsilon_i(r) = \begin{cases} \sqrt{ \varphi(r)} & \text{when } r \mid i \\ 0 &\text{otherwise} \\ \end{cases} $. This is because we conveniently have $ \gcd(i,j) = \sum_{r=1}^{n} \epsilon_i(r) \epsilon_j(r) $ since the product only evaluates to a nonzero value of $r$ when $ r \mid i, r\mid j \Rightarrow r \mid \gcd(i,j) $ and then we are reduced to the boxed expression. Now, we can go back to $ (*) $, $ \sum_{i|n}\sum_{j|n}\frac{x_{\frac{n}{i}}x_{\frac{n}{j}}}{n} \sum_{r=1}^{n} \epsilon_i(r) \epsilon_j(r) = \frac{1}{n} \sum_{r=1}^{n} \left(\sum_{i|n } x_{\frac{n}{i}} \epsilon_i(r) \right)^2 \geq \frac{1}{n} \left(\sum_{i|n } x_{\frac{n}{i}} \epsilon_i(n) \right)^2 = \frac{ \varphi(n)}{n} x_1^2 = \frac{ \varphi(n)}{n} = \text{RHS} $, as desired.
trumpeter
29.03.2019 01:02
I claim that \[\displaystyle\sum_{i\mid n}\displaystyle\sum_{j\mid n}\frac{nx_ix_j}{\operatorname{lcm}\left(i,j\right)}=\displaystyle\sum_{d\mid n}\varphi\left(d\right)\left(\displaystyle\sum_{k\mid\frac{n}{d}}x_k\right)^2\]for integers $n\geq2$. To prove this, we must compute the coefficients of $x_i^2$ and $x_ix_j$ on each side.
Note that $x_i^2$ with $i\mid n$ appears when $i=j$ only, so the coefficient of $x_i^2$ on the LHS is $\frac{n}{i}$. On the other hand, $x_i^2$ appears in the RHS sum under $d$ when $i\mid\frac{n}{d}$ (equivalently $d\mid\frac{n}{i}$). So the coefficient of $x_i^2$ on the RHS is $\displaystyle\sum_{d\mid\frac{n}{i}}\varphi\left(d\right)=\frac{n}{i}$ so the coefficients match.
Now, note that $x_ix_j$ with $i,j\mid n$ and $i\neq j$ appears on the LHS twice for $\left(i,j\right)$ and $\left(j,i\right)$, so the coefficient of $x_ix_j$ on the LHS is $\frac{2n}{\operatorname{lcm}\left(i,j\right)}$. On the other hand, $x_ix_j$ appears in the RHS sum under $d$ when $i,j\mid\frac{n}{d}$ (equivalently $d\mid\frac{n}{\operatorname{lcm}\left(i,j\right)}$), and it appears as $2x_ix_j$ in the squared part. So the coefficient of $x_ix_j$ on the RHS is $\displaystyle\sum_{d\mid\frac{n}{\operatorname{lcm}\left(i,j\right)}}2\varphi\left(d\right)=\frac{2n}{\operatorname{lcm}\left(i,j\right)}$ so the coefficients match.
Now, using this equality, we have that \[\displaystyle\sum_{i\mid n}\displaystyle\sum_{j\mid n}\frac{x_ix_j}{\operatorname{lcm}\left(i,j\right)}=\displaystyle\sum_{d\mid n}\frac{\varphi\left(d\right)}{n}\left(\displaystyle\sum_{k\mid\frac{n}{d}}x_k\right)^2\geq\frac{\varphi\left(n\right)}{n}x_1^2=\frac{\varphi\left(n\right)}{n}=\displaystyle\prod\left(1-\frac{1}{p}\right)\]as desired.
This inequality is tight, as we can take $x_n=\mu\left(n\right)$, where $\mu$ is the Möbius function defined as \[\mu\left(n\right)=
\begin{cases}
1 & \text{if }n\text{ squarefree with an even number of distinct prime factors} \\
-1 & \text{if }n\text{ squarefree with an odd number of distinct prime factors} \\
0 & \text{if }n\text{ not squarefree}
\end{cases}
\]This can be computed as follows:
WLOG let $x_1=1$ (since flipping the sign of all $x_i$ does not change anything). We require $\displaystyle\sum_{d\mid m}x_d=\delta_{m,1}$ for all $m\mid n$ as equality case in the trivial inequality, where $\delta_{m,1}=1$ if $m=1$ and $0$ otherwise (the Kronecker delta). So $\delta_{m,1}=x_d*1$ and thus by the Möbius inversion formula, $x_d=\delta_{m,1}*\mu=\mu\left(d\right)$ for all $d\mid n$.