Arithmetic Properties of Sparse Subsets of ℤ^{n}

Paul Potgieter Department of Decision Sciences University of South Africa P. O. Box 392 Pretoria 0003 South Africa

                  potgip@unisa.ac.za

Abstract

Arithmetic progressions of length three may be found in compact subsets of the reals that satisfy certain Fourier- as well as Hausdorff-dimensional requirements. Similar results hold in the integers under analogous conditions, with Fourier dimension being replaced by the decay of a discrete Fourier transform. In this paper we make this correspondence more precise, using a well-known construction by Salem. Specifically, we show that a subset of the integers can be mapped to a compact subset of the continuum in a way which preserves certain dimensional properties as well as arithmetic progressions of arbitrary length. The higher-dimensional version of this construction is then used to show that certain parallelogram configurations must exist in sparse subsets of ℤ^{n} satisfying appropriate density and Fourier-decay conditions.

1 Introduction

Subsets of ℝ^{n} satisfying certain Hausdorff- and Fourier-dimensional properties have been shown to have interesting arithmetic properties [2, 6, 12]. To obtain sets with the relevant properties, it has been standard practice to use integer sequences to construct Cantor-type subsets of ℝ^{n}. However, little has been said about the interpretation of such results in subsets ℤ^{n}. It seems likely that such interpretations should exist, because similar notions of dimension and of Fourier decay can be formulated in both the continuum and in ℤ^{n}. Yet the translation of results from the continuum to the discrete case is not necessarily trivial and there is at present no canonical method for doing so. We have, for example, the following result in the continuum:

Theorem 1. [6] Assume that E ⊂ [0, 1] is a closed set which supports a probability measure μ with the following properties:

(i) μ([x, x + ϵ]) ≤ C_{1}ϵ^{α} for all 0 < ϵ ≤ 1,

(ii) |μ̂(k)| ≤ C_{2}(1 − α)^{−B}|k|^{− \frac{β}{2}} for all k ≠ 0,

where 0 < α < 1 and 2/3 < β ≤ 1. If α > 1−ϵ_{0}, where ϵ_{0} > 0 is a sufficiently small constant depending only on C_{1}, C_{2}, B, β, then E contains a non-trivial 3-term arithmetic progression.

The first condition of the theorem ensures that the Hausdorff dimension of E is at least α. Theorem 3 shows that very similar conditions apply in ℕ to obtain arithmetic progressions of length 3. We first define an integer analogue to Hausdorff dimension [8]. Throughout the paper, [0, N) denotes the interval {0, 1, 2, …, N − 1} in ℕ.

Definition 2. We say that a set A ⊆ ℕ has upper fractional density α if

lim sup_{N→∞} \frac{|A ∩ [0, N)|}{N^{β}}

is ∞ for any β < α and 0 for any β > α. We indicate this by the notation d_{f}^{∗}(A) = α.

The lower fractional density can be similarly defined, and if the upper and lower fractional densities coincide we can of course simply refer to the fractional density of A, which will be denoted by d_{f}(A). The definition can trivially be extended to all of ℤ. We have the following analogue of Theorem 1 in the integers, where now we use the discrete Fourier transform instead of the Fourier-Stieltjes transform of a measure.

Theorem 3. [8] Let A ⊆ ℕ. Suppose A satisfies the following conditions:

(i) A has upper fractional density α, where α > 1/2.

(ii) For some C > 0, the Fourier coefficients of the indicator functions χ_{A_{N}} of A_{N} =

A ∩ [0, N) satisfy

|χ̂_{A_{N}} (k)| ≤ C(kN)^{−β/2}

for any 0 < k < N, for large N, for some 2/3 < β ≤ 1 satisfying β > 2 − 2α.

Then A contains a non-trivial arithmetic progression of length 3.

Examples of sets satisfying the conditions of Theorems 1 and 3 were constructed by Łaba and Pramanik [6] and Potgieter [8], respectively. One could ask whether the results could be extended to longer arithmetic progressions by, for instance, requiring a larger Hausdorff or Fourier dimension. This seems to be unlikely, since these dimensional conditions do not seem to provide enough structure to the set for longer progressions to be inevitable. Tao [13] discusses in full the failure of Fourier-dimensional conditions to guarantee progressions larger than 3. As was shown by Shmerkin [11], given equal Fourier and Hausdorff dimensions, the dimension can be increased arbitrarily whilst avoiding the existence of any non-trivial arithmetic progressions.

Theorem 3 was proved independently of Theorem 1, but using related techniques. The question is whether there is some method which can extract results such as Theorem 3 from results like Theorem 1. This paper partially answers this question in two cases, namely deducing the existence of arithmetic progressions in subsets of ℤ or parallelogram configurations in subsets of ℤ^{n} from their existence in corresponding subsets of ℝ or ℝ^{n}, respectively. The techniques utilized are mostly elementary, and seem to indicate that arithmetic properties analytically obtained in ℝ^{n} may be interpreted in ℤ^{n}, as long as one is careful with the construction used.

The basis of these results is the examination of the construction of Salem-type sets in the continuum using integer sequences. These methods are not dissimilar to the construction of the standard triadic Cantor set, although the specific construction used in this paper is a version of one used by Salem himself [10]. They form the core of much of the study of sparse sets in ℝ^{n}, including important restriction phenomena [1, 5, 7]. The construction is presented here not only for completeness, but because it is an integral part of the results obtained. The construction for higher dimensions is also rarely presented in full in a manner which highlights the dependencies of chosen constants, and therefore including it promotes self-containment.

The notion of density that will be used throughout is Hausdorff dimension, and its analogue in the integers, fractional density. Uniformity will be defined in terms of the decay of a Fourier-Stieltjes transform of a measure on a compact subset of ℝ^{n}, and in ℤ^{n} by a decay condition on the Fourier transform of the indicator function of a set. We define the Fourier-Stieltjes transform of a finite Borel measure μ supported on a compact set A ⊂ ℝ^{n} as

μ̂(ξ) = ∫_{A} e^{−2πiξ·x}dμ(x).  (1)

The Fourier dimension of a set is a measure of exactly how rapid the decay of the transform of that measure is.

Definition 4. A compact set A ⊆ [0, 1]^{n} is said to have Fourier dimension β if

β = sup{α ∈ [0, n] : ∃M_{1}^{+}(A) (|μ̂(ξ)|^{2} = o(|ξ|^{−α}))}.

Here M_{1}^{+}(A) denotes the set of probability measures on the set A. Condition (ii) of Theorem 1, for example, ensures that the Fourier dimension of the set under consideration is at least β. Salem [9] first showed how to construct sets with a specific Fourier dimension, and in a way that it coincides with the set’s Hausdorff dimension. Hence, sets of equal Fourier and Hausdorff dimension are called Salem sets. It is possible for sets to have a positive Fourier dimension which is strictly smaller than their Hausdorff dimension (it can never be larger). Such sets are referred to as Salem-type sets.

Following Theorem 3, we can define the Fourier dimension of a subset of the positive integers.

Definition 5. The Fourier dimension of set A ⊆ ℕ is the supremum of all β ∈ [0, 1] for which there exist a constant C > 0 such that, for A_{N} = A ∩ [0, N),

\frac{1}{N} ∑_{n=0}^{N−1} χ_{A_{N}} (n)e^{−2πi \frac{mn}{N}} ≤ C(mN)^{−β/2},

for any 0 < m < N, m ∈ ℕ, for all large N.

A Salem-type subset of the positive integers will then be one which has Fourier dimension strictly less than its fractional density.

In Section 2 we present the construction of a subset of [0, 1] from a given subset of the positive integers. Briefly, given some A ⊆ ℕ and some strictly increasing sequence of positive integers (N_{i})_{i≥1}, we form the subsets A_{i} = A ∩ [0, N_{i}). The interval [0, 1] is divided into N_{1} equal intervals, and a subinterval [i/k, i/k + ξ_{1}) is chosen whenever i ∈ A_{1}, where 0 < ξ_{1} < 1/N_{1}. The union of all subintervals chosen can be denoted by B_{1}. Once B_{k} is chosen, we find B_{k+1} by applying the construction applied to [0, 1] to each interval comprising B_{k}. That is, each interval in B_{k} is divided into N_{k+1} equal intervals, and from the i-th interval the initial subinterval of length ξ_{k+1}, 0 < ξ_{k+1} < (N_{1} ⋯ N_{k+1})^{−1} is chosen whenever i ∈ A_{k+1}. The intersection of all the B_{k}, k = 1, 2, …, is denoted by B, or B(A) if we want to highlight the dependence on A. We then have the following proposition:

