arxiv: 2605.14023 · v1 · submitted 2026-05-13 · 💻 cs.IT · math.IT

Recognition: 2 theorem links

· Lean Theorem

Function-Correction with Optimal Data Protection for the General Hamming Code Membership

Adityawardhan Yadava , Anjana A. Mahesh , Swaraj Sharma Durgi

Authors on Pith no claims yet

Pith reviewed 2026-05-15 02:11 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords function-correcting codesHamming codeSEFCCbent functionsWalsh transformmax-cutparity assignmenterror correction

0 comments

The pith

Bent Boolean functions deliver optimal parity assignments for single-error-correcting function-correcting codes on the general Hamming code membership function when the length parameter is even.

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

The paper establishes necessary and sufficient conditions for valid parity assignments that turn the Hamming code membership function into a single-error-correcting function-correcting code. It proves that the distance-3 codeword graph is connected and bipartite for every n at least 2, allowing a systematic construction that reaches the largest possible minimum distance of 2. The design problem of minimizing distance-2 pairs is reduced to a max-cut task on two distance-4 graphs; the eigenvectors for the smallest eigenvalue of these graphs directly supply the best parity vectors. For even n the eigenvector search is recast as moment optimization over Walsh coefficients of an auxiliary function, and a tight lower bound is proved that is achieved exactly by bent functions.

Core claim

Eigenvectors corresponding to the minimum eigenvalue of the distance-4 graphs on the two partite sets yield optimal parity assignments. The search for these eigenvectors reduces to an optimization problem over moments of the Walsh coefficients of a related Boolean function; for even n a tight lower bound on this optimization is attained precisely by bent functions, thereby establishing a direct link between optimal SEFCC design and bent Boolean functions.

What carries the argument

The bipartite structure of the distance-3 codeword graph together with the max-cut formulation on the induced distance-4 graphs, whose minimum-eigenvalue eigenvectors are obtained via Walsh-moment optimization attained by bent functions.

If this is right

A systematic construction produces SEFCCs with minimum distance exactly 2 for every n greater than or equal to 2.
For even n the optimal assignments are given by the support patterns of bent functions.
Known families of bent functions immediately supply explicit optimal parity vectors.
The Walsh-transform formulation allows the same optimality criterion to be checked for any candidate Boolean function.

Where Pith is reading between the lines

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

The same graph-theoretic reduction may apply to membership functions of other linear codes whose distance-3 graphs are bipartite.
Constructions of bent functions in higher dimensions would directly enlarge the set of optimal SEFCCs.
Numerical checks of the Walsh-moment bound for small even n could be performed by enumerating known bent functions.

Load-bearing premise

The distance-3 codeword graph forms a connected bipartite graph for every n at least 2.

What would settle it

An explicit parity assignment for even n that produces strictly fewer distance-2 codeword pairs than the number achieved by any bent function, or a proof that bent functions cannot attain the derived lower bound on the Walsh-moment objective.

read the original abstract

This paper investigates single-error-correcting function-correcting codes~(SEFCCs) for the $[2^n-1,\,2^n-1-n,\,3]$-Hamming code membership function~(HCMF) for general $n\geq 2$. Necessary and sufficient conditions for valid parity assignments are established, and the distance-$3$ codeword graph is shown to induce a connected bipartite structure for all $n\geq 2$, which is exploited to develop a systematic SEFCC construction achieving the largest possible minimum distance of~$2$. A novel framework is then developed that reduces the minimization of distance-$2$ codeword pairs to a max-cut problem on the distance-$4$ graphs of the two partite sets. Eigenvectors corresponding to the minimum eigenvalue of these graphs are shown to directly yield optimal parity assignments. We reduce the problem of finding these eigenvectors to an optimization problem involving moments of the Walsh coefficients of a related function, which we solve for even~$n$ by deriving a tight lower bound shown to be attained by bent functions, establishing a precise connection between optimal SEFCC design and bent Boolean functions.

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.

Desk Editor's Note private letter to a colleague

The paper gives a clean reduction of optimal parity design for Hamming membership SEFCCs to max-cut on distance-4 graphs and then to bent functions for even n, but the result stays narrow.

read the letter

