Bilinear Hulls for Support Splitting: Characterization, Optimization, and Applications

Abstract

Sendrier's Support Splitting Algorithm (SSA) is the standard solver for the Permutation Equivalence Problem (PEP); its cost is dominated by a term that grows exponentially in the hull dimension. We study, mathematically, how much this cost can be lowered by replacing the standard inner product, on which the hull is defined, with an alternative bilinear form. Two structural results give a complete answer: only a narrow two-parameter family of bilinear forms produces a hull on which SSA can still operate, namely those whose matrix in the standard basis is a linear combination of the identity and the all-ones matrix; and even within this family the hull dimension drops by at most one (with the reduction achieved on every self-dual code whose length is coprime to the field characteristic). Together, these results give a tight upper bound: since SSA on a code with hull dimension h has cost dominated by q^h, replacing the standard hull with Hull_M lowers this dominant term from q^h to at best q^h−1, so no bilinear-form generalization of the inner product can reduce the SSA cost by more than a factor of q, the field size. Going beyond this requires invariants outside the bilinear framework. As an application, we verify that PEP-based SPECK admits the factor-q cost reduction, while LEP-based LESS and PKP-based PERK lie outside our framework. A SageMath implementation of the bilinear-hull preprocessing confirms feasibility at SPECK's recommended length n = 252.

Bilinear generating functions of the multivariable Al-Salam-Carlitz polynomials and applications
Qi Chen, Xinrong Ma, Jin Wang
arXiv30 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Forest Characterization of When SDP-RLT Strengthens RLT for Bilinear Terms
Hayato Watanabe, Takami Sato, Kazuhide Nakata +1
arXiv20 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
On the stability of eigenvalues of varying bilinear forms in abstract Hilbertian settings and applications
Andrea Bisterzo, Roberto Ognibene, Prasun Roychowdhury +1
arXiv9 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
Failure of the H¹× H¹⟶ L^1/2,∞ estimate for the lacunary bilinear spherical maximal function and applications
Sanghyuk Lee, Ji Li, Chaojie Wen +1
arXiv29 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
Sliding Methods for Hölder-Smooth Convex--Concave Minimax Optimization with Bilinear Coupling
Nhat Trung Nguyen, Alexander Gasnikov
arXiv8 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{aikawa2026bilinear,
  title = {{Bilinear Hulls for Support Splitting: Characterization, Optimization, and Applications}},
  author = {Yusuke Aikawa and Keita Ishizuka and Tomoki Moriya},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.01337},
  eprint = {2611.01337},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01337},
}

RIS

TY  - UNPB
TI  - Bilinear Hulls for Support Splitting: Characterization, Optimization, and Applications
AU  - Yusuke Aikawa
AU  - Keita Ishizuka
AU  - Tomoki Moriya
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.01337
UR  - https://arxiv.org/abs/2611.01337
AB  - Sendrier's Support Splitting Algorithm (SSA) is the standard solver for the Permutation Equivalence Problem (PEP); its cost is dominated by a term that grows exponentially in the hull dimension. We study, mathematically, how much this cost can be lowered by replacing the standard inner product, on which the hull is defined, with an alternative bilinear form. Two structural results give a complete answer: only a narrow two-parameter family of bilinear forms produces a hull on which SSA can still operate, namely those whose matrix in the standard basis is a linear combination of the identity and the all-ones matrix; and even within this family the hull dimension drops by at most one (with the reduction achieved on every self-dual code whose length is coprime to the field characteristic). Together, these results give a tight upper bound: since SSA on a code with hull dimension h has cost dominated by q^h, replacing the standard hull with Hull_M lowers this dominant term from q^h to at best q^h−1, so no bilinear-form generalization of the inner product can reduce the SSA cost by more than a factor of q, the field size. Going beyond this requires invariants outside the bilinear framework. As an application, we verify that PEP-based SPECK admits the factor-q cost reduction, while LEP-based LESS and PKP-based PERK lie outside our framework. A SageMath implementation of the bilinear-hull preprocessing confirms feasibility at SPECK's recommended length n = 252.
ER  -

Abstract

Related

Cite