Proposition 6. Suppose that A ⊆ ℕ satisfies the conditions of Theorem 3. Then the set B obtained from A via the construction in Section 2.1 has Fourier dimension no less than β.

As is noted in Section 2, it is easily shown that the Hausdorff dimension of the set B is equal to the upper fractional density of the set A.

The fact that such dimensional concepts are preserved is an indication that arithmetic properties might also be preserved, as evinced by the correspondence between Theorems 1 and 3. That this is indeed the case is illustrated by the following, which holds irrespective of Hausdorff and Fourier dimension.

Proposition 7. For any n ∈ ℕ, a set A ⊆ ℕ contains an arithmetic progression of length n if and only if the set B(A) defined by (5) contains an arithmetic progression of length n.

The construction can be generalized to higher dimensions in a straightforward way, as presented in Section 3.2, in a manner which preserves relevant dimensions similarly to the one-dimensional case. The concept of a Salem-type set in ℤ^{n} is defined analogously to the one-dimensional case (Definition 11). The type of linear configuration we will examine is given by the following.

Definition 8. Suppose that n ≥ 2, m ≥ n and k ≥ 3. Let 𝔹 = {B_{i}: i = 1, …, k} be a collection of (m − n) × n matrices with non-negative integer entries. We say that a set A ⊆ ℤ^{n} contains a 𝔹-configuration if there exist x ∈ ℤ^{n} and y ∈ ℤ^{m−n} \ {0} such that x + B_{i}y ∈ A for each i.

As is shown in Section 4.3, we can define parallelograms in ℤ^{n} as such 𝔹-configurations. Setting aside the technical definition of a non-degenerate collection of matrices until Section 4.1, the main result of the paper is as follows:

Theorem 9. Suppose

n ⌈\frac{k + 1}{2}⌉ = m

and

\frac{2(nk − m)}{k} < β < n.

Let 𝔹 = {B_{1}, …, B_{k}} be a collection of n×(m−n) matrices with non-negative integer entries such that A_{j} = (I_{n×n}B_{j}) is non-degenerate in the sense of Definition 14. Furthermore, letting b_{i,j}^{(l)} denote the entries of the matrix B_{l}, l = 1, …, k, we require that

(i) B_{1} is the n × (m − n) zero matrix,

(ii) for each l = 1, …, m/n and each i = 1, 2, …, n, ∑_{j=1}^{n} b_{i,j}^{(l)} ≤ 1,

(iii) for each l = m/n + 1, …, k, B_{l} is of the form B_{i} + B_{j} for some i, j ∈ {2, 3, …, m/n}.

Then for any constant C > 0 there exists a positive ε = ε(C, n, k, m, 𝔹) ≪ 1 with the following property. Suppose that the set A ⊆ ℤ^{n} is of Salem-type, as in Definition 11, with a fractional density α, where n − ε < α < n and a Fourier dimension of at least β. Then A contains a 𝔹-configuration.

The proof of Theorem 9 is presented in Section 4.2. In Section 4.3, Theorem 9 is applied to show the existence of parallelograms in certain subsets of ℤ^{n}. Section 4.4 discusses some possible generalizations of the current work.

2 Correspondence between ℤ and [0, 1]

2.1 Constructing sets in [0, 1] from the integers

The construction used in this section to generate subsets of [0, 1] from subsets of ℤ is essentially due to Salem [10]. We now proceed with the construction, adjusted to our needs. Let A be a subset of the non-negative integers, with a fractional density of α > 0. Let (α_{i})_{i≥1} be any real sequence strictly increasing to α, and let (γ_{i})_{i≥1} be any real, increasing sequence tending to infinity. By the definition of upper density, we can find a sequence (N_{i})_{i≥1} (to be used in (10)) such that

c_{i} := \frac{|A ∩ [0, N_{i})|}{N_{i}^{α_{i}}} > γ_{i}.  (2)

Thus, c_{i} → ∞. We can also observe that, given the fractional density of A, certainly

|A ∩ [0, N_{i})| = o(2^{β}N_{i}^{β})

for any β > α, and therefore that

c_{i} = o(2^{β}N_{i}^{β−α_{i}})  (3)

for any β > α. This observation is useful in the determination of the Hausdorff dimension of the set to be constructed.

Divide [0, 1] into N_{1} equal intervals and choose an interval [i/N_{1}, i/N_{1} + ζ_{1}), where 0 < ζ_{1} < N_{1}^{−1}, if i ∈ A_{1} = A ∩ [0, N_{1}). The set of intervals chosen is denoted by B_{1}. That is,

B_{1} = ⋃_{i∈A_{1}} [\frac{i}{N_{1}} , \frac{i}{N_{1}} + ζ_{1}) .

Therefore, B_{1} consists of |A_{1}| intervals of length ζ_{1}. Let A_{k} = A ∩ [0, N_{k}) and inductively define B_{k+1} by dividing the intervals belonging to B_{k} into N_{k+1} equal intervals and setting

[x + \frac{ζ_{1} ⋯ ζ_{k}i}{N_{k+1}}, x + \frac{ζ_{1} ⋯ ζ_{k}i}{N_{k+1}} + ζ_{1} ⋯ ζ_{k+1}) ⊂ B_{k+1}

if

[x, x + ζ_{1} ⋯ ζ_{k}) ⊆ B_{k}  (4)

and i ∈ A_{k+1}, where 0 < ζ_{k+1} < N_{k+1}^{−1} and x is of the form

x = \frac{j_{1}}{N_{1}} + \frac{ζ_{1}j_{2}}{N_{2}} + ⋯ + \frac{ζ_{1} ⋯ ζ_{k−1}j_{k}}{N_{k}}

for some j_{1} ∈ A_{1}, …, j_{k} ∈ A_{k}. Thus, the set B_{k+1} consists of |A_{1}| ⋯ |A_{k+1}| intervals, each of length ζ_{1} ⋯ ζ_{k+1}. More concisely by letting J_{k} be the set of all x such that (4) holds,

B_{k+1} = ⋃_{x∈J_{k}} ⋃_{i∈A_{k+1}} [x + \frac{ζ_{1} ⋯ ζ_{k}i}{N_{k+1}}, x + \frac{ζ_{1} ⋯ ζ_{k}i}{N_{k+1}} + ζ_{1} ⋯ ζ_{k+1}) .

We define the set B as

B = ⋂_{k=1}^{∞} B_{k}.  (5)

The set B obtained in this manner is denoted by B(ζ_{1}, ζ_{2}, …, ζ_{k}, …), although we usually do not find it necessary to explicitly indicate the parameters used in the construction. If it is necessary to reference the set A used in the construction, we denote the resulting set by B(A).

In Salem’s original construction, it was required that, if we set ξ_{i} = N_{i}^{−1} for each i, the interval lengths ζ_{i} satisfy

(1 − \frac{1}{2i^{2}} ) ξ_{i} ≤ ζ_{i} < ξ_{i}, i = 1, 2, ….

This condition is specific to Salem’s approach and not necessary in our construction, and would in fact be detrimental to our goal of showing that arithmetic progressions are preserved by the construction. Thus, we set our parameters

ζ_{i} = 1/2N_{i}  (6)

at each stage. To verify that the set B has Hausdorff dimension equal to α, the upper fractional density of A, is easy to do, since the fractional density of the original subset of the integers dictates exactly how many intervals there are at each stage of the construction, and the diameter of each is known. What is more, no interval is contiguous to any other, which makes the sum involved in determining Hausdorff dimension trivial to compute, guaranteeing a dimension of no less than α. The condition (3) in turn ensures that the Hausdorff dimension is no larger than α, hence the desired result. (See, for instance, Example 4.6 of Falconer [4].)

