pith. sign in

arxiv: 2604.26397 · v1 · submitted 2026-04-29 · 💻 cs.IT · math.IT

Existence and Constructions of Strict Function-Correcting Codes with Data Protection

Charul Rajput , B. Sundar Rajan , Ragnar Freij-Hollanti , Camilla Hollanti This is my paper

Pith reviewed 2026-05-07 12:58 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords strict function-correcting codesdata protectionlinear codesCayley graphsBCH codeschain codesalpha-distance grapherror correction
0
0 comments X

The pith

Linear codes serve as strict function-correcting codes when minimum-weight codewords generate only a proper subcode.

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

The paper shows that a code can act as a strict function-correcting code with data protection—correcting errors in a function of the data at a higher level than in the data itself—if its alpha-distance graph meets a specific connectivity condition. For linear codes this graph is always a Cayley graph whose connected components are exactly the cosets of the subcode spanned by low-weight codewords, turning the existence question into one of whether that subcode is proper. The authors give a converse construction to Simonis’s theorem that produces equivalent codes with fewer independent minimum-weight generators whenever the weight distribution permits it, introduce the infinite family of chain codes as examples, and prove that narrow-sense BCH codes with designed distance three satisfy the condition because their minimum-weight words lie inside a proper subcode. This matters because perfect and MDS codes were already ruled out, so these results identify and construct the first infinite families that can deliver differentiated protection levels.

Core claim

A linear code is a strict function-correcting code with data protection precisely when the subcode generated by its minimum-weight codewords is proper. This equivalence follows from the fact that the code’s alpha-distance graph is isomorphic to a Cayley graph whose connected components are the cosets of that subcode. The property holds for the infinite family of chain codes, which are generated by their minimum-weight words, and for narrow-sense BCH codes of designed distance three, whose minimum-weight codewords are contained in a proper subcode.

What carries the argument

The alpha-distance graph of the code, which for linear codes is isomorphic to a Cayley graph whose connected components are the cosets of the subcode generated by low-weight codewords.

If this is right

  • Existence of strict function-correcting codes with data protection reduces to finding linear codes whose minimum-weight codewords span a proper subcode.
  • Chain codes supply an infinite family of linear codes that meet the condition directly.
  • Narrow-sense BCH codes with designed distance three can be used immediately as strict function-correcting codes.
  • Any linear code whose weight distribution allows the converse-Simonis transformation yields a strict function-correcting code.

Where Pith is reading between the lines

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

  • The Cayley-graph view may permit group-theoretic decoding algorithms for these codes.
  • Weight distributions of other linear families such as Reed-Muller codes could be checked to produce additional examples.
  • The same graph condition might be adapted to construct strict function-correcting codes over nonlinear or non-Hamming metrics.

Load-bearing premise

The weight distribution of a linear code permits a transformation into an equivalent code whose minimum-weight codewords span only a proper subcode, or the minimum-weight codewords of narrow-sense BCH codes with designed distance three lie inside such a proper subcode.

What would settle it

A narrow-sense BCH code with designed distance three whose minimum-weight codewords generate the entire code space would show that the BCH construction fails.

Figures

Figures reproduced from arXiv: 2604.26397 by B. Sundar Rajan, Camilla Hollanti, Charul Rajput, Ragnar Freij-Hollanti.

Figure 1
Figure 1. Figure 1: The α-distance graph G2(C) for Example 1. Definition 2 (Strict FCC [3]). An (f : dd, df)-FCC is called strict if df > dd. Remark 1. In the original FCC framework of [1], only systematic codes are considered. This is because if non￾systematic codes are allowed, multiple messages with the same function value could be mapped to the same codeword, making them indistinguishable at the decoder. In contrast, for … view at source ↗
Figure 2
Figure 2. Figure 2: The Cayley graph Cay(Z4, {1, 3}) for Example 2. Definition 4 (Cayley Graph). Let G be a group with identity element e, and let S ⊆ G \ {e} be a subset that is closed under taking inverses. The Cayley graph of G with respect to S , denoted by Cay(G, S ), is the undirected graph with vertex set G in which two vertices g, h ∈ G are adjacent if and only if g − h ∈ S . The following property of Cayley graphs is… view at source ↗
Figure 3
Figure 3. Figure 3: The distance graph G4(C) for Example 3. Example 3. Consider the code C = {000000000, 100110110, 010101110, 001011110, 110011101, 101101101, 011110101, 111000011} ⊆ F 9 2 with minimum distance dd = 4. The α-distance graph G4(C) has four connected components: S1 = {000000000}, S2 = {100110110, 010101110, 001011110}, S3 = {110011101, 101101101, 011110101}, S4 = {111000011}, as shown in view at source ↗
Figure 4
Figure 4. Figure 4: The distance graph G2(C) for Example 4. 0000 1100 2200 C0 0111 1211 2011 C1 0222 1022 2122 C2 view at source ↗
Figure 5
Figure 5. Figure 5: The distance graph G2(C) for Example 5. Example 5. Let q = 3, n = 4, and let C ⊆ F 4 3 be the linear code generated by g1 = (1, 1, 0, 0) and g2 = (0, 1, 1, 1). Then C = ⟨g1, g2⟩ = {ag1 + bg2 : a, b ∈ F3} = {(a, a + b, b, b) : a, b ∈ F3}, so |C| = 9 and dmin(C) = 2. For α = 2, we have S 2 = {(1, 1, 0, 0), (2, 2, 0, 0)} and ⟨S 2⟩ = {(0, 0, 0, 0), (1, 1, 0, 0), (2, 2, 0, 0)}. The three cosets of ⟨S 2⟩ in C ar… view at source ↗
read the original abstract

