Simultaneous approximations and covering by arithmetic progressions in Fp

[摘要] Given a set A = {a(1), ..., a(n)} subset of or equal to F-p of residues modulo prime p, we seek alpha, delta epsilon F-p (delta not equal0) which simultaneously minimize all the distances \\deltaa(i)-alpha\\ from the zero residue 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 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 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 find a sharp asymptotic and moreover, prove that -(4)rootP/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 module a prime. (C) 2000 Academic Press.

[发布日期] 2000-11-01