Linear exact repair schemes for free MDS and Reed-Solomon codes over Galois rings

Daniel P. Bossaller; Hiram H. L\'opez

REVIEW 3 major objections 4 minor 24 references

Linear exact repair schemes for free MDS and Reed-Solomon codes over Galois rings

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that free MDS codes and full-length Reed-Solomon codes over Galois rings admit linear exact repair schemes with repair bandwidth |T|-1, extending Guruswami-Wootters repair from finite fields to rings.

desk verdict The paper's central construction collapses on the trace: for Galois rings of characteristic p^n with n>1, the map x↦x^{p^m} is not an automorphism, so the trace, repair polynomials, and main theorems are unsupported. read the letter →

arxiv 2506.09017 v1 pith:XXBJADEK submitted 2025-06-10 cs.IT math.ITmath.RA

Daniel P. Bossaller , Hiram H. López This is my paper

classification cs.ITmath.ITmath.RA MSC 94B0594B3511T71

keywords linearexactrepairdistributedstorageGaloisringsReed-SolomoncodesMDStrace-dualbasisbandwidthsubpacketization

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper extends linear exact repair schemes, protocols that recover a failed node in a distributed storage system by downloading only subsymbols from the remaining nodes, from finite fields to Galois rings. The authors prove that every free MDS code over a Galois ring admits such a scheme, and for full-length Reed-Solomon codes they give an explicit construction with repair bandwidth |T|-1, expressed in subsymbols over the smaller ring. The central mechanism is the trace map between nested Galois rings and its trace-dual basis, which lets the lost coordinate be reconstructed from R-linear trace values. If correct, this makes ring-based codes, including those over Z_4 and its extensions, viable for high-efficiency storage systems.

What carries the argument

The trace map Tr_S^R(x)=Σ_{i=0}^{l-1} $x^{{p^{mi}}$} from GR(p^n,lm) to GR(p^n,m), the existence of a trace-dual basis for a free module basis, and the subtractive Teichmüller set of evaluation points. The dual of RS(T,k) is again RS(T,n−k), so the repair polynomials live in the dual code; their evaluations are trace values in R, reducing the per-node download to one R-symbol.

What would settle it

Test the construction on the smallest nontrivial case: GR(4,2) over Z_4. In Z_4, the map x↦$x^{2}$ sends 2 to 0, so it is not an automorphism; checking whether the paper's trace x+$x^{2}$ is additive on GR(4,2) and whether the repair equations reconstruct a lost coordinate would settle the central claim.

Watch

Extended reading notes

Core claim

Theorem 5.2: for Galois rings R=GR(p^n,m) and S=GR(p^n,lm), the full-length Reed-Solomon code RS(T,k) over S, evaluated on the Teichmüller set T, has a linear exact repair scheme with repair bandwidth |T|-1 over R whenever k ≤ $p^{{ml}}$(1−1/p^m). The scheme uses l repair polynomials p_{i,j}(x)=Tr(β_j(x−α_i))/(x−α_i), whose evaluations at the remaining nodes are elements of R; a trace-dual basis then reconstructs the lost symbol. The broader Theorem 4.9 asserts that any free MDS [n,k] code over S admits a linear exact repair scheme over R.

Load-bearing premise

The repair scheme assumes that raising to the p^m-th power is a ring automorphism of the larger Galois ring that leaves the smaller ring fixed; if that map is not a true automorphism, the trace used in the scheme stops being linear and the repair formula collapses.

Editorial extensions

If this is right

Any free MDS code over a Galois ring S can be repaired by contacting all remaining n−1 nodes and receiving one subsymbol, an element of the smaller ring R, from each, independent of the code dimension k.
Full-length Reed-Solomon codes over Galois rings with k ≤ p^{ml}(1−1/p^m) achieve this n−1 repair bandwidth, generalizing the Guruswami-Wootters bound k ≤ n(1−1/q) from finite fields to rings.
The scheme is linear and exact, so the repaired node is bit-identical to the original, and the operations are R-linear combinations of the downloaded trace values.
Because Z_4 is a Galois ring, the result covers full-length Reed-Solomon codes over Z_4 and its extensions, bringing ring-based coding families into the distributed-storage framework.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The proof's dependence on Proposition 2.2(e) suggests the result may not hold for n>1 unless the automorphism is properly defined; checking small cases like GR(4,2) could reveal whether the trace must be replaced by a different map.
If the trace issue is resolved, the same approach might extend to other Frobenius rings by replacing the automorphism sum with a trace-like functional that is still linear; the paper leaves this open.
One could test the scheme's communication cost on a small storage simulation with k close to the bound to verify that the n−1 bandwidth is actually achieved with R-symbols of size |R|.
The bound k ≤ p^{ml}(1−1/p^m) mirrors the field case and may be tight; a converse showing no linear scheme below this rate would complete the picture.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

