pith. sign in

arxiv: 2605.23120 · v1 · pith:DXU3X5WTnew · submitted 2026-05-22 · 💻 cs.IT · math.CO· math.IT

The Closure of LCD-to-GI Reductions via Generalized Inner Products

Keita Ishizuka This is my paper

Pith reviewed 2026-05-25 03:54 UTC · model grok-4.3

classification 💻 cs.IT math.COmath.IT
keywords permutation equivalencelinear codesgraph isomorphismLCD codeshull dimensionbilinear formsorthogonal projectors
0
0 comments X

The pith

The orthogonal projector reduction from code permutation equivalence to graph isomorphism works exactly for codes with hull dimension at most one under bilinear forms of the form aI + bJ.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper determines the precise limits of a known technique that turns the permutation equivalence problem for linear codes into an instance of graph isomorphism. It extends the method from the trivial-hull case to all codes whose hull has dimension at most one, but only when the underlying bilinear form is of type aI + bJ; no other nondegenerate symmetric form produces a valid reduction. In characteristic two the condition collapses to the LCD property alone. The result supplies exact counting formulas obtained from character sums and includes a polynomial-time algorithm that performs the reduction whenever the hull condition holds.

Core claim

We prove that this approach extends to bilinear forms M = aI + bJ, and that no other nondegenerate symmetric form yields a valid reduction. A code is reducible if and only if its hull dimension is at most 1 with an explicit condition on the hull vector; in characteristic 2, only LCD codes are reducible. This establishes the closure of the orthogonal projector method. We derive exact enumeration formulas via character sums over quadratic forms and provide a polynomial-time reduction algorithm.

What carries the argument

The bilinear forms M = aI + bJ together with the hull-dimension-at-most-1 condition that together decide whether an orthogonal projector produces a faithful reduction to graph isomorphism.

If this is right

  • The permutation equivalence problem for any code meeting the hull condition reduces in polynomial time to graph isomorphism.
  • In fields of characteristic two the reduction applies only to LCD codes.
  • The number of reducible codes admits an exact formula obtained by summing characters over quadratic forms.
  • A polynomial-time algorithm implements the reduction whenever the hull condition is satisfied.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Codes whose hull dimension exceeds one will require entirely different techniques if their permutation equivalence problem is to be reduced to graph isomorphism.
  • The explicit condition on the hull vector supplies a practical test that can classify codes as easy or hard for equivalence checking.
  • Enumeration formulas derived from the character-sum approach may be combined with existing code-counting methods to study isomorphism classes in larger families.

Load-bearing premise

Extending the orthogonal-projector construction from the trivial-hull case to forms M = aI + bJ preserves the exact one-to-one correspondence between code permutations and graph automorphisms.

What would settle it

Exhibiting either a code whose hull dimension exceeds one that nevertheless reduces to graph isomorphism via some symmetric bilinear form, or a nondegenerate symmetric form outside the aI + bJ family that yields a valid reduction for any code.

read the original abstract

The Permutation Equivalence Problem (PEP) for linear codes is a fundamental problem in coding theory and cryptography. A recent reduction shows that PEP for Linear Complementary Dual (LCD) codes reduces to Graph Isomorphism (GI) via orthogonal projectors, but is restricted to codes with trivial hull. We prove that this approach extends to bilinear forms $M = aI + bJ$, and that no other nondegenerate symmetric form yields a valid reduction. A code is reducible if and only if its hull dimension is at most $1$ with an explicit condition on the hull vector; in characteristic $2$, only LCD codes are reducible. This establishes the closure of the orthogonal projector method. We derive exact enumeration formulas via character sums over quadratic forms and provide a polynomial-time reduction algorithm.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper claims to close the LCD-to-GI reduction for the Permutation Equivalence Problem by extending the orthogonal-projector construction from trivial-hull LCD codes to bilinear forms M = aI + bJ. It proves that a code is reducible if and only if its hull dimension is at most 1 (with an explicit condition on the hull vector), that only LCD codes are reducible in characteristic 2, derives exact enumeration formulas via character sums over quadratic forms, and supplies a polynomial-time algorithm realizing the reduction.

Significance. If the central claims hold, the work provides a precise characterization of when the orthogonal-projector method yields a valid PEP-to-GI reduction, together with closed-form enumerations and an explicit algorithm. The character-sum derivations constitute an independent combinatorial contribution that strengthens the result beyond the reduction itself.