The core contribution is a systematic construction for single-error-correcting function-correcting codes on the general Hamming membership function that reaches the largest possible minimum distance of 2. It starts from the distance-3 codeword graph, shows this graph is connected and bipartite for n at least 2, and uses that structure to build the codes explicitly. For even n it further reduces the search for optimal parity vectors to a max-cut problem on the induced distance-4 graphs, solves it via minimum-eigenvalue eigenvectors, and recasts the eigenvector search as a moment optimization over Walsh coefficients whose lower bound is achieved exactly by bent functions. That last link is the freshest part; it is not a routine extension of earlier Hamming-code work and gives a concrete spectral connection between the two areas. The bipartite-structure argument and the max-cut framing look solid on the abstract and stress-test description, and the steps cited are standard tools in coding theory and spectral graph theory. The main soft spot is that the tightness claim for bent functions rests on the lower bound being independent of the flat-spectrum definition; without the full derivations it is hard to confirm there is no hidden circularity, though the stress-test indicates the bound is derived separately. The paper is quite specialized, so its audience is limited to researchers already working on function-correcting codes or on explicit constructions that mix coding theory with Boolean-function spectra. A reader in that niche will find the explicit reduction and the bent-function attainment useful to check or extend. It is worth sending to peer review because the framework is concrete enough for referees to verify the steps and assess whether the connection holds up in the proofs.

Referee Report

2 major / 2 minor

Summary. The manuscript investigates single-error-correcting function-correcting codes (SEFCCs) for the [2^n-1, 2^n-1-n, 3]-Hamming code membership function for general n ≥ 2. It establishes necessary and sufficient conditions for valid parity assignments, proves that the distance-3 codeword graph is connected and bipartite, constructs systematic SEFCCs achieving the maximum possible minimum distance of 2, reduces minimization of distance-2 codeword pairs to a max-cut problem on the induced distance-4 graphs, shows that minimum-eigenvalue eigenvectors yield optimal parity assignments, and reduces the eigenvector problem to moment optimization over Walsh coefficients of a related Boolean function. For even n the optimization is solved by deriving a tight lower bound attained precisely by bent functions, thereby linking optimal SEFCC design to the spectral properties of bent Boolean functions.

Significance. If the derivations hold, the paper supplies a concrete and systematic construction for SEFCCs on the Hamming membership function together with a precise spectral characterization that ties optimal parity assignment to bent functions. The graph-theoretic reductions (bipartite structure, max-cut formulation, eigenvector extraction) and the explicit attainment result for even n constitute the main technical contributions; they offer a reusable template for applying spectral graph theory and Walsh analysis to function-correction problems.

major comments (2)

[Section 5 (Walsh-moment optimization)] The central optimality claim rests on the assertion that the derived lower bound on the Walsh-moment objective is attained if and only if the underlying function is bent. The abstract outlines the reduction but does not exhibit the explicit equality case analysis or error-term control that would confirm the bound is achieved precisely when the Walsh spectrum is flat; this verification is load-bearing for the claimed connection to bent functions and must be supplied in full.
[Section 3 (graph structure)] The proof that the distance-3 codeword graph is connected and bipartite for every n ≥ 2 is invoked to justify the systematic construction and the subsequent max-cut reduction. While the abstract states the structural property, the manuscript must include an explicit inductive or combinatorial argument together with verification for small even and odd n to ensure the bipartition is well-defined and the max-cut formulation is valid without additional assumptions.

minor comments (2)

Notation for the parity-assignment vector and the two partite sets should be introduced once and used consistently; several passages reuse the same symbol for distinct objects.
[Abstract] The abstract claims the construction achieves the largest possible minimum distance of 2; a short remark clarifying why distance 3 is impossible under the single-error-correction constraint would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments highlight areas where additional explicit detail will strengthen the manuscript. We address each major comment below and will revise the paper accordingly.

read point-by-point responses

Referee: [Section 5 (Walsh-moment optimization)] The central optimality claim rests on the assertion that the derived lower bound on the Walsh-moment objective is attained if and only if the underlying function is bent. The abstract outlines the reduction but does not exhibit the explicit equality case analysis or error-term control that would confirm the bound is achieved precisely when the Walsh spectrum is flat; this verification is load-bearing for the claimed connection to bent functions and must be supplied in full.

Authors: We agree that the equality case requires explicit verification to fully support the claimed connection to bent functions. In the revised manuscript we will add a complete proof of the equality case for the Walsh-moment lower bound, including explicit error-term control and a demonstration that equality holds if and only if the Walsh spectrum is flat (i.e., precisely when the function is bent). revision: yes
Referee: [Section 3 (graph structure)] The proof that the distance-3 codeword graph is connected and bipartite for every n ≥ 2 is invoked to justify the systematic construction and the subsequent max-cut reduction. While the abstract states the structural property, the manuscript must include an explicit inductive or combinatorial argument together with verification for small even and odd n to ensure the bipartition is well-defined and the max-cut formulation is valid without additional assumptions.

