The dyadic case of the Erdős similarity conjecture

Introduction

Let $m$ denote Lebesgue measure on $\mathbb{R}$. For a set $A \subseteq\mathbb{R}$, a nontrivial affine copy of $A$ is a set

The set $A$ is measure universal if every Lebesgue-measurable subset of $\mathbb{R}$ of positive measure contains such a copy. The Erdős similarity conjecture asserts that no infinite subset of $\mathbb{R}$ is measure universal; the problem was posed by Erdős in [6], Problem 4.33.7*. Every nonempty finite pattern $F$ is measure universal. Indeed, if a measurable set contains a subset $E_0$ of finite positive measure, translation continuity in $L^1$ gives $m(\bigcap_{a\in F}(E_0-sa)) \to m(E_0) > 0$ as $s \to0$. A point in this intersection supplies an affine copy of $F$. The difficulty therefore lies in keeping infinitely many points in the same positive-measure set. We consider the single sequence

Theorem 1.1. For every $\eta\in(0,1)$, there is a compact set $E_\eta\subseteq[0,1]$ with $m(E_\eta)>1-\eta$ such that

Equivalently, for every such $x,s$ there is an integer $n\ge1$ with $x+s2^{-n}\notin E_\eta$.

Thus the dyadic sequence is not measure universal. The theorem concerns one infinite pattern and all of its signed affine copies; the conjecture for arbitrary infinite sets is not addressed. Compactness and the near-full-measure conclusion follow directly from the open sets used in the construction.

Related results

Classical results concern slowly decreasing sequences. Falconer [7] and Eigen [5] proved nonuniversality for positive sequences $a_n \downarrow0$ with $a_{n+1}/a_n \to1$; see also the proof in [9], Corollary 1. Humke and Laczkovich give a finite hitting-set characterization and further relative-gap criteria [9], Theorems 1–2. Kolountzakis’s finite-gap criterion uses arbitrarily large finite subsets of a positive sequence: the minimum gaps, divided by their largest points, must have negative logarithms growing sublinearly in the cardinalities [11], Theorem 3. Chlebík gives a translation-invariant formulation normalized by the diameter [2], Theorem 15. Dyadic subsets do not satisfy either condition: for $n\ge2$ dyadic points $a_1>\cdots>a_n$, the minimum gap is at most $a_{n-1}\le2^{-(n-2)}a_1$, whereas the diameter $a_1-a_n$ is at least $a_1/2$. Either normalized minimum gap is therefore at most $2^{-(n-3)}$.

Additive structure gives another family of results. Bourgain proved that a sum of three infinite sets is nonuniversal [1], and Kolountzakis treated sums of two copies of certain sequences, including $D+D$ [11], Section 3.4. The distinction between the dyadic sequence and larger patterns is important. Mora Cuéllar, Iosevich, Kulkarni, Rojas Aravena and Yavicoli prove nonuniversality for the sum or difference of a nonconstant geometric sequence tending to zero and an arbitrary infinite set [13], Theorem 2. Their Introduction explicitly separates the single dyadic sequence from this two-fold sumset result. Avoiding a larger pattern does not imply avoidance of a subset of that pattern.

Iosevich, Kulkarni, Mora Cuéllar, Rojas Aravena and Yavicoli prove a nonuniversality criterion for sets supporting a Rajchman probability measure, that is, a probability measure whose Fourier transform tends to zero at infinity [10], Theorem 1.5. A countable set cannot support such a measure [10], Proposition 4.1, so that criterion does not apply to $D$. Their more general uniform-density criterion on the circle [10], Proposition 3.2 also fails for $D\cup\{0\}$: for every integer $k\ge1$, dilation by $2^k$ leaves its image modulo one unchanged, and that image stays a distance $1/4$ from $3/4$.

Other notions of size and other transformation classes also lead to different questions. For certain sequences tending to zero, Cruz, Lai and Pramanik obtain sets of Hausdorff dimension one avoiding affine copies of the sequence together with its limit point; the avoiding sets in their construction have Lebesgue measure zero [4], preprint, Corollary 1.2 and Proposition 4.4. In the other direction, Feng, Lai and Xiong’s bi-Lipschitz embedding theorem applies to the dyadic sequence [8], preprint, Theorem 1.1. Such nonlinear embeddings are compatible with the affine nonuniversality in Theorem 1.1. A separate earlier preprint of Cruz, Lai and Pramanik claiming the full similarity conjecture was withdrawn because of a gap in its Proposition 3.3 [3].