Quick take: the central construction is built on a false premise. The trace in Definition 4.1 uses σ_m(x)=x^{p^m}, but for Galois rings GR(p^n, ml) with n>1 this map is not a ring automorphism—additivity fails already in Z_4. So Lemma 4.2, Eq. (1), Theorem 4.9, and Theorem 5.2 are unsupported. The stress-test note is right: in GR(4,3) with γ^3=γ+1, Tr(γ+1)=3 but Tr(γ)+Tr(1)=2γ+2γ^2+3.

What the paper does well: it is the first attempt I know to extend Guruswami-Wootters exact repair to Galois rings. The background on Galois rings and GRS codes over rings is cleanly organized, and the authors state their relied-upon facts explicitly. The example is concrete and easy to check.

The soft spots beyond the trace: Theorem 4.9's proof confuses m and l—for an extension of degree l it selects m codewords and an m-element trace-dual basis—so the argument never establishes the claimed low-rank helper selection. The definition of RS(T,k) uses f∈R[x], which gives a code over R, when the intention is a code over S; the later text switches to f∈S[x]. These are fixable, but the trace error is load-bearing.

For the record, Proposition 2.2(e) is stated from standard references, but as written it is false for n>1. The correct automorphism is the coefficient-wise Frobenius on p-adic expansions. A repair scheme may well be salvageable with that map, but this version is not.

Who gets value: a coding theorist curious about ring-valued storage codes might read the introduction and setup, but no conclusion should be drawn from the main theorems. It deserves a serious referee because the question is legitimate and the error is clearly diagnosable; the referee will likely reject it in current form but can point the authors to the standard Frobenius automorphism.

Recommendation: send it to a referee with Galois-ring expertise if it lands in your inbox; the current version is not publishable.

Referee Report

3 major / 4 minor

Summary. The manuscript develops linear exact repair schemes for free MDS codes and full-length Reed-Solomon codes over Galois rings, following the Guruswami-Wootters trace-based approach. It introduces a trace from GR(p^n, ml) to GR(p^n, m), a dual-basis expansion, and repair polynomials; it claims in Theorem 4.9 that every free MDS code over a Galois ring admits a linear exact repair scheme, and in Theorem 5.2 that full-length RS(T,k) over GR(p^n, lm) with k ≤ p^{ml}(1 - 1/p^m) has repair bandwidth |T| - 1 over GR(p^n, m). After reviewing Galois-ring and GRS background, the paper proves these claims and gives an example over GR(4,3).

Significance. The intended contribution is plausible and potentially useful: extending Guruswami-Wootters repair to ring-linear codes would connect algebraic coding over Galois rings with distributed storage. The paper correctly identifies free MDS codes as MDR and collects relevant background on subtractive sets and generalized Reed-Solomon codes over rings. However, the central construction depends on a trace that is not R-linear for characteristic p^n with n > 1, and the dual-code lemma for full-length Reed-Solomon codes is not valid in general Galois rings. The paper provides no machine-checked proofs or reproducible code; the main theorems are therefore not established for the ring case.

major comments (3)

[§2.2 (Prop. 2.2(e)) and §4 (Def. 4.1)] The automorphism statement in Proposition 2.2(e) is false as written for n > 1. The map σ_m(x) = x^{p^m} is not a ring endomorphism of GR(p^n, ml): in Z_4 = GR(2^2, 1), (1+1)^2 = 0 but 1^2 + 1^2 = 2, and σ_1(2) = 0 ≠ 2. Hence the trace in Definition 4.1 is not R-linear, the additive step Tr(Σ_i a_i p^i) = Σ_i Tr(a_i)p^i in Lemma 4.2 is invalid, and Proposition 4.5 cannot be applied to this trace. Because Eq. (1), Eq. (2), Theorem 4.9, and Theorem 5.2 all rely on R-linearity of Tr, the central claims are unsupported for every Galois ring with n > 1; only the n = 1 (finite-field) case reduces to the known Guruswami-Wootters trace.
[§4, Theorem 4.9] The proof of Theorem 4.9 confuses the ranks m and l. S = GR(p^n, lm) is a free R-module of rank l, so a repair over R requires l trace coefficients per helper node, not m. The proof first says the i-th coordinates of chosen dual codewords should generate S over R, then says they generate R over Z_{p^n}; these two statements are inconsistent. No argument shows that an [n, n-k] MDS dual can supply such codewords while keeping helper transmissions low-rank. Thus even with a correct trace, the existence proof is incomplete.
[§5, Lemma 5.1 and Theorem 5.2] Lemma 5.1 asserts without proof that the dual of the full-length RS(T,k) is RS(T,n-k) with the same all-ones multipliers. Proposition 2.9(c) only guarantees a dual GRS with modified multipliers, and the finite-field power-sum identity Σ_{a∈F_q} a^r = 0 for r < q-1 does not transfer to Galois rings: the constant power sum over T equals |T| = p^{ml}, which is nonzero in R when ml < n. For a concrete failure, over Z_8 = GR(2^3, 1) with T = {0,1}, the code RS(2,1) has dual generated by (1,-1), not by (1,1). Consequently the repair polynomials in Eq. (1) need not lie in C^⊥, and the repair equation in Theorem 5.2 is not justified.

