Locality for codes over integers
Giulia Cavicchioni, Eleonora Guerrini, Julien Lavauzelle · 2026
Read Locality for codes over integers by Giulia Cavicchioni, Eleonora Guerrini, Julien Lavauzelle (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-26756.txt.
Introduction
Cavicchioni, Guerrini, and Lavauzelle study codes over whole numbers under local-repair constraints, where each symbol can be rebuilt from a small set of other symbols. They introduce a weighted notion of local repair over products of cyclic groups , proving a Singleton-like bound for locally fixable codes. The paper also proposes code builds with local repair, including whole-number versions of Tamo-Barg codes.
Catalog record
| CREATOR | Giulia Cavicchioni, Eleonora Guerrini, Julien Lavauzelle |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27766 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.26756
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Locality for codes over integers Thanks: [email protected] Thanks: [email protected] Thanks: [email protected] Giulia Cavicchioni, Eleonora Guerrini, Julien Lavauzelle Abstract In this work, we study the codes over the integers with locality constraints. We introduce a weighted notion of locality over ℤ / q 1 ℤ × ⋯ × ℤ / q n ℤ \mathbb{Z}/q_{1}\mathbb{Z}\times\cdots\times\mathbb{Z}/q_{n}\mathbb{Z} and derive a Singleton-like bound for locally recoverable codes. We also propose some code constructions with locality, including integer analogs of Tamo–Barg codes. Keywords: Codes over integers, locally recoverable codes, Chinese Remainder codes. 1 Introduction Motivation. The rise of distributed computation has highlighted the need to verify or secure the outputs of remote calculations. When outsourcing computations, servers may fail, delay responses, or, in some cases, act maliciously, producing erroneous results. Integer codes have proven effective in this setting [ 15 , 4 ] . The idea is to decompose a large algebraic computation, such as the determinant of a matrix with large integer entries, into many smaller but similar computations modulo small prime numbers. After having sent each of these smaller computations and received the corresponding outputs, one is able to retrieve the expected result applying the Chinese Remainder Theorem. Moreover, if some nodes fail or return incorrect outputs, the result can still be recovered via error-correction algorithms [ 11 , 12 , 4 , 16 ] . However, if a node fails during the computation, reconstructing the lost residue using Chinese Remainder codes typically requires contacting many servers. Indeed, due to the Chinese Remainder isomorphism, recovering a missing symbol is essentially equivalent to reconstructing the whole data. Theoretically, it is also interesting to further explore the parallels between CRT-based constructions and Reed–Solomon codes, whose connection has proven fruitful for decoding, and extend this comparison to local recovery in order to better understand their similarities and differences. In this context, it is desirable to recover lost information more efficiently. This problem is closely related to the local recovery problem [ 13 , 5 ] , where data is distributed and stored on servers, and should be reconstructible from a small subset in case of failures. From an algebraic perspective, a locally recoverable code enables local repair of a coordinate by accessing a small subset of other coordinates. Research in this area has focused both on bounding the minimum distance of a locally recoverable code [ 5 ] and on constructing codes with optimal parameters [ 14 , 17 , 7 , 8 ] , that is, codes that maximize the number of codewords for a given length, distance, and locality. Outline. In this paper, we introduce locally recoverable codes over the integers, focusing on both deriving bounds for their minimum distance and constructing families of codes with locality. Since codes over the integers are naturally endowed with a metric different from the Hamming metric, in Section 3 we propose a new definition of locality suited for this context, and we state a Singleton-like bound for locally recoverable codes over the integers. Searching for good locally recoverable codes, in Section 4 , we analyze two asymptotic constructions: the cartesian power of integer codes, and the (newly introduced, up to our knowledge) concatenation of integer codes. Finally, in Section 5 we propose an adaptation of the Tamo–Barg construction over finite fields [ 14 ] to the integers. For some range of parameters, the construction approaches closely the proposed Singleton-like bound. 2 Preliminaries 2.1 Definitions and general results An integer code is a subset {\mathcal{C}}\subseteq\mathbb{Z}/{q_{1}}\mathbb{Z}\times\cdots\times\mathbb{Z}/{q_{n}}\mathbb{Z}\, , where n\geq 1 is the length of the code and q_{1},\dots,q_{n} are integers \geq 2 . The size of the ambient space N\coloneqq q_{1}q_{2}\cdots q_{n} is also called the amplitude of the code [ 4 ] . We usually denote by K\coloneqq|{\mathcal{C}}|\leq N its cardinality. In coding theory, we usually endow the ambient space with a metric which represents the loss of information failures can induce. The Hamming metric is the most usual: it represents individual errors on codeword symbols, assuming that each coordinate carries the same amount of information. Unfortunately, the latter assumption does not hold for integer codes: if some q_{i} is much larger than the other q_{j} , the corresponding codeword symbol c_{i} can provide much more information than the other c_{j} . Therefore, we have to consider the metric over \mathbb{Z}/{q_{1}}\mathbb{Z}\times\cdots\times\mathbb{Z}/{q_{n}}\mathbb{Z} taking this into account. Let I\subset[1,n] be a subset of coordinates. The weight of I is the maximum number of symbols supported by the coordinates in I , that is, {\rm wt}(I)\coloneqq\prod_{i\in I}q_{i} Definition 1 . Let {\bm{a}}=(a_{1},\dots,a_{n}) and {\bf b}=(b_{1},\dots,b_{n}) be two elements of \mathbb{Z}/{q_{1}}\mathbb{Z}\times\cdots\times\mathbb{Z}/{q_{n}}\mathbb{Z} . 1. The support of a vector {\bm{a}} is the set of its nonzero coordinates, namely \mathrm{supp}({\bm{a}})\coloneqq\{i\in[1,n]\mid a_{i}\neq 0\} . 2. The weight of {\bm{a}} is {\rm wt}({\bm{a}})\coloneqq{\rm wt}(\mathrm{supp}({\bm{a}}))=\prod_{i:a_{i}\neq 0}q_{i} . 3. The weighted distance between {\bm{a}} and {\bm{b}} is D({\bm{a}},{\bm{b}})\coloneqq{\rm wt}(\mathrm{supp}({\bm{a}}-{\bm{b}}))=\prod_{i:a_{i}\neq b_{i}}q_{i} . Definition 2 . The minimum (weighted) distance of an integer code {\mathcal{C}} of cardinality \geq 2 is D({\mathcal{C}})\coloneqq\min\{D({\bm{a}},{\bm{b}})\,\mid\,({\bm{a}},{\bm{b}})\in{\mathcal{C}}^{2},\,{\bm{a}}\neq{\bm{b}}\}. We usually denote by D the minimum distance of a code, by abuse of notation. The amplitude N of a code, its cardinality K and its minimum distance D are constrained by a Singleton-like bound, as stated in Theorem 2.1 . Theorem 2.1 (Singleton bound for integer codes) . Let {\mathcal{C}} be an integer code with parameters (N,K,D) . Then, for any set of coordinates I\subset[1,n] of weight strictly less than D , we have {\rm wt}(I)\leq N/K . Note that Theorem 2.1 can be rephrased as D\leq\min\{{\rm wt}(I)\mid I\subset[1,n],{\rm wt}(I)>N/K\}, which implies that D<N/K . We now recall some classical constructions of codes from others. 1. The puncturing of a code {\mathcal{C}} on a subset of coordinates I\subset[1,n] is {\rm Punct}({\mathcal{C}},I)\coloneqq\{(c_{i})_{i\in[1,n]\setminus I}\mid{\bm{c}}\in{\mathcal{C}}\}\;\subseteq\;\prod_{i\in[1,n]\setminus I}\mathbb{Z}/{q_{i}}\mathbb{Z}\,. 2. The shortening of a code {\mathcal{C}} on a set of coordinates I , according to a tuple {\bm{a}}=(a_{i})_{i\in I} , is {\rm Short}({\mathcal{C}},I,{\bm{a}})\coloneqq\{{\bm{c}}\in{\mathcal{C}}\mid c_{i}=a_{i},\;\forall i\in I\}\;\subseteq\;\prod_{i=1}^{n}\mathbb{Z}/{q_{i}}\mathbb{Z}\,. It is also usual to puncture a code that was previously shortened on I , since all codewords of the shortened code agree on I . Thus, we also define: {\rm Short}^{*}({\mathcal{C}},I,{\bm{a}})\coloneqq{\rm Punct}({\rm Short}({\mathcal{C}},I,{\bm{a}}),I). 2.2 Residue integer codes Let \phi be the residue map : \begin{array}[]{rclc}\phi:&[0,N-1]&\longrightarrow&\mathbb{Z}/{q_{1}}\mathbb{Z}\times\cdots\times\mathbb{Z}/{q_{n}}\mathbb{Z}\\ &x&\longmapsto&(x\!\!\mod q_{1},\;\dots,\;x\!\!\mod q_{n})\end{array} Definition 3 . An integer code {\mathcal{C}} of amplitude N is called a residue integer code if there exists a subset {\mathcal{M}}\subset[0,N-1] on which \phi is injective, and such that \phi({\mathcal{M}})={\mathcal{C}}\,. In some sense, residue integer codes can be thought as integer analogues of evaluation codes over finite fields. A very natural setting for residue integer codes arises when integers q_{i} are pairwise coprime. The Chinese Remainer Theorem (CRT) then ensures that the residue map \phi is injective over [0,N-1] . This setting leads to the construction of so-called Chinese Remainder codes (CR codes), which are counterparts of Reed–Solomon codes for integer codes [ 4 ] . Definition 4 . Let K\leq N=\prod_{i=1}^{n}q_{i} , with pairwise coprime q_{i} ’s. A Chinese Remainder code is the image of {\mathcal{M}}\coloneqq[0,K-1] by the residue map \phi : {\rm CR}({\bm{q}},K)\coloneqq\{(x\!\!\mod q_{1},\dots,x\!\!\mod q_{n})\mid 0\leq x<K\}\,. CR codes are optimal with respect to the Singleton-like bound. Theorem 2.2 (see [ 4 ] ) . The distance D of the code {\rm CR}({\bm{q}},K) is D=\min\{{\rm wt}(I)\mid I\subset[1,n],{\rm wt}(I)>N/K\}\,. CR codes can also be efficiently decoded, up to