The construction

Our main step is to construct an open, 1-periodic set of small density that meets every $x + tD$ with $x \in\mathbb{R}$ and $t \in[1,2]$. The next section states this intermediate result precisely. Dyadic rescaling and reflection then produce a small open set meeting every signed affine copy of $D$; its complement in $[0,1]$ is the desired compact set. Periodic blocking sets and summable measure budgets also appear in [10], Lemma 3.1 and Proposition 3.2; the finite construction below supplies the required hitting property for $D$.

Random cell constructions, discretization of the dilation parameter at a fixed center, and integration over centers occur in Kolountzakis [11], Section 3.2, Chlebík [2], Section 5, and Kolountzakis–Papageorgiou [12], Section 3.1. Exceptional centers are repaired by an open cover in Kolountzakis [11], Sections 2.2 and 3.2; Chlebík also describes adding the centers themselves when the pattern contains zero [2], Section 3, final remark. We use the open-neighborhood form, since 0 is a limit point of $D$ but is not in $D$. An earlier attempt to extend the random-cell approach to the dyadic sequence is described by Solymosi [14], Section 3; that report does not claim a completed construction. The argument below implements these principles with separated index windows and a finite routing construction. All estimates needed for the proof are supplied here.

To construct the periodic set, we first assign each point of the line to one leaf of a finite ordered tree with $M$ children at each internal node and $d$ levels. Independent fair binary tables, evaluated on dyadic cells, determine the route. At each node, the first successful test chooses a child; if all tests fail, the last child is chosen by default. Each leaf carries a second table whose entries select points with a small prescribed probability $p$. This keeps the expected density small.

At a node, the default child is chosen only when all $M-1$ tested bits vanish. Although this is rare for large $M$, taking the depth $d$ sufficiently large makes a default somewhere along the center’s route likely. At the first such node, all nondefault choices have been rejected by the center. Carefully chosen dyadic translates preserve the route to that node and its earlier rejections, but consult fresh entries at their current-window resolution. Many nondefault children and many translates then supply many potential hits.

Two features make those tests useful simultaneously for every normalized scale. First, an interval of dyadic indices is assigned to each edge, in the order in which the tree is traversed. Gaps between these intervals preserve the earlier routing decisions for all but a small set of centers. Second, each interval is long enough to control every cell resolution in its child subtree. This bounds the number of different local tests as the scale varies. We expose the tables in stages, proving that the terminal entries used by these adaptively chosen routes are distinct before multiplying their failure probabilities. A finite union bound then controls all scales in $[1,2]$.

The resulting set may still miss copies centered in a small closed set. An open neighborhood of those centers repairs every such copy, since $x + t2^{-n}$ converges to $x$. This last step is what changes an estimate on exceptional centers into a statement valid at every center.

The windows and their spatial stability are constructed in Section 3. Section 4 defines the random set and proves the independent-trial estimate. Section 5 handles the continuum of normalized scales and removes the exceptional centers. Section 6 completes the signed-scale deduction of Theorem 1.1.

The periodic hitting problem

For a measurable 1-periodic set $A \subseteq\mathbb{R}$, write

for its density in one period. We will sometimes identify such a set with its image in the circle $\mathbb{T} = \mathbb{R}/\mathbb{Z}$, equipped with normalized Lebesgue measure. This identification preserves the density. Open or closed subsets of the circle lift to open or closed periodic subsets of $\mathbb{R}$.

Lemma 2.1 (Periodic hitting sets). For every $p \in(0,1)$, there exists an open $1$-periodic set $H \subseteq\mathbb{R}$ such that $\rho(H) \le6p$ and

The same set $H$ works for every center and every scale in the displayed interval. The witness $n$ may depend on both. In Section 6, we apply the lemma with a summable sequence of parameters, rescale the resulting periodic sets by powers of two, and include their reflections. This handles every nonzero real scale while keeping the total measure removed from $[0,1]$ small.

