2025/11/10 by Kreuzer, Martin
Computer Science · Mathematics · #13C13 (Secondary) #94B05 #94B27 (Primary) 14G50 #Algebraic Geometry (math.AG) #Coding theory and cryptography #Commutative Algebra (math.AC) #Commutative Algebra and Its Applications #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Polynomial and algebraic computation
paper · doi:10.48550/arxiv.2511.06843
openalex publication_date 2025/11/10 · openalex created_date 2025/11/12 · openalex updated_date 2026/07/28
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 \mathbbX, let R be its homogeneous coordinate ring and \mathfrakJ_\mathbbX its canonical ideal. Then the LCE problem is shown to be equivalent to an algebra isomorphism problem for the doubling R/\mathfrakJ_\mathbbX. 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.