9 Solvability of linear equations within weak
mixing sets
Alexander Fish
November 4, 2018
Abstract
We introduce a new class of “random” subsets of natural numbers,
WM sets. This class contains normal sets (sets whose characteristic
function is a normal binary sequence). We establish necessary and suf-
ficient conditions for solvability of systems of linear equations within
every WM set and within every normal set. We also show that any
partition-regular system of linear equations with integer coefficients is
solvable in any WM set.
1 Introduction
1.1 Algebraic patterns within subsets of N
We use extensively the notion of “algebraic pattern”. By an algebraic pattern
we mean a solution of a diophantine system of equations. For example, an
arithmetic progression of length k is an algebraic pattern corresponding to
the following diophantine system:
2xi = xi−1 + xi+1, i = 2, 3, . . . , k − 1.
We investigate the problem of finding linear algebraic patterns (these cor-
respond to linear systems) within a family of subsets of natural numbers
satisfying some asymptotic conditions.
For instance, by Szemerédi theorem, subsets of positive upper Banach density
(all S ⊂ N : d∗(S) > 0, where d∗(S) = lim supbn−an→∞
|S∩[an,bn]|
bn−an+1
) contain the
pattern of an arithmetic progression of any finite length (see [12]).
http://arxiv.org/abs/0704.0600v2
On the other hand, Schur patterns, namely triples of the form {x, y, x+ y},
which correspond to solutions of the so-called Schur equation, x+ y = z, do
not necessarily occur in sets of positive upper density. For example, the odd
numbers do not contain this pattern. But if we take a random subset of N
by picking natural numbers with probability 1
independently, then this set
contains the Schur pattern with probability 1.
There is a deterministically defined analog of a random set - a normal set. To
define a normal set we recall the notions of a normal infinite binary sequence
and of a normal number.
An infinite {0, 1}-valued sequence λ is called a normal sequence if every
finite binary word w occurs in λ with frequency 1
, where |w| is the length
of w.
The more familiar notion is that of a normal number x ∈ [0, 1]. If to a number
x ∈ [0, 1] we associate its dyadic expansion x =
with xi ∈ {0, 1},
then x is called a normal number if the sequence (x1, x2, . . . , xn, . . .) is a
normal sequence.
Definition 1.1.1 A set S ⊂ N is called normal if the 0-1 sequence 1S
(1S(n) = 1 ⇔ n ∈ S) is normal.
Normal sets exhibit a non-periodic, “random” behavior. We notice that if S
is a normal set then S − S contains N. Therefore, the equation
z − y = x
is solvable within every normal set. This implies that every normal set con-
tains Schur patterns.
Normal sets are related to a class of dynamical systems displaying maximal
randomness; namely Bernoulli systems. In this work we investigate occur-
rence of linear patterns in sets corresponding to dynamical systems with a
lower degree of randomness, so called weakly mixing dynamical systems. The
sets we obtain will be called WM sets. We will make this precise in the next
section.
In the present paper we treat the following problem:
Give a complete characterization of the linear algebraic patterns which occur
in all WM sets.
Remark 1.1.1 It will follow from our definition of a WM set, that any
normal set is a WM set.
The problem of the solvability of a nonlinear equation or system of equa-
tions is beyond the limits of the technique used in this paper. Nevertheless,
some particular equations might be analyzed. In [3] it is shown that there
exist normal sets in which the multiplicative Schur equation xy = z is not
solvable.
1.2 Generic points and WM sets
For a formal definition of WM sets we need the notions of measure preserving
systems and of generic points.
Definition 1.2.1 Let X be a compact metric space, B the Borel σ-algebra
on X; let T : X → X be a continuous map and µ a probability measure on
B. The quadruple (X,B, µ, T ) is called a measure preserving system if
for every B ∈ B we have µ(T−1B) = µ(B).
For a compact metric space X we denote by C(X) the space of continuous
functions on X with the uniform norm.
Definition 1.2.2 Let (X,B, µ, T ) be a measure preserving system. A point
ξ ∈ X is called generic for the system (X,B, µ, T ) if for any f ∈ C(X) we
f(T nξ) =
f(x)dµ(x). (1.1)
Example: Consider the Bernoulli system: (X = {0, 1}N0,B, µ, T ), where X
is endowed with the Tychonoff topology, B is Borel σ-algebra on X , T is the
shift to the left, µ is the product measure of µi’s where µi(0) = µi(1) =
and N0 = N ∪ {0}. An alternative definition of a normal set which is purely
dynamical is the following.
A set S is normal if and only if the sequence 1S ∈ {0, 1}
N0 is a generic
point of the foregoing Bernoulli
system.
The notion of a WM set generalizes that of a normal set, where the role
played by Bernoulli dynamical system is taken over by dynamical systems of
more general character.
Let ξ(n) be any {0, 1}−valued sequence. There is a natural dynamical system
(Xξ, T ) connected to the sequence ξ:
On the compact space Ω = {0, 1}N0 endowed with the Tychonoff topology,
we define a continuous map T : Ω −→ Ω by (Tω)n = ωn+1. Now for any ξ in
Ω we define
Xξ = {T nξ}n∈N0 ⊂ Ω.
Let A be a subset of N. Choose ξ = 1A and assume that for an appropriate
measure µ, the point ξ is generic for (Xξ,B, µ, T ). We can attach to the set
A dynamical properties associated with the system (Xξ,B, µ, T ).
We recall the notions of ergodicity, total ergodicity and weak-mixing in er-
godic theory:
Definition 1.2.3 A measure preserving system (X,B, µ, T ) is called er-
godic if every A ∈ B which is invariant under T , i.e. T−1(A) = A, satisfies
µ(A) = 0 or 1.
A measure preserving system (X,B, µ, T ) is called totally ergodic if for ev-
ery n ∈ N the system (X,B, µ, T n) is ergodic.
A measure preserving system (X,B, µ, T ) is called weakly mixing if the
system (X ×X,BX×X , µ× µ, T × T ) is ergodic.
In our discussion of WM sets corresponding to weakly mixing systems, we
shall add the proviso that the dynamical system in question not be the trivial
1-point system supported on the point x ≡ 0. This implies that the “density”
of the set in question be positive.
Definition 1.2.4 Let S ⊂ N. If the limit of 1
n=1 1S(n) exists as N → ∞
we call it the density of S and denote by d(S).
Definition 1.2.5 A subset S ⊂ N is called a WM set if 1S is a generic
point of the weakly mixing system (X1S ,B, µ, T ) and d(S) > 0.
1.3 Solvability of linear diophantine systems within
WM sets and normal sets
Our main result is a complete characterization of linear systems of diophan-
tine equations which are solvable within every WM set. The characterization
is given by describing affine subspaces of Qk which intersect Ak, for any WM
set A ⊂ N.
Theorem 1.3.1 An affine subspace of Qk intersects Ak for every WM set
A ⊂ N if and only if it contains a set of the form
{n~a+m~b+ ~f |n,m ∈ N},
where ~a,~b, ~f have the following description:
~a = (a1, a2, . . . , ak)
t, ~b = (b1, b2, . . . , bk)
t ∈ Nk, ~f = (f1, f2, . . . , fk)
t ∈ Zk and
there exists a partition F1, . . . , Fl of {1, 2, . . . , k} such that:
a) for every r ∈ {1, . . . , l} there exist c1,r, c2,r ∈ N, such that for every i ∈ Fr
we have ai = c1,r , bi = c2,r and for every j ∈ {1, . . . , k} \ Fr we have
aj bj
c1,r c2,r
6= 0.
∀r ∈ {1, 2, . . . , l} ∃cr ∈ Z such that ∀i ∈ Fr : fi = cr.
We also classify all affine subspaces of Qk which intersect Ak for any normal
set A ⊂ N.
Theorem 1.3.2 An affine subspace of Qk intersects Ak for every normal set
A ⊂ N if and only if it contains a set of the form
{n~a+m~b+ ~f |n,m ∈ N},
where ~a,~b, ~f have the following description:
~a = (a1, a2, . . . , ak)
t, ~b = (b1, b2, . . . , bk)
t ∈ Nk, ~f = (f1, f2, . . . , fk)
t ∈ Zk
and there exists a partition F1, . . . , Fl of {1, 2, . . . , k} such that for every
r ∈ {1, . . . , l} there exist c1,r, c2,r ∈ N, such that for every i ∈ Fr we have
ai = c1,r , bi = c2,r and for every j ∈ {1, . . . , k} \ Fr we have
aj bj
c1,r c2,r
6= 0.
A family of linear algebraic patterns that has been studied previously are the
“partition regular” patterns. These are patterns which for any finite partition
of N: N = C1∪C2 ∪ . . .∪Cr, the pattern necessarily occurs in some Cj. (For
example by van der Waerden’s theorem, arithmetic progressions are partition
regular and by Schur’s theorem the Schur pattern is also partition regular).
A theorem of Rado gives a complete characterization of such patterns. We
will show in Proposition 4.1 that every linear algebraic pattern which is
partition-regular occurs in every WM set.
It is important to mention that if we weaken the requirement of weak mixing
to total ergodicity, then in the resulting family of sets, Rado’s patterns need
not necessarily occur. For example, for α 6∈ Q the set
n ∈ N|nα (mod 1) ∈
is totally ergodic, i.e., 1S is a generic point for a totally ergodic system and
the density of S is positive, but the equation x+ y = z is not solvable within
In the separate paper [4] we will address the question of solvability of more
general algebraic patterns, not necessarily linear, in totally ergodic and WM
sets.
The structure of the paper is the following. In Section 2 we prove the direction
“⇐” of Theorems 1.3.1 and 1.3.2. In Section 3, by use of a probabilistic
method, we prove the direction “⇒” of Theorems 1.3.1 and 1.3.2. In Section
4 we show that every linear system which is solvable in one of the cells of any
finite partition of N is also solvable within every WM set. The paper ends
with Appendix in which we collected proofs of technical statements which
have been used in Sections 2 and 3.
1.4 Acknowledgments
This paper is a part of the author’s Ph.D. thesis. I thank my advisor Prof.
Hillel Furstenberg for introducing me to ergodic theory and for many useful
ideas which I learned from him. I thank Prof. Vitaly Bergelson for fruitful
discussions and valuable suggestions. Also, I would like to thank an anony-
mous referee for numerous valuable remarks.
2 Proof of Sufficiency
Notation: We introduce the scalar product of two vectors v, w of length N
as follows:
< v,w >N
v(n)w(n).
We denote by L2(N) the (finite-dimensional) Hilbert space of all real vectors
of length N with the aforementioned scalar product.
We define: ‖ w ‖2N
=< w,w >N .
First we state the following proposition which will prove useful in the proof
of the sufficiency of the conditions of Theorem 1.3.1.
Proposition 2.1 Let Ai ⊂ N (1 ≤ i ≤ k) be WM sets. Let
ξi(n)
= 1Ai(n)−d(Ai), where d(Ai) denotes density of Ai. Suppose there are
(a1, b1), (a2, b2), . . . , (ak, bk) ∈ Z
2, such that ai > 0, 1 ≤ i ≤ k, and for every
i 6= j
ai bi
aj bj
6= 0.
Then for every ε > 0 there exists M(ε) ∈ N, such that for every M ≥ M(ε)
there exists N(M, ε) ∈ N, such that for every N ≥ N(M, ε)
where w(n)
m=1 ξ1(a1n+b1m)ξ2(a2n+b2m) . . . ξk(akn+bkm) for every
n = 1, 2, . . . , N .
Since the proof of Proposition 2.1 involves many technical details, first we
show how our main result follows from it. Afterwards we state and prove all
the lemmas necessary for the proof of Proposition 2.1.
We use an easy consequence of Proposition 2.1.
Corollary 2.1 Let A be a WM set. Let k ∈ N, suppose
(a1, b1), (a2, b2), . . . , (ak, bk) ∈ Z
2 satisfy all requirements of Proposition 2.1
and suppose f1, . . . , fk ∈ Z. Then for every δ > 0 there exists M(δ) such
that ∀M ≥ M(δ) there exists N(M, δ) such that ∀N ≥ N(M, δ) we have
∣‖v‖N − d
∣ < δ,
where v(n)
m=1 1A(a1n + b1m + f1)1A(a2n + b2m + f2) . . . 1A(akn +
bkm+ fk) for every n = 1, 2, . . . , N .
Proof. We rewrite v(n) in the following form:
v(n) =
(ξ1(a1n+ b1m) + d(A)) . . . (ξk(akn + bkm) + d(A)),
for every n = 1, 2, . . . , N . We introduce normalized WM sequences ξi(n) =
ξ(n+ fi) (of zero average), where ξ(n) = 1A(n)− d(A). By use of triangular
inequality and Proposition 2.1 it follows that for big enoughM and N (which
depends on M) ‖v‖N is as close as we wish to d
k(A). This finishes the proof.
Proof. (of Theorem 1.3.1, ⇚) Let A ⊂ N be a WM set. Without loss of
generality, we can assume that for every r : 1 ≤ r ≤ l we have r ∈ Fr.
It follows from Corollary 2.1 that the vector v defined by
1A(a1n+ b1m+ f1)1A(a2n + b2m+ f2) . . . 1A(aln + blm+ fl)
for every n = 1, 2, . . . , N , is not identically zero for big enough M and N .
But this is possible only if for some n,m ∈ N we have
(a1n+ b1m+ f1, a2n+ b2m+ f2, . . . , aln+ blm+ fl) ∈ A
The latter implies that Ak intersects the affine subspace.
Proof. (of Theorem 1.3.2, ⇚) For every r : 1 ≤ r ≤ l take all indices which
comprise Fr. Denote this sequence of indices by Ir. Denote cr = mini∈Ir fi.
Let Sr be the set of all non-zero shifts of fi, i ∈ Fr, centered at cr, i.e.,
Sr = {fi − cr | i ∈ Fr, fi > cr}.
For example, if the sequence of fi’s where i ∈ F1 is (−5, 2, 3, 2,−5), then
S1 = {7, 8}.
Let A be a normal set. For every r : 1 ≤ r ≤ l we define sets Ar by
Ar = {n ∈ N ∪ {0} |n ∈ A and n+ s ∈ A, ∀s ∈ Sr}.
Then Ar is no longer a normal set provided that Sr 6= ∅ (d(A) =
21+|Sr |
But, for all r : 1 ≤ r ≤ l the sets Ar’s are WM sets.
Without loss of generality, assume that for every r : 1 ≤ r ≤ l we have
r ∈ Fr.
From Proposition 2.1 it follows that for big enough M and N
1A1(a1n+ b1m)1A(a2n+ b2m) . . . 1A(aln+ blm) ≈
d(Ar).
The latter ensures that there exist m,n ∈ N such that
(a1n+ b1m+ f1, . . . , akn+ bkm+ fk) ∈ A
Now we state and prove all the claims that are required in order to prove
Proposition 2.1.
Definition 2.1 Let ξ be a WM-sequence (ξ is a generic point for a weakly
mixing system (Xξ,BXξ , µ, T )) of zero average. The autocorrelation function
of ξ of length j ∈ N with the shifts ~i = (i1, i2, . . . , ij) ∈ Z
j and r ∈ Z is the
sequence ψ
which is defined by
(n) =
w∈{0,1}j
ξ(n+ r + w ·~i), n ∈ N,
where w ·~i is the usual scalar product in Qj, and
(n) = 0, n ≤ 0.
Lemma 2.1 Let ξ be a WM-sequence of zero average and suppose ε, δ >
0, b ∈ Z \ {0}. Then for every j ≥ 1, (c1, c2, . . . , cj) ∈ (Z \ {0})
j and
(r1, r2, . . . , rj) ∈ Z
j there exist I = I(ε, δ, c1, . . . , cn), a set S ⊂ [−I, I]
density at least 1−δ and N(S, ε) ∈ N, such that for every N ≥ N(S, ε) there
exists L(N, S, ε) such that for every L ≥ L(N, S, ε)
r,(c1i1,...,cjij)
(l + bn)
for every (i1, i2, . . . , ij) ∈ S, where r =
k=1 rk.
Proof. We note that it is sufficient to prove the lemma in the case c1 =
c2 = . . . = cj = 1, since if the average of nonnegative numbers over a whole
lattice is small, then the average over a sublattice of a fixed positive density
is also small.
Recall that ξ ∈ Xξ
= {T nξ}∞n=0 ⊂ supp(ξ)
N0, where T is the usual shift to
the left on the dynamical system supp(ξ)N0, and by the assumption that ξ
is a WM-sequence of zero average it follows that ξ is a generic point of the
weakly mixing system (Xξ,BXξ , µ, T ) and the function f : f(ω)
= ω0 has
zero integral.
Denote ~i = (i1, . . . , ij).
We define functions g
on Xξ by
T r+ǫ·
~i ◦ f,
ǫ∈V ∗
T r+ǫ·
~i ◦ f,
where Vj is the j-dimensional discrete cube {0, 1}
j and V ∗j is the j-dimensional
discrete cube except the zero point.
Notice that
(T nξ) = ψ
We use the following theorem which is a special case of a multiparameter
weakly mixing PET of Bergelson and McCutcheon (theorem A.1 in [2]; it is
also a corollary of Theorem 13.1 of Host and Kra in [9]).
Let (X, µ, T ) be a weakly mixing system. Given an integer k and 2k bounded
functions fǫ on X, ǫ ∈ Vk , the functions
Ni −Mi
n∈[M1,N1)×...[Mk,Nk)
ǫ∈V ∗
T ǫ1n1+...ǫknk ◦ fǫ
converge in L2(µ) to the constant limit
ǫ∈V ∗
when N1 −M1, . . . , Nk −Mk tend to +∞.
From this theorem applied to the weakly mixing system Xξ × Xξ and the
functions fǫ(x) = T
r ◦ f ⊗ T r ◦ f for every ǫ ∈ Vj , we obtain for every Folner
sequence {Fn} in N
j that an average over the multi-index ~i = {i1, . . . , ij} of
on Fn’s converges to zero in L
2(µ) (the integral of T r ◦ f ⊗ T r ◦ f
is zero). Thus
Xξ×Xξ
Ni −Mi
~i∈[M1,N1)×...×[Mj,Nj)
(y)dµ(x)dµ(y) =
Ni −Mi
~i∈[M1,N1)×...×[Mj,Nj)
(x)dµ(x)
as N1 −M1, . . . , Nj −Mj → ∞.
As a result we obtain the following statement:
For every ε > 0, j ∈ N and every fixed (r1, r2, . . . , rj) ∈ N
j, there exists a
subset R ⊂ Nj of lower density equal to one, such that
< ε (2.1)
for every ~i ∈ R, where r =
k=1 rj.
Recall that lower density of a subset R ⊂ Nj is defined to be
d∗(R) = lim inf
N1−M1,...,Nj−Mj→∞
#{R ∩ [M1, N1)× . . .× [Mj , Nj)}
k=1(Nk −Mk)
Recall that ψ
(l + bn) = g
T l+bnξ
The definition of the sequences ψj implies
r1,~i
(l + bn)
= lim
r2,(±i1,...,±ij)
(l ± bn)
for any r1, r2 ∈ Z, where ~i = (i1, . . . , ij).
Therefore, in order to prove Lemma 2.1 it is sufficient to show the following:
For every ε, δ > 0 and for any a priori chosen b ∈ N there exists I(ε, δ) ∈ N,
such that for every I ≥ I(ε, δ) there exists a subset S ⊂ [1, I]j of density
at least 1 − δ (namely, we have
|S∩[1,I)j |
≥ 1 − δ) and N(S, ε) ∈ N, such
that for every N ≥ N(S, ε) there exists L(N, S, ε) ∈ N such that for every
L ≥ L(N, S, ε) the following holds for every ~i ∈ S:
(l + bn)
Let b ∈ N. Continuity of the function
g0,~i and genericity of the point ξ ∈ Xξ yield
(l + bn)
= lim
T bng0,~i
T bng0,~i
dµ. (2.2)
By applying the von Neumann ergodic theorem to the ergodic system
(Xξ,B, µ, T
b) (ergodicity follows from weak-mixing of the original measure
preserving system (Xξ,B, µ, T )) we have
T bng0,~i →
L2(Xξ)
g0,~idµ. (2.3)
From (2.1) there exists I(ε, δ) ∈ N big enough that for every I ≥ I(ε, δ) there
exists a set S ⊂ [1, I]j of density at least 1− δ such that
g0,~idµ
for all ~i ∈ S.
From equation (2.3) it follows that there exists N(S, ε) ∈ N, such that for
every N ≥ N(S, ε) we have
T bng0,~i
for all ~i ∈ S.
Finally, equation (2.2) implies that there exists L(N, S, ε) ∈ N, such that for
every L ≥ L(N, S, ε) we have
(l + bn)
for all ~i ∈ S.
The following lemma is a generalization of the previous lemma to a product
of several autocorrelation functions.
Lemma 2.2 Let ψ
r1,~i
, . . . , ψ
rk,~i
be autocorrelation functions of length j of
WM-sequences ξ1, . . . , ξk of zero average,
{c11, . . . , c
j , . . . , c
1, . . . , c
j} ∈ (Z \ {0})
jk and ε, δ > 0. Suppose
(a1, b1), (a2, b2), . . . , (ak, bk) ∈ Z
2, such that ai > 0 for all i : 1 ≤ i ≤ k and
for every i 6= j
ai bi
aj bj
6= 0.
(If k = 1 assume that b1 6= 0.)
Then there exists I(ε, δ) ∈ N, such that for every I ≥ I(ε, δ) there exist
S ⊂ [−I, I]j of density at least 1− δ, M(S, ε) ∈ N, such that for every M ≥
M(S, ε) there exists X(M,S, ε) ∈ N, such that for every X ≥ X(M,S, ε)
r1,(c
i1,...,c
(a1x+ b1m) . . . ψ
rk,(c
i1,...,c
(akx+ bkm)
for every (i1, i2, . . . , ij) ∈ S.
Proof. The proof is by induction on k.
THE CASE k = 1 (and arbitrary j):
If a1 = 1 then the statement of the lemma follows from Lemma 2.1. If a1 > 1
then by Proposition 5.1 of Appendix for a given ~i = (i1, . . . , ij) ∈ S we have
r1,(c
i1,...,c
(a1x+ b1m)
r1,(c
i1,...,c
(x+ b1m)
(2.4)
(Limits exist by genericity of the point ξ.)
By Lemma 2.1 the right hand side of (2.4) is small for large enough M . So,
for large enough X (depending on M and (i1, . . . , ij)) the statement of the
lemma is true. By finiteness of S we conclude that the statement of the
lemma holds for k = 1.
GENERAL CASE (k > 1):
Suppose that the statement holds for k − 1.
Denote
vm(x)
r1,(c
i1,...,c
(a1x+ b1m) . . . ψ
rk,(c
i1,...,c
(akx+ bkm).
Let ε, δ > 0. We show that there exists I(ε, δ) ∈ N such that for every
I > I(ε, δ) a set S ⊂ [−I, I]j of density at least 1− δ can be chosen satisfying
the following property:
There exists I(ε, S) ∈ N such that for every I > I(ε, S) there exists
M(I) ∈ N such that for all M > M(I) for a set of i’s in {1, 2, . . . , I} of
density at least 1− ε
we have
< vm, vm+i >X
(2.5)
for all (i1, . . . , ij) ∈ S.
The Van der Corput lemma (Lemma 5.1 of Appendix) finishes the proof.
Note that the set of “good” i’s in the interval {1, 2, . . . , I} depends on
(i1, . . . , ij) ∈ S.
Denote
< vm, vm+i >X
1,j+1
r1,(c
i1,...c
ij ,b1i)
(a1x+ b1m) . . . ψ
k,j+1
rk,(c
i1,...,c
ij ,bki)
(akx+ bkm)
Denote y = a1x+ b1m. Assume that (a1, b1) = d. Denote
B̃y,m = ψ
1,j+1
r1,(c
i1,...c
ij ,b1i)
(y) . . . ψ
k,j+1
rk,(c
i1,...,c
ij ,bki)
(a′ky + b
where a′p =
, b′p = bp − a
pb1, 2 ≤ p ≤ k. We rewrite Ã as follows:
y≡dl mod a1
m≡φ(l) mod
B̃y,m
+ δX,M . (2.6)
Here φ is a bijection of Za1
defined by the identity
for every 0 ≤ l ≤ a1
− 1, Y = a1X , a
p as above and δX,M accounts for
the fact that for small y’s and y’s close to Y there is a difference between
elements that are taken in the expression for Ã and in the expression on the
right hand side of equation (2.6). Nevertheless, we have δX,M → 0 if
Denote
C̃y,m = ψ
2,j+1
r2,(c
i1,...,c
ij ,b2i)
(a′2y + b
2m) . . . ψ
k,j+1
rk,(c
i1,...,c
ij ,bki)
(a′ky + b
It will suffice to prove that there exists I(ε, δ) ∈ N such that for every I >
I(ε, δ) we can find S ⊂ [−I, I]j of density at least 1 − δ with the following
property:
There exists I(ε, S) ∈ N such that for every I > I(ε, S) there exists
M(I) ∈ N such that for every M > M(I) we can find X(M) ∈ N such that
for every X > X(M) for a set of i’s in {1, 2, . . . , I} of density at least 1 − ε
we have
y≡dl mod a1
m≡φ(l) mod
C̃y,m
(2.7)
for all 0 ≤ l ≤ a1
− 1, for all (i1, . . . , ij) ∈ S.
Note that it is enough to prove the latter statement for every particular
l : 0 ≤ l ≤ a1
Denote the left hand side of inequality (2.7) for a fixed l by D̃l.
Introduce new variables z and n, such that y = za1+ dl and m = n
+φ(l).
We obtain
D̃l =
2,j+1
t2n,z,l
. . . ψ
k,j+1
tkn,z,l
2,j+1
(a2z + c2n + q2) . . . ψ
k,j+1
(akz + ckn+ qk)
where shp = (rp, (c
1i1, . . . , c
j ij , bpi)),
n,z,l
ap(a1z+dl)+(a1bp−apb1)(
n+φ(l))
, qp =
apld+(a1bp−apb1)φ(l)
a1bp−apb1
6= 0, Z = Y
and N = Md
From the conditions on the function φ it follows that qp ∈ Z, 2 ≤ p ≤ k.
From the conditions of the lemma we obtain for every p 6= q, p, q > 1,
ap cp
aq cq
a1 det
ap bp
aq bq
6= 0.
Therefore, D̃l can be rewritten as
D̃l =
φ2 (a2z + c2n) . . . φk (akz + ckn)
where φℓ = ψ
ℓ,j+1
rℓ+qℓ,(c
i1,...,c
ij ,bℓi)
, 2 ≤ ℓ ≤ k. By the induction hypothesis the
following is true.
There exists Il(ε, δ
′) ∈ N big enough, such that for every Il ≥ Il(ε, δ
′) there
exist a subset Sl ⊂ [−Il, Il]
j+1 of density at least 1 − δ′2 and N(Sl, ε) ∈ N,
such that for every N ≥ N(Sl, ε) there exists Z(N, Sl, ε) ∈ N, such that for
every Z ≥ Z(N, Sl, ε) we have
D̃l <
(2.8)
for all (i1, . . . , ij , i) ∈ Sl.
For every (i1, . . . , ij) ∈ [−Il, Il]
j we denote by Sli1,...,ij the fiber above (i1, . . . , ij):
Sli1,...,ij = {i ∈ [−Il, Il] | (i1, . . . , ij , i) ∈ Sl}.
Then there exists a set Tl ⊂ [−Il, Il]
j of density at least 1− δ′, such that for
every (i1, . . . , ij) ∈ Tl the density of S
i1,...,ij
is at least 1 − δ′. Let ε, δ > 0.
Take δ′ < min ( ε
, δ) and I > max (I ′(ε), Il(ε, δ
′)) (I ′(ε) is taken from the van
der Corput lemma).
Then it follows by (2.8) that there exists M(Tl, ε, δ) ∈ N, such that for
every M ≥ M(Tl, ε, δ) there exists X(M,Tl, ε, δ) ∈ N, such that for every
X ≥ X(M,Tl, ε, δ) the inequality (2.7) holds for every fixed (i1, . . . , ij) ∈ Tl
for a set of i’s within the interval {1, . . . , I} of density at least 1 − ε
. The
lemma follows from the van der Corput lemma.
Proof of Proposition 2.1.
Denote vm(n)
= ξ1(a1n+b1m) . . . ξk(akn+bkm). For every i ∈ N we introduce
Ã defined by
< vm, vm+i >N
0,(b1i)
(a1n+ b1m) . . . ψ
0,(bki)
(akn + bkm)
where the functions ψp,j’s are autocorrelation functions of the ξp’s of length
By Lemma 2.2 it follows that for every ε > 0 there exists I(ε) ∈ N such that
for every I ≥ I(ε) there exist S ⊂ {1, 2, . . . , I} of density at least 1− ε
M(S, ε) such that for every M ≥ M(S, ε) there exists N(M,S, ε) such that
for every N ≥ N(M,S, ε) we have
0,(b2i)
(a2n+ b2m) . . . ψ
0,(bki)
(akn+ bkm)
≤ ε2.
The proposition follows from the van der Corput Lemma 5.1.
3 Probabilistic constructions of WM sets
The goal of this section is to prove the necessity of the conditions of Theorem
1.3.1. The following proposition is the main tool for this task.
Proposition 3.1 Let a, b ∈ N, c ∈ Z such that a 6= b. Then there exists a
normal set A within which the equation
ax = by + c (3.1)
is unsolvable, i.e., for every (x, y) ∈ A2 we have ax 6= by + c.
Remark 3.1 The proposition is a particular case of Theorem 1.3.1. It is a
crucial ingredient in proving the necessity direction of the theorem in general.
Proof. Let S ⊂ N. We construct from S a new set AS within which the
equation ax = by + c is unsolvable.
Without loss of generality, suppose that a < b.
Assume (a, b) = 1 (the general case follows easily). It follows from (a, b) =
1 that (3.1) is solvable. Any solution (x, y) of the equation ax = by +
c has restrictions on x. Namely, x ≡ φ(a, b, c)(mod b), where φ(a, b, c) ∈
{0, 1, . . . , b − 1} is determined uniquely. Let us denote l0
= φ(a, b, c). We
define inductively a sequence {li} ⊂ N ∪ {0}. If a pair (x, y) is a solution of
equation (3.1) and y ∈ biN + li−1 then choose li ∈ {0, 1, . . . , b
i+1 − 1} such
that x ∈ bi+1N+ li.
Note that from (a, b) = 1 it follows that (a, bi+1) = 1. It is clear that
if u, v ∈ N satisfy (u, v) = 1 then for any w ∈ Z there exists a solution
(x, y) ∈ N2 of the equation ux = vy + w. The latter implies that there exist
x ∈ N, y ∈ biN+ li−1 such that ax = by+ c. Any such x should be a member
of bi+1N+ li. Note that li and li−1 are connected by the identity
ali ≡ bli−1 + c ( mod b
i+1). (3.2)
In addition, if x ∈ N is given then the equation
ax ≡ by + c ( mod bi+1)
has at most one solution y ∈ {0, 1, . . . , bi − 1}.
We define sets Hi
= biN+ li−1 ; i ∈ N. We prove that for every i ∈ N, Hi+1 ⊂
Hi. All elements of Hi+1 are in the same class modulo b
i+1, therefore all
elements of Hi+1 are in the same class modulo b
i. So, if we show for some
x ∈ Hi+1 that x ≡ li−1(mod b
i) then we are done. For i = 1 we know
that if y ∈ N then any x ∈ N such that (x, y) is a solution of the equation
(3.1) has to be in H1. Take x ∈ H2 such that there exists y ∈ H1 with
ax = by + c. Then x ∈ H1. Therefore, we have shown that H2 ⊂ H1. For
i > 1 there exists x ∈ Hi+1 such that there exists y ∈ Hi with ax = by + c.
By induction Hi ⊂ Hi−1. Therefore, the latter y is in Hi−1. Therefore, by
construction of li’s we have that x ∈ Hi. This shows Hi+1 ⊂ Hi. We define
sets Bi; 0 ≤ i <∞:
B0 = N \H1,
B1 = H1 \H2
. . .
Bi = Hi \Hi+1
. . .
Clearly we have Bi∩Bj = ∅ , ∀i 6= j and |N\ (∪
i=0Bi)| = | ∩
i=1Hi| ≤ 1. The
latter is because for every i the second element (in the increasing order) of
Hi is ≥ b
We define AS =
i=0Ai, where Ai’s are defined in the following manner:
= S ∩ B0, C0
= B0 \ A0
= B1 \ {x | ax ∈ bB0 + c}, A1
= (B1 ∩ {x | ax ∈ bC0 + c}) ∪ (D1 ∩ S) ,
= B1 \A1
. . .
= Bi \ {x | ax ∈ bBi−1 + c}, Ai = (Bi ∩ {x | ax ∈ bCi−1 + c}) ∪ (Di ∩ S) ,
= Bi \ Ai
. . .
Here it is worthwhile to remark that for every i, Bi = Ai ∪ Ci. Therefore
AS ⊂ ∪
i=0Bi.
If for some i ≥ 1 we have y ∈ Ai ⊂ Bi = Hi \ Hi+1, then any x with
ax = by + c satisfies
ax ≡ bli−1 + c ( mod b
i+1).
From (a, bi+1) = 1 it follows that there exists a unique solution x modulo
bi+1. By identity (3.2) we have
x ≡ li ( mod b
i+1).
Thus x ∈ Hi+1.
If x ∈ Hi+2, then
x ≡ li+1 ( mod b
i+2).
Thus we have
ali+1 ≡ by + c ( mod b
i+2).
By uniqueness of a solution ( y ) modulo bi+1 we get
y ≡ li ( mod b
i+1).
Thus y ∈ Hi+1. We have a contradiction, which shows that x ∈ Hi+1\Hi+2 =
Bi+1.
The same argument works for y ∈ A0 ⊂ B0 and it shows that any x with
ax = by + c satisfies x ∈ B1.
So, if y ∈ Ai (i ≥ 0) then any x with ax = by + c should satisfy x ∈ Bi+1.
By construction of AS, x 6∈ AS. Thus equation (3.1) is not solvable in AS.
We make the following claim:
For almost every subset S of N the set AS is a normal set.
(The probability measure on subsets of N considered here is the product on
{0, 1}∞ of probability measures (1
The tool for proving the claim is the following easy lemma (for a proof see
Appendix, Lemma 5.2).
A subset A of natural numbers is a normal set if and only if for any k ∈
(N ∪ {0}) and any i1 < i2 < . . . < ik we have
χA(n)χA(n + i1) . . . χA(n+ ik) = 0, (3.3)
where χA(n)
= 2 · 1A(n)− 1.
First of all, we denote TN =
n=1 χAS(n)χAS(n + i1) . . . χAS(n + ik). Be-
cause of randomness of S, TN is a random variable. We will prove that
N=1E(T
) <∞ and this will imply by Lemma 5.3 that TN →N→∞ 0 for
almost every S ⊂ N.
E(T 2N) =
n,m=1
E(χAS(n)χAS(n+i1) . . . χAS(n+ik)χAS(m) . . . χAS(m+ik)).
Adding (removing) of a finite set to (from) a normal set does not affect the
normality of the set. The set ∪iBi might differ from N by at most one element
(| ∩∞i=1 Hi| ≤ 1). This possible element does not affect the normality of AS
and we assume without loss of generality that ∩∞i=1Hi = ∅, thus N = ∪
i=0Bi.
For every number n ∈ N we define the chain of n, Ch(n), to be the following
finite sequence:
If n ∈ B0, then Ch(n) = (n).
If n ∈ B1, then two situations are possible. In the first one there exists a
unique y ∈ B0 such that an = by+c. We set Ch(n) = (n, y) = (n, Ch(y)). In
the second situation we can not find such y from B0 and we set Ch(n) = (n).
If n ∈ Bi+1, then again two situations are possible. In the first one there
exists y ∈ Bi such that an = by + c. In this case we set Ch(n) = (n, Ch(y)).
In the second situation there is no such y from Bi. In this case we set
Ch(n) = (n). We define l(n) to be the length of Ch(n).
For every n ∈ N we define the ancestor of n, a(n), to be the last element of
the chain of n (of Ch(n)). To determine whether or not n ∈ AS will depend
on whether a(n) ∈ S. The exact relationship depends on the i for which
n ∈ Bi and on the j for which a(n) ∈ Bj or in other words on the length of
Ch(n): χAS(n) = (−1)
i−jχS(a(n)) = (−1)
l(n)−1χS(a(n)).
We say that n is a descendant of a(n).
It is clear that E(χAS(n1) . . . χAS(nk)) 6= 0 (E(χAS(n1) . . . χAS(nk)) ∈ {0, 1})
if and only if every number a(ni) occurs an even number of times among
numbers a(n1), a(n2), . . . , a(nk).
We bound the number of n,m’s inside the square [1, N ] × [1, N ] such that
E(χAS(n)χAS(n+ i1) . . . χAS(n+ ik)χAS(m)χAS(m+ i1) . . . χAS(m+ ik)) 6= 0.
For a given n ∈ [1, N ] we count all m’s inside [1, N ] such that for the ancestor
of n there will be a chance to have a twin among the ancestors of n+i1, . . . , n+
ik, m,m+ i1, . . . , m+ ik.
First of all it is obvious that in the interval [1, N ] for a given ancestor there
can be at most log b
N + C1 descendants, where C1 is a constant. For all
but a constant number of n’s it is impossible that among n + i1, . . . , n + ik
there is the same ancestor as for n. Therefore we should focus on ancestors
of the set {m,m + i1, . . . , m + ik}. For a given n we might have at most
(k + 1)(log b
N + C1) options for the number m to provide that one of the
elements of {m,m + i1, . . . , m + ik} has the same ancestor as n. Therefore
for most of n ∈ [1, N ] (except maybe a bounded number C2 of n’s which
depends only on {i1, . . . , ik} and doesn’t depend on N) we have at most
(k + 1)(log b
N + C1) possibilities for m’s such that
E(χAS(n)χAS(n+ i1) . . . χAS(n+ ik)χAS(m)χAS(m+ i1) . . . χAS(m+ ik)) 6= 0.
Thus we have
E(T 2N) ≤
(k + 1)(log b
N + C1) + C2N
((k+1) log b
N +C3),
where C3 is a constant. This implies
E(T 2N2) <∞.
Therefore TN2 →N→∞ 0 for almost every S ⊂ N. By Lemma 5.3 it follows
that TN →N→∞ 0 almost surely.
In the general case, where a, b are not relatively prime, if c satisfies (3.1) then
it should be divisible by (a, b). Therefore by dividing the equation (3.1) by
(a, b) we reduce the problem to the previous case.
We use the following notation:
Let W be a subset ofQn. Then for any increasing subsequence I = (i1, . . . , ip) ⊂
{1, 2, . . . , n} we define
ProjIW = WI = {(wi1, . . . , wip) | ∃w = (w1, w2, . . . , wn) ∈ W}.
We recall the notion of a cone.
Definition 3.1 A subset W ⊂ Qn is called a cone if
(a) ∀w1, w2 ∈ W we have w1 + w2 ∈ W
(b) ∀α ∈ Q : α ≥ 0 and ∀w ∈ W we have αw ∈ W .
The next step involves an algebraic statement with a topological proof which
we have to establish.
Lemma 3.1 Let W be a non-trivial cone in Qn which has the property that
for every two vectors ~a = {a1, a2, . . . , an}
t,~b = {b1, b2, . . . , bn}
t ∈ W there
exist two coordinates 1 ≤ i < j ≤ n (depend on the choice of ~a,~b) such that
ai bi
aj bj
There exist two coordinates i < j such that the projection of W on these two
coordinates is of dimension ≤ 1 (dimQ SpanProj(i,j)W ≤ 1).
Proof. First of all W has positive volume in V = SpanW (Volume is Haar
measure which normalized by assigning measure one to a unit cube and W
contains a parallelepiped). Fix an arbitrary non-zero element ~x ∈ W . For
every i, j : 1 ≤ i < j ≤ n we define the subspace
Ui,j = {~v ∈ V |Proj(i,j)~v ∈ SpanProj(i,j)~x}.
From the assumptions of the lemma it follows that
i,j;1≤i<j≤n
(W ∩ Ui,j).
For every i 6= j we obviously have that the volume of Ui,j is either zero or
Ui,j = V . If we assume that the statement of the lemma does not hold then
Ui,j 6= V, ∀i 6= j, and thus the volume of Ui,j , ∀i 6= j is zero. We get a
contradiction because a finite union of sets with zero volume cannot be equal
to a set with positive volume.
Proof. (of Theorem 1.3.1, ⇛)
Assume that an affine subspace A of Qk intersects Ak for any WM set A ⊂ N.
First of all, we shift the affine space to obtain a vector subspace, denote it
by U . The linear space U must contain vectors with all positive coordinates,
since A ∩Ak must be infinite.
Denote by W = {~v ∈ U | 〈~v, ~ei〉 ≥ 0 , ∀ i : 1 ≤ i ≤ k}. W is a non-trivial
cone.
Assume that for every ~a = (a1, . . . , ak)
t,~b = (b1, . . . , bk)
t ∈ W we have that
∃i, j : 1 ≤ i < j ≤ k such that
ai bi
aj bj
Then by Lemma 3.1 we deduce that there exist maximal subsets of coordi-
nates F1, . . . , Fl (one of them, assume F1, should have at least two coordi-
nates) such that for every r ∈ {1, 2 . . . , l} we have VFr
= SpanWFr is one
dimensional.
We fix r : 1 ≤ r ≤ l. We show that the projection on Fr of W + ~f is on a
diagonal, where ~f ∈ Zk is such that U + ~f = A. If the projection of W on
Fr is not on a diagonal then there exist two coordinates i < j from Fr such
that W(i,j) = {(ax, bx) | x ∈ N} for some a 6= b natural numbers. Therefore
the projection of A on (i, j) has the form {(ax+ f1, bx+ f2) | x ∈ N}, where
f1, f2 are integers. From Proposition 3.1 it follows that for any a, b, c, where
a 6= b, there exists a WM set A (even a normal set) such that the equation
ax = by + c is not solvable within A. This proves the existence of a WM set
A0 such that for every x ∈ Z we have (ax+ f1, bx+ f2) 6∈ A
0 (introduce the
new variables z1, z2 by (z1, z2) = (ax1+ f1, bx+ f2) and take a normal set A0
such that the equation az2 = bz1 + (af2 − bf1) is unsolvable within A0).
Thus ∀i, j ∈ Fr : W(i,j) = {(ax, ax) | x ∈ N}.
To prove that a shift is the same for all coordinates in Fr we merely should
know that for any natural number c there exists a WM set Ac such that
inside Ac the equation x− y = c is not solvable. The last statement is easy
to verify.
Let jr ∈ Fr, ∀1 ≤ r ≤ l. Denote I = (j1, . . . , jl). We have proved that there
exist g1, . . . , gl ∈ N, c1, . . . , cl ∈ Z such that
(U + ~f)I = {(g1x1 + c1, . . . , glxl + cl) | x1, . . . , xl ∈ Q}.
It is clear that we can find ~a,~b which satisfy all the requirements of Theorem
1.3.1. This completes the proof.
Remark 3.2 We have proved that if an affine subspace A ⊂ Qk intersects
Ak for any normal set A ⊂ N, then there exist ~a,~b ∈ Nk and a partition
F1, . . . , Fl of {1, 2, . . . , k} such that:
(a) ∀r : 1 ≤ r ≤ l and ∀i ∈ Fr, ∀j 6∈ Fr we have
ai bi
aj bj
6= 0.
(b) ∃~f ∈ Zk such that the set {n~a +m~b+ ~f |n,m ∈ N} is in A.
Thus, we have proved the direction “⇛” of Theorem 1.3.2.
4 Comparison with Rado’s Theorem
We recall that the problem of solvability of a system of linear equations in
one cell of any finite partition of N was solved by Rado in [10]. Such systems
of linear equations are called partition-regular. We show that partition-
regular systems are solvable within every WM set by use of Theorem 1.3.1.
It is important to note that solvability of partition-regular linear systems of
equations within WM sets can be shown directly (without use of Theorem
1.3.1) by use of the technique of Furstenberg and Weiss that was developed
in their dynamical proof of Rado’s theorem (see [8]).
First of all we describe Rado’s regular systems.
Definition 4.1 A rational p × q matrix (aij) is said to be of level l if the
index set {1, 2, . . . , q} can be divided into l disjoint subsets I1, I2, . . . , Il and
rational numbers crj may be found for 1 ≤ r ≤ l and 1 ≤ j ≤ q such that the
following relationships are satisfied:
aij = 0
aij =
c1jaij
. . .
aij =
j∈I1∪I2∪...∪Il−1
cl−1j aij
for i = 1, 2, . . . , p.
Theorem 4.1 (Rado) A system of linear equations is partition-regular if and
only if for some l the matrix (aij) is of level l and it is homogeneous, i.e. a
system of the form
aijxj = 0, i = 1, 2, . . . , p.
The following claim is the main result of this section.
Proposition 4.1 A partition-regular system is solvable in every WM set.
Proof. Let a system
j=1 aijxj = 0, i = 1, 2, . . . , p be partition-regular.
We will use the fact that the system is solvable for any finite partition of N.
First of all, the set of solutions of a partition-regular system is a subspace of
Qq; denote it by V . It is obvious that V contains vectors with all positive
components. If for some 1 ≤ i < j ≤ q we have Proj+i,jV (where Proj
i,jV =
{(x, y)|x, y ≥ 0 & ∃~v ∈ V :< ~v, ~ei >= x , < ~v, ~ej >= y}) is contained
in a line, then Proj+i,jV is diagonal, i.e. it is contained in {(x, x)|x ∈ Q}.
Otherwise, we can generate a partition of N into two disjoint sets S1, S2 such
that no S
1 and no S
2 intersects V :
This partition is constructed by an iterative process. Without loss of gener-
ality we may assume that the line is x = ny, where n ∈ N. The general case
is treated in the simillar way. We start with S1 = S2 = ∅. Let 1 ∈ S1.
We “color” the infinite geometric progression {nm |m ∈ N} (adding elements
to either S1 or S2) in such way that there is no (x, y) on the line from S
1 , S
Then we take a minimal element from N which is still uncolored. Call it a.
Add a to S1. Next, “color” {an
m |m ∈ N}.
Continuing in this fashion, we obtain the desired partition of N.
This contradicts the assumption that the given system is partition-regular.
Let F1, . . . , Fl be a partition of {1, 2, . . . , k} such that for every r ∈ {1, . . . , l}
we have for every i 6= j , i, j ∈ Fr : dim QSpan(Proj
i,jV ) = 1, and for every
r : 1 ≤ r ≤ l, every i ∈ Fr .and for every j 6∈ Fr we have dim QSpan(Proj
i,jV ) =
2. For every r : 1 ≤ r ≤ l we choose arbitrarily one representative index
within Fr and denote it by jr (jr ∈ Fr).
Then there exist g1, . . . , gl ∈ N such that
VI = {(g1x1, . . . , glxl) | x1, . . . , xl ∈ Q}.
The latter ensures that there exist vectors ~a,~b ∈ V which satisfy all the
requirements of Theorem 1.3.1 and, therefore, the system is solvable in every
WM set.
5 Appendix
In this section we prove all technical lemmas and propositions that were used
in the paper.
We start with the key lemma which is a finite modification of Bergelson’s
lemma in [1]. Its origin is in a lemma of van der Corput.
Lemma 5.1 Suppose ε > 0 and {uj}
j=1 is a family of vectors in Hilbert
space, such that ‖uj‖ ≤ 1 (1 ≤ j ≤ ∞). Then there exists I
′(ε) ∈ N, such
that for every I ≥ I ′(ε) there exists J ′(I, ε) ∈ N, such that the following
holds:
For J ≥ J ′(I, ε) for which we obtain
〈uj, uj+i〉
for a set of i’s in the interval {1, . . . , I} of density 1− ε
we have
Proof. For an arbitrary J define uk = 0 for every k < 1 or k > J . The
following is an elementary identity:
uj−i = I
Therefore, the inequality
i=1 ui
i=1 ‖ui‖
yields
≤ (J + I)
= (J + I)
uj−p,
uj−s〉
= (J+I)
‖uj−p‖
+2(J+I)
r,s=1;s<r
〈uj−r, uj−s〉 = (J+I)(Σ1+2Σ2),
where Σ1 = I
by the aforementioned elementary identity and
h=1(I−h)
j=1〈uj, uj+h〉. The last expression is obtained by rewrit-
ing Σ2, where h = r − s. By dividing the foregoing inequality by I
2J2 we
obtain
J + I
J + I
J + I
Choose I ′(ε) ∈ N, such that 12
≤ I ′(ε) ≤ 12
+1. Then for every I ≥ I ′(ε) we
have 1
≤ 11ε
. There exists J ′(I, ε) ∈ N, such that for every J ≥ J ′(I, ε):
. As a result, for every I ≥ I ′(ε) there exists J ′(I, ε), such that for
every J ≥ J ′(I, ε)
The next proposition was used in Section 2.
Proposition 5.1 Let A ⊂ N be a WM-set. Then for every integer a > 0
and every integers b1, b2, . . . , bk
ξ(n+ b1)ξ(n+ b2) . . . ξ(n+ bk) =
ξ(an+ b1)ξ(an+ b2) . . . ξ(an+ bk),
where ξ
= 1A − d(A).
Proof. Consider the weak-mixing measure preserving system (Xξ,B, µ, T ).
The left side of the equation in the proposition is
T b1fT b2f . . . T bkfdµ,
where f(ω)
= ω0 for every infinite sequence inside Xξ. We make use of the
notion of disjointness of measure preserving systems. By [6] we know that
every weak-mixing system is disjoint from any Kronecker system which is
a compact monothethic group with Borel σ-algebra, the Haar probability
measure, and the shift by a chosen element of the group. In particular,
every weak-mixing system is disjoint from the measure preserving system
(Za,BZa , S, ν), where Za = Z/aZ, S(n)
= n+ 1( mod a). The measure and
the σ-algebra of the last system are uniquely determined. Therefore, from
Furstenberg’s theorem (see [6], Theorem I.6) it follows that the point (ξ, 0) ∈
Xξ×Za is a generic point of the product system (Xξ×Za,B×BZa , T×S, µ×ν).
Thus, for every continuous function g on Xξ × Za we obtain
Xξ×Za
g(x,m)dµ(x)dν(m) = lim
g(T nξ, Sn0).
Let g(x,m)
= f(x)10(m), which is obviously continuous on Xξ × Za. Then
genericity of the point (ξ, 0) yields
Xξ×Za
f(x)10(m)dµ(x)dν(m) =
f(x)dµ(x) =
f(T nξ)10(n) = lim
f(T anξ).
Taking instead of the function f the continuous function T b1fT b2f . . . T bkf
in the definition of g finishes the proof.
The next two lemmas are very useful for constructing normal sets with specif-
ical properties.
Lemma 5.2 Let A ⊂ N. Let λ(n) = 21A(n)− 1. Then A is a normal set ⇔
for any k ∈ (N ∪ {0}) and any i1 < i2 < . . . < ik we have
λ(n)λ(n+ i1) . . . λ(n+ ik) = 0.
Proof. “⇒” If A is normal then any finite word w ∈ {−1, 1}∗ has the
“right” frequency 1
inside wA. This guarantees that “half of the time” the
function λ(n)λ(n + i1) . . . λ(n + ik) equals 1 and “half of the time” is equal
to −1. Therefore we get the desired conclusion.
“⇐” Let w be an arbitrary finite word of plus and minus ones: w = a1a2 . . . ak
and we have to prove that w occurs in wA with the frequency 2
−k. For every
n ∈ N the word w occurs in 1A and starting from n if and only if
1A(n) = a1
. . .
1A(n+ k − 1) = ak
The latter is equivalent to the following
λ(n) = 2a1 − 1
. . .
λ(n+ k − 1) = 2ak − 1
The frequency of w within 1A is equal to
λ(n)(2a1 − 1) + 1
. . .
λ(n+ k − 1)(2ak − 1) + 1
The limit is equal to 1
Lemma 5.3 Let {an} be a bounded sequence. Let TN =
n=1 an. Then
TN converges to a limit t ⇔ there exists a sequence of increasing indices {Ni}
such that Ni
→ 1 and TNi →i→∞ t.
References
[1] Bergelson, V. Weakly mixing PET. Ergodic Theory Dynam. Sys-
tems 7 (1987), no. 3, 337–349.
[2] Bergelson, V.; McCutcheon, R. An ergodic IP polynomial Sze-
merédi theorem. Mem. Amer. Math. Soc. 146 (2000), no. 695.
[3] Fish, A. Random Liouville functions and normal sets. Acta Arith.
120 (2005), no. 2, 191–196.
[4] Fish, A. Polynomial largeness of sumsets and totally ergodic sets,
see http://arxiv.org/abs/0711.3201.
[5] Fish, A. Ph.D. thesis, Hebrew University, 2006.
[6] Furstenberg, H. Disjointness in ergodic theory, minimal sets, and
a problem in Diophantine approximation. Math. Systems Theory
1 (1967), 1-49.
[7] Furstenberg, H. Ergodic behavior of diagonal measures and a
theorem of Szemerédi on arithmetic progressions. J. d’ Analys
Math. 31 (1977), 204–256.
[8] Furstenberg, H. Recurrence in Ergodic Theory and Combinatorial
Number Theory. Princeton Univ. Press 1981.
[9] Host, B.; Kra, B. Nonconventional ergodic averages and nilman-
ifolds. Ann. of Math. (2) 161 (2005), no. 1, 397–488.
[10] Rado, R. Note on combinatorial analysis. Proc. London Math.
Soc. 48 (1943), 122–160.
[11] Schur, I. Uber die Kongruenz xm+ym ≡ zm(modp). Jahresbericht
der Deutschen Math.-Ver. 25 (1916), 114–117.
[12] Szemerédi, E. On sets of integers containing no k elements in
arithmetic progression. Collection of articles in memory of Jurǐi
Vladimirovič Linnik. Acta Arith. 27 (1975), 199–245.
Current Address:
Department of Mathematics
University of Wisconsin-Madison
480 Lincoln Dr.
Madison, WI 53706-1388
E-mail: afish@math.wisc.edu
http://arxiv.org/abs/0711.3201
	Introduction
	Algebraic patterns within subsets of N
	Generic points and WM sets
	Solvability of linear diophantine systems within WM sets and normal sets
	Acknowledgments
	Proof of Sufficiency
	Probabilistic constructions of WM sets
	 Comparison with Rado's Theorem
	Appendix

  We introduce a new class of "random" subsets of natural numbers, WM sets.
This class contains normal sets (sets whose characteristic function is a normal
binary sequence). We establish necessary and sufficient conditions for
solvability of systems of linear equations within every WM set and within every
normal set. We also show that partition-regular system of linear equations with
integer coefficients is solvable in any WM set.

Introduction
1.1 Algebraic patterns within subsets of N
We use extensively the notion of “algebraic pattern”. By an algebraic pattern
we mean a solution of a diophantine system of equations. For example, an
arithmetic progression of length k is an algebraic pattern corresponding to
the following diophantine system:
2xi = xi−1 + xi+1, i = 2, 3, . . . , k − 1.
We investigate the problem of finding linear algebraic patterns (these cor-
respond to linear systems) within a family of subsets of natural numbers
satisfying some asymptotic conditions.
For instance, by Szemerédi theorem, subsets of positive upper Banach density
(all S ⊂ N : d∗(S) > 0, where d∗(S) = lim supbn−an→∞
|S∩[an,bn]|
bn−an+1
) contain the
pattern of an arithmetic progression of any finite length (see [12]).
http://arxiv.org/abs/0704.0600v2
On the other hand, Schur patterns, namely triples of the form {x, y, x+ y},
which correspond to solutions of the so-called Schur equation, x+ y = z, do
not necessarily occur in sets of positive upper density. For example, the odd
numbers do not contain this pattern. But if we take a random subset of N
by picking natural numbers with probability 1
independently, then this set
contains the Schur pattern with probability 1.
There is a deterministically defined analog of a random set - a normal set. To
define a normal set we recall the notions of a normal infinite binary sequence
and of a normal number.
An infinite {0, 1}-valued sequence λ is called a normal sequence if every
finite binary word w occurs in λ with frequency 1
, where |w| is the length
of w.
The more familiar notion is that of a normal number x ∈ [0, 1]. If to a number
x ∈ [0, 1] we associate its dyadic expansion x =
with xi ∈ {0, 1},
then x is called a normal number if the sequence (x1, x2, . . . , xn, . . .) is a
normal sequence.
Definition 1.1.1 A set S ⊂ N is called normal if the 0-1 sequence 1S
(1S(n) = 1 ⇔ n ∈ S) is normal.
Normal sets exhibit a non-periodic, “random” behavior. We notice that if S
is a normal set then S − S contains N. Therefore, the equation
z − y = x
is solvable within every normal set. This implies that every normal set con-
tains Schur patterns.
Normal sets are related to a class of dynamical systems displaying maximal
randomness; namely Bernoulli systems. In this work we investigate occur-
rence of linear patterns in sets corresponding to dynamical systems with a
lower degree of randomness, so called weakly mixing dynamical systems. The
sets we obtain will be called WM sets. We will make this precise in the next
section.
In the present paper we treat the following problem:
Give a complete characterization of the linear algebraic patterns which occur
in all WM sets.
Remark 1.1.1 It will follow from our definition of a WM set, that any
normal set is a WM set.
The problem of the solvability of a nonlinear equation or system of equa-
tions is beyond the limits of the technique used in this paper. Nevertheless,
some particular equations might be analyzed. In [3] it is shown that there
exist normal sets in which the multiplicative Schur equation xy = z is not
solvable.
1.2 Generic points and WM sets
For a formal definition of WM sets we need the notions of measure preserving
systems and of generic points.
Definition 1.2.1 Let X be a compact metric space, B the Borel σ-algebra
on X; let T : X → X be a continuous map and µ a probability measure on
B. The quadruple (X,B, µ, T ) is called a measure preserving system if
for every B ∈ B we have µ(T−1B) = µ(B).
For a compact metric space X we denote by C(X) the space of continuous
functions on X with the uniform norm.
Definition 1.2.2 Let (X,B, µ, T ) be a measure preserving system. A point
ξ ∈ X is called generic for the system (X,B, µ, T ) if for any f ∈ C(X) we
f(T nξ) =
f(x)dµ(x). (1.1)
Example: Consider the Bernoulli system: (X = {0, 1}N0,B, µ, T ), where X
is endowed with the Tychonoff topology, B is Borel σ-algebra on X , T is the
shift to the left, µ is the product measure of µi’s where µi(0) = µi(1) =
and N0 = N ∪ {0}. An alternative definition of a normal set which is purely
dynamical is the following.
A set S is normal if and only if the sequence 1S ∈ {0, 1}
N0 is a generic
point of the foregoing Bernoulli
system.
The notion of a WM set generalizes that of a normal set, where the role
played by Bernoulli dynamical system is taken over by dynamical systems of
more general character.
Let ξ(n) be any {0, 1}−valued sequence. There is a natural dynamical system
(Xξ, T ) connected to the sequence ξ:
On the compact space Ω = {0, 1}N0 endowed with the Tychonoff topology,
we define a continuous map T : Ω −→ Ω by (Tω)n = ωn+1. Now for any ξ in
Ω we define
Xξ = {T nξ}n∈N0 ⊂ Ω.
Let A be a subset of N. Choose ξ = 1A and assume that for an appropriate
measure µ, the point ξ is generic for (Xξ,B, µ, T ). We can attach to the set
A dynamical properties associated with the system (Xξ,B, µ, T ).
We recall the notions of ergodicity, total ergodicity and weak-mixing in er-
godic theory:
Definition 1.2.3 A measure preserving system (X,B, µ, T ) is called er-
godic if every A ∈ B which is invariant under T , i.e. T−1(A) = A, satisfies
µ(A) = 0 or 1.
A measure preserving system (X,B, µ, T ) is called totally ergodic if for ev-
ery n ∈ N the system (X,B, µ, T n) is ergodic.
A measure preserving system (X,B, µ, T ) is called weakly mixing if the
system (X ×X,BX×X , µ× µ, T × T ) is ergodic.
In our discussion of WM sets corresponding to weakly mixing systems, we
shall add the proviso that the dynamical system in question not be the trivial
1-point system supported on the point x ≡ 0. This implies that the “density”
of the set in question be positive.
Definition 1.2.4 Let S ⊂ N. If the limit of 1
n=1 1S(n) exists as N → ∞
we call it the density of S and denote by d(S).
Definition 1.2.5 A subset S ⊂ N is called a WM set if 1S is a generic
point of the weakly mixing system (X1S ,B, µ, T ) and d(S) > 0.
1.3 Solvability of linear diophantine systems within
WM sets and normal sets
Our main result is a complete characterization of linear systems of diophan-
tine equations which are solvable within every WM set. The characterization
is given by describing affine subspaces of Qk which intersect Ak, for any WM
set A ⊂ N.
Theorem 1.3.1 An affine subspace of Qk intersects Ak for every WM set
A ⊂ N if and only if it contains a set of the form
{n~a+m~b+ ~f |n,m ∈ N},
where ~a,~b, ~f have the following description:
~a = (a1, a2, . . . , ak)
t, ~b = (b1, b2, . . . , bk)
t ∈ Nk, ~f = (f1, f2, . . . , fk)
t ∈ Zk and
there exists a partition F1, . . . , Fl of {1, 2, . . . , k} such that:
a) for every r ∈ {1, . . . , l} there exist c1,r, c2,r ∈ N, such that for every i ∈ Fr
we have ai = c1,r , bi = c2,r and for every j ∈ {1, . . . , k} \ Fr we have
aj bj
c1,r c2,r
6= 0.
∀r ∈ {1, 2, . . . , l} ∃cr ∈ Z such that ∀i ∈ Fr : fi = cr.
We also classify all affine subspaces of Qk which intersect Ak for any normal
set A ⊂ N.
Theorem 1.3.2 An affine subspace of Qk intersects Ak for every normal set
A ⊂ N if and only if it contains a set of the form
{n~a+m~b+ ~f |n,m ∈ N},
where ~a,~b, ~f have the following description:
~a = (a1, a2, . . . , ak)
t, ~b = (b1, b2, . . . , bk)
t ∈ Nk, ~f = (f1, f2, . . . , fk)
t ∈ Zk
and there exists a partition F1, . . . , Fl of {1, 2, . . . , k} such that for every
r ∈ {1, . . . , l} there exist c1,r, c2,r ∈ N, such that for every i ∈ Fr we have
ai = c1,r , bi = c2,r and for every j ∈ {1, . . . , k} \ Fr we have
aj bj
c1,r c2,r
6= 0.
A family of linear algebraic patterns that has been studied previously are the
“partition regular” patterns. These are patterns which for any finite partition
of N: N = C1∪C2 ∪ . . .∪Cr, the pattern necessarily occurs in some Cj. (For
example by van der Waerden’s theorem, arithmetic progressions are partition
regular and by Schur’s theorem the Schur pattern is also partition regular).
A theorem of Rado gives a complete characterization of such patterns. We
will show in Proposition 4.1 that every linear algebraic pattern which is
partition-regular occurs in every WM set.
It is important to mention that if we weaken the requirement of weak mixing
to total ergodicity, then in the resulting family of sets, Rado’s patterns need
not necessarily occur. For example, for α 6∈ Q the set
n ∈ N|nα (mod 1) ∈
is totally ergodic, i.e., 1S is a generic point for a totally ergodic system and
the density of S is positive, but the equation x+ y = z is not solvable within
In the separate paper [4] we will address the question of solvability of more
general algebraic patterns, not necessarily linear, in totally ergodic and WM
sets.
The structure of the paper is the following. In Section 2 we prove the direction
“⇐” of Theorems 1.3.1 and 1.3.2. In Section 3, by use of a probabilistic
method, we prove the direction “⇒” of Theorems 1.3.1 and 1.3.2. In Section
4 we show that every linear system which is solvable in one of the cells of any
finite partition of N is also solvable within every WM set. The paper ends
with Appendix in which we collected proofs of technical statements which
have been used in Sections 2 and 3.
1.4 Acknowledgments
This paper is a part of the author’s Ph.D. thesis. I thank my advisor Prof.
Hillel Furstenberg for introducing me to ergodic theory and for many useful
ideas which I learned from him. I thank Prof. Vitaly Bergelson for fruitful
discussions and valuable suggestions. Also, I would like to thank an anony-
mous referee for numerous valuable remarks.
2 Proof of Sufficiency
Notation: We introduce the scalar product of two vectors v, w of length N
as follows:
< v,w >N
v(n)w(n).
We denote by L2(N) the (finite-dimensional) Hilbert space of all real vectors
of length N with the aforementioned scalar product.
We define: ‖ w ‖2N
=< w,w >N .
First we state the following proposition which will prove useful in the proof
of the sufficiency of the conditions of Theorem 1.3.1.
Proposition 2.1 Let Ai ⊂ N (1 ≤ i ≤ k) be WM sets. Let
ξi(n)
= 1Ai(n)−d(Ai), where d(Ai) denotes density of Ai. Suppose there are
(a1, b1), (a2, b2), . . . , (ak, bk) ∈ Z
2, such that ai > 0, 1 ≤ i ≤ k, and for every
i 6= j
ai bi
aj bj
6= 0.
Then for every ε > 0 there exists M(ε) ∈ N, such that for every M ≥ M(ε)
there exists N(M, ε) ∈ N, such that for every N ≥ N(M, ε)
where w(n)
m=1 ξ1(a1n+b1m)ξ2(a2n+b2m) . . . ξk(akn+bkm) for every
n = 1, 2, . . . , N .
Since the proof of Proposition 2.1 involves many technical details, first we
show how our main result follows from it. Afterwards we state and prove all
the lemmas necessary for the proof of Proposition 2.1.
We use an easy consequence of Proposition 2.1.
Corollary 2.1 Let A be a WM set. Let k ∈ N, suppose
(a1, b1), (a2, b2), . . . , (ak, bk) ∈ Z
2 satisfy all requirements of Proposition 2.1
and suppose f1, . . . , fk ∈ Z. Then for every δ > 0 there exists M(δ) such
that ∀M ≥ M(δ) there exists N(M, δ) such that ∀N ≥ N(M, δ) we have
∣‖v‖N − d
∣ < δ,
where v(n)
m=1 1A(a1n + b1m + f1)1A(a2n + b2m + f2) . . . 1A(akn +
bkm+ fk) for every n = 1, 2, . . . , N .
Proof. We rewrite v(n) in the following form:
v(n) =
(ξ1(a1n+ b1m) + d(A)) . . . (ξk(akn + bkm) + d(A)),
for every n = 1, 2, . . . , N . We introduce normalized WM sequences ξi(n) =
ξ(n+ fi) (of zero average), where ξ(n) = 1A(n)− d(A). By use of triangular
inequality and Proposition 2.1 it follows that for big enoughM and N (which
depends on M) ‖v‖N is as close as we wish to d
k(A). This finishes the proof.
Proof. (of Theorem 1.3.1, ⇚) Let A ⊂ N be a WM set. Without loss of
generality, we can assume that for every r : 1 ≤ r ≤ l we have r ∈ Fr.
It follows from Corollary 2.1 that the vector v defined by
1A(a1n+ b1m+ f1)1A(a2n + b2m+ f2) . . . 1A(aln + blm+ fl)
for every n = 1, 2, . . . , N , is not identically zero for big enough M and N .
But this is possible only if for some n,m ∈ N we have
(a1n+ b1m+ f1, a2n+ b2m+ f2, . . . , aln+ blm+ fl) ∈ A
The latter implies that Ak intersects the affine subspace.
Proof. (of Theorem 1.3.2, ⇚) For every r : 1 ≤ r ≤ l take all indices which
comprise Fr. Denote this sequence of indices by Ir. Denote cr = mini∈Ir fi.
Let Sr be the set of all non-zero shifts of fi, i ∈ Fr, centered at cr, i.e.,
Sr = {fi − cr | i ∈ Fr, fi > cr}.
For example, if the sequence of fi’s where i ∈ F1 is (−5, 2, 3, 2,−5), then
S1 = {7, 8}.
Let A be a normal set. For every r : 1 ≤ r ≤ l we define sets Ar by
Ar = {n ∈ N ∪ {0} |n ∈ A and n+ s ∈ A, ∀s ∈ Sr}.
Then Ar is no longer a normal set provided that Sr 6= ∅ (d(A) =
21+|Sr |
But, for all r : 1 ≤ r ≤ l the sets Ar’s are WM sets.
Without loss of generality, assume that for every r : 1 ≤ r ≤ l we have
r ∈ Fr.
From Proposition 2.1 it follows that for big enough M and N
1A1(a1n+ b1m)1A(a2n+ b2m) . . . 1A(aln+ blm) ≈
d(Ar).
The latter ensures that there exist m,n ∈ N such that
(a1n+ b1m+ f1, . . . , akn+ bkm+ fk) ∈ A
Now we state and prove all the claims that are required in order to prove
Proposition 2.1.
Definition 2.1 Let ξ be a WM-sequence (ξ is a generic point for a weakly
mixing system (Xξ,BXξ , µ, T )) of zero average. The autocorrelation function
of ξ of length j ∈ N with the shifts ~i = (i1, i2, . . . , ij) ∈ Z
j and r ∈ Z is the
sequence ψ
which is defined by
(n) =
w∈{0,1}j
ξ(n+ r + w ·~i), n ∈ N,
where w ·~i is the usual scalar product in Qj, and
(n) = 0, n ≤ 0.
Lemma 2.1 Let ξ be a WM-sequence of zero average and suppose ε, δ >
0, b ∈ Z \ {0}. Then for every j ≥ 1, (c1, c2, . . . , cj) ∈ (Z \ {0})
j and
(r1, r2, . . . , rj) ∈ Z
j there exist I = I(ε, δ, c1, . . . , cn), a set S ⊂ [−I, I]
density at least 1−δ and N(S, ε) ∈ N, such that for every N ≥ N(S, ε) there
exists L(N, S, ε) such that for every L ≥ L(N, S, ε)
r,(c1i1,...,cjij)
(l + bn)
for every (i1, i2, . . . , ij) ∈ S, where r =
k=1 rk.
Proof. We note that it is sufficient to prove the lemma in the case c1 =
c2 = . . . = cj = 1, since if the average of nonnegative numbers over a whole
lattice is small, then the average over a sublattice of a fixed positive density
is also small.
Recall that ξ ∈ Xξ
= {T nξ}∞n=0 ⊂ supp(ξ)
N0, where T is the usual shift to
the left on the dynamical system supp(ξ)N0, and by the assumption that ξ
is a WM-sequence of zero average it follows that ξ is a generic point of the
weakly mixing system (Xξ,BXξ , µ, T ) and the function f : f(ω)
= ω0 has
zero integral.
Denote ~i = (i1, . . . , ij).
We define functions g
on Xξ by
T r+ǫ·
~i ◦ f,
ǫ∈V ∗
T r+ǫ·
~i ◦ f,
where Vj is the j-dimensional discrete cube {0, 1}
j and V ∗j is the j-dimensional
discrete cube except the zero point.
Notice that
(T nξ) = ψ
We use the following theorem which is a special case of a multiparameter
weakly mixing PET of Bergelson and McCutcheon (theorem A.1 in [2]; it is
also a corollary of Theorem 13.1 of Host and Kra in [9]).
Let (X, µ, T ) be a weakly mixing system. Given an integer k and 2k bounded
functions fǫ on X, ǫ ∈ Vk , the functions
Ni −Mi
n∈[M1,N1)×...[Mk,Nk)
ǫ∈V ∗
T ǫ1n1+...ǫknk ◦ fǫ
converge in L2(µ) to the constant limit
ǫ∈V ∗
when N1 −M1, . . . , Nk −Mk tend to +∞.
From this theorem applied to the weakly mixing system Xξ × Xξ and the
functions fǫ(x) = T
r ◦ f ⊗ T r ◦ f for every ǫ ∈ Vj , we obtain for every Folner
sequence {Fn} in N
j that an average over the multi-index ~i = {i1, . . . , ij} of
on Fn’s converges to zero in L
2(µ) (the integral of T r ◦ f ⊗ T r ◦ f
is zero). Thus
Xξ×Xξ
Ni −Mi
~i∈[M1,N1)×...×[Mj,Nj)
(y)dµ(x)dµ(y) =
Ni −Mi
~i∈[M1,N1)×...×[Mj,Nj)
(x)dµ(x)
as N1 −M1, . . . , Nj −Mj → ∞.
As a result we obtain the following statement:
For every ε > 0, j ∈ N and every fixed (r1, r2, . . . , rj) ∈ N
j, there exists a
subset R ⊂ Nj of lower density equal to one, such that
< ε (2.1)
for every ~i ∈ R, where r =
k=1 rj.
Recall that lower density of a subset R ⊂ Nj is defined to be
d∗(R) = lim inf
N1−M1,...,Nj−Mj→∞
#{R ∩ [M1, N1)× . . .× [Mj , Nj)}
k=1(Nk −Mk)
Recall that ψ
(l + bn) = g
T l+bnξ
The definition of the sequences ψj implies
r1,~i
(l + bn)
= lim
r2,(±i1,...,±ij)
(l ± bn)
for any r1, r2 ∈ Z, where ~i = (i1, . . . , ij).
Therefore, in order to prove Lemma 2.1 it is sufficient to show the following:
For every ε, δ > 0 and for any a priori chosen b ∈ N there exists I(ε, δ) ∈ N,
such that for every I ≥ I(ε, δ) there exists a subset S ⊂ [1, I]j of density
at least 1 − δ (namely, we have
|S∩[1,I)j |
≥ 1 − δ) and N(S, ε) ∈ N, such
that for every N ≥ N(S, ε) there exists L(N, S, ε) ∈ N such that for every
L ≥ L(N, S, ε) the following holds for every ~i ∈ S:
(l + bn)
Let b ∈ N. Continuity of the function
g0,~i and genericity of the point ξ ∈ Xξ yield
(l + bn)
= lim
T bng0,~i
T bng0,~i
dµ. (2.2)
By applying the von Neumann ergodic theorem to the ergodic system
(Xξ,B, µ, T
b) (ergodicity follows from weak-mixing of the original measure
preserving system (Xξ,B, µ, T )) we have
T bng0,~i →
L2(Xξ)
g0,~idµ. (2.3)
From (2.1) there exists I(ε, δ) ∈ N big enough that for every I ≥ I(ε, δ) there
exists a set S ⊂ [1, I]j of density at least 1− δ such that
g0,~idµ
for all ~i ∈ S.
From equation (2.3) it follows that there exists N(S, ε) ∈ N, such that for
every N ≥ N(S, ε) we have
T bng0,~i
for all ~i ∈ S.
Finally, equation (2.2) implies that there exists L(N, S, ε) ∈ N, such that for
every L ≥ L(N, S, ε) we have
(l + bn)
for all ~i ∈ S.
The following lemma is a generalization of the previous lemma to a product
of several autocorrelation functions.
Lemma 2.2 Let ψ
r1,~i
, . . . , ψ
rk,~i
be autocorrelation functions of length j of
WM-sequences ξ1, . . . , ξk of zero average,
{c11, . . . , c
j , . . . , c
1, . . . , c
j} ∈ (Z \ {0})
jk and ε, δ > 0. Suppose
(a1, b1), (a2, b2), . . . , (ak, bk) ∈ Z
2, such that ai > 0 for all i : 1 ≤ i ≤ k and
for every i 6= j
ai bi
aj bj
6= 0.
(If k = 1 assume that b1 6= 0.)
Then there exists I(ε, δ) ∈ N, such that for every I ≥ I(ε, δ) there exist
S ⊂ [−I, I]j of density at least 1− δ, M(S, ε) ∈ N, such that for every M ≥
M(S, ε) there exists X(M,S, ε) ∈ N, such that for every X ≥ X(M,S, ε)
r1,(c
i1,...,c
(a1x+ b1m) . . . ψ
rk,(c
i1,...,c
(akx+ bkm)
for every (i1, i2, . . . , ij) ∈ S.
Proof. The proof is by induction on k.
THE CASE k = 1 (and arbitrary j):
If a1 = 1 then the statement of the lemma follows from Lemma 2.1. If a1 > 1
then by Proposition 5.1 of Appendix for a given ~i = (i1, . . . , ij) ∈ S we have
r1,(c
i1,...,c
(a1x+ b1m)
r1,(c
i1,...,c
(x+ b1m)
(2.4)
(Limits exist by genericity of the point ξ.)
By Lemma 2.1 the right hand side of (2.4) is small for large enough M . So,
for large enough X (depending on M and (i1, . . . , ij)) the statement of the
lemma is true. By finiteness of S we conclude that the statement of the
lemma holds for k = 1.
GENERAL CASE (k > 1):
Suppose that the statement holds for k − 1.
Denote
vm(x)
r1,(c
i1,...,c
(a1x+ b1m) . . . ψ
rk,(c
i1,...,c
(akx+ bkm).
Let ε, δ > 0. We show that there exists I(ε, δ) ∈ N such that for every
I > I(ε, δ) a set S ⊂ [−I, I]j of density at least 1− δ can be chosen satisfying
the following property:
There exists I(ε, S) ∈ N such that for every I > I(ε, S) there exists
M(I) ∈ N such that for all M > M(I) for a set of i’s in {1, 2, . . . , I} of
density at least 1− ε
we have
< vm, vm+i >X
(2.5)
for all (i1, . . . , ij) ∈ S.
The Van der Corput lemma (Lemma 5.1 of Appendix) finishes the proof.
Note that the set of “good” i’s in the interval {1, 2, . . . , I} depends on
(i1, . . . , ij) ∈ S.
Denote
< vm, vm+i >X
1,j+1
r1,(c
i1,...c
ij ,b1i)
(a1x+ b1m) . . . ψ
k,j+1
rk,(c
i1,...,c
ij ,bki)
(akx+ bkm)
Denote y = a1x+ b1m. Assume that (a1, b1) = d. Denote
B̃y,m = ψ
1,j+1
r1,(c
i1,...c
ij ,b1i)
(y) . . . ψ
k,j+1
rk,(c
i1,...,c
ij ,bki)
(a′ky + b
where a′p =
, b′p = bp − a
pb1, 2 ≤ p ≤ k. We rewrite Ã as follows:
y≡dl mod a1
m≡φ(l) mod
B̃y,m
+ δX,M . (2.6)
Here φ is a bijection of Za1
defined by the identity
for every 0 ≤ l ≤ a1
− 1, Y = a1X , a
p as above and δX,M accounts for
the fact that for small y’s and y’s close to Y there is a difference between
elements that are taken in the expression for Ã and in the expression on the
right hand side of equation (2.6). Nevertheless, we have δX,M → 0 if
Denote
C̃y,m = ψ
2,j+1
r2,(c
i1,...,c
ij ,b2i)
(a′2y + b
2m) . . . ψ
k,j+1
rk,(c
i1,...,c
ij ,bki)
(a′ky + b
It will suffice to prove that there exists I(ε, δ) ∈ N such that for every I >
I(ε, δ) we can find S ⊂ [−I, I]j of density at least 1 − δ with the following
property:
There exists I(ε, S) ∈ N such that for every I > I(ε, S) there exists
M(I) ∈ N such that for every M > M(I) we can find X(M) ∈ N such that
for every X > X(M) for a set of i’s in {1, 2, . . . , I} of density at least 1 − ε
we have
y≡dl mod a1
m≡φ(l) mod
C̃y,m
(2.7)
for all 0 ≤ l ≤ a1
− 1, for all (i1, . . . , ij) ∈ S.
Note that it is enough to prove the latter statement for every particular
l : 0 ≤ l ≤ a1
Denote the left hand side of inequality (2.7) for a fixed l by D̃l.
Introduce new variables z and n, such that y = za1+ dl and m = n
+φ(l).
We obtain
D̃l =
2,j+1
t2n,z,l
. . . ψ
k,j+1
tkn,z,l
2,j+1
(a2z + c2n + q2) . . . ψ
k,j+1
(akz + ckn+ qk)
where shp = (rp, (c
1i1, . . . , c
j ij , bpi)),
n,z,l
ap(a1z+dl)+(a1bp−apb1)(
n+φ(l))
, qp =
apld+(a1bp−apb1)φ(l)
a1bp−apb1
6= 0, Z = Y
and N = Md
From the conditions on the function φ it follows that qp ∈ Z, 2 ≤ p ≤ k.
From the conditions of the lemma we obtain for every p 6= q, p, q > 1,
ap cp
aq cq
a1 det
ap bp
aq bq
6= 0.
Therefore, D̃l can be rewritten as
D̃l =
φ2 (a2z + c2n) . . . φk (akz + ckn)
where φℓ = ψ
ℓ,j+1
rℓ+qℓ,(c
i1,...,c
ij ,bℓi)
, 2 ≤ ℓ ≤ k. By the induction hypothesis the
following is true.
There exists Il(ε, δ
′) ∈ N big enough, such that for every Il ≥ Il(ε, δ
′) there
exist a subset Sl ⊂ [−Il, Il]
j+1 of density at least 1 − δ′2 and N(Sl, ε) ∈ N,
such that for every N ≥ N(Sl, ε) there exists Z(N, Sl, ε) ∈ N, such that for
every Z ≥ Z(N, Sl, ε) we have
D̃l <
(2.8)
for all (i1, . . . , ij , i) ∈ Sl.
For every (i1, . . . , ij) ∈ [−Il, Il]
j we denote by Sli1,...,ij the fiber above (i1, . . . , ij):
Sli1,...,ij = {i ∈ [−Il, Il] | (i1, . . . , ij , i) ∈ Sl}.
Then there exists a set Tl ⊂ [−Il, Il]
j of density at least 1− δ′, such that for
every (i1, . . . , ij) ∈ Tl the density of S
i1,...,ij
is at least 1 − δ′. Let ε, δ > 0.
Take δ′ < min ( ε
, δ) and I > max (I ′(ε), Il(ε, δ
′)) (I ′(ε) is taken from the van
der Corput lemma).
Then it follows by (2.8) that there exists M(Tl, ε, δ) ∈ N, such that for
every M ≥ M(Tl, ε, δ) there exists X(M,Tl, ε, δ) ∈ N, such that for every
X ≥ X(M,Tl, ε, δ) the inequality (2.7) holds for every fixed (i1, . . . , ij) ∈ Tl
for a set of i’s within the interval {1, . . . , I} of density at least 1 − ε
. The
lemma follows from the van der Corput lemma.
Proof of Proposition 2.1.
Denote vm(n)
= ξ1(a1n+b1m) . . . ξk(akn+bkm). For every i ∈ N we introduce
Ã defined by
< vm, vm+i >N
0,(b1i)
(a1n+ b1m) . . . ψ
0,(bki)
(akn + bkm)
where the functions ψp,j’s are autocorrelation functions of the ξp’s of length
By Lemma 2.2 it follows that for every ε > 0 there exists I(ε) ∈ N such that
for every I ≥ I(ε) there exist S ⊂ {1, 2, . . . , I} of density at least 1− ε
M(S, ε) such that for every M ≥ M(S, ε) there exists N(M,S, ε) such that
for every N ≥ N(M,S, ε) we have
0,(b2i)
(a2n+ b2m) . . . ψ
0,(bki)
(akn+ bkm)
≤ ε2.
The proposition follows from the van der Corput Lemma 5.1.
3 Probabilistic constructions of WM sets
The goal of this section is to prove the necessity of the conditions of Theorem
1.3.1. The following proposition is the main tool for this task.
Proposition 3.1 Let a, b ∈ N, c ∈ Z such that a 6= b. Then there exists a
normal set A within which the equation
ax = by + c (3.1)
is unsolvable, i.e., for every (x, y) ∈ A2 we have ax 6= by + c.
Remark 3.1 The proposition is a particular case of Theorem 1.3.1. It is a
crucial ingredient in proving the necessity direction of the theorem in general.
Proof. Let S ⊂ N. We construct from S a new set AS within which the
equation ax = by + c is unsolvable.
Without loss of generality, suppose that a < b.
Assume (a, b) = 1 (the general case follows easily). It follows from (a, b) =
1 that (3.1) is solvable. Any solution (x, y) of the equation ax = by +
c has restrictions on x. Namely, x ≡ φ(a, b, c)(mod b), where φ(a, b, c) ∈
{0, 1, . . . , b − 1} is determined uniquely. Let us denote l0
= φ(a, b, c). We
define inductively a sequence {li} ⊂ N ∪ {0}. If a pair (x, y) is a solution of
equation (3.1) and y ∈ biN + li−1 then choose li ∈ {0, 1, . . . , b
i+1 − 1} such
that x ∈ bi+1N+ li.
Note that from (a, b) = 1 it follows that (a, bi+1) = 1. It is clear that
if u, v ∈ N satisfy (u, v) = 1 then for any w ∈ Z there exists a solution
(x, y) ∈ N2 of the equation ux = vy + w. The latter implies that there exist
x ∈ N, y ∈ biN+ li−1 such that ax = by+ c. Any such x should be a member
of bi+1N+ li. Note that li and li−1 are connected by the identity
ali ≡ bli−1 + c ( mod b
i+1). (3.2)
In addition, if x ∈ N is given then the equation
ax ≡ by + c ( mod bi+1)
has at most one solution y ∈ {0, 1, . . . , bi − 1}.
We define sets Hi
= biN+ li−1 ; i ∈ N. We prove that for every i ∈ N, Hi+1 ⊂
Hi. All elements of Hi+1 are in the same class modulo b
i+1, therefore all
elements of Hi+1 are in the same class modulo b
i. So, if we show for some
x ∈ Hi+1 that x ≡ li−1(mod b
i) then we are done. For i = 1 we know
that if y ∈ N then any x ∈ N such that (x, y) is a solution of the equation
(3.1) has to be in H1. Take x ∈ H2 such that there exists y ∈ H1 with
ax = by + c. Then x ∈ H1. Therefore, we have shown that H2 ⊂ H1. For
i > 1 there exists x ∈ Hi+1 such that there exists y ∈ Hi with ax = by + c.
By induction Hi ⊂ Hi−1. Therefore, the latter y is in Hi−1. Therefore, by
construction of li’s we have that x ∈ Hi. This shows Hi+1 ⊂ Hi. We define
sets Bi; 0 ≤ i <∞:
B0 = N \H1,
B1 = H1 \H2
. . .
Bi = Hi \Hi+1
. . .
Clearly we have Bi∩Bj = ∅ , ∀i 6= j and |N\ (∪
i=0Bi)| = | ∩
i=1Hi| ≤ 1. The
latter is because for every i the second element (in the increasing order) of
Hi is ≥ b
We define AS =
i=0Ai, where Ai’s are defined in the following manner:
= S ∩ B0, C0
= B0 \ A0
= B1 \ {x | ax ∈ bB0 + c}, A1
= (B1 ∩ {x | ax ∈ bC0 + c}) ∪ (D1 ∩ S) ,
= B1 \A1
. . .
= Bi \ {x | ax ∈ bBi−1 + c}, Ai = (Bi ∩ {x | ax ∈ bCi−1 + c}) ∪ (Di ∩ S) ,
= Bi \ Ai
. . .
Here it is worthwhile to remark that for every i, Bi = Ai ∪ Ci. Therefore
AS ⊂ ∪
i=0Bi.
If for some i ≥ 1 we have y ∈ Ai ⊂ Bi = Hi \ Hi+1, then any x with
ax = by + c satisfies
ax ≡ bli−1 + c ( mod b
i+1).
From (a, bi+1) = 1 it follows that there exists a unique solution x modulo
bi+1. By identity (3.2) we have
x ≡ li ( mod b
i+1).
Thus x ∈ Hi+1.
If x ∈ Hi+2, then
x ≡ li+1 ( mod b
i+2).
Thus we have
ali+1 ≡ by + c ( mod b
i+2).
By uniqueness of a solution ( y ) modulo bi+1 we get
y ≡ li ( mod b
i+1).
Thus y ∈ Hi+1. We have a contradiction, which shows that x ∈ Hi+1\Hi+2 =
Bi+1.
The same argument works for y ∈ A0 ⊂ B0 and it shows that any x with
ax = by + c satisfies x ∈ B1.
So, if y ∈ Ai (i ≥ 0) then any x with ax = by + c should satisfy x ∈ Bi+1.
By construction of AS, x 6∈ AS. Thus equation (3.1) is not solvable in AS.
We make the following claim:
For almost every subset S of N the set AS is a normal set.
(The probability measure on subsets of N considered here is the product on
{0, 1}∞ of probability measures (1
The tool for proving the claim is the following easy lemma (for a proof see
Appendix, Lemma 5.2).
A subset A of natural numbers is a normal set if and only if for any k ∈
(N ∪ {0}) and any i1 < i2 < . . . < ik we have
χA(n)χA(n + i1) . . . χA(n+ ik) = 0, (3.3)
where χA(n)
= 2 · 1A(n)− 1.
First of all, we denote TN =
n=1 χAS(n)χAS(n + i1) . . . χAS(n + ik). Be-
cause of randomness of S, TN is a random variable. We will prove that
N=1E(T
) <∞ and this will imply by Lemma 5.3 that TN →N→∞ 0 for
almost every S ⊂ N.
E(T 2N) =
n,m=1
E(χAS(n)χAS(n+i1) . . . χAS(n+ik)χAS(m) . . . χAS(m+ik)).
Adding (removing) of a finite set to (from) a normal set does not affect the
normality of the set. The set ∪iBi might differ from N by at most one element
(| ∩∞i=1 Hi| ≤ 1). This possible element does not affect the normality of AS
and we assume without loss of generality that ∩∞i=1Hi = ∅, thus N = ∪
i=0Bi.
For every number n ∈ N we define the chain of n, Ch(n), to be the following
finite sequence:
If n ∈ B0, then Ch(n) = (n).
If n ∈ B1, then two situations are possible. In the first one there exists a
unique y ∈ B0 such that an = by+c. We set Ch(n) = (n, y) = (n, Ch(y)). In
the second situation we can not find such y from B0 and we set Ch(n) = (n).
If n ∈ Bi+1, then again two situations are possible. In the first one there
exists y ∈ Bi such that an = by + c. In this case we set Ch(n) = (n, Ch(y)).
In the second situation there is no such y from Bi. In this case we set
Ch(n) = (n). We define l(n) to be the length of Ch(n).
For every n ∈ N we define the ancestor of n, a(n), to be the last element of
the chain of n (of Ch(n)). To determine whether or not n ∈ AS will depend
on whether a(n) ∈ S. The exact relationship depends on the i for which
n ∈ Bi and on the j for which a(n) ∈ Bj or in other words on the length of
Ch(n): χAS(n) = (−1)
i−jχS(a(n)) = (−1)
l(n)−1χS(a(n)).
We say that n is a descendant of a(n).
It is clear that E(χAS(n1) . . . χAS(nk)) 6= 0 (E(χAS(n1) . . . χAS(nk)) ∈ {0, 1})
if and only if every number a(ni) occurs an even number of times among
numbers a(n1), a(n2), . . . , a(nk).
We bound the number of n,m’s inside the square [1, N ] × [1, N ] such that
E(χAS(n)χAS(n+ i1) . . . χAS(n+ ik)χAS(m)χAS(m+ i1) . . . χAS(m+ ik)) 6= 0.
For a given n ∈ [1, N ] we count all m’s inside [1, N ] such that for the ancestor
of n there will be a chance to have a twin among the ancestors of n+i1, . . . , n+
ik, m,m+ i1, . . . , m+ ik.
First of all it is obvious that in the interval [1, N ] for a given ancestor there
can be at most log b
N + C1 descendants, where C1 is a constant. For all
but a constant number of n’s it is impossible that among n + i1, . . . , n + ik
there is the same ancestor as for n. Therefore we should focus on ancestors
of the set {m,m + i1, . . . , m + ik}. For a given n we might have at most
(k + 1)(log b
N + C1) options for the number m to provide that one of the
elements of {m,m + i1, . . . , m + ik} has the same ancestor as n. Therefore
for most of n ∈ [1, N ] (except maybe a bounded number C2 of n’s which
depends only on {i1, . . . , ik} and doesn’t depend on N) we have at most
(k + 1)(log b
N + C1) possibilities for m’s such that
E(χAS(n)χAS(n+ i1) . . . χAS(n+ ik)χAS(m)χAS(m+ i1) . . . χAS(m+ ik)) 6= 0.
Thus we have
E(T 2N) ≤
(k + 1)(log b
N + C1) + C2N
((k+1) log b
N +C3),
where C3 is a constant. This implies
E(T 2N2) <∞.
Therefore TN2 →N→∞ 0 for almost every S ⊂ N. By Lemma 5.3 it follows
that TN →N→∞ 0 almost surely.
In the general case, where a, b are not relatively prime, if c satisfies (3.1) then
it should be divisible by (a, b). Therefore by dividing the equation (3.1) by
(a, b) we reduce the problem to the previous case.
We use the following notation:
Let W be a subset ofQn. Then for any increasing subsequence I = (i1, . . . , ip) ⊂
{1, 2, . . . , n} we define
ProjIW = WI = {(wi1, . . . , wip) | ∃w = (w1, w2, . . . , wn) ∈ W}.
We recall the notion of a cone.
Definition 3.1 A subset W ⊂ Qn is called a cone if
(a) ∀w1, w2 ∈ W we have w1 + w2 ∈ W
(b) ∀α ∈ Q : α ≥ 0 and ∀w ∈ W we have αw ∈ W .
The next step involves an algebraic statement with a topological proof which
we have to establish.
Lemma 3.1 Let W be a non-trivial cone in Qn which has the property that
for every two vectors ~a = {a1, a2, . . . , an}
t,~b = {b1, b2, . . . , bn}
t ∈ W there
exist two coordinates 1 ≤ i < j ≤ n (depend on the choice of ~a,~b) such that
ai bi
aj bj
There exist two coordinates i < j such that the projection of W on these two
coordinates is of dimension ≤ 1 (dimQ SpanProj(i,j)W ≤ 1).
Proof. First of all W has positive volume in V = SpanW (Volume is Haar
measure which normalized by assigning measure one to a unit cube and W
contains a parallelepiped). Fix an arbitrary non-zero element ~x ∈ W . For
every i, j : 1 ≤ i < j ≤ n we define the subspace
Ui,j = {~v ∈ V |Proj(i,j)~v ∈ SpanProj(i,j)~x}.
From the assumptions of the lemma it follows that
i,j;1≤i<j≤n
(W ∩ Ui,j).
For every i 6= j we obviously have that the volume of Ui,j is either zero or
Ui,j = V . If we assume that the statement of the lemma does not hold then
Ui,j 6= V, ∀i 6= j, and thus the volume of Ui,j , ∀i 6= j is zero. We get a
contradiction because a finite union of sets with zero volume cannot be equal
to a set with positive volume.
Proof. (of Theorem 1.3.1, ⇛)
Assume that an affine subspace A of Qk intersects Ak for any WM set A ⊂ N.
First of all, we shift the affine space to obtain a vector subspace, denote it
by U . The linear space U must contain vectors with all positive coordinates,
since A ∩Ak must be infinite.
Denote by W = {~v ∈ U | 〈~v, ~ei〉 ≥ 0 , ∀ i : 1 ≤ i ≤ k}. W is a non-trivial
cone.
Assume that for every ~a = (a1, . . . , ak)
t,~b = (b1, . . . , bk)
t ∈ W we have that
∃i, j : 1 ≤ i < j ≤ k such that
ai bi
aj bj
Then by Lemma 3.1 we deduce that there exist maximal subsets of coordi-
nates F1, . . . , Fl (one of them, assume F1, should have at least two coordi-
nates) such that for every r ∈ {1, 2 . . . , l} we have VFr
= SpanWFr is one
dimensional.
We fix r : 1 ≤ r ≤ l. We show that the projection on Fr of W + ~f is on a
diagonal, where ~f ∈ Zk is such that U + ~f = A. If the projection of W on
Fr is not on a diagonal then there exist two coordinates i < j from Fr such
that W(i,j) = {(ax, bx) | x ∈ N} for some a 6= b natural numbers. Therefore
the projection of A on (i, j) has the form {(ax+ f1, bx+ f2) | x ∈ N}, where
f1, f2 are integers. From Proposition 3.1 it follows that for any a, b, c, where
a 6= b, there exists a WM set A (even a normal set) such that the equation
ax = by + c is not solvable within A. This proves the existence of a WM set
A0 such that for every x ∈ Z we have (ax+ f1, bx+ f2) 6∈ A
0 (introduce the
new variables z1, z2 by (z1, z2) = (ax1+ f1, bx+ f2) and take a normal set A0
such that the equation az2 = bz1 + (af2 − bf1) is unsolvable within A0).
Thus ∀i, j ∈ Fr : W(i,j) = {(ax, ax) | x ∈ N}.
To prove that a shift is the same for all coordinates in Fr we merely should
know that for any natural number c there exists a WM set Ac such that
inside Ac the equation x− y = c is not solvable. The last statement is easy
to verify.
Let jr ∈ Fr, ∀1 ≤ r ≤ l. Denote I = (j1, . . . , jl). We have proved that there
exist g1, . . . , gl ∈ N, c1, . . . , cl ∈ Z such that
(U + ~f)I = {(g1x1 + c1, . . . , glxl + cl) | x1, . . . , xl ∈ Q}.
It is clear that we can find ~a,~b which satisfy all the requirements of Theorem
1.3.1. This completes the proof.
Remark 3.2 We have proved that if an affine subspace A ⊂ Qk intersects
Ak for any normal set A ⊂ N, then there exist ~a,~b ∈ Nk and a partition
F1, . . . , Fl of {1, 2, . . . , k} such that:
(a) ∀r : 1 ≤ r ≤ l and ∀i ∈ Fr, ∀j 6∈ Fr we have
ai bi
aj bj
6= 0.
(b) ∃~f ∈ Zk such that the set {n~a +m~b+ ~f |n,m ∈ N} is in A.
Thus, we have proved the direction “⇛” of Theorem 1.3.2.
4 Comparison with Rado’s Theorem
We recall that the problem of solvability of a system of linear equations in
one cell of any finite partition of N was solved by Rado in [10]. Such systems
of linear equations are called partition-regular. We show that partition-
regular systems are solvable within every WM set by use of Theorem 1.3.1.
It is important to note that solvability of partition-regular linear systems of
equations within WM sets can be shown directly (without use of Theorem
1.3.1) by use of the technique of Furstenberg and Weiss that was developed
in their dynamical proof of Rado’s theorem (see [8]).
First of all we describe Rado’s regular systems.
Definition 4.1 A rational p × q matrix (aij) is said to be of level l if the
index set {1, 2, . . . , q} can be divided into l disjoint subsets I1, I2, . . . , Il and
rational numbers crj may be found for 1 ≤ r ≤ l and 1 ≤ j ≤ q such that the
following relationships are satisfied:
aij = 0
aij =
c1jaij
. . .
aij =
j∈I1∪I2∪...∪Il−1
cl−1j aij
for i = 1, 2, . . . , p.
Theorem 4.1 (Rado) A system of linear equations is partition-regular if and
only if for some l the matrix (aij) is of level l and it is homogeneous, i.e. a
system of the form
aijxj = 0, i = 1, 2, . . . , p.
The following claim is the main result of this section.
Proposition 4.1 A partition-regular system is solvable in every WM set.
Proof. Let a system
j=1 aijxj = 0, i = 1, 2, . . . , p be partition-regular.
We will use the fact that the system is solvable for any finite partition of N.
First of all, the set of solutions of a partition-regular system is a subspace of
Qq; denote it by V . It is obvious that V contains vectors with all positive
components. If for some 1 ≤ i < j ≤ q we have Proj+i,jV (where Proj
i,jV =
{(x, y)|x, y ≥ 0 & ∃~v ∈ V :< ~v, ~ei >= x , < ~v, ~ej >= y}) is contained
in a line, then Proj+i,jV is diagonal, i.e. it is contained in {(x, x)|x ∈ Q}.
Otherwise, we can generate a partition of N into two disjoint sets S1, S2 such
that no S
1 and no S
2 intersects V :
This partition is constructed by an iterative process. Without loss of gener-
ality we may assume that the line is x = ny, where n ∈ N. The general case
is treated in the simillar way. We start with S1 = S2 = ∅. Let 1 ∈ S1.
We “color” the infinite geometric progression {nm |m ∈ N} (adding elements
to either S1 or S2) in such way that there is no (x, y) on the line from S
1 , S
Then we take a minimal element from N which is still uncolored. Call it a.
Add a to S1. Next, “color” {an
m |m ∈ N}.
Continuing in this fashion, we obtain the desired partition of N.
This contradicts the assumption that the given system is partition-regular.
Let F1, . . . , Fl be a partition of {1, 2, . . . , k} such that for every r ∈ {1, . . . , l}
we have for every i 6= j , i, j ∈ Fr : dim QSpan(Proj
i,jV ) = 1, and for every
r : 1 ≤ r ≤ l, every i ∈ Fr .and for every j 6∈ Fr we have dim QSpan(Proj
i,jV ) =
2. For every r : 1 ≤ r ≤ l we choose arbitrarily one representative index
within Fr and denote it by jr (jr ∈ Fr).
Then there exist g1, . . . , gl ∈ N such that
VI = {(g1x1, . . . , glxl) | x1, . . . , xl ∈ Q}.
The latter ensures that there exist vectors ~a,~b ∈ V which satisfy all the
requirements of Theorem 1.3.1 and, therefore, the system is solvable in every
WM set.
5 Appendix
In this section we prove all technical lemmas and propositions that were used
in the paper.
We start with the key lemma which is a finite modification of Bergelson’s
lemma in [1]. Its origin is in a lemma of van der Corput.
Lemma 5.1 Suppose ε > 0 and {uj}
j=1 is a family of vectors in Hilbert
space, such that ‖uj‖ ≤ 1 (1 ≤ j ≤ ∞). Then there exists I
′(ε) ∈ N, such
that for every I ≥ I ′(ε) there exists J ′(I, ε) ∈ N, such that the following
holds:
For J ≥ J ′(I, ε) for which we obtain
〈uj, uj+i〉
for a set of i’s in the interval {1, . . . , I} of density 1− ε
we have
Proof. For an arbitrary J define uk = 0 for every k < 1 or k > J . The
following is an elementary identity:
uj−i = I
Therefore, the inequality
i=1 ui
i=1 ‖ui‖
yields
≤ (J + I)
= (J + I)
uj−p,
uj−s〉
= (J+I)
‖uj−p‖
+2(J+I)
r,s=1;s<r
〈uj−r, uj−s〉 = (J+I)(Σ1+2Σ2),
where Σ1 = I
by the aforementioned elementary identity and
h=1(I−h)
j=1〈uj, uj+h〉. The last expression is obtained by rewrit-
ing Σ2, where h = r − s. By dividing the foregoing inequality by I
2J2 we
obtain
J + I
J + I
J + I
Choose I ′(ε) ∈ N, such that 12
≤ I ′(ε) ≤ 12
+1. Then for every I ≥ I ′(ε) we
have 1
≤ 11ε
. There exists J ′(I, ε) ∈ N, such that for every J ≥ J ′(I, ε):
. As a result, for every I ≥ I ′(ε) there exists J ′(I, ε), such that for
every J ≥ J ′(I, ε)
The next proposition was used in Section 2.
Proposition 5.1 Let A ⊂ N be a WM-set. Then for every integer a > 0
and every integers b1, b2, . . . , bk
ξ(n+ b1)ξ(n+ b2) . . . ξ(n+ bk) =
ξ(an+ b1)ξ(an+ b2) . . . ξ(an+ bk),
where ξ
= 1A − d(A).
Proof. Consider the weak-mixing measure preserving system (Xξ,B, µ, T ).
The left side of the equation in the proposition is
T b1fT b2f . . . T bkfdµ,
where f(ω)
= ω0 for every infinite sequence inside Xξ. We make use of the
notion of disjointness of measure preserving systems. By [6] we know that
every weak-mixing system is disjoint from any Kronecker system which is
a compact monothethic group with Borel σ-algebra, the Haar probability
measure, and the shift by a chosen element of the group. In particular,
every weak-mixing system is disjoint from the measure preserving system
(Za,BZa , S, ν), where Za = Z/aZ, S(n)
= n+ 1( mod a). The measure and
the σ-algebra of the last system are uniquely determined. Therefore, from
Furstenberg’s theorem (see [6], Theorem I.6) it follows that the point (ξ, 0) ∈
Xξ×Za is a generic point of the product system (Xξ×Za,B×BZa , T×S, µ×ν).
Thus, for every continuous function g on Xξ × Za we obtain
Xξ×Za
g(x,m)dµ(x)dν(m) = lim
g(T nξ, Sn0).
Let g(x,m)
= f(x)10(m), which is obviously continuous on Xξ × Za. Then
genericity of the point (ξ, 0) yields
Xξ×Za
f(x)10(m)dµ(x)dν(m) =
f(x)dµ(x) =
f(T nξ)10(n) = lim
f(T anξ).
Taking instead of the function f the continuous function T b1fT b2f . . . T bkf
in the definition of g finishes the proof.
The next two lemmas are very useful for constructing normal sets with specif-
ical properties.
Lemma 5.2 Let A ⊂ N. Let λ(n) = 21A(n)− 1. Then A is a normal set ⇔
for any k ∈ (N ∪ {0}) and any i1 < i2 < . . . < ik we have
λ(n)λ(n+ i1) . . . λ(n+ ik) = 0.
Proof. “⇒” If A is normal then any finite word w ∈ {−1, 1}∗ has the
“right” frequency 1
inside wA. This guarantees that “half of the time” the
function λ(n)λ(n + i1) . . . λ(n + ik) equals 1 and “half of the time” is equal
to −1. Therefore we get the desired conclusion.
“⇐” Let w be an arbitrary finite word of plus and minus ones: w = a1a2 . . . ak
and we have to prove that w occurs in wA with the frequency 2
−k. For every
n ∈ N the word w occurs in 1A and starting from n if and only if
1A(n) = a1
. . .
1A(n+ k − 1) = ak
The latter is equivalent to the following
λ(n) = 2a1 − 1
. . .
λ(n+ k − 1) = 2ak − 1
The frequency of w within 1A is equal to
λ(n)(2a1 − 1) + 1
. . .
λ(n+ k − 1)(2ak − 1) + 1
The limit is equal to 1
Lemma 5.3 Let {an} be a bounded sequence. Let TN =
n=1 an. Then
TN converges to a limit t ⇔ there exists a sequence of increasing indices {Ni}
such that Ni
→ 1 and TNi →i→∞ t.
References
[1] Bergelson, V. Weakly mixing PET. Ergodic Theory Dynam. Sys-
tems 7 (1987), no. 3, 337–349.
[2] Bergelson, V.; McCutcheon, R. An ergodic IP polynomial Sze-
merédi theorem. Mem. Amer. Math. Soc. 146 (2000), no. 695.
[3] Fish, A. Random Liouville functions and normal sets. Acta Arith.
120 (2005), no. 2, 191–196.
[4] Fish, A. Polynomial largeness of sumsets and totally ergodic sets,
see http://arxiv.org/abs/0711.3201.
[5] Fish, A. Ph.D. thesis, Hebrew University, 2006.
[6] Furstenberg, H. Disjointness in ergodic theory, minimal sets, and
a problem in Diophantine approximation. Math. Systems Theory
1 (1967), 1-49.
[7] Furstenberg, H. Ergodic behavior of diagonal measures and a
theorem of Szemerédi on arithmetic progressions. J. d’ Analys
Math. 31 (1977), 204–256.
[8] Furstenberg, H. Recurrence in Ergodic Theory and Combinatorial
Number Theory. Princeton Univ. Press 1981.
[9] Host, B.; Kra, B. Nonconventional ergodic averages and nilman-
ifolds. Ann. of Math. (2) 161 (2005), no. 1, 397–488.
[10] Rado, R. Note on combinatorial analysis. Proc. London Math.
Soc. 48 (1943), 122–160.
[11] Schur, I. Uber die Kongruenz xm+ym ≡ zm(modp). Jahresbericht
der Deutschen Math.-Ver. 25 (1916), 114–117.
[12] Szemerédi, E. On sets of integers containing no k elements in
arithmetic progression. Collection of articles in memory of Jurǐi
Vladimirovič Linnik. Acta Arith. 27 (1975), 199–245.
Current Address:
Department of Mathematics
University of Wisconsin-Madison
480 Lincoln Dr.
Madison, WI 53706-1388
E-mail: afish@math.wisc.edu
http://arxiv.org/abs/0711.3201
	Introduction
	Algebraic patterns within subsets of N
	Generic points and WM sets
	Solvability of linear diophantine systems within WM sets and normal sets
	Acknowledgments
	Proof of Sufficiency
	Probabilistic constructions of WM sets
	 Comparison with Rado's Theorem
	Appendix
