Constructions of locally recoverable codes with large availability (Q6933661)

A \([n,k,d,r]\) locally recoverable code (LRC) having availability \(t\) and locality \(r\) is a linear code \(\mathcal{C}\) of length \(n\) such that, given a codeword \(c\in\mathcal{C}\), an erased coordinate \(c_i\) of \(c\) can be recovered by looking at a set \(S_j\) of \(r\) distinct entries of \(c\). Furthermore, one can choose among \(t\) disjoint sets \(S_j\) of entries, all of which allow for the recovery of \(c_i\).\N\NLet \(f \in \mathbb{F}_{q}[x]\) be a fixed polynomial of degree \(n=r+1\) such that \(n \not \equiv 0,1 \bmod \operatorname{char}\left(\mathbb{F}_{q}\right)\). The authors prove that the Galois group of \(f-a x-b\) over the rational function field \(\mathbb{F}_{q}(b)\) is equal to \(S_{n}\) for all but \(O(1)\) choices of \(a \in \mathbb{F}_{q}\), as \(q\) grows. This result allows one to show that the number of locality sets arising from the construction in [\textit{C. Carvalho} and \textit{V. G. L. Neumann}, São Paulo J. Math. Sci. 17, No. 1, 55--63 (2023; Zbl 1541.94089)] is roughly \(q^{2} /(r+1)!\). A detailed explanation of the codes generated by paradoxical families and their parameters is also provided.\N\NThe next goal of the paper is to study the availability property that arises from paradoxical families, specifically to estimate the availability of a paradoxical family satisfied by a polynomial. By applying the Chebotarev density theorem [\textit{N. G. Chebotarev}, Math. Ann. 95, 191--228 (1925; JFM 51.0149.04)], it is shown that an availability of at least \(q / r!+O(\sqrt{q})\) is achieved when the locality \(r\) is chosen appropriately.\N\NFinally, examples of codes constructed from paradoxical families and their parameters, as well as some applications, are presented: a \([124, 5, 119, 3]\) LRC over \(\mathbb{F}_{125}\) with availability 21, a \([343, 10, 328, 4]\) LRC over \(\mathbb{F}_{343}\) with availability \(9\), and a \([124, 15, 100, 5]\) LRC over \(\mathbb{F}_{125}\) with availability \(6\).