Introduction
In 1920, Steinhaus [24 ] showed that if A A A is a finite subset of R \mathbb{R} R , then every measurable set E ⊂ R E \subset\mathbb{R} E ⊂ R of positive Lebesgue measure contains a nontrivial affine copy of A A A . In 1974, Erdős [10 ] conjectured that this finite-pattern phenomenon breaks down completely for infinite sets. This is known as the Erdős similarity conjecture ; see also Erdős Problem #120 [2 ] .
Conjecture 1.1 (Erdős similarity conjecture). If A A A is an infinite subset of R \mathbb{R} R , then there is a set E ⊂ [ 0 , 1 ] E \subset[0,1] E ⊂ [ 0 , 1 ] with ∣ E ∣ > 0 |E| > 0 ∣ E ∣ > 0 such that E E E does not contain any nontrivial affine copy of A A A .
To study Conjecture 1.1, it suffices to consider sequences of positive real numbers decreasing to 0 [25 ] . Although the conjecture remains widely open, several classes of sequences are known to satisfy the conjecture. Eigen [9 ] and Falconer [11 ] independently proved the conjecture for sublacunary sequences, that is, sequences A = ( a n ) n = 1 ∞ A = (a_n)_{n=1}^{\infty} A = ( a n ) n = 1 ∞ satisfying a n + 1 / a n → 1 a_{n+1}/a_n \to1 a n + 1 / a n → 1 . Humke and Laczkovich [16 ] showed that the condition lim n → ∞ a n + 1 / a n = 1 \lim_{n\to\infty} a_{n+1}/a_n = 1 lim n → ∞ a n + 1 / a n = 1 can be replaced with lim sup n → ∞ a n + 1 / a n = 1 \limsup_{n\to\infty} a_{n+1}/a_n = 1 lim sup n → ∞ a n + 1 / a n = 1 , and a m − a m + 1 ≤ a n − a n + 1 a_m-a_{m+1} \le a_n-a_{n+1} a m − a m + 1 ≤ a n − a n + 1 for all m > n m>n m > n . Kolountzakis [20 ] proved a more flexible criterion in terms of large finite subsets with large normalized gaps. Bourgain [3 ] proved the conjecture for sets with special additive structure, for instance sums of three infinite sets. We refer to [25 , 19 ] for surveys of the Erdős similarity problem. Very recently, OpenAI [23 ] claimed a proof of the conjecture for geometric progressions. See [17 , 18 ] for expositions and extensions. Nevertheless, The Erdős similarity conjecture remains open in general.
We study a variant of the Erdős similarity problem in which affine copies are replaced by polynomial copies, and more generally by analytic copies. We now explain the motivation for this variant.
The Erdős similarity problem is naturally connected with finite-pattern recurrence phenomena. As Bourgain [3 ] observed, Erdős’s question was likely motivated by the finite-pattern phenomena underlying Szemerédi’s theorem [26 ] and its extension by Furstenberg and Katznelson [14 ] . Szemerédi’s theorem guarantees arbitrarily long arithmetic progressions in every set of integers of positive upper density, while Steinhaus’ theorem implies that every measurable subset of R \mathbb{R} R of positive measure contains a nontrivial affine copy of every finite configuration. The Erdős similarity problem asks whether this universality breaks down for infinite configurations. The Erdős similarity problem in the large is particularly reminiscent of Szemerédi’s theorem, as it asks whether a uniform largeness condition forces the presence of infinite patterns [4 , 5 , 21 , 15 ] . It was recently resolved by Yip [28 ] , who proved that for every unbounded set A ⊂ R A \subset\mathbb{R} A ⊂ R and every 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 , there exists a closed set S ⊂ R S \subset\mathbb{R} S ⊂ R having measure at least 1 − ε 1-\varepsilon 1 − ε in every unit interval and containing no nontrivial affine copy of A A A .
The polynomial version of the problem is motivated by the corresponding polynomial recurrence theory. A real-line polynomial Szemerédi theorem of Bergelson and Leibman [1 Theorem B”] says that if P ∈ R [ x ] P \in\mathbb{R}[x] P ∈ R [ x ] satisfies P ( 0 ) = 0 P(0)=0 P ( 0 ) = 0 , if a 1 , … , a k ∈ R a_1,\ldots,a_k \in\mathbb{R} a 1 , … , a k ∈ R , and if E ⊂ R E \subset\mathbb{R} E ⊂ R has positive upper Banach density, then there are a positive integer n n n and a point x ∈ R x \in\mathbb{R} x ∈ R such that
x + P ( n a j ) ∈ E ( 1 ≤ j ≤ k ) . x + P(na_j) \in E \qquad(1 \leq j \leq k). x + P ( n a j ) ∈ E ( 1 ≤ j ≤ k ) .
Equivalently, with
Q ( t ) = x + P ( n t ) , Q(t) = x + P(nt), Q ( t ) = x + P ( n t ) ,
the set E E E contains the finite polynomial image
{ Q ( a 1 ) , … , Q ( a k ) } . \{Q(a_1),\ldots,Q(a_k)\}. { Q ( a 1 ) , … , Q ( a k )} .
Thus finite polynomial copies of arbitrary finite configurations are unavoidable in positive-density sets. We ask whether infinite polynomial copies can nevertheless be avoided by a set of positive measure.
This perspective is part of a broader circle of continuous analogues of classical results from additive combinatorics. For example, polynomial Roth-type theorems on sets of fractional dimension have been studied in [7 , 13 ] , and continuous Furstenberg–Sárközy-type problems have been studied in [8 , 22 ] . A more familiar polynomial Szemerédi theorem of Bergelson and Leibman [1 Theorem B’] concerns configurations u + p i ( n ) u+p_i(n) u + p i ( n ) generated by several polynomials p 1 , … , p k p_1,\ldots,p_k p 1 , … , p k . By the Lebesgue density theorem, this also has a continuous Steinhaus-type analogue; see for instance [7 p. 6973] .
It is therefore natural to ask for an Erdős similarity analogue in which affine maps are replaced by polynomial maps, and more generally by analytic maps. This direction is also motivated by the bi-Lipschitz variant studied recently by Feng, Lai, and Xiong [12 ] : since every nontrivial affine map is bi-Lipschitz, their problem already contains the classical affine setting and asks for avoidance under a larger class of transformations.
More precisely, we study the following polynomial and analytic analogue of the Erdős similarity problem.
Question 1.2 (Polynomial and analytic Erdős similarity problem). Let ( a n ) n = 1 ∞ (a_n)_{n=1}^{\infty} ( a n ) n = 1 ∞ be a decreasing sequence of positive numbers with a n → 0 a_n \to0 a n → 0 . Does there exist a measurable set E ⊂ [ 0 , 1 ] E \subset[0,1] E ⊂ [ 0 , 1 ] with ∣ E ∣ > 0 |E| > 0 ∣ E ∣ > 0 such that
{ P ( a n ) : n ∈ N } ⊄ E \{P(a_n): n \in\mathbb{N}\} \not\subset E { P ( a n ) : n ∈ N } ⊂ E for every nonconstant polynomial P ∈ R [ x ] P \in\mathbb{R}[x] P ∈ R [ x ] ? Can one choose E E E to avoid the images of ( a n ) (a_n) ( a n ) under every nonconstant real-analytic function defined near 0 0 0 ?
We prove positive results for Question 1.2 by three complementary methods. The first is an explicit Cantor-type construction . It is deterministic, works particularly well for sequences satisfying a global gap-comparability condition, and gives a strong tail-avoidance conclusion with a set of measure arbitrarily close to one.
We first state the result obtained by the explicit construction.
Theorem 1.3. Let ( a n ) n = 1 ∞ (a_n)_{n=1}^{\infty} ( a n ) n = 1 ∞ be a decreasing sequence of positive numbers such that a n → 0 a_n \to0 a n → 0 ,
lim sup n → ∞ a n + 1 a n = 1 , \limsup_{n\to\infty} \frac{a_{n+1}}{a_n}=1, n → ∞ lim sup a n a n + 1 = 1 , and there is a constant C > 0 C > 0 C > 0 such that
a m − a m + 1 ≤ C ( a n − a n + 1 ) ( m > n ) . a_m-a_{m+1} \le C(a_n-a_{n+1}) \qquad(m>n). a m − a m + 1 ≤ C ( a n − a n + 1 ) ( m > n ) . Then for each ϵ > 0 \epsilon> 0 ϵ > 0 , there is a set E ⊂ [ 0 , 1 ] E \subset[0,1] E ⊂ [ 0 , 1 ] with ∣ E ∣ ≥ 1 − ϵ |E| \ge1-\epsilon ∣ E ∣ ≥ 1 − ϵ such that E E E does not contain
{ f ( a n ) : n ≥ N } \{f(a_n):n\ge N\} { f ( a n ) : n ≥ N } for any nonconstant function f : R → R f:\mathbb{R}\to\mathbb{R} f : R → R analytic at 0 0 0 and any positive integer N N N .
The second is a random Cantor-type construction , in the spirit of Kolountzakis [20 ] . It is less explicit but more flexible: it applies under a local finite-block hypothesis, treats polynomial maps by counting finitely many interval patterns, and treats analytic maps by adding a Taylor-truncation estimate. The following theorem is a strengthening of a result of Kolountzakis [20 ] , Theorem 3.
Theorem 1.4. Let
A = ( a n ) n = 1 ∞ , a 1 > a 2 > ⋯ > 0 , a n → 0 , A=(a_n)_{n=1}^{\infty}, \qquad a_1>a_2>\cdots>0,\qquad a_n\to0, A = ( a n ) n = 1 ∞ , a 1 > a 2 > ⋯ > 0 , a n → 0 , and identify A A A with its underlying set. Suppose that there are finite subsets
B ν = { b ν , 1 > ⋯ > b ν , N ν > 0 } ⊂ A B_\nu=\{b_{\nu,1}>\cdots>b_{\nu,N_\nu}>0\}\subset A B ν = { b ν , 1 > ⋯ > b ν , N ν > 0 } ⊂ A such that
N ν → ∞ , b ν , 1 → 0 , N_\nu\to\infty,\qquad b_{\nu,1}\to0, N ν → ∞ , b ν , 1 → 0 , and, writing
Δ ν = min 1 ≤ i < N ν b ν , i − b ν , i + 1 b ν , 1 , \Delta_\nu=\min_{1\le i<N_\nu}\frac{b_{\nu,i}-b_{\nu,i+1}}{b_{\nu,1}}, Δ ν = 1 ≤ i < N ν min b ν , 1 b ν , i − b ν , i + 1 , one has
− log Δ ν = o ( N ν ) . -\log\Delta_\nu=o(N_\nu). − log Δ ν = o ( N ν ) . Then there exists a measurable set E ⊂ [ 0 , 1 ] E\subset[0,1] E ⊂ [ 0 , 1 ] of positive Lebesgue measure such that
P ( A ) ⊄ E P(A)\not\subset E P ( A ) ⊂ E for every nonconstant real polynomial P P P .
Moreover, if the sets B ν B_\nu B ν may be chosen so that
( 1 + ∣ log Δ ν ∣ log ( 1 / b ν , 1 ) ) ( log N ν + ∣ log Δ ν ∣ ) = o ( N ν ) , (1) \left(1+\frac{|\log\Delta_\nu|}{\log(1/b_{\nu,1})}\right)(\log N_\nu+|\log\Delta_\nu|)=o(N_\nu), \tag*{(1)} ( 1 + log ( 1/ b ν , 1 ) ∣ log Δ ν ∣ ) ( log N ν + ∣ log Δ ν ∣ ) = o ( N ν ) , (1) then E E E may be chosen so that
f ( A ) ⊄ E f(A)\not\subset E f ( A ) ⊂ E for every nonconstant real-analytic function f f f defined in a neighbourhood of 0 0 0 .
Remark 1.5. This formulation is equivalent, for the polynomial conclusion, to Kolountzakis’s large-gap hypothesis that A A A contains arbitrarily large finite subsets B B B with − log Δ ( B ) = o ( ∣ B ∣ ) -\log\Delta(B)=o(|B|) − log Δ ( B ) = o ( ∣ B ∣ ) . Indeed, since A A A is a sequence tending to 0 0 0 , one may pass to terminal portions of such good blocks to ensure that their largest elements tend to 0 0 0 , without worsening the normalized gap condition.
The following consequence gives convenient hypotheses which imply the analytic part of the random Cantor theorem. In particular, it contains the sublacunary and gap-comparable classes mentioned above.
Corollary 1.6. Let
A = ( a n ) n = 1 ∞ , a 1 > a 2 > ⋯ > 0 , a n → 0 , A=(a_n)_{n=1}^{\infty}, \qquad a_1>a_2>\cdots>0, \qquad a_n\to0, A = ( a n ) n = 1 ∞ , a 1 > a 2 > ⋯ > 0 , a n → 0 , and identify the sequence with its underlying set. Assume that at least one of the following conditions holds.
For each n n n , let ℓ ( n ) \ell(n) ℓ ( n ) be the smallest integer such that
a ℓ ( n ) ≤ a n 4 , a_{\ell(n)}\le\frac{a_n}{4}, a ℓ ( n ) ≤ 4 a n , and put T ( n ) = { n , n + 1 , … , ℓ ( n ) } T(n)=\{n,n+1,\ldots,\ell(n)\} T ( n ) = { n , n + 1 , … , ℓ ( n )} . Then
lim inf n → ∞ max m ∈ T ( n ) ( a m − a m + 1 ) a n = 0. \liminf_{n\to\infty}\frac{\max_{m\in T(n)}(a_m-a_{m+1})}{a_n}=0. n → ∞ lim inf a n max m ∈ T ( n ) ( a m − a m + 1 ) = 0. 2.
a n + 1 a n → 1. \frac{a_{n+1}}{a_n}\to1. a n a n + 1 → 1. 3.
lim sup n → ∞ a n + 1 a n = 1 , \limsup_{n\to\infty}\frac{a_{n+1}}{a_n}=1, n → ∞ lim sup a n a n + 1 = 1 , and there exists C > 0 C>0 C > 0 such that
a m − a m + 1 ≤ C ( a n − a n + 1 ) ( m > n ) . a_m-a_{m+1}\le C(a_n-a_{n+1}) \qquad(m>n). a m − a m + 1 ≤ C ( a n − a n + 1 ) ( m > n ) . Then there exists a measurable set E ⊂ [ 0 , 1 ] E\subset[0,1] E ⊂ [ 0 , 1 ] of positive Lebesgue measure such that
f ( A ) ⊄ E f(A)\not\subset E f ( A ) ⊂ E for every nonconstant real-analytic function f f f defined in a neighbourhood of 0 0 0 .
We now discuss another corollary to this theorem; this crucially uses an estimate in [6 ] , which shows that certain lacunary sequences cannot have too large additive energy.
Let us begin by setting up the framework. We call a sequence ( b i ) i ≥ 1 ⊂ ( 0 , ∞ ) (b_i)_{i\ge1}\subset(0,\infty) ( b i ) i ≥ 1 ⊂ ( 0 , ∞ ) lacunary with ratio q ∈ ( 0 , 1 ) q\in(0,1) q ∈ ( 0 , 1 ) if b i + 1 ≤ q b i b_{i+1}\le qb_i b i + 1 ≤ q b i for all i i i , and its associated counting function is
I ( W ) : = # { i : b i ≥ exp ( − W ) } , W > 0. I(W):=\#\{i:b_i\ge\exp(-W)\}, \qquad W>0. I ( W ) := # { i : b i ≥ exp ( − W )} , W > 0.
Corollary 1.7. Suppose S 1 S_1 S 1 and S 2 S_2 S 2 are two lacunary sequences with counting functions I ( W ) I(W) I ( W ) and J ( W ) J(W) J ( W ) , respectively. Then if
lim sup W → ∞ I ( W ) J ( W ) W = ∞ \limsup_{W\to\infty}\frac{I(W)J(W)}{W}=\infty W → ∞ lim sup W I ( W ) J ( W ) = ∞ then neither S 1 + S 2 S_1+S_2 S 1 + S 2 nor S 1 − S 2 S_1-S_2 S 1 − S 2 are polynomial universal.
Finally, restricting to polynomials of fixed degree, we are able to show a general result for sufficiently large sumsets of an arbitrary infinite sequence. For r ≥ 1 r \ge1 r ≥ 1 , let r A : = { a 1 + ⋯ + a r : a i ∈ A } rA := \{a_1+\cdots+a_r : a_i \in A\} r A := { a 1 + ⋯ + a r : a i ∈ A } . We can show the following result.
Theorem 1.8. Let d ≥ 1 d \ge1 d ≥ 1 be an integer and suppose A ⊂ ( 0 , ∞ ) A \subset(0,\infty) A ⊂ ( 0 , ∞ ) has zero as an accumulation point. For every ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) , there is a Borel set E ⊂ [ 0 , 1 ] E \subset[0,1] E ⊂ [ 0 , 1 ] with Lebesgue measure μ ( E ) > 1 − ϵ \mu(E)>1-\epsilon μ ( E ) > 1 − ϵ and
P ( ( d + 3 ) A ) ⊄ E for every nonconstant P ∈ R [ y ] with deg P ≤ d . P((d+3)A) \not\subset E \quad\text{for every nonconstant } P \in\mathbb{R}[y] \text{ with } \deg P \le d. P (( d + 3 ) A ) ⊂ E for every nonconstant P ∈ R [ y ] with deg P ≤ d . Our proof in § 5 resembles Bourgain’s proof [3 ] for the d = 1 d=1 d = 1 case and Tao’s related exposition [27 ] , but extends this to degree-d d d polynomial non-universality.
The explicit Cantor construction
This section proves Theorem 1.3 . The construction is deterministic: at each scale we remove regularly spaced gaps and then intersect the resulting high-measure sets. The proof is inspired by a recent paper by Feng, Lai, and Xiong [12 ] , where they studied the Erdős similarity problem via bi-Lipschitz embeddings.
For our purpose, we need the following strengthening of [12 Theorem 1.3] . We say a function f : R → R f:\mathbb{R}\to\mathbb{R} f : R → R is bi-Lipschitz near 0 if there exists δ > 0 \delta>0 δ > 0 and L > 1 L>1 L > 1 such that
L − 1 ∣ x − y ∣ ≤ ∣ f ( x ) − f ( y ) ∣ ≤ L ∣ x − y ∣ , ∀ x , y ∈ [ − δ , δ ] . L^{-1}|x-y|\le|f(x)-f(y)|\le L|x-y|,\quad\forall x,y\in[-\delta,\delta]. L − 1 ∣ x − y ∣ ≤ ∣ f ( x ) − f ( y ) ∣ ≤ L ∣ x − y ∣ , ∀ x , y ∈ [ − δ , δ ] .
Lemma 2.1. Let ( a n ) n = 1 ∞ (a_n)_{n=1}^{\infty} ( a n ) n = 1 ∞ be a decreasing sequence of positive numbers such that lim n → ∞ a n = 0 \lim_{n\to\infty}a_n=0 lim n → ∞ a n = 0 , lim sup n → ∞ a n + 1 / a n = 1 \limsup_{n\to\infty}a_{n+1}/a_n=1 lim sup n → ∞ a n + 1 / a n = 1 , and there is a constant C > 0 C>0 C > 0 such that a m − a m + 1 ≤ C ( a n − a n + 1 ) a_m-a_{m+1}\le C(a_n-a_{n+1}) a m − a m + 1 ≤ C ( a n − a n + 1 ) for all m > n m>n m > n . Then for each ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) , there is a set E ⊂ [ 0 , 1 ] E\subset[0,1] E ⊂ [ 0 , 1 ] with ∣ E ∣ ≥ 1 − ϵ |E|\ge1-\epsilon ∣ E ∣ ≥ 1 − ϵ , such that E E E does not contain { f ( a n ) : n ≥ N } \{f(a_n):n\ge N\} { f ( a n ) : n ≥ N } for any function f f f defined in a neighbourhood of 0 0 0 and bi-Lipschitz near 0 0 0 , and any positive integer N N N .
Proof. Since lim sup n → ∞ a n + 1 / a n = 1 \limsup_{n\to\infty}a_{n+1}/a_n=1 lim sup n → ∞ a n + 1 / a n = 1 , we have lim inf n → ∞ ( a n − a n + 1 ) / a n = 0 \liminf_{n\to\infty}(a_n-a_{n+1})/a_n=0 lim inf n → ∞ ( a n − a n + 1 ) / a n = 0 . In particular, we can find a strictly increasing sequence ( n k ) k = 1 ∞ (n_k)_{k=1}^{\infty} ( n k ) k = 1 ∞ such that
a n k − a n k + 1 a n k < ϵ 2 k k 2 . (2) \frac{a_{n_k}-a_{n_{k+1}}}{a_{n_k}}<\frac{\epsilon}{2^k k^2}. \tag*{(2)} a n k a n k − a n k + 1 < 2 k k 2 ϵ . (2)
Let δ k = k ( a n k − a n k + 1 ) \delta_k=k(a_{n_k}-a_{n_{k+1}}) δ k = k ( a n k − a n k + 1 ) . Let ℓ k \ell_k ℓ k be the smallest positive integer such that
2 a n k k ≥ 1 ℓ k . \frac{2a_{n_k}}{k}\ge\frac{1}{\ell_k}. k 2 a n k ≥ ℓ k 1 .
then we have 1 / ℓ k ≥ a n k / k 1/\ell_k\ge a_{n_k}/k 1/ ℓ k ≥ a n k / k . It then follows from inequality (2) that
δ k ℓ k ≤ k 2 a n k − a n k + 1 a n k < ϵ 2 k . \delta_k\ell_k\le k^2\frac{a_{n_k}-a_{n_{k+1}}}{a_{n_k}}<\frac{\epsilon}{2^k}. δ k ℓ k ≤ k 2 a n k a n k − a n k + 1 < 2 k ϵ .
Let
E k = ⋃ j = 0 ℓ k − 1 [ j ℓ k , j + 1 ℓ k − δ k ] . E_k=\bigcup_{j=0}^{\ell_k-1}\left[\frac{j}{\ell_k},\frac{j+1}{\ell_k}-\delta_k\right]. E k = j = 0 ⋃ ℓ k − 1 [ ℓ k j , ℓ k j + 1 − δ k ] .
Then ∣ E k ∣ = 1 − δ k ℓ k ≥ 1 − ϵ / 2 k |E_k|=1-\delta_k\ell_k\ge1-\epsilon/2^k ∣ E k ∣ = 1 − δ k ℓ k ≥ 1 − ϵ / 2 k . Let E = ⋂ k = 1 ∞ E k E=\bigcap_{k=1}^{\infty}E_k E = ⋂ k = 1 ∞ E k . Then we have ∣ E ∣ ≥ 1 − ϵ |E|\ge1-\epsilon ∣ E ∣ ≥ 1 − ϵ . We claim that E E E has the desired property. For the sake of contradiction, assume that f : R → R f:\mathbb{R}\to\mathbb{R} f : R → R is a function bi-Lipschitz near 0 and N N N is a positive integer, such that { f ( a n ) : n ≥ N } ⊂ E \{f(a_n):n\ge N\}\subset E { f ( a n ) : n ≥ N } ⊂ E . Then there exists δ > 0 \delta>0 δ > 0 and L > 1 L>1 L > 1 such that
L − 1 ∣ x − y ∣ ≤ ∣ f ( x ) − f ( y ) ∣ ≤ L ∣ x − y ∣ , ∀ x , y ∈ [ − δ , δ ] . (3) L^{-1}|x-y|\le|f(x)-f(y)|\le L|x-y|,\qquad\forall x,y\in[-\delta,\delta]. \tag*{(3)} L − 1 ∣ x − y ∣ ≤ ∣ f ( x ) − f ( y ) ∣ ≤ L ∣ x − y ∣ , ∀ x , y ∈ [ − δ , δ ] . (3)
By possibly increasing N N N , we may assume that a N ≤ δ a_N\le\delta a N ≤ δ . Note that f f f is monotone in [ − δ , δ ] [-\delta,\delta] [ − δ , δ ] . Let k k k be an integer such that k > 2 C L k>2CL k > 2 C L and n k > N n_k>N n k > N . Then inequality (3) implies that
∣ f ( a n k ) − f ( 0 ) ∣ = lim m → ∞ ∣ f ( a n k ) − f ( a m ) ∣ ≥ lim m → ∞ L − 1 ( a n k − a m ) = a n k L > 2 a n k k ≥ 1 ℓ k . |f(a_{n_k})-f(0)|=\lim_{m\to\infty}|f(a_{n_k})-f(a_m)|\ge\lim_{m\to\infty}L^{-1}(a_{n_k}-a_m)=\frac{a_{n_k}}{L}>\frac{2a_{n_k}}{k}\ge\frac{1}{\ell_k}. ∣ f ( a n k ) − f ( 0 ) ∣ = m → ∞ lim ∣ f ( a n k ) − f ( a m ) ∣ ≥ m → ∞ lim L − 1 ( a n k − a m ) = L a n k > k 2 a n k ≥ ℓ k 1 .
Thus, B = { f ( a n ) : n ≥ n k } B=\{f(a_n):n\ge n_k\} B = { f ( a n ) : n ≥ n k } is a subset of E k E_k E k with diameter at least 1 ℓ k \frac{1}{\ell_k} ℓ k 1 . Recall that E k E_k E k is a disjoint union of intervals of length less than 1 ℓ k \frac{1}{\ell_k} ℓ k 1 , so B B B intersects at least two of those intervals forming E k E_k E k .
On the other hand, for each m ≥ n k m\ge n_k m ≥ n k , inequality (3) implies that
∣ f ( a m ) − f ( a m + 1 ) ∣ ≤ L ( a m − a m + 1 ) ≤ C L ( a n k − a n k + 1 ) < k ( a n k − a n k + 1 ) = δ k . |f(a_m)-f(a_{m+1})|\le L(a_m-a_{m+1})\le CL(a_{n_k}-a_{n_k+1})<k(a_{n_k}-a_{n_k+1})=\delta_k. ∣ f ( a m ) − f ( a m + 1 ) ∣ ≤ L ( a m − a m + 1 ) ≤ C L ( a n k − a n k + 1 ) < k ( a n k − a n k + 1 ) = δ k .
However, the gap between any two intervals forming E k E_k E k has size at least δ k \delta_k δ k , a contradiction. This finishes the proof of the claim. □
Now we are ready to prove Theorem 1.3 .
Proof of Theorem 1.3 . Let ϵ > 0 \epsilon>0 ϵ > 0 . For each positive integer k k k , we have lim sup n → ∞ a n + 1 k / a n k = 1 \limsup_{n\to\infty}a_{n+1}^k/a_n^k=1 lim sup n → ∞ a n + 1 k / a n k = 1 ; moreover, for all m > n m>n m > n , we have
a m k − a m + 1 k = ( a m − a m + 1 ) ( ∑ j = 0 k − 1 a m j a m + 1 k − 1 − j ) ≤ k a m k − 1 ( a m − a m + 1 ) ≤ k a n + 1 k − 1 ( a m − a m + 1 ) ≤ C k a n + 1 k − 1 ( a n − a n + 1 ) ≤ C ( a n − a n + 1 ) ≤ C ( a n − a n + 1 ) ( ∑ j = 0 k − 1 a n j a n + 1 k − 1 − j ) ≤ C ( a n k − a n + 1 k ) . \begin{aligned}
a_m^k-a_{m+1}^k
&=(a_m-a_{m+1})\left(\sum_{j=0}^{k-1}a_m^j a_{m+1}^{k-1-j}\right)\\
&\le ka_m^{k-1}(a_m-a_{m+1})\le ka_{n+1}^{k-1}(a_m-a_{m+1})\\
&\le Cka_{n+1}^{k-1}(a_n-a_{n+1})\le C(a_n-a_{n+1})\\
&\le C(a_n-a_{n+1})\left(\sum_{j=0}^{k-1}a_n^j a_{n+1}^{k-1-j}\right)\le C(a_n^k-a_{n+1}^k).
\end{aligned} a m k − a m + 1 k = ( a m − a m + 1 ) ( j = 0 ∑ k − 1 a m j a m + 1 k − 1 − j ) ≤ k a m k − 1 ( a m − a m + 1 ) ≤ k a n + 1 k − 1 ( a m − a m + 1 ) ≤ C k a n + 1 k − 1 ( a n − a n + 1 ) ≤ C ( a n − a n + 1 ) ≤ C ( a n − a n + 1 ) ( j = 0 ∑ k − 1 a n j a n + 1 k − 1 − j ) ≤ C ( a n k − a n + 1 k ) .
Thus we can apply Lemma 2.1 to the sequence ( a n k ) n = 1 ∞ (a_n^k)_{n=1}^{\infty} ( a n k ) n = 1 ∞ to obtain a set E k ⊂ [ 0 , 1 ] E_k\subset[0,1] E k ⊂ [ 0 , 1 ] with ∣ E k ∣ ≥ 1 − ϵ / 2 k |E_k|\ge1-\epsilon/2^k ∣ E k ∣ ≥ 1 − ϵ / 2 k , such that E k E_k E k does not contain { f ( a n k ) : n ≥ N } \{f(a_n^k):n\ge N\} { f ( a n k ) : n ≥ N } for any function f : R → R f:\mathbb{R}\to\mathbb{R} f : R → R bi-Lipschitz near 0 and any positive integer N N N .
Let E = ⋂ k = 1 ∞ E k E=\bigcap_{k=1}^{\infty}E_k E = ⋂ k = 1 ∞ E k . Then we have ∣ E ∣ ≥ 1 − ϵ |E|\ge1-\epsilon ∣ E ∣ ≥ 1 − ϵ . We claim that E E E has the desired property. Suppose otherwise that there is a non-constant function f : R → R f:\mathbb{R}\to\mathbb{R} f : R → R analytic at 0 and a positive integer N N N , such that { f ( a n ) : n ≥ N } ⊂ E \{f(a_n):n\ge N\}\subset E { f ( a n ) : n ≥ N } ⊂ E . Since f f f is analytic at 0, there is δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , such that we can write
f ( x ) = ∑ i = 0 ∞ c i x i f(x)=\sum_{i=0}^{\infty}c_i x^i f ( x ) = i = 0 ∑ ∞ c i x i
and the series converges to f ( x ) f(x) f ( x ) for ∣ x ∣ ≤ δ |x|\le\delta ∣ x ∣ ≤ δ . Since f f f is non-constant, we can find the smallest positive integer k k k such that c k ≠ 0 c_k\ne0 c k = 0 . Since a n → 0 a_n\to0 a n → 0 as n → ∞ n\to\infty n → ∞ , there is m ≥ N m\ge N m ≥ N such that a n ≤ δ a_n\le\delta a n ≤ δ for all n ≥ m n\ge m n ≥ m . For 0 ≤ y ≤ δ k 0\le y\le\delta^k 0 ≤ y ≤ δ k , put
g + ( y ) = f ( y 1 / k ) . g_+(y)=f(y^{1/k}). g + ( y ) = f ( y 1/ k ) .
Since k k k is the first positive integer with c k ≠ 0 c_k\ne0 c k = 0 , we have
g + ( y ) = c 0 + c k y + O ( y 1 + 1 / k ) ( y ↓ 0 ) . g_+(y)=c_0+c_k y+O(y^{1+1/k})\qquad(y\downarrow0). g + ( y ) = c 0 + c k y + O ( y 1 + 1/ k ) ( y ↓ 0 ) .
Define g g g on a neighbourhood of 0 by
g ( y ) = g + ( y ) ( y ≥ 0 ) , g ( y ) = 2 c 0 − g + ( − y ) ( y < 0 ) . g(y)=g_+(y)\quad(y\ge0),\qquad g(y)=2c_0-g_+(-y)\quad(y<0). g ( y ) = g + ( y ) ( y ≥ 0 ) , g ( y ) = 2 c 0 − g + ( − y ) ( y < 0 ) .
Then
g ( y ) = c 0 + c k y + O ( ∣ y ∣ 1 + 1 / k ) ( y → 0 ) , g(y)=c_0+c_k y+O(|y|^{1+1/k}) \qquad(y\to0), g ( y ) = c 0 + c k y + O ( ∣ y ∣ 1 + 1/ k ) ( y → 0 ) ,
and hence g g g is bi-Lipschitz near 0. On the other hand, f ( a n ) = g ( a n k ) f(a_n)=g(a_n^k) f ( a n ) = g ( a n k ) for all n ≥ m n\ge m n ≥ m . It follows that
{ g ( a n k ) : n ≥ m } = { f ( a n ) : n ≥ m } ⊂ { f ( a n ) : n ≥ N } ⊂ E ⊂ E k , \{g(a_n^k):n\ge m\}=\{f(a_n):n\ge m\}\subset\{f(a_n):n\ge N\}\subset E\subset E_k, { g ( a n k ) : n ≥ m } = { f ( a n ) : n ≥ m } ⊂ { f ( a n ) : n ≥ N } ⊂ E ⊂ E k ,
which violates the defining property of E k E_k E k . This finishes the proof of the claim. □
The random Cantor construction
The second method is a random Cantor-type construction. It is less explicit than the construction in the previous section, but it is more flexible: it only requires large finite blocks with good normalized gaps. The main point is that, after a random partition of [ 0 , 1 ] [0,1] [ 0 , 1 ] , the uncountable family of polynomial or analytic maps gives only subexponentially many interval patterns on the chosen finite block.
A lemma on hyperplane intersection
We prove the following elementary counting fact.
Lemma 3.1. Let H ≥ 1 H\ge1 H ≥ 1 . Let L 1 , … , L H L_1,\ldots,L_H L 1 , … , L H be affine-linear functions on R r \mathbb{R}^r R r . Then the number of possible truth-value patterns
( 1 L 1 ( c ) ≥ 0 , … , 1 L H ( c ) ≥ 0 ) , c ∈ R r , (\mathbf{1}_{L_1(c)\ge0},\ldots,\mathbf{1}_{L_H(c)\ge0}),\qquad c\in\mathbb{R}^r, ( 1 L 1 ( c ) ≥ 0 , … , 1 L H ( c ) ≥ 0 ) , c ∈ R r , is at most ( r + 1 ) H r (r+1)H^r ( r + 1 ) H r .
Proof. Let N r ( H ) N_r(H) N r ( H ) denote the maximum possible number of such truth-value patterns cut out by H H H affine inequalities in R r \mathbb{R}^r R r . We prove by induction that
N r ( H ) ≤ ∑ q = 0 r ( H q ) . N_r(H)\le\sum_{q=0}^{r}\binom{H}{q}. N r ( H ) ≤ q = 0 ∑ r ( q H ) .
Consider adding the last inequality L H ( c ) ≥ 0 L_H(c)\ge0 L H ( c ) ≥ 0 . If L H L_H L H is constant, then it does not increase the number of patterns. Otherwise, its zero set
Z = { c ∈ R r : L H ( c ) = 0 } Z=\{c\in\mathbb{R}^r:L_H(c)=0\} Z = { c ∈ R r : L H ( c ) = 0 }
is an affine subspace of dimension r − 1 r-1 r − 1 . The only patterns for L 1 , … , L H − 1 L_1,\ldots,L_{H-1} L 1 , … , L H − 1 that can split into two different patterns after adding L H L_H L H are those whose regions meet Z Z Z . The number of such possible boundary patterns is at most the number of truth-value patterns cut out on Z Z Z by the restricted affine functions
L 1 ∣ Z , … , L H − 1 ∣ Z . L_1|_Z,\ldots,L_{H-1}|_Z. L 1 ∣ Z , … , L H − 1 ∣ Z .
Since Z Z Z has dimension r − 1 r-1 r − 1 , this number is at most N r − 1 ( H − 1 ) N_{r-1}(H-1) N r − 1 ( H − 1 ) . Hence
N r ( H ) ≤ N r ( H − 1 ) + N r − 1 ( H − 1 ) . N_r(H)\le N_r(H-1)+N_{r-1}(H-1). N r ( H ) ≤ N r ( H − 1 ) + N r − 1 ( H − 1 ) .
Together with N 0 ( H ) ≤ 1 N_0(H)\le1 N 0 ( H ) ≤ 1 and N r ( 0 ) = 1 N_r(0)=1 N r ( 0 ) = 1 , induction gives
N r ( H ) ≤ ∑ q = 0 r ( H q ) ≤ ( r + 1 ) H r . N_r(H)\le\sum_{q=0}^{r}\binom{H}{q}\le(r+1)H^r. N r ( H ) ≤ q = 0 ∑ r ( q H ) ≤ ( r + 1 ) H r .
Proof of the polynomial assertion
Lemma 3.2. Fix integers D ≥ m ≥ 1 D \ge m \ge1 D ≥ m ≥ 1 and real numbers 0 < b < B < ∞ 0 < b < B < \infty 0 < b < B < ∞ . Let
W D , m , b , B = { c = ( c m , … , c D ) : b ≤ ∣ c m ∣ ≤ B , ∣ c j ∣ ≤ B for j > m } . \mathcal{W}_{D,m,b,B}=\{c=(c_m,\ldots,c_D): b\leq|c_m|\leq B,\quad|c_j|\leq B\text{ for }j>m\}. W D , m , b , B = { c = ( c m , … , c D ) : b ≤ ∣ c m ∣ ≤ B , ∣ c j ∣ ≤ B for j > m } . For c ∈ W D , m , b , B c\in\mathcal{W}_{D,m,b,B} c ∈ W D , m , b , B , set
R c ( t ) = c m t m + c m + 1 t m + 1 + ⋯ + c D t D . R_c(t)=c_m t^m+c_{m+1}t^{m+1}+\cdots+c_Dt^D. R c ( t ) = c m t m + c m + 1 t m + 1 + ⋯ + c D t D . Let
A ν = { a ν , 1 > ⋯ > a ν , n ν > 0 } A_\nu=\{a_{\nu,1}>\cdots>a_{\nu,n_\nu}>0\} A ν = { a ν , 1 > ⋯ > a ν , n ν > 0 } be finite subsets satisfying
a ν , 1 → 0 , − log δ ν = o ( n ν ) , δ ν = min 1 ≤ i < n ν a ν , i − a ν , i + 1 a ν , 1 . a_{\nu,1}\to0,\qquad-\log\delta_\nu=o(n_\nu),\qquad
\delta_\nu=\min_{1\leq i<n_\nu}\frac{a_{\nu,i}-a_{\nu,i+1}}{a_{\nu,1}}. a ν , 1 → 0 , − log δ ν = o ( n ν ) , δ ν = 1 ≤ i < n ν min a ν , 1 a ν , i − a ν , i + 1 . Then, for every ε , η ∈ ( 0 , 1 ) \varepsilon,\eta\in(0,1) ε , η ∈ ( 0 , 1 ) , and for all sufficiently large ν \nu ν , there is a measurable set F ⊂ [ 0 , 1 ] F\subset[0,1] F ⊂ [ 0 , 1 ] with
μ ( F ) > 1 − ε \mu(F)>1-\varepsilon μ ( F ) > 1 − ε such that the exceptional set
X ν ( F ) = { γ ∈ [ 0 , 1 ] : ∃ c ∈ W D , m , b , B such that γ + R c ( a ν , i ) ∈ F for all 1 ≤ i ≤ n ν } X_\nu(F)=\{\gamma\in[0,1]:\exists c\in\mathcal{W}_{D,m,b,B}\text{ such that }\gamma+R_c(a_{\nu,i})\in F\text{ for all }1\leq i\leq n_\nu\} X ν ( F ) = { γ ∈ [ 0 , 1 ] : ∃ c ∈ W D , m , b , B such that γ + R c ( a ν , i ) ∈ F for all 1 ≤ i ≤ n ν } satisfies
μ ( X ν ( F ) ) < η . \mu(X_\nu(F))<\eta. μ ( X ν ( F )) < η .
Proof. We first record a uniform monotonicity estimate for R c R_c R c near 0 0 0 , uniform for c ∈ W D , m , b , B c\in\mathcal{W}_{D,m,b,B} c ∈ W D , m , b , B . Choose ρ > 0 \rho>0 ρ > 0 , depending only on D D D , m m m , b b b , B B B , so small that
B ∑ j = m + 1 D j ρ j − m ≤ m b 2 . B\sum_{j=m+1}^{D}j\rho^{j-m}\leq\frac{mb}{2}. B j = m + 1 ∑ D j ρ j − m ≤ 2 mb .
Claim 3.3. For each c ∈ W D , m , b , B c\in\mathcal{W}_{D,m,b,B} c ∈ W D , m , b , B , R c R_c R c is monotone on ( 0 , ρ ] (0,\rho] ( 0 , ρ ] , and for 0 < y < x ≤ ρ 0<y<x\leq\rho 0 < y < x ≤ ρ ,
∣ R c ( x ) − R c ( y ) ∣ ≥ b 2 ( x − y ) m . |R_c(x)-R_c(y)|\geq\frac{b}{2}(x-y)^m. ∣ R c ( x ) − R c ( y ) ∣ ≥ 2 b ( x − y ) m .
Proof of claim. Fix c ∈ W D , m , b , B c\in\mathcal{W}_{D,m,b,B} c ∈ W D , m , b , B . Then, for 0 < t ≤ ρ 0<t\leq\rho 0 < t ≤ ρ , we have
R c ′ ( t ) = m c m t m − 1 + ∑ j = m + 1 D j c j t j − 1 , R'_c(t)=mc_m t^{m-1}+\sum_{j=m+1}^{D}jc_jt^{j-1}, R c ′ ( t ) = m c m t m − 1 + j = m + 1 ∑ D j c j t j − 1 ,
where
∣ ∑ j = m + 1 D j c j t j − 1 ∣ ≤ t m − 1 ∑ j = m + 1 D j ∣ c j ∣ t j − m ≤ B t m − 1 ∑ j = m + 1 D j ρ j − m ≤ m b 2 t m − 1 . \left|\sum_{j=m+1}^{D}jc_jt^{j-1}\right|
\leq t^{m-1}\sum_{j=m+1}^{D}j|c_j|t^{j-m}
\leq Bt^{m-1}\sum_{j=m+1}^{D}j\rho^{j-m}
\leq\frac{mb}{2}t^{m-1}. j = m + 1 ∑ D j c j t j − 1 ≤ t m − 1 j = m + 1 ∑ D j ∣ c j ∣ t j − m ≤ B t m − 1 j = m + 1 ∑ D j ρ j − m ≤ 2 mb t m − 1 .
Thus, for 0 < t ≤ ρ 0<t\leq\rho 0 < t ≤ ρ ,
∣ R c ′ ( t ) ∣ ≥ m b 2 t m − 1 , |R'_c(t)|\geq\frac{mb}{2}t^{m-1}, ∣ R c ′ ( t ) ∣ ≥ 2 mb t m − 1 ,
and R c ′ R'_c R c ′ has constant sign. Hence R c R_c R c is monotone on ( 0 , ρ ] (0,\rho] ( 0 , ρ ] , and for 0 < y < x ≤ ρ 0<y<x\leq\rho 0 < y < x ≤ ρ ,
∣ R c ( x ) − R c ( y ) ∣ ≥ m b 2 ∫ y x t m − 1 d t = b 2 ( x m − y m ) ≥ b 2 ( x − y ) m . |R_c(x)-R_c(y)|\geq\frac{mb}{2}\int_y^x t^{m-1}\,dt
=\frac{b}{2}(x^m-y^m)\geq\frac{b}{2}(x-y)^m. ∣ R c ( x ) − R c ( y ) ∣ ≥ 2 mb ∫ y x t m − 1 d t = 2 b ( x m − y m ) ≥ 2 b ( x − y ) m .
■
Fix a large ν \nu ν , and write
n = n ν , a i = a ν , i , δ = δ ν . n=n_{\nu},\qquad a_i=a_{\nu,i},\qquad\delta=\delta_{\nu}. n = n ν , a i = a ν , i , δ = δ ν .
We may assume a 1 < ρ a_1<\rho a 1 < ρ . Let
r = D − m + 1 , k = ⌊ 8 b ( a 1 δ ) m ⌋ . r=D-m+1,\qquad k=\left\lfloor\frac{8}{b(a_1\delta)^m}\right\rfloor. r = D − m + 1 , k = ⌊ b ( a 1 δ ) m 8 ⌋ .
Partition [ 0 , 1 ) [0,1) [ 0 , 1 ) into the half-open intervals
I ℓ = [ ℓ k , ℓ + 1 k ) ( 0 ≤ ℓ ≤ k − 1 ) . I_\ell=\left[\frac{\ell}{k},\frac{\ell+1}{k}\right)\qquad(0\leq\ell\leq k-1). I ℓ = [ k ℓ , k ℓ + 1 ) ( 0 ≤ ℓ ≤ k − 1 ) .
We keep each interval independently with probability p = p ν p=p_\nu p = p ν to be determined later in the proof, and let F F F be the resulting random set. For each x ∈ [ 0 , 1 ) x\in[0,1) x ∈ [ 0 , 1 ) , write I ( x ) I(x) I ( x ) for the unique interval of this partition containing x x x .
Fix γ ∈ [ 0 , 1 ] \gamma\in[0,1] γ ∈ [ 0 , 1 ] . For c ∈ W D , m , b , B c\in\mathcal{W}_{D,m,b,B} c ∈ W D , m , b , B , suppose first that
γ + R c ( a i ) ∈ [ 0 , 1 ) ( 1 ≤ i ≤ n ) . \gamma+R_c(a_i)\in[0,1)\qquad(1\leq i\leq n). γ + R c ( a i ) ∈ [ 0 , 1 ) ( 1 ≤ i ≤ n ) .
Then define the interval pattern of c c c by
π γ ( c ) = ( ℓ 1 ( c ) , … , ℓ n ( c ) ) , \pi_\gamma(c)=(\ell_1(c),\ldots,\ell_n(c)), π γ ( c ) = ( ℓ 1 ( c ) , … , ℓ n ( c )) ,
where
γ + R c ( a i ) ∈ I ℓ i ( c ) . \gamma+R_c(a_i)\in I_{\ell_i(c)}. γ + R c ( a i ) ∈ I ℓ i ( c ) .
Since R c R_c R c is monotone on ( 0 , ρ ] (0,\rho] ( 0 , ρ ] , the values R c ( a 1 ) , … , R c ( a n ) R_c(a_1),\ldots,R_c(a_n) R c ( a 1 ) , … , R c ( a n ) are ordered. For each 1 ≤ i < n 1\leq i<n 1 ≤ i < n , Claim 3.3 implies that
∣ R c ( a i ) − R c ( a i + 1 ) ∣ ≥ b 2 ( a i − a i + 1 ) m ≥ b 2 ( a 1 δ ) m > 1 k . \left|R_c(a_i)-R_c(a_{i+1})\right|
\geq\frac{b}{2}(a_i-a_{i+1})^m
\geq\frac{b}{2}(a_1\delta)^m
>\frac{1}{k}. ∣ R c ( a i ) − R c ( a i + 1 ) ∣ ≥ 2 b ( a i − a i + 1 ) m ≥ 2 b ( a 1 δ ) m > k 1 .
Thus the intervals
I ℓ 1 ( c ) , … , I ℓ n ( c ) I_{\ell_1(c)},\ldots,I_{\ell_n(c)} I ℓ 1 ( c ) , … , I ℓ n ( c )
are distinct.
We now count the number of possible interval patterns as c c c varies in W D , m , b , B \mathcal{W}_{D,m,b,B} W D , m , b , B . We claim that only
O b , B , D ( n r δ − m r ) O_{b,B,D}\left(n^r\delta^{-mr}\right) O b , B , D ( n r δ − m r )
different interval patterns can occur. For fixed i i i , the interval containing γ + R c ( a i ) \gamma+R_c(a_i) γ + R c ( a i ) is determined by which partition endpoints lie to its left. Equivalently, it is determined by the truth values of the affine inequalities
γ + R c ( a i ) ≥ ℓ k . \gamma+R_c(a_i)\geq\frac{\ell}{k}. γ + R c ( a i ) ≥ k ℓ .
Writing this out, these inequalities are
γ + c m a i m + c m + 1 a i m + 1 + ⋯ + c D a i D ≥ ℓ k . \gamma+c_m a_i^m+c_{m+1}a_i^{m+1}+\cdots+c_Da_i^D\geq\frac{\ell}{k}. γ + c m a i m + c m + 1 a i m + 1 + ⋯ + c D a i D ≥ k ℓ .
For fixed i i i , the set of possible values of R c ( a i ) R_c(a_i) R c ( a i ) , with c ∈ W D , m , b , B c\in\mathcal{W}_{D,m,b,B} c ∈ W D , m , b , B , is contained in an interval of length O B , D ( a i m ) O_{B,D}(a_i^m) O B , D ( a i m ) , hence in an interval of length O B , D ( a 1 m ) O_{B,D}(a_1^m) O B , D ( a 1 m ) . Since the partition endpoints are spaced by 1 / k 1/k 1/ k , only
O b , B , D ( k a 1 m + 1 ) = O b , B , D ( δ − m ) O_{b,B,D}(ka_1^m+1)=O_{b,B,D}(\delta^{-m}) O b , B , D ( k a 1 m + 1 ) = O b , B , D ( δ − m )
values of ℓ \ell ℓ can change their truth value as c c c varies. Thus, as i i i ranges from 1 to n n n , the interval pattern is determined by the truth values of at most
H ≪ b , B , D n δ − m H \ll_{b,B,D} n\delta^{-m} H ≪ b , B , D n δ − m
affine inequalities in the r = D − m + 1 r = D - m + 1 r = D − m + 1 coefficient variables. By Lemma 3.1 , the number of possible truth-value patterns, and hence the number of possible interval patterns π γ ( c ) \pi_\gamma(c) π γ ( c ) , is at most
( r + 1 ) H r ≪ b , B , D n r δ − m r . (r+1)H^r \ll_{b,B,D} n^r\delta^{-mr}. ( r + 1 ) H r ≪ b , B , D n r δ − m r .
Now, if γ ∈ X ν ( F ) \gamma\in X_\nu(F) γ ∈ X ν ( F ) , then one of these possible interval patterns has all of its n n n intervals kept. Since the intervals in each pattern are distinct, the probability that a fixed pattern survives is p n p^n p n . Therefore, uniformly in γ \gamma γ ,
P ( γ ∈ X ν ( F ) ) ≤ C b , B , D n r δ − m r p n . \mathbb{P}(\gamma\in X_\nu(F)) \le C_{b,B,D}n^r\delta^{-mr}p^n. P ( γ ∈ X ν ( F )) ≤ C b , B , D n r δ − m r p n .
After integrating over γ ∈ [ 0 , 1 ] \gamma\in[0,1] γ ∈ [ 0 , 1 ] , we get
E μ ( X ν ( F ) ) ≤ C b , B , D n r δ − m r p n . \mathbb{E}\,\mu(X_\nu(F)) \le C_{b,B,D}n^r\delta^{-mr}p^n. E μ ( X ν ( F )) ≤ C b , B , D n r δ − m r p n .
Put
S ν = r log n ν + m r ∣ log δ ν ∣ . S_\nu= r\log n_\nu+ mr\lvert\log\delta_\nu\rvert. S ν = r log n ν + m r ∣ log δ ν ∣ .
Since m m m and r r r are fixed and − log δ ν = o ( n ν ) -\log\delta_\nu=o(n_\nu) − log δ ν = o ( n ν ) , we have
S ν = o ( n ν ) . S_\nu=o(n_\nu). S ν = o ( n ν ) .
Choose
p ν = exp ( − S ν + 1 n ν ) . p_\nu=\exp\left(-\sqrt{\frac{S_\nu+1}{n_\nu}}\right). p ν = exp ( − n ν S ν + 1 ) .
Then p ν → 1 p_\nu\to1 p ν → 1 . Moreover,
log ( n ν r δ ν − m r p ν n ν ) = r log n ν + m r ∣ log δ ν ∣ − n ν S ν + 1 n ν = S ν − n ν ( S ν + 1 ) → − ∞ , \begin{aligned}
\log\left(n_\nu^r\delta_\nu^{-mr}p_\nu^{n_\nu}\right)
= r\log n_\nu+mr\lvert\log\delta_\nu\rvert-n_\nu\sqrt{\frac{S_\nu+1}{n_\nu}} \\
&= S_\nu-\sqrt{n_\nu(S_\nu+1)}\to-\infty,
\end{aligned} log ( n ν r δ ν − m r p ν n ν ) = r log n ν + m r ∣ log δ ν ∣ − n ν n ν S ν + 1 = S ν − n ν ( S ν + 1 ) → − ∞ ,
because S ν + 1 = o ( n ν ) S_\nu+1=o(n_\nu) S ν + 1 = o ( n ν ) . Hence
n ν r δ ν − m r p ν n ν → 0. n_\nu^r\delta_\nu^{-mr}p_\nu^{n_\nu}\to0. n ν r δ ν − m r p ν n ν → 0.
In particular, for sufficiently large ν \nu ν , we have
1 − p ν < ε / 4 , E μ ( X ν ( F ) ) < η / 4. 1-p_\nu<\varepsilon/4,\qquad\mathbb{E}\,\mu(X_\nu(F))<\eta/4. 1 − p ν < ε /4 , E μ ( X ν ( F )) < η /4.
Since E μ ( F ) = p ν \mathbb{E}\,\mu(F)=p_\nu E μ ( F ) = p ν , Markov’s inequality gives
P ( μ ( F ) ≤ 1 − ε ) = P ( 1 − μ ( F ) ≥ ε ) < 1 4 , P ( μ ( X ν ( F ) ) ≥ η ) < 1 4 . \mathbb{P}(\mu(F)\le1-\varepsilon)=\mathbb{P}(1-\mu(F)\ge\varepsilon)<\frac14,\qquad
\mathbb{P}(\mu(X_\nu(F))\ge\eta)<\frac14. P ( μ ( F ) ≤ 1 − ε ) = P ( 1 − μ ( F ) ≥ ε ) < 4 1 , P ( μ ( X ν ( F )) ≥ η ) < 4 1 .
Thus, with positive probability, both desired inequalities hold. Fix such a realization of F F F . This proves the lemma. □
We are now ready to prove Theorem 1.4 .
Proof of the polynomial assertion in Theorem 1.4 . Consider finite blocks
A ν = { a ν , 1 > ⋯ > a ν , n ν > 0 } ⊂ A A_\nu=\{a_{\nu,1}>\cdots>a_{\nu,n_\nu}>0\}\subset A A ν = { a ν , 1 > ⋯ > a ν , n ν > 0 } ⊂ A
satisfying
a ν , 1 → 0 , − log δ ν = o ( n ν ) . a_{\nu,1}\to0,\qquad-\log\delta_\nu=o(n_\nu). a ν , 1 → 0 , − log δ ν = o ( n ν ) .
Enumerate all quadruples
( D j , m j , b j , B j ) , D j ≥ 1 , 1 ≤ m j ≤ D j , 0 < b j < B j , (D_j,m_j,b_j,B_j),\qquad D_j\ge1,\quad1\le m_j\le D_j,\quad0<b_j<B_j, ( D j , m j , b j , B j ) , D j ≥ 1 , 1 ≤ m j ≤ D j , 0 < b j < B j ,
where D j , m j D_j,m_j D j , m j are integers and b j , B j ∈ Q b_j,B_j\in\mathbb{Q} b j , B j ∈ Q . This enumeration covers every nonzero polynomial coefficient vector: if
P ( t ) = γ + c 1 t + ⋯ + c D t D P(t)=\gamma+c_1t+\cdots+c_Dt^D P ( t ) = γ + c 1 t + ⋯ + c D t D
is nonconstant and D = deg P D=\deg P D = deg P , then, with
m = min { i ≥ 1 : c i ≠ 0 } , m=\min\{i\ge1:c_i\ne0\}, m = min { i ≥ 1 : c i = 0 } ,
there is some j j j with D j = D D_j=D D j = D , m j = m m_j=m m j = m , and
( c m , … , c D ) ∈ W D j , m j , b j , B j . (c_m,\ldots,c_D)\in W_{D_j,m_j,b_j,B_j}. ( c m , … , c D ) ∈ W D j , m j , b j , B j .
Choose positive numbers ε j , η j \varepsilon_j,\eta_j ε j , η j such that
∑ j ε j < 1 4 , ∑ j η j < 1 8 . \sum_j\varepsilon_j<\frac{1}{4},\qquad\sum_j\eta_j<\frac{1}{8}. j ∑ ε j < 4 1 , j ∑ η j < 8 1 .
For each j j j , apply Lemma 3.2 to W D j , m j , b j , B j W_{D_j,m_j,b_j,B_j} W D j , m j , b j , B j , with parameters ε j , η j \varepsilon_j,\eta_j ε j , η j . We obtain a block A ν j ⊂ A A_{\nu_j}\subset A A ν j ⊂ A , a measurable set F j ⊂ [ 0 , 1 ] F_j\subset[0,1] F j ⊂ [ 0 , 1 ] , and an exceptional set X j ⊂ [ 0 , 1 ] X_j\subset[0,1] X j ⊂ [ 0 , 1 ] such that
μ ( F j ) > 1 − ε j , μ ( X j ) < η j . \mu(F_j)>1-\varepsilon_j,\qquad\mu(X_j)<\eta_j. μ ( F j ) > 1 − ε j , μ ( X j ) < η j .
Put
F = ⋂ j = 1 ∞ F j , X = ⋃ j = 1 ∞ X j . F=\bigcap_{j=1}^{\infty}F_j,\qquad X=\bigcup_{j=1}^{\infty}X_j. F = j = 1 ⋂ ∞ F j , X = j = 1 ⋃ ∞ X j .
Then μ ( F ) > 3 / 4 \mu(F)>3/4 μ ( F ) > 3/4 and μ ( X ) < 1 / 8 \mu(X)<1/8 μ ( X ) < 1/8 . Choose an open set G ⊃ X G\supset X G ⊃ X with μ ( G ) < 1 / 4 \mu(G)<1/4 μ ( G ) < 1/4 , and set
E = F ∖ G . E=F\setminus G. E = F ∖ G .
Then E ⊂ [ 0 , 1 ] E\subset[0,1] E ⊂ [ 0 , 1 ] has positive measure.
Suppose that P ( A ) ⊂ E P(A)\subset E P ( A ) ⊂ E for some nonconstant real polynomial P P P . Write
P ( t ) = γ + c 1 t + ⋯ + c D t D , D = deg P , P(t)=\gamma+c_1t+\cdots+c_Dt^D,\qquad D=\deg P, P ( t ) = γ + c 1 t + ⋯ + c D t D , D = deg P ,
and let m = min { i ≥ 1 : c i ≠ 0 } m=\min\{i\ge1:c_i\ne0\} m = min { i ≥ 1 : c i = 0 } . Since a n → 0 a_n\to0 a n → 0 and E ⊂ [ 0 , 1 ] E\subset[0,1] E ⊂ [ 0 , 1 ] , we have P ( a n ) → P ( 0 ) = γ P(a_n)\to P(0)=\gamma P ( a n ) → P ( 0 ) = γ , so γ ∈ [ 0 , 1 ] \gamma\in[0,1] γ ∈ [ 0 , 1 ] . Choose j j j with
D j = D , m j = m , ( c m , … , c D ) ∈ W D j , m j , b j , B j . D_j=D,\qquad m_j=m,\qquad(c_m,\ldots,c_D)\in W_{D_j,m_j,b_j,B_j}. D j = D , m j = m , ( c m , … , c D ) ∈ W D j , m j , b j , B j .
The block A ν j A_{\nu_j} A ν j used in constructing F j F_j F j is a subset of A A A , and P ( A ) ⊂ E ⊂ F j P(A)\subset E\subset F_j P ( A ) ⊂ E ⊂ F j . Hence P ( A ν j ) ⊂ F j P(A_{\nu_j})\subset F_j P ( A ν j ) ⊂ F j , so by the definition of X j X_j X j we have γ ∈ X j ⊂ G \gamma\in X_j\subset G γ ∈ X j ⊂ G . But G G G is open and P ( a n ) → γ P(a_n)\to\gamma P ( a n ) → γ as n → ∞ n\to\infty n → ∞ . Thus P ( a n ) ∈ G P(a_n)\in G P ( a n ) ∈ G for all sufficiently large n n n , contradicting P ( A ) ⊂ E = F ∖ G P(A)\subset E=F\setminus G P ( A ) ⊂ E = F ∖ G . □ \square □
Proof of the analytic assertion
Lemma 3.4. Fix
m ≥ 1 , R > 0 , M > 0 , 0 < b < B < ∞ . m \ge1,\qquad R>0,\qquad M>0,\qquad0<b<B<\infty. m ≥ 1 , R > 0 , M > 0 , 0 < b < B < ∞. Let V m , R , M , b , B \mathcal{V}_{m,R,M,b,B} V m , R , M , b , B be the family of functions
h ( t ) = c m t m + c m + 1 t m + 1 + ⋯ h(t)=c_m t^m+c_{m+1}t^{m+1}+\cdots h ( t ) = c m t m + c m + 1 t m + 1 + ⋯ with real coefficients, satisfying
b ≤ ∣ c m ∣ ≤ B , ∑ j = m ∞ ∣ c j ∣ R j ≤ M . b\leq\lvert c_m\rvert\leq B,\qquad\sum_{j=m}^{\infty}\lvert c_j\rvert R^j\leq M. b ≤ ∣ c m ∣ ≤ B , j = m ∑ ∞ ∣ c j ∣ R j ≤ M . Let
A ν = { a ν , 1 > ⋯ > a ν , n ν > 0 } A_\nu=\{a_{\nu,1}>\cdots>a_{\nu,n_\nu}>0\} A ν = { a ν , 1 > ⋯ > a ν , n ν > 0 } be finite blocks such that
a ν , 1 → 0 , − log δ ν = o ( n ν ) , δ ν = min 1 ≤ i < n ν a ν , i − a ν , i + 1 a ν , 1 , a_{\nu,1}\to0,\qquad-\log\delta_\nu=o(n_\nu),\qquad
\delta_\nu=\min_{1\leq i<n_\nu}\frac{a_{\nu,i}-a_{\nu,i+1}}{a_{\nu,1}}, a ν , 1 → 0 , − log δ ν = o ( n ν ) , δ ν = 1 ≤ i < n ν min a ν , 1 a ν , i − a ν , i + 1 , and
( 1 + ∣ log δ ν ∣ log ( 1 / a ν , 1 ) ) ( log n ν + ∣ log δ ν ∣ ) = o ( n ν ) . (4) \left(1+\frac{\lvert\log\delta_\nu\rvert}{\log(1/a_{\nu,1})}\right)
\left(\log n_\nu+\lvert\log\delta_\nu\rvert\right)=o(n_\nu). \tag*{(4)} ( 1 + log ( 1/ a ν , 1 ) ∣ log δ ν ∣ ) ( log n ν + ∣ log δ ν ∣ ) = o ( n ν ) . (4) Then, for every ε , η ∈ ( 0 , 1 ) \varepsilon,\eta\in(0,1) ε , η ∈ ( 0 , 1 ) , and for all sufficiently large ν \nu ν , there is a measurable set F ⊂ [ 0 , 1 ] F\subset[0,1] F ⊂ [ 0 , 1 ] with
μ ( F ) > 1 − ε \mu(F)>1-\varepsilon μ ( F ) > 1 − ε such that the exceptional set
X ν ( F ) = { γ ∈ [ 0 , 1 ] : ∃ h ∈ V m , R , M , b , B such that γ + h ( a ν , i ) ∈ F for all 1 ≤ i ≤ n ν } X_\nu(F)=\{\gamma\in[0,1]:\exists h\in\mathcal{V}_{m,R,M,b,B}\text{ such that }\gamma+h(a_{\nu,i})\in F\text{ for all }1\leq i\leq n_\nu\} X ν ( F ) = { γ ∈ [ 0 , 1 ] : ∃ h ∈ V m , R , M , b , B such that γ + h ( a ν , i ) ∈ F for all 1 ≤ i ≤ n ν } satisfies μ ( X ν ( F ) ) < η \mu(X_\nu(F))<\eta μ ( X ν ( F )) < η .
Proof. We first record a uniform monotonicity estimate for h h h near 0 0 0 , uniform for h ∈ V m , R , M , b , B h\in\mathcal{V}_{m,R,M,b,B} h ∈ V m , R , M , b , B . Choose 0 < ρ < R 0<\rho<R 0 < ρ < R , depending only on m , R , M , b m,R,M,b m , R , M , b , so small that
R − m M sup j ≥ m + 1 j ( ρ R ) j − m ≤ m b 2 . R^{-m}M\sup_{j\geq m+1}j\left(\frac{\rho}{R}\right)^{j-m}\leq\frac{mb}{2}. R − m M j ≥ m + 1 sup j ( R ρ ) j − m ≤ 2 mb .
Claim 3.5. Every h ∈ V m , R , M , b , B h\in\mathcal{V}_{m,R,M,b,B} h ∈ V m , R , M , b , B is monotone on ( 0 , ρ ] (0,\rho] ( 0 , ρ ] , and for 0 < y < x ≤ ρ 0<y<x\leq\rho 0 < y < x ≤ ρ ,
∣ h ( x ) − h ( y ) ∣ ≥ b 2 ( x − y ) m . \lvert h(x)-h(y)\rvert\geq\frac{b}{2}(x-y)^m. ∣ h ( x ) − h ( y )∣ ≥ 2 b ( x − y ) m .
Proof of claim. Write
h ( t ) = ∑ j = m ∞ c j t j ∈ V m , R , M , b , B . h(t)=\sum_{j=m}^{\infty}c_jt^j\in\mathcal{V}_{m,R,M,b,B}. h ( t ) = j = m ∑ ∞ c j t j ∈ V m , R , M , b , B .
Since
∑ j = m ∞ ∣ c j ∣ R j ≤ M , \sum_{j=m}^{\infty}\lvert c_j\rvert R^j\leq M, j = m ∑ ∞ ∣ c j ∣ R j ≤ M ,
for 0 < t ≤ ρ 0 < t \le\rho 0 < t ≤ ρ we have
∣ ∑ j = m + 1 ∞ j c j t j − 1 ∣ ≤ t m − 1 R − m ∑ j = m + 1 ∞ j ∣ c j ∣ R j ( t R ) j − m ≤ t m − 1 R − m M sup j ≥ m + 1 j ( t R ) j − m ≤ m b 2 t m − 1 . \left|\sum_{j=m+1}^{\infty} jc_jt^{j-1}\right| \le t^{m-1}R^{-m}\sum_{j=m+1}^{\infty} j|c_j|R^j\left(\frac{t}{R}\right)^{j-m} \le t^{m-1}R^{-m}M\sup_{j\ge m+1}j\left(\frac{t}{R}\right)^{j-m} \le\frac{mb}{2}t^{m-1}. j = m + 1 ∑ ∞ j c j t j − 1 ≤ t m − 1 R − m j = m + 1 ∑ ∞ j ∣ c j ∣ R j ( R t ) j − m ≤ t m − 1 R − m M j ≥ m + 1 sup j ( R t ) j − m ≤ 2 mb t m − 1 .
Since ∣ c m ∣ ≥ b |c_m|\ge b ∣ c m ∣ ≥ b , it follows that h ′ ( t ) h'(t) h ′ ( t ) has the sign of c m c_m c m and
∣ h ′ ( t ) ∣ ≥ m b 2 t m − 1 ( 0 < t ≤ ρ ) . |h'(t)|\ge\frac{mb}{2}t^{m-1}\qquad(0<t\le\rho). ∣ h ′ ( t ) ∣ ≥ 2 mb t m − 1 ( 0 < t ≤ ρ ) .
Integrating from y y y to x x x gives
∣ h ( x ) − h ( y ) ∣ ≥ m b 2 ∫ y x t m − 1 d t = b 2 ( x m − y m ) ≥ b 2 ( x − y ) m . |h(x)-h(y)|\ge\frac{mb}{2}\int_y^x t^{m-1}\,dt=\frac{b}{2}(x^m-y^m)\ge\frac{b}{2}(x-y)^m. ∣ h ( x ) − h ( y ) ∣ ≥ 2 mb ∫ y x t m − 1 d t = 2 b ( x m − y m ) ≥ 2 b ( x − y ) m .
Fix a large ν \nu ν , and write
n = n ν , a i = a ν , i , δ = δ ν . n=n_\nu,\qquad a_i=a_{\nu,i},\qquad\delta=\delta_\nu. n = n ν , a i = a ν , i , δ = δ ν .
We may assume
a 1 < ρ , a 1 < R / 4. a_1<\rho,\qquad a_1<R/4. a 1 < ρ , a 1 < R /4.
Let
k = ⌊ 16 b ( a 1 δ ) m ⌋ . k=\left\lfloor\frac{16}{b(a_1\delta)^m}\right\rfloor. k = ⌊ b ( a 1 δ ) m 16 ⌋ .
Partition [ 0 , 1 ) [0,1) [ 0 , 1 ) into the intervals
I ℓ = [ ℓ k , ℓ + 1 k ) , 0 ≤ ℓ ≤ k − 1. I_\ell=\left[\frac{\ell}{k},\frac{\ell+1}{k}\right),\qquad0\le\ell\le k-1. I ℓ = [ k ℓ , k ℓ + 1 ) , 0 ≤ ℓ ≤ k − 1.
Choose 0 < θ < 1 / 4 0<\theta<1/4 0 < θ < 1/4 so small that
2 θ < ε / 4. 2\theta<\varepsilon/4. 2 θ < ε /4.
For each ℓ \ell ℓ , let
J ℓ = [ ℓ + θ k , ℓ + 1 − θ k ) ⊂ I ℓ . J_\ell=\left[\frac{\ell+\theta}{k},\frac{\ell+1-\theta}{k}\right)\subset I_\ell. J ℓ = [ k ℓ + θ , k ℓ + 1 − θ ) ⊂ I ℓ .
We keep each interval I ℓ I_\ell I ℓ independently with probability p = p ν p=p_\nu p = p ν , and define F F F to be the union of those J ℓ J_\ell J ℓ for which I ℓ I_\ell I ℓ was kept. Then
E μ ( F ) = p ( 1 − 2 θ ) . \mathbb{E}\mu(F)=p(1-2\theta). E μ ( F ) = p ( 1 − 2 θ ) .
Let L = L ν ≥ m L=L_\nu\ge m L = L ν ≥ m so large that
M ( a 1 R ) L + 1 ≤ θ 4 k . M\left(\frac{a_1}{R}\right)^{L+1}\le\frac{\theta}{4k}. M ( R a 1 ) L + 1 ≤ 4 k θ .
For each
h ( t ) = ∑ j = m ∞ c j t j ∈ V m , R , M , b , B , h(t)=\sum_{j=m}^{\infty}c_jt^j\in\mathcal{V}_{m,R,M,b,B}, h ( t ) = j = m ∑ ∞ c j t j ∈ V m , R , M , b , B ,
define the Taylor truncation
h L ( t ) : = ∑ j = m L c j t j . h_L(t):=\sum_{j=m}^{L}c_jt^j. h L ( t ) := j = m ∑ L c j t j .
Then, since ∑ j ≥ m + 1 ∣ c j ∣ R j ≤ M \sum_{j\ge m+1} |c_j|R^j \le M ∑ j ≥ m + 1 ∣ c j ∣ R j ≤ M , for 0 ≤ t ≤ a 1 0 \le t \le a_1 0 ≤ t ≤ a 1 we have
∣ h ( t ) − h L ( t ) ∣ ≤ ∑ j = L + 1 ∞ ∣ c j ∣ t j ≤ M ( a 1 R ) L + 1 ≤ θ 4 k . (5) |h(t)-h_L(t)| \le\sum_{j=L+1}^{\infty}|c_j|t^j \le M\left(\frac{a_1}{R}\right)^{L+1} \le\frac{\theta}{4k}. \tag*{(5)} ∣ h ( t ) − h L ( t ) ∣ ≤ j = L + 1 ∑ ∞ ∣ c j ∣ t j ≤ M ( R a 1 ) L + 1 ≤ 4 k θ . (5)
Since
k ≍ b , m ( a 1 δ ) − m , k \asymp_{b,m}(a_1\delta)^{-m}, k ≍ b , m ( a 1 δ ) − m ,
we may choose L L L so that, with
r : = L − m + 1 , r:=L-m+1, r := L − m + 1 ,
one has
r ≪ m , R , M , b , θ 1 + ∣ log δ ∣ log ( R / a 1 ) . (6) r \ll_{m,R,M,b,\theta} 1+\frac{|\log\delta|}{\log(R/a_1)}. \tag*{(6)} r ≪ m , R , M , b , θ 1 + log ( R / a 1 ) ∣ log δ ∣ . (6)
Indeed, after cancelling the common factor a 1 m a_1^m a 1 m , it is enough to force
( a 1 R ) L + 1 − m ≪ m , R , M , b , θ δ m . \left(\frac{a_1}{R}\right)^{L+1-m}\ll_{m,R,M,b,\theta}\delta^m. ( R a 1 ) L + 1 − m ≪ m , R , M , b , θ δ m .
Now fix γ ∈ [ 0 , 1 ] \gamma\in[0,1] γ ∈ [ 0 , 1 ] . Suppose that for some h ∈ V m , R , M , b , B h\in\mathcal{V}_{m,R,M,b,B} h ∈ V m , R , M , b , B one has
γ + h ( a i ) ∈ F ( 1 ≤ i ≤ n ) . \gamma+h(a_i)\in F\qquad(1\le i\le n). γ + h ( a i ) ∈ F ( 1 ≤ i ≤ n ) .
For each i i i , let ℓ i = ℓ i ( h ) \ell_i=\ell_i(h) ℓ i = ℓ i ( h ) be the unique integer in { 0 , … , k − 1 } \{0,\ldots,k-1\} { 0 , … , k − 1 } such that
γ + h ( a i ) ∈ J ℓ i . \gamma+h(a_i)\in J_{\ell_i}. γ + h ( a i ) ∈ J ℓ i .
Since J ℓ i J_{\ell_i} J ℓ i has distance at least θ / k \theta/k θ / k from the endpoints of I ℓ i I_{\ell_i} I ℓ i , and since inequality (5) holds, the point
γ + h L ( a i ) \gamma+h_L(a_i) γ + h L ( a i )
lies in the same partition interval I ℓ i I_{\ell_i} I ℓ i . Thus the interval pattern
π γ ( h ) : = ( ℓ 1 ( h ) , … , ℓ n ( h ) ) \pi_\gamma(h):=(\ell_1(h),\ldots,\ell_n(h)) π γ ( h ) := ( ℓ 1 ( h ) , … , ℓ n ( h ))
is one of the interval patterns arising from the truncated polynomials h L h_L h L .
We now count the possible interval patterns of the truncated polynomials. The coefficient vector
( c m , … , c L ) (c_m,\ldots,c_L) ( c m , … , c L )
has dimension
For fixed i i i , the interval containing
γ + h L ( a i ) \gamma+h_L(a_i) γ + h L ( a i )
is determined by which partition endpoints lie to its left. Equivalently, it is determined by the truth values of the affine inequalities
γ + c m a i m + c m + 1 a i m + 1 + ⋯ + c L a i L ≥ ℓ k . \gamma+c_m a_i^m+c_{m+1}a_i^{m+1}+\cdots+c_La_i^L\ge\frac{\ell}{k}. γ + c m a i m + c m + 1 a i m + 1 + ⋯ + c L a i L ≥ k ℓ .
For fixed i i i , as h h h ranges over V m , R , M , b , B \mathcal{V}_{m,R,M,b,B} V m , R , M , b , B , the set of possible values of h L ( a i ) h_L(a_i) h L ( a i ) is contained in an interval of length O R , M ( a i m ) O_{R,M}(a_i^m) O R , M ( a i m ) , hence in an interval of length O R , M ( a 1 m ) O_{R,M}(a_1^m) O R , M ( a 1 m ) . Since the partition endpoints are spaced by 1 / k 1/k 1/ k , only
O m , R , M , b ( k a 1 m + 1 ) = O m , R , M , b ( δ − m ) O_{m,R,M,b}(ka_1^m+1)=O_{m,R,M,b}(\delta^{-m}) O m , R , M , b ( k a 1 m + 1 ) = O m , R , M , b ( δ − m )
values of ℓ \ell ℓ can affect the interval containing γ + h L ( a i ) \gamma+ h_L(a_i) γ + h L ( a i ) . Therefore, as i i i ranges from 1 to n n n , the possible interval patterns are determined by at most
H ≪ m , R , M , b n δ − m H \ll_{m,R,M,b} n^{\delta-m} H ≪ m , R , M , b n δ − m
affine inequalities in r r r variables.
Since R > 0 R > 0 R > 0 is fixed and a 1 → 0 a_1 \to0 a 1 → 0 ,
log ( R / a 1 ) = log ( 1 / a 1 ) + O R ( 1 ) ∼ log ( 1 / a 1 ) . \log(R/a_1) = \log(1/a_1) + O_R(1) \sim\log(1/a_1). log ( R / a 1 ) = log ( 1/ a 1 ) + O R ( 1 ) ∼ log ( 1/ a 1 ) .
Thus the estimates (4) and (6) imply
r ( log n + ∣ log δ ∣ ) = o ( n ) , (7) r(\log n + |\log\delta|) = o(n), \tag*{(7)} r ( log n + ∣ log δ ∣ ) = o ( n ) , (7)
and in particular r = o ( n ) r = o(n) r = o ( n ) . Let
H 0 = C m , R , M , b n δ − m H_0 = C_{m,R,M,b}n^{\delta-m} H 0 = C m , R , M , b n δ − m
be an upper bound for H H H , with C m , R , M , b C_{m,R,M,b} C m , R , M , b chosen large enough that H 0 ≥ n H_0 \ge n H 0 ≥ n . For all sufficiently large ν \nu ν , we also have H 0 ≥ r H_0 \ge r H 0 ≥ r . By Lemma 3.1 , the number of possible interval patterns is at most
( r + 1 ) H 0 r ≤ exp ( O m , R , M , b ( r ( log n + ∣ log δ ∣ ) ) ) . (8) (r+1)H_0^r \le\exp\left(O_{m,R,M,b}\left(r(\log n+|\log\delta|)\right)\right). \tag*{(8)} ( r + 1 ) H 0 r ≤ exp ( O m , R , M , b ( r ( log n + ∣ log δ ∣ ) ) ) . (8)
By Claim 3.5, the values h ( a i ) h(a_i) h ( a i ) are separated by at least
b 2 ( a 1 δ ) m > 4 k . \frac{b}{2}(a_1\delta)^m > \frac{4}{k}. 2 b ( a 1 δ ) m > k 4 .
Hence, whenever
γ + h ( a i ) ∈ [ 0 , 1 ] ( 1 ≤ i ≤ n ) , \gamma+h(a_i)\in[0,1]\qquad(1\le i\le n), γ + h ( a i ) ∈ [ 0 , 1 ] ( 1 ≤ i ≤ n ) ,
the intervals
I ℓ 1 ( h ) , … , I ℓ n ( h ) I_{\ell_1}(h),\ldots,I_{\ell_n}(h) I ℓ 1 ( h ) , … , I ℓ n ( h )
are distinct. Therefore, for any fixed interval pattern which can arise, the probability that all corresponding intervals are kept is p n p^n p n . It follows from (8) that, uniformly in γ \gamma γ ,
P ( γ ∈ X ν ( F ) ) ≤ exp ( O m , R , M , b ( r ( log n + ∣ log δ ∣ ) ) ) p n . \mathbb{P}(\gamma\in X_\nu(F))\le\exp\left(O_{m,R,M,b}\left(r(\log n+|\log\delta|)\right)\right)p^n. P ( γ ∈ X ν ( F )) ≤ exp ( O m , R , M , b ( r ( log n + ∣ log δ ∣ ) ) ) p n .
After integrating over γ ∈ [ 0 , 1 ] \gamma\in[0,1] γ ∈ [ 0 , 1 ] , the same bound holds for E μ ( X ν ( F ) ) \mathbb{E}\mu(X_\nu(F)) E μ ( X ν ( F )) .
Put
S ν = C r ( log n + ∣ log δ ∣ ) , S_\nu= Cr(\log n+|\log\delta|), S ν = C r ( log n + ∣ log δ ∣ ) ,
where C C C is larger than the implicit constant in the last display. Since S ν = o ( n ) S_\nu=o(n) S ν = o ( n ) by estimate (7) , choose
p ν = exp ( − S ν + 1 n ) . p_\nu=\exp\left(-\sqrt{\frac{S_\nu+1}{n}}\right). p ν = exp ( − n S ν + 1 ) .
Then p ν → 1 p_\nu\to1 p ν → 1 , and
exp ( S ν ) p ν n = exp ( S ν − n ( S ν + 1 ) ) → 0. \exp(S_\nu)p_\nu^n=\exp\left(S_\nu-\sqrt{n(S_\nu+1)}\right)\to0. exp ( S ν ) p ν n = exp ( S ν − n ( S ν + 1 ) ) → 0.
Thus
E μ ( X ν ( F ) ) → 0. \mathbb{E}\mu(X_\nu(F))\to0. E μ ( X ν ( F )) → 0.
For all sufficiently large ν \nu ν ,
1 − p ν < ε / 4 , E μ ( X ν ( F ) ) < η / 4. 1-p_\nu<\varepsilon/4,\qquad\mathbb{E}\mu(X_\nu(F))<\eta/4. 1 − p ν < ε /4 , E μ ( X ν ( F )) < η /4.
Since 2 θ < ε / 4 2\theta<\varepsilon/4 2 θ < ε /4 , we have
E μ ( [ 0 , 1 ] ∖ F ) = 1 − p ν ( 1 − 2 θ ) ≤ ( 1 − p ν ) + 2 θ < ε / 2. \mathbb{E}\mu([0,1]\setminus F)=1-p_\nu(1-2\theta)\le(1-p_\nu)+2\theta<\varepsilon/2. E μ ([ 0 , 1 ] ∖ F ) = 1 − p ν ( 1 − 2 θ ) ≤ ( 1 − p ν ) + 2 θ < ε /2.
Markov’s inequality gives
P ( μ ( F ) ≤ 1 − ε ) < 1 2 , P ( μ ( X ν ( F ) ) ≥ η ) < 1 4 . \mathbb{P}\left(\mu(F) \le1-\varepsilon\right) < \frac{1}{2}, \qquad\mathbb{P}\left(\mu(X_\nu(F)) \ge\eta\right) < \frac{1}{4}. P ( μ ( F ) ≤ 1 − ε ) < 2 1 , P ( μ ( X ν ( F )) ≥ η ) < 4 1 .
Hence some realization satisfies
μ ( F ) > 1 − ε , μ ( X ν ( F ) ) < η , \mu(F) > 1-\varepsilon, \qquad\mu(X_\nu(F)) < \eta, μ ( F ) > 1 − ε , μ ( X ν ( F )) < η ,
as required. □
Proof of the analytic assertion in Theorem 1.4 . We now prove the analytic assertion. Choose finite blocks A ν = { a ν , 1 > ⋯ > a ν , n ν > 0 } A_\nu=\{a_{\nu,1}>\cdots>a_{\nu,n_\nu}>0\} A ν = { a ν , 1 > ⋯ > a ν , n ν > 0 } witnessing the additional hypothesis (1) ; thus these blocks satisfy the hypotheses of Lemma 3.4 . Enumerate all analytic windows
V j = V m j , R j , M j , b j , B j , \mathcal{V}_j=\mathcal{V}_{m_j,R_j,M_j,b_j,B_j}, V j = V m j , R j , M j , b j , B j ,
where
m j ∈ N , R j , M j , b j , B j ∈ Q > 0 , b j < B j . m_j\in\mathbb{N}, \qquad R_j,M_j,b_j,B_j\in\mathbb{Q}_{>0}, \qquad b_j<B_j. m j ∈ N , R j , M j , b j , B j ∈ Q > 0 , b j < B j .
This countable family covers every nonzero real-analytic function defined in a neighbourhood of 0 0 0 , after possibly restricting the function to a smaller neighbourhood. Indeed, if
h ( t ) = c m t m + c m + 1 t m + 1 + ⋯ h(t)=c_mt^m+c_{m+1}t^{m+1}+\cdots h ( t ) = c m t m + c m + 1 t m + 1 + ⋯
is nonzero and real analytic near 0 0 0 , then its power series has positive radius of convergence. Choose a rational R > 0 R>0 R > 0 smaller than this radius. Then
∑ j = m ∞ ∣ c j ∣ R j < ∞ . \sum_{j=m}^{\infty}|c_j|R^j<\infty. j = m ∑ ∞ ∣ c j ∣ R j < ∞.
Choose rational numbers M , b , B > 0 M,b,B>0 M , b , B > 0 such that
M > ∑ j = m ∞ ∣ c j ∣ R j , 0 < b < ∣ c m ∣ < B . M>\sum_{j=m}^{\infty}|c_j|R^j,\qquad0<b<|c_m|<B. M > j = m ∑ ∞ ∣ c j ∣ R j , 0 < b < ∣ c m ∣ < B .
Then h ∈ V m , R , M , b , B h\in\mathcal{V}_{m,R,M,b,B} h ∈ V m , R , M , b , B .
Choose positive numbers ε j , η j \varepsilon_j,\eta_j ε j , η j with
∑ j ε j < 1 4 , ∑ j η j < 1 8 . \sum_j\varepsilon_j<\frac{1}{4},\qquad\sum_j\eta_j<\frac{1}{8}. j ∑ ε j < 4 1 , j ∑ η j < 8 1 .
Apply Lemma 3.4 to each V j \mathcal{V}_j V j . We obtain measurable sets F j ⊂ [ 0 , 1 ] F_j\subset[0,1] F j ⊂ [ 0 , 1 ] and exceptional base-value sets X j ⊂ [ 0 , 1 ] X_j\subset[0,1] X j ⊂ [ 0 , 1 ] with
μ ( F j ) > 1 − ε j , μ ( X j ) < η j . \mu(F_j)>1-\varepsilon_j,\qquad\mu(X_j)<\eta_j. μ ( F j ) > 1 − ε j , μ ( X j ) < η j .
Set again
F = ⋂ j = 1 ∞ F j , X = ⋃ j = 1 ∞ X j . F=\bigcap_{j=1}^{\infty}F_j,\qquad X=\bigcup_{j=1}^{\infty}X_j. F = j = 1 ⋂ ∞ F j , X = j = 1 ⋃ ∞ X j .
Then μ ( F ) > 3 / 4 \mu(F)>3/4 μ ( F ) > 3/4 and μ ( X ) < 1 / 8 \mu(X)<1/8 μ ( X ) < 1/8 . Choose an open set G ⊃ X G\supset X G ⊃ X with μ ( G ) < 1 / 4 \mu(G)<1/4 μ ( G ) < 1/4 , and put E = F ∖ G E=F\setminus G E = F ∖ G . Then E E E has positive measure.
Suppose, for contradiction, that f ( A ) ⊂ E f(A)\subset E f ( A ) ⊂ E for some nonconstant real-analytic f f f defined near 0 0 0 . Write
f ( t ) = γ + h ( t ) , γ = f ( 0 ) , f(t)=\gamma+h(t),\qquad\gamma=f(0), f ( t ) = γ + h ( t ) , γ = f ( 0 ) ,
where h h h is analytic and not identically zero. Since a n → 0 a_n \to0 a n → 0 and E ⊂ [ 0 , 1 ] E \subset[0,1] E ⊂ [ 0 , 1 ] , we have f ( a n ) → f ( 0 ) = γ f(a_n) \to f(0) = \gamma f ( a n ) → f ( 0 ) = γ , so γ ∈ [ 0 , 1 ] \gamma\in[0,1] γ ∈ [ 0 , 1 ] . Choose j j j such that h ∈ V j h \in V_j h ∈ V j . The block used in constructing F j F_j F j is a subset of A A A , and E ⊂ F j E \subset F_j E ⊂ F j . Hence the definition of X j X_j X j gives γ ∈ X j ⊂ G \gamma\in X_j \subset G γ ∈ X j ⊂ G . Since G G G is open and f ( a ) → γ f(a) \to\gamma f ( a ) → γ along a ∈ A a \in A a ∈ A , a → 0 a \to0 a → 0 , we have f ( a ) ∈ G f(a) \in G f ( a ) ∈ G for all sufficiently small a ∈ A a \in A a ∈ A , contradicting f ( A ) ⊂ E = F ∖ G f(A) \subset E = F \setminus G f ( A ) ⊂ E = F ∖ G . This proves the analytic assertion. □
Proof of Corollary 1.6 and Theorem 1.7
Proof of Corollary 1.6
Proof of Corollary 1.6. We first prove that condition (i) implies the analytic hypothesis in Theorem 1.4 . Put
G n = max m ∈ T ( n ) ( a m − a m + 1 ) . G_n = \max_{m \in T(n)} (a_m-a_{m+1}). G n = m ∈ T ( n ) max ( a m − a m + 1 ) .
Choose n j → ∞ n_j \to\infty n j → ∞ such that, with
a = a n j , G = G n j , θ = G / a , a=a_{n_j}, \qquad G=G_{n_j}, \qquad\theta=G/a, a = a n j , G = G n j , θ = G / a ,
one has θ → 0 \theta\to0 θ → 0 . Every interval contained in [ a / 4 , a ] [a/4,a] [ a /4 , a ] of length greater than G G G contains at least one point of { a n j , a n j + 1 , … , a ℓ ( n j ) } \{a_{n_j},a_{n_j+1},\ldots,a_{\ell(n_j)}\} { a n j , a n j + 1 , … , a ℓ ( n j ) } ; otherwise the sequence would jump over such an interval, contradicting the definition of G G G .
Choose disjoint intervals
J r = ( a − ( 4 r + 2 ) G , a − 4 r G ] , 0 ≤ r < N , J_r=\left(a-(4r+2)G,a-4rG\right], \qquad0 \le r<N, J r = ( a − ( 4 r + 2 ) G , a − 4 r G ] , 0 ≤ r < N ,
where
N = ⌊ a 16 G ⌋ . N=\left\lfloor\frac{a}{16G}\right\rfloor. N = ⌊ 16 G a ⌋ .
Since θ → 0 \theta\to0 θ → 0 , we have N → ∞ N \to\infty N → ∞ and N ≍ θ − 1 N \asymp\theta^{-1} N ≍ θ − 1 . For j j j sufficiently large, all the intervals J r J_r J r are contained in [ a / 2 , a ] [a/2,a] [ a /2 , a ] . Since each J r J_r J r has length 2 G 2G 2 G , choose
y r ∈ A ∩ J r ( 0 ≤ r < N ) . y_r \in A \cap J_r \qquad(0 \le r<N). y r ∈ A ∩ J r ( 0 ≤ r < N ) .
Then B j = { y 0 > y 1 > ⋯ > y N − 1 } ⊂ A B_j=\{y_0>y_1>\cdots>y_{N-1}\}\subset A B j = { y 0 > y 1 > ⋯ > y N − 1 } ⊂ A , consecutive chosen points are separated by at least 2 G 2G 2 G , and y 0 ≤ a y_0\le a y 0 ≤ a . Hence
Δ ( B j ) ≥ 2 G a = 2 θ , ∣ B j ∣ = N ≍ 1 θ . \Delta(B_j)\ge\frac{2G}{a}=2\theta, \qquad|B_j|=N\asymp\frac{1}{\theta}. Δ ( B j ) ≥ a 2 G = 2 θ , ∣ B j ∣ = N ≍ θ 1 .
Therefore
∣ log Δ ( B j ) ∣ ≪ log 1 θ , log N ≪ log 1 θ , N ≫ 1 θ . |\log\Delta(B_j)|\ll\log\frac{1}{\theta}, \qquad\log N\ll\log\frac{1}{\theta}, \qquad N\gg\frac{1}{\theta}. ∣ log Δ ( B j ) ∣ ≪ log θ 1 , log N ≪ log θ 1 , N ≫ θ 1 .
It follows that − log Δ ( B j ) = o ( N ) -\log\Delta(B_j)=o(N) − log Δ ( B j ) = o ( N ) . Moreover y 0 ≤ a n j → 0 y_0\le a_{n_j}\to0 y 0 ≤ a n j → 0 , so log ( 1 / y 0 ) → ∞ \log(1/y_0)\to\infty log ( 1/ y 0 ) → ∞ , and for large j j j ,
( 1 + ∣ log Δ ( B j ) ∣ log ( 1 / y 0 ) ) ( log N + ∣ log Δ ( B j ) ∣ ) ≪ ( log 1 θ ) 2 = o ( 1 θ ) = o ( N ) . \left(1+\frac{|\log\Delta(B_j)|}{\log(1/y_0)}\right)\left(\log N+|\log\Delta(B_j)|\right)\ll\left(\log\frac{1}{\theta}\right)^2=o\left(\frac{1}{\theta}\right)=o(N). ( 1 + log ( 1/ y 0 ) ∣ log Δ ( B j ) ∣ ) ( log N + ∣ log Δ ( B j ) ∣ ) ≪ ( log θ 1 ) 2 = o ( θ 1 ) = o ( N ) .
Thus the analytic part of Theorem 1.4 applies.
It remains to show that (ii) and (iii) imply (i). If a n + 1 / a n → 1 a_{n+1}/a_n\to1 a n + 1 / a n → 1 , then for every ε > 0 \varepsilon>0 ε > 0 and all large m m m ,
a m − a m + 1 = a m ( 1 − a m + 1 a m ) ≤ ε a m . a_m-a_{m+1}=a_m\left(1-\frac{a_{m+1}}{a_m}\right)\le\varepsilon a_m. a m − a m + 1 = a m ( 1 − a m a m + 1 ) ≤ ε a m .
Hence for all large n n n and all m ≥ n m\ge n m ≥ n ,
a m − a m + 1 ≤ ε a m ≤ ε a n . a_m-a_{m+1}\le\varepsilon a_m\le\varepsilon a_n. a m − a m + 1 ≤ ε a m ≤ ε a n .
Taking the maximum over m ∈ T ( n ) m \in T(n) m ∈ T ( n ) and then letting ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 gives (i).
Finally assume (iii), and write g n = a n − a n + 1 g_n = a_n-a_{n+1} g n = a n − a n + 1 . Since
a n + 1 a n = 1 − g n a n , \frac{a_{n+1}}{a_n}=1-\frac{g_n}{a_n}, a n a n + 1 = 1 − a n g n ,
there is a sequence n j → ∞ n_j \to\infty n j → ∞ such that g n j / a n j → 0 g_{n_j}/a_{n_j} \to0 g n j / a n j → 0 . Let C 0 = max { C , 1 } C_0=\max\{C,1\} C 0 = max { C , 1 } . For m ∈ T ( n j ) m \in T(n_j) m ∈ T ( n j ) , we have m ≥ n j m \ge n_j m ≥ n j , and therefore
g m ≤ C 0 g n j . g_m \le C_0g_{n_j}. g m ≤ C 0 g n j .
Consequently
max m ∈ T ( n j ) ( a m − a m + 1 ) a n j ≤ C 0 g n j a n j → 0. \frac{\max_{m\in T(n_j)}(a_m-a_{m+1})}{a_{n_j}}\le C_0\frac{g_{n_j}}{a_{n_j}}\to0. a n j max m ∈ T ( n j ) ( a m − a m + 1 ) ≤ C 0 a n j g n j → 0.
Thus (i) holds, and the conclusion follows from the first part of the proof.
Proof of Theorem 1.7
Let ( b i ) (b_i) ( b i ) and ( c j ) (c_j) ( c j ) be two lacunary sequences with ratios q 1 , q 2 q_1,q_2 q 1 , q 2 and counting functions I ( W ) , J ( W ) I(W),J(W) I ( W ) , J ( W ) , respectively, and for σ ∈ { ± 1 } \sigma\in\{\pm1\} σ ∈ { ± 1 } define the (signed) near-additive energy
E σ ( W ) : = # { ( i , i ′ , j , j ′ ) : i , i ′ ≤ I ( W ) , j , j ′ ≤ J ( W ) , ∣ ( b i − b i ′ ) + σ ( d j − d j ′ ) ∣ ≤ exp ( − W ) } . E_\sigma(W):=\#\{(i,i',j,j'):i,i'\le I(W),\ j,j'\le J(W),\ |(b_i-b_{i'})+\sigma(d_j-d_{j'})|\le\exp(-W)\}. E σ ( W ) := # {( i , i ′ , j , j ′ ) : i , i ′ ≤ I ( W ) , j , j ′ ≤ J ( W ) , ∣ ( b i − b i ′ ) + σ ( d j − d j ′ ) ∣ ≤ exp ( − W )} .
The relevant estimate is as follows.
Lemma 4.1 ([6 ] , Lemma 19). With max ( q 1 , q 2 ) < 1 2 \max(q_1,q_2)<\frac{1}{2} max ( q 1 , q 2 ) < 2 1 there is a constant C = C ( q ) C=C(q) C = C ( q ) such that for either σ ∈ { ± 1 } \sigma\in\{\pm1\} σ ∈ { ± 1 }
E σ ( W ) ≤ C I ( W ) J ( W ) for all W > 0. E_\sigma(W)\le CI(W)J(W)\quad\text{for all }W>0. E σ ( W ) ≤ C I ( W ) J ( W ) for all W > 0.
One also defines the cross grid
G σ ( W ) : = { b i + σ c j : i ≤ I ( W ) , j ≤ J ( W ) } , σ ∈ { ± 1 } . G_\sigma(W):=\{b_i+\sigma c_j:i\le I(W),j\le J(W)\},\quad\sigma\in\{\pm1\}. G σ ( W ) := { b i + σ c j : i ≤ I ( W ) , j ≤ J ( W )} , σ ∈ { ± 1 } .
The following proposition may then be deduced from their argument.
Proposition 4.2. Let ( b i ) (b_i) ( b i ) and ( c j ) (c_j) ( c j ) be two positive lacunary sequences with ratios q 1 , q 2 q_1,q_2 q 1 , q 2 , respectively, and max ( q 1 , q 2 ) < 1 2 \max(q_1,q_2)<\frac{1}{2} max ( q 1 , q 2 ) < 2 1 . There are constants c 0 , c 1 > 0 c_0,c_1>0 c 0 , c 1 > 0 , depending only on the lacunary ratios of the sequences, such that for any sufficiently large W > 0 W>0 W > 0 and either σ ∈ { ± 1 } \sigma\in\{\pm1\} σ ∈ { ± 1 } , there is a c 1 exp ( − W ) c_1\exp(-W) c 1 exp ( − W ) -separated set
X W ⊂ G σ ( W ) X_W\subset G_\sigma(W) X W ⊂ G σ ( W ) with
∣ X W ∣ ≥ c 0 I ( W ) J ( W ) . |X_W|\ge c_0I(W)J(W). ∣ X W ∣ ≥ c 0 I ( W ) J ( W ) .
Proof. Partition [ 0 , 1 ] [0,1] [ 0 , 1 ] into n : = ⌈ exp ( W ) ⌉ n:=\lceil\exp(W)\rceil n := ⌈ exp ( W )⌉ intervals I 1 , ⋯ , I n I_1,\cdots,I_n I 1 , ⋯ , I n , each of length δ = 1 n \delta=\frac{1}{n} δ = n 1 . We have, by Cauchy–Schwarz,
I ( W ) J ( W ) = ∑ k = 1 n ∑ i ≤ I ( W ) j ≤ J ( W ) 1 ( b i + σ c j ∈ I k ) ≤ c ( W ) 1 / 2 ( ∑ k = 1 n ( ∑ i , j 1 ( b i + σ c j ∈ I k ) ) 2 ) 1 / 2 , I(W)J(W)=\sum_{k=1}^{n}\sum_{\substack{i\le I(W)\\j\le J(W)}}1(b_i+\sigma c_j\in I_k)\le c(W)^{1/2}\left(\sum_{k=1}^{n}\left(\sum_{i,j}1(b_i+\sigma c_j\in I_k)\right)^2\right)^{1/2}, I ( W ) J ( W ) = k = 1 ∑ n i ≤ I ( W ) j ≤ J ( W ) ∑ 1 ( b i + σ c j ∈ I k ) ≤ c ( W ) 1/2 k = 1 ∑ n ( i , j ∑ 1 ( b i + σ c j ∈ I k ) ) 2 1/2 ,
where c ( W ) c(W) c ( W ) is the number of cells that are occupied; that is,
c ( W ) : = ∑ j = 1 n 1 ( ∃ i , j : b i + σ c i ∈ I j ) . c(W):=\sum_{j=1}^{n}1(\exists i,j:b_i+\sigma c_i\in I_j). c ( W ) := j = 1 ∑ n 1 ( ∃ i , j : b i + σ c i ∈ I j ) .
Since
∑ k = 1 n ( ∑ i , j 1 ( b i + σ c i ∈ I k ) ) 2 ≤ E σ ( W ) ≤ C I ( W ) J ( W ) \sum_{k=1}^{n}\left(\sum_{i,j}\mathbf{1}(b_i+\sigma c_i\in I_k)\right)^2\le E_\sigma(W)\le C I(W)J(W) k = 1 ∑ n ( i , j ∑ 1 ( b i + σ c i ∈ I k ) ) 2 ≤ E σ ( W ) ≤ C I ( W ) J ( W )
one then has that
I ( W ) J ( W ) C ≤ c ( W ) . \frac{I(W)J(W)}{C}\le c(W). C I ( W ) J ( W ) ≤ c ( W ) .
For each occupied cell I k I_k I k , choose one pair ( i , j ) (i,j) ( i , j ) such that b i + σ c i b_i+\sigma c_i b i + σ c i lands in I k I_k I k . The resulting set ( b i + σ c j ) ( i , j ) c h o s e n (b_i+\sigma c_j)_{(i,j)\ \mathrm{chosen}} ( b i + σ c j ) ( i , j ) chosen we call X W X_W X W . □
We are now able to prove Theorem 1.7 .
Proof of Theorem 1.7 . Let ( b i ) (b_i) ( b i ) and ( c j ) (c_j) ( c j ) be two positive lacunary sequences with ratios q 1 , q 2 ∈ ( 0 , 1 ) q_1,q_2\in(0,1) q 1 , q 2 ∈ ( 0 , 1 ) and counting functions I ( W ) , J ( W ) I(W),J(W) I ( W ) , J ( W ) , respectively, such that
lim sup W → ∞ I ( W ) J ( W ) W = ∞ (9) \limsup_{W\to\infty}\frac{I(W)J(W)}{W}=\infty \tag*{(9)} W → ∞ lim sup W I ( W ) J ( W ) = ∞ (9)
We first thin these sequences and pass to a tail, in a way that will not change (9) . If q 1 ≥ 1 2 q_1\ge\frac{1}{2} q 1 ≥ 2 1 then set m : = ⌈ log q 1 log ( 1 / 4 ) ⌉ m:=\left\lceil\frac{\log q_1}{\log(1/4)}\right\rceil m := ⌈ l o g ( 1/4 ) l o g q 1 ⌉ and pass to the subsequence ( b m i ) i ∈ N (b_{mi})_{i\in\mathbb{N}} ( b mi ) i ∈ N ; similarly, if q 2 ≥ 1 2 q_2\ge\frac{1}{2} q 2 ≥ 2 1 , do likewise. This will not change (9) , since the counting functions change by at most a constant factor. Passing to a fixed tail also will not change (9) : if one starts at the R R R th and S S S th element of ( b i ) (b_i) ( b i ) and ( c j ) (c_j) ( c j ) , respectively, then the new counting functions are I ( W ) − R I(W)-R I ( W ) − R and J ( W ) − S J(W)-S J ( W ) − S . We claim that
lim sup W → ∞ ( I ( W ) − R ) ( J ( W ) − S ) W = ∞ \limsup_{W\to\infty}\frac{(I(W)-R)(J(W)-S)}{W}=\infty W → ∞ lim sup W ( I ( W ) − R ) ( J ( W ) − S ) = ∞
follows from (9) . Indeed, if I ( W ) , J ( W ) I(W),J(W) I ( W ) , J ( W ) are both unbounded, then this is obviously true; if at least one is bounded, then since max ( I ( W ) , J ( W ) ) ≤ C max { q 1 , q 2 } W \max(I(W),J(W))\le C_{\max\{q_1,q_2\}}W max ( I ( W ) , J ( W )) ≤ C m a x { q 1 , q 2 } W for the lacunary sequences ( b i ) (b_i) ( b i ) and ( c j ) (c_j) ( c j ) , one has a violation to (9) .
With this in mind, we may assume that max ( q 1 , q 2 ) < 1 2 \max(q_1,q_2)<\frac{1}{2} max ( q 1 , q 2 ) < 2 1 . We now construct the blocks to apply Theorem 1.4 . Let k ∈ N k\in\mathbb{N} k ∈ N ; since ( b i ) , ( c j ) (b_i),(c_j) ( b i ) , ( c j ) tend to zero we may choose tail indices R k , S k R_k,S_k R k , S k such that
b R k + c S k < 2 − k . b_{R_k}+c_{S_k}<2^{-k}. b R k + c S k < 2 − k .
Since
lim sup W → ∞ ( I ( W ) − R k ) ( J ( W ) − S k ) W = ∞ \limsup_{W\to\infty}\frac{(I(W)-R_k)(J(W)-S_k)}{W}=\infty W → ∞ lim sup W ( I ( W ) − R k ) ( J ( W ) − S k ) = ∞
we may find some W k W_k W k such that the following three points hold:
( I ( W k ) − R k ) ( J ( W k ) − S k ) W k ≥ 8 c 0 − 1 k , \frac{(I(W_k)-R_k)(J(W_k)-S_k)}{W_k}\ge8c_0^{-1}k, W k ( I ( W k ) − R k ) ( J ( W k ) − S k ) ≥ 8 c 0 − 1 k ,
where c 0 c_0 c 0 is the constant in Proposition 4.2
W k W_k W k is large enough to appear in Proposition 4.2
I ( W k ) ≥ 2 R k I(W_k)\ge2R_k I ( W k ) ≥ 2 R k , J ( W k ) ≥ 2 S k J(W_k)\ge2S_k J ( W k ) ≥ 2 S k .
By Proposition 4.2, there are c 0 , c 1 > 0 c_0,c_1>0 c 0 , c 1 > 0 depending only on q 1 , q 2 q_1,q_2 q 1 , q 2 , such that there is a c 1 exp ( − W k ) c_1\exp(-W_k) c 1 exp ( − W k ) -separated set
X W k ⊂ { b i + σ c j : R k ≤ i ≤ I ( W k ) , S k ≤ j ≤ J ( W k ) } X_{W_k}\subset\{b_i+\sigma c_j:R_k\le i\le I(W_k),\ S_k\le j\le J(W_k)\} X W k ⊂ { b i + σ c j : R k ≤ i ≤ I ( W k ) , S k ≤ j ≤ J ( W k )}
with ∣ X W k ∣ ≥ c 0 I ( W k ) J ( W k ) |X_{W_k}|\ge c_0I(W_k)J(W_k) ∣ X W k ∣ ≥ c 0 I ( W k ) J ( W k ) . Thus,
N k : = ∣ X W k ∣ ≥ c 0 I ( W k ) J ( W k ) = c 0 ( 1 − R k I ( W k ) ) − 1 ( 1 − S k J ( W k ) ) − 1 ( I ( W k ) − R k ) ( J ( W k ) − S k ) ≥ 32 k W k . \begin{aligned}
N_k:=|X_{W_k}|&\ge c_0I(W_k)J(W_k)\\
&=c_0\left(1-\frac{R_k}{I(W_k)}\right)^{-1}\left(1-\frac{S_k}{J(W_k)}\right)^{-1}(I(W_k)-R_k)(J(W_k)-S_k)\\
&\ge32kW_k.
\end{aligned} N k := ∣ X W k ∣ ≥ c 0 I ( W k ) J ( W k ) = c 0 ( 1 − I ( W k ) R k ) − 1 ( 1 − J ( W k ) S k ) − 1 ( I ( W k ) − R k ) ( J ( W k ) − S k ) ≥ 32 k W k .
We have that
Δ k : = min x , y ∈ X W k x ≠ y ∣ x − y ∣ max X W k ≥ exp ( − W k ) \Delta_k:=\min_{\substack{x,y\in X_{W_k}\\x\ne y}}\frac{|x-y|}{\max X_{W_k}}\ge\exp(-W_k) Δ k := x , y ∈ X W k x = y min max X W k ∣ x − y ∣ ≥ exp ( − W k )
and so − log ( Δ k ) = o ( N k ) -\log(\Delta_k)=o(N_k) − log ( Δ k ) = o ( N k ) . Taking k → ∞ k\to\infty k → ∞ , we may then apply Theorem 1.4 to produce the desired result. □ \square □
Degree-d polynomial non-universality for (d+3)A
Let us discuss the roadmap for the proof of Theorem 1.8. Once and for all, choose distinct fixed points b 1 , ⋯ , b d ∈ A b_1,\cdots,b_d\in A b 1 , ⋯ , b d ∈ A . Since any polynomial P P P of degree at most d d d has at most d − 1 d-1 d − 1 critical points, any such polynomial cannot be flat on all of these fixed points. Restricting to a compact box of coordinates, one has uniformity in this observation, in that one of these points b ℓ b_\ell b ℓ has a neighborhood on which P P P roughly preserves distances.
Inside this neighborhood, we use points
b ℓ + a i 1 + ⋯ + a i d + 2 , i 1 < ⋯ < i d + 1 b_\ell+a_{i_1}+\cdots+a_{i_{d+2}},\qquad i_1<\cdots<i_{d+1} b ℓ + a i 1 + ⋯ + a i d + 2 , i 1 < ⋯ < i d + 1
with rapidly decreasing elements a j ∈ L ⊂ A a_j\in L\subset A a j ∈ L ⊂ A . For a fixed b ℓ b_\ell b ℓ , there are ( ∣ L ∣ d + 2 ) \binom{|L|}{d+2} ( d + 2 ∣ L ∣ ) such points.
A degree-d d d polynomial on b ℓ + ( d + 2 ) L b_\ell+(d+2)L b ℓ + ( d + 2 ) L has O ( ∣ L ∣ d + 1 ) O(|L|^{d+1}) O ( ∣ L ∣ d + 1 ) degrees of freedom, and so an approximation net for the total space of configurations has size O ( ∣ L ∣ d + 1 log ∣ L ∣ ) O(|L|^{d+1}\log|L|) O ( ∣ L ∣ d + 1 log ∣ L ∣ ) , whereas the number of separated points is of order ∣ L ∣ d + 2 |L|^{d+2} ∣ L ∣ d + 2 . This gap between the two quantities allows one to construct a small random set that hits every configuration. Finally, a slicing argument gives the full set E E E .
Definition 5.1. For a polynomial P P P with degree at most d d d , we say that b ∈ { b 1 , ⋯ , b d } b\in\{b_1,\cdots,b_d\} b ∈ { b 1 , ⋯ , b d } is a noncritical point if P ′ ( b ) ≠ 0 P'(b)\ne0 P ′ ( b ) = 0 .
We first specialize to the compact family
P : = { P ( y ) = ∑ k = 1 d t k y k : 1 ≤ max 1 ≤ k ≤ d ∣ t k ∣ ≤ 2 } . \mathcal{P}:=\left\{P(y)=\sum_{k=1}^{d}t_ky^k:1\le\max_{1\le k\le d}|t_k|\le2\right\}. P := { P ( y ) = k = 1 ∑ d t k y k : 1 ≤ 1 ≤ k ≤ d max ∣ t k ∣ ≤ 2 } .
Lemma 5.2. There are constants 0 < c ≤ C 0<c\le C 0 < c ≤ C and 0 < η ≤ 1 0<\eta\le1 0 < η ≤ 1 such that every P ∈ P P\in\mathcal{P} P ∈ P has a noncritical point b P = b ( P ) ∈ { b 1 , ⋯ , b d } b_P=b(P)\in\{b_1,\cdots,b_d\} b P = b ( P ) ∈ { b 1 , ⋯ , b d } satisfying
c ≤ ∣ P ′ ( b P + s ) ∣ ≤ C ( 0 ≤ s ≤ η ) . c\le|P'(b_P+s)|\le C\qquad(0\le s\le\eta). c ≤ ∣ P ′ ( b P + s ) ∣ ≤ C ( 0 ≤ s ≤ η ) . For any such point,
c ∣ s − s ′ ∣ ≤ ∣ P ( b P + s ) − P ( b P + s ′ ) ∣ ≤ C ∣ s − s ′ ∣ ( s , s ′ ∈ [ 0 , η ] ) . c|s-s'|\le|P(b_P+s)-P(b_P+s')|\le C|s-s'|\qquad(s,s'\in[0,\eta]). c ∣ s − s ′ ∣ ≤ ∣ P ( b P + s ) − P ( b P + s ′ ) ∣ ≤ C ∣ s − s ′ ∣ ( s , s ′ ∈ [ 0 , η ]) .
Proof. The function ϕ : P → R \phi:\mathcal{P}\to\mathbb{R} ϕ : P → R taking P P P to max ℓ ∣ P ′ ( b ℓ ) ∣ \max_{\ell}|P'(b_\ell)| max ℓ ∣ P ′ ( b ℓ ) ∣ is strictly positive: otherwise P ′ P' P ′ would have d d d distinct zeroes and degree at most d − 1 d-1 d − 1 , forcing P ′ = 0 P'=0 P ′ = 0 , a contradiction. By compactness, then,
min P ∈ P max ℓ ∣ P ′ ( b ℓ ) ∣ = c ′ > 0. (10) \min_{P\in\mathcal{P}}\max_{\ell}|P'(b_\ell)|=c'>0. \tag*{(10)} P ∈ P min ℓ max ∣ P ′ ( b ℓ ) ∣ = c ′ > 0. (10)
The quantities ∣ P ′ ∣ |P'| ∣ P ′ ∣ and ∣ P ′ ′ ∣ |P''| ∣ P ′′ ∣ are uniformly bounded on [ 0 , 2 ] [0,2] [ 0 , 2 ] for P ∈ P P\in\mathcal{P} P ∈ P . Choose an upper bound C ≥ c ′ C\ge c' C ≥ c ′ there. Uniform continuity of P ′ P' P ′ gives 0 < η ≤ 1 0<\eta\le1 0 < η ≤ 1 such that
∣ P ′ ( b ℓ + s ) − P ′ ( b ℓ ) ∣ ≤ c ′ / 2 , ( P ∈ P , 1 ≤ ℓ ≤ d , 0 ≤ s ≤ η ) (11) |P'(b_\ell+s)-P'(b_\ell)|\le c'/2,\qquad(P\in\mathcal{P},\ 1\le\ell\le d,\ 0\le s\le\eta) \tag*{(11)} ∣ P ′ ( b ℓ + s ) − P ′ ( b ℓ ) ∣ ≤ c ′ /2 , ( P ∈ P , 1 ≤ ℓ ≤ d , 0 ≤ s ≤ η ) (11)
Given P ∈ P P\in\mathcal{P} P ∈ P , we may find some ℓ \ell ℓ such that ∣ P ′ ( b ℓ ) ∣ ≥ c ′ |P'(b_\ell)|\ge c' ∣ P ′ ( b ℓ ) ∣ ≥ c ′ by (10) , and so by (11) ,
∣ P ′ ( b ℓ + s ) ∣ ≥ ∣ P ′ ( b ℓ ) ∣ − ∣ P ′ ( b ℓ + s ) − P ′ ( b ℓ ) ∣ ≥ c ′ / 2 , ( 0 ≤ s ≤ η ) . |P'(b_\ell+s)|\ge|P'(b_\ell)|-|P'(b_\ell+s)-P'(b_\ell)|\ge c'/2,\qquad(0\le s\le\eta). ∣ P ′ ( b ℓ + s ) ∣ ≥ ∣ P ′ ( b ℓ ) ∣ − ∣ P ′ ( b ℓ + s ) − P ′ ( b ℓ ) ∣ ≥ c ′ /2 , ( 0 ≤ s ≤ η ) .
Setting c = c ′ / 2 c=c'/2 c = c ′ /2 then provides the first part of the lemma. The mean value theorem then gives the second part. □ \square □
We now set up the family of points. Choose a lacunary family L ⊂ A L\subset A L ⊂ A of points, disjoint from { b 1 , … , b d } \{b_1,\ldots,b_d\} { b 1 , … , b d } in the following manner:
L = { a J < a J − 1 < ⋯ < a 1 < η / 2 } , 0 < a j + 1 ≤ a j / 100 ( 1 ≤ j < J ) . L=\{a_J<a_{J-1}<\cdots<a_1<\eta/2\},\qquad0<a_{j+1}\le a_j/100\quad(1\le j<J). L = { a J < a J − 1 < ⋯ < a 1 < η /2 } , 0 < a j + 1 ≤ a j /100 ( 1 ≤ j < J ) .
For I ⊂ [ J ] I\subset[J] I ⊂ [ J ] with ∣ I ∣ = d + 2 |I|=d+2 ∣ I ∣ = d + 2 , set s I : = ∑ j ∈ I a j s_I:=\sum_{j\in I}a_j s I := ∑ j ∈ I a j . Note that each s I s_I s I lies in [ 0 , η ] [0,\eta] [ 0 , η ] . If I ≠ I ′ I\ne I' I = I ′ , by considering their first differing index and the lacunary nature of L L L , the set ( s I ) I ⊂ [ J ] (s_I)_{I\subset[J]} ( s I ) I ⊂ [ J ] has ( J d + 2 ) \binom{J}{d+2} ( d + 2 J ) distinct elements, separated by at least Ω ( a J ) \Omega(a_J) Ω ( a J ) . For a sufficiently large constant C d ≥ 1 C_d\ge1 C d ≥ 1 depending on d d d , we define the lacunary vector v ∈ T J v\in\mathbb{T}^J v ∈ T J by
v : = 1 C d ( a 1 a 2 ⋮ a J ) . v:=\frac{1}{C_d}
\begin{pmatrix}
a_1\\
a_2\\
\vdots\\
a_J
\end{pmatrix}. v := C d 1 a 1 a 2 ⋮ a J .
For P ∈ P P\in\mathcal{P} P ∈ P , let b P ∈ { b 1 , … , b d } b_P\in\{b_1,\ldots,b_d\} b P ∈ { b 1 , … , b d } denote a choice of noncritical point given by Lemma 5.2 . Our total space of configurations will be
C : = ( z + ( P ( b P + s I ) − P ( b P ) ) v ) I ⊂ [ J ] , ∣ I ∣ = d + 2 , z ∈ T J , P ∈ P . \mathcal{C}:=\left(z+\left(P(b_P+s_I)-P(b_P)\right)v\right)_{I\subset[J],\,|I|=d+2},\qquad z\in\mathbb{T}^J,\ P\in\mathcal{P}. C := ( z + ( P ( b P + s I ) − P ( b P ) ) v ) I ⊂ [ J ] , ∣ I ∣ = d + 2 , z ∈ T J , P ∈ P .
For each fixed ( z , P ) (z,P) ( z , P ) pair, we view this as a list of vectors in T J \mathbb{T}^J T J . Equivalently,
C = ⋃ z ∈ T J P ∈ P C z , P , where C z , P : = ( z + ( P ( b P + s I ) − P ( b P ) ) v ) I ⊂ [ J ] , ∣ I ∣ = d + 2 . \mathcal{C}=\bigcup_{\substack{z\in\mathbb{T}^J\\P\in\mathcal{P}}}\mathcal{C}_{z,P},
\qquad\text{where}\qquad
\mathcal{C}_{z,P}:=\left(z+\left(P(b_P+s_I)-P(b_P)\right)v\right)_{I\subset[J],\,|I|=d+2}. C = z ∈ T J P ∈ P ⋃ C z , P , where C z , P := ( z + ( P ( b P + s I ) − P ( b P ) ) v ) I ⊂ [ J ] , ∣ I ∣ = d + 2 .
We endow the space of configurations with an appropriate metric by setting
d ( C z , P , C z ′ , Q ) : = max I ⊂ [ J ] ∣ I ∣ = d + 2 ∥ ( z + P ( b P + s I ) − P ( b P ) ) v − ( z ′ + Q ( b Q + s I ) − Q ( b Q ) ) v ∥ L ∞ ( T J ) . d(\mathcal{C}_{z,P},\mathcal{C}_{z',Q}):=\max_{\substack{I\subset[J]\\|I|=d+2}}\left\|(z+P(b_P+s_I)-P(b_P))v-(z'+Q(b_Q+s_I)-Q(b_Q))v\right\|_{L^\infty(\mathbb{T}^J)}. d ( C z , P , C z ′ , Q ) := I ⊂ [ J ] ∣ I ∣ = d + 2 max ∥ ( z + P ( b P + s I ) − P ( b P )) v − ( z ′ + Q ( b Q + s I ) − Q ( b Q )) v ∥ L ∞ ( T J ) .
We first claim that C \mathcal{C} C is adequate for the purposes of representing every degree-d d d configuration.
Lemma 5.3. Suppose there exists a set H ⊂ T J H\subset\mathbb{T}^J H ⊂ T J such that, for each z ∈ T J z\in\mathbb{T}^J z ∈ T J and P ∈ P P\in\mathcal{P} P ∈ P , there exists some I ⊂ [ J ] I\subset[J] I ⊂ [ J ] with ∣ I ∣ = d + 2 |I|=d+2 ∣ I ∣ = d + 2 such that
z + ( P ( b P + s I ) − P ( b P ) ) v ∈ H . z+\left(P(b_P+s_I)-P(b_P)\right)v\in H. z + ( P ( b P + s I ) − P ( b P ) ) v ∈ H .
Then, for every x ∈ T J x \in\mathbb{T}^{J} x ∈ T J and P ∈ P P \in\mathcal{P} P ∈ P there exists some y ∈ ( d + 3 ) A y \in(d+3)A y ∈ ( d + 3 ) A such that
x + P ( y ) v ∈ H . x + P(y)v \in H. x + P ( y ) v ∈ H .
Proof. Given x ∈ T J x \in\mathbb{T}^{J} x ∈ T J and P ∈ P P \in\mathcal{P} P ∈ P , set z = x + P ( b P ) v z=x+P(b_P)v z = x + P ( b P ) v . Then, by assumption there exists some I ⊂ [ J ] I \subset[J] I ⊂ [ J ] with ∣ I ∣ = d + 2 |I|=d+2 ∣ I ∣ = d + 2 such that x + P ( b P + s I ) v ∈ H x+P(b_P+s_I)v \in H x + P ( b P + s I ) v ∈ H . Since b P + s I ∈ ( d + 3 ) A b_P+s_I \in(d+3)A b P + s I ∈ ( d + 3 ) A , setting y = b P + s I y=b_P+s_I y = b P + s I provides the result. □
We now show we have the desired separation within each configuration.
Lemma 5.4. There exists an absolute constant ρ > 0 \rho>0 ρ > 0 depending only on c c c and C C C in Lemma 5.2 such that, for fixed z ∈ T J z \in\mathbb{T}^{J} z ∈ T J and P ∈ P P \in\mathcal{P} P ∈ P , and letting I I I vary over subsets of [ J ] [J] [ J ] with size d + 2 d+2 d + 2 , the points
z + P ( ( b P + s I ) − P ( b P ) ) v z+P\bigl((b_P+s_I)-P(b_P)\bigr)v z + P ( ( b P + s I ) − P ( b P ) ) v are ρ \rho ρ -separated.
Proof. Take I ≠ I ′ I \ne I' I = I ′ with ∣ I ∣ = ∣ I ′ ∣ = d + 2 |I|=|I'|=d+2 ∣ I ∣ = ∣ I ′ ∣ = d + 2 . Let m m m be their first differing index of I I I , I ′ I' I ′ ; then by Lemma 5.2 and the definition above,
c ∣ s I − s I ′ ∣ ≤ ∣ P ( b P + s I ) − P ( b P + s I ′ ) ∣ ≤ C ∣ s I − s I ′ ∣ . c|s_I-s_{I'}| \leq|P(b_P+s_I)-P(b_P+s_{I'})| \leq C|s_I-s_{I'}|. c ∣ s I − s I ′ ∣ ≤ ∣ P ( b P + s I ) − P ( b P + s I ′ ) ∣ ≤ C ∣ s I − s I ′ ∣.
Since ∣ s I − s I ′ ∣ = Θ ( a m ) |s_I-s_{I'}|=\Theta(a_m) ∣ s I − s I ′ ∣ = Θ ( a m ) , by definition of v v v one has that
∥ P ( b P + s I ) − P ( b P + s I ′ ) ∥ ∞ = Ω c , C ( 1 ) . \left\|P(b_P+s_I)-P(b_P+s_{I'})\right\|_\infty=\Omega_{c,C}(1). ∥ P ( b P + s I ) − P ( b P + s I ′ ) ∥ ∞ = Ω c , C ( 1 ) .
Set ρ \rho ρ to be the lower bound here. □
We now want to control the space of configurations C \mathcal{C} C with a finite number of representatives, with respect to the aforementioned metric. Let us define an h h h -net of C \mathcal{C} C to be a finite subset C 0 ⊂ C \mathcal{C}_0 \subset\mathcal{C} C 0 ⊂ C of representatives, such that
C z , P ∈ C ⟹ there exists some C z ′ , Q ∈ C 0 such that d ( C z , P , C z ′ , Q ) ≤ h . \mathcal{C}_{z,P} \in\mathcal{C} \Longrightarrow\text{ there exists some } \mathcal{C}_{z',Q} \in\mathcal{C}_0 \text{ such that } d(\mathcal{C}_{z,P},\mathcal{C}_{z',Q}) \leq h. C z , P ∈ C ⟹ there exists some C z ′ , Q ∈ C 0 such that d ( C z , P , C z ′ , Q ) ≤ h .
Lemma 5.5. For h ∈ ( 0 , 1 ) h \in(0,1) h ∈ ( 0 , 1 ) , the entire space of configurations C \mathcal{C} C admits an h h h -net C 0 \mathcal{C}_0 C 0 of size
∣ C 0 ∣ ≪ d h − O d ( J d + 1 ) . |\mathcal{C}_0| \ll_d h^{-O_d(J^{d+1})}. ∣ C 0 ∣ ≪ d h − O d ( J d + 1 ) .
Proof. Fix some b ∈ { b 1 , … , b d } b \in\{b_1,\ldots,b_d\} b ∈ { b 1 , … , b d } ; by the union bound it suffices to show that the set
( z + ( P ( b + s I ) − P ( b ) ) v ) I ⊂ [ J ] ∣ I ∣ = d + 2 , z ∈ T J , P ∈ P \left(z+\bigl(P(b+s_I)-P(b)\bigr)v\right)_{\substack{I\subset[J]\\ |I|=d+2}},\quad z\in\mathbb{T}^{J},\ P\in\mathcal{P} ( z + ( P ( b + s I ) − P ( b ) ) v ) I ⊂ [ J ] ∣ I ∣ = d + 2 , z ∈ T J , P ∈ P
admits an h h h -net of the same size (up to a constant depending on d d d ). We may expand
P ( b + s I ) − P ( b ) = ∑ k = 1 d c k ( b , P ) ( s I ) k P(b+s_I)-P(b)=\sum_{k=1}^{d}c_k(b,P)(s_I)^k P ( b + s I ) − P ( b ) = k = 1 ∑ d c k ( b , P ) ( s I ) k
for some coefficients c 1 ( b , P ) , … , c k ( b , P ) c_1(b,P),\ldots,c_k(b,P) c 1 ( b , P ) , … , c k ( b , P ) depending only on b b b and P P P , and so
P ( b + s I ) − P ( b ) = ∑ k = 1 d c k ( b , P ) ( ∑ j ∈ I a j ) k = ∑ k = 1 d ∑ j 1 , … , j k ∈ I c k ( b , P ) a j 1 ⋯ a j k . P(b+s_I)-P(b)=\sum_{k=1}^{d}c_k(b,P)\left(\sum_{j\in I}a_j\right)^k
=\sum_{k=1}^{d}\sum_{j_1,\ldots,j_k\in I}c_k(b,P)a_{j_1}\cdots a_{j_k}. P ( b + s I ) − P ( b ) = k = 1 ∑ d c k ( b , P ) j ∈ I ∑ a j k = k = 1 ∑ d j 1 , … , j k ∈ I ∑ c k ( b , P ) a j 1 ⋯ a j k .
Consequently, the i i i th entry of z + ( P ( b + s I ) − P ( b ) ) v z+(P(b+s_I)-P(b))v z + ( P ( b + s I ) − P ( b )) v is
z i + ∑ k = 1 d ∑ j 1 , … , j k ∈ I c k ′ ( b , P ) a j 1 ⋯ a j k a i , c k ′ : = c k C d . (12) z_i+\sum_{k=1}^{d}\sum_{j_1,\ldots,j_k\in I}c'_k(b,P)\frac{a_{j_1}\cdots a_{j_k}}{a_i},\qquad c'_k:=\frac{c_k}{C_d}. \tag*{(12)} z i + k = 1 ∑ d j 1 , … , j k ∈ I ∑ c k ′ ( b , P ) a i a j 1 ⋯ a j k , c k ′ := C d c k . (12)
Consider the map
ϕ : ( P , z ) ↦ ( z i , c k ′ ( b , P ) a j 1 ⋯ a j k a i ) 1 ≤ i , j 1 , … , j k ≤ J 1 ≤ k ≤ d \phi: (P,z) \mapsto\left(z_i,c'_k(b,P)\frac{a_{j_1}\cdots a_{j_k}}{a_i}\right)_{\substack{1\le i,j_1,\ldots,j_k\le J\\1\le k\le d}} ϕ : ( P , z ) ↦ ( z i , c k ′ ( b , P ) a i a j 1 ⋯ a j k ) 1 ≤ i , j 1 , … , j k ≤ J 1 ≤ k ≤ d
(at possible abuse of notation, the image of ϕ \phi ϕ here is a single vector). This image has O ( J d + 2 ) O(J^{d+2}) O ( J d + 2 ) coordinates, and so lies in T M \mathbb{T}^M T M with M = O ( J d + 2 ) M=O(J^{d+2}) M = O ( J d + 2 ) . For a constant c 0 ( d ) c_0(d) c 0 ( d ) to be determined, partition this image space T M \mathbb{T}^M T M into ⌈ c 0 ( d ) h ⌉ M \left\lceil\frac{c_0(d)}{h}\right\rceil^M ⌈ h c 0 ( d ) ⌉ M boxes by partitioning each coordinate into ⌈ c 0 ( d ) h ⌉ \left\lceil\frac{c_0(d)}{h}\right\rceil ⌈ h c 0 ( d ) ⌉ boxes. For each box B B B in the image space, choose some representative ( P , z ) (P,z) ( P , z ) such that ϕ ( P , z ) ∈ B \phi(P,z)\in B ϕ ( P , z ) ∈ B . In such a way, every ( P , z ) (P,z) ( P , z ) in the preimage has a representative ( Q , z ′ ) (Q,z') ( Q , z ′ ) such that ϕ ( ( P , z ) ) \phi((P,z)) ϕ (( P , z )) and ϕ ( ( Q , z ′ ) ) \phi((Q,z')) ϕ (( Q , z ′ )) lie in the same box. The map (12) is linear in the entries of ϕ ( ( P , z ) ) \phi((P,z)) ϕ (( P , z )) , and so by definition of the chosen representative one obtains the desired bound by applying the triangle inequality and choosing C 0 C_0 C 0 to be the set of representatives. □
We can now construct an arbitrarily small set that hits every configuration.
Proposition 5.6. For every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , some J ≫ d 1 J\gg_d 1 J ≫ d 1 , there exists a closed set H ⊂ T J H\subset\mathbb{T}^J H ⊂ T J such that μ ( H ) ≤ δ \mu(H)\le\delta μ ( H ) ≤ δ and for every z ∈ T J z\in\mathbb{T}^J z ∈ T J , P ∈ P P\in\mathcal{P} P ∈ P , z + P ( b P + s I ) v ∈ H z+P(b_P+s_I)\mathbf{v}\in H z + P ( b P + s I ) v ∈ H for some I ⊂ [ J ] I\subset[J] I ⊂ [ J ] , ∣ I ∣ = d + 2 |I|=d+2 ∣ I ∣ = d + 2 .
Proof. Let ρ \rho ρ be the lower bound for the separation in Lemma 5.4, and fix an integer k > 1 / ρ k>1/\rho k > 1/ ρ . For a sufficiently large J J J to be chosen, partition T J \mathbb{T}^J T J into k J k^J k J half-open cubes of side length 1 / k 1/k 1/ k . Select each cube independently with probability p p p . Set h : = 1 k J h:=\frac{1}{kJ} h := k J 1 and let H H H be the union of the closed h h h -neighborhoods of the selected cubes. This is a closed set, with expected measure
E μ ( H ) ≤ p k J ( 1 / k + 2 h ) J = p ( 1 + 2 h k ) J ≤ e p . \mathbb{E}_{\mu}(H)\le pk^J(1/k+2h)^J=p(1+2hk)^J\le ep. E μ ( H ) ≤ p k J ( 1/ k + 2 h ) J = p ( 1 + 2 hk ) J ≤ e p .
Take the net from Lemma 5.5 with radius h h h . By Lemma 5.4, each representative in this net has ( J d + 2 ) \binom{J}{d+2} ( d + 2 J ) points in distinct cubes, since a cube has diameter at most 1 / k < ρ 1/k<\rho 1/ k < ρ . The probability that a particular representative has no point in a selected cube is at most
( 1 − p ) ( J d + 2 ) ≤ exp ( − p ( J d + 2 ) ) . (1-p)^{\binom{J}{d+2}}\le\exp\left(-p\binom{J}{d+2}\right). ( 1 − p ) ( d + 2 J ) ≤ exp ( − p ( d + 2 J ) ) .
The union bound then gives
P ( some representative is missed ) ≪ d h − O d ( J d + 1 ) exp ( − p ( J d + 2 ) ) \mathbb{P}(\text{some representative is missed})\ll_d h^{-O_d(J^{d+1})}\exp\left(-p\binom{J}{d+2}\right) P ( some representative is missed ) ≪ d h − O d ( J d + 1 ) exp ( − p ( d + 2 J ) )
≪ d exp ( − p ( J d + 2 ) + O d ( J d + 1 log J ) ) . \ll_d\exp\left(-p\binom{J}{d+2}+O_d(J^{d+1}\log J)\right). ≪ d exp ( − p ( d + 2 J ) + O d ( J d + 1 log J ) ) .
Choosing p = δ / 4 e p=\delta/4e p = δ /4 e and taking J J J sufficiently large, one may obtain H H H such that E μ ( H ) ≤ δ / 2 \mathbb{E}_{\mu}(H)\le\delta/2 E μ ( H ) ≤ δ /2 and
P ( some representative is missed ) ≤ 1 / 8. \mathbb{P}(\text{some representative is missed})\le1/8. P ( some representative is missed ) ≤ 1/8.
By Markov’s inequality,
P ( μ ( H ) > δ ) ≤ E μ ( H ) δ ≤ 1 4 . \mathbb{P}(\mu(H)>\delta)\le\frac{\mathbb{E}_{\mu}(H)}{\delta}\le\frac14. P ( μ ( H ) > δ ) ≤ δ E μ ( H ) ≤ 4 1 .
Thus some choice of H H H satisfies μ ( H ) ≤ δ \mu(H)\le\delta μ ( H ) ≤ δ and hits every representative. By construction of H H H , and the construction of the h h h -net, this set thus hits every configuration in C \mathcal{C} C . □
By Lemma 5.3 , this supplies that for every x ∈ T J x\in\mathbb{T}^J x ∈ T J and P ∈ P P\in\mathcal{P} P ∈ P there exists some y ∈ ( d + 3 ) A y\in(d+3)A y ∈ ( d + 3 ) A such that x + P ( y ) v ∈ H x+P(y)\mathbf{v}\in H x + P ( y ) v ∈ H . We may now construct a set for all degree-d d d polynomial configurations.
Proof of Theorem 1.8 . Take ϵ > 0 \epsilon> 0 ϵ > 0 . For each n ∈ Z n \in\mathbb{Z} n ∈ Z we apply Proposition 5.6 with δ n = ϵ 12 2 − ∣ n ∣ \delta_n = \frac{\epsilon}{12}2^{-|n|} δ n = 12 ϵ 2 − ∣ n ∣ , to obtain a scale J n J_n J n , a set H n ⊂ T J n H_n \subset\mathbb{T}^{J_n} H n ⊂ T J n , and an associated vector v n v_n v n . We will use the normal product Haar probability measure on G : = ∏ n ∈ Z T J n G := \prod_{n\in\mathbb{Z}} \mathbb{T}^{J_n} G := ∏ n ∈ Z T J n . For z = ( z n ) n ∈ Z ∈ G z = (z_n)_{n\in\mathbb{Z}} \in G z = ( z n ) n ∈ Z ∈ G , define
E z : = { x ∈ [ 0 , 1 ] : z n + x 2 − n v n ∉ H n for every n ∈ Z } . E_z := \{x \in[0,1] : z_n + x2^{-n}v_n \notin H_n \text{ for every } n \in\mathbb{Z}\}. E z := { x ∈ [ 0 , 1 ] : z n + x 2 − n v n ∈ / H n for every n ∈ Z } .
Each E z E_z E z is Borel. For fixed x x x and n n n , letting z z z vary uniformly over G G G , translation-invariance gives
P ( z n + x 2 − n v n ∈ H n ) = μ ( H n ) ≤ δ n . \mathbb{P}(z_n + x2^{-n}v_n \in H_n) = \mu(H_n) \leq\delta_n. P ( z n + x 2 − n v n ∈ H n ) = μ ( H n ) ≤ δ n .
The union bound and Tonelli’s theorem then produce that
E μ ( [ 0 , 1 ] ∖ E z ) ≤ ∑ n ∈ Z δ n = ϵ 4 . \mathbb{E}\mu([0,1] \setminus E_z) \leq\sum_{n\in\mathbb{Z}}\delta_n = \frac{\epsilon}{4}. E μ ([ 0 , 1 ] ∖ E z ) ≤ n ∈ Z ∑ δ n = 4 ϵ .
Consequently, some z z z satisfies that μ ( E z ) ≥ 1 − ϵ \mu(E_z) \geq1-\epsilon μ ( E z ) ≥ 1 − ϵ . Fix such a z z z and write E = E z E=E_z E = E z .
Suppose a nonconstant polynomial Q Q Q of degree at most d d d satisfies Q ( ( d + 3 ) A ) ⊂ E Q((d+3)A) \subset E Q (( d + 3 ) A ) ⊂ E . By separating out its constant term and choosing a dyadic scale for its largest nonconstant coefficient, we may write
Q ( y ) = x 0 + 2 n P ( y ) , for some P ∈ P , n ∈ Z . Q(y) = x_0 + 2^nP(y), \qquad\text{for some } P \in\mathcal{P},\ n \in\mathbb{Z}. Q ( y ) = x 0 + 2 n P ( y ) , for some P ∈ P , n ∈ Z .
The definition of E E E at index n n n would then imply, for every y ∈ ( d + 3 ) A y \in(d+3)A y ∈ ( d + 3 ) A ,
z n + Q ( y ) 2 − n v n = z n + x 0 2 − n v n + P ( y ) v n ∉ H n . z_n + Q(y)2^{-n}v_n = z_n + x_0 2^{-n}v_n + P(y)v_n \notin H_n. z n + Q ( y ) 2 − n v n = z n + x 0 2 − n v n + P ( y ) v n ∈ / H n .
This is a violation of Proposition 5.6 , and so by construction Q ( ( d + 3 ) A ) ⊄ E Q((d+3)A) \not\subset E Q (( d + 3 ) A ) ⊂ E . □
Acknowledgments
The authors thank Xiang Gao and Joshua Zahl for helpful discussions.
References
SCHOOL OF MATHEMATICS, GEORGIA INSTITUTE OF TECHNOLOGY, ATLANTA, UNITED STATES
Email address: alexander.burgin@gatech.edu
DEPARTMENT OF MATHEMATICS, HONG KONG UNIVERSITY OF SCIENCE AND TECHNOLOGY, CLEAR WATER BAY, HONG KONG
Email address: machyip@ust.hk