Code Equivalence, Point Set Equivalence, and Polynomial Isomorphism

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 $\mathbb{X}$, let $R$ be its homogeneous coordinate ring and ${\mathfrak{J}}_{\mathbb{X}}$ its canonical ideal. Then the LCE problem is shown to be equivalent to an algebra isomorphism problem for the doubling $R\mathrm{/}{\mathfrak{J}}_{\mathbb{X}}$. As this doubling is an Artinian Gorenstein algebra, we can use its Macaulay inverse system to reduce the LCE problem to a Polynomial Isomorphism (PI) problem for homogeneous polynomials. The last step is polynomial time under some mild assumptions about the codes. Moreover, for indecomposable iso-dual codes we can reduce the LCE search problem to the PI search problem of degree 3 by noting that the corresponding point sets are self-associated and arithmetically Gorenstein, so that we can use the isomorphism problem for the Artinian reductions of the coordinate rings and form their Macaulay inverse systems.