gyro永不抽风！ - Math
type: channel
link: https://gyrojeff.top/index.php/tag/Math/
items: 深度学习分布偏移理论
items: 网络流——最大流证明详解
items: 深度学习的正则化方法
items: 深入理解多项式推理法
items: 具体数学 基本恒等式 旁注
items: 从精度问题看 softmax 与 CrossEntropyLoss
items: 具体数学 数论 基础题答案
items: 具体数学 数论 项链问题
items: 具体数学 μ函数 旁注
items: 具体数学 φ函数 旁注

深度学习分布偏移理论
type: item
date: 2022-04-02T12:37:00+00:00
description: 本节主要为以下内容的笔记：https://zh-v2.d2l.ai/chapter_multilayer-perceptrons/environment.html 训练到底在做什么？ 训练其实是在最小化通过数据集得到的经验风险： $$ \mathop{\mathrm{minimize}}_f \frac{1}{n} \sum_{i=1}^n l(f(\mathbf{x}_i), y_i), $$ 其中 $l$ 是损失函数，用来度量对于给定的标签 $y_i$，预测值 $f(\mathbf {x}_i)$ 的糟糕程度。 但是我们想要得到的又是什么呢？我们想要的是最小化实际风险，也就是最小化下面这个期望： $$ E_{p(\mathbf{x}, y)} [l(f(\mathbf{x}), y)] = \int\int l(f(\mathbf{x}), y) p(\mathbf{x}, y) \;d\mathbf{x}dy $$ 然而在实践中，我们通常无法获得总体数据。 因此，经验风险最小化， 是一种实用的机器学习策略，希望能近似最小化真实风险。 协变量偏移 在不同分布偏移中，协变量偏移可能是最为广泛研究的。这里我们假设：虽然输入的分布可能随时间而改变，但标签函数（即条件分布 $P(y \mid \mathbf{x})$ ）没有改变。统计学家称之为协变量偏移 （covariate shift），因为这个问题是由于协变量（特征）分布的变化而产生的。虽然有时我们可以在不引用因果关系的情况下对分布偏移进行推断，但在我们认为 $\mathbf{x}$ 导致 $y$ 的情况下，协变量偏移是一种自然假设。 协变量偏移的例子 现在我们使用猫狗照片 $\mathbf x$ 来训练一个猫狗分类器来给出猫狗标签 $y$ 训练数据集是真实的猫狗图片 测试数据集是卡通形象的猫狗图片 虽然猫狗图片的分布 $P(\mathbf{x})$ 被改变了（测试集上图片的分布改变了），但是猫狗图片对于猫狗分类的条件分布 $P(y \mid \mathbf{x})$ 并未改变（确定了照片，分类也就确定了） 这是由于特征分布的变化导致的（协变量的变化，这里的协变量就是图片风格） 在这种情况下，是猫狗图片 $\mathbf x$ 导致猫狗分类 $y$ 的，所以我们一般可以使用协变量偏移假设 协变量偏移的纠正 见：https://zh-v2.d2l.ai/chapter_multilayer-perceptrons/environment.html#subsec-covariate-shift-correction 总结一下： 设目标分布为 $p(x)$，源分布为 $q(x)$，则根据协变量偏移假设 $$ p(y \mid \mathbf x) = q(y \mid \mathbf x) $$ 则 $$ \begin{aligned} &\int\int l(f(\mathbf{x}), y) p(\mathbf{x},y) \;d\mathbf{x}dy \\ =&\int\int l(f(\mathbf{x}), y) p(y \mid \mathbf{x})p(\mathbf{x}) \;d\mathbf{x}dy \\ =&\int\int l(f(\mathbf{x}), y) q(y \mid \mathbf{x})q(\mathbf{x})\frac{p(\mathbf{x})}{q(\mathbf{x})} \;d\mathbf{x}dy. \end{aligned} $$ 所以现在我们需要一个额外的权重 $$ \beta_i \stackrel{\mathrm{def}}{=} \frac{p(\mathbf{x}_i)}{q(\mathbf{x}_i)} $$ 来调整训练方式： $$ \mathop{\mathrm{minimize}}_f \frac{1}{n} \sum_{i=1}^n \beta_i l(f(\mathbf{x}_i), y_i) $$ 为了得到这个权重，我们可以通过训练一个二元分类器，来学习数据到底是来自于训练集还是来自于测试集。如果无法区分这两个分布，则意味着想相关的样本可能来自这两个分布中的任何一个。 另一方面，任何可以很好区分的样本都应该相应地显著增加或减少权重。 接下来是训练的方法：为了简单起见，假设我们分别从 $p(x)$ 和 $q(x)$ 两个分布中抽取相同数量的样本。 现在用标签 $z$ 表示：从 $p$ 抽取的数据为 $1$，从 $q$ 抽取的数据为 $-1$。 根据上面的假设，我们有： $$ P(z=1 \mid \mathbf{x}) = \frac{p(\mathbf{x})}{p(\mathbf{x})+q(\m…

