Divergent Square Averages, , November 27, 2006

1 Introduction

Results of Bourgain [3] , [4] , [5] imply that given a dynamical system

(X, Σ, μ, T)

and

f \in L^{p} (μ)

, for some

p > 1

, the ergodic means

\begin{matrix} {lim}_{N \to \infty} \frac{1}{N} \sum_{n = 1}^{N} f (T^{n^{2}} (x)) \end{matrix}

(1)

converge almost surely. Bourgain also asked in [3] , [7] whether this result is true for

L^{1}

functions. In this paper we give a negative answer to this question.

Let us recall some concepts related to this problem.

Definition 1. A sequence

{n_{k}}_{k = 1}^{\infty}

L^{1}

-universally bad if for all ergodic dynamical systems there is some

f \in L^{1}

such that

{lim}_{N \to \infty} \frac{1}{N} \sum_{k = 1}^{N} f (T^{n_{k}} x)

fails to exist for all

x

in a set of positive measure.

By the Conze principle and the Banach principle of Sawyer (see [8] , [17] , or [16] ), the sequence

{n_{k}}_{k = 1}^{\infty}

L^{1}

-universally bad if there is no constant

C < \infty

such that for all systems

(X, Σ, μ, T)

and all

f \in L^{1} (μ)

we have the following weak

(1, 1)

inequality for all

t \in R :

\begin{matrix} μ ({x : {sup}_{N \geq 1} | \frac{1}{N} \sum_{k = 1}^{N} f (T^{n_{k}} x) | > t}) \leq \frac{C}{t} \int | f | d μ . \end{matrix}

(2)

The main result of this paper is

Theorem 1. The sequence

{k^{2}}_{k = 1}^{\infty}

L^{1}

-universally bad.

This theorem will be proved by showing that there is no constant

C

such that the weak

(1, 1)

inequality given in 2 holds.

This paper is a new and substantially modified version of our preprint from 2003. The proof in that preprint contained a gap but the methods of that paper lead to a solution of a counting problem raised by I. Assani (see [1] and [2] ).

The paper is organized as follows. In Section 2 we develop the necessary ingredients we need concerning the asymptotic distribution of squares modulo

q

where

q

is the product of

κ

distinct primes. The specific technical property we need is given in Lemma 2 . In Section 3 we develop the notion of a periodic rearrangement of a given periodic set. Lemma 3 states a property about the frequency squares hit such sets; we will need this later in our construction.

Section 4 is the technical heart of the paper. For positive integers

K

M

and a periodic set

Λ

we define the notion of a

K - M

family living on

Λ

What we need for the proof of our main theorem is the existence of some specific families living on

Λ = R .

The properties of these families are stated in Lemma 4 . However we need a double induction argument to show that such families exist. In Section 4.1 , in Lemma 5 assuming

K - M

families exist for all parameter values on

R

, we show that they exist on periodic sets

Λ

. In Section 4.2 we turn to the proof that if

K - M

families exist, then

(K + 1) - M

families exist as well, this induction on

K

is our outer inductive construction.

The proof of the existence

(K + 1) - M

families involves an intricate inner inductive construction, the “leakage process”, which is outlined in Section 4.2.1 and carried out in Sections 4.2.2 through 4.2.7 . Once it has halted, it is shown in Section 4.2.8 how to adjust the functions so that the next stage of the outer induction holds. In Section 5 , we give the proof of the main theorem. We construct a sequence of rational rotations

T_{p}

, functions

f_{p}

and numbers

t_{p}

which witness that there is no constant

C

satisfying 2 .

Let us fix some notation. Given

f : R \to R

, periodic by

p

we put

\int^{¯} f = \frac{1}{p} \int_{0}^{p} f (x) d x .

Given a Lebesgue measurable set

A

, periodic by

p

we put

\bar{λ} (A) = \frac{1}{p} λ (A \cap [0, p)) .

2 Number Theory/Quadratic residues

For each

q \in N

and

n \in Z

set

ɛ (n, q) = 1

n

is congruent to a square modulo

q

, and let

ɛ (n, q) = 0

if not. We denote by

σ_{q}

the number of squares modulo

q

. If

p

is an odd prime, then

σ_{p} = \frac{p + 1}{2}

. If

q = p_{1} \cdot \cdot \cdot p_{κ}

where

p_{1}, . . ., p_{κ}

are distinct odd primes, then (by the fact that something is a square modulo

q

if and only if it is a square modulo each

p_{i}

plus by using the Chinese remainder theorem)

σ_{q} = \prod_{i = 1}^{κ} \frac{p_{i} + 1}{2}

. For elementary properties of quadratic residues see [10] pages 67-69, or Chapter 3 of [14] . We remark that though

0^{2} = 0

, when talking about quadratic residues usually only those are considered which are not congruent to

0

, but since

ɛ (n, q) = 1

when

n

is congruent to

0

modulo

q

we will regard

0

a quadratic residue (or square) in this paper.

Put

Λ_{0} (q) = {n : ɛ (n, q) = 1}

, the set of quadratic residues modulo

q

Clearly,

\begin{matrix} # (Λ_{0} (q) \cap [0, q)) = σ_{q} > \frac{q}{2^{κ}} . \end{matrix}

(3)

Next we discuss some results from [15] concerning the distribution of the squares modulo

q

. Given

K

, consider a fixed sequence

(ɛ_{1}, . . ., ɛ_{K})

of zeros and ones. Assume that

a_{1}, . . ., a_{K}

are distinct integers modulo an odd prime

p

Set

ν_{p} (ɛ_{1}, . . ., ɛ_{K}; a_{1}, . . ., a_{K}) = # {n : 0 \leq n < p, ɛ (n + a_{i}, p) = ɛ_{i} for i = 1, . . ., K},

that is,

ν_{p} (ɛ_{1}, . . ., ɛ_{K}; a_{1}, . . ., a_{K})

counts the number of occurrences of

(ɛ_{1}, . . ., ɛ_{K})

in translated copies of

a_{1}, . . ., a_{K}

modulo

p

. Then

\frac{p}{2^{K}} - K (3 + \sqrt{p}) \leq ν_{p} (ɛ_{1}, . . ., ɛ_{K}; a_{1}, . . ., a_{K}) \leq \frac{p}{2^{K}} + K (3 + \sqrt{p}) .

The “probability” of the occurrence of

(ɛ_{1}, . . ., ɛ_{K})

in translated copies of

(a_{1}, . . ., a_{K})

P_{p} (ɛ_{1}, . . ., ɛ_{K}; a_{1}, . . ., a_{K}) = \frac{ν_{p} (ɛ_{1}, . . ., ɛ_{K}; a_{1}, . . ., a_{K})}{p}

and by the above result if

(a_{1}, . . ., a_{K})

is fixed, then

\begin{matrix} P_{p} (ɛ_{1}, . . ., ɛ_{K}; a_{1}, . . ., a_{K}) \to \frac{1}{2^{K}} as the odd prime p \to \infty . \end{matrix}

(4)

Next we want to choose square free numbers

q = p_{1} \cdot \cdot \cdot p_{κ}

, where

p_{1}, . . ., p_{κ}

are distinct sufficiently large odd primes with good statistical properties.

A number

n

is a square modulo

q

if and only if it is a square modulo each of the primes

p_{1}, . . ., p_{κ} .

By 4 given

a_{1}, . . ., a_{K}

and keeping

κ

, fixed as

min {p_{1}, . . ., p_{κ}} \to \infty

we have

\begin{matrix} P_{q} (ɛ_{1}, . . ., ɛ_{K}; a_{1}, . . ., a_{K}) \to {(\frac{1}{2^{κ}})}^{\sum_{i = 1}^{K} ɛ_{i}} {(1 - \frac{1}{2^{κ}})}^{K - \sum_{i = 1}^{K} ɛ_{i}}, \end{matrix}

(5)

that is, statistically squares modulo

q

look like outcomes of independent Bernoulli trials with probabilities

\frac{1}{2^{κ}}

and

(1 - \frac{1}{2^{κ}}) .

Without going into technical details of this fact from number theory, we just give an outline of a proof by induction on

κ

. For

κ = 1

, 5 follows from 4 . Suppose

κ > 1

and 5 holds for

κ - 1

. Set

q_{0} = p_{1} \cdot \cdot \cdot p_{κ - 1} .

For any possible choice of