Function-correcting codes with data protection simultaneously protect both the data and a function of the data at distinct error-correction levels. When the function receives strictly stronger protection than the data, such a code is called a strict function-correcting code with data protection. While prior work showed that perfect and MDS codes cannot serve as strict function-correcting codes, which codes can serve this role, and how to construct them, has remained open. In this paper, we address the existence and construction of strict function-correcting codes for linear codes through three main contributions. First, using the $\alpha$-distance graph framework from our prior work, we establish a graph-theoretic existence condition under which a code can serve as a strict function-correcting code. For linear codes, we prove this distance graph is isomorphic to a Cayley graph, which implies the connected components are cosets of the subcode generated by low-weight codewords. This transforms the existence problem into a subcode generation problem. Second, a classical result of Simonis shows any linear code can be transformed into one with the same parameters whose basis consists entirely of minimum-weight codewords. We develop a converse construction: under certain conditions on the weight distribution, a linear code can be transformed into a new code with the same parameters but fewer independent minimum-weight codewords, thereby producing codes suitable for use as strict function-correcting codes. As a source of codes satisfying these conditions, we introduce chain codes, an infinite family of linear codes generated by their minimum-weight codewords. Third, we present an independent construction of strict function-correcting codes from narrow-sense BCH codes with designed distance three, by proving the minimum-weight codewords of such codes are contained in a proper subcode.

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

1 major / 2 minor

Summary. The paper claims to address the open question of which linear codes can serve as strict function-correcting codes with data protection and how to construct them. Using the authors' prior α-distance graph framework, it establishes a graph-theoretic existence condition; for linear codes this graph is shown to be isomorphic to a Cayley graph whose connected components are cosets of the subcode generated by low-weight codewords. It develops a converse to Simonis' theorem allowing transformation of a linear code (under suitable weight-distribution conditions) into an equivalent code with fewer independent minimum-weight codewords, and introduces chain codes as an infinite family satisfying the conditions. As a third contribution, it claims an independent construction from narrow-sense BCH codes of designed distance three by proving that their minimum-weight codewords lie in a proper subcode.

Significance. If the graph-theoretic existence condition and the chain-code constructions hold, the work would provide a useful criterion for identifying suitable codes and an explicit infinite family, advancing the theory of codes that protect both data and functions at unequal error-correction levels. The introduction of chain codes generated by their minimum-weight words is a concrete strength that could be of independent interest. The BCH construction, however, does not hold, which reduces the overall significance unless that part is removed or corrected.

major comments (1)
  1. [Abstract (third main contribution)] Abstract (third main contribution): The claim that the minimum-weight codewords of narrow-sense BCH codes with designed distance three are contained in a proper subcode is false. The binary narrow-sense BCH code with designed distance 3 is the [7,4,3] Hamming code, which contains exactly 7 weight-3 codewords, all of odd weight. The even-weight subcode is a proper subspace of dimension 3. Any subspace of dimension at most 3 contains at most 4 odd-weight vectors, but 7 > 4, so the 7 weight-3 codewords cannot lie in any proper subcode and must span the full 4-dimensional code. This directly falsifies the BCH construction.
minor comments (2)
  1. [Section on the converse construction] The precise weight-distribution conditions required for the converse-to-Simonis transformation are stated only at a high level; a formal statement of the necessary and sufficient conditions on the weight enumerator would improve clarity.
  2. [Section introducing chain codes] Chain codes are introduced as a new family; a small explicit example (e.g., the smallest chain code and its generator matrix) would help readers verify the claimed properties.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying an error in the claimed BCH construction. We address this point directly below and describe the revisions that will be made.