There is a way of representing each element of the set B as an infinite sum, supposing that B was constructed as above. Let a^{(k)}(i) denote the i-th member of the set A_{k}. Each point x belonging to the set B can then be written as

x = \frac{a^{(1)}(ε_{1})}{N_{1}} + \frac{ζ_{1}a^{(2)}(ε_{2})}{N_{2}} + \frac{ζ_{1}ζ_{2}a^{(3)}(ε_{3})}{N_{3}} + ⋯,  (7)

where ε_{i} ranges over all values 1, 2, …, |A_{i}|. This representation is useful in calculating Fourier-Stieltjes transforms of measures on the set B.

2.2 Fourier correspondence between subsets of ℕ and [0, 1]

Since, as shown in the previous section, we can easily move from ℕ to [0, 1] in a way which preserves a notion of Hausdorff dimension, the question becomes whether we can do the same with Fourier dimension. The key to this is to use the decay of the Fourier coefficients of the indicator functions of the sets A_{N}, seen as contained in the group ℤ_{N}, to obtain bounds on the Fourier-Stieltjes transforms of certain discrete probability measures on [0, 1]. These Fourier-Stieltjes transforms can be used to find the Fourier-Stieljes transform of a certain probability measure μ on the set B constructed above.

Letting χ_{A_{N}} denote the indicator function of A_{N} considered as a subset of the cyclic group ℤ_{N}, the discrete Fourier transform is defined as follows:

χ̂_{A_{N}} (k) = \frac{1}{N} ∑_{n=0}^{N−1} χ_{A_{N}} (n)e^{−2πi \frac{kn}{N}} .

We remark that the construction of the measures in this section may seem slightly more deterministic in character than those constructed by Salem. His probabilistic construction yields the required dimension only almost surely, whereas our adapted construction will certainly yield a measure with the required decay. It has to be admitted that this only hides the probabilistic aspect, since the most likely way to obtain sets with the given properties would be through probabilistic means. A probabilistic construction of such a set is given in Potgieter [8].

We now present the proof of Proposition 6. Although we cannot exclude the possibility that Fourier dimension will be preserved for smaller values, our proof does require the Fourier decay of the indicator function of A to be rapid, and that it satisfies the above relation to the fractional density. This is sufficient for our purposes, because the configurations we are interested in seem to only occur under such conditions, even though weaker conditions cannot be entirely ruled out in exceptional circumstances.

Proof of Proposition 6. We construct a measure on the set B obtained in the previous section, assuming the set A and the numbers N_{i}, α_{i}, c_{i}, i ∈ ℕ, to be the same as before. At the k-th stage of the construction we introduce a continuous, non-decreasing function F_{k} : [0, 1] → [0, 1], where F_{k}(0) = 0, with the property that it increases linearly by (c_{1} ⋯ c_{k}N_{1}^{α_{1}} ⋯ N_{k}^{α_{k}})^{−1} over each interval of length ζ_{1} ⋯ ζ_{k} comprising B_{k}, with all the constants in question satisfying the requirements (2), (3) and (6) of Section 2.1. On intervals not part of the set B_{k}, the function remains constant, equal to its previously attained value on B_{k}. Hence, for each k we have a piecewise linear function increasing from 0 to 1 over the unit interval, which is a distribution function for a probability measure μ_{k} supported on the set B_{k}. These functions converge pointwise to a function F which will be continuous and non-decreasing, with F (0) = 0 and F (1) = 1, as can be easily seen by showing they form a Cauchy sequence with respect to the uniform norm. The measure corresponding to F will be denoted by μ.

Our interest now lies in calculating asymptotic properties of the Fourier-Stieltjes transform of μ as defined in (1). To do so, we must find a way of representing upper bounds on |μ̂| in terms of the upper bounds of the Fourier coefficients of the sets A_{N_{i}}.

We let |A_{k}| denote the number of intervals chosen in the k-th step of the construction of the set B = B(ζ_{1}, ζ_{2}, …) from the given set A. The numbers a^{(k)}(j), k, j = 1, 2, 3, …, are as determined in (7). We define

Q^{(k)}(u) = \frac{1}{|A_{k}|} ∑_{j=1}^{|A_{k}|} e^{−2πiu \frac{a^{(k)}(j)}{N_{k}}} ,

for all k ≥ 1. These may be seen as the Fourier-Stieltjes transforms of discrete measures on the unit interval. As in Salem [10], the Fourier-Stieltjes transform of the measure μ can then be written as

μ̂(u) = lim_{m→∞} Q^{(1)}(u) ∏_{k=1}^{m} Q^{(k+1)}(ζ_{1} ⋯ ζ_{k}u)

(see also, for instance, p. 195 of Zygmund [14]).

Note that Q^{(k)} corresponds closely to the discrete Fourier transform (modulo N_{k}) on integer values, as follows:

Q^{(k)}(m) = \frac{1}{|A_{k}|} ∑_{n=0}^{N_{k}−1} χ_{A_{k}}(n)e^{−2πin \frac{m}{N_{k}}} = \frac{N_{k}}{|A_{k}|}χ̂_{A_{k}}(m).

We can therefore dictate the decay of μ̂ by requiring sufficient decay of χ̂_{A_{k}}(m), as in the statement of the theorem. Thus, for any β satisfying the conditions of the theorem, there exists some constant C such that for any m ∈ [1, N_{k}) ⊂ ℕ,

|Q^{(k)}(m)| ≤ C \frac{N_{k}}{|A_{k}|}(mN_{k})^{−β/2} = c_{k}^{−1}Cm^{−β/2}N_{k}^{1− \frac{β}{2} −α_{k}}.  (8)

We will need to consider arbitrarily large arguments in the approximation of |μ̂(u)|, in which case the m in the above expression ought to be replaced by m mod N_{k}. However, once m ≥ N_{k}, we will use some other |Q^{(j)}(m)| with j > k as the main component of our approximation, thus avoiding the issue. This also lets us avoid the problem of approximating |Q^{(k)}(m)| when m is a multiple of N_{k}, where it would be equal to 1.

Since the inequalities bounding |Q^{(k)}| only hold for integer-valued arguments, we will need to extend them to arbitrary real arguments in order to approximate |μ̂|. To do so, note that an elementary calculation gives the upper bound

|\frac{d}{du}|Q^{(k)}(u)|| ≤ |Q^{(k)}(u)|

for any u > 0. For any interval [u, u + a], a > 0, we then have that

max_{x∈[0,a]} |Q^{(k)}(u + x)| ≤ a max_{x∈[0,a]} |\frac{d}{dw}|Q^{(k)}(w)||_{w=u+x}| + |Q^{(k)}(u)|

≤ a max_{x∈[0,a]} |Q^{(k)}(u + x)| + |Q^{(k)}(u)|

and therefore

max_{x∈[0,a]} |Q^{(k)}(u + x)| ≤ \frac{1}{1 − a}|Q^{(k)}(u)|

when 1 − a > 0. Set a = 1/2. For any integer m we therefore have that for any u ∈ [m, m + 1/2],

|Q^{(k)}(u)| ≤ 2|Q^{(k)}(m)| ≤ 2c_{k}^{−1}Cm^{−β/2}N_{k}^{1− \frac{β}{2} −α_{k}}.

To relate the quantities u^{−β/2} and m^{−β/2}, we use the same method applied to the function x^{−β/2}. For u ∈ [m, m + 1/2] we have

m^{−β/2} − u^{−β/2} ≤ \frac{1}{2} max_{x∈[m,m+1/2]} |\frac{d}{dx}x^{−β/2}| ,

and therefore

m^{−β/2} ≤ u^{−β/2} + \frac{β}{4} m^{−3β/2}.

The simple bounds m^{3} > u and β/4 < 1 imply that

\frac{β}{4} m^{−3β/2} ≤ \frac{β}{4} u^{−β/2} ≤ u^{−β/2},

and thus

|Q^{(k)}(u)| ≤ 4c_{k}^{−1}Cu^{−β/2}N_{k}^{1− \frac{β}{2} −α_{k}}, u ∈ [m, m + 1/2].

