The project CP-MACT aims to solve fundamental problems of algebraic coding theory and combinatorics: problem of classification of codes, studying their structure and conditions of existence. In the project "Classification Problems in Modern Algebraic Coding Theory", we plan to present new and develop the existing methods in the following areas of algebraic coding theory and design theory: perfect and extended perfect codes in Hamming graphs, perfect codes in Johnson graphs, optimal codes with restrictions on a weight distribution, special sets of points in finite projective geometries.
Duration of the project: February 2023 - February 2025
The project is funded by the P. Beron program.
We consider extended 1-perfect codes in Hamming graphs \(H(n,q)\). Such nontrivial codes are known only when \(n=2^k\), \(k\geq 1\), \(q=2\), or \(n=q+2\), \(q=2^m\), \(m \geq 1\). In this work, we characterize all positive integers \(n\), \(r\) and prime \(p\), for which there exist such a code in \(H(n,p^r)\). Using similar techniques we also find some new necessary conditions of existence of \(2\)-perfect codes in Hamming and Johnson graphs.
We prove that for every fixed \(d\) (\(d\) even) there exists an integer \(N(d)\) such that for every \(n\geq N(d)\), an optimal binary code of length n and distances \(d\) and \(d+2\) is a translation of some constant-weight code. We also prove some estimates on \(N(d)\) for \(d=4\) and \(d=6\). .
We use known perfect codes and some equitable \(2\)-partition to another close problem from algebraic combinatorics – existence of eigenfunctions with a small number of nodal domains. We prove conjecture by Bıyıkoğlu et al. from 2004 about existence of an eigenfunction of the hypercube with eigenvalue \(2i\) that has exactly two strong nodal domains for \(i\leq \frac{2}{3}(n−\frac{1}{2})\) if \(i\) is odd and for \(i\leq \frac{2}{3}(n−1)\) if \(i\) is even. We also obtain even stronger results for the Hamming graph \(H(n,q)\), \(q\geq 3\).
In this paper we prove a new reducibility result for mini-hypers in projective geometries over finite fields. It is further used to characterize the minihypers with parameters \((70, 22)\) in \(PG(4, 3)\). The latter can be used to attack the existence problem for some hypothetical ternary Griesmer codes of dimension \(6\).
Let \(C\) be a binary code of length \(n\) with distances \(0 < d_1 < \dots < d_s \leq n\). In this note we prove a general upper bound on the size of \(C\) without any restriction on the distances \(d_i\). The bound is asymptotically optimal.