$\mathbb Z/2\mathbb Z[x_1, \ldots, x_n]$中多项式函数等价类计数及置换等价类问题
咱们先解决第一个问题：不考虑变量置换时，多项式函数等价类的数量。
这里的等价关系是：两个多项式$p,q$等价当且仅当对所有$x \in (\mathbb Z/2\mathbb Z)^n$，$p(x)=q(x)$。在$\mathbb Z/2\mathbb Z$上有个核心性质：对任意元素$a \in \mathbb Z/2\mathbb Z$，都有$a2=a$。这意味着任何多项式都可以化简为**平方-free形式**——也就是所有单项式里的变量幂次都是1（比如$x_i3 = x_i$，$x_i^2x_j = x_j$）。
接下来关键的观察：每个平方-free多项式对应唯一的一个函数$f: (\mathbb Z/2\mathbb Z)^n \to \mathbb Z/2\mathbb Z$，反过来，每个这样的函数也都能被唯一的平方-free多项式表示（类似布尔函数的极小项展开）。而$(\mathbb Z/2\mathbb Z)n$总共有$2n$个元素，每个元素的函数值可以是0或1，所以函数总数是$2{2n}$。因此，不考虑置换时，多项式函数等价类的数量就是$\boldsymbol{2{2n}}$。
举个小例子验证：当$n=1$时，等价类是$0,1,x_1,1+x_1$，共$2{21}=4$个，完全符合；$n=2$时，等价类总数是$2{22}=16$个，和所有平方-free多项式一一对应。
然后是第二个问题：考虑变量置换的等价类，也就是两个多项式等价当且仅当存在变量的置换$\sigma$，使得$p(x_1,...,x_n)=q(x_{\sigma(1)},...,x_{\sigma(n)})$。这个问题没法直接给出简洁的闭公式，得用Burnside引理来计算，核心思路是“对称群中每个元素的不动点数量的平均值就是轨道（等价类）数量”。
具体步骤如下：
- 对称群$S_n$中的每个置换$\sigma$都可以分解为循环的乘积：比如$c_1$个1-循环、$c_2$个2-循环……$c_n$个n-循环，满足$\sum_{k=1}^n k \cdot c_k = n$。
- 对每个这样的$\sigma$，计算它作用下的不动点多项式数量：也就是满足$p(x_{\sigma(1)},...,x_{\sigma(n)})=p(x_1,...,x_n)$的多项式数量。这类多项式的特点是：如果某个单项式在多项式里，那么这个单项式经过$\sigma$置换变量后得到的新单项式也必须在多项式里——换句话说，多项式的支撑集是$\sigma$作用在变量子集上的轨道的并集。
- 设$N(\sigma)$是$\sigma$作用在变量子集上的轨道数量，那么不动点多项式的数量就是$2^{N(\sigma)}$（每个轨道可以选或不选加入多项式）。
- 最后用Burnside引理，等价类数量就是$\boldsymbol{\frac{1}{n!}\sum_{\sigma \in S_n} 2^{N(\sigma)}}$。
其中$N(\sigma)$可以通过$\sigma$的循环分解计算：对于每个k-循环，k个元素的集合在循环群$C_k$作用下的子集轨道数是$Q_k = \frac{1}{k}\sum_{d|k} \phi(d)2^{k/d}$（$\phi$是欧拉函数），而$\sigma$对应的$N(\sigma)$就是所有循环对应的$Q_k$的乘积，即$N(\sigma) = \prod_{k=1}^n Q_k^{c_k}$。
举个例子：当$n=2$时，$S_2$有两个置换：
- 恒等置换：循环分解是$c_1=2$，$Q_1=2$，所以$N(\sigma)=22=4$，不动点数量是$24=16$；
- 交换两个变量的置换：循环分解是$c_2=1$，$Q_2=\frac{1}{2}(\phi(1)2^2 + \phi(2)21)=3$，所以$N(\sigma)=3$，不动点数量是$23=8$。
代入Burnside引理，等价类数量就是$\frac{16+8}{2}=12$，和实际枚举的结果一致。
备注：内容来源于stack exchange，提问作者Markus Klyver