Having established this for u ∈ [m, m + 1/2], we can repeat the method on the interval [m+1/2, m+1). By adjusting the constant C, the inequality (8) now holds with m replaced by the continuous variable u ≥ 1.

In order to estimate μ̂, notice that for any p ≥ 1,

|μ̂(u)| ≤ ∏_{k=1}^{p} |Q^{(k+1)}(ζ_{1} ⋯ ζ_{k}u)|.  (9)

Given some p, we first consider values of u of the form

2^{p}N_{1} ⋯ N_{p}N_{p} ≤ u < 2^{p}N_{1} ⋯ N_{p}N_{p+1}.  (10)

This corresponds to

N_{p} ≤ ζ_{1} ⋯ ζ_{p}u < N_{p+1}.

Since the first p − 1 terms of (9) may be bounded by 1, it follows that

|μ̂(u)| ≤ Cc_{p+1}^{−1}(ζ_{1} ⋯ ζ_{p}u)^{−β/2}N_{p+1}^{1− \frac{β}{2} −α_{p+1}}.

(By choosing u in this range, we avoid the problematic cases of the argument of |Q^{(p+1)}| being a multiple of N_{p+1} or being very small, modulo N_{p+1}.) Because of the choice of the ζ_{i} in our construction, this gives

|μ̂(u)| ≤ c_{p+1}^{−1}C2^{pβ/2}N_{1}^{β/2} ⋯ N_{p}^{β/2}u^{−β/2}N_{p+1}^{1− \frac{β}{2} −α_{p+1}}.

As stated in Section 2.1, we may assume that c_{k} > \sqrt{2}C for each k ∈ ℕ, which means that

|μ̂(u)| ≤ 2^{pβ/2}u^{−β/2}N_{1}^{β/2} ⋯ N_{p}^{β/2}N_{p+1}^{1− \frac{β}{2} −α_{p+1}}.  (11)

By requiring the terms N_{k} to rapidly increase (passing to a subsequence if necessary), we can assume that

2^{pβ/2}N_{1}^{β/2} ⋯ N_{p}^{β/2}N_{p+1}^{1− \frac{β}{2} −α_{p+1}} = o(1),

This is possible, since by assumption β > 2 − 2α. For given β and α_{i} → α in the prescribed manner, we also have that β > 2 − 2α_{i} for α_{i} close enough to α, which we assume is the case, and hence that 1 − β/2 − α_{p+1} < 0.

Now consider u such that

2^{p}N_{1} ⋯ N_{p}N_{p+1} ≤ u < 2^{p+1}N_{1} ⋯ N_{p}N_{p+1}^{2},

which corresponds to

\frac{1}{2} ≤ ζ_{1} ⋯ ζ_{p+1}u < N_{p+1}.

For this range of u we apply the above argument, only with the approximation of |Q^{(p+2)}| instead of |Q^{(p+1)}|. The case 1/2 ≤ ζ_{1} ⋯ ζ_{p+1}u < 1 should be mentioned, as the previous calculation required that ζ_{1} ⋯ ζ_{p+1}u ≥ 1. However, since the upper bound on the derivative is valid for all u > 0, we can similarly approximate |Q^{(k)}|:

max_{u∈[1/2,1)} |Q^{(k)}(u)| ≤ 2|Q^{(k)}(1)| ≤ 2c_{k}^{−1}CN_{k}^{1− \frac{β}{2} −α_{k}}.

Since u^{−β/2} > 1 for u ∈ [1/2, 1), we see that

|Q^{(k)}(u)| ≤ 2c_{k}^{−1}Cu^{−β/2}N_{k}^{1− \frac{β}{2} −α_{k}}

on this interval. We therefore obtain

|μ̂(u)| ≤ 2^{(p+1)β/2}u^{−β/2}N_{1}^{β/2} ⋯ N_{p+1}^{β/2}N_{p+2}^{1− \frac{β}{2} −α_{p+2}}

for all u in the current range. The required decay is ensured by the rapid increase of N_{k}. By using increasing values of p, we see that

|μ̂(u)| = o(u^{−β/2})

for all β satisfying the conditions of Theorem 3.

The result indicates that at least some sets satisfying the conditions of Theorem 3 will be mapped to sets satisfying the conditions of Theorem 1, meaning that both the original set and its image will contain 3-arithmetic progressions. The next section further explores the invariance of the existence of arithmetic progressions under the mapping.

2.3 Preservation of arithmetic progressions

The purpose of this section is to show that arithmetic progressions are preserved when transitioning from the integers to the continuum as described in previous sections. This is not dependent on the Hausdorff- or Fourier-dimensional aspects of the sets, only on the construction. We shall frequently refer to an arithmetic progression of length n as an nAP.

Although the set B(A) is not uniquely determined by A alone but differs depending on constants used throughout, we suppress mention of the constants and regard B(A) as fixed, and refer merely to B throughout the proof.

Proof of Proposition 1.4. We first show that 3APs occurring in a subset of [0, 1] according to the construction (5) must arise from a 3AP in the integers. Recall that every element of our set B can be written in the form (7). Suppose that there are a_{1}, a_{2}, a_{3} ∈ B such that a_{2} − a_{1} = a_{3} − a_{2}. Each of the a_{i}, i = 1, 2, 3, is the image of a sequence of integers under the construction of B, and we can write

a_{i} = \frac{a_{1}^{(i)}}{N_{1}} + \frac{ζ_{1}a_{2}^{(i)}}{N_{2}} + \frac{ζ_{1}ζ_{2}a_{3}^{(i)}}{N_{3}} + ⋯,

where a_{j}^{(i)} ∈ [1, N_{i}) ∩ A for i = 1, 2, 3; j ∈ ℕ.

We therefore have that

\frac{2a_{1}^{(2)} − a_{1}^{(1)} − a_{1}^{(3)}}{N_{1}} + \frac{ζ_{1}(2a_{2}^{(2)} − a_{2}^{(1)} − a_{2}^{(3)})}{N_{2}} + \frac{ζ_{1}ζ_{2}(2a_{3}^{(2)} − a_{3}^{(1)} − a_{3}^{(3)})}{N_{3}} + ⋯ = 0.

Let k ∈ ℕ be such that the 3AP occurs within an interval of length ζ_{1} ⋯ ζ_{k−1} but not within an interval of length ζ_{1} ⋯ ζ_{k}. The choices of the parameters ζ_{i} guarantee that such a k must exist, since the largest distance between any two points in a new subdivision of an interval is less than the distance to the next interval. This would imply that the first k − 1 terms of the expression above will be 0 (trivially, since the points have equal terms in the expansion up to that point) and that the k-th term will only be 0 should 2a_{k}^{(2)} −a_{k}^{(1)} −a_{k}^{(3)} = 0. If the k-th term is not 0, we have either that a_{k}^{(3)} −a_{k}^{(2)} ≥ a_{k}^{(2)} −a_{k}^{(1)} +1 or that a_{k}^{(3)} − a_{k}^{(2)} ≤ a_{k}^{(2)} − a_{k}^{(1)} − 1. Suppose first that the former of the two alternatives holds, and consider the restricted case a_{k}^{(3)} − a_{k}^{(2)} = a_{k}^{(2)} − a_{k}^{(1)} + 1.

The maximum distance between two points in the two separate intervals indexed by a_{k}^{(1)} and a_{k}^{(2)} is strictly less than

ζ_{1} ⋯ ζ_{k−1} \frac{a_{k}^{(2)} − a_{k}^{(1)}}{N_{k}} + ζ_{1} ⋯ ζ_{k},

remembering that the intervals are half-open. The minimum distance between two points in the intervals indexed by a_{k}^{(2)} and a_{k}^{(3)} is strictly greater than

ζ_{1} ⋯ ζ_{k−1} \frac{a_{k}^{(2)} − a_{k}^{(1)} + 1}{N_{k}} − ζ_{1} ⋯ ζ_{k}

= ζ_{1} ⋯ ζ_{k−1} \frac{a_{k}^{(2)} − a_{k}^{(1)}}{N_{k}} + ζ_{1} ⋯ ζ_{k−1} (\frac{1}{N_{k}} − ζ_{k}) .

