Cargando…

Caps and progression-free sets in [Formula: see text]

We study progression-free sets in the abelian groups [Formula: see text] . Let [Formula: see text] denote the maximal size of a set [Formula: see text] that does not contain a proper arithmetic progression of length k. We give lower bound constructions, which e.g. include that [Formula: see text] ,...

Descripción completa

Detalles Bibliográficos
Autores principales: Elsholtz, Christian, Pach, Péter Pál
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer US 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7527337/
https://www.ncbi.nlm.nih.gov/pubmed/33071461
http://dx.doi.org/10.1007/s10623-020-00769-0
Descripción
Sumario:We study progression-free sets in the abelian groups [Formula: see text] . Let [Formula: see text] denote the maximal size of a set [Formula: see text] that does not contain a proper arithmetic progression of length k. We give lower bound constructions, which e.g. include that [Formula: see text] , when m is even. When [Formula: see text] this is of order at least [Formula: see text] . Moreover, if the progression-free set [Formula: see text] satisfies a technical condition, which dominates the problem at least in low dimension, then [Formula: see text] holds. We present a number of new methods which cover lower bounds for several infinite families of parameters m, k, n, which includes for example: [Formula: see text] . For [Formula: see text] we determine the exact values, when [Formula: see text] , e.g. [Formula: see text] , and for [Formula: see text] we determine the exact values, when [Formula: see text] , e.g. [Formula: see text] . With regard to affine caps, i.e. sets without 3 points on a line, the new methods asymptotically improve the known lower bounds, when [Formula: see text] and [Formula: see text] : in [Formula: see text] from [Formula: see text] to [Formula: see text] , and when [Formula: see text] from [Formula: see text] to [Formula: see text] . This last improvement modulo 5 appears to be the first asymptotic improvement of any cap in AG(n, m), when [Formula: see text] over a tensor lifting from dimension 6 (see Edel, in Des Codes Crytogr 31:5–14, 2004).