ɛ^{'} = (ɛ_{1}^{'}, . . ., ɛ_{K}^{'})

and

ɛ^{''} = (ɛ_{1}^{''}, . . ., ɛ_{K}^{''})

, set

W (ɛ^{'}, ɛ^{''}) = {n : 0 \leq n < q, ɛ (n + a_{i}, q_{0}) = ɛ_{i}^{'} and ɛ (n + a_{i}, p_{κ}) = ɛ_{i}^{''} for i = 1, . . ., K}

W_{0} (ɛ^{'}) = {n : 0 \leq n < q_{0}, ɛ (n + a_{i}, q_{0}) = ɛ_{i}^{'} for i = 1, . . ., K},

and

W_{κ} (ɛ^{''}) = {n : 0 \leq n < p_{κ}, ɛ (n + a_{i}, p_{κ}) = ɛ_{i}^{''} for i = 1, . . ., K} .

Observe that for any

n

the numbers

n + j q_{0}

j = 0, . . ., p_{κ} - 1

hit each residue class modulo

p_{κ}

exactly once, and

ɛ (n + j q_{0} + a_{i}, q_{0}) = ɛ (n + a_{i}, q_{0})

for all

i

. Using this one can see that

W_{0} (ɛ^{'})

and

W_{κ} (ɛ^{''})

are independent in the sense that

# W (ɛ^{'}, ɛ^{''}) = # W_{0} (ɛ^{'}) # W_{κ} (ɛ^{''})

. For

ɛ = (ɛ_{1}, . . ., ɛ_{K})

, set

G (ɛ) = {n : 0 \leq n < q, ɛ (n + a_{i}, q) = ɛ_{i} for i = 1, . . ., K} .

Then

# G (ɛ) = \sum # W (ɛ^{'}, ɛ^{''})

, where the sum is taken over all pairs

(ɛ^{'}, ɛ^{''})

whose coordinatewise product is

ɛ

. Taking the limit as

min p_{1}, . . ., p_{κ}

goes to infinity of

# G (ɛ) / q

, using 4 for the limit of

# W_{κ} (ɛ^{''}) / p_{κ}

and 5 for the limit of

# W_{0} (ɛ^{'}) / q_{0}

, and noting that the only thing that matters in these limiting probabilites is the number of

1

's in the sequence, we have after setting

m = \sum_{i = 1}^{K} ɛ_{i}

, that the limiting value is

\frac{1}{2^{K}} \sum_{i = 0}^{K - m} (\binom{K - m}{i}) (\frac{1}{2^{κ - 1}})^{m} (1 - \frac{1}{2^{κ - 1}})^{i} = (\frac{1}{2^{κ}})^{m} (1 - \frac{1}{2^{κ}})^{K - m},

which is what we wanted.

Consider an infinite sequence of pairwise independent random variables

X_{i} : Y \to {0, 1}

with

P (X_{i} (ω) = 1) = \frac{1}{2^{κ}}

P (X_{i} (ω) = 0) = 1 - \frac{1}{2^{κ}} .

Then

E (X_{i} (ω)) = \frac{1}{2^{κ}} .

By the law of large numbers if

ρ > 0

and

K \to \infty

, then

P (| \frac{1}{K} \sum_{i = 1}^{K} X_{i} (ω) - \frac{1}{2^{κ}} | \geq ρ) \to 0 .

Given

ρ, ε_{1} > 0

K

is large enough, then

P (| \frac{1}{K} \sum_{i = 1}^{K} X_{i} (ω) - \frac{1}{2^{κ}} | \geq ρ) < ε_{1} .

For odd primes

p_{1} < p_{2} < . . . < p_{κ}

put

q = p_{1} \cdot \cdot \cdot p_{κ} .

Given distinct integers

a_{1}, . . ., a_{K}

consider

X_{i} (n) = ɛ (n + a_{i}, q)

. By 5 as

p_{1} \to \infty

the variables

X_{i} (n)

approximate independent random variables with Bernoulli distribution

\frac{1}{2^{κ}}

(1 - \frac{1}{2^{κ}})

. Hence, given a sufficiently large

K

p_{1}

is sufficiently large then

\frac{# {n \in [0, q) : | \frac{1}{K} \sum_{i = 1}^{K} ɛ (n + a_{i}, q) - \frac{1}{2^{κ}} | \geq ρ}}{q} < ε_{1} .

In particular, we have

\begin{matrix} # {n \in [0, q) : \sum_{i = 1}^{K} ɛ (n + a_{i}, q) \geq \frac{K}{2^{κ}} + K ρ} < ε_{1} q . \end{matrix}

(6)

For later arguments we now introduce some parameters. We will need a suitably small “leakage constant”

γ \in (0, 1)

of the form

γ = 2^{- c_{γ}}

where

c_{γ} \in N .

Then we work with

κ > c_{γ} .

Furthermore we use small constants

ρ, ρ_{1} > 0 .

For large

K_{1}

we have

\begin{matrix} K_{2} \overset{d e f}{=} ⌈ (1 + ρ_{1} 2^{κ}) γ K_{1} ⌉ < (1 + ρ_{1}) (1 + ρ_{1} 2^{κ}) γ K_{1} and γ 2^{κ} / K_{1} < ε_{1} . \end{matrix}

(7)

Thus for a large

K_{1}

we can choose

p_{1}^{'}

such that

\begin{matrix} p_{1}^{'} > max {K_{1} + γ 2^{κ}, K_{1} / ε_{1}} \end{matrix}

(8)

and, in addition if

p_{1} > p_{1}^{'}

we have for any

q = p_{1} \cdot \cdot \cdot p_{κ},

p_{1} < . . . < p_{κ}

\begin{matrix} # {n \in [0, q) : | \frac{1}{K_{1}} \sum_{i = 1}^{K_{1}} ɛ (n + i, q) - \frac{1}{2^{κ}} | \geq ρ} < ε_{1} q . \end{matrix}

(9)

Also, given any integers

a_{1}, . . ., a_{K_{2}}

so that the difference of any two of them is less than

p_{1}^{'}

we also have, after a simple change of notation in 6

\begin{matrix} # {n \in [0, q) : \sum_{i = 1}^{K_{2}} ɛ (- (n + a_{i}), q) \geq \frac{K_{2}}{2^{κ}} + K_{2} ρ_{1}} < ε_{1} q, \end{matrix}

(10)

the negative sign in the first argument of

ɛ (\cdot, q)

is due to technical reasons in later arguments; it is clear that if

n

takes all possible values modulo

q

then so does

- n .

Let

n_{1} \in [0, \infty)

be the first number for which

D (K_{1}, n_{1}, q) \overset{d e f}{=} | \frac{1}{K_{1}} \sum_{i = 1}^{K_{1}} ɛ (n_{1} + i, q) - \frac{1}{2^{κ}} | < ρ .

Next choose the least

n_{2} \geq n_{1} + K_{1}

such that

D (K_{1}, n_{2}, q) < ρ .

Continue and set

J = {j \in N : 0 \leq n_{j} < q} .

n^{'} \in [0, q) \ \cup_{j \in J} [n_{j}, n_{j} + K_{1})

, then

D (K_{1}, n^{'}, q) \geq ρ

should hold.

Hence, by 9

\begin{matrix} # {n \in [0, q) : n \notin ⋃_{j \in J} [n_{j}, n_{j} + K_{1})} < ε_{1} q . \end{matrix}

(11)

j \in J

then by the definition of

ɛ (n, q)

\begin{matrix} K_{1} (\frac{1}{2^{κ}} - ρ) < # (Λ_{0} (q) \cap [n_{j} + 1, n_{j} + K_{1}]) < K_{1} (\frac{1}{2^{κ}} + ρ), \end{matrix}

(12)

so that the number of quadratic residues modulo

q

in the interval

[n_{j} + 1, n_{j} + K_{1}]

is approximately

K_{1} / 2^{κ} .

Definition 2. Set

Λ γ (q) = - Λ_{0} (q) + {j \in Z : 0 \leq j < γ 2^{κ}},

\bar{Λ} γ (q) = Λ γ (q) + [0, 1) = - Λ_{0} (q) + {x : 0 \leq x < γ 2^{κ}} .

For ease of notation in the sequel if we have a fixed

γ

and we do not want to emphasize the dependence on

γ

we will write

Λ (q)

and

\bar{Λ} (q)

, instead of

Λ γ (q)

and

\bar{Λ} γ (q)

, respectively.

Remark 1. Here is a “heuristic” comment related to the above definition. If

Λ_{0} (q)

equalled

{k \cdot 2^{κ} : k \in Z}

, then

\bar{λ} (\bar{Λ} (q))

would equal

γ .

By results in [11] for a fixed

γ

κ

goes to

\infty

, the normalized gaps between consecutive elements of

Λ_{0} (q)

tends to a Poisson distribution. Since the normalizing factor is

σ_{q}

, the number of squares modulo

q

approximately equals

q / 2^{κ}

and the average value of the spacing between elements of

Λ_{0} (q)

is very close to

2^{κ}

, if

κ

and

p_{1}

are both sufficiently large. For some different elements

i, i^{'} \in Λ_{0} (q)

the intervals

[i, i + γ 2^{κ})

and

[i^{'}, i^{'} + γ 2^{κ})

might overlap.

This means that

\bar{λ} (\bar{Λ} (q))

might be less than

γ

, but the smaller

γ

is, the closer

\bar{λ} (\bar{Λ} (q)) / γ

is to

1

for large

q

's. We will take advantage of this property.

Lemma 2. Given a positive integer

κ

and

ε

ρ > 0

there exists

p_{1}^{'}

such that if the odd primes satisfy

p_{1}^{'} < p_{1} < . . . < p_{κ}

and

q = p_{1} \cdot \cdot \cdot p_{κ}

, then

\begin{matrix} # {n \in [0, q) : & # (((n + Λ_{0} (q)) \ Λ (q)) \cap [0, q)) < \end{matrix}

(13)

\begin{matrix} (1 - ρ) (1 - γ) # (Λ_{0} (q) \cap [0, q))} < ε q . \end{matrix}

\begin{matrix}  \end{matrix}

Remark 2. The heuristics behind 13 are the following. The number of

n \in [0, q)

for which

n \in Λ (q)

is a little less than

γ q

, due to “overlaps”. This means that the number of those

n

's for which

n \notin Λ (q)

is a little larger than

(1 - γ) q .

Now one can examine what happens when we look at translated copies of

Λ_{0} (q) .

Formula 13 says that for “most” translated copies of

Λ_{0} (q)

we cannot have much less than

(1 - γ) # (Λ_{0} (q) \cap [0, q))

elements of

n + Λ_{0} (q)

outside

Λ (q) .

Choose

ρ_{0} > 0

such that

\begin{matrix} (1 - \frac{1}{(1 - ρ_{0})^{2}} γ) > (1 - ρ) (1 - γ) . \end{matrix}

(14)

Recall from number theory that if

p_{1}^{'}

is sufficiently large we have

\begin{matrix} (1 - ρ_{0}) \frac{q}{2^{κ}} < # (Λ_{0} (q) \cap [0, q)) = σ_{q} < \frac{1}{(1 - ρ_{0})} \frac{q}{2^{κ}} . \end{matrix}

(15)

Proof. We can assume that

ε < 1 .

Take

0 < ε_{1} < ε^{2} / 32

and then choose

K_{1}

and

p_{1}^{'}

as above. By 8 and

q > p_{1}^{'}

we have

q > K_{1} / ε_{1}

and by 11

\begin{matrix} # {n \in [0, q) : n \notin ⋃_{j \in J} [n_{j}, n_{j} + K_{1})} < ε_{1} q \end{matrix}

(16)

for a suitable index set

J

, defined above, and for each

j \in J

we have

D (K_{1}, n_{j}, q) < ρ_{1}

for a suitable

ρ_{1} > 0 .

This means that

\begin{matrix} K_{1} (\frac{1}{2^{κ}} - ρ_{1}) < # (Λ_{0} (q) \cap [n_{j} + 1, n_{j} + K_{1}]) < K_{1} (\frac{1}{2^{κ}} + ρ_{1}) . \end{matrix}

(17)

By Definition 2 for

n \in [0, q)

we have

n + n^{'} \in Λ (q)

n + n^{'} - i \in - Λ_{0} (q)

holds for an

i = 0, . . ., γ 2^{κ} - 1 .

Set

Λ_{0}^{j} (q) = Λ_{0} (q) \cap [n_{j} + 1, n_{j} + K_{1}]

and

Λ^{j} (q) = - (^{γ 2^{κ} - 1} ⋃_{i = 0} (Λ_{0}^{j} (q) - i))

for each

j \in J .

Using the definition of

K_{2}

in 7 , and 17 choose distinct numbers

a_{i^{'}, j}

i^{'} = 1, . . ., K_{2}

, so that

- Λ^{j} (q) =^{γ 2^{κ} - 1} ⋃_{i = 0} Λ_{0}^{j} (q) - i \subseteq A_{j} {\overset{d e f}{=}}^{K_{2}} ⋃_{i^{'} = 1} {a_{i^{'}, j}} \subset [n_{j} - γ 2^{κ}, n_{j} + K_{1}] .

Clearly, by the choice of

p_{1}^{'}

in 8 the difference of any two of the

a_{i^{'}, j}

's is less than

p_{1}^{'}

. This implies

(n + Λ_{0} (q)) \cap Λ^{j} (q) \subset (n + Λ_{0} (q)) \cap (- A_{j}) .

Observe that there exists

n^{'} \in Λ_{0} (q)

such that

n + n^{'} \in - A_{j}

if and only if there exists

i^{'}

such that

n + n^{'} = - a_{i^{'}, j}

, that is,

n + a_{i^{'}, j} = - n^{'} \in - Λ_{0} (q) .

Recall that

n + a_{i^{'}, j} \in - Λ_{0} (q)

if and only if

ɛ (- (n + a_{i^{'}, j}), q) = 1 .

Set

N_{j} = {n \in [0, q) : \sum_{i^{'} = 1}^{K_{2}} ɛ (- (n + a_{i^{'}, j}), q) \geq K_{2} (\frac{1}{2^{κ}} + ρ_{1})} .

n \notin N_{j}

n \in [0, q)

then

\begin{matrix} # ((n + Λ_{0} (q)) \cap Λ^{j} (q)) < K_{2} (\frac{1}{2^{κ}} + ρ_{1}) . \end{matrix}

(18)

By 10

\begin{matrix} # N_{j} < ε_{1} q . \end{matrix}

(19)

Here we remark that 10 can be used so that we have 19 for all

j \in J .

Indeed, assume

A \subset [- γ 2^{κ}, K_{1}]

and

A + n_{j} = A_{j}

then

N_{j} = N_{A} \overset{d e f}{=} {n \in [0, q) : \sum_{a \in A} ɛ (- (n + a), q) \geq K_{2} (\frac{1}{2^{κ}} + ρ_{1})} .

There are

2^{γ 2^{κ} + K_{1} + 1}

subsets of

[- γ 2^{κ}, K_{1}]

. So, we can choose

p_{1}^{'}

before 10 so that we have

# N_{A} < ε_{1} q

for all subsets

A

[- γ 2^{κ}, K_{1}] .

n \notin N_{j}

n \in [0, q)

then by 7 and 18

\begin{matrix} # ((n + Λ_{0} (q)) \cap Λ^{j} (q)) & < K_{2} (\frac{1}{2^{κ}} + ρ_{1}) < \end{matrix}

(20)

\begin{matrix} (1 + ρ_{1}) (1 + ρ_{1} 2^{κ}) γ K_{1} (\frac{1}{2^{κ}} + ρ_{1}) . \end{matrix}

\begin{matrix}  \end{matrix}

On the other hand, by 16

\begin{matrix} \frac{q - ε_{1} q}{K_{1}} \leq # J < \frac{q}{K_{1}} + 1 . \end{matrix}

(21)

For

0 \leq n < q

set

J (n) = {j \in J : n \notin N_{j}}

Consider an

n

such that

\begin{matrix} # J (n) > q \frac{1 - ε_{1}}{K_{1}} (1 - \sqrt{ε_{1}}) . \end{matrix}

(22)

Later we show that for most

n

's this inequality holds.

Observe that if

x \in [- (n_{j} + K_{1}) + γ 2^{κ} - 1, - n_{j} - 1] \cap Λ (q)

then there exists

i \in {0, . . ., γ 2^{κ} - 1}

such that

x - i \in - Λ_{0} (q)

and

x - i \in [- (n_{j} + K_{1}), - n_{j} - 1]

, that is,

x - i \in - Λ_{0}^{j} (q)

and hence

x \in Λ^{j} (q) .

Therefore,

[- (n_{j} + K_{1}) + γ 2^{κ} - 1, - n_{j} - 1] \cap Λ (q) \subset Λ^{j} (q) .

We want to estimate

# (((n + Λ_{0} (q)) \ Λ (q)) \cap [0, q)) = # (((n + Λ_{0} (q)) \ Λ (q)) \cap (- q, 0]) .

By 20 for any

j \in J (n)

\begin{matrix} # ((n + Λ_{0} (q)) \cap & Λ (q) \cap [- (n_{j} + K_{1}) + γ 2^{κ} - 1, - n_{j} - 1) < \end{matrix}

(23)

\begin{matrix} (1 + ρ_{1}) (1 + ρ_{1} 2^{κ}) γ K_{1} (\frac{1}{2^{κ}} + ρ_{1}) . \end{matrix}

\begin{matrix}  \end{matrix}

Put

T_{n} = {t \in Z : t \in (- q, 0] \ ⋃_{j \in J (n)} [- (n_{j} + K_{1}) + γ 2^{κ} - 1, - n_{j} - 1]} .

It is clear that

\begin{matrix} (n + Λ_{0} (q)) \cap Λ (q) \cap (- q, 0] \subset \end{matrix}

(24)

\begin{matrix} T_{n} \cup ⋃_{j \in J (n)} (n + Λ_{0} (q)) \cap Λ (q) \cap [- (n_{j} + K_{1}) + γ 2^{κ} - 1, - n_{j} - 1] . \end{matrix}

\begin{matrix}  \end{matrix}

We need to estimate

# T_{n}

. Since the intervals

[- (n_{j} + K_{1}), - n_{j} - 1]

are disjoint and, with the possible exception of the one with the largest index, are subsets of

(- q, 0]

we have by using 7 and 22

# T_{n} < q - # J (n) (K_{1} - γ 2^{κ}) < q - # J (n) (1 - ε_{1}) K_{1} <

q - q \frac{(1 - ε_{1})^{2}}{K_{1}} (1 - \sqrt{ε_{1}}) K_{1} = q (1 - (1 - ε_{1})^{2} (1 - \sqrt{ε_{1}})) < q c_{1} (ε_{1}),

where

c_{1} (ε_{1}) \to 0

ε_{1} \to 0 .

Now we use this, 23 and 24 to estimate

# ((n + Λ_{0} (q)) \cap Λ (q) \cap (- q, 0]) <

# J (n) \cdot (1 + ρ_{1}) (1 + ρ_{1} 2^{κ}) γ K_{1} (\frac{1}{2^{κ}} + ρ_{1}) + q c_{1} (ε_{1}) <

(using 21 )

(\frac{q}{K_{1}} + 1) (1 + ρ_{1}) (1 + ρ_{1} 2^{κ}) γ K_{1} (\frac{1}{2^{κ}} + ρ_{1}) + q c_{1} (ε_{1}) =

(1 + \frac{K_{1}}{q}) (1 + ρ_{1}) (1 + ρ_{1} 2^{κ})^{2} γ q \frac{1}{2^{κ}} + q c_{1} (ε_{1}) <

(using 8 and

q > p_{1}^{'} > K_{1} / ε_{1}

)

(1 + ε_{1}) (1 + ρ_{1}) (1 + ρ_{1} 2^{κ})^{2} γ q \frac{1}{2^{κ}} + q c_{1} (ε_{1}) =

((1 + ε_{1}) (1 + ρ_{1}) (1 + ρ_{1} 2^{κ})^{2} + \frac{2^{κ}}{γ} c_{1} (ε_{1})) γ q \frac{1}{2^{κ}} = c_{2} (ε_{1}, ρ_{1}) γ q \frac{1}{2^{κ}},

where

c_{2} (ε_{1}, ρ_{1}) \to 1

ε_{1}, ρ_{1} \to 0 .

We can choose

ε_{1}, ρ_{1} > 0

so that

c_{2} (ε_{1}, ρ_{1}) < \frac{1}{(1 - ρ_{0})} .

This by 15 implies

c_{2} (ε_{1}, ρ_{1}) γ q \frac{1}{2^{κ}} < \frac{1}{(1 - ρ_{0})^{2}} γ # (Λ_{0} (q) \cap [0, q)) .

By 14 we obtain

\begin{matrix} # (((n + Λ_{0} (q)) \ Λ (q)) \cap [0, q)) > \end{matrix}

(25)

\begin{matrix} # (Λ_{0} (q) \cap [0, q)) (1 - \frac{1}{(1 - ρ_{0})^{2}} γ) > # (Λ_{0} (q) \cap [0, q)) (1 - ρ) (1 - γ) . \end{matrix}

\begin{matrix}  \end{matrix}

To prove 13 we need to show that there are sufficiently many

n

's which satisfy the above inequality.

Let

b

be the number of

n

's for which

\begin{matrix} # J (n) \leq q \frac{1 - ε_{1}}{K_{1}} (1 - \sqrt{ε_{1}}) . \end{matrix}

(26)

If we can show that

b < ε q

, then we have finished the proof of Lemma 2 since if 22 holds for an

n

then we have 25 . If

n

satisfies 26 then by the definition of

J (n)

from 21 we infer that

n \in N_{j}

for at least

\sqrt{ε_{1}} \frac{1 - ε_{1}}{K_{1}} q

many

j

's.

Hence, using 19 and 21

b \sqrt{ε_{1}} \frac{1 - ε_{1}}{K_{1}} q \leq \sum_{j \in J} # N_{j} \leq ε_{1} q (\frac{q}{K_{1}} + 1) < \frac{2 ε_{1} q^{2}}{K_{1}}

which implies

b \leq \frac{2 \sqrt{ε_{1}}}{1 - ε_{1}} q < ε q .

3 Periodic rearrangements

Assume

F \subset R

is periodic by

τ^{'} \in N

and if

x \in F

then

[⌊ x ⌋, ⌊ x ⌋ + 1) \subset F .

Given a natural number

τ > τ^{'}

, the

τ

-periodic rearrangement of

F

is denoted by

F^{τ}

and it is periodic by

τ,

and

F^{τ} \cap [0, τ) = [0, ⌊ τ / τ^{'} ⌋ \cdot τ^{'}) \cap F .

Lemma 3. Given

τ^{'},

F,

ρ > 0

there exists

M_{ρ}

such that if

τ > M_{ρ}

is a prime number then for any

n \in N

and

x \in R

, if

τ | m

then

\begin{matrix} \frac{1}{m} \sum_{k = n}^{n + m - 1} χ_{F^{τ}} (x + k^{2}) \geq (1 - ρ) \bar{λ} (F) . \end{matrix}

(27)

Proof. It is enough to show the lemma if

τ = m .

Furthermore,

χ_{F^{τ}}

is periodic by

τ

and if

x \in F^{τ}

then

[⌊ x ⌋, ⌊ x ⌋ + 1) \subset F^{τ}

. Hence it is sufficient to verify 27 for

n = 1,

since

{n, n + 1, . . ., n + τ - 1}

forms a complete residue system modulo

τ

for any choice of

n

Given

ε^{'}, ρ^{'} > 0

choose

K

such that if

X_{i} (ω)

are independent random variables with

P (X_{i} (ω) = 1) = P (X_{i} (ω) = 0) = \frac{1}{2}

, then

P (| \frac{1}{K} \sum_{i = 1}^{K} X_{i} (ω) - \frac{1}{2} | \geq ρ^{'}) < ε^{'} .

Now, set

X_{i, j} (n^{'}) = ɛ (n^{'} + j + i τ^{'}, τ)

. We use some results from [15] .

There exists

M_{ρ^{'}}^{''} > K

such that if the prime number

τ > M_{ρ^{'}}^{''},

then for all

j = 0, . . ., τ^{'} - 1

# {n^{'} \in [0, τ) : | \frac{1}{K} \sum_{i = 1}^{K} ɛ (n^{'} + j + i τ^{'}, τ) - \frac{1}{2} | \geq ρ^{'}} < ε^{'} τ .

We conclude

\begin{matrix} # {n^{'} \in [0, τ) : {max}_{j = 0, . . ., τ^{'} - 1} | \frac{1}{K} \sum_{i = 1}^{K} ɛ (n^{'} + j + i τ^{'}, τ) - \frac{1}{2} | \geq ρ^{'}} < τ^{'} ε^{'} τ . \end{matrix}

(28)

We can also suppose that

M_{ρ^{'}}^{''}

is so large that for all

τ > M_{ρ^{'}}^{''}

we have

\begin{matrix} τ^{'} (K + 2) < min {ε^{'} τ^{'} τ, τ} . \end{matrix}

(29)

By 28 there exists

E_{0}

periodic by

τ

such that if

n^{'} \notin E_{0}

, then for all

j = 0, . . ., τ^{'} - 1

\begin{matrix} \sum_{i = 1}^{K} ɛ (n^{'} + j + i τ^{'}, τ) > (\frac{1}{2} - ρ^{'}) K \end{matrix}

(30)

and

\begin{matrix} # (E_{0} \cap [0, τ)) < τ^{'} ε^{'} τ . \end{matrix}

(31)

Recall that if

n^{'} + j + i τ^{'} ≢ 0

m o d

τ

and

ɛ (n^{'} + j + i τ^{'}, τ) = 1

, then there are two solutions of

k^{2} \equiv n^{'} + j + i τ^{'}

modulo

τ .

Assume

x \in R

is arbitrary. Consider

⌊ x ⌋ + k^{2}

. If

n^{'} \notin E_{0} + ⌊ x ⌋

, then 30 implies that for all

j = 0, . . ., τ^{'} - 1

\begin{matrix} \sum_{i = 1}^{K} ɛ (- ⌊ x ⌋ + n^{'} + j + i τ^{'}, τ) > (\frac{1}{2} - ρ^{'}) K . \end{matrix}

(32)

ɛ (- ⌊ x ⌋ + n^{'} + j + i τ^{'}, τ) = 1,

then there exists

k

such that

k^{2} \equiv - ⌊ x ⌋ + n^{'} + j + i τ^{'}

m o d

τ

, that is,

⌊ x ⌋ + k^{2} \equiv n^{'} + j + i τ^{'}

and if

- ⌊ x ⌋ + n^{'} + j + i τ^{'} ≢ 0

modulo

τ

we have two solutions

m o d

τ .

Let

N_{1}^{'} \in (0, τ)

be the least element of

(Z \ E_{0}) + ⌊ x ⌋ \cap [0, τ - τ^{'} (K + 2)) .

Given

N_{s - 1}^{'}

choose

N_{s}^{'}

so that it is the least element of

(Z \ E_{0}) + ⌊ x ⌋ \cap [N_{s - 1}^{'} + τ^{'} (K + 1), τ - τ^{'} (K + 2))

in case this set is nonempty. After

S

many steps the previous set is empty and we stop and obtain

N_{1}^{'}, . . ., N_{S}^{'} .

Then

\begin{matrix} (Z \cap [0, τ - τ^{'} (K + 2))) \^{S} ⋃_{l = 1} [N_{l}^{'}, N_{l}^{'} + τ^{'} (K + 1)) \subset E_{0} + ⌊ x ⌋ . \end{matrix}

(33)

Hence, by 29 and 31 , if

τ

is sufficiently large

\begin{matrix} # ((Z \cap [0, τ)) \^{S} ⋃_{l = 1} [N_{l}^{'}, N_{l}^{'} + τ^{'} (K + 1))) < 2 ε^{'} τ^{'} τ . \end{matrix}

(34)

Recalling that for any

n^{''} \in Z

we have at most two solutions of

⌊ x ⌋ + k^{2} \equiv n^{''}

m o d

τ

we obtain

# {k \in [0, τ) \cap Z : ⌊ x ⌋ + k^{2} \notin^{S} ⋃_{l = 1} [N_{l}^{'}, N_{l}^{'} + τ^{'} (K + 1)) + τ Z} < 4 ε^{'} τ^{'} τ .

Let

K_{l} = {k \in [0, τ) \cap Z : ⌊ x ⌋ + k^{2} \in [N_{l}^{'}, N_{l}^{'} + τ^{'} (K + 1)) + τ Z} .

To verify 27 we need to estimate

\sum_{k = 1}^{τ} χ_{F^{τ}} (x + k^{2}) .

In 38 we will consider subsums

\sum_{k \in K_{l}} χ_{F^{τ}} (x + k^{2}) .

N_{l}^{'} + j \in F^{τ}

for a

j \in {0, . . ., τ^{'} - 1}

, then

N_{l}^{'} \in [0, τ - τ^{'} (K + 2))

and

N_{l}^{'} + j + i τ^{'} \in [N_{l}^{'}, N_{l}^{'} + τ^{'} (K + 1)) \subset [0, τ - τ^{'})

for

i = 1, . . ., K

which, recalling that

F

is periodic by

τ^{'}

and since

τ - τ^{'} \leq ⌊ τ / τ^{'} ⌋ \cdot τ^{'},

F^{τ} \cap [0, τ - τ^{'}) = F \cap [0, τ - τ^{'})

, we have

N_{l}^{'} + j + i τ^{'} \in F^{τ} .

This means that from

χ_{F^{τ}} (N_{l}^{'} + j) = 1

, it follows that

χ_{F^{τ}} (N_{l}^{'} + j + i τ^{'}) = 1

for

i = 1, . . ., K .

If for an

i

ɛ (- ⌊ x ⌋ + N_{l}^{'} + j + i τ^{'}, τ) = 1

and

- ⌊ x ⌋ + N_{l}^{'} + j + i τ^{'} ≢ 0

modulo

τ

, then there exist exactly two

k_{1}

k_{2}

, different modulo

τ

, such that

\begin{matrix} ⌊ x ⌋ + k_{1}^{2} \equiv ⌊ x ⌋ + k_{2}^{2} \equiv N_{l}^{'} + j + i τ^{'} m o d τ . \end{matrix}

(35)

For

x,

N_{l}^{'},

j

fixed there is at most one

i \in {1, . . ., K}

for which

- ⌊ x ⌋ + N_{l}^{'} + j + i τ^{'} \equiv 0

m o d

τ .

Hence for the other

K - 1

values we have two solutions of 35 whenever

ɛ (- ⌊ x ⌋ + N_{l}^{'} + j + i τ^{'}, τ) = 1

. For these solutions,

k_{1}

and

k_{2}

, we have

\begin{matrix} χ_{F^{τ}} (x + k_{1}^{2}) = χ_{F^{τ}} (x + k_{2}^{2}) = 1 . \end{matrix}

(36)

Using again that

F

is periodic by

τ^{'}

and by the definition of

F^{τ}

we have

F \cap [N_{l}^{'}, N_{l}^{'} + τ^{'} - 1) = F^{τ} \cap [N_{l}^{'}, N_{l}^{'} + τ^{'} - 1)

we infer

\begin{matrix} # {j : N_{l}^{'} + j \in F^{τ}, j = 0, . . ., τ^{'} - 1} = \bar{λ} (F) τ^{'} . \end{matrix}

(37)

By 31 , 33 and 34 it is clear that if

ε^{'}

is sufficiently small, with

K

and

τ

are sufficiently large, we have

S τ^{'} (K - 1) = S τ^{'} (K + 1) (1 - \frac{2}{K + 1}) > (1 - ρ^{'}) τ .

If we add 32 with

n^{'} = N_{l}^{'}

for all

j = 0, . . ., τ^{'} - 1

by using 36 and 37 we find

\begin{matrix} \sum_{k \in K_{l}} χ_{F^{τ}} (x + k^{2}) \geq 2 (\frac{1}{2} - ρ^{'}) (K - 1) τ^{'} \bar{λ} (F) . \end{matrix}

(38)

Adding 38 for all

l = 1, . . ., S

\sum_{k = 1}^{τ} χ_{F^{τ}} (x + k^{2}) \geq S \cdot 2 (\frac{1}{2} - ρ^{'}) (K - 1) τ^{'} \bar{λ} (F) > 2 (\frac{1}{2} - ρ^{'}) (1 - ρ^{'}) τ \bar{λ} (F) .

Therefore, if

ρ^{'}

is chosen to be sufficiently small, we have

\frac{1}{τ} \sum_{k = 1}^{τ} χ_{F^{τ}} (x + k^{2}) > (1 - ρ) \bar{λ} (F) .

4 $K - M$ families

Definition 3. For a positive integer

M

we say that a periodic function or a “random variable”,

X : R \to R

is conditionally

M

-

0.99

distributed on the set

Λ

, which is periodic by the same period, if

X (x) \in {0, 0.99, 0.99 \cdot \frac{1}{2}, . . ., 0.99 \cdot 2^{- M + 1}}

, and

\bar{λ} ({x \in Λ : X (x) = 0.99 \cdot 2^{- l}}) = 0.99 \cdot 2^{- M + l - 1} \bar{λ} (Λ)

for

l = 0, . . ., M - 1 .

(We regard

R

as being periodic by

1

with

\bar{λ} (R) = 1

and if

Λ = R

then we just simply say that

X

M

-

0.99

-distributed.) By an obvious adjustment this definition will also be used for random variables

\bar{X}

defined on

[0, 1)

equipped with the Lebesgue measure

λ .

If we have two “random variables”

X_{1}

and

X_{2}

both conditionally

M

-

0.99

distributed on

Λ

then they are called pairwise independent (on

Λ

) if for any

y_{1}, y_{2} \in R

\begin{matrix} \bar{λ} {x \in Λ & : X_{1} (x) = y_{1} and X_{2} (x) = y_{2}} \bar{λ} (Λ) = \end{matrix}

(39)

\begin{matrix} \bar{λ} ({x \in Λ : X_{1} (x) = y_{1}}) \bar{λ} ({x \in Λ : X_{2} (x) = y_{2}}) \end{matrix}

\begin{matrix} or, equivalently, \bar{λ} {x \in Λ & : X_{1} (x) = y_{1} and X_{2} (x) = y_{2}} / \bar{λ} (Λ) = \end{matrix}

\begin{matrix} (\bar{λ} ({x \in Λ : X_{1} (x) = y_{1}}) / \bar{λ} (Λ)) (\bar{λ} ({x \in Λ : X_{2} (x) = y_{2}}) / \bar{λ} (Λ)) \end{matrix}

\begin{matrix}  \end{matrix}

If we say that

X_{1}

and

X_{2}

are pairwise independent, without specifying

Λ

then we mean

Λ = R

We will use the following simple properties. Assume

Λ_{1}

and

Λ_{2}

are two disjoint sets with a common period. If

X_{1}

and

X_{2}

are conditionally

M

-

0.99

distributed on

Λ_{1}

and on

Λ_{2}

, then

X_{1}

(and similarly

X_{2}

) is conditionally

M

-

0.99

distributed on

Λ_{1} \cup Λ_{2}

. If, in addition

X_{1}

and

X_{2}

are pairwise independent on each

Λ_{1}

and

Λ_{2}

, then

X_{1}

and

X_{2}

are pairwise independent on

Λ_{1} \cup Λ_{2}

. We note the last property depends on

X_{1}

and

X_{2}

having the same distribution on

Λ_{1}

and

Λ_{2}

. Similar properties hold if we have finitely many functions

X_{1}, . . ., X_{K}

with the same conditional distribution.

Definition 4. We say that a set

P \subset N

has sufficiently large complement if there are infinitely many primes relatively prime to any number in

P .

Definition 5. Assume

q = p_{1} \cdot \cdot \cdot p_{κ}

, where

p_{1} < . . . < p_{κ}

are odd primes. Set

Λ_{0}^{'} (q) = {n \in Λ_{0} (q) : p_{j} |̸ n, for all j = 1, . . ., κ} .

n \in Λ_{0}^{'} (q)

, then there are

2^{κ}

many solutions of

x^{2} \equiv n

m o d

q

, also observe that for fixed

κ

\begin{matrix} if p_{1} \to \infty, then \frac{# (Λ_{0} (q) \cap [0, q))}{# (Λ_{0}^{'} (q) \cap [0, q))} \to 1 . \end{matrix}

(40)

Given

γ \in (0, 1)

we also put

Λ_{γ}^{'} (q) = - Λ_{0}^{'} (q) + {j \in Z : 0 \leq j < γ 2^{κ}},

{\bar{Λ}}_{γ}^{'} (q) = Λ_{γ}^{'} (q) + [0, 1) = - Λ_{0}^{'} (q) + {x : 0 \leq x < γ 2^{κ}} .

In the sequel often if

γ

is fixed we will suppress the dependence on

γ

by writing

Λ^{'} (q)

and

{\bar{Λ}}^{'} (q)

instead of

Λ_{γ}^{'} (q)

and

{\bar{Λ}}_{γ}^{'} (q)

, respectively.

Definition 6. Suppose

K, M \in N

Λ \subset R

is periodic by

\tilde{q} .

There is a parameter

γ^{'}

associated to

Λ

. (If

Λ = R

then

\tilde{q} = γ^{'} = 1

Otherwise one should think of

Λ = {\bar{Λ}}_{γ^{'}}^{'} (\tilde{q})

and

γ^{'}

is the parameter used in the definition of

Λ

.) In the sequel we assume that

P \subset N

has sufficiently large complement. A

K - M

family living on

Λ

with input parameters

δ > 0,

Ω

Γ > 1

A \in N,

P

with output objects

τ

f_{h}

f_{h, x}

X_{h}

(

h = 1, . . ., K

);

E_{δ}

ω (x)

α (x)

and

τ (x)

is a system satisfying:

(i) There exist a period $τ$ , functions $f_{h} : R \to [0, \infty)$ , pairwise independent, conditionally $M$ $-$ $0.99$ -distributed on $Λ$ “random” variables $X_{h} : R \to R$ , for $h = 1, . . ., K,$ and a set $E_{δ}$ such that all these objects are periodic by $τ$ where $τ$ is an integer multiple of $\tilde{q}$ .

(ii) We have

\bar{λ} (E_{δ}) < δ

. For all

x \notin E_{δ}

, there exist

0 \leq f_{h, x} \leq f_{h}

ω (x) > α (x) > A,

τ (x) < τ

such that

ω^{2} (x) < τ,

\frac{ω (x)}{α (x)} > Ω \cdot τ (x)

; moreover if

α (x) \leq n < n + m \leq ω (x)

and

τ (x) | m

, then for all

h = 1, . . ., K,

\begin{matrix} \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h} (x + k^{2}) \geq \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, x} (x + k^{2}) > X_{h} (x) . \end{matrix}

(41)

(iii) For all $p \in P$ , $(τ (x), p) = 1,$ $(τ, p) = 1 .$

(iv) For all

x \in Λ \ E_{δ}

, for all

h \in {1, . . ., K}

\begin{matrix} f_{h, x} (x + j + τ (x)) = f_{h, x} (x + j) \end{matrix}

(42)

whenever

α^{2} (x) \leq j < j + τ (x) \leq ω^{2} (x) .

(v) Finally, for $h = 1, . . ., K$ $\frac{1}{τ} \int_{0}^{τ} f_{h} = \int^{¯} f_{h} < Γ \cdot γ^{'} \cdot 2^{- M + 1} .$

Remark 3. The input parameters in the above definition should be regarded as something given in advance while the output objects are defined and constructed later. The most important property is 41 , while the numerous other technical properties are needed in order to verify by mathematical induction the existence of

K - M

families.

x

is not in the exceptional set

E_{δ}

then 41 says that the average over multiples of

τ (x)

of each

f_{h}

along squares staying in the window

[α (x), ω (x)]

dominates

X_{h} (x) .

The auxiliary functions

f_{h, x}

are technical aides carried along in the induction argument to ensure this domination. In 42 we claim that these functions appear to be periodic in the window

[α^{2} (x), β^{2} (x)],

that is, when squares stay in the window

[α (x), β (x)] .

Lemma 4. Let

M \in N

Λ = R

(this implies

\tilde{q} = γ^{'} = 1

). Then for each positive integer

K

and parameters

δ > 0,

Ω, Γ > 1

A \in N,

and

P \subset N

such that

P

has sufficiently large complement there exist a

K - M

family living on

R

4.1 Putting $K - M$ families on quadratic residue classes

The proof of Lemma 4 is quite involved. It will be done by mathematical induction. In this section we assume that

K - M

families on

R

exist for a fixed

K \in N

for all possible parameter values.

We will use the following lemma about “putting a

K - M

-family on a residue class”. We assume that

\bar{P}

is a set of natural numbers with sufficiently large complement and we have a number

\tilde{q}

such that

\begin{matrix} (\tilde{q}, p) = 1 for all p \in \bar{P}, \tilde{q} = p_{0, 1} \cdot \cdot \cdot p_{0, κ}, \end{matrix}

(43)

and

p_{0, 1} < . . . < p_{0, κ}

are odd primes.

We also assume that a constant

γ = 2^{- c_{γ}}

, the so called “leakage constant” is given with

c_{γ} \in N

and

κ > c_{γ}

. This

γ

is used in the definition of

{\bar{Λ}}^{'} (\tilde{q}) = {\bar{Λ}}_{γ}^{'} (\tilde{q})

Lemma 5. Let

M \in N

be given and suppose for some

K \in N

that

K - M

families exist on

R

for all possible parameter values.

Suppose that

\bar{P}

\tilde{q}

and the parameter

γ

associated to

{\bar{Λ}}^{'} (\tilde{q})

satisfy the above assumptions. In addition, let

δ > 0,

Ω, Γ > 1

, and

A \in N

be given. Then for the above input parameters there exists a

K - M

family living on

{\bar{Λ}}^{'} (\tilde{q})

with output objects

\bar{τ}

{\bar{f}}_{h}

{\bar{f}}_{h, x}

{\bar{X}}_{h}

(

h = 1, . . ., K

);

{\bar{E}}_{δ}

\bar{ω} (x)

\bar{α} (x)

and

\bar{τ} (x)

Proof. Using

P = \bar{P} \cup {\tilde{q}}

, choose a

K - M

family living on

R

with input parameters

δ,

Ω^{'} = Ω \tilde{q},

Γ,

A .

This

K - M

family provides us with

τ

f_{h}

f_{h, x}

X_{h}

E_{δ},

ω (x),

α (x)

, and

τ (x)

, satisfying (i)-(v) of Definition 6 . Especially,

\begin{matrix} for all p \in \bar{P} \cup {\tilde{q}} we have (τ (x), p) = 1 and (τ, p) = 1 . \end{matrix}

(44)

We construct a new

K

-system marked by overlines which lives on

{\bar{Λ}}^{'} (\tilde{q})

and is periodic by

\bar{τ} = τ \tilde{q}

Set

{\bar{f}}_{h} (x) = f_{h} (x) \tilde{q} / 2^{κ}

x \in [j \tilde{q}, j \tilde{q} + γ 2^{κ})

for a

j \in Z

, otherwise put

{\bar{f}}_{h} (x) = 0 .

Then

{\bar{f}}_{h}

is periodic by

τ \tilde{q}

Next we define

{\bar{X}}_{h} (x)

so that

{\bar{X}}_{h} (x) = X_{h} (x)

for

x \in {\bar{Λ}}^{'} (\tilde{q})

, and otherwise let

{\bar{X}}_{h} (x) = 0 .

Clearly,

{\bar{X}}_{h}

is periodic by

\tilde{q}

and is supported on

{\bar{Λ}}^{'} (\tilde{q})

Next we check the distribution of

{\bar{X}}_{h} (x) |_{{\bar{Λ}}^{'} (\tilde{q})} .

We know that

X_{h} (x + τ) = X_{h} (x)

. Since from 44 it follows that

(τ, \tilde{q}) = 1

the numbers

j τ

j = 0, . . ., \tilde{q} - 1

cover all residue classes modulo

\tilde{q} .

Now we can compute

\bar{λ} ({x \in {\bar{Λ}}^{'} (\tilde{q}) : {\bar{X}}_{h} (x) = 0.99 \cdot 2^{- l}}) =

\bar{λ} ({x \in R : {\bar{X}}_{h} (x) = 0.99 \cdot 2^{- l}}) =

\frac{1}{τ \tilde{q}} λ ({x \in [0, τ \tilde{q}) : {\bar{X}}_{h} (x) = 0.99 \cdot 2^{- l}}) =

\frac{1}{τ \tilde{q}} \sum_{j = 0}^{\tilde{q} - 1} λ ({x \in [j τ, (j + 1) τ) : {\bar{X}}_{h} (x) = 0.99 \cdot 2^{- l}}) =

\frac{1}{τ \tilde{q}} \sum_{j = 0}^{\tilde{q} - 1} λ ({x \in [0, τ) : {\bar{X}}_{h} (x + j τ) = 0.99 \cdot 2^{- l}}) =

\frac{1}{τ \tilde{q}} (# Λ^{'} (\tilde{q}) \cap [0, \tilde{q})) \cdot λ ({x \in [0, τ) : X_{h} (x) = 0.99 \cdot 2^{- l}}) =

(using that

# (Λ^{'} (\tilde{q}) \cap [0, \tilde{q})) / \tilde{q} = \bar{λ} ({\bar{Λ}}^{'} (\tilde{q}))

)

\bar{λ} ({\bar{Λ}}^{'} (\tilde{q})) \cdot \bar{λ} ({x \in R : X_{h} (x) = 0.99 \cdot 2^{- l}}) = \frac{1}{τ} \bar{λ} ({\bar{Λ}}^{'} (\tilde{q})) τ \cdot 0.99 \cdot 2^{- M + l - 1} =

\bar{λ} ({\bar{Λ}}^{'} (\tilde{q})) \cdot 0.99 \cdot 2^{- M + l - 1} .

Thus the “conditional distribution” of

{\bar{X}}_{h}

{\bar{Λ}}^{'} (\tilde{q})

M

-

0.99 .

Set

ϒ = {0, 0.99, 0.99 \cdot 2^{- 1}, . . ., 0.99 \cdot 2^{- M + 1}}

and

ϒ_{+} = ϒ \ {0} .

Next we show that the functions

{\bar{X}}_{h}

are pairwise independent on

{\bar{Λ}}^{'} (\tilde{q})

. Suppose

h_{1} \neq h_{2}

. First assume

y_{1}, y_{2} \in ϒ_{+}

. Then the above argument shows

\begin{matrix} \bar{λ} ({x \in {\bar{Λ}}^{'} (\tilde{q}) : {\bar{X}}_{h_{j}} (x) = y_{j}}) = \bar{λ} ({x \in R : X_{h_{j}} (x) = y_{j}}) \bar{λ} ({\bar{Λ}}^{'} (\tilde{q})) \end{matrix}

(45)

for

j = 1, 2 .

A similar argument shows

\begin{matrix} \bar{λ} ({x \in {\bar{Λ}}^{'} (\tilde{q}) : {\bar{X}}_{h_{1}} (x) = y_{1} and {\bar{X}}_{h_{2}} (x) = y_{2}}) = \end{matrix}

(46)

\begin{matrix} \bar{λ} ({x \in R : X_{h_{1}} (x) = y_{1} and X_{h_{2}} (x) = y_{2}}) \bar{λ} ({\bar{Λ}}^{'} (\tilde{q})) . \end{matrix}

\begin{matrix}  \end{matrix}

The range of

{\bar{X}}_{h_{j}}

and

X_{h_{j}}

equals

ϒ = ϒ_{+} \cup {0}

and 45 holds for all

y_{j} \in ϒ_{+}

. Therefore,

\begin{matrix} \bar{λ} ({x \in {\bar{Λ}}^{'} (\tilde{q}) : {\bar{X}}_{h_{j}} (x) = 0}) = \bar{λ} ({x \in R : X_{h_{j}} (x) = 0}) \bar{λ} ({\bar{Λ}}^{'} (\tilde{q})) \end{matrix}

(47)

should also hold for

j = 1, 2 .

Recalling that

X_{h_{j}}

are

M - 0.99

distributed and pairwise independent on

R

, using for a fixed

y_{2} \in ϒ_{+}

, 46 for all

y_{1} \in ϒ_{+}

, and using 45 with

j = 2

one can deduce

\begin{matrix} \bar{λ} ({x \in {\bar{Λ}}^{'} (\tilde{q}) : {\bar{X}}_{h_{1}} (x) = 0 and {\bar{X}}_{h_{2}} (x) = y_{2}}) = \end{matrix}

(48)

\begin{matrix} \bar{λ} ({x \in {\bar{Λ}}^{'} (\tilde{q}) : {\bar{X}}_{h_{2}} (x) = y_{2}}) - \end{matrix}

\begin{matrix} \bar{λ} ({x \in {\bar{Λ}}^{'} (\tilde{q}) : {\bar{X}}_{h_{1}} (x) \in ϒ_{+} and {\bar{X}}_{h_{2}} (x) = y_{2}}) = \end{matrix}

\begin{matrix} \bar{λ} ({x \in R : X_{h_{1}} (x) = 0 and X_{h_{2}} (x) = y_{2}}) \bar{λ} ({\bar{Λ}}^{'} (\tilde{q})) . \end{matrix}

\begin{matrix}  \end{matrix}

Similarly, one can see that for any

y_{1} \in ϒ_{+}

\begin{matrix} \bar{λ} ({x \in {\bar{Λ}}^{'} (\tilde{q}) : {\bar{X}}_{h_{1}} (x) = y_{1} and {\bar{X}}_{h_{1}} (x) = 0}) = \end{matrix}

(49)

\begin{matrix} \bar{λ} ({x \in R : X_{h_{1}} (x) = y_{1} and X_{h_{2}} (x) = 0}) \bar{λ} ({\bar{Λ}}^{'} (\tilde{q})) . \end{matrix}

\begin{matrix}  \end{matrix}

Recalling that

X_{h_{2}}

M - 0.99

-distributed on

R

and using 48 for all

y_{2} \in ϒ_{+}

and 47 with

j = 1

one can see that

\begin{matrix} \bar{λ} ({x \in {\bar{Λ}}^{'} (\tilde{q}) : {\bar{X}}_{h_{1}} (x) = 0 and {\bar{X}}_{h_{2}} (x) = 0}) = \end{matrix}

(50)

\begin{matrix} \bar{λ} ({x \in {\bar{Λ}}^{'} (\tilde{q}) : {\bar{X}}_{h_{1}} (x) = 0}) - \end{matrix}

\begin{matrix} \bar{λ} ({x \in {\bar{Λ}}^{'} (\tilde{q}) : {\bar{X}}_{h_{1}} (x) = 0 and {\bar{X}}_{h_{2}} (x) \in ϒ_{+}}) = \end{matrix}

\begin{matrix} \bar{λ} ({x \in R : X_{h_{1}} (x) = 0 and X_{h_{2}} (x) = 0}) \bar{λ} ({\bar{Λ}}^{'} (\tilde{q})) . \end{matrix}

\begin{matrix}  \end{matrix}

Since

X_{h_{1}}

and

X_{h_{2}}

are pairwise independent and

M - 0.99

-distributed on

R

, from ( 45 - 50 ) it follows that

{\bar{X}}_{h_{1}}

and

{\bar{X}}_{h_{2}}

are pairwise independent on

{\bar{Λ}}^{'} (\tilde{q}) .

Put

{\bar{E}}_{δ} = E_{δ}

. Clearly,

{\bar{E}}_{δ}

is periodic by

\bar{τ}

and this completes the proof of (i).

It is clear that

\bar{λ} ({\bar{E}}_{δ}) = \bar{λ} (E_{δ}) < δ .

For

x \notin {\bar{E}}_{δ}

, set

{\bar{f}}_{h, x} (x^{'}) = f_{h, x} (x^{'}) \tilde{q} / 2^{κ}

x^{'} \in [j \tilde{q}, j \tilde{q} + γ 2^{κ})

for a

j \in Z

, otherwise put

{\bar{f}}_{h, x} (x^{'}) = 0 .

Clearly,

{\bar{f}}_{h, x} \leq {\bar{f}}_{h} .

For all

x \notin {\bar{E}}_{δ}

h \in {1, . . ., K}

, let

\bar{α} (x) = α (x)

\bar{ω} (x) = ω (x)

\bar{τ} (x) = \tilde{q} τ (x)

, then we have

\frac{\bar{ω} (x)}{\bar{α} (x)} > Ω^{'} τ (x) = Ω \tilde{q} τ (x) = Ω \bar{τ} (x)

Now we verify 41 for

{\bar{f}}_{h}

{\bar{f}}_{h, x}

and

{\bar{X}}_{h}

. Assume

x \in {\bar{Λ}}^{'} (\tilde{q}) \ {\bar{E}}_{δ}

\bar{α} (x) = α (x) \leq n < n + m \leq ω (x) = \bar{ω} (x),

\bar{τ} (x) = τ (x) \tilde{q} | m,

in fact, it is enough to consider the case when

τ (x) \tilde{q} = m = \bar{τ} (x)

. We claim that for any

h = 1, . . ., K

we have

\frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, x} (x + k^{2}) \leq \frac{1}{m} \sum_{k = n}^{n + m - 1} {\bar{f}}_{h, x} (x + k^{2}),

then we will apply 41 for

f_{h}

f_{h, x}

and

X_{h}

Since

τ (x) \tilde{q} = m

and

x \in {\bar{Λ}}^{'} (\tilde{q}) \ {\bar{E}}_{δ}

implies

x \notin E_{δ}

, using 42 several times we obtain

\frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, x} (x + k^{2}) = \frac{1}{m} \sum_{k^{'} = n}^{n + τ (x) - 1} \sum_{j = 0}^{\tilde{q} - 1} f_{h, x} (x + (k^{'} + j τ (x))^{2}) =

\frac{1}{m} \sum_{k^{'} = n}^{n + τ (x) - 1} \tilde{q} f_{h, x} (x + {k^{'}}^{2}) .

From

x \in {\bar{Λ}}^{'} (\tilde{q}),

it follows that there exists

k_{0}

such that

x \in - k_{0}^{2} + [i_{k_{0}} \tilde{q}, i_{k_{0}} \tilde{q} + γ 2^{κ})

, that is,

x + k_{0}^{2} \in [i_{k_{0}} \tilde{q}, i_{k_{0}} \tilde{q} + γ 2^{κ})

for an

i_{k_{0}} \in Z,

and

k_{0}^{2} \in Λ_{0}^{'} (\tilde{q})

. Recall that there are

2^{κ}

many solutions of

x^{2} \equiv k_{0}^{2}

modulo

\tilde{q} .

Since

(τ (x), \tilde{q}) = 1

for a fixed

k^{'}

, the set

k^{'} + j τ (x)

forms a complete residue system modulo

\tilde{q}

j

runs from

0

\tilde{q} - 1

, hence there are at least

2^{κ}

many

j_{k^{'}, l}

l = 1, . . ., 2^{κ}

with

(k^{'} + j_{k^{'}, l} τ (x))^{2} \equiv k_{0}^{2}

modulo

\tilde{q}

, where

k_{0}

is defined above. Recalling that

x \in {\bar{Λ}}^{'} (\tilde{q}) \ {\bar{E}}_{δ}

, for any

k^{'} = n, . . ., n + τ (x) - 1

, we have

\sum_{j = 0}^{\tilde{q} - 1} {\bar{f}}_{h, x} (x + (k^{'} + j τ (x))^{2}) \geq \sum_{l = 1}^{2^{κ}} {\bar{f}}_{h, x} (x + (k^{'} + j_{k^{'}, l} τ (x))^{2}) =

\sum_{l = 1}^{2^{κ}} f_{h, x} (x + (k^{'} + j_{k^{'}, l} τ (x))^{2}) \frac{\tilde{q}}{2^{κ}} \geq 2^{κ} f_{h, x} (x + {k^{'}}^{2}) \frac{\tilde{q}}{2^{κ}} .

Therefore,

\frac{1}{m} \sum_{k = n}^{n + m - 1} {\bar{f}}_{h, x} (x + k^{2}) = \frac{1}{m} \sum_{k^{'} = n}^{n + τ (x) - 1} \sum_{j = 0}^{\tilde{q} - 1} {\bar{f}}_{h, x} (x + (k^{'} + j τ (x))^{2}) \geq

applying 41 for

f_{h}

f_{h, x}

and

X_{h}

\frac{1}{m} \sum_{k^{'} = n}^{n + τ (x) - 1} \tilde{q} f_{h, x} (x + {k^{'}}^{2}) = \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, x} (x + k^{2}) \geq X_{h} (x) \geq {\bar{X}}_{h} (x) .

This proves (ii) for

x \in {\bar{Λ}}^{'} (\tilde{q}) \ {\bar{E}}_{δ}

. Since

{\bar{X}}_{h} (x) = 0

for

x \in R \ ({\bar{Λ}}^{'} (\tilde{q}) \cup {\bar{E}}_{δ})

for these

x

's 41 holds obviously for

{\bar{f}}_{h}

{\bar{f}}_{h, x}

and

{\bar{X}}_{h}

Using 44 and

(\tilde{q}, p) = 1

for all

p \in \bar{P}

we have

(\bar{τ} (x), p) = (\tilde{q} τ (x), p) = 1

and

(τ \tilde{q}, p) = (\bar{τ}, p) = 1

for all

p \in \bar{P} .

This proves (iii).

To verify (iv), suppose

x \in {\bar{Λ}}^{'} (\tilde{q}) \ {\bar{E}}_{δ}

h \in {1, . . ., K}

and

α^{2} (x) = {\bar{α}}^{2} (x) \leq j < j + \tilde{q} τ (x) \leq {\bar{ω}}^{2} (x) = ω^{2} (x) .

x + j \in [j^{'} \tilde{q}, j^{'} \tilde{q} + γ 2^{κ})

for a

j^{'} \in Z

, then

\begin{matrix} {\bar{f}}_{h, x} (x + j) & = f_{h, x} (x + j) \tilde{q} / 2^{κ} = f_{h, x} (x + j + τ (x)) \tilde{q} / 2^{κ} = . . . = \end{matrix}

(51)

\begin{matrix} f_{h, x} (x + j + \tilde{q} τ (x)) \tilde{q} / 2^{κ} = {\bar{f}}_{h, x} (x + j + \tilde{q} τ (x)) \end{matrix}

\begin{matrix}  \end{matrix}

when

α^{2} (x) = {\bar{α}}^{2} (x) \leq j < j + \tilde{q} τ (x) \leq {\bar{ω}}^{2} (x) = ω^{2} (x)

x + j \notin [j^{'} \tilde{q}, j^{'} \tilde{q} + γ 2^{κ})

for all

j^{'} \in Z

, then

{\bar{f}}_{h, x} (x + j) = 0 = {\bar{f}}_{h, x} (x + j + \tilde{q} τ (x)) .

This verifies (iv).

Next we prove (v)

\begin{matrix} \frac{1}{τ \tilde{q}} \int_{0}^{τ \tilde{q}} {\bar{f}}_{h} = \int^{¯} {\bar{f}}_{h} \leq Γ \cdot γ \cdot 2^{- M + 1} . \end{matrix}

(52)

Indeed,

\frac{1}{τ \tilde{q}} \sum_{j = 0}^{\tilde{q} - 1} \int_{0}^{τ} {\bar{f}}_{h} (x + j τ) d x = \frac{1}{τ} \int_{0}^{τ} \frac{1}{\tilde{q}} \sum_{j = 0}^{\tilde{q} - 1} {\bar{f}}_{h} (x + j τ) d x = (*) .

To continue this computation recall that from

(τ, \tilde{q}) = 1

it follows that

⌊ x ⌋ + j τ

hits each residue class modulo

\tilde{q}

once as

j

varies from

0

\tilde{q} - 1

and

f_{h} (x + j τ) = f_{h} (x)

for all

j

. Thus, recalling that

γ^{'}

associated to

Λ = R

equals

1

and using (v) for

f_{h}

(*) = \frac{1}{τ} \int_{0}^{τ} \frac{1}{\tilde{q}} f_{h} (x) \frac{\tilde{q}}{2^{κ}} γ 2^{κ} d x = \frac{1}{τ} γ \int_{0}^{τ} f_{h} (x) d x \leq Γ γ 2^{- M + 1} .

This proves 52 .

4.2 Proof of Lemma 4

Recall

q = p_{1} \cdot \cdot \cdot p_{κ}

where

p_{1}, . . ., p_{κ}

are odd primes. By results in [11] when

κ

and

p_{1}

are large the normalized gaps between consecutive elements of

Λ_{0} (q)

approximate a Poisson distribution and the average gap size is

2^{κ} .

Hence, if

γ

is small then most of the gaps between points of

Λ_{0} (q)

are bigger than

γ 2^{κ}

Considering the sets

{\bar{Λ}}_{γ}^{'} (q)

, due to small gaps, there might be some overlaps and hence

\begin{matrix} \bar{λ} ({\bar{Λ}}_{γ}^{'} (q)) < γ and \bar{λ} (R \ {\bar{Λ}}_{γ}^{'} (q)) > 1 - γ . \end{matrix}

(53)

However, the closer

γ

0

, the smaller the percentage of “loss due to overlaps”. Thus taking into consideration 40 as well one can choose constants

C_{γ} > 1 > {\tilde{C}}_{γ} > 0

κ_{γ}^{'},

such that for all

κ > κ_{γ}^{'}

there exists

p_{κ}^{'}

for which from

p_{κ}^{'} < p_{1} < . . . < p_{κ}

q = p_{1} \cdot \cdot \cdot p_{κ}

it follows that

\begin{matrix} C_{γ} > \frac{γ}{\bar{λ} ({\bar{Λ}}_{γ}^{'} (q))} and {\tilde{C}}_{γ} \bar{λ} (R \ {\bar{Λ}}_{γ}^{'} (q)) < 1 - γ - γ^{2} . \end{matrix}

(54)

We can also require that

C_{γ} \to 1

and

{\tilde{C}}_{γ} \to 1

γ \to 0 + .

In 54 the second order term in

(1 - γ - γ^{2})

appears for technical reasons. It is clear that

(1 - γ - γ^{2}) / (1 - γ) \to 1

γ \to 0 + .

In order to apply Lemma 5 we need to choose a positive “leakage constant,”

γ

, which remains fixed during all steps of the leakage producing the

(K + 1) - M

family. We choose

γ_{0} < 10^{- 6}

so that if

γ < γ_{0}

γ = 2^{- c_{γ}}

c_{γ} \in N

there exists

κ_{γ} \geq κ_{γ}^{'}

such that for all

κ > κ_{γ}

there exists

p_{γ, κ} > p_{κ}^{'}

for which if

p_{γ, κ} < p_{1} < . . . < p_{κ}

q = p_{1} \cdot \cdot \cdot p_{κ},

then

\begin{matrix} \bar{λ} ({\bar{Λ}}_{γ}^{'} (q)) > 9 γ / 10 and \bar{λ} (R \ {\bar{Λ}}_{γ}^{'} (q)) < 1 - \frac{9 γ}{10} . \end{matrix}

(55)

Recall that

Γ

is one of the input parameters of Lemma 4 . We also assume that

γ

is chosen so that

C_{γ} < Γ

for

C_{γ}

defined in 54 and

{\tilde{C}}_{γ} > 1 - 10^{- 6}

From now on a value of

γ < γ_{0}

, with

γ = 2^{- c_{γ}}

c_{γ} \in N

satisfying the above assumptions is fixed. We will write

Λ (q)

\bar{Λ} (q)

and

{\bar{Λ}}^{'} (q)

instead of

Λ_{γ} (q)

{\bar{Λ}}_{γ} (q)

and

{\bar{Λ}}_{γ}^{'} (q)

, respectively.

Next, after giving an outline we start the details of the proof of Lemma 4 .

4.2.1 Setting up the induction argument for Lemma 4

We proceed by mathematical induction.

Here is a short explanation of our plan. We assume that

K - M

families living on

R

exist for all possible input parameter choices. Let

δ > 0,

Ω,

Γ > 1

A \in N

and

P \subset N

be given. We will define our

(K + 1) - M

family with these input parameters. We can assume that

P

is closed under products.

During the definition of the

(K + 1) - M

family another, “inner” finite induction is used (with respect to

L

) which is called the leakage process.

This technically delicate process is the focus of the next several sections.

During this process we will use Lemma 5 to define families which are almost

(K + 1) - M

families on sets of the type

{\bar{Λ}}^{'} (q)

, except for the new functions

f_{K + 1, L}

and

X_{K + 1, L}

. Each

f_{K + 1, L}

is the indicator function of a set. As

L

grows the support of

f_{K + 1, L}

decreases. Lemma 2 and Lemma 3 are used to ensure that “squares hit sufficiently often” the support of

f_{K + 1, L}

. (This motivated the term “leakage” since the values of

f_{K + 1, L}

leak onto some larger sets when we consider averages along the squares.) This also requires that before defining

f_{K + 1, L}

one uses Lemma 3 to choose

τ_{L - 1}^{'}

and make a

τ_{L - 1}^{'}

rearrangement to yield an intermediate function

f_{K + 1, L - 1}^{'}

. At the same time we must keep track of our new random variable

X_{K + 1, L}

and other auxiliary functions. It is essential in this induction that we can vary

τ

and

κ .

To help the reader going through the details of the proof here is an outline of the main features of the various sections of the proof. We hope this outline might help prevent the reader from becoming lost in the details of the proof.

In Section 4.2.2 we start the leakage process with a

K - M

family periodic by

τ_{0}

, consisting of functions

f_{h, 0}

X_{h, 0}

for

h = 1, . . ., K

. We also define

f_{K + 1, 0} \equiv 1

and

X_{K + 1, 0}

. At this stage

f_{K + 1, 0}

is supported on

R

. During the leakage process the size of the support of the functions

f_{K + 1, L}

is shrinking and we are interested in how much of

f_{K + 1, L}

is “leaking” onto larger sets.

In Section 4.2.3 we assume that we have accomplished step

L - 1

of the leakage and we have a family periodic by

τ_{L - 1}

, consisting of functions

f_{h, L - 1},

X_{h, L - 1}

for

h = 1, . . ., K + 1

. We also introduce the auxiliary sets

S_{L - 1, l}

l = 0, . . ., L - 1

used to describe the distribution of

X_{K + 1, L - 1}

In Section 4.2.4 we choose a prime number

τ_{L - 1}^{'}

which is much larger than

τ_{L - 1}

and by using Lemma 3 we perform a

τ_{L - 1}^{'}

rearrangement of the family coming from Section 4.2.3 . This way we obtain a family periodic by

τ_{L - 1}^{'}

, consisting of functions

f_{h, L - 1}^{'}

X_{h, L - 1}^{'}

. The auxiliary sets used for describing the distribution of

X_{K + 1, L - 1}^{'}

are denoted by

S_{L - 1, l}^{'}

l = 0, . . ., L - 1 .

In Section 4.2.5 we choose a

κ_{L}

and a square free number

q_{L} = p_{1, L} \cdot \cdot \cdot q_{κ_{L}, L}

such that

2^{κ_{L}}

is much larger than

τ_{L - 1}^{'}

. The average value of the difference between elements of

Λ_{0} (q_{L})

is close to

2^{κ_{L}}

. We introduce some auxiliary sets, among them

Φ_{L}

and

Ψ_{L}

, so that

Φ_{L} \subset R \ {\bar{Λ}}^{'} (q_{L}) \subset Ψ_{L}

and these two auxiliary sets consist of intervals of the form

[j τ_{L - 1}^{'}, (j + 1) τ_{L - 1}^{'}),

j \in Z .

2^{κ_{L}}

is much larger than

τ_{L - 1}^{'}

, then

\bar{λ} (Φ_{L})

and

\bar{λ} (Ψ_{L})

both approximately equal

\bar{λ} (R \ {\bar{Λ}}^{'} (q_{L})) .

To define our

(K + 1) - M

family on

Ψ_{L}

(which is approximately

R \ {\bar{Λ}}^{'} (q_{L})

) we will use mainly the functions coming from Section 4.2.5 . In particular, we define

X_{h, L} = X_{h, L - 1}^{'}

h \leq K + 1

and

x \in Φ_{L}

In Section 4.2.6 by using Lemma 5 we put a

K - M

family onto

{\bar{Λ}}^{'} (q_{L})

This will yield functions

{\bar{f}}_{h, L}

{\bar{X}}_{h, L}

periodic by

{\bar{τ}}_{L} q_{L}

. For

h = 1, . . ., K

we define

X_{h, L}

{\bar{Λ}}^{'} (q_{L})

by using

{\bar{X}}_{h, L}

. For

h = 1, . . ., K

our functions will be sums of

f_{h, L - 1}^{'}

restricted to

Ψ_{L}

and of the functions

{\bar{f}}_{h, L}

“living” on

{\bar{Λ}}^{'} (q_{L}) .

This combined family will be periodic by

τ_{L} = q_{L} {\bar{τ}}_{L} τ_{L - 1}^{'} .

The “leakage” is done when we define

f_{K + 1, L}

so that it equals the restriction of

f_{K + 1, L - 1}^{'}

onto the set

Ψ_{L}

. This means that the support

F_{L}

f_{K + 1, L}

will have a very small intersection with

{\bar{Λ}}^{'} (q_{L})

. “Most” of

F_{L}

will be a subset of

R \ {\bar{Λ}}^{'} (q_{L})

and will approximately equal the auxiliary set

S_{L, 0}

. The nested sequence

S_{L, l}

l = 0, . . ., L

will describe the distribution

X_{K + 1, L}

, the larger

l

, the smaller the values

X_{K + 1, L}

can take on

S_{L, l} \ S_{L, l - 1}

In Section 4.2.7 we make the calculations needed to show that we have enough “leakage” from the support of

f_{K + 1, L}

so that we have the domination inequality 41 with

f_{K + 1, L}

and

X_{K + 1, L}

Finally, in Section 4.2.8 we terminate the leakage process when we have reached a suitably large

L = L^{''} \leq L^{'}

. The functions

f_{h, L^{''}}

for

h = 1, . . ., K + 1

will yield the functions

f_{h}

we need for the

(K + 1) - M

family. For

h = 1, . . ., K

the functions

X_{h}

of the

(K + 1) - M

family will equal the functions

X_{h, L^{''}}

To define

X_{K + 1}

we use the sets

S_{L^{''}, l}

l = 0, . . ., L^{''}

related to the distribution of

X_{K + 1, L^{''}}

. We will choose

X_{K + 1}

so that it is

M

-

0.99

distributed and less or equal than

X_{K + 1, L^{''}}

After this outline we turn to the details of the proof.

Naturally, one needs to start the induction by showing that

1 - M

families exist. We could just simply say that the

0 - M

families are the empty families, but we will be more specific. To obtain

1 - M

families we need to do a leakage process without any reference to

0 - M

families. In the proof below we will indicate which parts need to be altered, or else, are not needed for the first step of our induction, that is when

K + 1 = 1 .

At this stage there are no

h

's satisfying

h = 1, . . ., K

and hence the formulae involving

f_{h}

X_{h}

etc. for these values of

h

are vacuous.

Assume

K - M

families exist; again, for

K = 0

it is the empty family.

We have to build a

(K + 1) - M

family.

Choose a positive integer

L^{'}

such that

\begin{matrix} (1 - \frac{γ}{2})^{L^{'}} < \frac{1}{2^{M}} . \end{matrix}

(56)

The inner finite induction, the “leakage” will halt at some

L^{''} \leq L^{'} .

Fix constants

Γ_{0} \leq . . . \leq Γ_{L^{'}}

such that

\begin{matrix} C_{γ} Γ_{L} < Γ for all L = 0, . . ., L^{'} . \end{matrix}

(57)

Put

δ_{L} = \frac{δ}{4 (L^{'} + 1)} for L = 0, . . ., L^{'} .

We will choose sufficiently small positive constants

ρ

and

ρ^{'} .

Finally, we set

P_{0} = P \cup P_{0}^{'} \cup . . . \cup P_{L^{'}}^{'}

where

P

and each

P_{j}^{'}

contains infinitely many primes and all their possible products, but numbers in different sets are relatively prime; moreover

P_{0}

has sufficiently large complement.

4.2.2 Step $L = 0$ of the leakage process

We put

f_{K + 1, 0} \equiv 1

. For any

x \in R

, set

f_{K + 1, 0, x} = f_{K + 1, 0},

F_{0} = R,

S_{0, 0} = R

r_{0} = 1 .

So,

\bar{λ} (F_{0}) = 1

and

X_{K + 1, 0} \overset{d e f}{=} (1 - ρ^{'}) {\tilde{C}}_{γ} = (1 - ρ^{'}) {\tilde{C}}_{γ} \bar{λ} (F_{0})

, In case

K = 0

, we want to construct a

1 - M

family.

We also put

E^{0} = E_{δ_{0}} = \emptyset .

Then we choose a sufficiently large

τ_{0}

, and functions

α_{0} (x)

ω_{0} (x)

τ_{0} (x)

taking integer values for all

x \in R

(in fact, these functions can be constant on

R

), such that the following assumptions hold:

ω_{0} (x) > α_{0} (x) > A,

τ_{0} (x) < τ_{0}

ω_{0}^{2} (x) < τ_{0},

\frac{ω_{0} (x)}{α_{0} (x)} > Ω τ_{0} (x) = Ω_{0} τ_{0} (x)

, and for all

p \in P_{0}

(τ_{0} (x), p) = 1,

(τ_{0}, p) = 1 .

For example, we could take

α_{0} (x) = A + 1

τ_{0} (x)

to be the smallest odd prime which is relatively prime to all elements of

P_{0}

ω_{0} (x) = τ_{0} (x) Ω (A + 2)

and

τ_{0}

be the smallest prime relatively prime to the elements of

P_{0}

and greater than

(ω_{0} (x))^{2}

By our choice of

f_{K + 1, 0} = f_{1, 0} = f_{K + 1, 0, x} = f_{1, 0, x} \equiv 1

for any

m \in N

we have

\frac{1}{m} \sum_{k = n}^{n + m - 1} f_{1, 0} (x + k^{2}) \geq \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{1, 0, x} (x + k^{2}) > X_{1, 0} (x) .

It is also clear that for all

x \in R

f_{1, 0, x} (x + j + τ_{0} (x)) = f_{1, 0, x} (x + j)

for any

j \in R

. This completes stage

0

of the leakage in case

K = 0 .

In case

K > 0

we proceed as follows: Choose a

K - M

family on

R

with input constants

δ_{0} = \frac{δ}{4 (L^{'} + 1)}

Ω_{0} = Ω

Γ_{0} C_{γ} < Γ

A_{0} = A

P_{0}

. Then there exist a period

τ_{0}

; functions

f_{h, 0} : R \to [0, \infty)

, pairwise independent

M

-

0.99

-distributed “random” variables

X_{h, 0} : R \to R

, for

h = 1, . . ., K,

a set

E_{δ_{0}}

periodic by

τ_{0},

with

\bar{λ} (E_{δ_{0}}) < δ_{0} .

Moreover, for all

x \notin E_{δ_{0}}

, there exist

ω_{0} (x) > α_{0} (x) > A,

τ_{0} (x) < τ_{0}

such that

ω_{0}^{2} (x) < τ_{0},

\frac{ω_{0} (x)}{α_{0} (x)} > Ω τ_{0} (x) = Ω_{0} τ_{0} (x)

, if

α_{0} (x) \leq n < n + m \leq ω_{0} (x)

, and

τ_{0} (x) | m

then for all

h = 1, . . ., K + 1

(for

h = 1, . . ., K

by the definition of the

K - M

family, for

h = K + 1

by the above definition) there exists

0 \leq f_{h, 0, x} \leq f_{h, 0}

such that

\frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, 0} (x + k^{2}) \geq \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, 0, x} (x + k^{2}) > X_{h, 0} (x) .

For all

p \in P_{0}

(τ_{0} (x), p) = 1,

(τ_{0}, p) = 1 .

For all

x \notin E_{δ_{0}}

and all

h = 1, . . ., K + 1,

f_{h, 0, x} (x + j + τ_{0} (x)) = f_{h, 0, x} (x + j)

whenever

α_{0}^{2} (x) \leq j < j + τ_{0} (x) \leq ω_{0}^{2} (x) .

Finally,

\frac{1}{τ_{0}} \int_{0}^{τ_{0}} f_{h, 0} = \int^{¯} f_{h, 0} < C_{γ} Γ_{0} \cdot 2^{- M + 1},

for

h = 1, . . ., K .

We put

E_{0}^{'} = E_{0}^{''} = E_{0}^{'''} = \emptyset

and

E^{0} = E_{δ_{0}} \cup E_{0}^{'} \cup E_{0}^{''} \cup E_{0}^{'''} .

4.2.3 The setting after step $L - 1$ of the leakage

Assume we have accomplished step

L - 1

of the leakage process. We have an exceptional set

E^{L - 1} = E_{δ_{L - 1}} \cup E_{L - 1}^{'} \cup E_{L - 1}^{''} \cup E_{L - 1}^{'''}

with

\begin{matrix} \bar{λ} (E^{L - 1}) < \frac{L}{(L^{'} + 1)} δ; \end{matrix}

(58)

P_{L - 1} = P \cup P_{L}^{'} \cup . . . \cup P_{L^{'}}^{'};

there exists a period

τ_{L - 1}

such that

E^{L - 1}

X_{h, L - 1},

f_{h, L - 1}

(h = 1, . . ., K + 1)

are periodic by

τ_{L - 1},

f_{h, L - 1} : R \to [0, \infty)

, the “random” variables

X_{h, L - 1} : R \to R

are pairwise independent for

h = 1, . . ., K + 1,

X_{h, L - 1}

are

M

-

0.99

-distributed for

h = 1, . . ., K

(later there will be comments about the distribution of

X_{K + 1, L - 1}

). For all

x \notin E^{L - 1}

there exist

0 \leq f_{h, L - 1, x} \leq f_{h, L - 1}

and

ω_{L - 1} (x) > α_{L - 1} (x) > A,

τ_{L - 1} (x) < τ_{L - 1}

such that

ω_{L - 1}^{2} (x) < τ_{L - 1},

\frac{ω_{L - 1} (x)}{α_{L - 1} (x)} > Ω τ_{L - 1} (x)

; moreover if

α_{L - 1} (x) \leq n < n + m \leq ω_{L - 1} (x)

and

τ_{L - 1} (x) | m

, then for all

h = 1, . . ., K + 1

\begin{matrix} \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, L - 1} (x + k^{2}) \geq \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, L - 1, x} (x + k^{2}) > X_{h, L - 1} (x); \end{matrix}

(59)

for all

p \in P_{L - 1}

(τ_{L - 1} (x), p) = 1,

(τ_{L - 1}, p) = 1;

for all

x \notin E^{L - 1}

f_{h, L - 1, x} (x + j + τ_{L - 1} (x)) = f_{h, L - 1, x} (x + j)

whenever

α_{L - 1}^{2} (x) \leq j < j + τ_{L - 1} (x) \leq ω_{L - 1}^{2} (x)

for all

h \in {1, . . ., K + 1}

. Finally, for

h = 1, . . ., K

\begin{matrix} \frac{1}{τ_{L - 1}} \int_{0}^{τ_{L - 1}} f_{h, L - 1} = \int^{¯} f_{h, L - 1} < C_{γ} Γ_{L - 1} \cdot 2^{- M + 1} . \end{matrix}

(60)

We emphasize that we do not expect that 60 holds for

h = K + 1

. On the other hand, we suppose that the values of

f_{K + 1, L - 1}

are

0

1

, that is, it is an indicator function.

L - 1 = 0

, then

X_{K + 1, L - 1}

is constant and no assumptions are needed about its distribution.

L - 1 > 0

, that is,

L \geq 2

then we give the extra assumptions about the distribution of

X_{K + 1, L - 1}

as follows. Recall

F_{0} = R .

Set

F_{L - 1} = {x : f_{K + 1, L - 1} (x) = 1}

and

r_{L - 1} = \frac{\bar{λ} (F_{L - 1})}{\bar{λ} (F_{L - 2})} < 1 .

We also assume

\begin{matrix} 1 - 2 γ < r_{L - 1} < 1 - \frac{γ}{2}, \end{matrix}

(61)

\bar{λ} (F_{L - 1}) = r_{1} \cdot \cdot \cdot r_{L - 1} = r_{0} \cdot \cdot \cdot r_{L - 1},

the sets

S_{L - 1, 0} \subset . . . \subset S_{L - 1, L - 1} = R

are defined so that

\begin{matrix} \frac{1}{1 - ρ} \bar{λ} (F_{L - 1}) > \bar{λ} (S_{L - 1, 0}) > (1 - ρ) \bar{λ} (F_{L - 1}), \end{matrix}

(62)

x \in S_{L - 1, 0}

then

X_{K + 1, L - 1} (x) = (1 - ρ^{'}) {\tilde{C}}_{γ} = (1 - ρ^{'}) {\tilde{C}}_{γ} \bar{λ} (F_{0}) .

For

l = 0, . . ., L - 1

we have

\begin{matrix} \frac{1}{(1 - ρ) r_{0} \cdot \cdot \cdot r_{l}} \bar{λ} (S_{L - 1, 0}) > \bar{λ} (S_{L - 1, l}) > \frac{1 - ρ}{r_{0} \cdot \cdot \cdot r_{l}} \bar{λ} (S_{L - 1, 0}), \end{matrix}

(63)

which is equivalent to

\begin{matrix} \frac{1}{(1 - ρ)} \bar{λ} (S_{L - 1, 0}) > \bar{λ} (F_{l}) \cdot \bar{λ} (S_{L - 1, l}) > (1 - ρ) \bar{λ} (S_{L - 1, 0}) . \end{matrix}

(64)

x \in S_{L - 1, l} \ S_{L - 1, l - 1}

for

l \in {1, . . ., L - 1},

then

\begin{matrix} X_{K + 1, L - 1} (x) = (1 - ρ^{'}) r_{0} \cdot \cdot \cdot r_{l} {\tilde{C}}_{γ} = (1 - ρ^{'}) \bar{λ} (F_{l}) {\tilde{C}}_{γ} . \end{matrix}

(65)

The sets

S_{L - 1, l}

are increasing almost by a factor

1 / r_{l}

in size whereas the value of

X_{K + 1, L - 1}

on the difference is decreasing by a factor

r_{l}

. We also assume that

F_{L - 1}

has the property that if

x \in F_{L - 1}

then

[⌊ x ⌋, ⌊ x ⌋ + 1) \subset F_{L - 1} .

4.2.4 Rearrangement with respect to $τ_{L - 1}^{'}$

Since the set

F_{L - 1}

is periodic by

τ_{L - 1}

and is the union of some integral intervals we can apply Lemma 3 . We choose

M_{ρ^{'} / 2}

such that for all prime numbers

τ_{L - 1}^{'} > M_{ρ^{'} / 2}

if we consider

F_{L - 1}^{τ_{L - 1}^{'}}

, the

τ_{L - 1}^{'}

periodic rearrangement of

F_{L - 1}

, then for any

x \in R

τ_{L - 1}^{'} | m

, then

\begin{matrix} \frac{1}{m} \sum_{k = n}^{n + m - 1} χ_{F_{L - 1}^{τ_{L - 1}^{'}}} (x + k^{2}) \geq (1 - \frac{ρ^{'}}{2}) \bar{λ} (F_{L - 1}) . \end{matrix}

(66)

We will choose and fix a sufficiently large prime

τ_{L - 1}^{'} \in P_{L - 1}^{'} .

Now we modify our sets and functions so that they are all periodic with respect to

τ_{L - 1}^{'}

. Since we are going to define functions which are periodic by

τ_{L - 1}^{'},

it is sufficient to define them on

[0, τ_{L - 1}^{'}) .

x \in [0, ⌊ τ_{L - 1}^{'} / τ_{L - 1} ⌋ \cdot τ_{L - 1})

and the righthandside of the equation is defined at

x

, set

\begin{matrix} f_{h, L - 1}^{'} (x) & = f_{h, L - 1} (x), h = 1, . . ., K + 1, \end{matrix}

\begin{matrix} α_{L - 1}^{'} (x) & = α_{L - 1} (x), \end{matrix}

\begin{matrix} ω_{L - 1}^{'} (x) & = ω_{L - 1} (x), \end{matrix}

\begin{matrix} τ_{L - 1}^{'} (x) & = τ_{L - 1} (x), \end{matrix}

\begin{matrix} X_{h, L - 1}^{'} (x) & = X_{h, L - 1} (x), h = 1, . . ., K + 1 . \end{matrix}

\begin{matrix}  \end{matrix}

[⌊ τ_{L - 1}^{'} / τ_{L - 1} ⌋ τ_{L - 1}, τ_{L - 1}^{'})

we define all the above functions equal to zero with the exception of the functions

X_{h, L - 1}^{'}

h = 1, . . ., K + 1

. For these functions some minor adjustments will be made on this interval in order to ensure that they are pairwise independent for

h = 1, . . ., K + 1

and are

M

-

0.99

-distributed for

h = 1, . . ., K .

We can also assume that

X_{K + 1, L - 1}^{'}

has constant value

(1 - ρ^{'}) \bar{λ} (F_{L - 1}) {\tilde{C}}_{γ}

[⌊ τ_{L - 1}^{'} / τ_{L - 1} ⌋ τ_{L - 1}, τ_{L - 1}^{'})

. When

L - 1 = 0

then this implies that

X_{K + 1, L - 1}^{'}

takes this constant value on

R .

We define

{E^{'}}^{L - 1}

so that it is periodic by

τ_{L - 1}^{'}

and

\begin{matrix} {E^{'}}^{L - 1} \cap [0, τ_{L - 1}^{'}) = \end{matrix}

(67)

\begin{matrix} (E^{L - 1} \cap [0, (⌊ \frac{τ_{L - 1}^{'}}{τ_{L - 1}} ⌋ - 1) τ_{L - 1})) \cup [(⌊ \frac{τ_{L - 1}^{'}}{τ_{L - 1}} ⌋ - 1) τ_{L - 1}, τ_{L - 1}^{'}) . \end{matrix}

\begin{matrix}  \end{matrix}

By choosing

τ_{L - 1}^{'}

sufficiently large we can make

0 < \bar{λ} ({E^{'}}^{L - 1}) - \bar{λ} (E^{L - 1})

as small as we wish, hence, using 58 we can assume that

τ_{L - 1}^{'}

is chosen so large that

\bar{λ} ({E^{'}}^{L - 1}) < \frac{L}{(L^{'} + 1)} δ .

When

L - 1 = 0

then

\begin{matrix} X_{K + 1, 0}^{'} (x) = (1 - ρ^{'}) \bar{λ} (F_{0}) {\tilde{C}}_{γ} for all x \in R . \end{matrix}

(68)

L - 1 > 0

, that is,

L \geq 2

we need to deal with the auxiliary sets related to the distribution of

X_{K + 1, L - 1}^{'} .

We put

S_{L - 1, L - 1}^{'} = R

. Observe that 67 holds with

{E^{'}}^{L - 1},

E^{L - 1}

being replaced by

S_{L - 1, L - 1}^{'},

and

S_{L - 1, L - 1} = R,

respectively.

For

l = 0, . . ., L - 2

we define the sets

S_{L - 1, l}^{'}

so that they are periodic by

τ_{L - 1}^{'}

and we have

S_{L - 1, l}^{'} \cap [0, τ_{L - 1}^{'}) = S_{L - 1, l} \cap [0, (⌊ τ_{L - 1}^{'} / τ_{L - 1} ⌋ - 1) τ_{L - 1}) .

The above definitions imply

\begin{matrix} X_{K + 1, L - 1}^{'} (x) & = (1 - ρ^{'}) {\tilde{C}}_{γ} \bar{λ} (F_{0}) for x \in S_{L - 1, 0}^{'}, and \end{matrix}

(69)

\begin{matrix} X_{K + 1, L - 1}^{'} (x) & = (1 - ρ^{'}) {\tilde{C}}_{γ} \bar{λ} (F_{l}) for x \in S_{L - 1, l}^{'} \ S_{L - 1, l - 1}^{'}, l = 1, . . ., L - 1 . \end{matrix}

\begin{matrix}  \end{matrix}

We can also assume that

τ_{L - 1}^{'}

is chosen so large that from 62 , 63 and 64 we can deduce

\begin{matrix} \frac{1}{1 - ρ} \bar{λ} (F_{L - 1}) > \bar{λ} (S_{L - 1, 0}^{'}) > (1 - ρ) \bar{λ} (F_{L - 1}) \end{matrix}

(70)

and for

l = 0, . . ., L - 1

\begin{matrix} \frac{1}{(1 - ρ) r_{0} \cdot \cdot \cdot r_{l}} \bar{λ} (S_{L - 1, 0}^{'}) > \bar{λ} (S_{L - 1, l}^{'}) > (1 - ρ) \frac{1}{r_{0} \cdot \cdot \cdot r_{l}} \bar{λ} (S_{L - 1, 0}^{'}), \end{matrix}

(71)

or, equivalently,

\begin{matrix} \frac{1}{1 - ρ} \bar{λ} (S_{L - 1, 0}^{'}) > \bar{λ} (F_{l}) \cdot \bar{λ} (S_{L - 1, l}^{'}) > (1 - ρ) \bar{λ} (S_{L - 1, 0}^{'}) . \end{matrix}

(72)

Set

F_{L - 1}^{'} = {x : f_{K + 1, L - 1}^{'} (x) = 1}

, that is,

F_{L - 1}^{'} \cap [0, τ_{L - 1}^{'}) = F_{L - 1} \cap [0, ⌊ τ_{L - 1}^{'} / τ_{L - 1} ⌋ τ_{L - 1}) = F_{L - 1}^{τ_{L - 1}^{'}} \cap [0, ⌊ τ_{L - 1}^{'} / τ_{L - 1} ⌋ τ_{L - 1})

and

f_{K + 1, L - 1}^{'} (x) = χ_{F_{L - 1}^{τ_{L - 1}^{'}}} (x)

for all

x \in R

. For the case

L - 1 = 0

we note that

F_{0} \cap [0, τ_{L - 1}^{'}) = [0, ⌊ τ_{L - 1}^{'} / τ_{L - 1} ⌋ τ_{L - 1}) .

By 66 for any

x \in R

from

τ_{L - 1}^{'} | m

, it follows that letting

f_{K + 1, L - 1, x}^{'} = f_{K + 1, L - 1}^{'} = f_{K + 1, L - 1}^{'} = χ_{F_{L - 1}^{τ_{L - 1}^{'}}} :

\begin{matrix} \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{K + 1, L - 1}^{'} (x + k^{2}) = \end{matrix}

(73)

\begin{matrix} \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{K + 1, L - 1, x}^{'} (x + k^{2}) > (1 - \frac{ρ^{'}}{2}) \bar{λ} (F_{L - 1}) . \end{matrix}

\begin{matrix}  \end{matrix}

This formula is the main motivation for introducing the

τ_{L - 1}^{'}

periodic rearrangements. Observe that if

τ_{L - 1}^{'}

is large then

\bar{λ} (F_{L - 1}^{'}) / \bar{λ} (F_{L - 1})

is very close to

1;

namely we can suppose that

\begin{matrix} 1 - \frac{γ}{10} < \frac{\bar{λ} (F_{L - 1}^{'})}{\bar{λ} (F_{L - 1})} < 1 + \frac{γ}{10} . \end{matrix}

(74)

Hence, by 70 if

L \geq 2

we can assume that

τ_{L - 1}^{'}

is so large that

\begin{matrix} \frac{1}{1 - ρ} \bar{λ} (F_{L - 1}^{'}) > \bar{λ} (S_{L - 1, 0}^{'}) > (1 - ρ) \bar{λ} (F_{L - 1}^{'}) \end{matrix}

(75)

holds as well.

x \in [0, τ_{L - 1}^{'}) \ {E^{'}}^{L - 1}

, then put

α_{L - 1}^{'} (x) = α_{L - 1} (x),

ω_{L - 1}^{'} (x) = ω_{L - 1} (x),

τ_{L - 1}^{'} (x) = τ_{L - 1} (x) < τ_{L - 1} ≪ τ_{L - 1}^{'} .

We have

(ω_{L - 1}^{'} (x))^{2} < τ_{L - 1},

\begin{matrix} \frac{ω_{L - 1}^{'} (x)}{α_{L - 1}^{'} (x)} > Ω τ_{L - 1}^{'} (x), \end{matrix}

(76)

α_{L - 1}^{'} (x) \leq n < n + m \leq ω_{L - 1}^{'} (x)

τ_{L - 1}^{'} (x) = τ_{L - 1} (x) | m

, then letting

f_{h, L - 1, x}^{'} = f_{h, L - 1, x}

and recalling

x \notin {E^{'}}^{L - 1}

and 67 implies that

x + k^{2} \in [0, ⌊ τ_{L - 1}^{'} / τ_{L - 1} ⌋ τ_{L - 1})

for

k \in {n, . . ., n + m - 1}

we infer

\begin{matrix} \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, L - 1, x}^{'} (x + k^{2}) & = \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, L - 1, x} (x + k^{2}) > \end{matrix}

(77)

\begin{matrix} X_{h, L - 1} (x) = X_{h, L - 1}^{'} (x) . \end{matrix}

\begin{matrix}  \end{matrix}

For all

x \in [0, τ_{L - 1}^{'}) \ {E^{'}}^{L - 1}

h \in {1, . . ., K + 1}

, if

{α^{'}}_{L - 1}^{2} (x) \leq j < j + τ_{L - 1}^{'} (x) \leq {ω^{'}}_{L - 1}^{2} (x),

f_{h, L - 1, x} (x + j + τ_{L - 1} (x)) = f_{h, L - 1, x}^{'} (x + j + τ_{L - 1}^{'} (x)) = f_{h, L - 1, x}^{'} (x + j) = f_{h, L - 1, x} (x + j) .

We also have

\begin{matrix} \int^{¯} f_{h, L - 1}^{'} \leq \int^{¯} f_{h, L - 1} < C_{γ} Γ_{L - 1} \cdot 2^{- M + 1}, \end{matrix}

(78)

for

h = 1, . . ., K .

We extend the definition of

f_{h, L - 1, x}^{'}

to arbitrary

x \notin {E^{'}}^{L - 1}

by choosing

j

such that

x - j τ_{L - 1}^{'} \in [0, τ_{L - 1}^{'}) \ {E^{'}}^{L - 1}

and setting

f_{h, L - 1, x}^{'} (x^{'}) = f_{h, L - 1, x - j τ_{L - 1}^{'}} (x^{'} - j τ_{L - 1}^{'}) .

By periodicity with respect to

τ_{L - 1}^{'}

, the above estimates hold for any

x \notin {E^{'}}^{L - 1} .

4.2.5 Choice of $κ_{L}$ , $q_{L}$ , $Φ_{L}$ , $Ψ_{L}$ , and $X_{h, L}$ on $R \ {\bar{Λ}}^{'} (q_{L})$

Next we choose a number

q_{L} \in P_{L}^{'},

q_{L} = p_{1, L} \cdot \cdot \cdot p_{κ_{L}, L}

p_{1, L} < . . . < p_{κ_{L}, L}

, where

κ_{L}

and

p_{1, L}

are both sufficiently large. Recall from Remark 1 that the average gap length between points of

Λ_{0} (q_{L})

is approximately

2^{κ_{L}}

and we can assume that it is much larger than

τ_{L - 1}^{'}

. The normalized difference between elements of

Λ_{0} (q_{L})

approximates Poisson distribution by the results in [11] . We put

{\tilde{Φ}}_{L} = {x : d i s t (x, {\bar{Λ}}^{'} (q_{L})) > 2 τ_{L - 1}^{'}},

Φ_{L} = \cup {[j τ_{L - 1}^{'}, (j + 1) τ_{L - 1}^{'}) : {\tilde{Φ}}_{L} \cap [j τ_{L - 1}^{'}, (j + 1) τ_{L - 1}^{'}) \neq \emptyset},

{\hat{Φ}}_{L} = {x : d i s t (x, {\bar{Λ}}^{'} (q_{L})) > τ_{L - 1}^{'}},

{\hat{Ψ}}_{L} = {x : d i s t (x, R \ {\bar{Λ}}^{'} (q_{L})) \leq τ_{L - 1}^{'}},

Ψ_{L} = \cup {[j τ_{L - 1}^{'}, (j + 1) τ_{L - 1}^{'}) : {\hat{Ψ}}_{L} \cap [j τ_{L - 1}^{'}, (j + 1) τ_{L - 1}^{'}) \neq \emptyset},

and finally

{\tilde{Ψ}}_{L} = {x : d i s t (x, R \ {\bar{Λ}}^{'} (q_{L})) \leq 2 τ_{L - 1}^{'}} .

It is clear that

\begin{matrix} {\tilde{Φ}}_{L} \subset Φ_{L} \subset {\hat{Φ}}_{L} \subset R \ {\bar{Λ}}^{'} (q_{L}) \subset {\hat{Ψ}}_{L} \subset Ψ_{L} \subset {\tilde{Ψ}}_{L} . \end{matrix}

(79)

The sets

Φ_{L}

and

Ψ_{L}

are periodic by

τ_{L - 1}^{'} q_{L}

and the sets

{\tilde{Φ}}_{L}

{\hat{Φ}}_{L}

{\tilde{Ψ}}_{L}

, and

{\hat{Ψ}}_{L}

are periodic by

q_{L}

. If

κ_{L}

is sufficiently large, then

2^{κ_{L}}

and hence most of the gaps between points of

Λ_{0} (q_{L})

are much larger than

τ_{L - 1}^{'} .

In the sequel by

\approx

we mean that if

τ_{L - 1}^{'}

p_{1, L}

and

2^{κ_{L}}

(compared to

τ_{L - 1}^{'}

) are sufficiently large, then the ratio of the two sides of

\approx

is sufficiently close to

1

. Since

{\bar{Λ}}^{'} (q_{L})

consists of intervals of length

γ 2^{κ_{L}}

which is much larger than

τ_{L - 1}^{'}

, we have

\begin{matrix} \bar{λ} ({\tilde{Ψ}}_{L}) \approx \bar{λ} ({\tilde{Φ}}_{L}) \approx \bar{λ} (Ψ_{L}) \approx \bar{λ} (Φ_{L}) \approx \bar{λ} ({\hat{Ψ}}_{L}) \approx \bar{λ} ({\hat{Φ}}_{L}), \end{matrix}

(80)

\begin{matrix} \bar{λ} (Φ_{L}) \leq \bar{λ} (R \ {\bar{Λ}}^{'} (q_{L})) \leq \bar{λ} (Ψ_{L}) and \bar{λ} (R \ {\bar{Λ}}^{'} (q_{L})) \approx \bar{λ} (Ψ_{L}) . \end{matrix}

(81)

\begin{matrix}  \end{matrix}

Set

E_{L}^{''} = R \ ({\bar{Λ}}^{'} (q_{L}) \cup {\tilde{Φ}}_{L}),

this will be part of the new exceptional set

E^{L}

. We also introduce

{\tilde{E}}_{L}^{''} = R \ ({\bar{Λ}}^{'} (q_{L}) \cup Φ_{L})

which is a subset of

E_{L}^{''}

. It is clear that

E_{L}^{''}

is periodic by

q_{L}

, while

{\tilde{E}}_{L}^{''}

is periodic by

τ_{L - 1}^{'} q_{L}

. Choosing

κ_{L}

and

p_{1, L}

sufficiently large we can ensure that

\bar{λ} ({\tilde{E}}_{L}^{''}) \leq \bar{λ} (E_{L}^{''}) < δ / 4 L^{'} .

Set

\begin{matrix} X_{h, L} (x) = X_{h, L - 1}^{'} (x) if h \leq K + 1 and x \in Φ_{L} . \end{matrix}

(82)

Since

Φ_{L}

consists of intervals of the form

[j τ_{L - 1}^{'}, (j + 1) τ_{L - 1}^{'}),

this definition and the remark after the definition of

X_{h, L - 1}^{'}

in Section 4.2.4 ensures that the functions

X_{h, L}

are pairwise independent for

h = 1, . . ., K + 1

and are conditionally

M

-

0.99

distributed on

Φ_{L}

for

h = 1, . . ., K

{\tilde{E}}_{L}^{''}

we define

X_{h, L}

for

h = 1, . . ., K + 1

so that they are pairwise independent on

{\tilde{E}}_{L}^{''}

, furthermore

X_{h, L}

are conditionally

M

-

0.99

-distributed on

{\tilde{E}}_{L}^{''}

for

h = 1, . . ., K,

X_{K + 1, L} (x) = (1 - ρ^{'}) \bar{λ} (F_{L - 1}) {\tilde{C}}_{γ}

{\tilde{E}}_{L}^{''}

X_{h, L}

are periodic on

{\tilde{E}}_{L}^{''}

τ_{L - 1}^{'} q_{L}

for

h = 1, . . ., K + 1 .

This way the

X_{h, L}

's are defined on

Φ_{L} \cup {\tilde{E}}_{L}^{''} = R \ {\bar{Λ}}^{'} (q_{L})

. In the next section after putting a

K - M

family on

{\bar{Λ}}^{'} (q_{L})

we complete their definition. We set

E_{L}^{'} = Ψ_{L} \cap {E^{'}}^{L - 1} .

Next we consider some sets which are used to describe the distribution of

X_{K + 1, L}

L = 1

set

S_{1, 0} = R \ {\bar{Λ}}^{'} (q_{1})

and

S_{1, 1} = R .

L \geq 2

first we define

S_{L, l}

for

l = 0, . . ., L - 1

so that

S_{L, l} \cap Φ_{L} = S_{L - 1, l}^{'} \cap Φ_{L}

for

l = 0, . . ., L - 1 .

We choose

S_{L, l}

so that

S_{L, l} \cap (R \ Φ_{L}) = \emptyset

for

l = 0, . . ., L - 2 .

We choose

S_{L, L - 1}

so that

S_{L, L - 1} = {\tilde{E}}_{L}^{''} \cup (S_{L - 1, L - 1}^{'} \cap Φ_{L}) = {\tilde{E}}_{L}^{''} \cup Φ_{L} = R \ {\bar{Λ}}^{'} (q_{L}) .

Finally, we set

S_{L, L} = R,

then

S_{L, L} \ S_{L, L - 1} = {\bar{Λ}}^{'} (q_{L}) .

We have by 69 , (for the case

L = 1

by 68 ) and 82

\begin{matrix} X_{K + 1, L} (x) = (1 - ρ^{'}) \bar{λ} (F_{0}) {\tilde{C}}_{γ} for x \in S_{L, 0}, and \end{matrix}

(83)

\begin{matrix} X_{K + 1, L} (x) = (1 - ρ^{'}) \bar{λ} (F_{l}) {\tilde{C}}_{γ} for x \in S_{L, l} \ S_{L, l - 1}, l = 1, . . ., L - 1 . \end{matrix}

\begin{matrix}  \end{matrix}

The case when

l = L

will be considered in 86 .

Let

F_{L} = Ψ_{L} \cap F_{L - 1}^{'} .

Using the fact that

F_{L - 1}^{'}

is periodic by

τ_{L - 1}^{'}

and

Ψ_{L}

is the union of some intervals of the form

[j τ_{L - 1}^{'}, (j + 1) τ_{L - 1}^{'})

and is periodic by

τ_{L - 1}^{'} q_{L}

one can easily see that

\bar{λ} (F_{L}) = \bar{λ} (Ψ_{L}) \bar{λ} (F_{L - 1}^{'}) .

Moreover,

r_{L} \overset{d e f}{=} \frac{\bar{λ} (F_{L})}{\bar{λ} (F_{L - 1})} = \bar{λ} (Ψ_{L}) \frac{\bar{λ} (F_{L - 1}^{'})}{\bar{λ} (F_{L - 1})} \approx \bar{λ} (Ψ_{L}) \approx \bar{λ} (Φ_{L}) \approx \bar{λ} (R \ {\bar{Λ}}^{'} (q_{L})) .

τ_{L - 1}^{'}

κ_{L}

and

p_{1, L}

are sufficiently large by 81 we have

\bar{λ} (Ψ_{L}) \frac{\bar{λ} (F_{L - 1}^{'})}{\bar{λ} (F_{L - 1})} < \frac{1 - γ}{1 - γ - γ^{2}} \bar{λ} (R \ {\bar{Λ}}^{'} (q_{L})) .

By 54 we obtain

\begin{matrix} {\tilde{C}}_{γ} r_{L} = {\tilde{C}}_{γ} \frac{\bar{λ} (F_{L})}{\bar{λ} (F_{L - 1})} = {\tilde{C}}_{γ} \bar{λ} (Ψ_{L}) \frac{\bar{λ} (F_{L - 1}^{'})}{\bar{λ} (F_{L - 1})} < 1 - γ . \end{matrix}

(84)

By 53 , 55 , 74 and

\bar{λ} (Ψ_{L}) \approx \bar{λ} (R \ {\bar{Λ}}^{'} (q_{L}))

, if

κ_{L}

and

p_{1, L}

are sufficiently large then

\begin{matrix} 1 - 2 γ < r_{L} < 1 - \frac{γ}{2} . \end{matrix}

(85)

We set

\begin{matrix} X_{K + 1, L} (x) = (1 - ρ^{'}) \bar{λ} (F_{L}) {\tilde{C}}_{γ} for x \in S_{L, L} \ S_{L, L - 1} = {\bar{Λ}}^{'} (q_{L}) . \end{matrix}

(86)

L = 1

then

\bar{λ} (F_{1}) = \bar{λ} (Ψ_{1}) \bar{λ} (F_{0}^{'}) \approx \bar{λ} (R \ {\bar{Λ}}^{'} (q_{1}))

and

\bar{λ} (S_{1, 0}) = \bar{λ} (R \ {\bar{Λ}}^{'} (q_{1})) .

Furthermore,

\bar{λ} (S_{1, 1}) = \bar{λ} (R) = 1,

r_{1} \approx \bar{λ} (R \ {\bar{Λ}}^{'} (q_{1}))

. Hence, if

τ_{0}^{'}

κ_{1}

and

p_{1, 1}

are sufficiently large we have by 53 and 54

1 - 2 γ < r_{1} < 1 - \frac{γ}{2},

\begin{matrix} \frac{1}{1 - ρ} \bar{λ} (F_{1}) > \bar{λ} (S_{1, 0}) > (1 - ρ) \bar{λ} (F_{1}), \end{matrix}

(87)

\begin{matrix} \frac{1}{(1 - ρ) r_{0} r_{1}} \bar{λ} (S_{1, 0}) > \bar{λ} (S_{1, 1}) > (1 - ρ) \frac{1}{r_{0} r_{1}} \bar{λ} (S_{1, 0}) \end{matrix}

(88)

and

\begin{matrix} \frac{1}{1 - ρ} \bar{λ} (S_{1, 0}) > \bar{λ} (F_{1}) \bar{λ} (S_{1, 1}) > (1 - ρ) \bar{λ} (S_{1, 0}) . \end{matrix}

(89)

This shows that 91 and 92 below hold for

L = 1

and

l = 1 .

For

L = 1

and

l = 0

, 91 and 92 are obvious.

L \geq 2

we have

\bar{λ} (S_{L, 0}) = \bar{λ} (Φ_{L}) \cdot \bar{λ} (S_{L - 1, 0}^{'})

and using 75 and 80 , if

κ_{L}

and

p_{1, L}

are sufficiently large then

\begin{matrix} \frac{1}{1 - ρ} \bar{λ} (F_{L}) > \bar{λ} (S_{L, 0}) > (1 - ρ) \bar{λ} (F_{L}) . \end{matrix}

(90)

It is also clear that

\bar{λ} (S_{L, l}) = \bar{λ} (Φ_{L}) \cdot \bar{λ} (S_{L - 1, l}^{'})

for

l = 0, . . ., L - 2

and

\bar{λ} (S_{L, L - 1}) = (\bar{λ} (Φ_{L}) + \bar{λ} ({\tilde{E}}_{L}^{''})) \bar{λ} (S_{L - 1, L - 1}^{'}) = \bar{λ} (R \ {\bar{Λ}}^{'} (q_{L}))

hence, for

l = 0, . . ., L - 1

κ_{L}

and

p_{1, L}

are large

\bar{λ} (S_{L, l}) / \bar{λ} (S_{L - 1, l}^{'}) \approx r_{L} .

Using 71 and

\bar{λ} (S_{L, l}) \approx r_{L} \bar{λ} (S_{L - 1, l}^{'})

, we have for

l = 0, . . ., L - 1

\begin{matrix} \frac{1}{(1 - ρ) r_{0} \cdot \cdot \cdot r_{l}} \bar{λ} (S_{L, 0}) > \bar{λ} (S_{L, l}) > (1 - ρ) \frac{1}{r_{0} \cdot \cdot \cdot r_{l}} \bar{λ} (S_{L, 0}) \end{matrix}

(91)

and by 72

\begin{matrix} \frac{1}{1 - ρ} \bar{λ} (S_{L, 0}) > \bar{λ} (F_{l}) \bar{λ} (S_{L, l}) > (1 - ρ) \bar{λ} (S_{L, 0}) . \end{matrix}

(92)

From

\bar{λ} (S_{L, L}) = 1

and 90 it follows that

\frac{1}{1 - ρ} \bar{λ} (S_{L, 0}) > \bar{λ} (F_{L}) \bar{λ} (S_{L, L}) > (1 - ρ) \bar{λ} (S_{L, 0}) .

Using the fact that

\bar{λ} (F_{L}) = r_{0} \cdot \cdot \cdot r_{L}

we find that 91 and 92 hold for

l = L

as well.

Applying Lemma 2 with

κ_{L},

ε = δ / 4 L^{'}

and sufficiently small

\tilde{ρ} > 0

yields

p_{1, L}^{'}

sufficiently large so that

q_{L} = p_{1, L} \cdot \cdot \cdot p_{κ_{L}, L}

, with

p_{1, L}^{'} < p_{1, L}

satisfies 13 .

Denote by

{\bar{E}}_{L}^{'''}

the set of those

n

's for which

# (((n + Λ_{0} (q_{L})) \ Λ (q_{L})) \cap [0, q_{L})) < (1 - \tilde{ρ}) (1 - γ) # (Λ_{0} (q_{L}) \cap [0, q_{L})) .

By Lemma 2

# ({\bar{E}}_{L}^{'''} \cap [0, q_{L})) < \frac{δ}{4 L^{'}} q_{L} .

Set

E_{L}^{'''} = {x \in R : ⌊ x ⌋ \in {\bar{E}}_{L}^{'''}} .

Then

\bar{λ} (E_{L}^{'''}) < δ / 4 L^{'}

and if

x \notin E_{L}^{'''}

we have

\begin{matrix} \frac{1}{q_{L}} # {k^{'} \in [0, q_{L}) \cap Z : ⌊ x ⌋ + {k^{'}}^{2} \notin Λ (q_{L})} \geq \end{matrix}

(93)

\frac{1}{q_{L}} # {k^{'} \in [0, q_{L}) \cap Z : ⌊ x ⌋ + {k^{'}}^{2} \notin Λ (q_{L}), {k^{'}}^{2} \in Λ_{0}^{'} (q_{L})} \geq

\frac{1}{q_{L}} 2^{κ_{L}} # (((⌊ x ⌋ + Λ_{0}^{'} (q_{L})) \ Λ (q_{L})) \cap [0, q_{L})) \geq

\frac{1}{q_{L}} 2^{κ_{L}} (# (((⌊ x ⌋ + Λ_{0} (q_{L})) \ Λ (q_{L})) \cap [0, q_{L})) - # ((Λ_{0} (q_{L}) \ Λ_{0}^{'} (q_{L})) \cap [0, q_{L}))) \geq

\frac{1}{q_{L}} 2^{κ_{L}} (((1 - \tilde{ρ}) (1 - γ) # (Λ_{0} (q_{L}) \cap [0, q_{L}))) - # ((Λ_{0} (q_{L}) \ Λ_{0}^{'} (q_{L})) \cap [0, q_{L}))) = (*) .

To continue the above estimate we use the fact that we can assume that

p_{1, L}

is so large that

# ((Λ_{0} (q_{L}) \ Λ_{0}^{'} (q_{L})) \cap [0, q_{L})) < \tilde{ρ} (1 - γ) # (Λ_{0} (q_{L}) \cap [0, q_{L}))

and hence

(*) \geq \frac{1}{q_{L}} 2^{κ_{L}} (1 - 2 \tilde{ρ}) (1 - γ) # (Λ_{0} (q_{L}) \cap [0, q_{L})) = (* *) .

By using 3 we can finish with the inequality

\begin{matrix} (* *) > \frac{1}{q_{L}} 2^{κ_{L}} (1 - 2 \tilde{ρ}) (1 - γ) (1 - \tilde{ρ}) \frac{q_{L}}{2^{κ_{L}}} = (1 - 2 \tilde{ρ}) (1 - \tilde{ρ}) (1 - γ) . \end{matrix}

(94)

4.2.6 Putting $K - M$ families on ${\bar{Λ}}^{'} (q_{L})$

We put

\begin{matrix} f_{K + 1, L} = f_{K + 1, L - 1}^{'} \cdot χ_{Ψ_{L}}, and f_{K + 1, L, x} = f_{K + 1, L} for any x \in R . \end{matrix}

(95)

Then indeed,

F_{L} = {x : f_{K + 1, L} (x) = 1} = Ψ_{L} \cap F_{L - 1}^{'},

and we have

\int^{¯} f_{K + 1, L} = \bar{λ} (F_{L}) .

Choose

P_{L}^{''} \subset P_{L}^{'}

such that it contains infinitely many primes and all their possible products, moreover all numbers in

P_{L}^{''}

are relatively prime to

q_{L} \in P_{L}^{'}

and set

{\bar{P}}_{L} = P \cup P_{L}^{''} \cup P_{L + 1}^{'} \cup . . . \cup P_{L^{'}}^{'} .

When

K = 0

, that is when constructing a

1 - M

family we do not have to put anything on

{\bar{Λ}}^{'} (q_{L})

. We just set

{\bar{τ}}_{L} = 1

E_{δ_{L}} = \emptyset

and skip the following application of Lemma 5 and continue reading this section from the place which is marked by a

†

a few paragraphs below.

For the choice of the

K - M

family living on

{\bar{Λ}}^{'} (q_{L})

use Lemma 5 with

{\bar{P}}_{L},

δ_{L} = δ / 4 (L^{'} + 1)

Ω_{L} = Ω \cdot q_{L} τ_{L - 1}^{'}

Γ_{L}

and

A .

(i) We obtain functions ${\bar{f}}_{h, L}$ , ${\bar{X}}_{h, L}$ periodic by ${\bar{τ}}_{L} q_{L}$ for $h = 1, . . ., K .$ The functions ${\bar{X}}_{h, L} : R \to R$ are pairwise independent and conditionally $M$ $-$ $0.99$ distributed on ${\bar{Λ}}^{'} (q_{L}) .$ There exists $E_{δ_{L}}$ periodic by $q_{L} {\bar{τ}}_{L}$ .

(ii) We have

\bar{λ} (E_{δ_{L}}) < δ_{L} = δ / 4 (L^{'} + 1)

. For all

x \notin E_{δ_{L}}

, there exist

0 \leq {\bar{f}}_{h, L, x} \leq {\bar{f}}_{h, L}

and

{\bar{ω}}_{L} (x) > {\bar{α}}_{L} (x) > A

{\bar{τ}}_{L} (x) < {\bar{τ}}_{L} q_{L},

{\bar{ω}}_{L}^{2} (x) < {\bar{τ}}_{L} q_{L}

\frac{{\bar{ω}}_{L} (x)}{{\bar{α}}_{L} (x)} > Ω_{L} {\bar{τ}}_{L} (x) = Ω q_{L} τ_{L - 1}^{'} {\bar{τ}}_{L} (x) .

Moreover, if

{\bar{α}}_{L} (x) \leq n < n + m \leq {\bar{ω}}_{L} (x)

and

{\bar{τ}}_{L} (x) | m

then for

h = 1, . . ., K

\begin{matrix} \frac{1}{m} \sum_{k = n}^{n + m - 1} {\bar{f}}_{h, L} (x + k^{2}) \geq \frac{1}{m} \sum_{k = n}^{n + m - 1} {\bar{f}}_{h, L, x} (x + k^{2}) > {\bar{X}}_{h, L} (x) . \end{matrix}

(96)

(iii) For all $p \in {\bar{P}}_{L},$ $({\bar{τ}}_{L} (x), p) = 1$ , $({\bar{τ}}_{L} q_{L}, p) = 1$ .
(iv) For all $x \in {\bar{Λ}}^{'} (q_{L}) \ E_{δ_{L}},$ for all $h = 1, . . ., K$ , ${\bar{f}}_{h, L, x} (x + j + {\bar{τ}}_{L} (x)) = {\bar{f}}_{h, L, x} (x + j),$ when ${\bar{α}}_{L}^{2} (x) \leq j < j + {\bar{τ}}_{L} (x) \leq {\bar{ω}}_{L}^{2} (x)$ .

(v) Finally, for all

h = 1, . . ., K

\begin{matrix} \int^{¯} {\bar{f}}_{h, L} < Γ_{L} \cdot γ \cdot 2^{- M + 1} . \end{matrix}

(97)

So far we have not defined the functions

X_{h, L}

{\bar{Λ}}^{'} (q_{L})

for

h = 1, . . ., K

Set

X_{h, L} (x) = {\bar{X}}_{h, L} (x)

x \in {\bar{Λ}}^{'} (q_{L}),

h = 1, . . ., K

; also set

\begin{matrix} f_{h, L} = f_{h, L - 1}^{'} \cdot χ_{Ψ_{L}} + {\bar{f}}_{h, L} for h = 1, . . ., K . \end{matrix}

(98)

Recall from 78 that

\int^{¯} f_{h, L - 1}^{'} \leq \int^{¯} f_{h, L - 1}

for

h = 1, . . ., K .

Using 97 and that

f_{h, L - 1}^{'}

is periodic by

τ_{L - 1}^{'}

and

Ψ_{L}

consists of blocks of length

τ_{L - 1}^{'}

\int^{¯} f_{h, L} \leq \bar{λ} (Ψ_{L}) \cdot \int^{¯} f_{h, L - 1} + Γ_{L} (\frac{γ}{\bar{λ} ({\bar{Λ}}^{'} (q_{L}))}) 2^{- M + 1} \bar{λ} ({\bar{Λ}}^{'} (q_{L})) = (*) .

We can assume that

κ_{L}

and

p_{1, L}

are chosen so large that, taking into consideration 60 , 80 and 81

(\int^{¯} f_{h, L - 1}) \frac{\bar{λ} (Ψ_{L})}{\bar{λ} (R \ {\bar{Λ}}^{'} (q_{L}^{'}))} < Γ_{L - 1} \cdot C_{γ} 2^{- M + 1} \leq Γ_{L} \cdot C_{γ} 2^{- M + 1}

holds as well. Hence using 54 we can continue our estimation by

(*) < (\int^{¯} f_{h, L - 1}) \frac{\bar{λ} (Ψ_{L})}{\bar{λ} (R \ {\bar{Λ}}^{'} (q_{L}))} \cdot \bar{λ} (R \ {\bar{Λ}}^{'} (q_{L})) + Γ_{L} C_{γ} 2^{- M + 1} \bar{λ} ({\bar{Λ}}^{'} (q_{L})) <

Γ_{L} \cdot C_{γ} \cdot 2^{- M + 1} .

†

In case

K = 0

after skipping a few of the preceding paragraphs one should continue reading the proof from here, again keeping in mind that for

K = 0

there are no

h

's satisfying

h = 1, . . ., K

and hence many expressions are vacuous and not needed for this case.

Set

P_{L} = P \cup P_{L + 1}^{'} \cup . . . \cup P_{L^{'}}^{'} \subset {\bar{P}}_{L} \subset P_{L - 1}

. We also put

E^{L} = E_{δ_{L}} \cup E_{L}^{'} \cup E_{L}^{''} \cup E_{L}^{'''}

, and

τ_{L} = q_{L} {\bar{τ}}_{L} τ_{L - 1}^{'}

. Then for all

p \in P_{L} \subset {\bar{P}}_{L}

we have

(τ_{L}, p) = 1

. Assume

x \in R \ ({\bar{Λ}}^{'} (q_{L}) \cup E^{L}) .

Then

x \in {\tilde{Φ}}_{L} \subset Φ_{L}

and the old estimates work. In other words, for

x \in R \ ({\bar{Λ}}^{'} (q_{L}) \cup E^{L}) \subset {\tilde{Φ}}_{L},

set

α_{L} (x) = α_{L - 1}^{'} (x),

ω_{L} (x) = ω_{L - 1}^{'} (x),

τ_{L} (x) = τ_{L - 1}^{'} (x) = τ_{L - 1} (x)

. Then

ω_{L}^{2} (x) < τ_{L - 1} < τ_{L}

and by 76 we have

\frac{ω_{L - 1}^{'} (x)}{α_{L - 1}^{'} (x)} = \frac{ω_{L} (x)}{α_{L} (x)} > Ω τ_{L - 1}^{'} (x) = Ω τ_{L} (x) .

Furthermore, if

α_{L} (x) \leq n < n + m \leq ω_{L} (x)

and

τ_{L} (x) | m

then, for

h = 1, . . ., K

letting

f_{h, L, x} = f_{h, L - 1, x}^{'} \cdot χ_{Ψ_{L}} \leq f_{h, L}

by 77 and 82

\frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, L - 1, x}^{'} (x + k^{2}) = \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, L, x} (x + k^{2}) > X_{h, L} (x) = X_{h, L - 1}^{'} (x) .

Also observe that if

x \in R \ ({\bar{Λ}}^{'} (q_{L}) \cup E^{L}) \subset {\tilde{Φ}}_{L} \subset Φ_{L}

, then from

α_{L} (x) \leq n \leq k < n + m \leq ω_{L} (x)

, and

ω_{L}^{2} (x) < τ_{L - 1}

it follows that

x + k^{2} \in Ψ_{L}

and hence by 95 ,

f_{K + 1, L} (x + k^{2}) = f_{K + 1, L - 1}^{'} (x + k^{2}) = f_{K + 1, L, x} (x + k^{2}) = f_{K + 1, L - 1, x}^{'} (x + k^{2})

and

\frac{1}{m} \sum_{k = n}^{n + m - 1} f_{K + 1, L - 1, x}^{'} (x + k^{2}) = \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{K + 1, L, x} (x + k^{2}) >

X_{K + 1, L} (x) = X_{K + 1, L - 1}^{'} (x) .

Finally, for all

x \in R \ ({\bar{Λ}}^{'} (q_{L}) \cup E^{L}) \subset {\tilde{Φ}}_{L}

h = 1, . . ., K + 1

, if

α_{L}^{2} (x) \leq j < j + τ_{L} (x) \leq ω_{L}^{2} (x) < τ_{L - 1}

, then

f_{h, L - 1, x}^{'} (x + j + τ_{L - 1}^{'} (x)) = f_{h, L, x} (x + j + τ_{L} (x)) = f_{h, L, x} (x + j) = f_{h, L - 1, x}^{'} (x + j) .

Note that for

h = K + 1

one needs to use again that if

0 \leq j^{'} < ω_{L}^{2} (x) < τ_{L - 1},

then

x + j^{'} \in Ψ_{L}

and

f_{K + 1, L} (x + j^{'}) = f_{K + 1, L - 1}^{'} (x + j^{'}) .

Assume

x \in {\bar{Λ}}^{'} (q_{L}) \ E^{L} \subset {\bar{Λ}}^{'} (q_{L}) \ E_{δ_{L}}

In case

K = 0

set again

α_{L} (x) = α_{L - 1}^{'} (x),

ω_{L} (x) = ω_{L - 1}^{'} (x),

τ_{L} (x) = τ_{L - 1}^{'} (x) = τ_{L - 1} (x)

and skip the rest of this subsection.

Now we turn to the case when

K > 0 .

Since

x \in {\bar{Λ}}^{'} (q_{L}) \ E^{L} \subset {\bar{Λ}}^{'} (q_{L}) \ E_{δ_{L}}

for

h = 1, . . ., K

, the estimates which we have for the

K - M

family put on

{\bar{Λ}}^{'} (q_{L})

can be applied. In other words, for these

x

set

ω_{L} (x) \overset{d e f}{=} {\bar{ω}}_{L} (x) > α_{L} (x) \overset{d e f}{=} {\bar{α}}_{L} (x),

τ_{L} (x) \overset{d e f}{=} {\bar{τ}}_{L} (x) q_{L} τ_{L - 1}^{'} < τ_{L}

. Then

ω_{L}^{2} (x) < τ_{L}

, and

\frac{ω_{L} (x)}{α_{L} (x)} > Ω_{L} {\bar{τ}}_{L} (x) = Ω τ_{L} (x) .

Furthermore, if

α_{L} (x) \leq n < n + m \leq ω_{L} (x)

and

τ_{L} (x) | m

, then

{\bar{τ}}_{L} (x) | m

and by 96 and 98 if we let

f_{h, L, x} = {\bar{f}}_{h, L, x} \leq {\bar{f}}_{h, L} \leq f_{h, L}

, we have for

h = 1, . . ., K

\frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, L} (x + k^{2}) \geq \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, L, x} (x + k^{2}) > X_{h, L} (x) .

For all

p \in P_{L} \subset {\bar{P}}_{L}

we have

({\bar{τ}}_{L} (x) q_{L} τ_{L - 1}^{'}, p) = (τ_{L} (x), p) = 1

and for

h = 1, . . ., K

, if

α_{L}^{2} (x) \leq j < j + τ_{L} (x) \leq ω_{L}^{2} (x)

then

α_{L}^{2} (x) = {\bar{α}}_{L}^{2} (x) \leq j < j + {\bar{τ}}_{L} (x) < . . . < j + q_{L} {\bar{τ}}_{L} (x) \leq ω_{L}^{2} (x) = {\bar{ω}}_{L}^{2} (x)

and hence

f_{h, L, x} (x + j + τ_{L} (x)) = {\bar{f}}_{h, L, x} (x + j + τ_{L} (x)) = {\bar{f}}_{h, L, x} (x + j + q_{L} τ_{L - 1}^{'} {\bar{τ}}_{L} (x)) = {\bar{f}}_{h, L, x} (x + j + (q_{L} τ_{L - 1}^{'} - 1) {\bar{τ}}_{L} (x)) = . . . = {\bar{f}}_{h, L, x} (x + j) = f_{h, L, x} (x + j) .

4.2.7 Properties of $f_{K + 1, L}$

We need to check 41 when

h = K + 1

and

x \in {\bar{Λ}}^{'} (q_{L}) \ E^{L} \subset (S_{L, L} \ S_{L, L - 1}) \ E^{L},

and

τ_{L} (x) = τ_{L - 1}^{'} q_{L} {\bar{τ}}_{L} (x) | m

. If we can show 41 holds when

m = τ_{L - 1}^{'} q_{L}

then this clearly implies that it holds when

τ_{L} (x) | m

. Recall that

{\hat{Ψ}}_{L}

is periodic by

q_{L} .

Since

τ_{L - 1}^{'} \in P_{L - 1}^{'}

q_{L} \in P_{L}^{'}

implies

(τ_{L - 1}^{'}, q_{L}) = 1

k^{'} + j q_{L}

covers all residues modulo

τ_{L - 1}^{'}

j

runs from

0

τ_{L - 1}^{'} - 1 .

Since

f_{K + 1, L - 1, x}^{'} = f_{K + 1, L - 1}^{'}

is periodic by

τ_{L - 1}^{'}

, using 73 we obtain

\begin{matrix} \frac{1}{τ_{L - 1}^{'}} \sum_{j = 0}^{τ_{L - 1}^{'} - 1} f_{K + 1, L - 1, x}^{'} (x + (k^{'} + j q_{L})^{2}) > (1 - \frac{ρ^{'}}{2}) \bar{λ} (F_{L - 1}) . \end{matrix}

(99)

Also observe that from the periodicity of

{\hat{Ψ}}_{L}

q_{L}

it follows that if

x + {k^{'}}^{2} \in {\hat{Ψ}}_{L}

then

x + (k^{'} + j q_{L})^{2} \in {\hat{Ψ}}_{L} \subset Ψ_{L}

as well. Hence from

x + {k^{'}}^{2} \in {\hat{Ψ}}_{L}

it follows that

f_{K + 1, L, x} (x + (k^{'} + j q_{L})^{2}) = f_{K + 1, L - 1, x}^{'} (x + (k^{'} + j q_{L})^{2}) .

Therefore,

\frac{1}{τ_{L - 1}^{'} q_{L}} \sum_{k = n}^{n + τ_{L - 1}^{'} q_{L} - 1} f_{K + 1, L, x} (x + k^{2}) =

\frac{1}{τ_{L - 1}^{'} q_{L}} \sum_{k^{'} = n}^{n + q_{L} - 1} \sum_{j = 0}^{τ_{L - 1}^{'} - 1} f_{K + 1, L, x} (x + (k^{'} + j q_{L})^{2}) \geq

\frac{1}{τ_{L - 1}^{'} q_{L}} \sum_{\begin{matrix} k^{'} = n \\ x + {k^{'}}^{2} \in {\hat{Ψ}}_{L} \end{matrix}}^{n + q_{L} - 1} \sum_{j = 0}^{τ_{L - 1}^{'} - 1} f_{K + 1, L, x} (x + (k^{'} + j q_{L})^{2}) =

\frac{1}{q_{L}} \sum_{\begin{matrix} k^{'} = n \\ x + {k^{'}}^{2} \in {\hat{Ψ}}_{L} \end{matrix}}^{n + q_{L} - 1} \frac{1}{τ_{L - 1}^{'}} \sum_{j = 0}^{τ_{L - 1}^{'} - 1} f_{K + 1, L - 1, x}^{'} (x + (k^{'} + j q_{L})^{2}) >

(using 99 )

\frac{1}{q_{L}} \sum_{\begin{matrix} k^{'} = n \\ x + {k^{'}}^{2} \in {\hat{Ψ}}_{L} \end{matrix}}^{n + q_{L} - 1} (1 - \frac{ρ^{'}}{2}) \bar{λ} (F_{L - 1}) \geq

(using 79 )

\frac{1}{q_{L}} (1 - \frac{ρ^{'}}{2}) \bar{λ} (F_{L - 1}) # {k^{'} \in [0, q_{L}) \cap Z : x + {k^{'}}^{2} \notin {\bar{Λ}}^{'} (q_{L})} \geq

\frac{1}{q_{L}} (1 - \frac{ρ^{'}}{2}) \bar{λ} (F_{L - 1}) # {k^{'} \in [0, q_{L}) \cap Z : x + {k^{'}}^{2} \notin \bar{Λ} (q_{L})} =

(1 - \frac{ρ^{'}}{2}) \bar{λ} (F_{L - 1}) \frac{1}{q_{L}} # {k^{'} \in [0, q_{L}) \cap Z : ⌊ x ⌋ + {k^{'}}^{2} \notin Λ (q_{L})} .

Now use the estimates 93 through 94 and obtain that for

x \notin E_{L}^{'''}

\frac{1}{q_{L}} # {k^{'} \in [0, q_{L}) \cap Z : ⌊ x ⌋ + {k^{'}}^{2} \notin Λ (q_{L})} \geq (1 - 2 \tilde{ρ}) (1 - \tilde{ρ}) (1 - γ) .

Thus, if

x \in (S_{L, L} \ S_{L, L - 1}) \ E^{L}

we have for a suitable choice of

\tilde{ρ}

\frac{1}{τ_{L - 1}^{'} q_{L}} \sum_{k = n}^{n + τ_{L - 1}^{'} q_{L} - 1} f_{K + 1, L, x} (x + k^{2}) >

(1 - \frac{ρ^{'}}{2}) \bar{λ} (F_{L - 1}) (1 - 2 \tilde{ρ}) (1 - \tilde{ρ}) (1 - γ) \geq

(Using 84 and 86 and choosing a sufficiently small

\tilde{ρ} > 0

we have)

\geq (1 - ρ^{'}) (1 - γ) \bar{λ} (F_{L - 1}) > (1 - ρ^{'}) {\tilde{C}}_{γ} \bar{λ} (F_{L}) = X_{K + 1, L} (x) .

4.2.8 Finishing the leakage

We keep repeating the leakage steps until for the first time for an

L^{''}

we have

\bar{λ} (F_{L^{''}}) < 2^{- M}

. By 56 and 85 we have

L^{''} \leq L^{'}

and by

γ < γ_{0} < 10^{- 6}

we have

L^{''} \geq 2 .

We set

f_{h} = f_{h, L^{''}}

for

h = 1, . . ., K + 1,

and

X_{h} = X_{h, L^{''}}

for

h = 1, . . ., K .

From the induction steps we have

E_{δ} \overset{d e f}{=} E^{L^{''}}

such that

\bar{λ} (E_{δ}) < \frac{(L^{''} + 1)}{(L^{'} + 1)} δ \leq δ .

There exists

τ \overset{d e f}{=} τ_{L^{''}}

such that

f_{h}

h = 1, . . ., K + 1

X_{h}

h = 1, . . ., K

and

X_{K + 1, L^{''}}

are periodic by

τ,

X_{h}

h = 1, . . ., K

and

X_{K + 1, L^{''}}

are pairwise independent

X_{h}

h = 1, . . ., K

are

M

-

0.99

-distributed. By using the distributional properties of

X_{K + 1, L^{''}}

we will define

X_{K + 1}

at the end of this section.

For all

x \notin E_{δ}

there exist

ω (x) = ω_{L^{''}} (x) > α (x) = α_{L^{''}} (x) > A,

τ (x) = τ_{L^{''}} (x) < τ

such that

ω^{2} (x) < τ,

\frac{ω (x)}{α (x)} > Ω τ (x)

. Moreover, if

α (x) \leq n < n + m \leq ω (x)

and

τ (x) | m

, then for all

h = 1, . . ., K

letting

f_{h, x} = f_{h, L^{''}, x} \leq f_{h, L^{''}} = f_{h}

(see also 59 )

\begin{matrix} \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h} (x + k^{2}) \geq \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{h, x} (x + k^{2}) > X_{h} (x), \end{matrix}

(100)

and setting

f_{K + 1, x} = f_{K + 1, L^{''}, x} = f_{K + 1, L^{''}} = f_{K + 1}

, (see also 95 )

\begin{matrix} \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{K + 1} (x + k^{2}) = \frac{1}{m} \sum_{k = n}^{n + m - 1} f_{K + 1, x} (x + k^{2}) > X_{K + 1, L^{''}} (x), \end{matrix}

(101)

for all

p \in P_{L^{''}} \supset P

(τ (x), p) = 1,

(τ, p) = 1,

for all

x \notin E_{δ}

, for all

h \in {1, . . ., K + 1}

f_{h, x} (x + j + τ (x)) = f_{h, x} (x + j)

whenever

α^{2} (x) \leq j < j + τ (x) \leq ω^{2} (x) .

Finally, for

h = 1, . . ., K

\int^{¯} f_{h} < C_{γ} Γ_{L^{''}} 2^{- M + 1} < Γ \cdot 2^{- M + 1},

and

\int^{¯} f_{K + 1} = \bar{λ} (F_{L^{''}}) < 2^{- M + 1} < Γ \cdot 2^{- M + 1} .

We need to replace

X_{K + 1, L^{''}}

by a suitably chosen

X_{K + 1}

which is

M

-

0.99

-distributed, pairwise independent from

X_{h}

when

h = 1, . . ., K

and 100 holds with

h = K + 1

as well; in fact, this is the easiest part since by choosing

X_{K + 1}

so that

X_{K + 1} \leq X_{K + 1, L^{''}}

then 101 yields 100 .

Since

L^{''}

is the first index when

\bar{λ} (F_{L^{''}}) < 2^{- M}

we have

\bar{λ} (F_{L^{''} - 1}) \geq 2^{- M}

which by 85 implies

\begin{matrix} \bar{λ} (F_{L^{''}}) > (1 - 2 γ) 2^{- M} . \end{matrix}

(102)

What is the distribution of

X_{K + 1, L^{''}}

? Recall

F_{L^{''}} = {x : f_{K + 1} (x) = 1}

1 - 2 γ < r_{L} = \bar{λ} (F_{L}) / \bar{λ} (F_{L - 1}) < 1 - \frac{γ}{2},

for

L = 1, . . ., L^{''},

and

\bar{λ} (F_{L}) = r_{0} \cdot \cdot \cdot r_{L} = r_{1} \cdot \cdot \cdot r_{L}

. By 90

\begin{matrix} \frac{1}{1 - ρ} 2^{- M} > \frac{1}{1 - ρ} \bar{λ} (F_{L^{''}}) > \bar{λ} (S_{L^{''}, 0}) > (1 - ρ) \bar{λ} (F_{L^{''}}) > (1 - 3 γ) 2^{- M}, \end{matrix}

(103)

where the last inequality holds if

ρ > 0

is so small that

(1 - ρ) (1 - 2 γ) > (1 - 3 γ) .

Recall that

1 > {\tilde{C}}_{γ} > 1 - 10^{- 6}

and we can choose

ρ^{'} > 0

so that we can assume that

\begin{matrix} 0.999 < {\tilde{C}}_{γ} (1 - ρ^{'}) < 1.001 . \end{matrix}

(104)

By 83 ,

X_{K + 1, L^{''}} (x) = (1 - ρ^{'}) {\tilde{C}}_{γ} \cdot 1 = (1 - ρ^{'}) {\tilde{C}}_{γ} \bar{λ} (F_{0})

x \in S_{L^{''}, 0} .

By 83 and 86 if

x \in S_{L^{''}, l} \ S_{L^{''}, l - 1}

then for

l = 1, . . ., L^{''}

\begin{matrix} X_{K + 1, L^{''}} (x) = (1 - ρ^{'}) r_{0} \cdot \cdot \cdot r_{l} {\tilde{C}}_{γ} = (1 - ρ^{'}) \bar{λ} (F_{l}) {\tilde{C}}_{γ} . \end{matrix}

(105)

This and 104 imply that for

x \in S_{L^{''}, L^{''}} \ S_{L^{''}, L^{''} - 1}

\begin{matrix} X_{K + 1, L^{''}} (x) = (1 - ρ^{'}) {\tilde{C}}_{γ} \bar{λ} (F_{L^{''}}) < 2^{- M} (1 - ρ^{'}) {\tilde{C}}_{γ} < 0.999 \cdot 2^{- M + 1} . \end{matrix}

(106)

Using 91 we have the following measure estimate:

\frac{1}{(1 - ρ) r_{0} \cdot \cdot \cdot r_{l}} \bar{λ} (S_{L^{''}, 0}) > \bar{λ} (S_{L^{''}, l}) > (1 - ρ) \frac{1}{r_{0} \cdot \cdot \cdot r_{l}} \bar{λ} (S_{L^{''}, 0}),

which is equivalent to

\begin{matrix} \frac{1}{1 - ρ} \bar{λ} (S_{L^{''}, 0}) > \bar{λ} (F_{l}) \bar{λ} (S_{L^{''}, l}) > (1 - ρ) \bar{λ} (S_{L^{''}, 0}) . \end{matrix}

(107)

Suppose for

l = 0, . . ., M - 1,

ℓ^{'} (l)

is chosen so that

\begin{matrix} X_{K + 1, L^{''}} (x) \geq 0.999 \cdot 2^{- l} when x \in S_{L^{''}, ℓ^{'} (l)}, \end{matrix}

(108)

but

X_{K + 1, L^{''}} (x) < 0.999 \cdot 2^{- l}

for some

x \in S_{L^{''}, ℓ^{'} (l) + 1}

, by 106 such an

ℓ^{'} (l) \leq L^{''}

exists. By 105

(1 - ρ^{'}) \bar{λ} (F_{ℓ^{'} (l) + 1}) {\tilde{C}}_{γ} < 0.999 \cdot 2^{- l},

and

(1 - ρ^{'}) \bar{λ} (F_{ℓ^{'} (l)}) {\tilde{C}}_{γ} \geq 0.999 \cdot 2^{- l}

hold. Therefore, using

\bar{λ} (F_{ℓ^{'} (l) + 1}) / \bar{λ} (F_{ℓ^{'} (l)}) > (1 - 2 γ)

we infer

\begin{matrix} 0.999 \cdot 2^{- l} \leq (1 - ρ^{'}) \bar{λ} (F_{ℓ^{'} (l)}) {\tilde{C}}_{γ} < \frac{0.999}{1 - 2 γ} 2^{- l} . \end{matrix}

(109)

Set

S_{L^{''}, ℓ^{'} (- 1)} = \emptyset .

By using 105 and the above definitions, estimates for

l = 0, . . ., M - 1,

x \in S_{L^{''}, ℓ^{'} (l)} \ S_{L^{''}, ℓ^{'} (l - 1)}

we have

\begin{matrix} 0.999 \cdot 2^{- l} \leq X_{K + 1, L^{''}} (x) < 0.999 \cdot 2^{- (l - 1)} . \end{matrix}

(110)

By 107

\bar{λ} (S_{L^{''}, ℓ^{'} (l)}) < \frac{1}{1 - ρ} \bar{λ} (S_{L^{''}, 0}) \frac{1}{\bar{λ} (F_{ℓ^{'} (l)})} <

(using 103 and 109 )

\frac{1}{(1 - ρ)^{2}} \bar{λ} (F_{L^{''}}) \frac{(1 - ρ^{'}) {\tilde{C}}_{γ}}{0.999 \cdot 2^{- l}} < \frac{(1 - ρ^{'}) {\tilde{C}}_{γ} 2^{l}}{0.999 \cdot (1 - ρ)^{2}} 2^{- M},

on the other hand, by using 107

\bar{λ} (S_{L^{''}, ℓ^{'} (l)}) > \frac{(1 - ρ) \bar{λ} (S_{L^{''}, 0})}{\bar{λ} (F_{ℓ^{'} (l)})} >

(using 103 and 109 again)

\frac{(1 - ρ)^{2} \bar{λ} (F_{L^{''}}) (1 - ρ^{'}) {\tilde{C}}_{γ} (1 - 2 γ)}{0.999 \cdot 2^{- l}} >

(using 102 )

(1 - ρ)^{2} (1 - 2 γ)^{2} 2^{- M} \cdot 2^{l} (1 - ρ^{'}) {\tilde{C}}_{γ} .

Thus for

l = 0, . . ., M - 1

\begin{matrix} \bar{λ} (S_{L^{''}, ℓ^{'} (l)} \ S_{L^{''}, ℓ^{'} (l - 1)}) > \end{matrix}

(111)

(1 - ρ)^{2} (1 - 2 γ)^{2} 2^{- M + l} (1 - ρ^{'}) {\tilde{C}}_{γ} - \frac{(1 - ρ^{'}) {\tilde{C}}_{γ}}{0.999 \cdot (1 - ρ)^{2}} \cdot 2^{- M + l - 1} > 0.99 \cdot 2^{- M + l - 1}

if parameters are chosen properly, that is,

ρ

and

ρ^{'}

are sufficiently close to

0

, and recalling that

0 < γ < γ_{0} < 10^{- 6}

and

1 > {\tilde{C}}_{γ} > 1 - 10^{- 6}

. By 110 if

l = 0, . . ., M - 1,

x \in S_{L^{''}, ℓ^{'} (l)} \ S_{L^{''}, ℓ^{'} (l - 1)}

we have

X_{K + 1, L^{''}} (x) \geq 0.999 \cdot 2^{- l} .

By 105 ,

X_{K + 1, L^{''}}

takes different constant values on the set

S_{L^{''}, 0}

and on the sets

S_{L^{''}, l} \ S_{L^{''}, l - 1}

for

l = 1, . . ., L^{''} .

We also know that

X_{K + 1, L^{''}}

is pairwise independent from

X_{h}

for

h = 1, . . ., K .

Hence any function which is constant on the sets

S_{L^{''}, 0}

S_{L^{''}, l} \ S_{L^{''}, l - 1}

l = 1, . . ., L^{''}

is still pairwise independent from

X_{h}

for

h = 1, . . ., K .

Set

X_{K + 1}^{'} (x) = 0.99 \cdot 2^{- l}

x \in S_{L^{''}, ℓ^{'} (l)} \ S_{L^{''}, ℓ^{'} (l - 1)}

for

l = 0, . . ., M - 1 .

Set

S_{K + 1}^{'} (x) = 0

x \notin S_{L^{''}, ℓ^{'} (M - 1)} .

Now

X_{K + 1}^{'} \leq X_{K + 1, L^{''}}

and it is still pairwise independent from

X_{h}

h = 1, . . ., K .

It takes its values in

{0, 0.99, . . ., 0.99 \cdot 2^{- M + 1}}

but it is

M

-

0.99

-“super” distributed, by this we mean that

\bar{λ} ({x \in R : X_{K + 1}^{'} (x) = 0.99 \cdot 2^{- l}}) =

\bar{λ} (S_{L^{''}, ℓ^{'} (l)} \ S_{L^{''}, ℓ^{'} (l - 1)}) \geq 0.99 \cdot 2^{- M + (l - 1)}

holds for

l = 0, . . ., M - 1 .

Since our measure space is nonatomic one can choose an

M

-

0.99

-distributed

X_{K + 1} \leq X_{K + 1}^{'}

so that it is still pairwise independent from

X_{h}

for

h = 1, . . ., K .

5 Proof of the Main Result

Lemma 4 yields the next theorem which as we will see easily implies Theorem 1 .

Theorem 6. Given

δ > 0

M

and

K

there exist

τ_{0} \in N,

{\bar{E}}_{δ} \subset [0, 1),

a measurable transformation

T : [0, 1) \to [0, 1)

T (x) = x + \frac{1}{τ_{0}}

modulo

1

f : [0, 1) \to [0, + \infty)

X_{h},

h = 1, . . ., K

which are pairwise independent

M

-

0.99

-distributed random variables defined on

[0, 1)

equipped with the Lebesgue measure,

λ

, such that

λ ({\bar{E}}_{δ}) < δ

, for all

x \in [0, 1) \ {\bar{E}}_{δ}

there exists

N_{x}

satisfying

\frac{1}{N_{x}} \sum_{k = 1}^{N_{x}} f (T^{k^{2}} (x)) > \sum_{h = 1}^{K} {\bar{X}}_{h} (x),

and

\int_{[0, 1)} f d λ < K \cdot 2^{- M + 2} .

Proof. Use Lemma 4 with $δ$ , $Ω = 1000,$ $Γ = 1.1$ , $A = 1,$ $P = \emptyset$ to obtain a $K - M$ family with $E_{δ}$ , $f_{h}$ and $X_{h}$ periodic by $τ = τ_{0} .$ Set ${\bar{E}}_{δ} = \frac{1}{τ_{0}} E_{δ} \cap [0, 1)$ and for $x \in [0, 1)$ set ${\bar{f}}_{h} (x) = f_{h} (τ_{0} \cdot x),$ ${\bar{X}}_{h} (x) = X_{h} (τ_{0} \cdot x)$ .
Assume $x \in [0, 1) \ {\bar{E}}_{δ}$ . Since $Ω α (τ_{0} \cdot x) τ (τ_{0} \cdot x) < ω (τ_{0} \cdot x)$ we have $α (τ_{0} \cdot x) = n < n + (Ω - 1) α (τ_{0} \cdot x) τ (τ_{0} \cdot x) < ω (τ_{0} \cdot x)$ and $\frac{1}{(Ω - 1) α (τ_{0} \cdot x) τ (τ_{0} \cdot x)} \sum_{k = α (τ_{0} \cdot x)}^{α (τ_{0} \cdot x) + (Ω - 1) α (τ_{0} \cdot x) τ (τ_{0} \cdot x) - 1} f_{h} (τ_{0} \cdot T^{k^{2}} x) =$ $\frac{1}{(Ω - 1) α (τ_{0} \cdot x) τ (τ_{0} \cdot x)} \sum_{k = α (τ_{0} \cdot x)}^{α (τ_{0} \cdot x) + (Ω - 1) α (τ_{0} \cdot x) τ (τ_{0} \cdot x) - 1} f_{h} (τ_{0} \cdot x + k^{2}) > X_{h} (τ_{0} x) .$ Since $f_{h} \geq 0$ , if we let $N_{x} = α (τ_{0} \cdot x) + (Ω - 1) α (τ_{0} \cdot x) τ (τ_{0} \cdot x) - 1$ , then for all $h = 1, . . ., K$ $\frac{1.01}{N_{x}} \sum_{k = 1}^{N_{x}} {\bar{f}}_{h} (T^{k^{2}} (x)) = \frac{1.01}{N_{x}} \sum_{k = 1}^{N_{x}} f_{h} (τ_{0} \cdot T^{k^{2}} (x)) \geq {\bar{X}}_{h} (x) .$ Let $f (x)$ be the restriction of $\sum_{h = 1}^{K} 1.01 \cdot {\bar{f}}_{h} (x)$ onto $[0, 1) .$ Then $\int_{0}^{1} f (x) d λ (x) = 1.01 \sum_{h = 1}^{K} \int^{¯} f_{h} < 1.01 \cdot Γ \cdot K \cdot 2^{- M + 1} < K \cdot 2^{- M + 2} .$ For all $x \in [0, 1) \ {\bar{E}}_{δ}$ there exists $N_{x}$ such that $\frac{1}{N_{x}} \sum_{k = 1}^{N_{x}} f (T^{k^{2}} x) > \sum_{h = 1}^{K} {\bar{X}}_{h} (x) .$

Now we can complete the proof of Theorem 1 .

Proof. For each $p \in N$ set $M_{p} = 4^{p} .$ On the probability space $([0, 1), λ)$ consider $M_{p} - 0.99$ -distributed random variables ${\bar{X}}_{h}$ for $h = 1, . . ., K$ for a sufficiently large $K$ . Assume that $u$ denotes the mean of these variables. An easy calculation shows that $u = \int_{[0, 1]} {\bar{X}}_{h} (x) d λ (x) = \sum_{l = 0}^{M_{p} - 1} {0.99}^{2} \cdot 2^{- l} \cdot 2^{- M_{p} + l - 1} > 0.9 \cdot M_{p} \cdot 2^{- M_{p} - 1} .$ By the weak law of large numbers $λ {x : | \frac{1}{K} \sum_{h = 1}^{K} {\bar{X}}_{h} (x) - u | \geq \frac{u}{2}} \to 0 .$ Fix $K$ so large that $λ {x : \frac{1}{K} \sum_{h = 1}^{K} {\bar{X}}_{h} (x) \geq \frac{u}{2}} > 1 - \frac{1}{p},$ and let $U_{p}^{'} = {x : \frac{1}{K} \sum_{h = 1}^{K} {\bar{X}}_{h} (x) > \frac{0.9}{2} \cdot M_{p} \cdot 2^{- M_{p} - 1}} .$ We have $λ (U_{p}^{'}) > 1 - \frac{1}{p} .$ By Theorem 6 used with $δ = \frac{1}{p},$ $M_{p}$ and $K$ there exist $τ_{0} \in N,$ ${\bar{E}}_{1 / p} \subset [0, 1)$ and a periodic transformation $T : [0, 1) \to [0, 1),$ $T (x) = x + \frac{1}{τ_{0}}$ modulo $1,$ $f : [0, 1) \to [0, + \infty)$ , ${\bar{X}}_{h}$ pairwise independent $M_{p} - 0.99$ -distributed random variables defined on $[0, 1)$ such that $λ ({\bar{E}}_{1 / p}) < \frac{1}{p}$ and for all $x \in [0, 1) \ {\bar{E}}_{1 / p}$ there exists $N_{x}$ such that $\frac{1}{N_{x}} \sum_{k = 1}^{N_{x}} f (T^{k^{2}} x) > \sum_{h = 1}^{K} {\bar{X}}_{h} (x)$ and $\int_{[0, 1)} f d λ < K \cdot 2^{- M_{p} + 2} .$ Put $U_{p} = U_{p}^{'} \ {\bar{E}}_{1 / p} .$ Then $λ (U_{p}) > 1 - \frac{2}{p}$ and for $x \in U_{p}$ there exists $N_{x}$ such that $\frac{1}{N_{x}} \sum_{k = 1}^{N_{x}} f (T^{k^{2}} x) > \sum_{h = 1}^{K} {\bar{X}}_{h} (x) > K \cdot \frac{0.9}{2} \cdot M_{p} \cdot 2^{- M_{p} - 1} .$ Thus letting $t = K \cdot \frac{0.9}{2} \cdot M_{p} \cdot 2^{- M_{p} - 1}$ , and ${\tilde{U}}_{p} = {x : {sup}_{N} \frac{1}{N} \sum_{k = 1}^{N} f (T^{k^{2}} x) > t}$ we have $U_{p} \subset {\tilde{U}}_{p}$ and hence $λ ({\tilde{U}}_{p}) > 1 - \frac{2}{p} .$ On the other hand $\frac{\int | f | d λ}{t} < \frac{K \cdot 2^{- M_{p} + 2}}{K \cdot \frac{0.9}{2} \cdot M_{p} \cdot 2^{- M_{p} - 1}} < \frac{32}{M_{p}} .$ Hence, $λ ({\tilde{U}}_{p}) \to 1$ and $\int | f | d λ / t \to 0$ as $p \to \infty .$ Therefore there is no $C$ for which 2 holds with $μ = λ$ . This implies that the sequence $n_{k} = k^{2}$ is $L^{1}$ -universally bad.

References

I. Assani, Z. Buczolich and R. D. Mauldin “An $L^{1}$ Counting Problem in Ergodic Theory”, to appear in J. Anal. Math.
I. Assani, Z. Buczolich and R. D. Mauldin “Counting and convergence in Ergodic Theory”, Acta Univ. Carolinae. 45 (2004), 5–21.
J. Bourgain, “Pointwise ergodic theorems for arithmetic sets”, With an appendix by the author, Harry Fürstenberg, Yitzhak Katznelson and Donald S. Ornstein, Inst. Hautes Études Sci. Publ. Math. No. 69 (1989), 5–45.
J. Bourgain, “An approach to pointwise ergodic theorems”, Geometric aspects of functional analysis (1986/87), 204–223, Lecture Notes in Math., 1317, Springer, Berlin, 1988.
J. Bourgain, “On the pointwise ergodic theorem on $L^{p}$ for arithmetic sets”, Israel J. Math. 61 (1988), no. 1, 73–84.
J. Bourgain, “On the maximal ergodic theorem for certain subsets of the integers”, Israel J. Math. 61 (1988), no. 1, 39–72.
J. Bourgain, “Almost sure convergence in ergodic theory”, Almost everywhere convergence. Proceedings of the International Conference on Almost Everywhere Convergence in Probability and Ergodic Theory held in Columbus, Ohio, June 11–14, 1988. Edited by Gerald A. Edgar and Louis Sucheston. Academic Press, Inc., Boston, MA, (1989).
J. P. Conze, “Convergence des moyennes ergodiques pour des sous suites”, Bull. Soc. Math. France, 35 (1973), 7-15.
A. Garsia, Topics in Almost Everywhere Convergence, Chicago, Markham Publ. Co. 1970.
G. H. Hardy and E. M. Wright An introduction to the Theory of Numbers, Fifth edition, Oxford Science Publications, 1979.
P. Kurlberg and Z. Rudnick, “The distribution of spacings between quadratic residues”, Duke Math. J. 100 (1999), no. 2, 211-242.
P. Kurlberg, “The distribution of spacings between quadratic residues II”, Israel J. Math. 120 (2000), part A, 205-224.
J. Lamperti, Probability: A survey of the Mathematical Theory, W. A. Benjamin Inc., New York (1966).
I. Niven and H. S. Zuckerman An Introduction to the Theory of Numbers,
R. Peralta, “On the distribution of quadratic residues and nonresidues modulo a prime number”, Math. Comp. 58 (1992), no. 197, 433-440.
J. Rosenblatt and M. Wierdl “Pointwise ergodic theorems via harmonic analysis”, Ergodic theory and its connections with harmonic analysis (Alexandria, 1993), 3–151, London Math. Soc. Lecture Note Ser., 205, Cambridge Univ. Press, Cambridge, 1995.
S. Sawyer, “Maximal inequalities of weak type”, Ann. of Math. 84 (1966) no. 4, 157-174.
E. M. Stein, “On limits of sequences of operators”, Ann. of Math. 74 (1961) no. 4, 140-170.