Caps and progression-free sets in Z m n.

ABSTRACT

We study progression-free sets in the abelian groups G = ( Z m n , + ) . Let r k ( Z m n ) denote the maximal size of a set S ⊂ Z m n that does not contain a proper arithmetic progression of length k. We give lower bound constructions, which e.g. include that r 3 ( Z m n ) ≥ C m ( ( m + 2 ) / 2 ) n n , when m is even. When m = 4 this is of order at least 3 n / n ≫ | G | 0.7924 . Moreover, if the progression-free set S ⊂ Z 4 n satisfies a technical condition, which dominates the problem at least in low dimension, then | S | ≤ 3 n 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 r 6 ( Z 125 n ) ≥ ( 85 - o ( 1 ) ) n . For r 3 ( Z 4 n ) we determine the exact values, when n ≤ 5 , e.g.  r 3 ( Z 4 5 ) = 124 , and for r 4 ( Z 4 n ) we determine the exact values, when n ≤ 4 , e.g.  r 4 ( Z 4 4 ) = 128 . With regard to affine caps, i.e. sets without 3 points on a line, the new methods asymptotically improve the known lower bounds, when m = 4 and m = 5 in Z 4 n from 2 . 519 n to ( 3 - o ( 1 ) ) n , and when m = 5 from 2 . 942 n to ( 3 - o ( 1 ) ) n . This last improvement modulo 5 appears to be the first asymptotic improvement of any cap in AG(n, m), when m ≥ 5 over a tensor lifting from dimension 6 (see Edel, in Des Codes Crytogr 315-14, 2004).