Simultaneous Approximations and Covering by Arithmetic Progressions in Fp

✍ Scribed by Vsevolod F. Lev

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 140 KB
• Volume: 92
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1999.3034

✦ Synopsis

outer maximum being taken over all n-element subsets of F p . It is shown that this extremal simultaneous approximation problem is equivalent to the combinatorial problem of finding minimal l n such that any set of n residues modulo p can be covered by an arithmetic progression of the length l n . For n 4, we determine the order of magnitude of m n and prove that 1 2 p 1&1Â(n&1) (1+o(1))<m n <n &1Â(n&1) p 1&1Â(n&1) (1+o( 1)) (as p Ä and n is small compared to p). For n=3, we find a sharp asymptotic and moreover, prove that & 4 -pÂ3<m 3 &-pÂ3<1Â2. These results answer a question of Straus about the maximum possible affine diameter of an n-element set of residues modulo a prime.