For the proof of Lemma 2.1, fix $p \in(0,1)$. We construct a random periodic set $B$ with expected density $p$, together with a finite set $\mathcal{N}$ of positive integer indices. Outside a deterministic set of centers of density less than $p$, the probability that some $t \in[1,2]$ avoids $B$ at all indices in $\mathcal{N}$ will be at most $2p$. We then enlarge $B$ to an open set, bound the expected measure of its exceptional centers, and cover those centers by a small open set. The last step uses further indices in the dyadic tail; $\mathcal{N}$ need not provide the hits at the repaired centers.

Separated index windows

We first assign a finite block of dyadic indices to every edge of an ordered tree. Gaps between the blocks will let small translations preserve earlier grid cells. Each block will also be long enough to control all resolutions needed below its child. These two properties will serve different purposes in the random construction.

The tree and the window lengths

Fix $p \in(0,1)$. Choose integers $M \ge2$ and $d \ge1$ such that

Such choices can be made in this order: the first inequality holds for large enough $M$, after which $0 < 1-2^{1-M} < 1$ permits the second choice. Let $T$ be the complete ordered tree of height $d$ in which each internal vertex has $M$ children. Its root has height $d$, its leaves have height $0$, and the children of an internal vertex $P$ are $P_1,\ldots,P_M$. Write $e=(P,i)$ for the edge from $P$ to $P_i$. The finite total number of edges is

List the edges in the following preorder: for each vertex $P$, list $(P,1)$ and all edges below $P_1$, then $(P,2)$ and all edges below $P_2$, and so on. Thus an edge together with all edges below its child forms one consecutive block in the list.

Choose an integer $g \ge1$ such that

This choice depends only on the already fixed tree. We will leave $g$ unused indices between consecutive windows.

The $M-1$ nondefault child windows of a node, each of length $r$, will together supply $(M-1)r$ random tests at a fixed scale $t \in[1,2]$. The exponential factor in the next inequality will bound the probability that all these tests fail. The preceding factor will bound the size of a finite list of scale values that represents every possible collection of local grid keys as $t$ varies. Making their product small will control all normalized scales by a finite union bound; Sections 4 and 5 prove these two bounds.

Choose an integer $r_* \ge1$ such that, for every integer $r \ge r_*$,

For completeness, the left side is at most $100Me^{-7r}$ when $r \ge1$: use (1), $1+2^{2r+2} \le5e^{2r}$, and $r \le e^r$. Hence any integer $r_* > \log(100M/p)/7$ works simultaneously for all larger $r$. The uniformity will allow us to enlarge windows as needed.

We assign a window length $r_h$ to edges whose parent has height $h$. At the same time we compute the span $\sigma_h$ of all windows in a subtree of height $h$, including the gaps between them. Starting with $\sigma_0=0$, define successively for $h=1,\ldots,d$

This is a finite bottom-up recursion: $r_h$ depends only on lengths already chosen below height $h$. In particular, the choice of $g$ did not depend on the sizes of these lengths.

Now place the actual integer windows in the edge preorder, starting at 3. An edge $e$ from height $h$ receives $W_e=\{a_e,\ldots,b_e\}$ with $b_e=a_e+r_h-1$; if $f$ immediately precedes $e$, set $a_e=b_f+g+1$. Put

where the union is over the edges of the tree. The span interpretation of (4) follows by induction. At height 1 there are $M$ windows and $M-1$ gaps. At height $h\ge2$, each child block consists of an incoming window of length $r_h$, one gap, and a subtree block of span $\sigma_{h-1}$; there are another $M-1$ gaps between these child blocks.

For an edge $e=(P,i)$, let $b_e^*$ be the largest window endpoint among $e$ and all edges below $P_i$. If $P$ has height $h=1$, this block consists only of $e$, and its span is $r_1$. If $h\ge2$, its span is $r_h+g+\sigma_{h-1}$. Therefore in both cases

In particular, (3) applies to every length $r_h$, while (5) bounds a whole child block in terms of its incoming window. All edges, including those with child index $M$, receive windows under this construction.

The padding bound has a specific purpose: the range of window indices from $a_e$ through $b_e^*$ in a child block is controlled by the length of its incoming window. The gaps have a different role, established next: for most centers, translations indexed by a later window preserve the earlier cells used in the routing decisions. These are the two deterministic inputs to the routing and scale-counting arguments.

Earlier grid cells remain unchanged

For every nonnegative integer $b$, define the periodic cell key

