Construction of isodual codes from polycirculant matrices (Q2211336)

A linear code \(C\) of length \(n\) over a field \(\mathbb{F}\) is polycyclic if there exists a vector \(c = (c_0, c_1,\ldots, c_{n-1})\in\mathbb{F}^n\) such that for every \((a_0, a_1,\ldots , a_{n-1}) \in C\) we have \((0, a_0, a_1,\ldots, a_{n-2}) + a_{n-1} (c_0, c_1,\ldots, c_{n-1})\in C.\) Denoting by \(T_c\) the endomorphism of \(\mathbb{F}^n\) with the matrix which is transposed of the the companion matrix of \(f(x)=x^n-c.\) A matrix \(A\) of size \(n\times n\) is polycirculant for a polyshift \(T_c\) if its rows are in succession \(a, T_c(a), T_c^2(a),\ldots, T_c^{n-1}(a).\) In the present paper, the authors generalize this technique to polycirculant matrices, thus introducing and studying a class of codes -- the double polycirculant codes. A linear code \(C\) of length \(2n\) is said to be double polycirculant (DP) if its generator matrix \(G\) is of the form \(G = (I, A),\) where \(I\) is the identity matrix of size \(n\times n,\) and \(A\) is a polycirculant matrix of the same size. When \(A^t=QAQ\) for \(Q\) a permutation matrix it is easy to show that the DP code is equivalent to its dual, and is, in particular, formally self-dual (FSD). The authors show that DP codes can be binary self-dual only if they are double circulant. The special case when the matrix of the polyshift is the companion matrix of a trinomial with nonzero constant term is examined. In that situation, every polycirculant matrix satisfies the condition on its transpose mentioned above. For \(q = 2,\) 3, 5, 7 numerical examples in short to medium lengths show the DP codes have parameters equal or up to one unit of the best-known FSD codes. By using random coding, it is shown that the relative distances of long binary codes in that family satisfy a family of lower bounds that is, up to epsilons, the Gilbert-Varshamov bound for linear codes of rate one half. The argument relies on the construction of an infinite family of irreducible trinomials, a fact of independent interest, and on some properties of cyclic vectors in linear algebra. This generalizes the asymptotic properties of self-dual double-circulant codes, and of self-dual negacirculant codes. The proof is restricted to \(\mathbb{F}_2\) where it is shown that an infinite family of irreducible trinomials exists. The duality properties of DP codes: isoduality, self-duality and evenness is further studied and asymptotic bounds by random coding are derived. Some numerical examples of parameters of DP codes are given.