Simultaneous approximations and covering by arithmetic progressions in F-p

Given a set A = {a(1), ..., a(n)} subset of or equal to F-p of residues mod ulo prime p, we seek alpha, delta epsilon F-p (delta not equal0) which simu ltaneously minimize all the distances \\deltaa(i)-alpha\\ from the zero res idue and investigate the quantity m(n) = max(\A\-n) min(alpha,delta) max(1 less than or equal to i less than or equal to n) \\deltaa(i)-alpha\\, the o uter maximum being taken over all n-element subsets of F-p. It is shown tha t this extremal simultaneous approximation problem is equivalent to the com binatorial 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). Fo r n greater than or equal to 4, we determine the order of magnitude of m(n) and prove that 1/2p(1-1/(n-1))(1 + o(1)) < m(n) < n(-1/(n-1)) p(1-1/(n-1)) (1 + o(1)) (as p --> infinity and n is small compared to p). For n=3, we fi nd a sharp asymptotic and moreover, prove that -(4)rootP/3 < m(3) - <root>p /3 < 1/2. These results answer a question of Straus about the maximum possi ble affine diameter of an n-element set of residues module a prime. (C) 200 0 Academic Press.