Authors: We acknowledge that the current text states the connectedness and bipartiteness without a fully expanded argument. We will insert an explicit combinatorial proof (with an inductive step on n) establishing that the distance-3 codeword graph is connected and bipartite for all n ≥ 2, together with direct verification for representative small even and odd values (n = 2, 3, 4) to confirm the bipartition and the validity of the subsequent max-cut reduction. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper derives the connected bipartite structure of the distance-3 codeword graph directly from the Hamming code properties for n≥2, reduces optimal parity assignment to a max-cut on the induced distance-4 graphs via standard spectral graph theory, and obtains the minimum-eigenvalue eigenvectors by optimizing moments of Walsh coefficients. The tight lower bound for even n is attained precisely by bent functions because of their independently known flat Walsh spectrum (a defining property established outside this work), not by construction from the same equations. No load-bearing self-citations, fitted inputs renamed as predictions, or ansatzes smuggled via prior work appear; each step is externally verifiable in coding theory and Boolean function analysis without reducing to the target result by definition.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central claims rest on the unproved (in the abstract) assertion that the distance-3 graph is connected and bipartite for every n≥2, plus the assumption that eigenvectors of the distance-4 graphs directly solve the max-cut instance without additional verification.

free parameters (1)

parity assignment vector
Chosen via the minimum-eigenvalue eigenvector; its concrete values are not fixed a priori but derived from the graph spectrum.

axioms (1)

domain assumption The distance-3 codeword graph of the Hamming code induces a connected bipartite structure for all n≥2
Invoked to guarantee the existence of the systematic construction with minimum distance 2.

pith-pipeline@v0.9.0 · 5503 in / 1488 out tokens · 57381 ms · 2026-05-15T02:11:06.020910+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We reduce the problem of finding these eigenvectors to an optimization problem involving moments of the Walsh coefficients of a related function, which we solve for even n by deriving a tight lower bound shown to be attained by bent functions
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the distance-3 codeword graph is shown to induce a connected bipartite structure for all n≥2

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[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, 2023

work page 2023
[2]

Optimal redundancy of function-correcting codes,

G. Ge, Z. Xu, X. Zhang, and Y . Zhang, “Optimal redundancy of function-correcting codes,”arXiv preprintarXiv:2502.16983, 2025

work page arXiv 2025
[3]

On Function-Correcting Codes,

R. Premlal and B. S. Rajan, “On Function-Correcting Codes,” in IEEE Transactions on Information Theory, vol. 71, no. 8, pp. 5884-5897

work page
[4]

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, 2024

work page 2024
[5]

Function-correcting codes for b-symbol read channels,

A. Singh, A. K. Singh, and E. Yaakobi, “Function-correcting codes for b-symbol read channels,”arXiv preprintarXiv:2503.12894, 2025

work page arXiv 2025
[6]

A note on function correcting codes for b-symbol read channels,

S. Sampath and B. S. Rajan, “A note on function correcting codes for b-symbol read channels,”arXiv preprintarXiv:2503.23059, 2025

work page arXiv 2025
[7]

Function-correcting codes with homogeneous distance,

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

work page arXiv 2025
[8]

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,”arXiv preprint arXiv:2504.07804, 2025

work page arXiv 2025
[9]

Function- correcting codes with data protection,

C. Rajput, B. S. Rajan, R. Freij-Hollanti, and C. Hollanti, “Function- correcting codes with data protection,”arXiv preprintarXiv:2511.18420, 2025

work page arXiv 2025
[10]

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", arXiv:2602.21932 [cs.IT]

work page arXiv
[11]

F. J. MacWilliams and N. J. A. Sloane,The Theory of Error-Correcting Codes. Amsterdam, The Netherlands: North-Holland, 1977

work page 1977
[12]

A closed set of normal orthogonal functions

J. L. Walsh, “A closed set of normal orthogonal functions", American Journal of Mathematics, V ol. 45, No. 1 (Jan., 1923), pp. 5-24

work page 1923
[13]

Function-Correction with Optimal Data Protection for the General Hamming Code Membership

A. Yadava, A. A. Mahesh, and S. S. Durgi, “Function-Correction with Optimal Data Protection for the General Hamming Code Membership", arXiv, May 2026

work page 2026
[14]

Sur une généralisation des polynomes d’Hermite,

M. Krawtchouk, “Sur une généralisation des polynomes d’Hermite,” Comptes Rendus, vol. 189, pp. 620–622, 1929

work page 1929