Requiring, as we did in the construction, that ζ_{k} = 1/2N_{k}, we see that it is impossible for the difference between any two elements in the intervals indexed by a_{k}^{(2)} and a_{k}^{(1)} to be added to any element in the interval indexed by a_{k}^{(2)} to obtain an element of the interval indexed by a_{k}^{(3)}. Therefore, it cannot be true that a_{k}^{(3)} − a_{k}^{(2)} = a_{k}^{(2)} − a_{k}^{(1)} + 1. Since increasing k only increases the minimum distance, it is not true that a_{k}^{(3)} − a_{k}^{(2)} = a_{k}^{(2)} − a_{k}^{(1)} + k for any integer k ≥ 1.

The same reasoning discounts the case a_{k}^{(3)} − a_{k}^{(2)} ≤ a_{k}^{(2)} − a_{k}^{(1)} − 1, by considering the minimum possible distance between points in the two separate intervals indexed by a_{k}^{(2)} and a_{k}^{(1)} and the maximum possible distance between points in the intervals indexed by a_{k}^{(2)} and a_{k}^{(3)}. The minimum will always exceed the maximum, as in the previous case. Hence, a_{k}^{(3)} − a_{k}^{(2)} = a_{k}^{(2)} − a_{k}^{(1)}. Therefore, we can conclude that a 3AP in the set B must be the result of a 3AP in the generating set A.

To pass to the general case of a kAP, we only need notice that such an AP can be seen as k − 2 3APs, each with the same common difference and the initial point of each shifted by the common difference each time. Here too, it is important to note the distances between intervals determined by the ζ_{i}. Thus, the second 3AP must also correspond to a 3AP in A, with initial point the second member of the first 3AP, and so on, yielding a kAP in A.

We now turn to the reverse, to show that a kAP in the generating set always leads to a kAP in B. Suppose that P = {p_{1}, …, p_{k}} ⊆ A, p_{1} < p_{2} < … < p_{k}, is a kAP with common difference d occurring in the m-th stage of the construction, that is, p_{k} < N_{m}. Then, for any fixed a_{i} ∈ A ∩ [0, N_{i}), i ∈ ℕ \ {m} there will be elements of B expressible as

c_{n} = \frac{a_{1}}{N_{1}} + ζ_{1} \frac{a_{2}}{N_{2}} + ⋯ + ζ_{1} ⋯ ζ_{m−1} \frac{p_{n}}{N_{m}} + ζ_{1} ⋯ ζ_{m} \frac{a_{m+1}}{N^{m+1}} + ⋯

for n = 1, 2, …, k. Then c_{1}, …, c_{k} form a kAP in [0, 1] with common difference ζ_{1} ⋯ ζ_{m−1}d/N^{m}.

3 Correspondence in higher dimensions

3.1 Hausdorff and Fourier dimensions

The method for obtaining subsets of [0, 1]^{n} from subsets of ℕ^{n} is not much different from the one-dimensional case. First, we need to define the higher-dimensional notion of fractional density:

Definition 10. We say that a set A ⊆ ℕ^{n} has upper fractional density α, 0 ≤ α ≤ n, if

lim sup_{N→∞} \frac{|A ∩ [0, N) × ⋯ × [0, N)|}{N^{β}}

is ∞ for any β < α and 0 for any β > α. This is indicated by d_{f}^{∗}(A) = α.

The notions of lower fractional density and fractional density are defined analogously to the one-dimensional case.

With A given, let A_{N} = A ∩ [0, N) × ⋯ × [0, N), for some N ∈ ℕ. If a sequence of natural numbers (N_{i})_{i≥1} is given, we will set A_{i} = A ∩ [0, N_{i}) × ⋯ × [0, N_{i}). The definition of a Salem-type set in ℕ^{n} is as follows:

Definition 11. A set A ⊆ ℕ^{n} is a Salem-type set if it has upper fractional density α ∈ (0, n] and for each m⃗ = (m_{1}, …, m_{n}) ∈ [0, N)^{n} \ {0},

\frac{1}{N^{n}} ∑_{n⃗∈[0,N)×···×[0,N)} χ_{A_{N}} (n⃗)e^{−2πi \frac{m⃗·n⃗}{N}} ≤ C(|m⃗|N)^{−β/2}

for all large N ∈ ℕ, for some C > 0 and 0 < β ≤ α. The supremum of the β for which the above holds is the Fourier dimension of A.

The fact that the Fourier dimension will always be less than the fractional density follows from the correspondences in the next section.

3.2 Constructing a subset of [0, 1]^{n}

Suppose that A ⊆ ℤ^{n} such that d_{f}(A) = α > 0. As before, we choose a strictly increasing sequence (α_{i})_{i≥1} of real numbers such that α_{i} → α, and a strictly increasing sequence (γ_{i})_{i≥1} tending to infinity. Let (N_{i})_{i≥1} be an increasing sequence for which

c_{i} := \frac{|A ∩ [0, N_{i}) × ⋯ × [0, N_{i})|}{N_{i}^{α_{i}}} > γ_{i}.

For each i ∈ ℕ, choose ζ_{i} = (2N_{i})^{−1} for all i ∈ ℕ. Define A_{i} = A ∩ [0, N_{i}) × ⋯ × [0, N_{i}) ⊂ ℕ^{n} for all i ∈ ℕ. Set

B_{1} = ⋃_{(i_{1},...,i_{n})∈A_{1}} [\frac{i_{1}}{N_{1}} , \frac{i_{1}}{N_{1}} + ζ_{1}) × ⋯ × [\frac{i_{n}}{N_{1}} , \frac{i_{n}}{N_{1}} + ζ_{1}) .

Define the set J_{k} by

J_{k} = {(x_{1}, …, x_{n}) ∈ ℝ^{n} : [x_{1}, x_{1} + ζ_{1} ⋯ ζ_{k}) × ⋯ × [x_{n}, x_{n} + ζ_{1} ⋯ ζ_{k}) ⊆ B_{k}} .

Once again, we define B_{k+1} recursively:

\begin{matrix}B_{k+1} = ⋃_{x⃗∈J_{k}} ⋃_{i⃗∈A_{k+1}} [x_{1} + \frac{ζ_{1} ⋯ ζ_{k}i_{1}}{N_{k+1}} , x_{1} + \frac{ζ_{1} ⋯ ζ_{k}i_{1}}{N_{k+1}} + ζ_{1} ⋯ ζ_{k+1}) × ⋯ × \\ [x_{n} + \frac{ζ_{1} ⋯ ζ_{k}i_{n}}{N_{k+1}} , x_{n} + \frac{ζ_{1} ⋯ ζ_{k}i_{n}}{N_{k+1}} + ζ_{1} ⋯ ζ_{k+1}) . \end{matrix}

Finally, let

B = ⋂_{k=1}^{∞} B_{k}.

As before, each element of the set B can be expressed as a series

\frac{a^{(1)}(ε_{1})}{N_{1}} + \frac{ζ_{1}a^{(2)}(ε_{2})}{N_{2}} + \frac{ζ_{1}ζ_{2}a^{(3)}(ε_{3})}{N_{3}} + ⋯,

where a^{(k)}(i) = (a_{1}^{(k)}(i), …, a_{n}^{(k)}(i)) denotes the i-th element of the set A_{k} (with some ordering) and each ε_{i} ranges over all values 1, 2, …, |A_{i}|.

Proposition 12. Suppose that A ⊆ ℕ^{n} has upper fractional density α and satisfies the conditions of Definition 3.2 for some β, where β > 2n − 2α. Then the set B constructed above has Hausdorff dimension α and Fourier dimension no less than β.

Proof. Verifying that the set B has Hausdorff dimension equal to the upper fractional density is no harder than in the one-dimensional case. For the existence of the measure and the decay of the Fourier-Stieltjes transform, we proceed analogously to the one-dimensional case, with only minor differences in the approximation of μ̂. At each stage k of the construction, a probability measure μ_{k} can be defined on the set B_{k} which assigns equal measure to each cube comprising B_{k}, with a distribution function

