THE GEOMETRIC CASE OF THE ERDOS SIMILARITY CONJECTURE
=====================================================
A complete and self-contained proof.
Everything in the proof is proved here. The only background used is:
Lebesgue measure on the line, the fractional part of a real number, and
the probability of independent coin flips. A reader who knows what a
limit is can follow all of it.
CONTENTS
0. Summary
1. The theorem
2. The plan
3. Step 1. One periodic set for all centers
4. Step 2. Grids
5. Step 3. The tree and the windows
6. Step 4. Random tests
7. Step 5. The tests are independent
8. Step 6. All scales at once
9. Step 7. All centers at once
10. The theorem
11. Remarks and history
12. Symbols
0. SUMMARY
----------
Fix a ratio q with 0 < q < 1 and look at the geometric progression
G_q = { q, q^2, q^3, ... }.
A copy of G_q is a translate and rescale of it:
x + s G_q = { x + s q^n : n = 1, 2, 3, ... }, s not 0.
The Erdos similarity conjecture says that no infinite set is contained
in every set of positive measure. This note proves the conjecture for
the single set G_q: for every q and every eta with 0 < eta < 1 there is
a compact set E inside [0,1] that fills more than 1 - eta of the
interval and contains no copy of G_q at all.
So almost all of [0,1] can be made free of progressions of ratio q. The
set E depends on q; we do not claim that one set works for two
different ratios at the same time.
1. THE THEOREM
--------------
Write m for Lebesgue measure on the real line R, and
{z} = z - floor(z)
for the fractional part of a real number z.
THEOREM. Let 0 < q < 1 and 0 < eta < 1. There is a compact set E
contained in [0,1] with m(E) > 1 - eta such that for every real x and
every real s not 0 there is an integer n >= 1 with
x + s q^n not in E.
In words: no translate-and-rescale copy of G_q is contained in E.
We build the complement C = [0,1] minus E. It must be small (measure
less than eta) and it must meet every copy of G_q, because a copy that
meets C cannot be contained in E.
2. THE PLAN
-----------
Three ideas carry the proof.
(i) ONE PERIODIC SET HANDLES ALL CENTERS. Instead of chasing single
copies we build an open set H that repeats with period 1 and
meets every copy whose scale factor lies in the fixed window
[1,2]. Periodicity does the work for all centers at once.
(ii) SUMMABLE BUDGETS HANDLE ALL SCALES. Every nonzero scale is
s = (+ or -) 2^k t with k an integer and t in [1,2). Densities
that decay geometrically in k cover all scales at arbitrarily
small total cost.
(iii) RANDOM TESTS IN A TREE HANDLE ALL CENTERS AND SCALES. For one
fixed center and one fixed scale, many independent random tests
make a total miss unlikely. The hard part is that center and
scale both vary continuously. A finite ordered tree of tables
lets each group of tests read only the grids of one edge and of
its subtree, so a moving scale triggers only boundedly many
"grid events" per group.
Part (i) is the whole content of the proof, Sections 4 to 9. Part (ii)
is short and we do it first, so that the construction has one clear
target.
3. STEP 1. ONE PERIODIC SET FOR ALL CENTERS
-------------------------------------------
For a measurable set A that repeats with period 1, write
rho(A) = m( A intersect [0,1) )
for the measure of one period.
PROPOSITION. Let 0 < q < 1 and 0 < p < 1. There is an open set H,
periodic with period 1, such that
rho(H) <= 6p, (3.1)
and for every real x and every t in [1,2] there is an integer n >= 1
with
x + t q^n in H. (3.2)
Sections 4 to 9 prove the Proposition. Here we deduce the theorem from
it.
PROOF OF THE THEOREM, ASSUMING THE PROPOSITION.
For each integer k put
p_k = (eta/64) * 4^(-|k|)
and let H_k be a set supplied by the Proposition with p = p_k. Define
C = union over all integers k of ( 2^k H_k union -2^k H_k ),
E = [0,1] minus C.
STEP A: E is compact. C is open, being a union of open sets, so E is
closed; E is also bounded. Hence E is compact.
STEP B: C is small. Suppose A has period 1. Then 2^k A has period 2^k
and measure 2^k rho(A) in each of its periods.
- If k <= 0, the interval [0,1] is exactly 2^(-k) periods long, so
m( (2^k A) intersect [0,1] ) = rho(A).
- If k > 0, the interval [0,1] fits inside one period of length 2^k,
so
m( (2^k A) intersect [0,1] ) <= 2^k rho(A).
In both cases m( (2^k A) intersect [0,1] ) <= max(1, 2^k) rho(A), and
the same holds for -2^k A. Apply this to A = H_k and use (3.1):
m( C intersect [0,1] )
<= 2 * sum over k of 6 p_k max(1, 2^k)
= 12 * (eta/64) * sum over k of 4^(-|k|) max(1, 2^k).
The sum splits. For k <= 0, max(1, 2^k) = 1 and
sum over k <= 0 of 4^(-|k|) = sum over j >= 0 of 4^(-j) = 4/3.
For k >= 1, max(1, 2^k) = 2^k and
sum over k >= 1 of 4^(-k) 2^k = sum over k >= 1 of 2^(-k) = 1.
The total is 4/3 + 1 = 7/3, so
m( C intersect [0,1] ) <= 12 * (eta/64) * (7/3) = 7 eta / 16 < eta,
and therefore m(E) > 1 - eta.
STEP C: every copy meets C. Fix a real x and a real s not 0.
- If s > 0, write s = 2^k t with k an integer and t in [1,2). Apply
(3.2) to H_k with the center x / 2^k: there is n >= 1 with
x/2^k + t q^n in H_k,
and multiplying by 2^k gives x + s q^n in 2^k H_k, which lies in C.
- If s < 0, apply the s > 0 case to -x and -s > 0, then use the
reflection symmetry of C.
So every copy of G_q meets C, hence no copy is contained in E. This
proves the theorem, apart from the Proposition. []
4. STEP 2. GRIDS
----------------
Fix q with 0 < q < 1 for the rest of the proof, and put
c = 4 / (1 - q).
For each integer b >= 1 define
N_b = 2 ^ ( smallest integer >= log2( c q^(-b) ) ),
Gamma_b = (1 / N_b) Z.
So Gamma_b is a grid of points spaced 1/N_b apart, and N_b is a power
of two. For real z let
J_b(z) = floor( N_b {z} )
be the index of the half-open cell of Gamma_b that contains z, namely
[ J_b(z)/N_b , (J_b(z)+1)/N_b ).
Cells are closed on the left and open on the right, so a grid point
belongs to the cell on its right.
FACT 1 (grid size). For every b >= 1,
c q^(-b) <= N_b < 2 c q^(-b). (4.1)
The right inequality holds because the chosen exponent is at most one
more than log2(c q^(-b)); the left one because it is at least that.
FACT 2 (nesting). Each N_b is a power of two, and since c q^(-b) grows
with b, N_b <= N_(b+1). Hence for b' >= b the quotient N_(b')/N_b is
a positive integer and
J_b(z) = floor( J_(b')(z) / (N_(b')/N_b) ) for every real z.
In words: a fine key determines every coarser key. This is the only
reason we insist on powers of two. It lets a random table indexed by a
coarse grid be read unambiguously at a finer resolution.
Every key J_b is periodic with period 1, because {z} is.
5. STEP 3. THE TREE AND THE WINDOWS
-----------------------------------
Fix integers
M >= 2, d >= 1, g >= 1, r_0 >= 1.
They are chosen in Section 9. Everything in this section and the next
three is valid for any such choice.
THE TREE. Let T be the complete ordered M-ary tree of height d. The
root has height d, leaves have height 0, and every vertex of height
h >= 1 has exactly M children, each of height h - 1. Write P_1,...,P_M
for the children of P in order, and (P,i) for the edge from P to P_i.
The number of edges is
K = M + M^2 + ... + M^d.
PREORDER. Order the edges as follows: from a vertex P, first list
(P,1), then all edges in the subtree of P_1, then (P,2), then the
subtree of P_2, and so on up to P_M. The useful consequence: an edge
together with its whole child subtree occupies one consecutive block
of the list.
WINDOWS. Attach to each edge e an interval of integers
W_e = [a_e, b_e] intersect the positive integers,
placing these intervals in preorder and leaving exactly g unused
integers between consecutive ones. All M edges leaving a vertex of
height h get a window of the same length r_h, defined from the bottom
up. Let sigma_h be the total span, gaps included, of all windows
inside a subtree of height h. Set
r_1 = r_0,
sigma_1 = M r_1 + (M - 1) g,
and for 2 <= h <= d
r_h = max( r_0 , g + sigma_(h-1) ), (5.1)
sigma_h = M ( r_h + g + sigma_(h-1) ) + (M - 1) g.
Read (5.1) as follows: a window is at least as long as the following
gap plus everything in its child subtree together. That single
condition is the technical heart of the proof.
BEGIN FAR OUT. Choose an integer n_0 >= 1 with
2 q^(n_0) <= 1/4, (5.2)
and start the whole list of windows at n_0 or later. Let
N = union of all W_e
be the set of indices the finite construction uses.
RESOLUTIONS. Edge e carries the grid Gamma_(b_e).
BLOCKS. For an edge e = (P,i), let b_e^* be the largest endpoint among
W_e and all windows below e. So the block "e and everything after it"
uses grids Gamma_b with b_e <= b <= b_e^*.
LEMMA 1 (block span). If e leaves a vertex of height h, then
b_e^* - a_e + 1 <= 2 r_h. (5.3)
PROOF. If h = 1 the child P_i is a leaf, so the block is just W_e,
b_e^* = b_e, and the span is r_1 = r_0 <= 2 r_0. If h >= 2, preorder
puts the whole child subtree immediately after W_e, across one gap of
length g, so
b_e^* - a_e + 1 = r_h + g + sigma_(h-1),
which is at most 2 r_h by (5.1). []
By (5.3) the finest grid used anywhere in e's block has index at most
2 r_h - 1 beyond a_e. That resolution bound depends only on the length
of W_e, not on the size of the whole tree. This is what makes the
argument work.
STABLE CENTERS. Call x stable if, for every window W_e other than the
first, with b' the endpoint of the window immediately before it,
the interval (x, x + 2 q^(a_e)] contains no point of Gamma_(b').
Let S be the set of stable centers. Reason for the definition: if n is
in W_e and t is in [1,2], then x + t q^n sits at distance at most
2 q^(a_e) to the right of x. If no point of Gamma_(b') lies in
between, no coarse key of x changes.
LEMMA 2 (stability). The set S is measurable and periodic with period
1, and
rho( R minus S ) <= 4 K c q^(g+1). (5.4)
If x is stable, n is in W_e and t is in [1,2], then every edge f that
precedes e in preorder satisfies
J_(b_f)( x + t q^n ) = J_(b_f)( x ). (5.5)
PROOF. Fix a noninitial window W_e, with b' the endpoint of the window
before it. The centers that break stability there form the union of
intervals
[ gamma - 2 q^(a_e), gamma ) over all gamma in Gamma_(b').
Its measure per period is at most the sum of the interval lengths,
2 q^(a_e) N_(b') <= 2 q^(a_e) * 2 c q^(-b') = 4 c q^(a_e - b'),
by (4.1). Since consecutive windows leave exactly g unused indices,
a_e = b' + g + 1, so this density is at most 4 c q^(g+1). There are at
most K - 1 noninitial windows, so summing gives (5.4). Each Gamma_(b')
is periodic with period 1, so S is too.
Now let x be stable, n in W_e, t in [1,2]. If e is the first window
there is no earlier edge and nothing to prove. Otherwise let b' be the
endpoint of the preceding window. Since n >= a_e and t <= 2,
0 < t q^n <= 2 q^(a_e).
The interval (x, x + t q^n] lies inside (x, x + 2 q^(a_e)], which holds
no point of Gamma_(b'). A half-open cell of Gamma_(b') that contains x
therefore also contains x + t q^n: if x is not a grid point the segment
cannot cross one, and if x is a grid point it is the left end of its
own cell and the next grid point to the right lies beyond x + t q^n.
Hence J_(b')(x + t q^n) = J_(b')(x). Every earlier edge f has
b_f <= b', so nesting (Fact 2) gives (5.5). []
SEPARATION. Stability freezes the keys read before. Inside the current
window the translated points are far enough apart to be told apart by
the current grid.
LEMMA 3 (separation). Fix an edge e, a real x and t in [1,2]. The
points
x, and x + t q^n for n in W_e,
have pairwise distinct keys under J_(b_e). They also have pairwise
distinct keys under every J_b with b >= b_e.
PROOF. Write b = b_e. By (5.2) and n >= n_0, all the listed points lie
in [x, x + 2 q^(n_0)], an interval of length at most 1/4. Two points at
distance at most 1/4 have equal distance on the circle R/Z and on the
line, so there is no wraparound to worry about. Compare distances with
the cell width 1/N_b.
- Distance from x to x + t q^n: this is t q^n, and t >= 1 with
n <= b, so it is at least q^b.
- Distance from x + t q^n to x + t q^(n'), for n < n': this is
t q^n ( 1 - q^(n'-n) ) >= (1 - q) q^n >= (1 - q) q^b.
On the other hand (4.1) gives
1/N_b <= q^b / c = (1 - q) q^b / 4 < (1 - q) q^b,
which is smaller than every distance above. Two points with the same
key under J_b lie in the same half-open cell, so their circular
distance is less than 1/N_b. All distances above exceed 1/N_b, so all
keys are distinct. For b >= b_e the key J_b determines J_(b_e) by
nesting, so distinctness persists at every finer resolution. []
6. STEP 4. RANDOM TESTS
-----------------------
Keep the tree, the windows and the grids of Section 5, and fix
0 < p < 1.
SELECTOR TABLES. For every edge e = (P,i) with i < M let S_e be a
table of independent fair coin flips, one per cell of Gamma_(b_e):
S_e : {0, 1, ..., N_(b_e) - 1} -> {0, 1}.
The last child P_M is the default child and has no table.
TERMINAL TABLES. For every leaf L let e(L) be its incoming edge and
b(L) its window endpoint. Let T_L be a table whose entries are
independent, each equal to 1 with probability p and to 0 with
probability 1 - p:
T_L : {0, 1, ..., N_(b(L)) - 1} -> {0, 1}.
All entries of all tables are mutually independent. There are finitely
many, so they form a finite probability space Omega with probability P
and expectation E.
ROUTING. Given an outcome and a real point z, route z down the tree.
At an internal vertex P take the first child P_i, i < M, whose selector
reads a 1 at the cell of z:
S_(P,i)( J_(b_(P,i))(z) ) = 1.
If all M - 1 selectors read 0, take the default child P_M. Continue to
a leaf. Let L(z) be the leaf reached, and define
B = { z : T_(L(z))( J_(b(L(z)))(z) ) = 1 }. (6.1)
So z is in B when its route ends at a leaf whose terminal bit at z's
cell is 1.
Every J_b is periodic, so every realization of B is 1-periodic. Only
finitely many grids appear, each refining the coarsest, so B is a
finite union of half-open cells per period.
LEMMA 4 (mean density). E rho(B) = p.
PROOF. Let A be the sigma-field generated by all selector entries, so
A knows every route but no terminal bit. Fix z. Given A, the leaf L(z)
and the terminal address J_(b(L(z)))(z) are known, and the single
terminal bit there is still Bernoulli(p). Hence P(z in B | A) = p.
Integrating over one period, and exchanging the integral with the
finite sum over outcomes,
E rho(B) = integral over [0,1) of P(z in B) dz
= integral over [0,1) of p dz = p. []
7. STEP 5. THE TESTS ARE INDEPENDENT
------------------------------------
Fix a center x. Reveal, in every selector table, the single entry that
x addresses:
F_x = sigma( S_e( J_(b_e)(x) ) : e = (P,i), i < M ).
An atom xi of F_x is a definite pattern of zeros and ones on those
entries, with positive probability. Since x is fixed, the addresses are
fixed before we look. On every atom:
- every selector entry not addressed by x is still an independent
fair bit;
- every terminal entry is still an independent Bernoulli(p) bit.
The revealed entries determine the whole route of x. Either it uses a
default child somewhere, or it never does.
LEMMA 5 (no default is unlikely). For every real x,
P( the route of x never takes a default child )
= ( 1 - 2^(1-M) )^d. (7.1)
PROOF. Walk down the route. At each of the d internal vertices on it,
the M - 1 selector entries checked there are independent fair bits,
because the route so far used only tables of earlier edges. The
probability that all of them read 0 is 2^(-(M-1)) = 2^(1-M). The d
decisions use disjoint sets of tables, hence are independent, and we
multiply. []
Now fix a stable center x and an atom xi on which the route of x does
take a default. Let U be the first vertex where it does, let h be the
height of U, and put
r = r_h, e_i = (U,i) for 1 <= i < M, y_n(t) = x + t q^n.
All M - 1 selector values at x on e_1,...,e_(M-1) are zero: that is
what "first default at U" means. Note F_x reveals these entries even
for children the route of x does not take.
For i < M let L_i(z) be the leaf reached by routing z starting at the
child U_i; if U_i is a leaf, put L_i(z) = U_i. Define the local test
Q_i(z) = S_(e_i)( J_(b_(e_i))(z) ) * T_(L_i(z))( J_(b(L_i(z)))(z) ).
The first factor says "the selector on e_i sends z to child i"; the
second says "the terminal table at the end of that road says member".
So Q_i(z) = 1 certifies z in B. Note Q_i consults only tables attached
to e_i and to edges below it.
LEMMA 6 (a local hit is a real hit). Let x be stable and let xi be an
atom of F_x on which the route of x has a first default U. Then for
every outcome in xi, every i < M, every n in W_(e_i) and every t in
[1,2], the point y_n(t) reaches U; and if Q_i( y_n(t) ) = 1 then
y_n(t) lies in B.
PROOF. Let P be a vertex strictly above U and let a < M be the child
the route of x takes at P. Then the entries at x on (P,1),...,(P,a-1)
are 0 and the entry on (P,a) is 1. All these edges precede e_i in
preorder, so by Lemma 2 the point y_n(t) reads the same entries there
as x. Hence y_n(t) also takes child a at P. Applying this from the root
down, y_n(t) reaches U.
At U, for every j < i the edge (U,j) precedes e_i, so y_n(t) reads the
same zero at (U,j) that x does, and y_n(t) takes no child below i. If
also Q_i( y_n(t) ) = 1, then the selector on e_i sends y_n(t) to child
i, the route continues to the leaf L_i( y_n(t) ), and the terminal bit
there is 1. That is exactly the membership condition (6.1). []
LEMMA 7 (exact failure probability at one scale). Keep the hypotheses
of Lemma 6 and put r = r_h. For every fixed t in [1,2],
P( Q_i( y_n(t) ) = 0 for all i < M and all n in W_(e_i) | xi )
= ( 1 - p/2 )^( (M-1) r ). (7.2)
PROOF. On the atom xi the index set
I = { (i,n) : 1 <= i < M, n in W_(e_i) }
is fixed and has exactly (M - 1) r elements. For each pair put
A_(i,n) = S_(e_i)( J_(b_(e_i))( y_n(t) ) ).
STEP 1: given xi, the A_(i,n) are independent fair bits. For fixed i,
Lemma 3 says x and the points y_n(t), n in W_(e_i), have pairwise
distinct keys at resolution b_(e_i). So the A_(i,n) read distinct
entries of the single table S_(e_i), none of them the entry addressed
by x that xi fixed. Different i use different tables. Every unrevealed
selector entry is still an independent fair bit on xi.
STEP 2: condition further on A, the sigma-field of all selectors. Now
every route is known, so every leaf and every terminal address
kappa_(i,n) = ( L_i( y_n(t) ), J_(b(L_i(y_n(t))))( y_n(t) ) )
is fixed. These addresses are pairwise distinct:
- if the indices i differ, the leaves lie in different subtrees of U,
so their tables differ;
- if the indices i agree but the leaves differ, the tables again
differ;
- if both i and the leaf L agree for two indices n, n', then the
incoming edge of L is e_i or one below it, so b(L) >= b_(e_i); by
Lemma 3 the points y_n(t), y_(n')(t) have different keys at
resolution b_(e_i), and nesting keeps them different at b(L).
So, even after conditioning on A, the terminal bits at all these
addresses are independent Bernoulli(p) bits.
Now compute. Given A, a pair with A_(i,n) = 0 fails at once, and a pair
with A_(i,n) = 1 fails exactly when its terminal bit is 0. Hence
P( all Q_i( y_n(t) ) = 0 | A ) = (1 - p) ^ ( sum of A_(i,n) ).
Average over the selector bits using Step 1. Each A_(i,n) is a fair bit
and they are jointly independent, so
E[ (1 - p)^(A_(i,n)) | xi ] = (1/2) * 1 + (1/2) * (1 - p)
= 1 - p/2,
and the exponent splits as a product over the (M - 1) r pairs. That is
(7.2). []
8. STEP 6. ALL SCALES AT ONCE
-----------------------------
Lemma 7 controls one fixed scale. As t runs over [1,2] the vector
( Q_i( y_n(t) ) : i < M, n in W_(e_i) )
changes, but only finitely often, and the number of regimes is
controlled by the block span (5.3).
LEMMA 8 (all normalized scales, conditionally). Fix p, M, d, g, r_0.
Let x be stable and let xi be an atom of F_x on which the route of x
has a first default U of height h. Put r = r_h and
D(r) = 4 + 2 (M - 1) r ( 1 + 2 c q^(-2r) ). (8.1)
Then
P( there is t in [1,2] with y_n(t) not in B for all n in N | xi )
<= D(r) * exp( - p (M - 1) r / 2 ). (8.2)
PROOF. Write b*_i = b*_(e_i). Every table consulted by Q_i is attached
to e_i or an edge below it, each with window endpoint at most b*_i; the
selector on e_i itself is read at resolution b_(e_i), also at most b*_i.
By nesting (Fact 2), Q_i(z) is therefore a function of the single key
J_(b*_i)(z): the finest key of the block determines every coarser key
of the block, hence every bit Q_i consults.
Fix i < M and n in W_(e_i), and let t run over [1,2]. The point y_n(t)
travels along a segment of length q^n. Its key at resolution b*_i
changes only when y_n(t) is a point of Gamma_(b*_i), and a segment of
length L contains at most 1 + L N_(b*_i) grid points. So the number of
such t is at most
1 + q^n N_(b*_i) <= 1 + q^n * 2 c q^(-b*_i) = 1 + 2 c q^(n - b*_i).
Now n >= a_(e_i) and Lemma 1 gives b*_i <= a_(e_i) + 2r - 1, so
n - b*_i >= a_(e_i) - ( a_(e_i) + 2r - 1 ) = -(2r - 1) >= -2r,
and the count is at most 1 + 2 c q^(-2r).
Collect all these numbers over the (M - 1) r pairs (i,n), add the
endpoints 1 and 2, and keep only the distinct values. These are the
critical values. Let T consist of the critical values together with the
midpoint of each pair of consecutive critical values. Then
|T| <= 2 + 2 (M - 1) r ( 1 + 2 c q^(-2r) ) <= D(r).
The set T depends only on x, on the deterministic tree, grids and
windows, and on U, which xi determines. So T is fixed before any
further table entry is revealed. Between two consecutive elements of T
no point y_n(t) crosses a grid point of its own grid Gamma_(b*_i), so
each key J_(b*_i)( y_n(t) ) is constant there, and the whole vector of
local tests is constant there. Each critical value is itself in T, so
every value the vector takes on [1,2] is taken at some element of T.
Now suppose some t in [1,2] satisfies y_n(t) not in B for all n in N.
By Lemma 6 no local test can succeed at t, that is,
Q_i( y_n(t) ) = 0 for all i < M and all n in W_(e_i).
If t is critical then t is in T. Otherwise t lies in an open gap between
consecutive critical values, and the midpoint t' of that gap belongs to
T and carries the same vector, so the same failure happens at t'. In
both cases some t' in T fails completely.
For each fixed t' the probability of a complete failure is
(1 - p/2)^((M-1)r) by Lemma 7, and since 1 - u <= exp(-u),
( 1 - p/2 )^( (M-1) r ) <= exp( - p (M - 1) r / 2 ).
A union bound over the at most D(r) elements of T gives (8.2). []
9. STEP 7. ALL CENTERS AT ONCE
------------------------------
Now choose the free parameters.
(a) BRANCHING. Choose an integer M >= 2 with
alpha := p (M - 1) / 2 > 2 log(1/q). (9.1)
Possible because the left side grows linearly in M.
(b) HEIGHT. Choose an integer d >= 1 with
( 1 - 2^(1-M) )^d < p. (9.2)
(c) GAP. The tree now has K = M + ... + M^d edges. Choose an integer
g >= 1 with
4 K c q^(g+1) < p. (9.3)
(d) WINDOW LENGTH. With M fixed, (8.1) gives D(r) = O(r), and
D(r) exp( - alpha r )
= O( r exp( - ( alpha - 2 log(1/q) ) r ) ) -> 0
by (9.1). So we may choose an integer r_0 >= 1 with
D(r) exp( - p (M - 1) r / 2 ) < p for all integers
r >= r_0. (9.4)
Build the tree, windows, grids and the random set B of Section 6 with
these M, d, g, r_0.
By (9.2) and Lemma 5, for every center x the route of x has no default
child with probability less than p. For stable x, on every atom xi on
which a default does occur, Lemma 8 applies with r = r_h >= r_0, and by
(9.4) bounds the probability of a miss at some scale t in [1,2] by p.
Summing over the atoms of F_x,
P( there is t in [1,2] with x + t q^n not in B for all n in N )
<= p + p = 2p for every stable x. (9.5)
The set N is finite, so this event is genuine: a finite Boolean
combination of events depending on finitely many bits.
REPAIR AT THE EXCEPTIONAL CENTERS. The estimate (9.5) may fail at
centers that are not stable, and the finite index set N cannot hit
every copy. Both problems are cured by opening B up a little.
For each outcome, B is a finite union of half-open cells per period.
Enlarge each selected half-open cell to an open interval around it, and
let B+ be the result. If the enlargement is small enough then B+ is
open and periodic with period 1, contains B, and
rho(B+) <= rho(B) + p (9.6)
for every outcome. (There are at most N_max cells per period; widening
each by epsilon on both sides costs at most 2 epsilon N_max, made
smaller than p.)
For a given outcome define the centers the finitely many indices in N
still fail to hit:
R = { x : there is t in [1,2] with x + t q^n not in B+ for all
n in N }.
This set is closed and periodic with period 1. On the circle R/Z it is
the image under the projection to the first coordinate of
{ (x,t) in (R/Z) x [1,2] : x + t q^n not in B+ for all n in N },
a closed subset of a compact space, because each condition "not in B+"
is open in (x,t) and there are finitely many. So R is measurable and
its density is defined.
Since B is contained in B+, a stable center in R satisfies the event in
(9.5). Integrating over one period,
E rho(R) = integral over [0,1) of P( x in R ) dx
<= 2p rho(S) + rho( R minus S )
<= 2p + p = 3p, (9.7)
by (9.5), Lemma 2 and (9.3). Also, by (9.6) and Lemma 4,
E rho(B+) <= E rho(B) + p = 2p. (9.8)
So E[ rho(B+) + rho(R) ] <= 5p, and some outcome satisfies
rho(B+) + rho(R) <= 5p. (9.9)
Fix such an outcome. By outer regularity of Lebesgue measure on the
circle, choose an open periodic set V containing R with
rho(V) <= rho(R) + p. (9.10)
Put H = B+ union V. Then H is open and periodic with period 1, and by
(9.9) and (9.10),
rho(H) <= rho(B+) + rho(R) + p <= 6p,
which is (3.1).
HITTING. Let x be any real number and t in [1,2].
- If x is not in R, the definition of R gives n in N with
x + t q^n in B+, hence in H.
- If x is in R, then x lies in V, and V is open, so x + t q^n lies in
V for all sufficiently large n, because t q^n tends to 0. Those n
need not belong to N, but (3.2) only asks for some n >= 1.
In both cases x + t q^n lies in H for some n >= 1. This proves the
Proposition. []
10. THE THEOREM
---------------
Combine the two halves.
- Section 3 shows: if the Proposition holds for every p in (0,1),
then the Theorem holds.
- Sections 4 to 9 prove the Proposition for every p in (0,1).
Hence the Theorem holds: for every q in (0,1) and every eta in (0,1)
there is a compact set E inside [0,1] with m(E) > 1 - eta containing no
copy of G_q. []
11. REMARKS AND HISTORY
-----------------------
FINITE PATTERNS ARE EASY. If F is a finite set and A is measurable with
finite positive measure, then continuity of translations in L^1 gives
m( intersection over a in F of ( A - s a ) ) -> m(A) > 0
as s -> 0. So every finite pattern lies inside some positive-measure
set. The conjecture is exactly the statement that this fails for every
infinite pattern.
WHY GEOMETRIC PROGRESSIONS ARE HARD. A known criterion (Chlebik,
Theorem 15) says a bounded infinite set {a_1 > a_2 > ...} is
nonuniversal if it has finite subsets of arbitrarily large size m with
- log( min over i < m of (a_i - a_(i+1)) / (a_1 - a_m) ) = o(m).
Geometric progressions fail this test. For a_i = q^(i-1) a_1 we have
a_(m-1) <= q^(m-2) a_1 and a_1 - a_m >= (1 - q) a_1, so the normalized
minimum gap is at most q^(m-2)/(1-q), whose negative logarithm grows
linearly in m. The known criteria say nothing, and a new argument is
needed. The tree of windows supplies it.
WHAT IS NEW HERE. Random cells, discretizing the scale at a fixed
center, and integrating over exceptional centers all appear earlier, in
work of Kolountzakis, Chlebik, and Kolountzakis-Papageorgiou. The new
ingredient is the finite routing construction together with local
control of the number of scales: the inequality (5.1), which makes the
block of an edge at most twice as long as its own window, keeps the
count D(r) proportional to r instead of to the resolution of the whole
tree.
RELATED RESULTS. Falconer and Eigen proved the conjecture for
decreasing sequences whose consecutive ratios tend to 1. Bourgain
proved a sum of three infinite sets is not universal. Humke and
Laczkovich gave covering criteria; Kolountzakis gave a probabilistic
criterion. Cruz, Lai and Pramanik built large sets of Hausdorff
dimension one avoiding certain null sequences, but those sets have
Lebesgue measure zero. Feng, Lai and Xiong showed every G_q sits inside
every positive-measure set under a bi-Lipschitz map, which is why the
restriction to affine maps matters.
A NOTE ON DEPENDENCE. The set E depends on q: the grids, the branching
number M and the window lengths are all built from q. A set avoiding
G_q and a set avoiding G_(q') need not be related, and nothing here
says one set avoids two ratios at once.
12. SYMBOLS
-----------
m Lebesgue measure on R
rho(A) measure of one period of a set of period 1
{z} fractional part of z
q fixed ratio, 0 < q < 1
G_q { q^n : n >= 1 }
p density parameter of the random construction
eta the measure the final set E may lose
c 4/(1-q)
N_b 2^ceil(log2(c q^(-b))), always a power of two
Gamma_b grid (1/N_b) Z
J_b(z) floor(N_b {z}), the cell index of z on Gamma_b
M branching number of the tree
d height of the tree
K number of edges, M + ... + M^d
g number of unused indices between two windows
r_0 base window length, chosen in (9.4)
r_h window length on an edge leaving height h
sigma_h span of all windows inside a subtree of height h
W_e window of indices attached to the edge e
a_e, b_e first and last index of W_e
b_e^* last index used anywhere in the block of e
N union of all windows
S set of stable centers
B the random periodic set
B+ an open enlargement of B
R centers the finite index set N still fails to hit
H the final periodic hitting set
E the compact set with no copy of G_q