一种经典树哈希算法的正确性证明

我们有一个经典的有根树哈希算法：$f(T)=x\prod(f(T_i)+y)$，$T_i$ 表示 $T$ 的一个子树，这个算法一直以来被认为是不正确的，然而我们发现在随机 $x,y$ 的情况下，这个算法判断两棵树是否同构的错误率只有 $O(\frac n{\text{mod}})$，也就意味着只要不对着卡就是对的。

我们发现对于一棵确定的有根树 $T$，$f(T)$ 的值是一个关于 $x,y$ 的二元多项式，只需证 $f(S)=f(T)$ 时必有 $S$ 同构于 $T$ 即可。然后我们进行归纳，因此只需要证明 $f(S)=f(T)$ 时必有 $\{f(S_i)\}=\{f(T_i)\}$。

如果 $f(S_i)+y$ 在有理数域内是不可约的，那么上一条显然成立，因为我们有任意元整系数多项式的唯一分解定理。

假设 $f(S_i)+y=A\times B$，考察 $[x^0]A$ 与 $[x^0]B$，显然 $[x^0]A\times[x^0]B=y$。然后我们考察 $[y^0]A$ 与 $[y^0]B$，显然 $[y^0]A\times[y^0]B=x^{|S_i|}$（$|S_i|$ 是 $S_i$ 的大小），但是我们注意到 $[x^0y^0]A=1$，所以 $[y^0]A=1,[y^0]B=x^{|S_i|}$，注意到 $f(S_i)+y$ 在 $x$ 的次数大于等于 $|S_i|$ 时只有一项 $x^{|S_i|}$，因此 $A=1$，$f(S_i)+y$ 其实不可约。

于是我们证明了两棵有根树不同时，对应的二元多项式也不同（以上证明也可以直接被搬到 $\mathbb F_p$，所以对于 $\bmod p$ 的情况这一点也成立），根据 schwartz zippel lemma，我们随机取 $x,y$，错误率就是 $O(\frac n{\text{mod}})$ 的。