Long binary linear codes and large caps in projective space (Q1963172): Difference between revisions

A \textit{cap} in \(PG(n,2)\) is a set of points, no three of which lie on a line. A cap is called \textit{maximal} if cannot be extended to a larger cap. \textit{A. A. Davydov} and \textit{L. M. Tombak} [Probl. Inf. Transm. 25, No. 4, 265-275 (1989; Zbl 0711.94018)] showed that if the size of a maximal cap \(S\) in \(PG(n,2)\) is at least \(2^{n-1}+2\), then \(S\) can be obtained by doubling a cap in lower dimensions. Therefore, in order to determine the structure of large maximal caps in \(PG(n,2)\), it suffices to determine the structure of so-called \textit{critical caps}, i.e. caps of size \(2^{n-1}+1\), that are maximal in \(PG(n,2)\). In this paper the structure of maximal critical caps in \(PG(n,2)\) is determined. It is shown that a maximal critical cap is either \(P_1\)-decomposable, or has a tangent hyperplane. Structure theorems are given describing the caps of both types. Rephrased for codes the result yields a complete classification of all long inextendable binary linear codes of minimum distance 4. The paper moreover presents several related constructions and results.