2025/05/29 by Benedek Kovács, Kovács, Benedek
Computer Science · Engineering · Mathematics · #20G15 #51E21 #51E22 #94B05 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Rings, Modules, and Algebras #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2505.24072
openalex publication_date 2025/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The author, together with Nagy, studied the following problem on unavoidable intersections of given size in binary affine spaces. Given an m-element set S⊆ \mathbbF2n, is there guaranteed to be a [k,t]-flat, that is, a k-dimensional affine subspace of \mathbbF2n containing exactly t points of S? Such problems can be viewed as generalizations of the cap set problem over the binary field. They conjectured that for every fixed pair (k,t) with k≥ 1 and 0≤ t≤ 2k, the density of values m∈ \0,...,2n\ for which a [k,t]-flat is guaranteed tends to 1. In this paper, motivated by the study of the smallest open case (k,t)=(3,1), we present explicit constructions of sets in \mathbbF2n avoiding [k,1]-flats for exponentially many sizes. These sets rely on carefully constructed binary linear codes, whose weight enumerators determine the size of the construction.