minor comments (4)

[§5, definition of RS(T,k)] The definition of RS(T,k) says f(x) ∈ R[x], but the following paragraph and Example 5.3 use f(x) ∈ S[x]; the code should be defined with coefficients in S, not in the characteristic ring R.
[§5, Eq. (1)] The displayed formula for p_{i,j}(x) is garbled: it has unbalanced parentheses, and the stated degree q^l - 1 does not match the displayed expression, whose highest exponent is q^{l-1} - 1.
[§4, Lemma 4.4] The proof of Lemma 4.4 refers to 'Lemma 2.2 (d)', but the cited statement is Proposition 2.2(d).
[§4–§5] Notation for the trace is inconsistent: Theorem 4.9 uses tr for the trace from S to R, while Definition 4.1 writes Tr_S^R, and the text also uses Tr for the trace onto Z_{p^n}.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the repair schemes are constructive uses of external Galois-ring facts; the trace-automorphism issue is a mathematical correctness defect, not a self-referential derivation.

full rationale

The derivation chain in Theorems 4.9 and 5.2 is constructive and does not reduce to its inputs. No parameter is fitted to a target repair outcome; the repair polynomials in Eq. (1) are explicitly designed from the trace and the trace-dual basis, and the reconstruction in Eq. (2) is the ordinary dual-basis expansion. The only self-citation, reference [13], appears in the introduction and is not load-bearing. The central dependence on Proposition 2.2(e) and Definition 4.1 concerns whether sigma_m(x)=x^{p^m} is an automorphism of GR(p^n,ml) for n>1; if it is not, the trace is not additive or R-linear and the proofs fail. That would be a false-premise or correctness flaw, not circularity: the paper's claims are not assumed by definition, are not fitted from the data they predict, and the cited supporting results are external references (McDonald, Wan, Sison) rather than prior work by the present authors. There is no self-definition, no fitted input renamed as a prediction, and no self-citation chain forcing the conclusion.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No fitted parameters. The construction depends on standard Galois ring results, a cited trace-dual basis theorem, and the cited dual-MDS property. The critical assumption is the automorphism statement in Proposition 2.2(e), which is false for n>1 but is load-bearing for the trace and repair polynomials. No invented entities are introduced.

assumptions (4)

domain assumption The map σ_m(x)=x^{p^m} is a ring automorphism of GR(p^n,ml) fixing GR(p^n,m).
Stated in Proposition 2.2(e) and used in Definition 4.1 and Eq. (1). For n>1 the map is not multiplicative/additive on all elements; in GR(4,2), 2^2=0 whereas 2 must be fixed. This invalidates the trace.
standard math Every basis of GR(p^n,m) over Z_{p^n} has a unique trace-dual basis with respect to the trace.
Proposition 4.5, cited from [21]; used in Corollary 4.8 and Theorem 5.2 to recover coefficients.
domain assumption The dual of every free MDS code over a Galois ring is a free MDS code.
Invoked before Theorem 4.9 and needed to choose dual codewords; cited to [17].
domain assumption The Teichmüller set T is subtractive, so evaluation codes RS(T,k) are free MDS and their dual is RS(T,n-k).
Used in Lemma 5.1 and Theorem 5.2; this is true for Galois rings, but the paper's stated coefficient ring in the definition of RS(T,k) is inconsistent.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Linear exact repair schemes for free MDS and Reed-Solomon codes over Galois rings." pith.science (2026). https://pith.science/paper/XXBJADEK

@misc{pith2026250609017,
  author       = {Pith},
  title        = {Pith review of: Linear exact repair schemes for free MDS and Reed-Solomon codes over Galois rings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XXBJADEK}},
  note         = {Machine review of arXiv:2506.09017}
}

