1

約数関数関連の不等式

159
0
$$\newcommand{A}[0]{\boldsymbol A} \newcommand{B}[0]{\boldsymbol x} \newcommand{C}[0]{\mathbb C} \newcommand{Cov}[0]{\mathrm{Cov}} \newcommand{d}[1]{\mathrm d} \newcommand{E}[0]{\mathrm E} \newcommand{F}[0]{\mathcal F} \newcommand{L}[0]{\mathcal L} \newcommand{M}[0]{\mathcal M} \newcommand{mod}[0]{\mathrm{mod}} \newcommand{R}[0]{\mathbb R} \newcommand{x}[0]{\boldsymbol x} $$

初めに

Twitterに投稿した自作クイズ
https://x.com/miyagisendaiaka/status/1722511645585600816?s=20
の答えです.
誰も解いてくれなくて悲しいです.

まず,約数関数とは次式で定義されます.

約数関数

$$\sigma_p(n):=\sum_{d|n}d^p$$

要するに,$n$の正の約数を$p$乗したものをすべて足し合わせたものです.
また,知っていると便利な道具をいくつか準備しましょう.別に無くても解けるんだけども.

$$\prod_{d|n}d^p = \sqrt{n^{p \ \sigma_0(n)}}$$

きれいな証明

$$ \prod_{d|n}d^p=\prod_{d|n}\left(\frac nd\right)^p $$
に注意すると,
$$ \left(\prod_{d|n}d^p \right)^2 = \prod_{d|n}d^p\prod_{d|n}\left(\frac nd\right)^p = \prod_{d|n}d^p\left(\frac nd\right)^p = \prod_{d|n}n^p = n^{p \ \sigma_0(n)} $$

より,$\prod_{d|n}d^p>0$に注意すると,
$$ \prod_{d|n}d^p = \sqrt{n^{p \ \sigma_0(n)}} $$

を得る.

$n$の正の約数の個数は$\sigma_0(n)$となることに注意されたし.

$$ \sigma_p(n)\sigma_q(n) \leq \sigma_0(n)\sigma_{p+q}(n) $$

約数を大きい順に並べた数列は単調減少列となるから,Chebyshev's sum inequalityより,
$$ \frac{1}{\sigma_0(n)}\sum_{d|n}d^p\frac{1}{\sigma_0(n)}\sum_{d|n}d^q \leq \frac{1}{\sigma_0(n)}\sum_{d|n}d^{p+q} $$
が成り立つ.
両辺に$\sigma_0(n)^2$を乗じて,

$$ \sigma_p(n)\sigma_q(n) \leq \sigma_0(n)\sigma_{p+q}(n) $$

を得る.

余談だが,俺が思いついた共分散を用いた証明も載せておこう.

美しい証明

$n$の正の約数を$p$乗したものの集合を$D^p$とすると,
$$ \Cov(D^p,D^q) = \E(D^p D^q)-\E(D^p)\E(D^q) $$

$D^p,D^q$の要素をそれぞれ大きい順に並べたものとすると,明らかに$\Cov(D^p,D^q)\geq0$だから,

$$ \E(D^p D^q)-\E(D^p)\E(D^q) \geq 0 $$

両辺に$\sigma_0(n)^2$を乗じて,

$$ \sigma_p(n)\sigma_q(n) \leq \sigma_0(n)\sigma_{p+q}(n) $$

を得る.

次に,不等式にあまり関係のない公式を載せておく.

$$ n^p\sigma_{-p}(n) = \sigma_p(n) $$

$$ \sum_{d|n}d^p=\sum_{d|n}\left(\frac nd\right)^p $$
に注意すると,

$$ n^p\sigma_{-p}(n) = n^p\sum_{d|n}d^{-p} = n^p\sum_{d|n}\left(\frac dn\right)^p = \sum_{d|n}d^p = \sigma_p(n) $$

問1.

$$\sigma_p(n) \geq \sqrt{n^{p-q}} \sigma_{q/2}(n)$$

その1

$\sigma_p(n)$の項数が$\sigma_0(n)$であることに注意すると,AM$\geq$GMと先に証明した公式1より,
$$ \frac{\sigma_p(n)}{\sigma_0(n)} \geq \sqrt[\sigma_0(n)]{\prod_{d|n}d^p} = \sqrt[\sigma_0(n)]{\sqrt {n^{p\sigma_0(n)}}} = \sqrt {n^p} $$

また,$\sigma_{q/2}(n) = \sum_{d|n}d^{q/2} \leq \sum_{d|n}n^{q/2} = n^{q/2}\sigma_0(n)$だから,

$$ \sigma_0(n) \geq n^{-q/2}\sigma_{q/2}(n) $$

以上により,

$$ \sigma_p(n) \geq\sqrt {n^p}\sigma_0(n) \geq \sqrt{n^{p-q}}\sigma_{q/2}(n) $$
(等号成立条件は$p=q=0$)
を得る.

次に,$\sigma_p(n)/\sigma_0(n) \geq \sqrt {n^p}$を公式1を知らなくても解ける方法を記しておく

その2 美しい証明

AM$\geq$HMより,

$$ \frac{\sigma_p(n)}{\sigma_0(n)} \geq \frac{\sigma_0(n)}{\sigma_{-p}(n)} = \frac{\sigma_0(n)}{\sigma_p(n)/n^p}(\because \mathrm{公式3}) $$