网络流——最大流证明详解
type: item
date: 2022-03-31T14:30:00+00:00
description: Preface 证明思路 Q&A 网络流的定义 网络流的性质 最大流解决的问题 Ford-Fulkerson方法 残存网络 增广路径 网络流的切割 最大流最小割定理 Ford-Fulkerson 算法 Preface 本文为我初三下时学习网络流的笔记整理，大多源自算法导论。当时学习的是网络流代数法建模。（手动@金牌教练） 证明思路 明确 Ford-Fulkerson 算法的思路：在残存网络找增广路，直到不存在增广路径为止 证明如果残存不存在增广路径等价于现在的网络流已经是最大流 Q&A Q: 增广路会不会越变越多？或者说，在找增广路的过程中会不会陷入死循环？ A: 首先我们要明确：最大流问题在正权有向无环图上必定有解。而增广路必然会增广 $f$，所以增广路的条数必然是有限的，所以必然不会陷入死循环。 网络流的定义 网络流：$G = (V,E)$为一个有向图，每条边 $(u,v) \in E$都有一个非负的容量值，即$c(u,v) \geq 0$。对于每条边$(u,v) \in E$，不存在反向边$(v,u)$。若$(u,v) \notin E$，规定$c(u,v) = 0$，图中不允许出现环，即为有向无环图。在网络流的所有节点$v \in V$当中，存在两个特殊节点：源点$s$，汇点$t$。对于所有$v \in V - \{s,t\}$，都存在路径$s \rightsquigarrow v \rightsquigarrow t$，即所有节点都是互相联通的，对于每个节点，至少存在一条进入与离开的路径，即：$|E| ≥ |V| - 1$。 网络流的性质 容量限制（capacity constraint）：对于每一条边$(u,v) \in E$，存在： $$ 0 ≤ f(u,v) ≤ c(u,v) $$ 流量守恒（flow conservation）：对于每一个节点$v \in V - \{s,t\}$，必定存在： $$ \sum_{u \in V} f(u,v) = \sum_{u \in V} f(v,u) $$ 其中，$f(u,v)$表示的是从节点$u \rightarrow v$的流。 上式成立是因为对于每个节点来说，流入流量必定等于流出流量。 在此，对一个图上的流$f$定义其的$|f|$值： $$ |f| = \sum_{v\in V} f(s,v) - \sum_{v\in V} f(v,s) $$ 尽管在一个最大流当中，并不会存在流入源点的边，因此对于其来说上式的后半部分$\sum_{v\in V} f(v,s)$的值为$0$，但是这在稍后讨论的残存网络中会有应用。 最大流解决的问题 现在有一张有向无环图，将其想象成一个水管，水流会从高向低流，图中的每一条边就是一根水管，水流是单向的，而水流的方向就是图中边的方向。水在水管中流动时，会有一个流量限制，也就是它的最大容积，在这里每条边同样有流量限制，若$C_i$表示第$i$根水管的流量上限，$x_i$表示第$i$根水管当前的水流流量，则可以表示为： $$ x_i \leq C_i,~i \in [1,n] $$ 在这个问题当中：$S$点和$T$点表示起点和终点。 在这个概念定义完成之后，便可以讨论最大流问题，也就是在一群水管当中（连接起点和终点），从起点到终点，最多可以流多少水。 举一个简单形象的例子：先看下面这幅图，每条边代表的是最大流量： 很明显，这里有两条路可以走，首先看上面那条，显然能够流过的最大流量为3，另外一条则为7，所以由$S$到$T$的最大流为10： 上面是一个简单的例子，类似于这样的问题是最大流问题。 通过网络流的表述，可以将其表达为，需要求在满足网络流的两个性质的情况下： $$ \max \{|f|\} $$ 其中$|f|$表示网络$G$的流，即为 $$ \begin {aligned} &\max \{\sum_{v \in V} f(s,v) - \sum_{v \in V} f(v,s)\} \\ =&\max \{\sum_{v \in V} f(s,v) - 0\} \\ =&\max \{\sum_{v \in V} f(s,v)\} \end {aligned} $$ 其根据流量守恒，亦为$\max\{\sum_{v\in V} f(v,t)\}$。 Ford-Fulkerson方法 对于一个网络$G$，存在对应的残存网络，每次在残存网络中寻找增广路径，当找到了一条增广路径，不难找出其原先对应的边，对于两个网络的这些边上的流进行修改，从而增加流的值，但是对于原图$G$来说，每一条增广路径却可能会对边增加或减少，但是这确实是非常必要的，比如在某一张有向图中，每个节点的值都相等，则若找到一条增广路径可能会使得其他增光路径消失，但是却会停止循环…