Its boundaries on the real line form the lattice $\Gamma_b=2^{-(b+2)}\mathbb{Z}$. In particular, every integer is a boundary. Cells are half-open on the right, so a boundary belongs to the cell starting there. The grids are nested: for $B\ge b$,

This follows by writing $2^{B+2}\{z\}=J_B(z)+\varepsilon$ with $0\le\varepsilon<1$ and dividing by the integer $2^{B-b}$.

We seek centers for which translations indexed by one window preserve every earlier grid key. For a noninitial window $W_e$, let $b'$ be the endpoint of the immediately preceding window, and put $\delta_e=2^{1-a_e}$. Call $x$ stable if, for every such window,

Let $G$ denote the set of stable centers. The intervals in (8) are taken on the real line, so crossings of an integer are included without a separate convention on the circle.

Lemma 3.1. The set $G$ is measurable and $1$-periodic, and $\rho(G^{c})<p$. For every $x\in G$, every window $W_e$, every $n\in W_e$, every $t\in[1,2]$, and every window $W_f$ earlier than $W_e$,

These assertions include centers lying on grid boundaries.

Proof. For a fixed noninitial window, the centers violating (8) are exactly

because $\beta\in(x,x+\delta_e]$ if and only if $\beta-\delta_e\le x<\beta$. This is a measurable periodic set. Since $a_e=b'+g+1$,

