整式递推的精度保留问题

· · 个人记录

大约两周前，leukocyte 等人跟我反应了一个尝试计算 g=f^k 时发现的现象：

我们使用经典的求导方法 g'f=kf'g 来进行计算，但在 \bmod p 的情况下，递推式由于形如 na_n = \cdots，在 p\mid n 的地方是推不下去的。但如果我们在 \bmod p^2 的情况下进行计算呢？显然 g_p \bmod p 的值是正确的，一直到 g_{2p-1} \bmod p 的正确性也都比较显然。但经过测试我们发现不止于此——对于 <p^2 的项，g_n \bmod p 的值都是正确的！因此我们很自然地想要提问：

我的能力是有限的，不可能一下解决所有问题，姑且在此先丢出一个想法。

我们回顾等式 g'f-kf'g=0，对于同余运算，我们认为在 \bmod p^2 意义下的这样一个 g 实际上满足的是一个被扰动的等式 g'f - kf'g = p^2 \mathcal E，其中 \mathcal E 是扰动项（把整个问题看做 \mathbb Q_p[[x]] 上考虑更为自然，这样就是说 \mathcal E 是某一个属于 \mathbb Z_p[[x]] 的项）。变形就有 (\ln g)'=k(\ln f)' + p^2\mathcal E。也即

g = f^k \cdot \exp \left(\int p^2 \mathcal E \,\mathrm{d} x\right)

积分之后，在次数 <p^2 的部分我们就有 g = f^k \cdot \exp (p^2\mathcal E_1 + p \mathcal E_2(x^p))。容易验证最坏的情况 \exp p^2x 和 \exp p x^p 都不会污染 \bmod p 的结果。

那么不难类比，如果我们 \bmod p^e，所得的结果应当是在 <p^e 的部分，有

g = f^k \cdot \exp\left( p^e \mathcal E_1(x) + p^{e-1} \mathcal E_2(x^p) + \cdots + p \mathcal E_e(x^{p^{e-1}}) \right)

考虑数 \dfrac{(p^j x^{p^{e-j}})^n}{n!} 的质因子数，是 jn - (\lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \cdots)\ge n\left(j - \frac 1{p-1}\right) 的。而 j=1 的时候，我们在 <p^e 的项的影响有 n<p，显然满足。否则 \ge n \ge 1。

对于更加一般的情况，我还没有很好的想法，而且我们还有很多东西不知道是否能派上用场：比如 Witt 向量（其中有的部分和我们形式相近？）、Artin-Hasse 指数……小模数问题还有很多未知。