両辺に$\sigma_p(n)\sigma_0(n)(>0)$を乗じて,

$$ \sigma_p(n)^2 \geq n^p \sigma_0(n)^2 $$

$0 < x\leq y$のとき,$ x \leq y \iff \sqrt x \leq \sqrt y$だから,

$$ \sigma_p(n) \geq \sqrt {n^p}\sigma_0(n) $$
(等号成立条件は$p=0$)
また,$\sigma_{q/2}(n) = \sum_{d|n}d^{q/2} \leq \sum_{d|n}n^{q/2} = n^{q/2}\sigma_0(n)$だから,

$$ \sigma_0(n) \geq n^{-q/2}\sigma_{q/2}(n) $$

以上により,

$$ \sigma_p(n) \geq\sqrt {n^p}\sigma_0(n) \geq \sqrt{n^{p-q}}\sigma_{q/2}(n) $$
(等号成立条件は$p=q=0$)
を得る.

問2

$$ \prod_{i=1}^r \sigma_{p_i}(n) \leq \sigma_0(n)^{r-1}\sigma_{\sum_{i=1}^r p_i}(n) $$

その1

対称性より,

$$ \prod_{i=1}^r \sigma_{p_i}(n) = \sum_{d_1|n} \cdots \sum_{d_r|n}d_1^{p_1} \cdots d_r^{p_r} = \frac1{r!}\sum_{d_1|n} \cdots \sum_{d_r|n}\sum_{\tau}d_{\tau(1)}^{p_1} \cdots d_{\tau(r)}^{p_r} $$
($\tau$$\{1,...,r\}$の置換)

Muirhead's Inequalityより,

$$ \sum_{\tau}d_{\tau(1)}^{p_1} \cdots d_{\tau(r)}^{p_r} \leq \sum_{\tau}d_{\tau(1)}^{\sum_{i=1}^r p_i} $$

だから,

$$\begin{align} \prod_{i=1}^r \sigma_{p_i}(n) & \leq\frac1{r!}\sum_{d_1|n} \cdots \sum_{d_r|n}\sum_{\tau}d_{\tau(1)}^{p_1} \cdots d_{\tau(r)}^{p_r}\\ & \leq \frac1{r!}\sum_{d_1|n} \cdots \sum_{d_r|n}\sum_{\tau}d_{\tau(1)}^{\sum_{i=1}^r p_i}\\ & = \frac1{r!}\sum_{d_1|n} \cdots \sum_{d_r|n}\left(d_1^{\sum_{i=1}^r p_i}(r-1)! + \cdots + d_r^{\sum_{i=1}^r p_i}(r-1)!\right)\\ & = \left(\frac1{r}\sum_{d_1|n} \cdots \sum_{d_r|n}d_1^{\sum_{i=1}^r p_i}\right) \cdot r\\ & = \sigma_0(n)^{r-1}\sigma_{\sum_{i=1}^r p_i}(n) \end{align}$$

(等号成立条件は$p_1=...=p_r=0$)
を得る.

俺がこの不等式を思いついたときはこういう手順だったが,実は帰納法で簡単に解けてしまうという問題としての脆弱性も孕んでいる.

ズル

$r=1$のときは自明.
$r=2$のとき,$\sigma_{p_1}(n)\sigma_{p_2}(n) \leq \sigma_0(n)\sigma_{p_1+p_2}(n)...(*)$...公式2より成立.
$r=k$のとき,与不等式が成立すると仮定すると,$r=k+1$のとき
$$ \prod_{i=1}^{k+1} \sigma_{p_i}(n) \leq \sigma_0(n)^{k}\sigma_{\sum_{i=1}^{k+1} p_i}(n) $$
となることを示す.
$$\begin{align} \prod_{i=1}^{k+1} \sigma_{p_i}(n) & = \prod_{i=1}^{k} \sigma_{p_i}(n) \cdot \sigma_{p_{k+1}}(n)\\ & \leq \sigma_0(n)^{k-1}\sigma_{\sum_{i=1}^k p_i}(n)\cdot \sigma_{p_{k+1}}(n)\\ & \leq \sigma_0(n)^{k-1}\sigma_0(n)\sigma_{\sum_{i=1}^{k+1} p_i}(n) \ \ (\because(*))\\ & \leq \sigma_0(n)^{k}\sigma_{\sum_{i=1}^{k+1} p_i}(n) \end{align}$$

$r=k+1$でも成立.
以上により,題意は示された.

最後に

バイト中に生徒に問題を解かせている間に作ったものゆえ改善の余地は幾らでも在りそうです.新しいクイズを思いついたら,暇があれば追加していこうと思います.
ここに載せていないだけで様々な解法を思いついています.
(例えば,$\sigma_p(n)=\sum_{i=1}^{\sigma_0(n)}(d_i+d_{n+1-i})/2\ \geq \sum_{i=1}^{\sigma_0(n)}\sqrt n=\sqrt n\sigma_0(n)$等.)
もし,別の解法を思いついたら教えてください.

投稿日:20231111
更新日:20231111

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

東北大学工学研究科出身 できるだけ受け売りはせず,自分で思いついた解法や妄想を備忘録がてら書き綴っていこうと思います.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中