Thus these intervals have disjoint interiors modulo one. There are $2^{b'+2}$ of them per period, each of length $\delta_e$, and hence $\rho(E_e)=2^{2-g}$. The complement of $G$ is the union of these sets over the $K-1$ noninitial windows. Consequently

This also proves measurability and periodicity of $G$.

Now fix the data in (9). If $W_e$ is the first window, there is no earlier $W_f$. Otherwise $0<t2^{-n}\le2^{1-a_e}=\delta_e$, so stability implies that the interval $(x,x+t2^{-n}]$ contains no boundary of $\Gamma_{b'}$. Both endpoints therefore have the same $J_{b'}$ key. This remains true when $x$ itself is a boundary, since it belongs to the cell on its right; landing on a boundary at a positive displacement has been excluded. An integer cannot lie in this interval either, so passing to periodic keys introduces no additional case. Finally, every earlier window satisfies $b_f\le b'$, and (7) gives (9).

The tree, all windows, and $G$ are now fixed before any random choices. The key agreement concerns earlier windows only. This is the property that will preserve the required earlier decisions while allowing tests at the current window’s finer resolution.

Random routing and independent tests

We now use the windows from the preceding section to construct a random periodic set $B$ of expected density $p$. Selectors send each spatial point to one leaf of the tree, where an independent terminal entry decides membership in $B$. For a stable center, the first default choice on its path will provide several child windows in which to test nearby points.

The tables and the selected set

For each edge $e=(P,i)$ with $i<M$, let

be a random table whose entries are independent Bernoulli variables with parameter $1/2$. There is no selector table for the default edge $(P,M)$. For a leaf $L$, let $b(L)$ be the endpoint of the window assigned to its unique incoming edge, and let

be a random table whose entries are independent Bernoulli variables with parameter $p$. All entries of all selector and terminal tables are mutually independent. The tree and every table are finite, so these variables define a finite product probability space $\Omega$. We write $\mathbb{P}$ and $\mathbb{E}$ for its probability and expectation.

Given the tables and a point $z\in\mathbb{R}$, start at the root. At an internal node $P$, choose the first child $P_i$, $i<M$, for which

If all $M-1$ values are zero, choose the default child $P_M$. Continue until reaching a leaf, denoted by $L(z)$, and define

The table rules use only periodic keys. Since all grids in the construction are nested, membership in $B$ is constant on each cell of the finest grid used. Thus every realization of $B$ is a 1-periodic measurable set, consisting of finitely many half-open cells per period.

Let $\mathcal{S}$ be the sigma-field generated by every entry of every selector table. For fixed $z$, conditioning on $\mathcal{S}$ fixes $L(z)$ and the key of its terminal entry. That entry still has probability $p$ of being one, since terminal tables are independent of all selectors. Hence

Integrating over one period and interchanging the integral with the finite weighted sum over $\Omega$ gives

Conditioning at a center

For a fixed center $x \in\mathbb{R}$, expose one entry from every selector table, including those in subtrees not visited by its path. The resulting sigma-field is

An atom $\xi$ of $\mathcal{F}_{x}$ means the event specifying all these exposed values; we write $\mathbb{P}(\cdot\mid\xi)$ for conditioning on that event. Every such atom has positive probability. The exposed addresses $(e,J_{b_{e}}(x))$ are deterministic once $x$ is fixed, with the table name $e$ included in the address. Consequently, on each atom, all remaining selector entries retain their independent fair law, and all terminal entries retain their independent Bernoulli-$p$ law.

The exposed values determine the full path of $x$. When that path chooses a default child, let $U$ denote its first internal node at which this happens. Thus the existence and identity of $U$ are determined by $\mathcal{F}_{x}$. The next estimate concerns the original product law, before an atom of $\mathcal{F}_{x}$ is fixed.

Lemma 4.1 (A default choice on the center path). For every fixed $x \in\mathbb{R}$,

Proof. At any internal node, the default child is chosen exactly when its $M-1$ selector entries at $x$ are all zero. This has probability $2^{-(M-1)} = 2^{1-M}$.

To compute the probability along the path, reveal the entries at an internal node only when the path first reaches it. The decisions leading to that node use tables at its strict ancestors. Its own tables are distinct from all of those tables and have not yet been revealed, so their entries at $x$ remain independent fair bits, conditional on the preceding path history. At each of the $d$ internal-node decisions, the conditional probability of a non-default choice is therefore $1-2^{1-M}$. Iterating this conditional probability gives $\left(1-2^{1-M}\right)^{d}$. The strict inequality is the choice of $d$ in (1). $\square$

Routing trials through the first default

Fix henceforth a stable center $x \in G$, and condition on an atom $\xi$ of $\mathcal{F}_{x}$ for which $U$ exists. The node $U$ is fixed under this conditioning. Let $h$ be its height, and write

At $U$, all the exposed non-default selector values are zero. For $i < M$ and $z \in\mathbb{R}$, let $L_i(z)$ be the leaf obtained by applying the same path rule starting at the child $U_i$. If $U_i$ is already a leaf, set $L_i(z) = U_i$. Define the local predicate

The function $Q_i$ takes values in $\{0,1\}$ and consults only the selector on $e_i$ and tables in the subtree rooted at $U_i$. It provides a sufficient condition for membership in $B$ at the points indexed by $W_{e_i}$.

Lemma 4.2 (Preservation of the route). For every outcome in $\Xi$, every $i < M$, every $n \in W_{e_i}$, and every $t \in[1,2]$, the actual root path of $y_n(t)$ reaches $U$ and rejects children $1,\ldots,i-1$ there. In particular,

Proof. Consider a strict ancestor $P$ of $U$, and let $P_a$ be its child on the path of $x$ to $U$. Since $U$ is the first default node, $a < M$. The decision at $P$ uses precisely the zero values of the selectors $1,\ldots,a-1$ and the value one of selector $a$. Each of the edges $(P,j)$, $j \le a$, precedes every edge in the subtree of $P_a$ in the prescribed preorder. Their windows therefore precede $W_{e_i}$. By the stable-key identity (9), each of these selector evaluations at $y_n(t)$ agrees with its evaluation at $x$. Induction from the root along the ancestor chain shows that $y_n(t)$ makes the same choices and reaches $U$. Later sibling selectors at an ancestor are not needed to make its choice.

For every $j < i$, the edge $(U,j)$ also precedes $e_i$. Its selector value at $x$ is zero, because $x$ takes the default child at $U$. Another application of (9) makes the corresponding value at $y_n(t)$ zero. Thus the actual path rejects children $1,\ldots,i-1$ at $U$.

If $Q_i(y_n(t)) = 1$, the selector on $e_i$ is one, so the actual path chooses child $i$ at $U$. Its continuation is exactly the rule defining $L_i(y_n(t))$, and the terminal entry in (14) is one. The membership rule (11) now gives $y_n(t) \in B$. Figure 2 records this common-prefix and branching argument. All equalities used here hold for every completion of the unexposed tables and every $t \in[1,2]$, as required.

Independent terminal tests

We now estimate the probability that all the local tests fail at one fixed scale. The selected leaves may depend on the selectors. To keep that dependence explicit, we first expose all selectors, identify the terminal entries being read, and then average over the selectors.

Lemma 4.3 (The fixed-scale estimate). Fix a stable center $x$ and an atom $\xi$ of the center-exposure sigma-field $\mathcal{F}_x$ in (13), on which the first default node $U$ exists. Let $h$ be its height, put $r=r_h$, and use the local predicates $Q_i$ for $e_i=(U,i)$, $1\le i<M$, defined in (14), with $y_n(t)=x+t2^{-n}$. For every fixed $t\in[1,2]$,

Proof. On the fixed atom $\xi$, the node $U$, the windows $W_{e_i}$, and the set of pairs

are fixed. Its cardinality is $(M-1)r$. For these pairs define

We first check that these are distinct selector entries, none of which was exposed at $x$. Fix $i$, and abbreviate $a=a_{e_i}$ and $b=b_{e_i}$. For $n<n'$ in this window,

Also $y_n(t)-x=t2^{-n}\ge2^{-b}$. All these points lie in $[x,x+2^{1-a}]$, an interval of length at most $1/4$, since $a\ge3$. Thus the circular distance between any two of them equals their ordinary distance and is at least $2^{-b}$. Two points in the same half-open $J_b$-cell have circular distance less than $2^{-(b+2)}$. Consequently the keys of $x$ and all $y_n(t)$, $n\in W_{e_i}$, are pairwise distinct. This argument also covers a crossing of an integer and points on cell boundaries.

For different $i$, the selector tables themselves differ. The variables $A_{i,n}$ therefore read distinct coordinates outside the entire exposed coordinate set defining $\mathcal{F}_x$. Conditional on $\xi$, they remain independent fair bits.

Next condition on the sigma-algebra $\mathcal{S}$ of all selectors. For each pair, its selected local leaf

and its terminal address

are now fixed. We claim that these addresses are distinct for all pairs in $\mathcal{I}$. If the child indices differ, the leaves lie in disjoint child subtrees of $U$, so their terminal tables differ. If the child indices agree but the leaves differ, their tables again differ. It remains to consider two different indices $n,n'$ that select the same leaf $L$ below one child $U_i$.

For every leaf below $U_i$, its terminal resolution satisfies $b(L)\ge b_{e_i}$. If $U_i$ is a leaf, then $b(L)=b_{e_i}$. Otherwise the last edge into $L$ occurs after $e_i$ in the preorder, so its window endpoint is larger. By the nested-key identity (7), different keys at resolution $b_{e_i}$ remain different at resolution $b(L)$, including at grid boundaries. The preceding separation of $y_n(t)$ and $y_{n'}(t)$ proves $\kappa_{i,n}\ne\kappa_{i,n'}$. This proves the claim, even for pairs with $A_{i,n}=0$.

The terminal tables are independent of $S$. For each realization of all selectors, the addresses just identified are fixed distinct coordinates of those tables. The corresponding terminal bits

therefore have the product Bernoulli $p$ law conditional on $S$. Since $Q_i(y_n(t))=A_{i,n}V_{i,n}$, only the pairs with $A_{i,n}=1$ require a terminal bit to vanish. On $\xi$ we obtain

The empty-success case has exponent zero and probability one.

Finally, $\mathcal{F}_x\subset S$, so conditional expectation and the independent fair law of the $A_{i,n}$ on $\xi$ give

The estimate applies separately to each scale fixed on the exposure atom. In the next step, the grid geometry will supply finitely many such scales, allowing a union bound over all $t\in[1,2]$.

All normalized scales and all centers

The preceding estimate concerns a fixed scale. To control every $t\in[1,2]$, we track the local predicates $Q_i$ on the grids of their own child subtrees. The padding of each window bounds the number of changes in these predicates as the scale varies. The use of deterministic grid crossings to discretize scales at a fixed center follows the same principle as [11], Section 3.2, [2], Section 5, and [12], Section 3.1. Here the crossings must be counted within each child subtree, so that the bound remains compatible with the conditional trial estimate.

Lemma 5.1. Fix a stable center $x$ and an atom $\xi$ of the full center exposure $\mathcal{F}_x$ in (12) on which the first-default node $U$ exists. Let $h$ be its height, put $r=r_h$, and write

There is a finite set $\mathcal{R}(x,U)\subset[1,2]$, depending only on $x$, $U$ and the deterministic windows, with

such that the following holds for the local predicates $Q_i$ in (13), for every realization of the tables consistent with $\xi$. For each $t\in[1,2]$, some $t'\in\mathcal{R}(x,U)$ satisfies

Proof. For fixed tables, $Q_i(z)$ is determined by $J_{b_i^*}(z)$. Indeed, its initial selector has resolution $b_{e_i}\le b_i^*$, and all selectors used to route from $U_i$ lie in that child subtree. The incoming edge of every possible terminal leaf also has endpoint at most $b_i^*$. This includes the case that $U_i$ itself is a leaf, whose terminal resolution is $b_{e_i}$, as well as leaves reached through default children. Since the grids are nested, the key $J_{b_i^*}(z)$ determines every address needed for this local predicate.

For each tested pair $(i,n)$, let

These are precisely the scales at which $x+t2^{-n}$ meets a boundary of the periodic grid $J_{b_i^*}$. The full real-line lattice in this definition also includes every passage through an integer, where the periodic key returns to its first cell.

As $t$ ranges over $[1,2]$, the point traverses a closed interval of length $2^{-n}$. Counting lattice points in that interval gives

The extra one allows both endpoints to be lattice points. The subtree span bound (5) gives $b_i^*-a_{e_i}+1\leq2r$; since $n\geq a_{e_i}$,

Take the union of these sets and the two endpoints:

List its distinct elements as $d_1=1<\cdots<d_L=2$, and set

There are $(M-1)r$ tested pairs, so

On each open interval $(d_j,d_{j+1})$, every relevant grid key is constant, hence so is every tested local predicate. Its midpoint therefore represents the entire interval. Each breakpoint and each endpoint is included separately and represents its own value. This proves (17), including the values at the boundaries of the half-open cells.

The representatives use only the local predicates. A point for which $Q_i$ vanishes may take its actual route through another subtree with a finer grid. That route does not enter the count: we need only the implication from a successful local predicate to a hit of $B$.

Proposition 5.2. For every fixed stable center $x$,

Proof. Condition first on an atom $\xi$ of $\mathcal{F}_x$ in (12) on which the first-default node $U$ exists, and retain the notation of Lemma 5.1. The node $U$ and the entire set $\mathcal{R}(x,U)$ are fixed on this atom, before any remaining selector or terminal label is revealed. Thus Lemma 4.3 applies separately to every $t'\in\mathcal{R}(x,U)$ and gives

If some scale $t$ misses $B$ at every index in $\mathcal{N}$, then Lemma 4.2 implies that all its tested local predicates vanish. By Lemma 5.1, they all vanish at one of the representative scales as well. The conditional union bound and (3) therefore give

No independence between different representative scales is required.

This bound holds on every center-exposure atom that has a first default, since every corresponding window length is at least $r_*$. Averaging over those atoms introduces no factor for the number of possible nodes. By Lemma 4.1, the remaining event, on which the center’s path never chooses the default child, has probability less than $p$. Bounding failure by one on that event yields (19).

Removing exceptional centers

The pointwise probability bound will control the measure of the centers at which some normalized scale is missed. We first enlarge the random set to an open set, so that those exceptional centers form a closed set. A small open neighborhood of that closed set will then provide hits from the dyadic tail. This follows the open-cover completion of Kolountzakis [11], Sections 2.2 and 3.2; we give the closedness, measure and tail arguments explicitly.

Completion of the proof of Lemma 2.1. The probability space $\Omega$ of all table entries is finite. For each outcome $\omega$, the set $B_\omega$ is a union of cells from one finite dyadic grid per period: its finest key determines every table lookup. Regard a periodic set as a subset of the circle $\mathbb{T}=\mathbb{R}/\mathbb{Z}$, with normalized Lebesgue measure equal to the density of its periodic lift. Taking the closures of the selected cells adds only finitely many endpoints. Enlarging these closed arcs by sufficiently small open circular neighborhoods therefore gives an open periodic set $B_\omega^+\supseteq B_\omega$ with

For example, if the grid has $Q$ cells, enlargement by circular distance $p/(4Q)$ adds at most $p/2$ to the measure of their union. For the empty set use the empty enlargement. Since there are only finitely many outcomes, these choices introduce no measurable-selection issue. Equation (12) gives

Define the exceptional-center set

This set is periodic and closed. To prove closedness without any endpoint convention on a fundamental interval, let $\pi:\mathbb{R}\to\mathbb{T}$ be the quotient map and let $B_{\omega,\mathbb{T}}^+\subset\mathbb{T}$ denote the open image of $B_\omega^+$. Each map

is continuous. The conditions that all these images avoid $B_{\omega,\mathbb{T}}^+$, for $n\in\mathcal{N}$, consequently define a closed subset of the compact space $\mathbb{T}\times[1,2]$. Its projection to $\mathbb{T}$ is compact and hence closed. Its inverse image under $\pi$ is exactly $R_\omega$.

In particular, each indicator $\mathbf{1}_{R_\omega}(x)$ is Borel measurable in $x$. Since $\Omega$ is finite, it is also jointly measurable in $(\omega,x)$. For every stable center $x \in G$, the inclusion $B_\omega\subseteq B_\omega^+$ and Proposition [5] give

At the other centers the probability is at most $1$. Interchanging a finite sum and an integral, and using Lemma [3], we obtain

Thus (21) and (23) imply

Choose one outcome whose summed density is at most this bound, and write its sets as $B^+$ and $R$. We have

It remains to cover every center in $R$. Its image $R_{\mathbb{T}} = \pi(R)$ is closed in the circle. If it is empty, put $V = \varnothing$. Otherwise, for $\varepsilon> 0$, its open metric neighborhoods

decrease to $R_{\mathbb{T}}$ as $\varepsilon\downarrow0$. Continuity of finite measure from above lets us choose $\varepsilon> 0$ so that the open periodic lift $V = \pi^{-1}(V_\varepsilon^{\mathbb{T}})$ satisfies

Set $H = B^+ \cup V$. It is open and periodic, and (24) gives

If $x \notin R$, negating (22) shows that for every $t \in[1,2]$ some $n \in\mathbb{N}$ satisfies $x + t2^{-n} \in B^+ \subseteq H$. If $x \in R$, choose an integer $n_0 \ge1$ with $2^{1-n_0} < \varepsilon$. For every $t \in[1,2]$ and every $n \ge n_0$, the circle distance satisfies

Hence $x+t2^{-n} \in V \subseteq H$. These indices are taken from the full dyadic tail. The two cases establish the required hit for every real $x$ and every $t \in[1,2]$, completing the lemma. □

The compact avoiding set

The periodic hitting sets cover scales in $[1,2]$. We now combine their dyadic dilations, with summable densities, to cover every nonzero scale while removing arbitrarily little measure from $[0,1]$.

Proof of Theorem 1.1. Fix $\eta\in(0,1)$ and put

Each $p_j$ belongs to $(0,1)$. By Lemma 2.1, choose an open 1-periodic set $H_j \subset\mathbb{R}$ with $\rho(H_j) \le6p_j$ such that

All these sets are fixed before any center or scale is chosen. Define

Dilations and reflections preserve openness, so $C$ is open. Its paired definition gives $-C=C$. Thus $E$ is a closed subset of $[0,1]$, and is compact.

For each $j$, periodicity and a change of variables give the exact identities

Indeed, each interval on the right contains exactly $2^j$ unit periods; their endpoints do not affect Lebesgue measure. Countable subadditivity therefore yields

Consequently

It remains to show that every signed affine copy of $D$ meets $C$. Let $x\in\mathbb{R}$ and first suppose that $s>0$. Choose an integer $k$ with

and set $j=\max\{1,k\}$. Apply (24) to the center $2^j x$ and the normalized scale $t$. There is an integer $n\ge1$ such that

Multiplying by $2^{-j}$ gives

The index $N=n+j-k$ is an integer and satisfies $N\ge n\ge1$, because $j\ge k$. Hence this point belongs to the original copy $x+sD$. The argument applies to every real center and every positive scale, including arbitrarily small scales, for which larger values of $j$ are available.

If $s<0$, apply the positive-scale conclusion to the center $-x$ and scale $-s$. For some integer $N\ge1$,

Since $-C=C$, it follows that $x+s2^{-N}\in C$ as well. In either case, the copy $x+sD$ has a point in $C$, which is disjoint from $E$. Thus the fixed compact set $E$ excludes every such copy, as required. ∎