标签：dots right sum circ finite ODE 自动机 left

机械化求解整式递推，又称 ODE 自动机

最后还是要自己写一个（
用别人的不放心！
你就放心吧，我会写使用说明的（

定义

对函数 \(y(x)\)，方程

\[\sum_{i = 0}^n a_i(x) y^{(i)}(x) = C(x) \]

为其的一个 \(n\) 阶线性微分方程。若 \(C(x) = 0\)，则其为一个齐次的线性微分方程，并称满足这一方程的函数是微分有限（d-finite）的。若 \(\forall i, \text{deg }a_i(x) = 0\)，则其是常系数的，反之则是变系数的。若对应函数是单变量的，就称对应的线性微分方程为常微分方程（ordinary differential equation，ODE）。

对数列 \(\{a_n\}\)，方程

\[\sum_{i = 0}^d p_i(n) a_{n - i} = 0 \]

为其的一个 \(d\) 阶整式递推，其中 \(\forall p_i(n)\) 为多项式，并称满足这一方程的函数是可多项式递推（P-recursive）的。

可以证明：

1. 令数列 \(\{a_n\}\) 的生成函数为 \(A(x)\)，那么 \(A(x)\) d-finite，当且仅当 \(\{a_n\}\) P-recursive。

2. 若 \(f(x), g(x)\) d-finite，则对任意常数 \(c_1, c_2\)，\(c_1 f(x) + c_2 g(x)\) d-finite。

3. 若 \(f(x), g(x)\) d-finite，则 \(f(x)g(x)\) d-finite。

4. 若 \(f(x)\) d-finite，\(g(x)\) 代数，则 \(f(g(x))\) d-finite。其中，\(g(x)\) 代数，当且仅当存在不可约方程（不可被分解为两个次数较低的多项式之乘积的多项式与 \(0\) 形成的等式）

   \[\sum_{i = 0}^n a_i(x) g^i(x) = 0 \]

   恒成立。

基础函数的构造

