Caps and progression-free sets in $${{\mathbb {Z}}}_m^n$$ Z m n
- PDF / 603,666 Bytes
- 38 Pages / 439.37 x 666.142 pts Page_size
- 26 Downloads / 181 Views
Caps and progression-free sets in Znm Christian Elsholtz1
· Péter Pál Pach2
Received: 21 July 2019 / Revised: 5 March 2020 / Accepted: 29 May 2020 © The Author(s) 2020
Abstract We study progression-free sets in the abelian groups G = (Znm , +). Let rk (Znm ) denote the maximal size of a set S ⊂ Znm that does not contain a proper arithmetic progression of length n √ , k. We give lower bound constructions, which e.g. include that r3 (Znm ) ≥ Cm ((m+2)/2) n √ n 0.7924 when m is even. When m = 4 this is of order at least 3 / n |G| . Moreover, if the progression-free set S ⊂ Zn4 satisfies a technical condition, which dominates the problem at least in low dimension, then |S| ≤ 3n 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: r6 (Zn125 ) ≥ (85 − o(1))n . For r3 (Zn4 ) we determine the exact values, when n ≤ 5, e.g. r3 (Z54 ) = 124, and for r4 (Zn4 ) we determine the exact values, when n ≤ 4, e.g. r4 (Z44 ) = 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 Zn4 from 2.519n to (3 − o(1))n , and when m = 5 from 2.942n 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 31:5–14, 2004). Keywords Permutation polynomial · Triple-cycle permutation · Finite field; Block cipher Mathematics Subject Classification 06E30 · 14G50 · 94A60
Communicated by J. Bierbrauer.
B
Christian Elsholtz [email protected] Péter Pál Pach [email protected]
1
Institute of Analysis and Number Theory, Graz University of Technology, Kopernikusgasse 24/II, 8010 Graz, Austria
2
MTA-BME Lendület Arithmetic Combinatorics Research Group, Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Magyar tudósok körútja 2, Budapest 1117, Hungary
123
C. Elsholtz, P. P. Pach
1 Introduction There has been great interest in finding progression-free sets in Znm :=(Z/(mZ))n , especially when m = 3 or 4. When m = 3, 4, 5 the properties “no arithmetic progression of length 3 modulo m” and “no 3 points on any line” are equivalent. The last property is also well known under the name cap-sets. In spite of this great interest in progression-free sets and caps there is not much literature on progression-free sets in Znm , in the case of general m > 3, and of general progressions of length k, and hardly any explicit values of the maximal size of such sets is known.1 This paper intends to fill this gap and provides several new techniques to find lower bounds, and even to find exact values in the case m = 4, which are comparable in size to the known values for m = 3. However, before we come to this, we briefly summarize a number of related questions. The problem of finding sets S ⊂ Znm with, or without, a given property has been investigated frequently. Often one
Data Loading...
