Affine Diameter of a Set of Residues

The affine diameter l(A) of a set A of residues modulo a prime number p was introduced by E.G.Straus in 1976; it is the length of the shortest arithmetic progression modulo p, containing A as its subset. For example, the affine diameter of A={1, 5, 6} (mod 7) is 3, the shortest progression being {6, 1, 3, 5}. (Actually, Straus used a slightly different definition and another notation. In our definition above, the length of a progression is the number, less by one than the number of its elements.)

Straus raised the problem of estimating l(n), the maximum possible diameter of an n-element set of residues modulo given p. This problem is essentially solved in my recent paper "Simultaneous Approximations and Covering by Arithmetic Progressions modulo a prime", where I prove that

p1-µ (1+o(1)) < l(n) < 2n-µ p1-µ ;       µ=1/(n-1),
as p increases to infinity and n is fixed (or at least relatively small compared to p).

As a next step, it is natural to ask for the sharp asymptotic for l(n) / p1-µ or more precisely, for the liminf and limsup of this ratio as p grows to infinity and n is fixed. In the above mentioned paper, I was able to find the asymptotic for n=3 and moreover, to show that

| l(3) - 2(p/3)1/2 | < 2(p/3)1/4 .
Along with the numerical evidence for n=4, this suggests that the following is likely to hold.

Conjecture.

l(n) = 2 n-µ p1-µ (1+o(1))
for any fixed n and for p growing to infinity.

HOME    1    2    3    4    5    6    PROBLEMS PAGE