1. \(f(x) = x^{\alpha}\)
   考察 \(x f'(x) = x\times \alpha x^{\alpha - 1} = \alpha x^{\alpha} = \alpha f(x)\)，因此有

   \[\alpha f - x f' = 0 \]

2. \(f(x) = e^x\)
   考察 \(f'(x) = e^x = f(x)\)，因此有

   \[f - f' = 0 \]

3. \(f(x) = {}_pF_q(a_1,\dots, a_p; b_1, \dots, b_q; x)\)
   令 \(\vartheta = xD\)，则有

   \[(\vartheta + a_1)\cdots (\vartheta + a_p) f = D (\vartheta + b_1 - 1)\cdots (\vartheta + b_q - 1) f \]

4. \(f(x) = c\times g(x)\)，其中 \(c\) 为与 \(x\) 无关的常数。则 \(f(x)\) 满足的微分方程和 \(g(x)\) 相同。
   写这个的原因是老是忘记常数咋处理。记住：微分方程不管常数，常数无论如何都能消掉，递推时它们的信息由初值给出。

如何实现？

一般而言，我们想要求得 ODE 的函数都是由上方基础函数加减乘除复合得来，因此我们只需要让机器帮我们做两个 ODE 相加、相乘，ODE 和代数函数复合，就基本上可以解决我们面对的问题。

受到我没看过的论文证明的启发，我们应当维护对应 d-finite 函数 \(f\) 的各阶导数 \(f, f', f'', \dots\) 组成的线性空间。

下面令系数都在模 \(p\) 意义下进行，即属于域 \(F_p\)。令我们要处理的两个 d-finite 函数为 \(f(x), g(x)\)，并令

\[f^{(n)}(x) = \sum_{i = 0}^{n - 1} p_i(x) f^{(i)}(x), \qquad g^{(m)}(x) = \sum_{i = 0}^{m - 1} q_i(x) g^{(i)}(x) \]

其中 \(\forall p_i(x), q_i(x) \in F_p(x)\)，即系数均属于 \(F_p\) 的有理分式集。此外，不妨令 \(n\le m\)。

\(f(x) + g(x)\)

考察 \((f + g)^{(k)}\)。我们需要的就是用 \(f, \dots, f^{(n-1)}, g, \dots, g^{(m-1)}\) 表出每个 \((f + g)^{(k)}\)。

当 \(k < n\) 的时候，知道 \((f + g)^{(k)} = f^{(k)} + g^{(k)}\)。
当 \(k = n\) 的时候，\((f + g)^{(n)} = f^{(n)} + g^{(n)}\)，而 \(f^{(n)}\) 可使用微分方程降次。

从而当 \(k \ge n\) 时，若

\[(f + g)^{(k)} = \sum_{i = 0}^{n - 1} a_{k, i}(x) f^{(i)} + \sum_{i = 0}^{n - 1}(x) b_{k, i} g^{(i)} \]

则

\[\begin{aligned} (f + g)^{(k + 1)} & = \left(\sum_{i = 0}^{n - 1} a_{k, i}(x) f^{(i)} + \sum_{i = 0}^{n - 1}(x) b_{k, i} g^{(i)}\right)' \\ & = \sum_{i = 0}^{n - 1} \left(a_{k, i}'(x) f^{(i)} + a_{k, i}(x) f^{(i + 1)}\right) + \sum_{i = 0}^{n - 1}(x) \left(b_{k, i}'(x) g^{(i)} + b_{k,i}(x) g^{(i+1)}\right) \end{aligned}\]

随后只需将 \(f^{(n)}\) 用微分方程降次即可。这样由归纳法可以知道，我们总能将每个 \((f + g)^{(k)}\) 用 \(f, \dots, f^{(n-1)}, g, \dots, g^{(m-1)}\) 表出。由于向量 \([f, \dots, f^{(n-1)}, g, \dots, g^{(m-1)}] ^{\mathsf T}\) 只有 \(n + m\) 维，则 \((f + g)^{(n + m)}\) 必定能由 \(f + g, (f + g)^{(1)}, \dots, (f + g)^{(n + m - 1)}\) 表出。

因此我们可以用与维护线性基类似的思想，一个个插入 \((f + g)^{(k)}\)，最后必定可以得到一个 \((f + g)^{(k_0)}\) 使得其可以被线性表出，且 \(k_0 \le n + m\)。

\(f(x)g(x)\)

考察 \((fg)^{(k)}\) 和 \((fg)^{(k + 1)}\)。若

\[(fg)^{(k)} = \sum_{i = 0}^{n - 1} \sum_{j = 0}^{m - 1} a_{i,j}(x) f^{(i)} g^{(j)} \]

而 \(\left(a_{i,j}(x) f^{(i)} g^{(j)}\right)' = a_{i,j}'(x) f^{(i)} g^{(j)} + a_{i,j}(x) f^{(i + 1)} g^{(j)} + a_{i,j}(x) f^{(i)} g^{(j + 1)}\)，并使用微分方程降次可以知道

\[(fg)^{(k + 1)} = \sum_{i = 0}^{n - 1} \sum_{j = 0}^{m - 1} \left(a_{i,j}(x) f^{(i)} g^{(j)}\right)' \]

也符合 \((fg)^{(k)}\) 的形式。这样由归纳法可以知道，我们总能将每个 \((f g)^{(k)}\) 用 \(fg, f^{(1)}g, \dots, f^{(n-1)}g, \dots, f^{(n-2)}g^{(m-1)}, f^{(n-1)}g^{(m-1)}\) 表出。由于以上的分量只有 \(n m\) 维，则 \((f + g)^{(n m)}\) 必定能由 \(f + g, (f + g)^{(1)}, \dots, (f + g)^{(n m - 1)}\) 表出。

因此我们可以用与维护线性基类似的思想，一个个插入 \((f + g)^{(k)}\)，最后必定可以得到一个 \((f + g)^{(k_0)}\) 使得其可以被线性表出，且 \(k_0 \le nm\)。

\(f \circ g\)

这里 \(g(x)\) 符合一个代数方程 \(P(g) = 0\)。其系数 \(\in F_p(x)\)。

若 \(\text{deg } P = 1\)，则 \(g(x)\) 也 \(\in F_p(x)\)。这时令

\[(f\circ g)^{(k)} = \sum_{i = 0}^{n - 1} a_{k,i}(x) \left(f^{(i)} \circ g\right) \]

考察 \(\left(a_{k,i}(x)\left(f^{(i)} \circ g\right)\right)' = a_{k,i}'(x) \left(f^{(i)} \circ g\right) + a_{k,i}(x) \left(f^{(i + 1)} \circ g\right) g'\)，当 \(i + 1 = n\) 时可以用微分方程降次，即

\[f^{(n)}\circ g = \sum_{i = 0}^{n - 1} \left(p_i\circ g\right)\left(f^{(i)} \circ g\right) \]

若 \(\text{deg } P > 1\)，\(g(x)\) 不再具有简单的有理分式形式。上面的过程中有两个点无法直接解决：求解 \(g'\) 和求解每个 \(p_i\circ g\)。

若我们能将 \(g'\) 表示成关于 \(g\) 的某个整式 \(h(g)\)，我们就能直接将其并入前一部分的 \(\left(f^{(i + 1)} \circ g\right)\)，因此下面就是要用 \(g\) 表出 \(g'\)。

由于 \(P(g) = 0\)，其对 \(x\) 求导得到的应为零函数。考察某项 \(a_i(x) g^i(x)\)，其导数为 \(\left(a_i(x) g^i(x)\right)' = a_i'(x) g^i(x) + a_i(x) i g^{i - 1}(x) g'(x)\)，前半部分求和得到 \(\dfrac{\partial P(t)}{\partial x} \circ g\)，后半部分求和得到 \(\left(\dfrac{\partial P(t)}{\partial t}\circ g\right) g'\)，其中 \(t\) 为占位元，与 \(x\) 无关。化简得到

\[g' = -\dfrac{\partial_x P}{\partial_g P} \]

这里视 \(P(g, x)\) 为二元代数函数，\(g,x\) 彼此无关。

为降次，把 \(g'\) （对应的 \(h(g)\)）对 \(P(g)\) 取模。要算的就是同余方程

\[y\partial_g P \equiv -\partial_x P \pmod{P} \]

的解 \(y\)。可以证明这解必定存在，使用多项式扩展欧几里得即可。

对 \(p_i\circ g\)，也可以对 \(P(g)\) 取模来降次。\(p_i(x) \in F_p(x)\)，因此 \(p_i\) 分母 \(\in F_p[x]\)。而由于 \(P(u)\) 代数，其在系数所属的域 \(F_p[x]\) 上无法分解，故 \(P(u)\) 的根都在 \(F_p(x) / F_p[x]\) 上，其和 \(p_i(x)\) 的分母不存在公因式，可以求逆。

实现

我们难以实现符号计算，一般都是根据输入数据动态地寻找 ODE。当然也没必要优化多项式乘法或多项式欧几里得，大多数时候它们都难以成为瓶颈。虽然有现成的多项式板子的话没必要再写一个暴力

待补。

标签：dots,right,sum,circ,finite,ODE,自动机,left
From： https://www.cnblogs.com/joke3579/p/-/ode-automaton