Code Equivalence, Point Set Equivalence, and Polynomial Isomorphism
Martin Kreuzer
线性码等价(LCE)问题被证明等价于点集等价(PSE)问题，即检查有限域上射影空间中两个点集是否仅相差一个线性坐标变换的问题。对于这样的点集𝕏，令R为其齐次坐标环，𝔍_𝕏为其典范理想。那么LCE问题被证明等价于其倍化R/𝔍_𝕏的一个代数同构问题。由于这个倍化是一个Artinian Gorenstein代数，我们可以使用其Macaulay逆系统将LCE问题约化为齐次多项式的多项式同构(PI)问题。在关于码的一些温和假设下，最后一步是多项式时间的。此外，对于不可分解的等偶码，我们可以通过注意到相应的点集是自关联且算术Gorenstein的，从而将LCE搜索问题约化为3次的多项式同构搜索问题，这样我们就可以使用坐标环的Artinian约化的同构问题并构造它们的Macaulay逆系统。
The linear code equivalence (LCE) problem is shown to be equivalent to the point set equivalence (PSE) problem, i.e., the problem to check whether two sets of points in a projective space over a finite field differ by a linear change of coordinates. For such a point set 𝕏, let R be its homogeneous coordinate ring and 𝔍_𝕏 its canonical ideal. Then the LCE problem is shown to be equivalent to an algebra isomorphism problem for the doubling R/𝔍_𝕏. As this doubling is an Artinian Gorenstein alg...