F_{k}(x⃗) = μ_{k}([y⃗ ∈ [0, 1]^{n} : y_{i} ≤ x_{i}, i = 1, …, n]).

The μ_{k} converge weakly to a measure μ. Setting

Q^{(k)}(u⃗) = \frac{1}{|A_{k}|} ∑_{j=1}^{|A_{k}|} e^{−_{\frac{2πi}{N_{k}}} u⃗·a^{(k)}(j)},

we can write

μ̂(u⃗) = lim_{n→∞} Q^{(1)}(u⃗) ∏_{k=1}^{m} Q^{(k+1)}(ζ_{1} ⋯ ζ_{k}u⃗)

and

|μ̂(u⃗)| ≤ ∏_{k=1}^{p} |Q^{(k+1)}(ζ_{1} ⋯ ζ_{k}u⃗)|,

as before. We have the upper bound

|Q^{(k)}(m⃗)| ≤ \frac{C}{c_{k}} |m⃗|^{−β/2}N^{n− \frac{β}{2} −α_{k}}

for m⃗ ∈ [1, N_{k}) × ⋯ × [1, N_{k}) ⊂ ℕ^{n}, and we can assume that this holds for non-integer arguments for much the same reasons as before. Specifically, for x⃗ = (x_{1}, …, x_{n}) ∈ ℝ^{n} and u⃗ = (u_{1}, …, u_{n}),

|\frac{∂}{∂u_{i}} |Q^{(k)}(u⃗)|| ≤ |Q^{(k)}(u⃗)|

for each i = 1, …, n. For a given y ∈ ℝ, let u⃗_{i}(y) = (u_{1}, …, u_{i−1}, y, u_{i+1}, …, u_{n}). The previous inequality implies that

max_{y∈[u_{i},u_{i}+a]} |∂_{x_{i}}|Q^{(k)}(x⃗)||_{x⃗=u⃗_{i}(y)}| ≤ max_{y∈[u_{i},u_{i}+a]} |Q^{(k)}(u⃗_{i}(y))| ≤ max_{\begin{matrix}0≤x_{i}≤a \\ 1≤i≤n \end{matrix}} |Q^{(k)}(u⃗ + x⃗)|,

and consequently

max_{\begin{matrix}0≤x_{i}≤a \\ 1≤i≤n \end{matrix}} |Q^{(k)}(u⃗ + x⃗)| ≤ a (∑_{i=1}^{n} ( max_{y∈[u_{i},u_{i}+a]} |∂_{x_{i}}|Q^{(k)}(x⃗)||_{x⃗=u⃗_{i}(y)}|)^{2})^{1/2} + |Q^{(k)}(u⃗)|

≤ a\sqrt{n} max_{\begin{matrix}0≤x_{i}≤a \\ 1≤i≤n \end{matrix}} |Q^{(k)}(u⃗ + x⃗)| + |Q^{(k)}(u⃗)|,

yielding

max_{\begin{matrix}0≤x_{i}≤a \\ 1≤i≤n \end{matrix}} |Q^{(k)}(u⃗ + x⃗)| ≤ \frac{1}{1 − a\sqrt{n}}|Q^{(k)}(u⃗)|

as long as 1 − a\sqrt{n} > 0. As with the one-dimensional case, we can now repeatedly extend the upper bound over cubes of side-length no greater than, for instance, (2\sqrt{n})^{−1}, by using the inequality

|m⃗|^{−β/2} ≤ K|u⃗|^{−β/2}

for some constant K independent of m⃗ and u⃗, with u⃗ contained in the cube

\{u⃗ = (u_{1}, …, u_{n}) ∈ ℝ^{n} : 0 ≤ u_{i} − m_{i} ≤ (2\sqrt{n})^{−1}, i = 1, 2, …, n\}.

With the upper bound on |Q^{(k)}(u⃗)| established for this cube, we can repeat the argument to obtain the same bound for neighboring cubes, and therefore for all u⃗ ∈ ℝ^{n} with u_{i} ≥ 1, i = 1, …, n. When u_{i} ∈ [1/2, 1), the argument in the one-dimensional case applies similarly.

The reasoning of Section 2.2 now transfers to the multidimensional case almost seamlessly. The restrictions on the values of u in the previous must only be replaced by restrictions on the coordinates of u⃗; thus, we consider the cases

2^{p}N_{1} ⋯ N_{p}N_{p} ≤ u_{i} < 2^{p}N_{1} ⋯ N_{p}N_{p+1}, i = 1, 2, …, n

and

2^{p}N_{1} ⋯ N_{p}N_{p+1} ≤ u_{i} < 2^{p+1}N_{1} ⋯ N_{p}N_{p+1}^{2}, i = 1, 2, …, n.

Also taking into account that now we have β > 2n − 2α, we find that

|μ̂(u⃗)| = o(|u⃗|^{−β/2}).

We can conclude that the Fourier dimension of B is β or greater.

4 Finite configurations in sparse subsets

4.1 Subsets of ℝ^{n}

In this section we briefly describe the result of Chan, Łaba and Pramanik [2], to which we shall find a corresponding theorem in the integers. Whereas before we used vector notation to indicate elements of higher-dimensional spaces in order to distinguish from the one-dimensional case, we abandon that now for readability.

Definition 13. [2] Fix integers n ≥ 2, k ≥ 3 and m ≥ n. Suppose 𝔹 = {B_{1}, …, B_{k}} is a collection of n × (m − n) real matrices.

(a) We say that E ⊂ ℝ^{n} contains a 𝔹-configuration if there exist x ∈ ℝ^{n} and y ∈ ℝ^{m−n}\{0} such that {x + B_{j}y}_{j=1}^{k} ⊆ E.

(b) Given any finite collection of subspaces V_{1}, …, V_{q} ⊆ ℝ^{m−n} with dim(V_{i}) < m − n, we say that E contains a non-trivial 𝔹-configuration with respect to (V_{1}, …, V_{q}) if there exist x ∈ ℝ^{n} and y ∈ ℝ^{m−n} \ ⋃_{i=1}^{q} V_{i} such that {x + B_{j}y}_{j=1}^{k} ⊆ E.

In order to formulate the theorem, we shall need the notion of non-degeneracy for our configurations. Let A_{1}, …, A_{k} be n × m matrices. For any set of (distinct) indices J = {j_{1}, …, j_{s}} ⊆ {1, …, k}, define the ns × m matrix 𝔸_{J} by

𝔸_{J}^{t} = (A_{j_{1}}^{t} ⋯ A_{j_{s}}^{t}).

Let r be the unique positive integer such that

n(r − 1) < nk − m ≤ nr.

The meaning of this integer is as follows. Suppose that we construct an m × m matrix from certain of the matrices A_{1}^{t}, …, A_{k}^{t}, each of which consists of n columns. If m is not a multiple of n, we fill up the remaining columns (fewer than n) with columns from one of the other matrices. The total number of columns of all matrices minus the number used for the m × m matrix is therefore nk − m. The number r − 1 then represents the maximum number of groups of n columns that can be entirely contained in nk − m columns, unless nk −m is a multiple of n, in which case r groups are contained. In other words, r is the total number of groups of n columns that are wholly or partly contained in the nk − m columns not contained in the m × m matrix. The number of columns fewer than n, outside these r groups, that remain “outside” the m × m matrix constructed, is then

n′ = nk − m − (r − 1)n.

It is possible that n′ = n, when nk − m is a multiple of n.

Definition 14. [2] We say that {A_{1}, …, A_{k}} is non-degenerate if for any J ⊆ {1, …, k} with |J| = k − r and any j ∈ {1, …, k} \ J, the m × m matrix

(𝔸_{J}^{t} Ã_{j}^{t})

is non-singular for any choice Ã_{j}^{t} a submatrix of A_{j} consisting of n − n′ rows.

That is, we create an m × m matrix by using as many of the matrices A_{i}^{t} as we can without obtaining more than m columns in total, then fill out the rest of the matrix by using columns from one of the matrices not yet used. If all such matrices are non-singular, the assembly {A_{1}, …, A_{k}} is non-degenerate.

