26e9adb c4fecf1
THE GEOMETRIC CASE OF THE ERDOS SIMILARITY CONJECTURE
=====================================================
A complete and self-contained proof.
Every step is proved. Nothing is quoted without proof. 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, all scales
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. Proof of 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 what you get by translating and rescaling 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 sits inside
every set of positive measure. This note proves the conjecture for the
single set G_q: for every q and every eta > 0 there is a compact set E
inside [0,1] that fills more than 1 - eta of the interval and still
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 write
{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 prove the theorem by building its complement C = [0,1] minus E.
The set C has to be small (measure < eta) and it has to 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 TRANSLATIONS. Instead of chasing
individual 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). Summing over k
with geometrically decaying densities covers all scales and
still costs arbitrarily little measure.
(iii) RANDOM TESTS PLUS A TREE HANDLE ALL CENTERS. For one fixed
center and one fixed scale, many independent random tests make
a total miss unlikely. The hard part is that the center and the
scale both vary continuously. A finite ordered tree of tables
arranges that each group of tests looks only at the grids of
one edge and of its subtree, so the number of "grid events"
that a moving scale can trigger stays under control.
The proof of (i) is Sections 4 to 9 and is the whole content. The
reductions (ii) and (iii) are short; we do (ii) first so that the
construction has one clear target.
3. STEP 1. ONE PERIODIC SET, ALL SCALES
---------------------------------------
For a measurable set A that repeats with period 1, write
rho(A) = m( A intersect [0,1) )
for its density, i.e. 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. The set C is open, being a union of open sets,
and it is symmetric about 0. So E is closed and bounded, hence compact.
STEP B: C is small. Let A be the family of sets that repeat with
period 1 and have density rho(A). If 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] sits inside the single period
[0, 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 bound holds for -2^k A.
Apply this to A = H_k and use rho(H_k) <= 6 p_k:
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 we have 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 we have 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, then -x and -s > 0 give -x + (-s) q^n in C, and by
symmetry of C also x + s q^n in C.
So every copy of G_q meets C, hence no copy of G_q is contained in E.
This proves the theorem. []
It remains to prove 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 always 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 exponent is at most one more
than log2(c q^(-b)); the left one because the exponent is at least
log2(c q^(-b)).
FACT 2 (nesting). Each N_b is a power of two, and since c q^(-b) grows
with b, the exponents satisfy 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 nesting is the
only reason we insist on powers of two. It lets a random table indexed
by a coarse grid be read at a finer resolution without ambiguity.
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 will be chosen in Section 9. Everything in this section and the
next two is valid for every choice of them.
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 the given 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 rooted at P_1, then (P,2), then
all edges in the subtree rooted at P_2, and so on up to P_M. The
useful consequence: an edge together with the entire child subtree
below it 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 that leave a vertex of
height h receive 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: the window on an edge is at least as long as
the gap that follows it plus everything below its child 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 that 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
the window of e itself and the windows of all edges 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 then the child P_i is a leaf, so the block is just W_e
and b_e^* = b_e, giving b_e - a_e + 1 = r_1 = r_0 <= 2 r_0.
If h >= 2, preorder puts the whole child subtree immediately after W_e,
separated by exactly one gap of length g. Hence
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 the block of e has index at
most 2 r_h - 1 beyond a_e. That is a bound on resolution that depends
only on the length of W_e itself, not on the size of the whole tree.
This is the point that makes the argument work.
STABLE CENTERS. Call a real number x stable if for every window W_e
other than the very first one, writing b' for the endpoint of the
window immediately before W_e,
the interval (x, x + 2 q^(a_e)] contains no point of Gamma_(b').
Let S be the set of stable centers.
The reason for this definition: if n is in W_e and t is in [1,2] then
x + t q^n lies at distance at most 2 q^(a_e) to the right of x. If no
grid 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 window W_e that is not the first, and let b' be the
endpoint of the window immediately before it. The centers x that break
stability at this window form the union of intervals
[ gamma - 2 q^(a_e), gamma ) over all gamma in Gamma_(b').
That is a periodic set whose density is at most
2 q^(a_e) N_(b') <= 2 q^(a_e) * 2 c q^(-b') = 4 c q^(a_e - b'),
using (4.1). Since the windows are placed in preorder with exactly g
unused indices between consecutive ones, a_e = b' + g + 1, so this
density is at most 4 c q^(g+1). There are at most K windows in total,
so summing over the at most K - 1 noninitial windows gives (5.4).
Periodicity is clear because every Gamma_(b') has period 1.
Now let x be stable, let n be in W_e and 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] is contained in (x, x + 2 q^(a_e)], which
holds no point of Gamma_(b') by stability. 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; if x is a grid point,
x is the left end of its own cell and the next grid point to the right
is beyond x + t q^n by the same bound. Hence
J_(b')( x + t q^n ) = J_(b')( x ).
Every edge f preceding e has b_f <= b', so by nesting (Fact 2) the
same identity holds with b_f in place of b'. That is (5.5). []
SEPARATION. Stability freezes the keys that were 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 the interval [x, x + 2 q^(n_0)], which is at most 1/4 long. Two
points whose distance is at most 1/4 have the same distance on the
circle R/Z as in the line, so there is no wrap-around to worry about.
Compare each distance with the cell width 1/N_b.
- Distance from x to x + t q^n: this is t q^n, and t >= 1 while
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 listed above. Two points with the
same key under J_b lie in the same half-open cell, so their circular
distance is less than the cell width 1/N_b. All distances above are
larger, so all keys are distinct.
For b >= b_e the key J_b determines J_(b_e) by nesting, so distinctness
at resolution b_e 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 for each 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 gets 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 with independent entries
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 of them, 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 look at the children in order and 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
until a leaf. Let L(z) be the leaf reached. Define
B = { z : T_(L(z))( J_(b(L(z)))(z) ) = 1 }. (6.1)
So a point is in B when its route ends at a leaf whose terminal bit at
that point's cell is 1.
Every J_b has period 1, so for every outcome the set B has period 1.
Only finitely many grids appear, each is a refinement of the coarsest,
and B is a union of cells of the finest; hence 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
that 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 at that address is still Bernoulli(p). Hence
P( z in B | A ) = p.
Integrating over z in [0,1),
E rho(B) = E of the integral of P(z in B | A) over z
= integral over [0,1) of P(z in B) dz
= integral of p dz = p,
where exchanging the integral with the finite sum over outcomes is
legitimate because Omega is finite. []
7. STEP 5. THE TESTS ARE INDEPENDENT
------------------------------------
Fix a center x. Reveal, in every selector table, the single entry that
x addresses. Let
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 of
these entries are fixed before we look. Two properties hold 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 the route
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 attached to earlier edges.
The probability that all of them read 0 is 2^(-(M-1)) = 2^(1-M). The d
decisions use pairwise disjoint sets of tables, so they 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 the edges e_1,...,e_(M-1) are zero:
that is what "first default at U" means. The reader should note that
F_x reveals these entries even for children that 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 itself 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 is a certificate of membership in B. Note also that 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
that the route of x takes at P. Then the entries at x on the edges
(P,1),...,(P,a-1) are 0 and the entry at x 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 does. Hence y_n(t) also takes child a at P.
Applying this from the root downwards shows that 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. Hence y_n(t) does not take any child
below i. If in addition 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 equals 1. That is precisely 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: the A_(i,n) are independent fair bits, given xi. For a fixed i,
Lemma 3 says that 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), and none of these entries is the
one addressed by x, which xi has already fixed. Different i use
different tables. Every unrevealed selector entry is still an
independent fair bit on the atom xi.
STEP 2: condition further on A, the sigma-field of all selectors. Then
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 child indices i differ, the leaves lie in different subtrees
of U and their tables are different tables;
- if the child indices agree but the leaves differ, the tables again
differ;
- if both the child index i and the leaf L agree for two different
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) and y_(n')(t)
have different keys at resolution b_(e_i), and by nesting they
still have different keys at the finer resolution 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 immediately, 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. This
gives (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 to an edge below it, and every such edge has window endpoint
at most b*_i; the selector on e_i itself is read at resolution b_(e_i)
which is also at most b*_i. By nesting (Fact 2), Q_i(z) is therefore a
function of the single key J_(b*_i)(z). Knowing the key of z at the
finest grid of the block determines every coarser key of the block,
hence every bit that Q_i consults.
Now 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 at those t for which y_n(t) is a point of Gamma_(b*_i),
and the number of grid points in a segment of length L is at most
1 + L N_(b*_i). 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 the numbers produced this way, over the (M - 1) r pairs
(i,n); add the two endpoints 1 and 2; keep only the distinct values.
Call the result the set of critical values, and let T consist of the
critical values together with the midpoint of every two 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 is determined by xi. So T is fixed before any
further table entry is revealed.
Between two consecutive elements of T no point y_n(t) passes a grid
point of its own grid Gamma_(b*_i), so each key J_(b*_i)( y_n(t) ) is
constant there, and therefore the whole vector of local tests is
constant there. Each critical value is itself in T, so every possible
value of the vector at a point of [1,2] is attained 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 exactly 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 parameters that were left free.
(a) BRANCHING. Choose an integer M >= 2 with
alpha := p (M - 1) / 2 > 2 log(1/q). (9.1)
This is 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, the windows, the 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 the route does have a default, Lemma 8 applies with r = r_h,
which is at least 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 of indices N is finite, so this event is genuine (no
measurability worries: it is a finite Boolean combination of events
that depend 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 up B 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 resulting set. If the enlargement is small enough then B+
is open, 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, and
widening each cell by epsilon on both sides costs at most
2 epsilon N_max, which can be made smaller than p.)
For a given outcome define the set of centers that 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. Indeed, 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 },
which is a closed subset of a compact space, because each condition
"not in B+" is open in (x,t) and there are finitely many of them. So
R is measurable and its density is defined.
Since B is contained in B+, a stable center that lies in R satisfies
the event in (9.5). Therefore, 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 the expectation of rho(B+) + rho(R) is at most 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, then by the definition of R there is 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. PROOF OF 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
translate-and-rescale copy of G_q. []
11. REMARKS AND HISTORY
-----------------------
FINITE PATTERNS ARE EASY. If F is a finite set and A is measurable with
positive finite 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 sits inside some positive measure
set. The conjecture is exactly the statement that this fails for every
infinite pattern.
WHY GEOMETRIC PROGRESSIONS ARE HARD. A standard criterion (Chlebik,
Theorem 15) says that 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. So the known criteria say nothing, and a new argument is
needed. That is what the tree of windows supplies.
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 the 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, is what 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 that 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 that every G_q sits
inside every positive measure set under a bi-Lipschitz map, which is
why restricting to affine maps matters.
A NOTE ON DEPENDENCE. The set E depends on q. Indeed 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 that 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 is allowed to 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 of the tree, M + ... + M^d
g number of unused indices between two windows
r_0 base window length, chosen in (9.4)
r_h length of a window 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