read the original abstract

Codes over rings, especially over Galois rings, have been extensively studied for nearly three decades due to their similarity to linear codes over finite fields. A distributed storage system uses a linear code to encode a large file across several nodes. If one of the nodes fails, a linear exact repair scheme efficiently recovers the failed node by accessing and downloading data from the rest of the servers of the storage system. In this article, we develop a linear repair scheme for free maximum distance separable codes, which coincide with free maximum distance with respect to the rank codes over Galois rings. In particular, we give a linear repair scheme for full-length Reed-Solomon codes over a Galois ring.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[1]

Repairing Generalized Reed-Muller Codes

Tingting Chen and Xiande Zhang. Repairing generalized reed-muller codes.CoRR, abs/1906.10310, 2019

work page Pith review arXiv 1906
[2]

Network coding for distributed storage systems.IEEE transactions on information theory, 56(9):4539–4551, 2010

Alexandros G Dimakis, P Brighten Godfrey, Yunnan Wu, Martin J Wainwright, and Kan- nan Ramchandran. Network coding for distributed storage systems.IEEE transactions on information theory, 56(9):4539–4551, 2010

work page 2010
[3]

Springer, 2017

Steven T Dougherty.Algebraic coding theory over finite commutative rings. Springer, 2017

work page 2017
[4]

Mds codes over finite principal ideal rings.Designs, Codes and Cryptography, 50:77–92, 2009

Steven T Dougherty, Jon-Lark Kim, and Hamid Kulosman. Mds codes over finite principal ideal rings.Designs, Codes and Cryptography, 50:77–92, 2009

work page 2009
[5]

Available athttps:// hadoop.apache.org/docs/stable/index.html

Apache Software Foundation.Apache Hadoop 3.4.1, October 2024. Available athttps:// hadoop.apache.org/docs/stable/index.html

work page 2024
[6]

Generalized frobenius extensions of finite rings and trace functions

Marcus Greferath and Alexandr Nechaev. Generalized frobenius extensions of finite rings and trace functions. In2010 IEEE Information Theory Workshop, pages 1–5. IEEE, 2010

work page 2010
[7]

Repairing reed-solomon codes.IEEE Transac- tions on Information Theory, 63(9):5684–5698, 2017

Venkatesan Guruswami and Mary Wootters. Repairing reed-solomon codes.IEEE Transac- tions on Information Theory, 63(9):5684–5698, 2017

work page 2017
[8]

The z/sub 4/-linearity of kerdock, preparata, goethals, and related codes.IEEE Transactions on Information Theory, 40(2):301–319, 1994

A Roger Hammons, P Vijay Kumar, A Robert Calderbank, Neil JA Sloane, and Patrick Sol´ e. The z/sub 4/-linearity of kerdock, preparata, goethals, and related codes.IEEE Transactions on Information Theory, 40(2):301–319, 1994

work page 1994

Show all 24 references

[9]

Linear codes over finite chain rings.the electronic journal of combinatorics, 7:R11–R11, 2000

Thomas Honold and Ivan Landjev. Linear codes over finite chain rings.the electronic journal of combinatorics, 7:R11–R11, 2000

2000
[10]

Repairing algebraic geometry codes.IEEE Trans- actions on Information Theory, 64(2):900–908, 2018

Lingfei Jin, Yuan Luo, and Chaoping Xing. Repairing algebraic geometry codes.IEEE Trans- actions on Information Theory, 64(2):900–908, 2018

2018
[11]

On cyclic codes over galois rings.Discrete Applied Mathematics, 280:156–161, 2020

Jasbir Kaur, Sucheta Dutt, and Ranjeet Sehmi. On cyclic codes over galois rings.Discrete Applied Mathematics, 280:156–161, 2020

2020
[12]

Cam- bridge university press, 1994

Rudolf Lidl and Harald Niederreiter.Introduction to finite fields and their applications. Cam- bridge university press, 1994

1994
[13]

L´ opez, Gretchen L

Hiram H. L´ opez, Gretchen L. Matthews, and Daniel Valvo. Erasures repair for decreasing monomial-cartesian and augmented reed-muller codes of high rate.IEEE Transactions on Information Theory, 68(3):1651–1662, 2022

2022
[14]

F. J. MacWilliams.Combinatorial problems of elementary abelian groups. PhD thesis, Rad- cliffe College, 1962

1962
[15]

MacWilliams and N.J.A

F.J. MacWilliams and N.J.A. Sloane.The theory of error-correcting codes. North-holland Publishing Company, 2nd edition, 1978

1978
[16]

