.fp 4 M2 UnivMath2
.fp 5 H
.fp 6 M6 UnivMath6
.fp 7 M4 UnivMath4
.S 11
.ds xX .aU
.de aU
Stockholm, Sweden
.sp
.I
J. C. Lagarias
.R
..
.ds yY .bU
.de bU
Murray Hill, NJ 07974
.sp
(July 29, 1992)
..
.ds HP 11 11 11
.ds HF 3 3 3
.EQ
delim $$
gsize 11
define mem % ^ member ^ %
define lc % left ceiling %
define lf % left floor %
define rf % right floor %
define rc % right ceiling %
define pprime % sup prime %
define sF % font M2 "\N'94'" %
define sl % font M2 "\N'60'" %
define cup % font M4 "\N'60'" %
define cap % font M4 "\N'62'" %
define rProb % roman Prob %
define sstar % sup star %
define lb % roman "{" %
define rb % roman "}" %
define dZ % font M6 Z %
define dR % font M6 R %
define hI % font M6 I %
define dN % font M6 N %
define dJ % font M6 J %
define ci % font M6 "\N'43'" %
define hR % font H R %
define hN % font H N %
define hZ % font H Z %
define hI % font H I %
define hA % font H A %
define hB % font H B %
define hM % font H M %
define hJ % font H J %
.EN
.nr Pt 1
.am DE
.ls 2
.sp
..
.ND ""
.TL ""
On the Distribution of Multiplicative Translates of
Sets of Residues (mod $p$)
.AF "Royal Institute of Technology" 1
.AU "J. H\o'a\(de'stad" JH xX
.AF "AT&T Bell Laboratories" 1
.AU "A. M. Odlyzko" AMO yY
.AS 1
.P
Let $hR$ be a set of $r$ distinct nonzero residues modulo a prime $p$,
and suppose that the random variable
$a$ is drawn with the uniform distribution
from $lb 1, 2 ,..., p-1 rb$.
We show for all sets $hR$ that
${p^-^ 2} over 2r ^<=^ E [ min [ a hR ] ] ^<=^ 100 p over {r sup 1/2}$,
where in the
set
$a hR$ each integer is identified with its least positive residue modulo $p$.
We give examples where $E[ min [ a hR ]] ^<=^ 0.8p over r$ and
$E[ min [ a hR ]] ^>=^ 0.4 ^ {p ^ log ^ r} over r$.
We conjecture that $E[ min [ a hR ]] ^<<^ p over {r sup {1^-^ epsilon}}$
holds for a wide range of $r$.
These results are applicable to the analysis of certain
randomization
procedures.
.AE
.OK ""
.MT 4 1
.ls 2
.H 1 Introduction
Let $p$ be a prime and view residues (mod $p$) as members of the set $lb 0,^ 1 ,..., ^ p - 1 rb$.\0\0Let $hR$ be a set of $r$ distinct nonzero residues
(mod $p$).
Suppose that the random variable $a$ is drawn uniformly from $( dZ / p dZ ) sup star ~=~ dZ / p dZ - lb 0 rb$,
and
denote the normalized expected size of the minimal residue in the multiplicative
translate $a hR$ (mod $p$) by
.DS 2
.EQ (1.1)
M sup star ( hR ) ^: = ^ 1 over p ^ E [ min ( a hR ) ]~.
.EN
.DE
Our object is to obtain upper and lower bounds for $M sup star ( hR )$
which depend only on $r ~=~ | hR |^$.
.P
This problem arises in two contexts.
The first concerns the analysis of a simple randomization scheme to select an element of a set
$hR tilde$ of distinct integers in $[0,~ p-1]$ whose size $| hR tilde |$ is not
specified in advance.
Draw $a$ and $b$ independently from the uniform distributions on
$( dZ / p dZ ) sup star$ and $dZ / p dZ$, respectively.
The set $a hR tilde$ divides the circle
$dR / p dZ$ into $| hR tilde |$ intervals.
The randomization procedure is to select that element $x ^mem^ hR tilde$
such that $ax$ is the leftmost element of the interval in which $b$ falls,
i.e. $ax$ is the largest element in $a hR tilde$ (mod $p$) less than or
equal to $b$, unless there is no such integer, in which case $ax$ is the largest element
in $a hR tilde$ (mod $p$).
The induced distribution on $hR tilde$ need not be uniform.
How non-uniform can this induced distribution be?
Since translating $hR tilde$ by an additive constant does not change the distribution,
we may reduce to the case where $hR tilde$
contains 0, so that $hR tilde ^ := ^ hR ^ cup ^ lb 0 rb$,
and investigate the probability that the randomly selected element $x ^member ^ hR tilde$ equals 0.
Thus we are interested in bounding the
quantity
.DS 2
.EQ (1.2)
M( hR tilde ) ~: =~ roman Prob lb b ~=~ min [a hR ^+^ b] ^:^
a,^
b ^mem ^ dZ / p dZ   ,~a ^ != ^ 0 rb ~.
.EN
.DE
This problem easily reduces to bounding quantities of the form (1.1), because one has
.DS 2
.EQ (1.3)
M ( hR tilde ) ~=~ M sup star ( - hR )~.
.EN
.DE
To see this, note that for fixed $a$ and variable $b$, the element
$b$ is the smallest nonnegative residue of $a hR tilde ^+^ b$
exactly for $0 ^<=^ b ^<=^ p ^-^ max [ a hR ] ~=~ min [ -a hR ]$.
Averaging over all $a$ then gives (1.3).
.P
The second context is the analysis of a particular pseudorandom number generator.
Given a small number of absolutely random bits, called a
.I seed,
the pseudorandom number generation problem is
to use these bits in a deterministic manner to produce a much larger number of ``random-looking'' bits.
Here ``random-looking'' means that the bits appear well-distributed with
respect to certain statistical measures.
We call such a set of bits
.I
pseudorandom bits
.R
with respect to these measures,
cf. Lagarias (1990).
This problem can also be reversed: one can consider a particular deterministic
mapping with random input and obtain bounds on the distribution of its
output with respect to various statistical measures.
.P
We consider a problem of this latter sort, concerning the generation procedure
which when given a seed $(a,b)$, consisting of elements $a$ and $b$ drawn independently from
the uniform distributions on $( dZ / p dZ ) sup star$ and $dZ / p dZ$, respectively,
together with a deterministically constructed set $hR$, produces the set
.DS 2
.EQ
a hR ^+^ b ~~~~ ( roman mod ~p )
.EN
.DE
as a set of $| hR |$ pseudorandom numbers.
Here the seed $(a,^b)$ contains about $2 log sub 2 ^p $ random bits, while the
output has about $r ^ log ^p$ bits, which
can give an exponential expansion of the
number of bits
if $r ~=~ p sup beta$ with $beta ^>^ 0$.
The elements of $a hR ^+^ b$ are pseudorandom only in a relatively weak sense, but
they do possess some nice distribution properties which are
useful in applications.
Indeed,
it is well-known that if $hR ~=~ lb x sub 1 ,^ x sub 2 rb$ consists of exactly
two distinct elements, then the random variables $ax sub 1 ^+^ b$ and $ax sub 2 ^+^ b$ are
independent and identically distributed
if $a$ and $b$ are chosen independently from $dZ / p dZ$.
Consequently the elements of $a hR ^+^ b$ are pairwise independent when
regarded as random variables.
This pairwise independence property has been exploited by
Luby\ (1985) in constructing a simple parallel algorithm for the maximal
independent set problem.
See also Alon, Babai and Itai (1986), \(sc6, for a history and applications
of this idea
to derandomize parallel algorithms.
A related construction of $k$-wise independent variables is due to Joffe\ (1974),
see also Zuckerman (1990).
.P
Relevant statistical measures of $a hR ^+^ b$ in these applications concern the distribution of
the lengths of the $r$ intervals into which
$a hR ^+^ b$ cuts the circle $dR / p dZ$,
for $a ^member ^ ( dZ / p dZ ) sup star$,
$b ^member ^ dZ / p dZ$.
We consider here the
.I
mean square spacing measure
.R
.DS 2
.EQ
 roman mss [ a hR ^+^ b ] ^: = ^ ^ sum from i=1 to r ^sl sub i sup 2 ^,
.EN
.DE
where $sl sub i$ are the lengths of these intervals, and the associated statistical measure
.DS 2
.EQ (1.4)
S ( hR ) ^: = ^ E[  roman mss [a hR ^+^ b ] ]~.
.EN
.DE
The quantity $S( hR )$ has a simple relation to various
quantities $M sup star ( hR sup prime )$.
Since the measure $S( hR )$ is translation-invariant, one has
.DS 2
.EQ (1.5)
S ( hR ) ~=~ E [  roman mss [ a hR ] ]~.
.EN
.DE
Now set $hR sub b ^: = ^ hR ^+^ b$ (mod $p$).
One has the identities
.DS 2
.EQ
sum from b=0 to p-1 ^ min [ hR ^+^ b ] ~=~ sum from i=1 to r ^ {( sl sub i -1) sl sub i} over 2 ~=~ 1 over 2  roman mss ( hR ) ^-^ 1 over 2 p 
.EN
.DE
and
.DS 2
.EQ
sum from b=0 to p-1 ^ min [ a hR ^+^ b ] ~=~ sum from b=0 to p-1 ^ min [ a ( hR ^+^ b ) ]~,
.EN
.DE
since $a ^!=^ 0$.
These yield
.DS 3
.EQ
S ( hR ) ~mark =~ 1 over {p-1} ^ sum from a=0 to p-1 ^  roman mss [ a hR ]
.EN
.sp .5
.EQ
lineup =~ 1 over p-1 ^ sum from a=1 to p-1 ^ left "{" 2 sum from b=0 to p ^ min [ a ( hR ^+^ b ) ] ~+~ p right "}"
.EN
.sp .5
.EQ (1.6)
lineup =~ 2 ^ sum from b=0 to p ^ p M sup star ( hR sub b ) ^+^ 2p ~.
.EN
.DE
Thus $S( hR )$ is determined by values of $M sup star ( hR sub b )$
for various sets $hR sub b$ having a fixed cardinality $r$.
Consequently upper and lower bounds valid for all $M sup star ( hR )$ of fixed cardinality $r$ yield upper and
lower bounds for all $S( hR )$.
It is possible that $S ( hR )$ satisfies stronger bounds than those inferred from
$M sup star ( hR )$, due to the averaging in (1.6).
However if Conjecture\ 1.3 below is true, then little
improvement is possible.
.P
Now we describe our bounds for $M sup star ( hR )$.
For reference observe that the
.I
expected size
.R
of $M sup star ( hR )$, averaged over all sets of cardinality $r$, is easily
calculated to be
.DS 2
.EQ (1.7)
E [ M sup star ( hR ) ^:^ | hR | ~=~ r ] ~=~ 1 over {r ^+^ 1 } ^,
.EN
.DE
because this average is exactly the expected size of the minimal element of a
uniformly
drawn $r$-tuple of $lb 1,^ 2 ,..., p ^-^ 1 rb$.
.P
There is a simple lower bound for $M sup star ( hR )$.
.br
.B
Theorem 1.1.
.I
For all sets $hR$ (mod $p$) of cardinality $r$,
.DS 2
.EQ (1.8)
M sup star ( hR ) ^>=^ 1 over 2r ^-^ 1 over pr ~.
.EN
.DE
.br
.B Proof.
.R
For any residue $x ^mem ^ lb 1,^ 2 ,..., p ^-^ 1 rb$ there are
exactly $r$ values of $a$ such that $x ^mem ^ a hR$.
Hence $min [ a hR ] ~=~ x$ can occur at most $r$ times,
and $min [ a hR ] ~=~ 0$ occurs once,
whence
.DS 3
.EQ
M sup star ( hR ) ~mark =~ r over {p  } left [ ( sum from j=1 to { left [ p-1 over r right ] } ^j  ) ^+^
( left [ p-1 over r right ] ^+^ 1 )
( p-1-r left [ p-1 over r right ]  )  right ]
.EN
.sp .5
.EQ
lineup >=~ r over p ^ {p-1 over r ( p-1 over r ^+^ 1 ) } over 2 ^,
.EN
.DE
which gives (1.8).\0\0\0\0$blot$
.P
This worst-case lower bound (1.8) for $M sup star ( hR )$ gives something
away, but in view of (1.7) it can be at most a multiplicative factor of 2,
as $p ~->~ inf$.
In fact, it is at most a smaller multiplicative factor, because in \(sc3 we show that the set
$hJ sub 2r ~=~ lb +- 1 ,^ +- 2 ,..., +- r rb$ has
.DS 2
.EQ (1.9)
M sup star ( hJ sub 2r ) ~=~ c sub r sup star left ( p over 2r right ) ^+^ O left ( {r sup 2 } over p right ) ^,
.EN
.DE
for constants $c sub r sup star$ satisfying
.DS 2
.EQ
c sub r sup star ~=~ {12 ^ log ^2} over {pi sup 2 } ^+^ O left ( {log ^r} over r right )
.EN
.DE
as $r~->~ inf$.
Hence the multiplicative factor is asymptotically at most ${24^ log ^2} over {pi sup 2 } ~=~ 1.6855 . . .$ (Note that $J sub 2r$ has $2r$ elements.)
.P
The more interesting problem concerns worst-case upper bounds for
$M sup star ( hR )$.
In \(sc2, we establish the following bound.
.br
.B
Theorem 1.2.
.I
For all primes
$p$ and for all
sets $hR$ (mod $p$)
of cardinality $r$,
.DS 2
.EQ (1.10)
M sup star ( hR ) ^<=^ 100 over {r sup {1/2}} ~.
.EN
.DE
.P
.R
The proof uses a second-moment method.
The constant 100, as well as many of the other constants in \(sc2, can be improved easily.
.P
In \(sc3 we show by example that the worst-case upper bound cannot be the
same order of magnitude as (1.7).
The set $hI sub r ~=~ lb 1,^ 2 ,..., r rb$ has
.DS 2
.EQ (1.11)
M sup star ( hI sub r ) ^=^ c sub r {log ^r} over r ^+^
O left ( {r sup 2 } over {p sup 2} right )
.EN
.DE
where $c sub r$ are positive constants bounded away from zero, which satisfy
.DS 2
.EQ
c sub r ~=~ {pi sup 2} over 24 ^+^ O left ( {log ^ r} over r right )
.EN
.DE
as $r ~->~ inf$.
.P
Another example is given by taking the set $hN sub p$ of quadratic nonresidues
(mod $p$),
so that $r ~=~ (p^-^ 1)/2$.
Then $min [ a hN sub p ]$ equals 1 if $a$ is a quadratic nonresidue
and otherwise it equals the minimal quadratic nonresidue $alpha sub p$, so that
.DS 2
.EQ (1.12)
M sup star [ hN sub p ] ~=~ 1 over 2 ( 1 ^+^ alpha sub p )~.
.EN
.DE
Graham and Ringrose (1990) show that $alpha sub p$ is infinitely often greater than
$c sup star ( log ^p ) ( log ^ log ^ log ^ p)$, for some constant
$c sup star ^>^ 0$, so that
.DS 2
.EQ (1.13)
M sup star ( hN sub p ) ^>>^ left ( r over {log ^ r ^ log ^ log ^ log ^r} right ) sup -1
.EN
.DE
for such primes $p$.
If the Generalized Riemann Hypothesis is true, then the $log^log^log ^r$ factor in (1.13)
can be strengthened to $log^log ^r$.
.P
What is the true order-of-magnitude of the worst-case bound for
$M sup star ( hR )$?
For definiteness we propose:
.br
.B
Conjecture 1.3.
.I
For each $epsilon ^>^ 0$ there is a constant $c ( epsilon )$ such that for
all primes $p$ and all sets $hR ( roman mod ~p )$,
.DS 2
.EQ (1.14)
M sup star ( hR ) ^<=^ c ( epsilon ) r sup {-1^+^ epsilon} ~.
.EN
.DE
.R
.P
This conjecture is likely to be hard to settle affirmatively, in view of the quadratic nonresidue example $hN sub p$.
Proving (1.14) for $hR ~=~ hN sub p$ and
$epsilon ~=~ 1/4$ would already improve the current
best bound $O ( p sup 1/4 log ^p )$ for the least quadratic nonresidue $alpha sub p$, due to Burgess\ (1963),
and the truth of Conjecture\ 1.3 would imply Linnik's conjecture that
$alpha sub p ^<<^ p sup epsilon$ for all $epsilon ^>^ 0$.
However it seems likely that improvements of Theorem\ 1.2 in the
direction of (1.14) may be possible for
small $r$,
cf. the discussion at the end of
\(sc2.
.P
Questions concerning the distribution of multiplicative dilations $a hR ( roman mod ~1)$ also
arise in studying asymptotic denseness of sets on the torus $dR / dZ$,
see Berend and Peres\ (1991).
In particular
Alon and Peres (1991) consider a closely related problem, concerning
the size of the maximal gap in sets $a hR ^+^ b$ as $a$ and $b$ vary.
They show that for every set $hR$ (mod $p$) there
exists some $a ~( roman mod ~p )$ such that the set $a hR$ viewed on the
circle $dR / p dZ $ has small discrepancy, i.e. all the intervals into
which it cuts $dR / p dZ $ are of roughly the
same length.
.H 1 "General Upper Bound"
We use a second-moment method to establish the following bound.
.br
.B
Theorem 2.1.
.I
Suppose that $p$ is a prime and $hR ~=~ lb x sub 1 ,..., x sub r rb$ is a
set of
integers
with $1^<=^ x sub 1 ^<^ x sub 2 ^<^ cdot cdot cdot ^<^ x sub r ^<=^ p ^-^ 1$.
If $a ^member ^ dZ / p dZ$ is drawn with the uniform distribution, then
.DS 2
.EQ (2.1)
roman Prob lb min [ a hR ] ^>=^ DELTA rb ^<=^ {1600 p sup 2} over {r DELTA sup 2 }
.EN
.DE
holds for any positive $DELTA$.
.br
.B Proof.
.R
We use Fourier analysis on $dZ / p dZ$.
Let
$chi sub t (y)$ denote the characteristic function of
$lb 0,^ 1 ,..., t ^-^ 1 rb$, i.e.
.DS 3
.EQ
chi sub t (y) ~=~ left "{"
matrix {
lcol {1 above nothing above 0~~~}
lcol {0^<=^ y ^<=^ t ^-^ 1^, above nothing above t^<=^ y ^<=^ p ^-^ 1~.}
}
.EN
.DE
Set $e(y) ^: = ^ exp ( {2 pi i y} over p )$.
Then $chi sub t $ has the Fourier series
.DS 2
.EQ
chi sub t (y) ~=~ sum from k=0 to p-1 ^ a sub k e(ky)
.EN
.DE
with coefficients
.DS 2
.EQ
a sub k ~=~ 2 over p ^ sum from y=0 to p-1 ^ chi sub t (y) e (-ky)^,
.EN
.DE
and a simple calculation gives
.DS 3
.EQ
a sub k ~=~ left "{"
matrix {
lcol {t over p above nothing above {sin ( { pi tk} over p ) } over {p ^ sin ^ ( {pi k} over p ) } ^e ( - (t-1)k over 2 )~~~~}
lcol {k ~=~ 0 ^, above nothing above 1^<=^ k^<=^ p ^-^ 1~.}
}
.EN
.DE
We want a function whose Fourier coefficients drop off sufficiently rapidly in $k$ and for this purpose use
the convolution
$f sub t (y) ~=~ chi sub t star chi sub t (y)$ of $chi sub t (y)$
with itself.
Recall that the convolution of two functions $g$ and $h$ is
.DS 2
.EQ
g star h (y) ~=~ r over p ^ sum from u=0 to p-1 ^ g(y-u) h(u)
.EN
.DE
and that Fourier coefficients of a convolution are the product of the Fourier coefficients of the factors.
Hence
.DS 2
.EQ
f sub t (y) ~=~ sum from k=0 to p-1 ^ b sub k e (ky)
.EN
.DE
has Fourier coefficients
.DS 3
.EQ (2.3)
b sub k ~=~ left "{"
matrix {
lcol {{t sup 2} over {p sup 2 } above nothing above
{sin sup 2 ( {pi t k} over p )} over {p sup 2 sin sup 2 ( {pi k} over p ) } e(-2(t-1)k)~~~~}
lcol {k ~=~ 0 ^, above nothing above 1^<=^ k^<=^ p^-^ 1^.}
}
.EN
.DE
The function $f sub t$ is nonnegative and is supported on the
set $lb 0,^ 1,^ 2 ,..., 2t^-^ 2 rb$.
We will choose $t ~=~ lc DELTA over 2 rc$ which guarantees that
$f sub t$ is supported on $lb 0,^ 1 ,..., DELTA rb$.
Since only the case $DELTA ^<=^ p-1$ is of interest, we suppose that $t ^<=^ (p-1) /2$.
.P
Now given the set $hR$, we define the random variable
.DS 2
.EQ (2.4)
F sub t (a) ^: = ^ sum from {x ^member^ R} ^f sub t (ax) ~.
.EN
.DE
IF $F sub t (a) ^!=^ 0$ then $a hR$ must contain an element in the support
of $^F sub t$, so that
.DS 2
.EQ
min [ a hR ] ^<=^ 2t ^-^ 2 ^<=^ DELTA ~.
.EN
.DE
Hence
.DS 2
.EQ (2.5)
roman Prob lb min [ a hR ] ^>=^ DELTA rb ^<=^ roman Prob lb F sub t (a) ~=~ 0 rb ~.
.EN
.DE
.P
It suffices to establish the upper bound (2.1) for $roman Prob lb F sub t (a) ~=~ 0 rb$ and for this we use Chebyshev's inequality, which asserts that any random
variable $F$ satisfies
.DS 2
.EQ
roman Prob lb | F(a) ^-^ m | ^>=^ lambda sigma rb ^<=^ lambda sup -2^,
.EN
.DE
where $m ~=~ E[F]$ and $sigma sup 2 ~=~ E[F sup 2 ] ^-^ E[F] sup 2$
are its mean and variance, respectively.
Applying this with $F ~=~ F sub t$ and
$lambda ~=~ m/ sigma$ we obtain
.DS 3
.EQ
roman Prob lb F sub t (a) ~=~ 0 rb ~mark <=~ roman Prob lb | F sub t (a) ^-^ E[F sub t ] | ^<=^
E[F sub t ] rb
.EN
.sp .5
.EQ (2.6)
lineup <=~ {E[F sub t sup 2 ] ^-^ E[F sub t ] sup 2 } over {E[F sub t ] sup 2 } ~.
.EN
.DE
To use this bound we calculate the first two moments of $F sub t$.
.P
The first moment $E[F sub t ]$ is easy to calculate.
It is
.DS 3
.EQ
E[F sub t ] ~mark =~ 1 over p ^ sum from a=0 to p-1 ^ F sub t (a)
.EN
.sp .5
.EQ
lineup =~ 1 over p ^ sum from k=0 to p-1 ^b sub k ^ sum from {x ^member ^ hR} ^
left ( sum from a=0 to p-1 ^ e(kax) right )
.EN
.sp .5
.EQ (2.7)
lineup =~ r b sub 0 ~=~ r {t sup 2} over {p sup 2 } ^,
.EN
.DE
using (2.3).
.P
It remains to obtain an upper bound for $E[F sub t sup 2 ]$.
To estimate it, we define
.DS 2
.EQ (2.8)
w(h,k) ~=~ | lb (x sub 1 ,^ x sub 2 ) ^:^
x sub 1 ,^ x sub 2 ^member ^ hR ~ roman and ~
hx sub 1 ~==~ kx sub 2 ~ ( roman mod ~p ) rb | ~.
.EN
.DE
Then,
since $F sub t (x)$ is real,
.DS 3
.EQ
E[ F sub t sup 2 ] ~mark = ~ 1 over p ^ sum from a=0 to p-1 ^ F sub t (a) sup 2~=~
1 over p ^sum from a=0 to p-1 F sub t (a) {F sub t (a)} bar
.EN
.sp .5
.EQ
lineup =~ 1 over p ^ sum from a=0 to p-1 ^ left ( sum from {x sub 1 ,^ x sub 2 ^member ^ hR} f sub t ( ax sub 1 ) {f sub t ( ax sub 2 )} bar right )
.EN
.sp .5
.EQ
lineup =~ 1 over p ^ sum from a=0 to p-1 ^ sum from {x sub 1 , x sub 2 ^member ^ hR} ^
sum from {h,k^=^ 0} to p-1 ^
b sub h b bar sub k e (a(hx sub 1 ^-^ kx sub 2 ))
.EN
.sp .5
.EQ
lineup =~ 1 over p ^ sum from {h,k=0} to p-1 ^
b sub h b bar sub k
left "{" sum from {x sub 1 , x sub 2 ^member ^ hR} ^
sum from a=0 to p-1 ^ e(a(bx sub 1 ^-^ kx sub 2 )) right "}"
.EN
.sp .5
.EQ
lineup =~ sum from {h,k^=^ 0} to p-1 ^ b sub h b bar sub k w(h,k) ~.
.EN
.DE
We simplify this formula by observing that $w(0,^0) ~=~ r sup 2$, and
$w(h,k) ~=~ 0$ if either $h ~=~ 0$ or $k ~=~ 0$ but not both.
Thus we obtain
.DS 2
.EQ (2.9)
E[F sub t sup 2 ] ~=~ r sup 2 b sub 0 sup 2 ^+^ sum from h,k=1 to p-1 ^ b sub h b bar sub k w(h,k) ~.
.EN
.DE
To bound this expression, we observe that
.DS 2
.EQ
0^<=^ w(h,k) ^<=^ r
.EN
.DE
for all $(h,k) ^!=^ (0,0)$, which gives
.DS 2
.EQ (2.10)
| sum from h,k=1 to p-1 ^ b sub h b bar sub k w(h,k) | ^<=^ r ( sum from k=1 to p-1 | b sub k | ) sup 2 ~.
.EN
.DE
For the Fourier coefficients of $F sub t$ we have the trivial bound
.DS 2
.EQ
| b sub k | ^<=^ b sub 0 ~=~ {t sup 2} over {p sup 2}
.EN
.DE
and also the bounds
.DS 3
.EQ
|b sub k | ^mark <=^ 4 over {k sup 2 }~~~~~~~~~~~~~~~ roman if ~ 1 ^<=^ k ^<^ p/2 ^,
.EN
.sp .5
.EQ
| b sub k | ^lineup <=^ 4 over {(p-k) sup 2} ~~~~~~~~ roman if ~ p/2 ^<^ k^<=^ p ^-^ 1 ^,
.EN
.DE
which follow from (2.3) since $| sin (x) | ^>=^ 2|x| over pi$ for $|x| ^<=^ pi /2$.
These bounds imply that
.DS 2
.EQ (2.11)
sum from k=1 to p-1 ^ | b sub k | ^<=^ 20 {t } over {p  } ~,
.EN
.DE
on using the first bound above for the range $0 ^<=^ k^<=^ p over t$ and the last two for the
remainder.
Combining (2.9)\(en(2.11) yields the second moment bound
.DS 2
.EQ (2.12)
E[F sub t sup 2 ] ^<=^ {r sup 2 t sup 4} over {p sup 4} ^+^ 400 {rt sup 2} over {p sup 2} ~.
.EN
.DE
.P
Substituting these first and second moment bounds into (2.6) yields
.DS 3
.EQ
roman Prob lb F sub t (a) ~=~ 0 rb ~mark <=~
{400 p sup 2} over {rt sup 2}
.EN
.sp .5
.EQ
lineup <=~ 1600 {p sup 2} over {r DELTA sup 2 } ^,
.EN
.DE
since $t^>=^ DELTA over 2$.\0\0\0$blot$
.P
Theorem 1.2 is an immediate consequence of this result.
.br
.B
Proof of Theorem 1.2.
.R
Theorem 2.1 yields
.DS 3
.EQ
E[ min [ a hR ]] ^<=^ sum from {DELTA ~=~ 0} to { p-1 } ^
roman Prob lb min [ a hR ] ^>=^ DELTA  rb
.EN
.sp .5
.EQ
lineup <= sum from {DELTA ~=~ 1} to p-1 ^ min left ( 1, ^ {1600 p sup 2} over {r DELTA sup 2 } right ) ^<=^ 100 p r sup {- {1/2} } ^,
.EN
.DE
the desired bound.\0\0\0$blot$
.P
To get stronger results in the direction of Conjecture\ 1.3 we must strengthen
the bound for $roman Prob lb min [ a hR ] ^>=^ DELTA rb$.
Examination of the proof of Theorem\ 2.1 suggests that better bounds than (2.1)
are likely to hold, at least for certain ranges of $r$ and $DELTA$.
Improvements might come by showing that the quantities $w(h,k)$ cannot be too
large too often for small values of $h$ and $k$, which are those smaller than
$p over {DELTA sup {1- epsilon }}$,
where the products $| b sub h b sub k |$ are large.
It is easy to see that
.DS 2
.EQ (2.13)
sum from h,k=1 to p-1 ^ w(h,k) ~=~ (p ^-^ 1) r sup 2 ^,
.EN
.DE
so that the quantities $w(h,k)$ are on average of size ${r sup 2} over {p ^-^ 1}$.
Some gain may be possible for $r$ not too large,
perhaps up to $r ^<=^ p sup beta$ for some $beta ^<^ 1$.
However for the quadratic nonresidue example $hN sub p$ one has $r ~=~ p-1 over 2$
and improvements in bounding (2.9) appear to require
cancellation involving the complex arguments of the Fourier coefficients $b sub k$.
.P
In addition, the use of the second moment method itself presumably gives something away,
because Chebyshev's inequality is not tight for distributions having smooth
tails.
Estimates for higher moments might conceivably yield improved bounds for $roman Prob lb min [a hR ] ^>=^ DELTA rb$.\0Such
moment estimates involve various interesting problems concerning the
distribution of solutions to linear Diophantine equations (mod $p$) with
bounds on the variables.
In Theorem\ 2.1 they concern the ensemble of quantities $w(h,k)$, and
other examples of such problems appear in Alon and Peres (1991),
Lemma 5.1, and in Lagarias and
H$roman a back 45 up 55 ci$stad\ (1986).
.H 1 "Constant $| hR | $ Case: Two Examples"
Now we consider $M sup star ( hR )$
for $| hR | ~=~ r$ of a fixed size as
$p~->~ inf$.
We estimate $M sup star ( hR )$ for the sets
$hI sub r ~=~ [ 1,^2 ,..., ^r ]$
and $hJ sub 2r ~=~ [ +- 1 ,^ +- 2 ,..., ^+- r]$,
which give relatively large and relatively small values of
$M sup star ( hR )$, respectively.
.br
.B
Theorem\ 3.1.\0
.I
One has
.DS 2
.EQ (3.1)
M sup star ( hI sub r ) ~=~ 1 over 4 ^ sum from {sF sub r} ^
1 over {k k pprime} ( 1 over k ^+^ 1 over {k pprime} ) ^+^
O ( r over p )^,
.EN
.DE
as $p~->~ inf$,
where the sum runs over all intervals $ ( sl over k ,^ {sl pprime} over {k pprime } )$ in the Farey series $sF sub r$ of order $r$.
.br
.B
Proof.\0
.R
Divide the real interval $[ 0,^p] $ into segments
$[ sl over k p ,^ {sl pprime} over {k pprime} p ]$ using the
dissection $p sF sub r$.
.br
.B
Claim.\0
.I
For those $a ^mem^ ( dZ / p dZ ) sstar$ for which $sl over k p ^<=^ a^<^ {sl pprime} over {k pprime } p$, the minimal element in
$a hI sub r$ ( mod $p$) is $ak$ (mod $p$).
.br
.B
Proof of claim.\0
.R
Consider the piecewise linear function $f(x) ~=~ kx ^-^ p [ kx over p ]$, written $f(x) ~=~ kx$ (mod $p$), on the
interval $[ sl over k p ,^ {sl pprime} over {k pprime} p ]$.
It is 0 at the left endpoint $sl over k p$, and it is
$1 over { k pprime} p$ at the right endpoint ${sl pprime} over {k pprime} p$
since the interval has length $p over {kk pprime}$.
If some $f(x) ~=~ sl x$ (mod $p$) with $0 ^<^ sl ^<^ r$,
$sl ^!=^ k$ were smaller than it anywhere inside the interval,
then it must have an intersection point inside the interval.
Any such intersection point satisfies
$kx ~=~ sl x ^+^ ap$ for some
$| a | ^<^ r$, hence $x ~=~ | a over {k ^-^ sl} | p$ and
$| a over {k ^-^ sl} | ^mem ^ sF sub r$ with
$sl over k ^<^ | a over {k ^-^ l} | ^<^ {sl pprime } over {k pprime }$,
a contradiction proving the claim.\0\0\0$blot$
.P
Now define
.DS 2
.EQ
s ( sl over k ^, ~ {sl pprime} over {k pprime } ) ~: =~ sum from
{sl over k p ^<=^ a ^<=^ {sl pprime} over {k pprime } p} ^ min
(a hI sub r ) ^.
.EN
.DE
By the claim,
.DS 2
.EQ
s( sl over k ^, ~ {sl pprime } over {k pprime } ) ~=~
sum from {sl over k p ^<=^ a^<=^ {sl pprime} over {k pprime } p} ^ ak
( roman mod ^p )^.
.EN
.DE
This gives
.DS 2
.EQ (3.2)
s( sl over k ^,~
{sl pprime} over {k pprime } ) ~=~ 1 over 2 {p sup 2 k} over {(kk pprime ) sup 2} ^+^ O ( p over {k pprime } ) ~.
.EN
.DE
The main term in this expression is the area under the line
$kx$ (mod $p$) in the interval, see Figure\ 3.1.
.DS
.ce 3
\l'1i'
.sp .25
Insert Figure 3.1 about here.
\l'1i'
.DE
Using this estimate
.DS 3
.EQ
(p(p-1)M sup star ( hI sub r ) ~mark =~ sum from {sF sub r }
s( sl over k ^,~
{sl pprime} over {k pprime } )
.EN
.sp .5
.EQ (3.3)
lineup =~ {p sup 2} over 2 sum from {sF sub r} 1 over {kk pprime} ( 1 over {k pprime }) ^+^ O ( p ^ sum from {sF sub r} 1 over {k pprime } )~.
.EN
.DE
Now use the fact that the Farey series is symmetric about 1/2,
hence if $( sl over k ^,~ {sl pprime} over {k pprime} ) mem sF sub r$
then
$left ( {k pprime - l pprime} over {k pprime} ,~ k-l over k right ) mem sF sub r$.
Pairing these terms gives
.DS 2
.EQ
sum from {sF sub r} ^ 1 over {kk pprime} ^ ( 1 over {k pprime} ) ~=~ 1 over 2 ^
sum from {sF sub r} ^ 1 over {kk pprime} ( 1 over k ^+^ 1 over {k pprime} ) ~.
.EN
.DE
Now (3.1) follows by dividing (3.3) by $p(p ^-^ 1)$.
There is a remainder arising from both terms on the right side of
(3.3), and it is bounded using
.DS 2
.EQ (3.4)
sum from {sF sub r} ^ 1 over {k pprime} ^<=^ sum from {k pprime = 2} to r
^ 1 over {k pprime} ( sum from {j=1} to {k pprime} 1 ) ^+^ 2 ~=~ r ^+^ 1 ~,
.EN
.DE
which gives the result.\0\0\0$blot$
.P
Now define
.DS 2
.EQ
D sub r ^: = ^ sum from {sF sub r} ^ 1 over {kk pprime} ( 1 over k ^+^
1 over {k pprime} )~.
.EN
.DE
The sums $D sub r$ were studied by Hans and Chander\ (1964) (see also Robertson\ (1968)), who showed that
.DS 2
.EQ (3.5)
D sub r ~=~ ( {pi sup 2} over 6 ^+^ o(1) ) ^ r over {log ^r}
.EN
.DE
as $r ~->~ inf$.
In particular $D sub r ^>=^ c sub 0 r over {log ^r}$ for some absolute constant
$c sub 0 ^>^ 0$ for all $r$.
This yields:
.br
.B
Corollary\ 3.1a.\0
.I
One has
.DS 2
.EQ (3.6)
M sup star ( hI sub r )  ~=~ 1 over 4 D sub r ^+^ O( r over p )
.EN
.DE
as $p~->~ inf$,
where $D sub r ~=~ {pi sup 2} over 6 (1 ^+^ o(1))$ as $r ~->~ inf$.
.R
.P
Next we treat $hJ sub 2r ~=~ [ +- 1,^ +- 2 ,..., +- 2 r ]$.
.br
.B
Theorem\ 3.2.\0
.I
For fixed $r$ and $p ^->^ inf$,
.DS 2
.EQ (3.7)
M( hJ sub 2r sstar ) ~=~ 1 over 2 ^ sum from {sF sub r} ^ 1 over {kk pprime }
( 1 over {k ^+^ k pprime} ) ^+^ O( r over p ) ^,
.EN
.DE
where $( sl over k ,^ {sl pprime} over {k pprime} )$ runs over all intervals of the Farey series $sF sub r$ of order $r$.
.br
.B Proof.\0
.R
We proceed similarly to Theorem\ 3.1.
.br
.B
Claim.
.I
For those $a mem dZ / p dZ$ with $sl over k p ^<=^ a ^<=^ {sl pprime} over {k pprime} p$ the minimal element in $a hJ sub 2r sstar$ (mod $p$) is
$ak$ (mod $p$) for
$sl over k p ^<^ a ^<=^ ( sl over k ^+^ 1 over {k(k ^+^ k pprime )} ) p$ and
$-ak pprime$ (mod $p$) for $( sl over k ^+^ 1 over {k(k ^+^ k pprime )} ) p ^<=^ a^<=^ {sl pprime} over {k pprime} p$.
.br
.B
Proof of claim.\0
.R
The proof of Theorem\ 3.1 showed that in the interval
$( sl over k p ,^ {sl pprime} over {k pprime} p )$ the function
$ak$ (mod $p$) lies below all $a^sl$ (mod $p$) with $sl ^!=^ k$ for
$1^<=^ sl ^<=^ r$.
A similar argument shows that the function $- ak pprime$ (mod $p$) lies below
all $-^ a sl$ (mod $p$) with $sl ^!=^ k pprime$ for $1^<=^ sl^<=^ r$ on the
interval.
Hence the minimal value for $a hJ sub 2r sstar$ is $min ( ak, ^ -ak pprime )$ on the interval, and determining which is
smaller gives the stated result.\0\0\0$blot$
.P
Now set
.DS 2
.EQ
s sstar ( sl over k ,^ {sl pprime} over {k pprime} ) ~=~ sum from
{sl over k p ^<=^ a^<=^ {sl pprime} over {k pprime} p} ^ min (
a hJ sub 2r ) ~.
.EN
.DE
Using the claim, we have
.DS 3
.EQ
s sstar ( sl over k ^,~ {sl pprime} over {k pprime} ) ~mark =~ sum from
{sl over k p ^<^ a^<=^ {sl pprime} over {k pprime} p} ^ min (ak , ^-ak pprime ) ~
( roman mod ~p)
.EN
.sp
.EQ (3.8)
lineup =~ {p sup 2} over 2 ^ 1 over {kk pprime} ( 1 over {k ^+^ k pprime} ) ^+^ O ( p over {k ^+^ k pprime} ) ^,
.EN
.DE
where the main term in this expression is the area of the triangle pictured in Figure\ 3.2.
.DS
.ce 3
\l'1i'
.sp .25
Insert Figure\ 3.2 about here.
\l'1i'
.ce 0
.DE
Proceeding as in Theorem\ 3.1, we obtain
.DS 2
.EQ
p(p-1) M sup star ( hJ sub 2r ) ~=~ {p sup 2} over 2 ^ sum from {sF sub r} ^ 1 over {kk pprime} ( 1 over k ^+^ 1 over {k pprime} ) ^+^ O(
p ^ sum from {sF sub r} 1 over {k ^+^ k pprime } ) ^,
.EN
.DE
and dividing by $p(p ^-^ 1)$ yields (3.7).\0\0\0$blot$
.P
Now set
.DS 2
.EQ
E sub r ^: = ^ sum from {sF sub r } ^ 1 over {kk pprime} ( 1 over {k ^+^ k pprime} )~.
.EN
.DE
These sums were estimated asymptotically by Lehner and
Newman\ (1969), Theorem\ 2, who showed that
.DS 2
.EQ (3.9)
E sub r ~=~ {12 ^ log ^2} over {pi sup 2} ^ 1 over r ^ ^+^ O ( {log ^r} over {r sup 2} ) ~.
.EN
.DE
This yields:
.br
.B
Corollary\ 3.2a.\0
.I
One has
.DS 2
.EQ
M sup star ( J sub 2r ) ~=~ 1 over 2 E sub r ^+^ O( r over p ) ~~~ as ~ p~->~ inf^,
.EN
.DE
where $E sub r ~=~ {12 ^ log ^2} over {pi sup 2} ^ 1 over r ^+^ O (
{log ^r} over {r sup 2} )$ as $r~->~ inf$.
.R
.sp
.B Acknowledgements.
We are indebted to Gary Miller and Sandeep Sen for bringing problems of this kind to our attention and to Yuval Peres for pointing out the
quadratic residue example in [4].
.SG sam
.bp
.ce
.B References
.ls 2
.R
.sp
.RL
.LI
M. Ajtai, J. Komlos, E. Szemeredi (1990), Generating expanders from two
permutations; in:
.I
A Tribute to Paul Erd$roman o dotdot$s
.R
(A. Baker, B. Bollobas, A. Hajnal, Eds.),
Cambridge U. Press, 1-12.
.LI
N. Alon, L. Babai and A. Itai (1986),
A fast and simple randomized parallel algorithm for the maximal independent set problem,
J. Algorithms 7, 567-583.
.LI
N. Alon and Y. Peres (1991),
Uniform dilations, preprint.
.LI
D. Berend and Y. Peres (1991), Asymptotically dense dilations of sets on the
circle, J. London Math. Soc., to appear.
.LI
D. A. Burgess (1963), A note on the distribution of residues and
nonresidues, J. London Math. Soc.
.B 38,
253-256.
.LI
S. W. Graham and C. J. Ringrose (1990),
Lower bounds for least quadratic nonresidues, in:
.I
Analytic Number Theory: Proceedings of a Conference in Honor of P. Bateman
.R
(B.\ Berndt et al., eds.), Birkh$roman a dotdot$user, Boston.
.LI
R. J. Hans and V. Chander (1964), An interesting identity, Res. Bull. Panjab Univ.
.B 15,
353-356.
.LI
G. H. Hardy and E. M. Wright (1960),
.I
Introduction to the Theory of Numbers
.R
(4$"" sup roman th$\ Edition), Oxford U. Press.
.LI
A. Joffe (1974), On a set of almost deterministic $k$-independent random
variables,
Ann. Prob.
.B 2,
161-162.
.LI
J. C. Lagarias (1990), Pseudorandom number generators in cryptography and number
theory, in:
.I
Cryptology and Computational Number Theory,
.R
C. Pomerance, Ed., Proc. Symp. Applied Math. 42,
American Math. Society, 115-143.
.LI
J. C. Lagarias and J. H$roman a back 45 up 55 ci$stad (1986),
Simultaneous diophantine approximation of rationals by rationals, J. Number
Theory
.B 24,
200-228.
.LI
J. Lehner and M. Newman (1969),
Sums involving Farey fractions, Acta Arithmetica
.B 15,
182-187.
.LI
M. Luby (1985),
A simple parallel algorithm for the maximal independent set problem, Proc. 11th ACM Symp. on Theory of Computing,
ACM Press, 1-10.
.LI
M. M. Robertson (1968),
Sums associated with Farey series, Prob. Camb. Phil. Soc.
.B 64,
393-398.
.LI
D. Zuckerman (1990), General weak random sources,
Proc. 21st IEEE Conf. on Foundations of Computer Science, Vol.\ II, 534-543.
.LE
.ls 1
.CS