The Closure of LCD-to-GI Reductions via Generalized Inner Products
Abstract
The Permutation Equivalence Problem (PEP) for linear complementary dual (LCD) codes reduces to Graph Isomorphism (GI) through the orthogonal projector onto the code, but this requires a trivial hull. We ask whether the reduction extends when the standard inner product is replaced by a nondegenerate symmetric bilinear form M. We make precise what it means for M to yield a valid reduction to GI and prove that, for length n ≥ 3 and every field size, this holds if and only if M is permutation-invariant. The reduction then reaches, beyond LCD codes, a class of codes with one-dimensional hull: exactly those whose hull is spanned by a vector with nonzero coordinate sum. We count these codes exactly; for odd q, asymptotically the method covers a fraction ∏i ≥ 2(1+q−i)−1 of all codes, 1 + q−1 times the fraction of LCD codes. A polynomial-time reduction algorithm is given.
Related
- Painlevé Integrability, Hamiltonian Structure and Exact Elliptic Reductions of a Generalized Nonlinear Wave Equation
- Inner Products and Banach Algebra structures on Bicomplex Numbers and Their Associated Spaces
- On the Gram matrix of standard inner products of asymmetrically-weighted Hermite functions
- Recovery of latent inner products from an anisotropic Gaussian random geometric graph
- Exact probability laws of random inner products: Dirichlet splines, overlaps, uncertainty, and Bargmann invariants
BibTeX
@misc{ishizuka2026closure,
title = {{The Closure of LCD-to-GI Reductions via Generalized Inner Products}},
author = {Keita Ishizuka},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.23120},
eprint = {2605.23120},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.23120},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Closure of LCD-to-GI Reductions via Generalized Inner Products
AU - Keita Ishizuka
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2605.23120
UR - https://arxiv.org/abs/2605.23120
AB - The Permutation Equivalence Problem (PEP) for linear complementary dual (LCD) codes reduces to Graph Isomorphism (GI) through the orthogonal projector onto the code, but this requires a trivial hull. We ask whether the reduction extends when the standard inner product is replaced by a nondegenerate symmetric bilinear form M. We make precise what it means for M to yield a valid reduction to GI and prove that, for length n ≥ 3 and every field size, this holds if and only if M is permutation-invariant. The reduction then reaches, beyond LCD codes, a class of codes with one-dimensional hull: exactly those whose hull is spanned by a vector with nonzero coordinate sum. We count these codes exactly; for odd q, asymptotically the method covers a fraction ∏_i ≥ 2(1+q^−i)^−1 of all codes, 1 + q^−1 times the fraction of LCD codes. A polynomial-time reduction algorithm is given.
ER -