read point-by-point responses

  1. Referee: The claim that the minimum-weight codewords of narrow-sense BCH codes with designed distance three are contained in a proper subcode is false. The binary narrow-sense BCH code with designed distance 3 is the [7,4,3] Hamming code, which contains exactly 7 weight-3 codewords, all of odd weight. The even-weight subcode is a proper subspace of dimension 3. Any subspace of dimension at most 3 contains at most 4 odd-weight vectors, but 7 > 4, so the 7 weight-3 codewords cannot lie in any proper subcode and must span the full 4-dimensional code. This directly falsifies the BCH construction.

    Authors: We acknowledge the referee's counterexample with the [7,4,3] Hamming code. The argument presented in the manuscript for narrow-sense BCH codes of designed distance three is incorrect, as the seven weight-3 codewords span the full code and cannot be contained in any proper subcode. We will remove the third main contribution from the abstract, delete the corresponding section on the BCH construction, and revise the introduction and conclusion to reflect that the paper now focuses on the graph-theoretic existence condition and the chain-code family. These two contributions are unaffected by the error. revision: yes

Circularity Check

0 steps flagged

Minor self-citation of prior α-distance graph framework; all three central derivations remain independent of fitted inputs or self-definition

full rationale

The paper invokes its own prior α-distance graph framework only as a starting point for a new graph-theoretic existence condition and a Cayley-graph isomorphism proof for linear codes. These steps produce an original reduction of the problem to subcode generation. The converse-to-Simonis construction, the definition of chain codes, and the BCH subcode-containment argument are each developed from classical external results (Simonis) or direct weight-distribution analysis inside the paper; none of the claimed existence or construction results is obtained by renaming a fitted parameter or by a self-citation chain that itself assumes the target statement. The self-citation is therefore non-load-bearing and does not trigger any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the isomorphism of the alpha-distance graph to a Cayley graph (standard linear-algebra fact) and on the existence of codes whose minimum-weight vectors span a proper subcode; chain codes are introduced as a new family without external verification.

axioms (1)
  • standard math Any linear code can be transformed into one with the same parameters whose basis consists entirely of minimum-weight codewords (Simonis theorem)
    Invoked to develop the converse construction that reduces the number of independent minimum-weight codewords.
invented entities (1)
  • chain codes no independent evidence
    purpose: Infinite family of linear codes generated by their minimum-weight codewords that satisfy the proper-subcode condition for strict function-correcting codes
    Newly defined in the paper as a source of codes meeting the weight-distribution requirements.

pith-pipeline@v0.9.0 · 5628 in / 1515 out tokens · 155714 ms · 2026-05-07T12:58:02.303347+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