McDonald.Finite rings with identity, volume 28

Bernard R. McDonald.Finite rings with identity, volume 28. Marcel Dekker, Inc., 1974

1974
[17]

Norton and A

G.H. Norton and A. Salagean. On the hamming distance of linear codes over a finite chain ring.IEEE Transactions on Information Theory, 46(3):1060–1067, 2000

2000
[18]

Strong gr¨ obner bases and cyclic codes over a finite-chain ring.Electronic Notes in Discrete Mathematics, 6:240–250, 2001

Graham H Norton and Ana Sˇ alˇ agean. Strong gr¨ obner bases and cyclic codes over a finite-chain ring.Electronic Notes in Discrete Mathematics, 6:240–250, 2001

2001
[19]

On generalized reed–solomon codes over commutative and noncommutative rings.IEEE transactions on information the- ory, 59(9):5882–5897, 2013

Guillaume Quintin, Morgan Barbier, and Christophe Chabot. On generalized reed–solomon codes over commutative and noncommutative rings.IEEE transactions on information the- ory, 59(9):5882–5897, 2013

2013
[20]

Academic Press, 2017

Minjia Shi, Adel Alahmadi, and Patrick Sol´ e.Codes and rings: theory and practice. Academic Press, 2017

2017
[21]

Bases and automorphism matrix of the galois ring GR(p r, m) overZ pr

Virgilio P Sison. Bases and automorphism matrix of the galois ring GR(p r, m) overZ pr . International Electronic Journal of Algebra, 28(28):206–219, 2020

2020
[22]

World Scientific Publishing Com- pany, 2003

Zhe-Xian Wan.Lectures on finite fields and galois rings. World Scientific Publishing Com- pany, 2003

2003
[23]

Code equivalence characterizes finite frobenius rings.Proceedings of the American Mathematical Society, 136(2):699–706, 2008

Jay Wood. Code equivalence characterizes finite frobenius rings.Proceedings of the American Mathematical Society, 136(2):699–706, 2008

2008
[24]

Duality for modules over finite rings and applications to coding theory.American journal of Mathematics, pages 555–575, 1999

Jay A Wood. Duality for modules over finite rings and applications to coding theory.American journal of Mathematics, pages 555–575, 1999. 14

1999

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Repairing Generalized Reed-Muller Codes

Tingting Chen and Xiande Zhang. Repairing generalized reed-muller codes.CoRR, abs/1906.10310, 2019

work page Pith review arXiv 1906

[2] [2]

Network coding for distributed storage systems.IEEE transactions on information theory, 56(9):4539–4551, 2010

Alexandros G Dimakis, P Brighten Godfrey, Yunnan Wu, Martin J Wainwright, and Kan- nan Ramchandran. Network coding for distributed storage systems.IEEE transactions on information theory, 56(9):4539–4551, 2010

work page 2010

[3] [3]

Springer, 2017

Steven T Dougherty.Algebraic coding theory over finite commutative rings. Springer, 2017

work page 2017

[4] [4]

Mds codes over finite principal ideal rings.Designs, Codes and Cryptography, 50:77–92, 2009

Steven T Dougherty, Jon-Lark Kim, and Hamid Kulosman. Mds codes over finite principal ideal rings.Designs, Codes and Cryptography, 50:77–92, 2009

work page 2009

[5] [5]

Available athttps:// hadoop.apache.org/docs/stable/index.html

Apache Software Foundation.Apache Hadoop 3.4.1, October 2024. Available athttps:// hadoop.apache.org/docs/stable/index.html

work page 2024

[6] [6]

Generalized frobenius extensions of finite rings and trace functions

Marcus Greferath and Alexandr Nechaev. Generalized frobenius extensions of finite rings and trace functions. In2010 IEEE Information Theory Workshop, pages 1–5. IEEE, 2010

work page 2010

[7] [7]

Repairing reed-solomon codes.IEEE Transac- tions on Information Theory, 63(9):5684–5698, 2017

Venkatesan Guruswami and Mary Wootters. Repairing reed-solomon codes.IEEE Transac- tions on Information Theory, 63(9):5684–5698, 2017

work page 2017

[8] [8]

The z/sub 4/-linearity of kerdock, preparata, goethals, and related codes.IEEE Transactions on Information Theory, 40(2):301–319, 1994

A Roger Hammons, P Vijay Kumar, A Robert Calderbank, Neil JA Sloane, and Patrick Sol´ e. The z/sub 4/-linearity of kerdock, preparata, goethals, and related codes.IEEE Transactions on Information Theory, 40(2):301–319, 1994

work page 1994