We then have the following theorem from Chan et al. [2]. Note that I_{n×n} denotes the n × n identity matrix.

Theorem 15. Suppose

n ⌈\frac{k + 1}{2}⌉ ≤ m ≤ nk

and

\frac{2(nk − m)}{k} < β < n.

Let 𝔹 = {B_{1}, …, B_{k}} be a collection of n × (m − n) matrices such that A_{j} = (I_{n×n}B_{j}) is non-degenerate in the sense of Definition 14. Then for any constant C > 0, there exists a positive number ε = ε(C, n, k, m, 𝔹) ≪ 1 with the following property. Suppose the set E ⊆ ℝ^{n} with |E| = 0 supports a positive, finite, Radon measure μ satisfying the following two conditions:

(a) ball condition:

sup_{\begin{matrix}x∈E \\ 0<r<1 \end{matrix}} \frac{μ(B(x, r))}{r^{α}} ≤ C if n − ε < α < n,

(b) Fourier decay:

|μ̂(ξ)| ≤ \frac{C}{(1 + |ξ|)^{β/2}} .

for every ξ ∈ ℝ^{n}.

Then (i) E contains a 𝔹-configuration.

(ii) For any finite collection of subspaces V_{1}, …, V_{q} ⊆ ℝ^{m−n} with dim(V_{i}) < m − n, E contains a non-trivial 𝔹-configuration with respect to (V_{1}, …, V_{q}) in the sense of Definition 13.

We remark that condition (b) is fulfilled when |μ̂(ξ)| = o(|ξ|^{−β/2}).

4.2 Subsets of ℤ^{n}

Matrices of the form specified in Theorem 9 will be said to define “parallelogram-like” configurations. This will be further illustrated in Section 4.3, which will also discuss the issue of degeneracy in the configurations, such as when some of the points of the parallelogram are equal, leading to a trivial configuration.

Proof of Theorem 1.5. The proof is already largely accomplished, due to the constructions and correspondences of previous sections. Suppose that A satisfies the conditions of the theorem. Let B be the subset of [0, 1]^{n} obtained via the construction in Section 3.2. By the dimensional correspondence of the construction, we see immediately that B satisfies the conditions of Theorem 15, and must contain a 𝔹-configuration. The rest of the proof aims to show that this configuration corresponds to one in A ⊆ ℕ^{n}, much as we earlier showed that arithmetic progressions in B ⊆ [0, 1] must correspond to arithmetic progressions in the generating set A ⊆ ℕ.

Without loss of generality, we suppose that N_{1} is large enough to separate the points of the configuration (since no matter which N_{1} we start with, B must contain the required configuration). Partition ℝ^{n} and ℝ^{m−n} into cubes so that

ℝ^{l} = ⋃_{z∈ℤ^{l}} ⋃_{i_{1},...,i_{l}=0}^{N_{1}−1} z + [\frac{i_{1}}{N_{1}} , \frac{i_{1} + 1}{N_{1}}) × ⋯ × [\frac{i_{l}}{N_{1}} , \frac{i_{l} + 1}{N_{1}}) ,

for l = n, m − n.

Let x = (x_{1}, …, x_{n}) ∈ ℝ^{n} and y = (y_{1}, …, y_{m−n}) ∈ ℝ^{m−n} be the two points whose existence is guaranteed by Theorem 15. By assumption, B_{1} is the zero matrix, and hence x ∈ B. The N_{1}-approximation x^{(1)} = (x_{1}^{(1)}, …, x_{n}^{(1)}) ∈ ℤ^{n} of the point x in ℝ^{n} is then the corner of the cube with side-lengths 1/N_{1} containing the point with the smallest coordinates in each dimension (in two dimensions, this would be the southwest corner of the containing square). More precisely,

for each i = 1, 2, …, n : 0 ≤ x_{i} − x_{i}^{(1)} < \frac{1}{2N_{1}} and ∃a_{i} ∈ ℕ such that x_{i}^{(1)} = \frac{a_{i}}{N_{1}} .

Note that the nature of the construction of B, specifically the choice of ζ_{1}, ensures that this approximation is possible and unique. For any z ∈ ℝ^{n}, z^{(1)} shall denote the N_{1}- approximation of z in the above sense. Elements of ℝ^{m−n} (considered as a distinct space for the purposes of the argument even when n = m − n), will be approximated slightly differently. Approximate y ∈ ℝ^{m−n} by the closest corner available, that is, the point y^{(2)} = (y_{1}^{(2)}, …, y_{m−n}^{(2)}) such that

for each i = 1, 2, …, m − n : |y_{i} − y_{i}^{(2)}| ≤ \frac{1}{2N_{1}} and ∃b_{i} ∈ ℕ such that y_{i}^{(2)} = \frac{b_{i}}{N_{1}} .

If, for any coordinate, there are two possible choices for an approximation, we choose the one for which y − y_{i}^{(2)} > 0, thus ensuring that y − y_{i}^{(2)} > −(2N_{1})^{−1} for all i.

We can write

x = [x_{1}^{(1)} + ϵ(x_{1}^{(1)}) ; x_{2}^{(1)} + ϵ(x_{2}^{(1)}) ; ⋮ ; x_{n}^{(1)} + ϵ(x_{n}^{(1)})] , y = [ y_{1}^{(2)} + ϵ(y_{1}^{(2)}) ; y_{2}^{(2)} + ϵ(y_{2}^{(2)}) ; ⋮ ; y_{m−n}^{(2)} + ϵ(y_{m−n}^{(2)})] ,

where 0 ≤ ϵ(x_{i}^{(1)}) < (2N_{1})^{−1}, 1 ≤ i ≤ n, and −(2N_{1})^{−1} < ϵ(y_{j}^{(2)}) ≤ (2N_{1})^{−1}, 1 ≤ j ≤ m − n. We shall use the notation

ϵ(x^{(1)}) = (ϵ(x_{1}^{(1)}), …, ϵ(x_{n}^{(1)}))^{t}
ϵ(y^{(2)}) = (ϵ(y_{1}^{(2)}), …, ϵ(y_{m−n}^{(2)}))^{t}.

We assert that x^{(1)} + B_{j}y^{(2)} is the N_{1}-approximation of the point x + B_{j}y, j = 1, …, k. Observe the j-th error term

ϵ(x^{(1)}) + B_{j}ϵ(y^{(2)}) = [ϵ(x_{1}^{(1)}) ; ϵ(x_{2}^{(1)}) ; ⋮ ; ϵ(x_{n}^{(1)})] + B_{j} [ ϵ(y_{1}^{(2)}) ; ϵ(y_{2}^{(2)}) ; ⋮ ; ϵ(y_{m−n}^{(2)})] .

Each component of this term represents the extent to which each coordinate of x^{(1)} + B_{j}y^{(2)} differs from a multiple of 1/N_{1}. Our assertion is then that

0 ≤ (ϵ(x^{(1)}) + B_{j}ϵ(y^{(2)}))_{i} < \frac{1}{N_{1}}

for the i-th component of ϵ(x^{(1)}) + B_{j}ϵ(y^{(2)}), i = 1, 2, …, n. For the moment, consider only j = 1, 2, …, m/n. For the assertion to be violated, we must have that

(ϵ(x^{(1)}) + B_{j}ϵ(y^{(2)}))_{i} ≥ \frac{1}{N_{1}}

or

(ϵ(x^{(1)}) + B_{j}ϵ(y^{(2)}))_{i} < 0

for some value of i. The first case is eliminated by the bounds on the error terms and the restrictions on entries of B_{j}. Since we have x + B_{j}y ∈ B (and must therefore be contained in one of the cubes specified by the construction at the first stage), the second case can only occur when

(ϵ(x^{(1)}) + B_{j}ϵ(y^{(2)}))_{i} ≤ −\frac{1}{2N_{1}}

in some coordinate i, which represents the case where the N_{1}-approximation (x + B_{j}y)^{(1)} is less in some coordinate than x^{(1)} + B_{j}y^{(1)}. Once again, this is prohibited by the bounds on ϵ(x^{(1)}) and ϵ(y^{(2)}).