minor comments (3)
  1. [§3] §3: the statement of the hull-vector condition is given after the iff theorem; moving the explicit vector condition to the statement of Theorem 3.2 would improve readability.
  2. [§5] The character-sum enumeration in §5 is presented without a short sanity-check computation for small parameters (e.g., n=4, q=2); adding one would help verify the formulas.
  3. [§6] Notation for the generalized inner product induced by M is introduced in §2 but reused without re-statement in the algorithm of §6; a one-sentence reminder would prevent ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work on the closure of the LCD-to-GI reduction via generalized inner products, including the characterization of reducible codes, the restriction to LCD codes in characteristic 2, the character-sum enumerations, and the polynomial-time algorithm. The recommendation for minor revision is noted, and we will incorporate any editorial suggestions in the revised manuscript.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The manuscript establishes its central claims through explicit mathematical proofs: an extension of the orthogonal-projector construction to forms M = aI + bJ, an iff characterization of reducible codes via hull dimension ≤1 with a hull-vector condition, necessity arguments for this restriction, character-sum enumeration formulas over quadratic forms, and a polynomial-time algorithm. These derivations are self-contained and rely on independent algebraic and combinatorial techniques rather than parameter fitting, self-definitional reductions, or load-bearing self-citations. No step reduces by construction to its own inputs or prior author work in a circular manner.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The abstract indicates reliance on standard linear-algebra facts about symmetric bilinear forms and orthogonal projectors; no free parameters, invented entities, or ad-hoc axioms are visible.

axioms (2)
  • standard math Standard properties of nondegenerate symmetric bilinear forms over finite fields
    Invoked to define the generalized inner products that extend the projector construction.
  • domain assumption Existence and basic properties of orthogonal projectors compatible with the bilinear form
    Required for the reduction from code permutations to graph automorphisms to remain valid.

pith-pipeline@v0.9.0 · 5657 in / 1442 out tokens · 34625 ms · 2026-05-25T03:54:51.033389+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [1]

    L. Babai. Graph isomorphism in quasipolynomial time. InProceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 684–697. ACM, 2016

    work page 2016

  2. [2]

    Baldi, M

    M. Baldi, M. Battagliola, R. El Mechri, P. Santini, R. Schiavoni, and D. De Zuane. SPECK: Signatures from permutation equivalence of codes and kernels. Cryptology ePrint Archive, Paper 2025/923, 2025

    work page 2025

  3. [3]

    Bardet, A

    M. Bardet, A. Otmani, and M. Saeed-Taha. Permutation code equiv- alence is not harder than graph isomorphism when hulls are trivial. InIEEE International Symposium on Information Theory, ISIT 2019, pages 2464–2468. IEEE, 2019

    work page 2019

  4. [4]

    Biasse, G

    J.-F. Biasse, G. Micheli, E. Persichetti, and P. Santini. LESS is More: Code-based signatures without syndromes. InProgress in Cryptology – AFRICACRYPT 2020, pages 45–65. Springer, 2020

    work page 2020

  5. [5]

    Carlet, S

    C. Carlet, S. Mesnager, C. Tang, and Y. Qi. New characterization and parametrization of LCD codes.IEEE Trans. Inf. Theory, 65(1):39–49, 2019

    work page 2019

  6. [6]

    Ishizuka

    K. Ishizuka. Poster: Reducing hull dimensions for efficient permutation recovery in code-based cryptography. InProceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security (CCS 2025), pages 4812–4814. ACM, 2025

    work page 2025

  7. [7]

    S. Li, M. Shi, and S. Ling. A mass formula for linear codes with pre- scribed hull dimension and related classification.IEEE Trans. Inf. The- ory, 71(1):273–286, 2025

    work page 2025

  8. [8]

    Lidl and H

    R. Lidl and H. Niederreiter.Finite Fields. Cambridge University Press, second edition, 1997. 25

    work page 1997

  9. [9]

    J. L. Massey. Linear codes with complementary duals.Discrete Math., 106–107:337–342, 1992

    work page 1992

  10. [10]

    Petrank and R

    E. Petrank and R. M. Roth. Is code equivalence easy to decide?IEEE Trans. Inf. Theory, 43(5):1602–1604, 1997

    work page 1997

  11. [11]

    Sendrier

    N. Sendrier. Finding the permutation between equivalent linear codes: The support splitting algorithm.IEEE Trans. Inf. Theory, 46(4):1193– 1203, 2000

    work page 2000

  12. [12]

    D. E. Taylor.The Geometry of the Classical Groups, volume 9 ofSigma Series in Pure Mathematics. Heldermann Verlag, Berlin, 1992

    work page 1992

  13. [13]

    Weyl.The Classical Groups: Their Invariants and Representations

    H. Weyl.The Classical Groups: Their Invariants and Representations. Princeton University Press, 1939. Reprinted 2016. 26

    work page 1939