21 extracted references · 10 canonical work pages · 2 internal anchors

  1. [1]

    Function-correcting codes,

    A. Lenz, R. Bitar, A. Wachter-Zeh, and E. Yaakobi, “Function-correcting codes,”IEEE Trans. Inf. Theory, vol. 69, no. 9, pp. 5604–5618, Sep. 2023

    2023

  2. [2]

    Function- correcting codes with data protection,

    C. Rajput, B. S. Rajan, R. Freij-Hollanti, and C. Hollanti, “Function-correcting codes with data protection,” accepted for presentation inProc. IEEE Int. Symp. Inf. Theory (ISIT), 2026. An extended version has been accepted for publication inIEEE Trans. Inf. Theory. Available: arXiv:2511.18420

    work page internal anchor Pith review arXiv 2026

  3. [3]

    Non-existence of some function-correcting codes with data protection,

    C. Rajput, B. S. Rajan, R. Freij-Hollanti, and C. Hollanti, “Non-existence of some function-correcting codes with data protection,” accepted for presentation inProc. IEEE Int. Symp. Inf. Theory (ISIT), 2026. Available: arXiv:2603.01049

    work page arXiv 2026

  4. [4]

    On function-correcting codes,

    R. Premlal and B. S. Rajan, “On function-correcting codes,”IEEE Trans. Inf. Theory, vol. 71, no. 8, pp. 5884–5897, Aug. 2025

    2025

  5. [5]

    Optimal redundancy of function-correcting codes,

    G. Ge, Z. Xu, X. Zhang, and Y . Zhang, “Optimal redundancy of function-correcting codes,”IEEE Trans. Inf. Theory, vol. 71, no. 12, pp. 9458–9467, Dec. 2025

    2025

  6. [6]

    On the redundancy of function-correcting codes over finite fields,

    H. Ly and E. Soljanin, “On the redundancy of function-correcting codes over finite fields,” inProc. 13th Int. Symp. Topics in Coding (ISTC), Los Angeles, CA, USA, 2025

    2025

  7. [7]

    Function-correcting codes for symbol-pair read channels,

    Q. Xia, H. Liu, and B. Chen, “Function-correcting codes for symbol-pair read channels,”IEEE Trans. Inf. Theory, vol. 70, no. 11, pp. 7807–7819, Nov. 2024

    2024

  8. [8]

    Function-correcting codes for b-symbol read channels,

    A. Singh, A. K. Singh, and E. Yaakobi, “Function-correcting codes forb-symbol read channels,”arXiv preprint arXiv:2503.12894, Mar. 2025

    work page arXiv 2025

  9. [9]

    A Note on Function Correcting Codes for b-Symbol Read Channels,

    S. Sampath and B. S. Rajan, “A note on function correcting codes forb-symbol read channels,”arXiv preprint arXiv:2503.23059, Mar. 2025

    work page arXiv 2025

  10. [10]

    On Function-Correcting Codes in the Lee Metric,

    G. K. Verma and A. K. Singh, “On function-correcting codes in the Lee metric,”arXiv preprint arXiv:2507.17654, Jul. 2025

    work page arXiv 2025

  11. [11]

    Plotkin-like Bound and Explicit Function-Correcting Code Constructions for Lee Metric Channels

    H. K. Hareesh, R. Ummer N. T., and B. S. Rajan, “Plotkin-like bound and explicit function-correcting code constructions for Lee metric channels,”arXiv preprint arXiv:2508.01702, Aug. 2025. April 30, 2026 DRAFT 22

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  12. [12]

    Function-Correcting Codes with Homogeneous Distance,

    H. Liu and H. Liu, “Function-correcting codes with homogeneous distance,”arXiv preprint arXiv:2507.03332, Jul. 2025

    work page arXiv 2025

  13. [13]

    Function-correcting codes for locally bounded functions,

    C. Rajput, B. S. Rajan, R. Freij-Hollanti, and C. Hollanti, “Function-correcting codes for locally bounded functions,” inProc. IEEE Inf. Theory Workshop (ITW), Sydney, Australia, 2025, pp. 851–856

    2025

  14. [14]

    Function-correcting partition codes,

    C. Rajput, B. S. Rajan, R. Freij-Hollanti, and C. Hollanti, “Function-correcting partition codes,”arXiv preprint arXiv:2601.06450, Jan. 2026

    work page arXiv 2026

  15. [15]

    Function-Correcting Codes with Optimal Data Protection for Hamming Code Membership

    S. S. Durgi, A. A. Mahesh, A. Kumari, R. Pandey, and B. S. Rajan, “Function-correcting codes with optimal data protection for Hamming code membership,” accepted for presentation inProc. IEEE Int. Symp. Inf. Theory (ISIT), 2026. Available: arXiv:2602.21932

    work page arXiv 2026

  16. [16]

    Function correcting codes for maximally-unbalanced Boolean functions,

    R. Pandey, S. Bajpai, A. A. Mahesh, and B. S. Rajan, “Function correcting codes for maximally-unbalanced Boolean functions,” accepted for presentation inProc. IEEE Int. Symp. Inf. Theory (ISIT), 2026. Available: arXiv:2601.10135

    work page arXiv 2026

  17. [17]

    On generator matrices of codes,

    J. Simonis, “On generator matrices of codes,”IEEE Trans. Inf. Theory, vol. 38, no. 2, pp. 516–516, Mar. 1992

    1992

  18. [18]

    On bases of BCH codes with designed distance 3 and their extensions,

    I. Yu. Mogilnykh and F. I. Solov’eva, “On bases of BCH codes with designed distance 3 and their extensions,”Problems Inf. Transm., vol. 56, no. 4, pp. 309–316, 2020

    2020

  19. [19]

    On the minimum distances of non-binary cyclic codes,

    P. Charpin, A. Tiet ¨av¨ainen, and V . Zinoviev, “On the minimum distances of non-binary cyclic codes,”Des. Codes Cryptogr., vol. 17, no. 1–3, pp. 81–85, 1999

    1999

  20. [20]

    Some properties of unitary Cayley graphs,

    W. Klotz and T. Sander, “Some properties of unitary Cayley graphs,”Electron. J. Combin., vol. 14, R45, 2007

    2007

  21. [21]

    Function-correcting codes for (λ, ρ,b)-functions,

    G. K. Verma, A. Singh, and A. K. Singh, “Function-correcting codes for (λ, ρ,b)-functions,”IEEE Trans. Inf. Theory, vol. 72, no. 1, pp. 331–341, Jan. 2026. April 30, 2026 DRAFT

    2026