By construction, the point x^{(1)} corresponds to a point in the original set A, specifically x_{A} = (N_{1}x_{1}^{(1)}, …, N_{1}x_{n}^{(1)}). In turn, y^{(2)} defines an element y_{A} = (N_{1}y_{1}^{(2)}, …, N_{1}y_{m−n}^{(2)}) of ℤ^{m−n}. For each point x^{(1)} + B_{j}y^{(2)}, j = 1, 2, …, m/n, there therefore exists some a_{j} ∈ A such that

x^{(1)} + B_{j}y^{(2)} = \frac{a_{j}}{N_{1}} ,

and we have that

x_{A} + B_{j}y_{A} = a_{j}, j = 1, 2, …, m/n.

To deal with the matrices B_{j}, m/n < j ≤ k, observe again that the point x + B_{l}y, l = 1, …, m/n, is an element of the set B. This implies that, for each coordinate i,

0 ≤ (ϵ(x^{(1)}) + B_{l}ϵ(y^{(2)}))_{i} < \frac{1}{2N_{1}} , l = 1, 2, …, m/n.

Since for j = m/n + 1, …, k we have B_{j} = B_{j_{1}} + B_{j_{2}} for some j_{1}, j_{2} ∈ {2, 3, …, m/n}, the above implies that

−\frac{1}{2N_{1}} < (ϵ(x^{(1)}) + B_{j_{1}}ϵ(y^{(2)}) + B_{j_{2}}ϵ(y^{(2)}))_{i} < \frac{1}{N_{1}}

for any i = 1, 2, …, n, and hence that

−\frac{1}{2N_{1}} < (ϵ(x^{(1)}) + B_{j}ϵ(y^{(2)}))_{i} < \frac{1}{N_{1}}

for any j = m/n + 1, …, k. By the same argument as above, taking into account that x + B_{j}y ∈ B also for j = m/n + 1, …, k, we can conclude that

0 ≤ (ϵ(x^{(1)}) + B_{j}ϵ(y^{(2)}))_{i} < \frac{1}{N_{1}}

and hence

x^{(1)} + B_{j}y^{(2)} = \frac{a_{j}}{N_{1}}

for some a_{j} ∈ A, m/n < j ≤ k. This establishes the result.

4.3 Existence of parallelograms

Fix n ≥ 2, k = 4 and m = 3n and suppose the set A ⊆ ℤ^{n} satisfies the conditions of Theorem 9. Let

B_{1} = 0_{n×2n}
B_{2} = (I_{n×n}0_{n×n})
B_{3} = (0_{n×n}I_{n×n})
B_{4} = B_{2} + B_{3}.

Chan et al. [2] show that the collection of matrices {A_{1}, A_{2}, A_{3}, A_{4}}, formed from {B_{1}, B_{2}, B_{3}, B_{4}} in the manner described in Theorem 9, are non-degenerate and satisfy all other conditions of the theorem. This means that there are some x ∈ ℤ^{n}, y ∈ ℤ^{2n} such that the points

x, x + [y_{1} ; ⋮ ; y_{n}] , x + [y_{n+1} ; ⋮ ; y_{2n}] , x + [y_{1} + y_{n+1} ; ⋮ ; y_{n} + y_{2n}]

are all contained in A. In other words, there are points x, u, v ∈ ℤ^{n} such that

{x, x + u, x + v, x + u + v} ⊂ A.

It is important to mention the possibility of degenerate configurations, where not all points are distinct. Setting v = 0 in the above configuration would mean that sets could trivially contain parallelograms as long as they consist of more than two elements. This is addressed by part (ii) of the conclusion of Theorem 15. By defining the subspaces V_{1}, V_{2}, V_{3}, V_{4} suitably, we can conclude that the points obtained are all distinct; see Chan et al. [2, Sec. 7]. Since the points are also separated by our N_{1}-approximation in Theorem 9, we can conclude that the elements of A obtained are also distinct.

4.4 Possible generalizations of configurations

The following generalizations of Theorem 9 suggest themselves.

1. There is of course no need to require that y ∈ ℤ^{m−n} in Theorem 9, nor even that the matrices must all have integer entries, as long as the configuration obtained exists in ℤ^{n}. For instance, if we consider assemblies 𝔹 in which the matrices have some rational but non-integer coefficients that satisfy the constraints of Theorem 15, such configurations could still exist in the set B if conditions are satisfied. This would imply that we could consider y ∈ ℚ^{m−n} instead, for which the corresponding configuration exists in A. This could be useful in establishing analogues of Corollary 1.7 in Chan et al. [2], concerning the existence of certain triangle configurations.

2. It is not necessary to assume that ζ_{i} = (2N_{i})^{−1} during the construction in Section 2. The ζ_{i} could be taken to be, for instance, (3N_{i})^{−1} (as long as some small extra growth condition is applied to (N_{i})), which would open the door to proving Theorem 9 for configurations with some matrices being the sum of three other matrices. This could allow one to prove the existence of parallelogram-like configurations in A such as {x, x+ u, x + v, x + z, x + u + v + z}, for instance.

3. Only a single value of m, the smallest possible, was considered in Theorem 9. Larger values should be considered for more general configurations, although the non-degeneracy conditions on the matrices A_{1}, …, A_{k} complicate the proof of Theorem 9

4. Just as arithmetic progressions of length greater than 3 seem to require higher-order uniformity conditions (see Conlon et al. [3], for instance), we can conjecture that more general configurations in ℤ^{n} and [0, 1]^{n} will require such conditions. It seems feasible, given the results of this paper, that these conditions will be preserved under the current construction.

5 Acknowledgments

The author would like to thank an anonymous referee whose comments and suggestions greatly improved the presentation and correctness of this paper.

References

[1] C. Bluhm, On a theorem of Kaufman: Cantor-type construction of linear fractal Salem sets, Ark. Mat. 36 (1998), 307–316.

[2] V. Chan, I. Łaba, and M. Pramanik, Finite configurations in sparse sets, J. Anal. Math. 128 (2016), 289–335.

[3] D. Conlon, J. Fox, and Y. Zhao, A relative Szemerédi theorem, Geom. Funct. Anal. 25 (2015), 733–762.

[4] K. Falconer, Fractal Geometry: Mathematical Foundations and Applications, John Wiley & Sons, 2004.

[5] K. Hambrook and I. Łaba, On the sharpness of Mockenhaupt’s restriction theorem, Geom. Funct. Anal. 23 (2013), 1262–1277.

[6] I. Łaba and M. Pramanik, Arithmetic progressions in sets of fractional dimension, Geom. Funct. Anal. 19 (2009), 429–456.

[7] G. Mockenhaupt, Salem sets and restriction properties of Fourier transforms, Geom. Funct. Anal. 10 (2000), 1579–1587.

[8] P. Potgieter, Arithmetic progressions in Salem-type subsets of the integers, J. Fourier Anal. Appl. 17 (2011), 1138–1151.

[9] R. Salem, On some properties of symmetrical perfect sets, Bull. Amer. Math. Soc. 47 (1941), 820–828.

[10] R. Salem, On singular monotonic functions whose spectrum has a given Hausdorff dimension, Ark. Mat. 1 (1951), 353–365.

[11] P. Shmerkin, Salem sets with no arithmetic progressions, Int. Math. Res. Not. 2017 (2017), 1929–1941.

[12] P. Shmerkin and V. Suomala, A class of random Cantor measures, with applications, in Conference of Fractals and Related Fields, Birkhäuser, 2005, pp. 233–260.

[13] T. Tao, Higher Order Fourier Analysis, Vol. 142. American Mathematical Soc., 2012.

[14] A. Zygmund, Trigonometric Series, Vol. 1, Cambridge University Press, 2002.

2010 Mathematics Subject Classification: Primary 42A16; Secondary 42B05, 11B25, 43A46, 28A78. Keywords: discrete Fourier transform, Fourier-Stieltjes transform, Hausdorff dimension, Fourier dimension, arithmetic progression, parallelogram.

Received August 11 2020; revised version received August 12 2020; April 15 2021. Published in Journal of Integer Sequences, April 16 2021.

Return to Journal of Integer Sequences home page.