深度学习的正则化方法
type: item
date: 2022-03-29T12:23:13+00:00
description: 为什么要正则化？ 在探讨这个问题之前，我们需要先引入欠拟合和过拟合的概念。 左侧：欠拟合，high bias, $error_{train} \gg error_{dev}$ 右侧：过拟合，high variance, $error_{train} \rightarrow 0\%$ 在过拟合的时候我们需要引入正则化，来避免过拟合。 这里介绍两种正则化方式： 权重衰减 (weight decay) Dropout Weight Decay Weight Decay 的主要思想就是加快参数的更新幅度，也就是说增大损失函数，使得梯度下降的步幅变大。但为什么这样可以防止过拟合？根据奥卡姆剃刀法则，我们倾向于认为，参数越小，网络越不复杂，越不容易过拟合，而实践也证明了这一点。 下面的公式节选自我之前的汇报笔记： 逻辑回归: $\min_{w, b}J(w, b), w\in \mathbb R^{n_x}, b\in \mathbb R$ L2 正则化：重定义 $J(w, b)$ $$ J(w, b) = \frac{1}{m}\sum_{i = 1}^{m}\mathcal L(\hat y^{(i)}, y^{(i)}) + \frac{\lambda}{2m}||w||_2^2,~||w||_2^2 = \sum_{j = 1}^{n_x}w_j^2 = w^\mathrm T w $$ L1 正则化：重定义 $J(w, b)$ $$ J(w, b) = \frac{1}{m}\sum_{i = 1}^{m}\mathcal L(\hat y^{(i)}, y^{(i)}) + \frac{\lambda}{2m}||w||_1,~||w||_1 = \sum_{j = 1}^{n_x} |w_j| $$ 神经网络：重定义损失函数： $$ J(W^{[1]}, b^{[1]},\cdots, W^{[l]}, b^{[l]}) = \frac{1}{m}\sum_{i = 1}^m \mathcal L(\hat y^{(i)}, y^{(i)}) + \frac{\lambda}{2m}\sum_{i = 1}^m ||W^{[l]}||_\mathrm F^2 $$ $$ ||W^{[l]}||_\mathrm F^2 = \displaystyle\sum_{i = 1}^{n^{[l]}}\displaystyle\sum_{j=1}^{n^{[l-1]}}(W^{[l]}_{ij})^2 $$ 红色的项标出了正则化后迭代中增加的项： $$ dW^{[l]} = \frac{1}{m} dZ^{[l]} A^{[l-1] T} \color{red}{ + \frac {\lambda}{m}W^{[l]}} $$ $$ W^{[l]} \leftarrow W^{[l]} - \alpha\frac{1}{m} dZ^{[l]} A^{[l-1] T}\color{red}{ - \alpha \frac {\lambda}{m}W^{[l]}} $$ 下面的公式出自 d2l 教科书，能让我们更好的理解超参数 $\lambda$ 的作用： 对于线性回归的损失函数： $$ L(\mathbf{w}, b) = \frac{1}{n}\sum_{i=1}^n \frac{1}{2}\left(\mathbf{w}^\top \mathbf{x}^{(i)} + b - y^{(i)}\right)^2 $$ 我们将其重定义为： $$ J(\mathbf{w}, b) = L(\mathbf{w}, b) + \frac{\lambda}{2} \|\mathbf{w}\|^2, $$ 我们来看参数的迭代式发生了什么变化。这是原来的迭代式： $$ \begin{aligned} \mathbf{w} &\leftarrow \mathbf{w} - \frac{\eta}{|\mathcal{B}|} \sum_{i \in \mathcal{B}} \partial_{\mathbf{w}} l^{(i)}(\mathbf{w}, b) = \mathbf{w} - \frac{\eta}{|\mathcal{B}|} \sum_{i \in \mathcal{B}} \mathbf{x}^{(i)} \left(\mathbf{w}^\top \mathbf{x}^{(i)} + b - y^{(i)}\right),\\ b &\leftarrow b - \frac{\eta}{|\mathcal{B}|} \sum_{i \in \mathcal{B}} \partial_b l^{(i)}(\mathbf{w}, …

深入理解多项式推理法
type: item
date: 2022-03-29T08:09:31+00:00
description: 注：本节内容为《具体数学》(原书第二版) 第五章 二项式系数 5.1 基本恒等式 的旁注，但可以独立阅读。 多项式推理法 对于多项式 $A(x)$ 与 $B(x)$ 而言。我们设其都是关于 $x$ 的不高于 $n$ 次多项式。 现在，我们求 $A(x)$ 与 $B(x)$ 的差，记作 $C(x)$： $$ A(x) - B(x) = C(x) $$ 其中，$C(x)$ 为一个不高于 $n$ 次的多项式，也就是说 $C(x)$ 有不多于 $n$ 个零点，除非 $C(x)$ 恒为零。 所以，如果我们要证明 $A(x)$ 与 $B(x)$ 相等，我们只需要证明，$A(x) - B(x)$ 存在多于 $n$ （也就是 $A(x), B(x)$ 最高次幂）个零点。换句话说，如果我们能找到多余 $n$ 个 $x_i$ 使得 $A(x_i) = B(x_i)$，我们便能证明 $A(x) = B(x)$ 多项式推理法在组合数恒等式证明中的应用 由于二项式系数在上指标与下指标均为整数的情况下会有非常简洁且容易处理的形式，我们通常能够简单地给出证明。但是，当上指标是实数时就会变得十分困难。这个时候，我们便可以使用多项式推理法。在进行向实数的推广之前，我们首先需要确认我们想要证明的式子是有限次数的式子。接下来，由于我们能够找到无穷多组正整数解，所以必然能将式子推广到实数域。证毕。 Reference 《组合数学》 P130

具体数学 基本恒等式 旁注
type: item
date: 2022-03-29T07:58:49+00:00
description: 注：本节内容为《具体数学》(原书第二版) 第五章 二项式系数 5.1 基本恒等式 的旁注。 P129 关于超出范围的整数 $k$ 的讨论 $$ \binom{n}{k} = 0, k < 0 $$ $$ \binom{n}{k} = \frac {n^{\underline{k}}}{k!} = \frac {n!\times 0 \times (-1)^{k-n-1}(k-n-1)!}{k!} = 0, k > n \geq 0, n,k \in \mathbb Z $$ 帕斯卡定理的推论 我在其他文章里写过，这里就再写一遍吧。 $$ \sum_{i=0}^k \binom{n}{n+i} =\binom{n}{n} + \binom{n+1}{n} + \cdots + \binom{n+k}{n} = \binom{n+k+1}{n+1} $$ 证明： $$ \begin{aligned} \sum_{i=0}^k \binom{n}{n+i} &=\binom{n}{n} + \binom{n+1}{n} + \cdots + \binom{n+k}{n} \\ &= \binom{n+1}{n+1} + \binom{n+1}{n} + \cdots + \binom{n+k}{n} \\ &= \binom{n+2}{n+1} + \binom{n+2}{n} + \cdots + \binom{n+k}{n} \\ &= \cdots \\ &= \binom{n+k+1}{n+1} \end{aligned} $$ 再列一下书上证明的其他推论： $$ \sum_{i \leq n} \binom{n+i}{i} = \binom{n}{0} + \binom{n+1}{1} + \cdots + \binom{n + k}{k} = \binom{n+k+1}{k} $$ $$ \sum_{i = 0}^k \binom{i}{n} = \binom{0}{n} + \binom{1}{n} + \cdots + \binom{k}{n} = \binom{k+1}{n+1} $$ P135 证明二项式定理的级数收敛 二项式定理： $$ (1+z)^r = \sum_{k=-\infty}^{+\infty} \binom{r}{k} z^k, |z| < 1 $$ 证明： 令 $$ f(z) = (1+z)^r $$ 不难由归纳法证明 $$ f^{(k)} (z) = r^{\underline{k}}(1+z)^{r-k} $$ 根据泰勒级数： $$ f(z) = \frac {f(0)} {0!} z^0 + \frac {f'(0)}{1!} z^1 + \frac {f''(0)}{2!} z^2 + \cdots = \sum_{k \geq 0} \frac {f^{(k)}(0)} {k!} z^k $$ 不难发现， $$ (1+z)^r = \sum_{k=-\infty}^{-1} \binom{r}{k} z^k + \sum_{k=0}^{+\infty} \binom{r}{k} z^k = \sum_{k\geq 0} \binom{r}{k} z^k $$ 而其中的每一项都与泰勒级数对应： $$ \binom{r}{k}z^k = \frac {f^{(k)}(0)} {k!}z^k $$ 故恒等式成立。接下来，我们要证明收敛。 不难发现： $$ \sum_{k\geq 0} \binom{r}{k} z^k \leq \sum_{k\geq 0} \left | \binom{r}{k} z^k \right | $$ 根据比较审敛法，我们证明右侧那个级数收敛即可。右侧级数： $$ u_k = \left | \binom{r}{k} z^k \right | $$ $$ \frac {u_{k+1}} {u_k} = \left | \frac {\binom{r}{k+1} z^{k+1}} {\binom{r}{k} z^k} \right | = \left | \frac {r-k} {k+1} z \right | = \left | \left ( \frac {r+1} {k+1} - 1 \right) z \right| $$ $$ \rho = \lim_{k \rightarrow \infty} \frac {u_{k+1}} {u_k} = |z| < 1 $$ 故根据比值审敛法，收敛。故原级数收敛。 P137 证明 $(5.18)$ $$ \sum_{k\leq m} \binom rk \left ( \frac r 2 - k\right) = …

从精度问题看 softmax 与 CrossEntropyLoss
type: item
date: 2022-03-28T11:59:42+00:00
description: Softmax 运算 softmax 运算用于将实数序列映射为和为一的概率序列，换句话说，softmax 运算用于将实数值规格化，使其和为一，映射成一个合理的概率分布。 下面是 softmax 的定义： $$ \hat{\mathbf{y}} = \mathrm{softmax}(\mathbf{o})\quad \text{where}\quad \hat{y}_j = \frac{\exp(o_j)}{\sum_k \exp(o_k)} $$ 对数似然与交叉熵损失函数 这里应用 d2l 教科书上的一系列公式与语段： softmax函数给出了一个向量 $\hat{\mathbf{y}}$， 我们可以将其视为“对给定任意输入$\mathbf{x}$的每个类的条件概率”。 例如，$P(y=\text{猫} \mid \mathbf{x})$。 假设整个数据集 $\{\mathbf{X}, \mathbf{Y}\}$ 具有 $n$ 个样本， 其中索引 $i$ 的样本由特征向量 $\mathbf{x}^{(i)}$ 和独热标签向量 $\mathbf{y}^{(i)}$ 组成。 我们可以将估计值与实际值进行比较： $$ P(\mathbf{Y} \mid \mathbf{X}) = \prod_{i=1}^n P(\mathbf{y}^{(i)} \mid \mathbf{x}^{(i)}) $$ 根据最大似然估计，我们最大化 $P(\mathbf{Y} \mid \mathbf{X})$ ，相当于最小化负对数似然： $$ -\log P(\mathbf{Y} \mid \mathbf{X}) = \sum_{i=1}^n -\log P(\mathbf{y}^{(i)} \mid \mathbf{x}^{(i)}) = \sum_{i=1}^n l(\mathbf{y}^{(i)}, \hat{\mathbf{y}}^{(i)}) $$ 其中，对于任何标签 $\mathbf{y}$ 和模型预测 $\hat{\mathbf{y}}$ ，损失函数为： $$ l(\mathbf{y}, \hat{\mathbf{y}}) = - \sum_{j=1}^q y_j \log \hat{y}_j $$ 再论交叉熵损失函数 我们一定要明确一个点：交叉熵损失函数的值是一个数。我们再来看这个公式： $$ l(\mathbf{y}, \hat{\mathbf{y}}) = - \sum_{j=1}^q y_j \log \hat{y}_j $$ $\mathbf{y}$ 是一个独热编码的向量 $\hat{\mathbf{y}}$ 是经过 softmax 计算的各分量和为一的预测向量 对于所有的 $y_j$，只有一个值为 $1$，其余皆为 $0$. 交叉熵损失函数的实现 # y_hat: [vector] -> matrix # y: [scalar, represent index] -> vector # the outer dimension represent sample count def cross_entropy(y_hat, y): # 这里的 range(len(y_hat)) 的意思是对于每一个 sample 都做计算，是一个 index 集合 return - torch.log(y_hat[range(len(y_hat)), y]) y_hat = torch.tensor( [[0.2, 0.7, 0.1], [0.2, 0.7, 0.1], [0.4, 0.6, 0]]) y = [1, 1, 1] cross_entropy(y_hat, y) Out: tensor([0.3567, 0.3567, 0.5108]) 由于是批量计算，所以这里 y_hat 是矩阵，y 是向量，返回值也是一个向量。 Softmax 带来的问题 https://zh-v2.d2l.ai/chapter_linear-networks/softmax-regression-concise.html#subsec-softmax-implementation-revisited 简而言之，就是 softmax 既有可能带来指数所造成的数值过大的问题，也有可能带来除法所造成的精度丧失的问题。 为了解决第一个问题，我们可以尝试通过在计算 softmax 之前从每个参数 $o_k$ 中减去 $\max(o_k)$ : $$ \begin{aligned} \hat y_j & = \frac{\exp(o_j - \max(o_k))\exp(\max(o_k))}{\sum_k \exp(o_k - \max(o_k))\exp(\max(o_k…

具体数学 数论 基础题答案
type: item
date: 2022-03-13T06:56:57+00:00
description: 注：本节内容为《具体数学》(原书第二版) 第四章 数论 基础题的答案。 4.14 (a) $$ \begin{aligned} ~& \gcd(km, kn) = t \\ \Leftrightarrow ~& t_p = \min(k_p+m_p,k_p+n_p) \\ \Leftrightarrow ~& t_p = k_p + \min(m_p,n_p) \\ \Leftrightarrow ~& t_p - k_p = \min(m_p,n_p) \\ \Leftrightarrow ~& \frac t k = \gcd(m,n), \text{According to (4.12)} \\ \Leftrightarrow ~& k\gcd(m,n) = \gcd(km, kn) \end{aligned} $$ (b) $$ \begin{aligned} ~&\operatorname{lcm}(k m, kn)=t \\ \Leftrightarrow ~& t_{p}=\max \left(k_{p}+k_{m}, k_{p}+k_{n}\right) \\ \Leftrightarrow ~& t_{p}=k_{p}+\max \left(k_{m}, k_{n}\right) \\ \Leftrightarrow ~& t_{p}-k_{p}=\max \left(k_{m}, k_{n}\right) \\ \Leftrightarrow ~& \frac{t}{k}=\operatorname{lcm}(m, n), \text{According to (4.12)} \\ \Leftrightarrow ~& k \operatorname{lcm}(m, n)=\operatorname{lcm}(k m, k n) \\ \end{aligned} $$ 4.15 不可能 引理 1：除了 $e_1$，所有欧几里得数都是奇数。 证明：根据欧几里得数的构造，每两个欧几里得数都互相互素，而 $e_1 = 2$，故后面的欧几里得数都必然不是偶数，为奇数。 引理 2：所有欧几里得数同余 $5$ 交替于 $2$ 与 $3$。 证明：通过归纳法证明： $e_1 = 2$，$e_2 = 3$，成立。 设对于所有 $k \leq 2n$ 题设都成立。 对于 $$ e_{2n+1} = \prod_{k=1}^{2n} e_k + 1 \equiv (2 \times 3) ^ n + 1 \equiv 1^n+1 \equiv 2 \pmod 5 $$ $$ e_{2n+2} = e_{2n}\prod_{k=1}^{2n} e_k + 1 \equiv 2 \times 1^n + 1 \equiv 3 \pmod 5 $$ Q.E.D. 故根据引理 2，素数 $5$ 不是任何一个欧几里得数的因子。 4.16 可由归纳法证得 $$ \sum_{i=1}^n \frac 1 {e_i} = 1 - \frac 1 {e_{n+1} - 1} $$ 证明： $$ \sum_{i=1}^{n+1} \frac 1 {e_i} = 1 - \frac 1 {e_{n+1} - 1} + \frac 1 {e_{n+1}} = 1 - \frac 1 {e_{n+1}(e_{n+1} - 1)} = 1 - \frac 1 {e_{n+2}} $$ 4.17 当 $n > m$ 时，我们有 $$ 2^{2^n} = 2^{2^m2^{n-m}} = \left(2^{2^m}\right)^{2^{n-m}} $$ $$ \begin{aligned} 2^{2^n} &= 2^{2^n} + 2^{2^m} - 2^{2^m} \\ &= \left(2^{2^m}\right)^{2^{n-m}} + 2^{2^m} - 2^{2^m} \\ &= 2^{2^m}\left(1 + \left(2^{2^m}\right)^{2^{n-m}-1}\right) - 2^{2^m} \\ &= 2^{2^m}\left(1 + 2^{2^m}\right)\left( \left(2^{2^m}\right)^{2^{n-m}-2} - \left(2^{2^m}\right)^{2^{n-m}-3} + \cdots - \left(2^{2^m}\right)^{1} + 1 \right) - 2^{2^m} \end{aligned} $$ $$ 2^{2^m}\left( \left(2^{2^m}\right)^{2^{n-m}-2} - \left(2^{2^m}\right)^{2^{n-m}-3} …

具体数学 数论 项链问题
type: item
date: 2022-03-13T05:30:32+00:00
description: 注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.9 $\varphi$ 与 $\mu$ 节中的项链问题的旁注。 P116 $mN(m,n)$ $$ m N(m, n)=\sum_{a_{0}, \ldots, a_{m-1} \in S_{n}} \sum_{0 \leqslant k<m}\left[a_{0} \ldots a_{m-1}=a_{k} \ldots a_{m-1} a_{0} \ldots a_{k-1}\right] $$ 这个式子没有问题。注意 $k$ 的下标，$k$ 包含了 $0$，所以不支持循环位移的数也会被计入。 我们来考察一下这个和式到底计入了那些值： $k=0$，不考虑循环位移产生的影响，完全对 $S_n$ 进行枚举，贡献为 $n^m$ $0<k<m$，考虑循环位移产生的影响，贡献为 $mN(m,n)-n^m$ P116 引理回顾 这页的下半部分在阐述循环位移的等价情况。这里我们回顾一下 4.8 节证明的引理。 对于 $\bmod m$ 来说，$0 \bmod m, k \bmod m, 2k \bmod m, \cdots, (m-1)k\bmod m$ 为 $0, d, 2d, \cdots, m-d$ 的排列的 $d$ 次循环。 P117 $N(m,n)$ 推导补充 $$ \begin{aligned} {N}({m}, {n}) &=\frac 1 m\sum_{0 \leqslant {k}<{m}} n^{\gcd(m,k)} \\ &=\frac 1 m\sum_{0 \leqslant {k}<{m}}\sum_{d\backslash m} n^{d}[d=\gcd(m,k)] \\ &=\frac 1 m\sum_{d\backslash m} \sum_{0 \leqslant {k}<{m}}n^{d}[d=\gcd(m,k)] \\ &=\frac{1}{{m}} \sum_{{d} \backslash {m}} {n}^{{d}} \sum_{0 \leqslant {k}<{m}}[{d}=\operatorname{gcd}({k}, {m})] \\ &=\frac{1}{{m}} \sum_{{d} \backslash {m}} n^{{d}} \sum_{0 \leqslant {k}<{m}}[{k} / {d} \perp {m} / {d}] \\ &=\frac{1}{{m}} \sum_{{d} \backslash {m}} n^{{d}} \sum_{0 \leqslant {k}<{m} / {d}}[{k} \perp {m} / {d}] \end{aligned} $$ P119 归纳证明的补充 我们还需要证明当 $m=p^k$ 时， $$ \sum_{d\backslash m} \varphi(d) n^{m/d} \equiv 0 \pmod m $$ 证明： $$ \begin{aligned} \sum_{d\backslash m} \varphi(d) n^{m/d} &= n^{p^k} + \varphi(p) n^{p^{k-1}} + \cdots + \varphi(p^{k-1})n^p + \varphi(p^k)n \\ &=n^{p^k} + (p^2-p)n^{p^{k-1}} + \cdots + (p^{k-2}-p^{k-1})n^p + (p^k-p^{k-1})n \\ &=(n^{p^k}-n^{p^{k-1}}) + p(n^{p^{k-1}}-n^{p^{k-2}}) + \cdots + p^{k-1}(n^p-n) + p^k \end{aligned} $$ （上面的每一步都可以用归纳法证得） 接下来，我们将要证明： $$ n^{p^k}-n^{p^{k-1}} \equiv 0 \pmod {p^k} $$ $$ n^{p^{k-1}}-n^{p^{k-2}} \equiv 0 \pmod {p^{k-1}} $$ $$ \cdots $$ $$ n^p - n \equiv 0 \pmod {p^{k}} $$ 为了证明这个，我们可以用归纳的方式以及二项式展开证明下面这个结论： $$ n^{p^k} = n^{p^{k-1}} + p^k \mathfrak{O}, \mathfrak O \in \mathbb Z $$ P119 为什么内和对 $m_2$ 同余于 $0$? 考察和式 $$ \sum_{d_1\backslash m_1} \varphi(d_1) \left ( \sum_{d_2 \backslash m_2} \varphi(d_2) …

具体数学 μ函数 旁注
type: item
date: 2022-03-12T07:59:42+00:00
description: 注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.9 $\varphi$ 与 $\mu$ 的旁注。 P112 $\mu$ 函数为什么能递推？ 先看定义： $$ \boxed{\sum_{d\mid m}\mu(d)}=\boxed{[m=1]} $$ $\mu(m)$ 之所以是递归式，是因为最初我们可以很轻松地确定：$\mu(1)=1$，之后随着 $m$ 值的增长，我们计算 $\mu(m)$ 时用到的值 $\mu(d)$ 一定有 $d < m$。故整个过程可以通过递推得到。 P113 莫比乌斯反演的证明 试证: $$ g(m) = \sum_{d\mid m}f(d) \Leftrightarrow f(m)=\sum_{d \mid m} \mu(d) g\left(\frac{m}{d}\right) $$ 证明： 若 $g(m) = \sum_{d\mid m}f(d)$，则 $$ \begin{aligned} &\sum_{d \mid m} \mu(d) g\left(\frac{m}{d}\right) \\ &=\sum_{d \backslash m} \mu\left(\frac{m}{d}\right) g(d) \\ &=\sum_{d \backslash m} \mu\left(\frac{m}{d}\right) \sum_{k \backslash d} f(k) \\ &=\sum_{d \backslash m} \sum_{k \backslash d} \mu\left(\frac{m}{d}\right) f(k) \\ &=\sum_{k \backslash m} \sum_{d \backslash(m / k)} \mu\left(\frac{m}{k d}\right) f(k), \text{by equation (4.9)} \\ &=\sum_{k \backslash m} \sum_{d \backslash(m / k)} \mu(d) f(k) \\ &=\sum_{k \backslash m} f(k) \sum_{d \backslash(m / k)} \mu(d) \\ &=\sum_{k \backslash m} f(k)\left[\frac m k=1\right]=f(m) \end{aligned} $$ 若 $f(m)=\sum_{d \backslash m} \mu(d) g\left(\frac{m}{d}\right)$，则 $$ \begin{aligned} &\sum_{d\backslash m}f(d) \\ =&\sum_{d\backslash m} \sum_{k\backslash d} \mu\left(\frac d k\right) g\left(k\right) \\ =&\sum_{k\backslash m} \sum_{d\backslash (m/k)} \mu\left ( \frac {dk} {k} \right) g(k) \\ =&\sum_{k\backslash m} \sum_{d\backslash (m/k)} \mu(d) g\left (k\right) \\ =&\sum_{k\backslash m} g\left (k\right) \sum_{d\backslash (m/k)} \mu(d) \\ =&\sum_{k\backslash m} g\left (k\right) \left[\frac m k = 1\right] \\ =&\sum_{k\backslash m} g\left (k\right) \left[m = k\right] \\ =&g(m) \end{aligned} $$ Q.E.D. 此处也包含了习题 12 的证明。 P114 $\sum\Phi\left(\frac x d\right)$ 的含义 我们来考察下面的式子的含义: $$ \sum_{d \geq 1} \Phi \left( \frac xd\right) $$ 其中 $$ \Phi(x) = \sum_{1 \leq k \leq x} \varphi(k) $$ 这个式子代表了 满足 $0\leq m < n \leq x$ 的基本分数 $\displaystyle\frac m n$的个数（既有最简分数，又有）。 为什么？我们不妨来逐项分析。同时，我们首先考虑 $x\in \mathbb Z$ 的情况。 $\displaystyle\Phi \left( \frac xd\right)$ 代表的是最大分母为 $\displaystyle \left…

具体数学 φ函数 旁注
type: item
date: 2022-03-12T05:23:33+00:00
description: 注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.9 $\varphi$ 与 $\mu$ 的旁注。 P111 最上方的推导 $$ n \perp m \Leftrightarrow n \perp m_1 , n \perp m_2 $$ $$ \Leftrightarrow \gcd(n, m_1) = 1, \gcd(n, m_2) = 1 $$ $$ \Leftrightarrow \gcd(n \bmod m_1, m_1) = 1, \gcd(n \bmod m_2, m_2) = 1 $$ $$ \Leftrightarrow n \bmod m_1 \perp m_1, n \bmod m_2 \perp m_2 $$ P111 “好的”的推导 这里的将互素定义为“好的”的一系列论述让人摸不着头脑。其实它就是指出互素的充要条件。然后注意 $n < m$，所以整个逻辑链可以构成递推： $$ n \bmod m \perp m \Leftrightarrow n \bmod m_1 \perp m_1, n \bmod m_2 \perp m_2 $$ 这个可以一直往下递推到素数 (以及素数的幂) 的情况。 注意：有一点原文中讲的有些含糊，那就是： 根据独立剩余得到的性质，我们任取 $n \bmod m_1$ 与 $n \bmod m_2$ 的值，总能找到唯一的 $0 \leq n < m$ 使之成立。这是这个递推能够成立的至关重要的一点！ 完成了上面的论述，我们便有： $$ \varphi(m) = \varphi(m_1) \varphi(m_2), m_1\perp m_2, m = m_1m_2 $$ P111 $\varphi$ 函数公式推导的补充 $$ \begin{aligned} \varphi(m) &= \prod _{p\mid m} \varphi(p^{m_p}) \\ &= \prod _{p\mid m} (p^{m_p} - p^{m_p-1}) \\ &= \prod _{p\mid m} p^{m_p} \Big (1 - \frac 1 p \Big) \\ &= \prod _{p\mid m} p^{m_p} \prod _{p\mid m}\Big (1 - \frac 1 p \Big) \\ &= m \prod _{p\mid m}\Big (1 - \frac 1 p \Big) \\ \end{aligned} $$ P112 为什么 $\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)+\varphi(6)+\varphi(12)=12$? 求证：对于 $d\mid m$，$\displaystyle \frac i d (i \leq d)$一定出现在 $\displaystyle \frac j m (j \leq m)$ 中。 证明： $$ \frac i d = \frac i d \frac {m/d}{m/d} = \frac {im/d} {m}, \frac {im}d \leq m $$ 所以我们可以知道：对于 $\displaystyle \frac j {12}$，约分后的最简分数 $\displaystyle\frac i d$ 一定有 $i \perp d$，且根据我们证明的引理，$\forall i \in [0..d), i \perp d$ 一定会出现原分数组 $\displaystyle \frac j {12}$ 中。 故 $$ \varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)+\varphi(6)+\varphi(12)=12 $$ 用同样的方式推广，即 $$ \sum_{d\mid m} \varphi(d) = m $$ P112 $g$ 是积性的则 $f$ 必然是积性的，证明补充 稍作补充。对于 $m=1$ $$ g(1) = \sum _{d\mid 1} f(d) = f(1) = 1 $$ 其中 $g(1)=1$ 是积性函数的定义。 对于 $m > 1$，根据归纳假设，$m_1m_2 < m, m_1\perp m_2$ 时有 $f(m_1)f(m_2) = f(m_1m_2)$，我们现在需要证明 $m_1m_2 = m$ 的情况。 $$ \begin{aligned} g(m_1m_2) &= \boxed{\sum _{d \mid m_1m_2} f(d) = \sum_{d_1\mid m_1}\sum_{d_2\mid m_2} f(d_1d_2)}^{\text{ note: }1} \\ &= \Big (\sum_…