betaFeedback

WorksMathematics

Sumsets modulo ideals: Baire category and descriptive complexity

Abstract

Given an ideal I\mathcal I on the nonnegative integers, we study the family Σ(I)Σ(\mathcal I) of all sets for which every I\mathcal{I}-small modification is not a nontrivial sumset A+BA+B. We prove that Σ(I)Σ(\mathcal I) is comeager whenever I\mathcal{I} is an Erdős–Ulam ideal generated by a nonincreasing sequence of positive weights. This answers an open question for the ideal Z\mathcal{Z} of asymptotic density zero sets in [Proc. Amer. Math. Soc. 151 (2023), 3681–3689]. We also show that Σ(I)Σ(\mathcal I) is either empty or a dense GδG_δ-complete set whenever I\mathcal{I} is an FσF_σ ideal which is invariant under finite modifications. This implies that the family of nontrivial sumsets A+BA+B is FσF_σ-complete (hence, Borel). On the other hand, we construct a meager ideal I\mathcal{I} for which Σ(I)Σ(\mathcal I) is neither meager nor comeager. Finally, we prove that Σ(Z)Σ(\mathcal Z) is coanalytic and not FσδF_{σδ}.

Introduction

Sumsets and irreducibility

A subset AA of the nonnegative integers N\mathbb{N} is said to be irreducible if it is not a nontrivial sumset, i.e., if there are no B,C⊆NB,C \subseteq\mathbb{N} such that ∣B∣,∣C∣≥2|B|,|C| \ge2 and A=B+C:={b+c:b∈B,c∈C}A=B+C:=\{b+c:b\in B,c\in C\}. Moreover, A⊆NA\subseteq\mathbb{N} is called totally irreducible if there are no sets B,C⊆NB,C\subseteq\mathbb{N} such that ∣B∣,∣C∣≥2|B|,|C|\ge2 and A△(B+C)A\mathbin{\triangle}(B+C) is finite, cf. [2, 10]. Let Σ\Sigma and Σ⋆\Sigma_\star be the families of irreducible and totally irreducible sets, respectively, so that Σ⋆⊆Σ\Sigma_\star\subseteq\Sigma. Let R\mathcal{R} and R⋆\mathcal{R}_\star respectively be their complements to P(N)\mathcal{P}(\mathbb{N}). Wirsing [10] initiated the investigation of these families of subsets of N\mathbb{N} and discovered that Σ⋆\Sigma_\star had full measure, in other words, that almost all sets of integers are totally irreducible; the measure here is the natural product probability measure on P(N)\mathcal{P}(\mathbb{N}).

In this article, we will use a stronger notion of irreducibility, which describes a set, every “small” alteration (deletion or insertion of small subsets) of which is again irreducible. Following [7 Definition 1.3], given I⊆P(N)\mathcal{I}\subseteq\mathcal{P}(\mathbb{N}), thought to be a family of small subsets, we denote by Σ(I)\Sigma(\mathcal{I}) the family of I\mathcal{I}-irreducible sets, namely,

Σ(I)={A⊆N:A≠I(B+C) for all B,C⊆N with ∣B∣,∣C∣≥2},\Sigma(\mathcal{I})=\{A\subseteq\mathbb{N}: A\ne_{\mathcal{I}}(B+C)\text{ for all }B,C\subseteq\mathbb{N}\text{ with }|B|,|C|\ge2\},

where A≠I(B+C)A\ne_{\mathcal{I}}(B+C) stands for A△(B+C)∉IA\mathbin{\triangle}(B+C)\notin\mathcal{I}. We denote by R(I)=P(N)∖Σ(I)\mathcal{R}(\mathcal{I})=\mathcal{P}(\mathbb{N})\setminus\Sigma(\mathcal{I}) its complement. In particular,

Σ=Σ({∅})andΣ⋆=Σ(Fin)\Sigma=\Sigma(\{\varnothing\})\qquad\text{and}\qquad\Sigma_\star=\Sigma(\mathrm{Fin})

where Fin\mathrm{Fin} stands for the family of all finite subsets of N\mathbb{N}.

Since I\mathcal{I} represents a family of small sets, this notion is attractive when I\mathcal{I} is an ideal on N\mathbb{N}, that is, a nonempty family of subsets stable under subsets and finite unions. A family I⊆P(N)\mathcal{I} \subseteq\mathcal{P}(\mathbb{N}) is admissible if it is stable under finite modifications, i.e., A△F∈IA \mathbin{\triangle} F \in\mathcal{I} for all A∈IA \in\mathcal{I} and F∈FinF \in\mathrm{Fin}. An admissible family which is an ideal, equivalently an ideal containing Fin\mathrm{Fin}, is called an admissible ideal.

Examples of ideals are the trivial family {∅}\{\varnothing\}, the family of finite sets Fin\mathrm{Fin}, the summable ideal

I1/n:={A⊆N:∑n∈A1n+1<∞}\mathcal{I}_{1/n}:=\left\{A\subseteq\mathbb{N}:\sum_{n\in A}\frac{1}{n+1}<\infty\right\}

the family Z\mathcal{Z} of asymptotic density zero sets, or the families

Zα={A⊆N:∣A(n)∣=o(nα) as n→∞}\mathcal{Z}_{\alpha}=\left\{A\subseteq\mathbb{N}:|A(n)|=o(n^{\alpha})\text{ as }n\to\infty\right\}

for each α∈(0,1]\alpha\in(0,1], where A(n):=A∩[0,n]A(n):=A\cap[0,n] (of course, Z1=Z\mathcal{Z}_{1}=\mathcal{Z}).

Observe that, if I\mathcal{I} is an ideal on N\mathbb{N}, the binary relation between sets of nonnegative integers A=IB⟺A△B∈IA =_{\mathcal{I}} B \Longleftrightarrow A\mathbin{\triangle}B\in\mathcal{I} is an equivalence relation, and Σ(I)\Sigma(\mathcal{I}) is the set of all sets of nonnegative integers whose equivalence class contains no nontrivial sumsets. In addition, Σ(⋅)\Sigma(\cdot) is nonincreasing on P(P(N))\mathcal{P}(\mathcal{P}(\mathbb{N})), i.e., Σ(I)⊆Σ(J)\Sigma(\mathcal{I})\subseteq\Sigma(\mathcal{J}) for all families I,J⊆P(N)\mathcal{I},\mathcal{J}\subseteq\mathcal{P}(\mathbb{N}) with J⊆I\mathcal{J}\subseteq\mathcal{I}. Further Σ(∅)=P(N)\Sigma(\varnothing)=\mathcal{P}(\mathbb{N}) and Σ(P(N))=∅\Sigma(\mathcal{P}(\mathbb{N}))=\varnothing, so it suffices to study Σ(I)\Sigma(\mathcal{I}) in the case of nonempty proper families I\mathcal{I}.

Topological and measure framework

In this paper, we focus on topological and measure-theoretic properties of Σ(I)\Sigma(\mathcal{I}). To this end, we identify P(N)\mathcal{P}(\mathbb{N}) with {0,1}N\{0,1\}^{\mathbb{N}}. Equipped with the product topology, it is a compact space by Tychonoff’s theorem. In fact, (P(N),△)(\mathcal{P}(\mathbb{N}),\triangle) can be regarded as the abelian compact topological group ((Z/2Z)N,+)((\mathbb{Z}/2\mathbb{Z})^{\mathbb{N}},+).

We endow this group with the completion λ\lambda of the Bernoulli product probability measure

(12δ0+12δ1)⊗N.\left(\tfrac{1}{2}\delta_{0}+\tfrac{1}{2}\delta_{1}\right)^{\otimes\mathbb{N}}.

Its restriction to the Borel σ\sigma-algebra is the unique Haar probability measure, where translation is the action of △\triangle. Further, the map {0,1}N→[0,1]\{0,1\}^{\mathbb{N}}\to[0,1] defined by x↦∑ixi2−i−1x\mapsto\sum_i x_i2^{-i-1} preserves the measure, and induces a bijection P(N)∖Fin→(0,1]\mathcal{P}(\mathbb{N})\setminus\mathrm{Fin}\to(0,1] (by the nonterminating dyadic expansion) and a homeomorphism from the set of all infinite noncofinite subsets of N\mathbb{N} to the set of all nondyadic real numbers in (0,1)(0,1). Since cofinite subsets and dyadic rationals are countable, measure and Baire category statements do not depend on the chosen framework. Recall that {0,1}N\{0,1\}^{\mathbb{N}} is a zero-dimensional Polish space, that is, a separable and completely metrizable topological space with a base of clopen sets.

Recall that a subset of a topological space is nowhere dense if its closure has empty interior, meager if it is a countable union of nowhere dense sets, and comeager if its complement is meager. A set has the Baire property if it differs from an open set by a meager set. By the Baire Category Theorem [6 Theorem 8.4], in a Polish space every comeager set is dense. Lastly, given a pointclass Γ⊆P(P(N))\Gamma\subseteq\mathcal{P}(\mathcal{P}(\mathbb{N})) (for instance, Γ={S⊆P(N):S is a Gδ subset}\Gamma=\{S\subseteq\mathcal{P}(\mathbb{N}):S\text{ is a }G_{\delta}\text{ subset}\}), we say that S⊆P(N)S\subseteq\mathcal{P}(\mathbb{N}) is Γ\Gamma-complete if S∈ΓS\in\Gamma and P(N)∖S∉Γ\mathcal{P}(\mathbb{N})\setminus S\notin\Gamma, cf. [6 Definition 22.9 and Theorem 22.10].

Main results

The following has been shown in [7 Theorem 1.4].

Theorem 2.1. Σ(Zα)\Sigma(\mathcal{Z}_{\alpha}) is a comeager subset of P(N)\mathcal{P}(\mathbb{N}) for all α∈(0,1/3)\alpha\in(0,1/3).

It was left open in [7 Section 3] whether the smaller subset Σ(Z)\Sigma(\mathcal{Z}) is comeager as well. Below, we provide an affirmative answer to this question, hence generalizing Theorem 2.1. To this aim, given a positive real sequence (wn)n≥0(w_n)_{n\geq0} such that ∑nwn=∞\sum_n w_n=\infty and lim⁡nwn/∑k≤nwk=0\lim_n w_n/\sum_{k\leq n}w_k=0, define the Erdős–Ulam ideal

Zw:={A⊆N:lim⁡n→∞∑k∈A∩[0,n]wk∑k∈[0,n]wk=0},\mathcal{Z}_w:=\left\{A\subseteq\mathbb{N}:\lim_{n\to\infty}\frac{\sum_{k\in A\cap[0,n]}w_k}{\sum_{k\in[0,n]}w_k}=0\right\},

see e.g. [3 Section 1.13] or [1, 5]. It is immediate that, if wn=1w_n=1 for each n∈Nn\in\mathbb{N}, then Zw=Z\mathcal{Z}_w=\mathcal{Z}.

Theorem 2.2. Let (wn)n≥0(w_n)_{n\geq0} be a nonincreasing positive real sequence with ∑nwn=∞\sum_n w_n=\infty. Then Σ(Zw)\Sigma(\mathcal{Z}_w) is a comeager subset of P(N)\mathcal{P}(\mathbb{N}).

Now we turn to Σ(I)\Sigma(\mathcal{I}) for general classes I\mathcal{I} (hence, not necessarily ideals). We obtain a number of basic topological properties.

Proposition 2.3. Pick a nonempty family I⊆P(N)\mathcal{I}\subseteq\mathcal{P}(\mathbb{N}). Then the following hold:

  • (i) If I\mathcal{I} is FσF_\sigma then Σ(I)\Sigma(\mathcal{I}) is GδG_\delta;

  • (ii) If I\mathcal{I} is analytic then Σ(I)\Sigma(\mathcal{I}) is coanalytic;

  • (iii) P(N)∖Σ(I)\mathcal{P}(\mathbb{N})\setminus\Sigma(\mathcal{I}) is dense;

  • (iv) If Σ(I)\Sigma(\mathcal{I}) is comeager then Σ(I)\Sigma(\mathcal{I}) is not FσF_\sigma;

  • (v) If I\mathcal{I} is admissible then Σ(I)\Sigma(\mathcal{I}) is either empty or invariant under finite modifications (hence dense);

  • (vi) If I\mathcal{I} is admissible and Σ(I)\Sigma(\mathcal{I}) has the Baire property then Σ(I)\Sigma(\mathcal{I}) is either meager or comeager.

  • (vii) If Σ(I)\Sigma(\mathcal{I}) is comeager, then I\mathcal{I} is meager.

In view of these results, one might conjecture that Σ(I)\Sigma(\mathcal{I}) is comeager for all ideals I\mathcal{I} with sufficiently low topological complexity. The following result shows that this is false, even for well-behaved FσF_\sigma ideals. Here, an ideal I\mathcal{I} is said to be translation-invariant if S+k:={n∈N:n−k∈S}∈IS+k:=\{n\in\mathbb{N}:n-k\in S\}\in\mathcal{I} for all S∈IS\in\mathcal{I} and k∈Zk\in\mathbb{Z}.

Theorem 2.4. There exists an admissible proper translation-invariant FσF_\sigma ideal I\mathcal{I} on N\mathbb{N} such that Σ(I)=∅\Sigma(\mathcal{I})=\varnothing.

Alternatively, one might conjecture that if I\mathcal{I} is a meager ideal then Σ(I)\Sigma(\mathcal{I}) is either meager or comeager (note that, thanks to Proposition 2.3, this holds if I\mathcal{I} is an admissible analytic ideal). Again, this turns out to be false.

Theorem 2.5. There exists an admissible meager ideal I\mathcal{I} on N\mathbb{N} such that Σ(I)\Sigma(\mathcal{I}) is neither meager nor comeager in P(N)\mathcal{P}(\mathbb{N}).

Next, relying on Proposition 2.3, we find the exact topological complexity of certain families of I\mathcal{I}-irreducible sets. In a related result, Schmerl proved in [8] that the family {(A−A)∩N:A⊆N}\{(A-A)\cap\mathbb{N}:A\subseteq\mathbb{N}\} is analytic but not coanalytic (hence, in particular, not Borel).

Theorem 2.6. Let I\mathcal{I} be an admissible nonempty FσF_\sigma subset of P(N)\mathcal{P}(\mathbb{N}). Then Σ(I)\Sigma(\mathcal{I}) is either empty or dense GδG_\delta-complete (hence comeager).

Note that Σ(I)\Sigma(\mathcal{I}) may well be empty even under the hypotheses of Theorem 2.6, see Theorem 2.4. Moreover, establishing Σ(I)≠∅\Sigma(\mathcal{I})\ne\varnothing is not always easy when it is true: in fact, an elementary argument shows that any infinite set A⊆NA \subseteq\mathbb{N} with increasing enumeration (an:n∈N)(a_n : n \in\mathbb{N}) satisfying lim⁡n(an+1−an)=∞\lim_{n}(a_{n+1}-a_n)=\infty is totally irreducible, i.e., A∈Σ(Fin)A \in\Sigma(\mathrm{Fin}), but there does not seem to be a simpler argument than the probabilistic one for the analogous nonemptiness result for, e.g., Σ(I1/n)\Sigma(\mathcal{I}_{1/n}).

Combining Proposition 2.3 and Theorem 2.2, we obtain the following.

Corollary 2.7. Each of the families Σ\Sigma, Σ⋆\Sigma_\star, and Σ(I1/n)\Sigma(\mathcal{I}_{1/n}) is dense GδG_\delta-complete (hence comeager), and with empty interior.

In particular, the family R=P(N)∖Σ\mathcal{R}=\mathcal{P}(\mathbb{N})\setminus\Sigma of all nontrivial sumsets is FσF_\sigma-complete.

In the case of the ideal Z\mathcal{Z}, we get the following.

Corollary 2.8. Σ(Z)\Sigma(\mathcal{Z}) is comeager, coanalytic, not FσF_\sigma, and with empty interior.

It would be interesting to calculate the exact topological complexity of Σ(Z)\Sigma(\mathcal{Z}), hence, in particular, whether it is Borel or not.

Question 2.9. Is Σ(Z)\Sigma(\mathcal{Z}) Borel?

Although we do not have an answer to Question 2.9, we conclude by showing, in particular, that the complexity of Σ(Z)\Sigma(\mathcal{Z}) is at least GδσG_{\delta\sigma}.

Theorem 2.10. Let (wn)n≥0(w_n)_{n\geq0} be a nonincreasing positive real sequence with ∑nwn=∞\sum_n w_n=\infty. Then Σ(Zw)\Sigma(\mathcal{Z}_w) is not FσδF_{\sigma\delta}.

The proofs of our results are given in the next section.

Proofs

First, we need some preliminaries. To this end, define the family

Z−:={A⊆N:lim inf⁡n→∞∣A(n)∣n=0}.\mathcal{Z}_{-}:=\left\{A\subseteq\mathbb{N}:\liminf_{n\to\infty}\frac{|A(n)|}{n}=0\right\}.

Notice that Z−\mathcal{Z}_{-} need not be an ideal (more precisely, Z−\mathcal{Z}_{-} is stable under subsets but not under finite unions). Hereafter, we will use the following slight abuse of notation common in probability theory: given a predicate P(X)P(X) on a set X∈P(N)X\in\mathcal{P}(\mathbb{N}), we write λ(P(X))\lambda(P(X)) for λ({X∈P(N):P(X)})\lambda(\{X\in\mathcal{P}(\mathbb{N}):P(X)\}). Also, we define

η:=1100\eta:=\frac{1}{100}

and

Ih(n):=((1−12h)n,n]∩NI_h(n):=\left(\left(1-\frac{1}{2^h}\right)n,n\right]\cap\mathbb{N}

for all integers h,n∈Nh,n\in\mathbb{N}. In addition, for each t∈(0,1)t\in(0,1), set

H(t):=−tlog⁡2t−(1−t)log⁡2(1−t).H(t):=-t\log_2 t-(1-t)\log_2(1-t).

Observe that lim⁡t→0H(t)=0\lim_{t\to0}H(t)=0. In particular, for each t∈(0,1)t\in(0,1), it is possible to fix εt∈(0,1/2)\varepsilon_t\in(0,1/2) such that H(εt)<t/8H(\varepsilon_t)<t/8.

Lemma 3.1. The following properties are satisfied by λ\lambda-almost every set X⊆NX\subseteq\mathbb{N}:

(i) for every finite F⊆ZF\subseteq\mathbb{Z}, every G⊆FG\subseteq F and every h∈Nh\in\mathbb{N},

lim⁡n→∞∣{t∈Ih(n):t+F⊆N and X∩(t+F)=t+G}∣∣Ih(n)∣=12∣F∣.(1)\lim_{n\to\infty}\frac{\left|\left\{t\in I_h(n):t+F\subseteq\mathbb{N}\ \text{and}\ X\cap(t+F)=t+G\right\}\right|}{|I_h(n)|}=\frac{1}{2^{|F|}}. \tag*{(1)}

(ii) for every integer h≥1h \ge1 and for every sufficiently large n∈Nn \in\mathbb{N}, there are no sets P,Q⊆[0,n]P,Q \subseteq[0,n] satisfying

∣P∣,∣Q∣≤ε2−hnand∣(X△(P+Q))∩Ih(n)∣≤η∣Ih(n)∣.(2)|P|,|Q| \le\varepsilon2^{-h}n \qquad\text{and}\qquad|(X \mathbin{\triangle} (P+Q)) \cap I_h(n)| \le\eta|I_h(n)|. \tag*{(2)}

Proof. (i) Fix G⊆F⊆ZG \subseteq F \subseteq\mathbb{Z} and h∈Nh \in\mathbb{N}. If F=∅F=\varnothing the claim is clear. Otherwise, set r:=max⁡F−min⁡Fr:=\max F-\min F. At most ∣min⁡F∣|\min F| elements t∈Ih(n)t\in I_h(n) violate t+F⊆Nt+F\subseteq\mathbb{N}, so we may restrict to the others. For these, the random variables

ξt=ξt(X):=1{X∩(t+F)=t+G}\xi_t=\xi_t(X):=\mathbf{1}\{X\cap(t+F)=t+G\}

have mean 2−∣F∣2^{-|F|}.

For tt ranging over a fixed residue class modulo r+1r+1, the sets t+Ft+F are pairwise disjoint, so inside each of the r+1r+1 classes the ξt\xi_t are independent; each class has at most 2n/(r+1)2n/(r+1) elements if n≥r+1n\ge r+1. Combined with the pigeonhole principle, Hoeffding’s inequality [4 Theorem 1], applied in each class with deviation n3/4/(r+1)n^{3/4}/(r+1), shows that the numerator in (1) differs from 2−∣F∣∣Ih(n)∣2^{-|F|}|I_h(n)| by more than n3/4+∣min⁡F∣n^{3/4}+|\min F| with probability at most

pn=2(r+1)en/(r+1).p_n=\frac{2(r+1)}{e^{\sqrt{n}/(r+1)}}.

Observe that ∑npn<∞\sum_n p_n<\infty. Hence, the conclusion follows by the Borel–Cantelli lemma and a countable intersection over (F,G,h)(F,G,h).

(ii) Fix a positive integer hh and set ε:=ε2−h\varepsilon:=\varepsilon2^{-h}. Observe that

∀n∈N, ∀θ∈[0,1/2],∑i=0θn(ni)≤2H(θ)n.\forall n\in\mathbb{N},\ \forall\theta\in[0,1/2],\qquad\sum_{i=0}^{\theta n}\binom{n}{i}\le2^{H(\theta)n}.

Hence there are at most 22H(ε)(n+1)2^{2H(\varepsilon)(n+1)} pairs (P,Q)(P,Q) of subsets of [0,n][0,n] of size at most εn\varepsilon n. For a fixed pair, set R:=(P+Q)∩Ih(n)R:=(P+Q)\cap I_h(n) and note that the coordinates of XX on Ih(n)I_h(n) are independent and each with probability 1/21/2, so

λ(∣(X△R)∩Ih(n)∣≤η∣Ih(n)∣)≤12(1−H(η))∣Ih(n)∣.\lambda\bigl(|(X\mathbin{\triangle}R)\cap I_h(n)|\le\eta|I_h(n)|\bigr)\le\frac{1}{2^{(1-H(\eta))|I_h(n)|}}.

Since ∣Ih(n)∣≥2−hn|I_h(n)|\ge2^{-h}n, H(η)<1/10H(\eta)<1/10, and 2H(ε)≤2−h−22H(\varepsilon)\le2^{-h-2}, the probability that some pair satisfies (2) is at most 2−n/2h+1+12^{-n/2^{h+1}+1}. As in the previous point, the latter sequence is summable in nn, hence the conclusion follows by the Borel–Cantelli lemma and a countable intersection over h≥1h\ge1. □

The following lemma is not probabilistic but demonstrates some rigidity properties of a set satisfying the generic properties outlined in Lemma 3.1. Roughly, a sumset cannot stay essentially inside XX below some large nn while coinciding essentially with XX on the final segment Ih(n)I_h(n).

Lemma 3.2. Pick a set X⊆NX\subseteq\mathbb{N} satisfying the conditions of Lemma 3.1, and fix an integer ℓ≥1\ell\ge1. Then there are no sets B,C⊆NB,C\subseteq\mathbb{N} with ∣B∣,∣C∣≥2|B|,|C|\ge2 such that

lim inf⁡n→∞∣(B+C)∖X∣(n)+∣(X△(B+C))∩Iℓ(n)∣n=0.(3)\liminf_{n\to\infty}\frac{|(B+C)\setminus X|(n)+|(X\mathbin{\triangle}(B+C))\cap I_\ell(n)|}{n}=0. \tag*{(3)}

Proof. Let us suppose for the sake of contradiction that there exists a strictly increasing sequence (nj)(n_j) in N\mathbb{N} and sets B,C⊆NB,C\subseteq\mathbb{N} with ∣B∣,∣C∣≥2|B|,|C|\ge2 such that

∣(S∖X)(nj)∣=o(nj)and∣(X△S)∩Ij∣=o(nj).|(S\setminus X)(n_j)|=o(n_j)\qquad\text{and}\qquad|(X\mathbin{\triangle}S)\cap I_j|=o(n_j).

as j→∞j \to\infty, where S:=B+CS := B + C and Ij:=Iℓ(nj)I_j := I_{\ell}(n_j) for all j∈Nj \in\mathbb{N}. Define also c:=2−ℓc := 2^{-\ell} and

∀j∈N,ej:=∣(S∖X)(nj)∣+∣(X△S)∩Ij∣,\forall j \in\mathbb{N},\qquad e_j := |(S \setminus X)(n_j)| + |(X \triangle S) \cap I_j|,

and observe that $\lim_j e_j/n_j = 0.

B and C are infinite. Suppose that BB is finite and put m:=1+max⁡Bm := 1+\max B. By (1) with F={−m,…,m}F = \{-m,\ldots,m\}, h=ℓh = \ell and G={0}G = \{0\}, the interval IjI_j contains at least 2−(2m+1)cnj−o(nj)2^{-(2m+1)}cn_j-o(n_j) points tt with X∩[t−m,t+m]={t}X \cap[t-m,t+m] = \{t\}. If such a tt is not in SS, it lies in (X△S)∩Ij(X \triangle S)\cap I_j. Otherwise t=b+yt=b+y with b∈Bb \in B, y∈Cy \in C; choosing b′∈B∖{b}b' \in B \setminus\{b\}, the point t′:=b′+yt' := b'+y lies in SS, satisfies 0<∣t′−t∣<m0 < |t'-t| < m, hence t′∉Xt' \notin X, i.e., t′∈(S∖X)(nj+m)t' \in(S \setminus X)(n_j+m). Each t′t' arises from at most 2m+12m+1 points tt. Therefore

2−(2m+1)cnj−o(nj)≤∣(X△S)∩Ij∣+(2m+1)(∣(S∖X)(nj)∣+m)≤(2m+1)(ej+m),2^{-(2m+1)}cn_j-o(n_j) \le|(X \triangle S)\cap I_j| + (2m+1)(|(S \setminus X)(n_j)|+m) \le(2m+1)(e_j+m),

a contradiction. By symmetry, CC is infinite as well.

B(nj)B(n_j) and C(nj)C(n_j) are small. Fix k∈Nk \in\mathbb{N} with 2−(k+1)≤εc/22^{-(k+1)} \le\varepsilon c/2, let b0<⋯<bkb_0 < \cdots< b_k be the first k+1k+1 elements of BB and F:={bi−b0:i≤k}⊆NF := \{b_i-b_0:i\le k\}\subseteq\mathbb{N}. At most bkb_k elements y∈C(nj)y \in C(n_j) satisfy y+bk>njy+b_k>n_j. If y∈Cy \in C and y+bk≤njy+b_k\le n_j, the points y+b0,…,y+bky+b_0,\ldots,y+b_k belong to S(nj)S(n_j); if none of them lies in S∖XS\setminus X, then t:=y+b0∈[0,nj]t:=y+b_0\in[0,n_j] satisfies t+F⊆Xt+F\subseteq X, and y↦ty\mapsto t is injective. Each point of S∖XS\setminus X can be written as y+biy+b_i in at most k+1k+1 ways. By (1) with G=FG=F and h=0h=0, we obtain

∣C(nj)∣≤bk+1+2−(k+1)nj+o(nj)+(k+1)∣(S∖X)(nj)∣≤εcnj|C(n_j)| \le b_k+1+2^{-(k+1)}n_j+o(n_j)+(k+1)|(S\setminus X)(n_j)|\le\varepsilon c n_j

for all large jj. Exchanging the roles of BB and CC gives ∣B(nj)∣≤εcnj|B(n_j)|\le\varepsilon c n_j.

Conclusion. Put P:=B(nj)P:=B(n_j) and Q:=C(nj)Q:=C(n_j). Every element of S∩[0,nj]S\cap[0,n_j] is a sum of elements of PP and QQ, so S∩Ij=(P+Q)∩IjS\cap I_j=(P+Q)\cap I_j and

∣(X△(P+Q))∩Ij∣=∣(X△S)∩Ij∣≤ej≤ηcnj≤η∣Ij∣|(X\triangle(P+Q))\cap I_j|=|(X\triangle S)\cap I_j|\le e_j\le\eta c n_j\le\eta|I_j|

for all large jj. Together with ∣P∣,∣Q∣≤εcnj|P|,|Q|\le\varepsilon c n_j, this contradicts Lemma 3.1(ii) with h=ℓh=\ell and n=njn=n_j. □\square

The following provides a strengthening of [7], Theorem 1.5.

Proposition 3.3. λ(Σ(Z−))=1\lambda(\Sigma(\mathcal{Z}_{-}))=1.

Proof. By Lemma 3.1, it suffices to show that every set XX which satisfies the two properties of that lemma belongs to Σ(Z−)\Sigma(\mathcal{Z}_{-}). Let XX be as in Lemma 3.1, and suppose that D:=X△S∈Z−D:=X\triangle S\in\mathcal{Z}_{-} for some S=B+CS=B+C with ∣B∣,∣C∣≥2|B|,|C|\ge2. Choose nj→∞n_j\to\infty with ∣D(nj)∣=o(nj)|D(n_j)|=o(n_j). Since S∖X⊆DS\setminus X\subseteq D and (X△S)∩I1(nj)⊆D(nj)(X\triangle S)\cap I_1(n_j)\subseteq D(n_j), we have

∣(S∖X)(nj)∣+∣(X△S)∩I1(nj)∣≤2∣D(nj)∣=o(nj).|(S\setminus X)(n_j)|+|(X\triangle S)\cap I_1(n_j)|\le2|D(n_j)|=o(n_j).

Hence the liminf in (3) with ℓ=1\ell=1 vanishes, which contradicts Lemma 3.2. □\square

Before we proceed to the proof of Theorem 2.2, we show another intermediate claim. Hereafter, if (wn)n≥0(w_n)_{n\ge0} is a positive real sequence with ∑nwn=∞\sum_n w_n=\infty, we write

∀n∈N,W(n):=∑k=0nwk.(4)\forall n\in\mathbb{N},\qquad W(n):=\sum_{k=0}^{n}w_k. \tag*{(4)}

Lemma 3.4. Let (wn)n≥0(w_n)_{n\ge0} be a nonincreasing positive real sequence with ∑nwn=∞\sum_n w_n=\infty. Pick sequences (am)(a_m) and (bm)(b_m) of positive integers such that

am<bm,lim⁡m→∞am=∞,andlim sup⁡m→∞W(am)W(bm)<1.(5)a_m<b_m,\qquad\lim_{m\to\infty}a_m=\infty,\qquad\text{and}\qquad\limsup_{m\to\infty}\frac{W(a_m)}{W(b_m)}<1. \tag*{(5)}

Then

∀D∈Zw,lim⁡m→∞min⁡am≤n≤bm∣D(n)∣n=0.(6)\forall D\in\mathcal{Z}_w,\qquad\lim_{m\to\infty}\min_{a_m\le n\le b_m}\frac{|D(n)|}{n}=0. \tag*{(6)}

Proof. Suppose that (3.5) holds, and pick D⊆ND\subseteq\mathbb{N} such that (3.6) fails. Then there exist ε>0\varepsilon>0 and a strictly increasing sequence (mj)(m_j) of positive integers such that ∣D(n)∣≥εn|D(n)|\ge\varepsilon n for every n∈[amj,bmj]n\in[a_{m_j},b_{m_j}] and every j∈Nj\in\mathbb{N}. Since (wn)(w_n) is nonincreasing, summation by parts gives

∀j∈N,∑d∈D(bmj)wd=∣D(bmj)∣wbmj+∑t=amjbmj−1∣D(t)∣(wt−wt+1)≥εbmjwbmj+ε∑t=amjbmj−1t(wt−wt+1)=ε(amjwamj+∑t=amj+1bmjwt)≥ε(W(bmj)−W(amj)).\begin{aligned} \forall j\in\mathbb{N},\qquad \sum_{d\in D(b_{m_j})}w_d =|D(b_{m_j})|w_{b_{m_j}}+\sum_{t=a_{m_j}}^{b_{m_j}-1}|D(t)|(w_t-w_{t+1}) \\ &\ge\varepsilon b_{m_j}w_{b_{m_j}}+\varepsilon\sum_{t=a_{m_j}}^{b_{m_j}-1}t(w_t-w_{t+1}) \\ &=\varepsilon\left(a_{m_j}w_{a_{m_j}}+\sum_{t=a_{m_j}+1}^{b_{m_j}}w_t\right) \\ &\ge\varepsilon\bigl(W(b_{m_j})-W(a_{m_j})\bigr). \end{aligned}

It follows that

∀j∈N,∑d∈D(bmj)wdW(bmj)≥ε(1−W(amj)W(bmj)).\forall j\in\mathbb{N},\qquad \frac{\sum_{d\in D(b_{m_j})}w_d}{W(b_{m_j})} \ge\varepsilon\left(1-\frac{W(a_{m_j})}{W(b_{m_j})}\right).

By (3.5), the right-hand side is bounded below by a positive constant for all large jj. This proves that D∉ZwD\notin\mathcal{Z}_w. □\square

Proof of Theorem 2.2. Thanks to Proposition 3.3, it is possible to fix a set X∈Σ(Z−)X\in\Sigma(\mathbb{Z}_{-}). For every integer k≥1k\ge1, choose hk>k2h_k>k^2 such that

W(k2)W(hk)≤1k.(7)\frac{W(k^2)}{W(h_k)}\le\frac{1}{k}. \tag*{(7)}

For every m≥1m\ge1, define the open set

Um:=⋃k≥m{A⊆N:A∩(k,hk]=X∩(k,hk]}.U_m:=\bigcup_{k\ge m}\{A\subseteq\mathbb{N}:A\cap(k,h_k]=X\cap(k,h_k]\}.

In addition, UmU_m is dense. Indeed, fix a nonempty basic open set V:={A⊆N:A(N)=F}V:=\{A\subseteq\mathbb{N}:A(N)=F\}, where N∈NN\in\mathbb{N} and F⊆[0,N]F\subseteq[0,N]. Choosing k>max⁡{m,N}k>\max\{m,N\}, we may prescribe the coordinates in (k,hk](k,h_k] to agree with those of XX without changing the coordinates in [0,N][0,N]. Therefore V∩Um≠∅V\cap U_m\ne\varnothing.

It follows from the Baire category theorem, see e.g. [6 Theorem 8.4], that

U:=⋂m≥1UmU:=\bigcap_{m\ge1}U_m

@page 7/15 starts_mid=0 ends_mid=1

Lemma 3.4. Let (wn)n≥0(w_n)_{n\ge0} be a nonincreasing positive real sequence with ∑nwn=∞\sum_n w_n=\infty. Pick sequences (am)(a_m) and (bm)(b_m) of positive integers such that

am<bm,lim⁡m→∞am=∞,andlim sup⁡m→∞W(am)W(bm)<1.(8)a_m<b_m,\qquad\lim_{m\to\infty}a_m=\infty,\qquad\text{and}\qquad\limsup_{m\to\infty}\frac{W(a_m)}{W(b_m)}<1. \tag*{(8)}

Then

∀D∈Zw,lim⁡m→∞min⁡am≤n≤bm∣D(n)∣n=0.(9)\forall D\in\mathcal{Z}_w,\qquad\lim_{m\to\infty}\min_{a_m\le n\le b_m}\frac{|D(n)|}{n}=0. \tag*{(9)}

Proof. Suppose that (3.5) holds, and pick D⊆ND\subseteq\mathbb{N} such that (3.6) fails. Then there exist ε>0\varepsilon>0 and a strictly increasing sequence (mj)(m_j) of positive integers such that ∣D(n)∣≥εn|D(n)|\ge\varepsilon n for every n∈[amj,bmj]n\in[a_{m_j},b_{m_j}] and every j∈Nj\in\mathbb{N}. Since (wn)(w_n) is nonincreasing, summation by parts gives

∀j∈N,∑d∈D(bmj)wd=∣D(bmj)∣wbmj+∑t=amjbmj−1∣D(t)∣(wt−wt+1)≥εbmjwbmj+ε∑t=amjbmj−1t(wt−wt+1)=ε(amjwamj+∑t=amj+1bmjwt)≥ε(W(bmj)−W(amj)).\begin{aligned} \forall j\in\mathbb{N},\qquad \sum_{d\in D(b_{m_j})}w_d =|D(b_{m_j})|w_{b_{m_j}}+\sum_{t=a_{m_j}}^{b_{m_j}-1}|D(t)|(w_t-w_{t+1}) \\ &\ge\varepsilon b_{m_j}w_{b_{m_j}}+\varepsilon\sum_{t=a_{m_j}}^{b_{m_j}-1}t(w_t-w_{t+1}) \\ &=\varepsilon\left(a_{m_j}w_{a_{m_j}}+\sum_{t=a_{m_j}+1}^{b_{m_j}}w_t\right) \\ &\ge\varepsilon\bigl(W(b_{m_j})-W(a_{m_j})\bigr). \end{aligned}

It follows that

∀j∈N,∑d∈D(bmj)wdW(bmj)≥ε(1−W(amj)W(bmj)).\forall j\in\mathbb{N},\qquad \frac{\sum_{d\in D(b_{m_j})}w_d}{W(b_{m_j})} \ge\varepsilon\left(1-\frac{W(a_{m_j})}{W(b_{m_j})}\right).

By (3.5), the right-hand side is bounded below by a positive constant for all large jj. This proves that D∉ZwD\notin\mathcal{Z}_w. □\square

Proof of Theorem 2.2. Thanks to Proposition 3.3, it is possible to fix a set X∈Σ(Z−)X\in\Sigma(\mathbb{Z}_{-}). For every integer k≥1k\ge1, choose hk>k2h_k>k^2 such that

W(k2)W(hk)≤1k.(10)\frac{W(k^2)}{W(h_k)}\le\frac{1}{k}. \tag*{(10)}

For every m≥1m\ge1, define the open set

Um:=⋃k≥m{A⊆N:A∩(k,hk]=X∩(k,hk]}.U_m:=\bigcup_{k\ge m}\{A\subseteq\mathbb{N}:A\cap(k,h_k]=X\cap(k,h_k]\}.

In addition, UmU_m is dense. Indeed, fix a nonempty basic open set V:={A⊆N:A(N)=F}V:=\{A\subseteq\mathbb{N}:A(N)=F\}, where N∈NN\in\mathbb{N} and F⊆[0,N]F\subseteq[0,N]. Choosing k>max⁡{m,N}k>\max\{m,N\}, we may prescribe the coordinates in (k,hk](k,h_k] to agree with those of XX without changing the coordinates in [0,N][0,N]. Therefore V∩Um≠∅V\cap U_m\ne\varnothing.

It follows from the Baire category theorem, see e.g. [6 Theorem 8.4], that

U:=⋂m≥1UmU:=\bigcap_{m\ge1}U_m

is comeager. To complete the proof, we claim that

U⊆Σ(Zw).(11)U \subseteq\Sigma(\mathcal{Z}_w). \tag*{(11)}

To this aim, fix A∈UA \in U. There exists a strictly increasing sequence (kj)(k_j) such that

A∩(kj,hkj]=X∩(kj,hkj](12)A \cap(k_j,h_{k_j}] = X \cap(k_j,h_{k_j}] \tag*{(12)}

for every jj. Suppose, towards a contradiction, that A∉Σ(Zw)A \notin\Sigma(\mathcal{Z}_w). Then there exist B,C⊆NB,C \subseteq\mathbb{N}, with ∣B∣,∣C∣≥2|B|,|C| \ge2, such that

D:=A△(B+C)∈Zw.D := A \mathbin{\triangle} (B+C) \in\mathcal{Z}_w.

Now, set aj:=kj2a_j := k_j^2 and bj:=hkjb_j := h_{k_j} for each jj, and note that lim⁡jaj=∞\lim_j a_j = \infty and lim⁡jW(aj)/W(bj)=0\lim_j W(a_j)/W(b_j) = 0 by (3.7). It follows by Lemma 3.4 that there exist integers nj∈[kj2,hkj]n_j \in[k_j^2,h_{k_j}] such that

lim⁡j→∞∣D(nj)∣nj=0.(13)\lim_{j\to\infty}\frac{|D(n_j)|}{n_j}=0. \tag*{(13)}

On the other hand, (12) implies that (A△X)(nj)⊆[0,kj](A \mathbin{\triangle} X)(n_j) \subseteq[0,k_j]. Since nj≥kj2n_j \ge k_j^2, we obtain

∣(A△X)(nj)∣nj≤kj+1kj2⟶0as j→∞.(14)\frac{|(A \mathbin{\triangle} X)(n_j)|}{n_j} \le\frac{k_j+1}{k_j^2} \longrightarrow0 \quad\text{as } j\to\infty. \tag*{(14)}

Putting together (13) and (14), we get

∣(X△(B+C))(nj)∣nj≤∣(X△A)(nj)∣nj+∣(A△(B+C))(nj)∣nj,\frac{|(X \mathbin{\triangle} (B+C))(n_j)|}{n_j} \le \frac{|(X \mathbin{\triangle} A)(n_j)|}{n_j} + \frac{|(A \mathbin{\triangle} (B+C))(n_j)|}{n_j},

which converges to 00 as j→∞j\to\infty. Therefore X△(B+C)∈Z−X \mathbin{\triangle} (B+C) \in\mathcal{Z}_-, contradicting X∈Σ(Z−)X \in\Sigma(\mathcal{Z}_-). This proves (11). Since UU is comeager, it follows that Σ(Zw)\Sigma(\mathcal{Z}_w) is comeager as well. □

Proof of Proposition 2.3. (i) We first claim that R:=P(N)∖Σ\mathcal{R} := \mathcal{P}(\mathbb{N}) \setminus\Sigma is FσF_\sigma. For, consider the map φ:P(N)2→P(N)\varphi: \mathcal{P}(\mathbb{N})^2 \to\mathcal{P}(\mathbb{N}) defined by

∀(B,C)∈P(N)2,φ(B,C):=B+C.\forall(B,C) \in\mathcal{P}(\mathbb{N})^2,\qquad\varphi(B,C) := B+C.

The map φ\varphi is continuous. Indeed, for every n∈Nn \in\mathbb{N}, whether n∈B+Cn \in B+C depends only on the coordinates of BB and CC in [0,n][0,n].

Now, for all integers b0<b1b_0<b_1 and c0<c1c_0<c_1, set

Kb0,b1,c0,c1:={(B,C)∈P(N)2:b0,b1∈B and c0,c1∈C}.K_{b_0,b_1,c_0,c_1}:=\{(B,C)\in\mathcal{P}(\mathbb{N})^2:b_0,b_1\in B\text{ and }c_0,c_1\in C\}.

Each Kb0,b1,c0,c1K_{b_0,b_1,c_0,c_1} is a compact subset of P(N)2\mathcal{P}(\mathbb{N})^2. Therefore φ[Kb0,b1,c0,c1]\varphi[K_{b_0,b_1,c_0,c_1}] is compact and, hence, closed. Moreover,

R=⋃b0<b1c0<c1φ[Kb0,b1,c0,c1].\mathcal{R}=\bigcup_{\substack{b_0<b_1\\c_0<c_1}}\varphi[K_{b_0,b_1,c_0,c_1}].

Thus R\mathcal{R} is FσF_\sigma.

Since both I\mathcal{I} and R\mathcal{R} are FσF_\sigma, there exist closed sets En,Fm⊆P(N)E_n,F_m\subseteq\mathcal{P}(\mathbb{N}) such that I=⋃nEn\mathcal{I}=\bigcup_n E_n and R=⋃mFm\mathcal{R}=\bigcup_m F_m. Consider the continuous map Δ:P(N)2→P(N)\Delta:\mathcal{P}(\mathbb{N})^2\to\mathcal{P}(\mathbb{N}) defined by

∀(E,S)∈P(N)2,Δ(E,S):=E△S.\forall(E,S)\in\mathcal{P}(\mathbb{N})^2,\qquad\Delta(E,S):=E\mathbin{\triangle}S.

By the definition of I\mathcal{I}-irreducibility,

P(N)∖Σ(I)=Δ[I×R]=⋃n,m∈NΔ[En×Fm].\mathcal{P}(\mathbb{N}) \setminus\Sigma(\mathcal{I}) = \Delta[\mathcal{I} \times\mathcal{R}] = \bigcup_{n,m\in\mathbb{N}} \Delta[E_n \times F_m].

For every n,m∈Nn,m \in\mathbb{N}, the set En×FmE_n \times F_m is compact, because it is a closed subset of the compact space P(N)2\mathcal{P}(\mathbb{N})^2. Hence its image under Δ\Delta is compact and, therefore, closed. It follows that P(N)∖Σ(I)\mathcal{P}(\mathbb{N}) \setminus\Sigma(\mathcal{I}) is FσF_{\sigma}. Therefore Σ(I)\Sigma(\mathcal{I}) is GδG_{\delta}.

(ii) Consider the continuous map Φ:P(N)3→P(N)\Phi: \mathcal{P}(\mathbb{N})^3 \to\mathcal{P}(\mathbb{N}) defined by

∀(A,B,C)∈P(N)3,Φ(A,B,C):=A△(B+C).\forall(A,B,C) \in\mathcal{P}(\mathbb{N})^3,\quad\Phi(A,B,C) := A \mathbin{\triangle} (B+C).

Indeed, the value of the nn-th coordinate of Φ(A,B,C)\Phi(A,B,C) depends only on the coordinates of AA, BB, and CC in [0,n][0,n]. Now set

X:={(A,B,C)∈P(N)3:∣B∣,∣C∣≥2 and Φ(A,B,C)∈I}.\mathcal{X} := \{(A,B,C) \in\mathcal{P}(\mathbb{N})^3 : |B|,|C| \ge2 \text{ and } \Phi(A,B,C) \in\mathcal{I}\}.

Since I\mathcal{I} is analytic, its continuous preimage Φ−1[I]\Phi^{-1}[\mathcal{I}] is analytic. Moreover, the conditions ∣B∣,∣C∣≥2|B|,|C| \ge2 define an open subset of P(N)3\mathcal{P}(\mathbb{N})^3. Since analytic sets are stable under intersections with Borel sets, it follows that X\mathcal{X} is analytic.

By definition,

P(N)∖Σ(I)={A⊆N:∃B,C⊆N, (A,B,C)∈X}.\mathcal{P}(\mathbb{N}) \setminus\Sigma(\mathcal{I}) = \{A \subseteq\mathbb{N} : \exists B,C \subseteq\mathbb{N},\ (A,B,C) \in\mathcal{X}\}.

Thus P(N)∖Σ(I)\mathcal{P}(\mathbb{N}) \setminus\Sigma(\mathcal{I}) is analytic, being the projection of an analytic set. Therefore Σ(I)\Sigma(\mathcal{I}) is coanalytic.

(iii) Fix E∈IE \in\mathcal{I}. By the definition of I\mathcal{I}-irreducibility,

{E△S:S∈R}⊆P(N)∖Σ(I).\{E \mathbin{\triangle} S : S \in\mathcal{R}\} \subseteq\mathcal{P}(\mathbb{N}) \setminus\Sigma(\mathcal{I}).

Since S↦E△SS \mapsto E \mathbin{\triangle} S is a homeomorphism, it is enough to show that R\mathcal{R} is dense. To this end, fix a nonempty basic open set

U:={A⊆N:A(k)=F},U := \{A \subseteq\mathbb{N} : A(k)=F\},

where k∈Nk \in\mathbb{N} and F⊆[0,k]F \subseteq[0,k]. Define

B:={0,k+1}andC:=F∪{k+1,k+2}.B := \{0,k+1\} \qquad\text{and} \qquad C := F \cup\{k+1,k+2\}.

Then ∣B∣,∣C∣≥2|B|,|C| \ge2 and (B+C)(k)=F(B+C)(k)=F. Thus B+C∈U∩RB+C \in U \cap\mathcal{R}.

(iv) Suppose that Σ(I)\Sigma(\mathcal{I}) is comeager and, thanks to item (iii) its complement is dense. It follows by the Baire Category Theorem, see e.g. [6 Theorem 8.4], that Σ(I)\Sigma(\mathcal{I}) cannot be FσF_{\sigma}.

(v) Suppose that Σ(I)≠∅\Sigma(\mathcal{I}) \ne\varnothing and fix A∈Σ(I)A \in\Sigma(\mathcal{I}). We claim that A△F∈Σ(I)A \mathbin{\triangle} F \in\Sigma(\mathcal{I}) for every F∈FinF \in\mathrm{Fin}. Indeed, otherwise there exist F∈FinF \in\mathrm{Fin} and B,C⊆NB,C \subseteq\mathbb{N} with ∣B∣,∣C∣≥2|B|,|C| \ge2 such that (A△F)△(B+C)∈I(A \mathbin{\triangle} F) \mathbin{\triangle} (B+C) \in\mathcal{I}. By admissibility,

A△(B+C)=F△((A△F)△(B+C))∈I,A \mathbin{\triangle} (B+C) = F \mathbin{\triangle} ((A \mathbin{\triangle} F) \mathbin{\triangle} (B+C)) \in\mathcal{I},

which contradicts A∈Σ(I)A \in\Sigma(\mathcal{I}).

Now, fix a nonempty basic open set U:={S⊆N:S(k)=E}U := \{S \subseteq\mathbb{N} : S(k)=E\}, where k∈Nk \in\mathbb{N} and E⊆[0,k]E \subseteq[0,k]. Define F:=(A∩[0,k])△EF := (A \cap[0,k]) \mathbin{\triangle} E. Then F∈FinF \in\mathrm{Fin} and (A△F)(k)=E(A \mathbin{\triangle} F)(k)=E. Hence, by the above observation, A△F∈U∩Σ(I)A \mathbin{\triangle} F \in U \cap\Sigma(\mathcal{I}). Thus every nonempty basic open subset of P(N)\mathcal{P}(\mathbb{N}) has nonempty intersection with Σ(I)\Sigma(\mathcal{I}).

(vi) It follows by item (v) and [6 Theorem 8.46].

(vii) Set S:={0,1}+{0,1}={0,1,2}S := \{0,1\} + \{0,1\} = \{0,1,2\}. By definition,

{E△S:E∈I}⊆P(N)∖Σ(I)=R(I).\{E \mathbin{\triangle} S : E \in\mathcal{I}\} \subseteq\mathcal{P}(\mathbb{N}) \setminus\Sigma(\mathcal{I}) = \mathcal{R}(\mathcal{I}).

If Σ(I)\Sigma(\mathcal{I}) is comeager, R(I)\mathcal{R}(\mathcal{I}) is meager. Since E↦E△SE \mapsto E \mathbin{\triangle} S is a homeomorphism, I\mathcal{I} is meager. □\square

Remark 3.5. The family Z−\mathcal{Z}_{-} shows that measure and category may disagree for Σ(⋅)\Sigma(\mathord{\cdot}). On the one hand, λ(Σ(Z−))=1\lambda(\Sigma(\mathcal{Z}_{-})) = 1 by Proposition 3.3. On the other hand, Σ(Z−)\Sigma(\mathcal{Z}_{-}) is meager. Indeed,

Z−=⋂k≥1⋂N∈N⋃n≥N{A⊆N:∣A(n)∣<nk}.\mathcal{Z}_{-} = \bigcap_{k \ge1} \bigcap_{N \in\mathbb{N}} \bigcup_{n \ge N} \left\{A \subseteq\mathbb{N} : \lvert A(n) \rvert< \frac{n}{k}\right\}.

is a GδG_{\delta} subset of P(N)\mathcal{P}(\mathbb{N}): each inner set is clopen, and each union over n≥Nn \ge N is open and dense. In fact, any prescribed finite initial segment can be followed by a sufficiently long interval containing no elements of AA. Hence Z−\mathcal{Z}_{-} is comeager. Moreover, Z−\mathcal{Z}_{-} is stable under finite modifications, so for every A∈Z−A \in\mathcal{Z}_{-} we have A△({0,1}+{0,1})=A△{0,1,2}∈Z−A \mathbin{\triangle} (\{0,1\} + \{0,1\}) = A \mathbin{\triangle} \{0,1,2\} \in\mathcal{Z}_{-}, that is, A∉Σ(Z−)A \notin\Sigma(\mathcal{Z}_{-}). Therefore Σ(Z−)⊆P(N)∖Z−\Sigma(\mathcal{Z}_{-}) \subseteq\mathcal{P}(\mathbb{N}) \setminus\mathcal{Z}_{-}, which is meager. Note that Σ(Z−)\Sigma(\mathcal{Z}_{-}) is nevertheless dense, by Proposition 2.3(v).

This contrasts with Σ(Z)\Sigma(\mathcal{Z}), which is both comeager (Theorem 2.2) and of full measure.

Proof of Theorem 2.4. Set mj:=22j+2m_j := 2^{2^{j+2}} for all j∈Nj \in\mathbb{N}, and define

E:=⋃j∈NEj,whereEj:=N∩[2mj,2mj+j] for all j∈N.E := \bigcup_{j \in\mathbb{N}} E_j, \qquad\text{where} \qquad E_j := \mathbb{N} \cap[2m_j,2m_j+j] \text{ for all } j \in\mathbb{N}.

Observe that 2mj−1+j<mj2m_{j-1}+j < m_j for all j≥1j \ge1, and that for every nonempty finite F⊆ZF \subseteq\mathbb{Z}, we have

⋂t∈F(E+t)\bigcap_{t \in F}(E+t)

is infinite, where E+t:={n∈N:n−t∈E}E+t := \{n \in\mathbb{N} : n-t \in E\}. Indeed, if j≥max⁡F−min⁡Fj \ge\max F-\min F is sufficiently large, then

⋂t∈F(E+t)⊇⋂t∈F(Ej+t)⊇[2mj+max⁡F,2mj+j+min⁡F]∩N≠∅.\bigcap_{t \in F}(E+t) \supseteq\bigcap_{t \in F}(E_j+t) \supseteq[2m_j+\max F,2m_j+j+\min F] \cap\mathbb{N} \ne\varnothing.

This implies that no finite union of translates of Ec:=N∖EE^{c} := \mathbb{N} \setminus E can be cofinite. At this point, define the ideal

I:={D⊆N:D∖⋃t∈F(Ec+t)∈Fin⁡ for some nonempty finite F⊆Z}.\mathcal{I} := \left\{D \subseteq\mathbb{N} : D \setminus\bigcup_{t \in F}(E^{c}+t) \in\operatorname{Fin} \text{ for some nonempty finite } F \subseteq\mathbb{Z}\right\}.

Then it is routine to check that I\mathcal{I} is a proper admissible translation-invariant FσF_{\sigma} ideal. To complete the proof, it is enough to show that every subset of N\mathbb{N} is not I\mathcal{I}-irreducible. To this aim, fix A⊆NA \subseteq\mathbb{N} and define Hj:={h∈[0,j]:2mj+h∈A}H_j := \{h \in[0,j] : 2m_j+h \in A\} for all j∈Nj \in\mathbb{N}. Then, set

B:={mj:j∈N}andC:={0,1}∪⋃j∈N(Hj+mj).B := \{m_j : j \in\mathbb{N}\} \qquad\text{and} \qquad C := \{0,1\} \cup\bigcup_{j \in\mathbb{N}}(H_j+m_j).

Clearly, ∣B∣,∣C∣≥2\lvert B\rvert,\lvert C\rvert\ge2.

At this point, we claim that

(B+C)∩E=A∩E.(15)(B+C) \cap E = A \cap E. \tag*{(15)}

Fix j∈Nj \in\mathbb{N}. The sums of the type mj+(mj+h)=2mj+hm_j+(m_j+h)=2m_j+h with h∈Hjh \in H_j produce precisely the elements of A∩EjA \cap E_j. It remains to check that no other sum enters EjE_j. If i≠ki \ne k and r:=max⁡{i,k}r := \max\{i,k\}, then 2mr−1+r−1<mi+mk+h<2mr2m_{r-1}+r-1 < m_i+m_k+h < 2m_r whenever 0≤h≤k0 \le h \le k. Thus every sum mi+(mk+h)m_i+(m_k+h) with i≠ki \ne k lies strictly between two consecutive intervals forming EE. Similarly, each of the sums mim_i and mi+1m_{i+1}, arising from the two distinguished elements 0,1∈C0,1 \in C, lies outside EE. This proves (15). By the definition of I\mathcal{I}, we conclude that A△(B+C)⊆N∖E∈IA \mathbin{\triangle} (B+C) \subseteq\mathbb{N}\setminus E \in\mathcal{I}. Therefore Σ(I)=∅\Sigma(\mathcal{I})=\varnothing. □

Proof of Theorem 2.5. Let J\mathcal{J} be a maximal ideal on N\mathbb{N} such that Fin⁡⊆J\operatorname{Fin}\subseteq\mathcal{J} (that is, the complement of a free ultrafilter). Define m0:=0m_0:=0, mn:=22nm_n:=2^{2^n} for n≥1n\ge1, and In:=[mn,mn+1)I_n:=[m_n,m_{n+1}). For every A⊆NA\subseteq\mathbb{N} and n∈Nn\in\mathbb{N}, set μn(A):=∣A∩In∣/∣In∣\mu_n(A):=|A\cap I_n|/|I_n|, and define

K:={A⊆N:J-lim⁡n→∞μn(A)=0}.(16)\mathcal{K}:=\left\{A\subseteq\mathbb{N}:\mathcal{J}\text{-}\lim_{n\to\infty}\mu_n(A)=0\right\}. \tag*{(16)}

Here, for a real sequence (xn)(x_n) and a∈Ra\in\mathbb{R}, the notation J-lim⁡n→∞xn=a\mathcal{J}\text{-}\lim_{n\to\infty}x_n=a means that {n∈N:∣xn−a∣≥ε}∈J\{n\in\mathbb{N}:|x_n-a|\ge\varepsilon\}\in\mathcal{J} for all ε>0\varepsilon>0. Since J\mathcal{J} is maximal, every bounded real sequence has a unique J\mathcal{J}-limit. Then K\mathcal{K} is a proper ideal containing Fin⁡\operatorname{Fin}.

First, we claim that

K⊆Z−.(17)\mathcal{K}\subseteq\mathcal{Z}_{-}. \tag*{(17)}

Indeed, if A∈KA\in\mathcal{K}, there exists a strictly increasing sequence (nj)(n_j) such that

∀j∈N,μnj(A)≤2−jandmnjmnj+1≤2−j.\forall j\in\mathbb{N},\qquad\mu_{n_j}(A)\le2^{-j}\qquad\text{and}\qquad\frac{m_{n_j}}{m_{n_j+1}}\le2^{-j}.

It follows that

∣A(mnj+1−1)∣mnj+1−1≤mnjmnj+1−1+∣Inj∣2j(mnj+1−1)⟶0as j→∞,\frac{|A(m_{n_j+1}-1)|}{m_{n_j+1}-1}\le\frac{m_{n_j}}{m_{n_j+1}-1}+\frac{|I_{n_j}|}{2^j(m_{n_j+1}-1)}\longrightarrow0\qquad\text{as }j\to\infty,

which proves (17).

Second, set E:=2NE:=2\mathbb{N} and O:=2N+1O:=2\mathbb{N}+1. We claim that both K\mathcal{K} and Ko:=K∩P(O)\mathcal{K}_o:=\mathcal{K}\cap\mathcal{P}(O) are not meager, where the latter is regarded as a subset of P(O)\mathcal{P}(O). Fix Q∈{N,O}Q\in\{\mathbb{N},O\} and let (Pk)(P_k) be an arbitrary partition of QQ into finite sets. For each L⊆NL\subseteq\mathbb{N}, define

ν(L):=J-lim⁡n→∞∣PL∩In∩Q∣∣In∩Q∣,where PL:=⋃k∈LPk.\nu(L):=\mathcal{J}\text{-}\lim_{n\to\infty}\frac{|P_L\cap I_n\cap Q|}{|I_n\cap Q|},\qquad\text{where }P_L:=\bigcup_{k\in L}P_k.

Then ν\nu is a finitely additive probability measure on P(N)\mathcal{P}(\mathbb{N}) and ν({k})=0\nu(\{k\})=0 for each k∈Nk\in\mathbb{N}. By successively splitting infinite sets into two infinite pieces, we obtain that there exist decreasing infinite sets (Lj)(L_j) such that

ν(Lj)≤2−j.(18)\nu(L_j)\le2^{-j}. \tag*{(18)}

Choose distinct kj∈Ljk_j\in L_j and set L:={kj:j∈N}L:=\{k_j:j\in\mathbb{N}\}. Since L⊂{k0,…,kj−1}∪LjL\subset\{k_0,\ldots,k_{j-1}\}\cup L_j, it follows by Inequality (18) that ν(L)=0\nu(L)=0. Consequently, PL∈KP_L\in\mathcal{K} if Q=NQ=\mathbb{N}, and PL∈KoP_L\in\mathcal{K}_o if Q=OQ=O, while PLP_L contains infinitely many members of the given partition. By Talagrand’s characterization [9 Theorem 21], an ideal M\mathcal{M} on N\mathbb{N} is meager if and only if there exists a partition (Sn)(S_n) of N\mathbb{N} into finite intervals such that every A∈MA\in\mathcal{M} contains at most finitely many of the sets SnS_n. Hence both K\mathcal{K} and Ko\mathcal{K}_o are not meager.

At this point, define

I:=K∩L,where L:={A⊆N:∣A∩2N∣<∞}.(19)\mathcal{I}:=\mathcal{K}\cap\mathcal{L},\qquad\text{where }\mathcal{L}:=\{A\subseteq\mathbb{N}:|A\cap2\mathbb{N}|<\infty\}. \tag*{(19)}

The family L\mathcal{L} is an FσF_{\sigma} ideal, hence meager. It follows that I\mathcal{I} is meager as well.

Next, we show that Σ(I)\Sigma(\mathcal{I}) is not meager. By Proposition 3.3, it is possible to pick X∈Σ(Z−)X\in\Sigma(\mathcal{Z}_{-}). In view of (17), we have X∈Σ(K)X\in\Sigma(\mathcal{K}). Moreover,

X△K:={X△Y:Y∈K}⊆Σ(K).(20)X\mathbin{\triangle}\mathcal{K}:=\{X\mathbin{\triangle}Y:Y\in\mathcal{K}\}\subseteq\Sigma(\mathcal{K}). \tag*{(20)}

Indeed, if Y∈KY\in\mathcal{K} and

(X△Y)△(B+C)∈K,(X\mathbin{\triangle}Y)\mathbin{\triangle}(B+C)\in\mathcal{K},

then X△(B+C)∈KX\mathbin{\triangle}(B+C)\in\mathcal{K}, which is a contradiction. Since Y↦X△YY\mapsto X\mathbin{\triangle}Y is a homeomorphism for each XX, and since K\mathcal{K} is not meager, (20) implies that Σ(K)\Sigma(\mathcal{K}) is not meager. Finally, I⊆K\mathcal{I}\subseteq\mathcal{K} gives Σ(K)⊆Σ(I)\Sigma(\mathcal{K})\subseteq\Sigma(\mathcal{I}), and hence Σ(I)\Sigma(\mathcal{I}) is not meager.

It remains to prove that Σ(I)\Sigma(\mathcal{I}) is not comeager. Define Φ:P(N)→P(O)\Phi:\mathcal{P}(\mathbb{N})\to\mathcal{P}(O) by

∀A∈P(N),Φ(A):=A△({0,1}+(A∩E)).\forall A\in\mathcal{P}(\mathbb{N}),\qquad\Phi(A):=A\mathbin{\triangle}(\{0,1\}+(A\cap E)).

Notice that Φ(A)⊆O\Phi(A)\subseteq O for every AA. Moreover, the map P(N)→P(E)×P(O)\mathcal{P}(\mathbb{N})\to\mathcal{P}(E)\times\mathcal{P}(O) defined by A↦(A∩E,Φ(A))A\mapsto(A\cap E,\Phi(A)) is a homeomorphism. Since Ko\mathcal{K}_{o} is not meager, it follows that

Φ−1[Ko] is not meager.(21)\Phi^{-1}[\mathcal{K}_{o}]\text{ is not meager}. \tag*{(21)}

The set G:={A⊆N:∣A∩E∣≥2}G:=\{A\subseteq\mathbb{N}:|A\cap E|\ge2\} is open and dense. Thus G∩Φ−1[Ko]G\cap\Phi^{-1}[\mathcal{K}_{o}] is not meager by (21). If AA belongs to this intersection, put

B:={0,1}andC:=A∩E.B:=\{0,1\}\qquad\text{and}\qquad C:=A\cap E.

Then ∣B∣,∣C∣≥2|B|,|C|\ge2 and

A△(B+C)=Φ(A)∈Ko⊆K∩L=I.A\mathbin{\triangle}(B+C)=\Phi(A)\in\mathcal{K}_{o}\subseteq\mathcal{K}\cap\mathcal{L}=\mathcal{I}.

Consequently,

G∩Φ−1[Ko]⊆P(N)∖Σ(I).G\cap\Phi^{-1}[\mathcal{K}_{o}]\subseteq\mathcal{P}(\mathbb{N})\setminus\Sigma(\mathcal{I}).

The complement of Σ(I)\Sigma(\mathcal{I}) is therefore not meager, so Σ(I)\Sigma(\mathcal{I}) is not comeager. □

Proof of Theorem 2.6. It follows by items (i), (iii), (iv), and (v) in Proposition 2.3. □

Proof of Corollary 2.7. Recall that {∅}\{\varnothing\}, Fin\mathrm{Fin}, and I1/n\mathcal{I}_{1/n} are FσF_{\sigma} ideals, with {∅}⊆Fin⊆I1/n⊆Z\{\varnothing\}\subseteq\mathrm{Fin}\subseteq\mathcal{I}_{1/n}\subseteq\mathcal{Z}. Hence Σ(Z)⊆Σ(I1/n)⊆Σ⋆⊆Σ\Sigma(\mathcal{Z})\subseteq\Sigma(\mathcal{I}_{1/n})\subseteq\Sigma_{\star}\subseteq\Sigma. Since Σ(Z)\Sigma(\mathcal{Z}) is comeager by Theorem 2.2, these families are comeager. The remaining claims follow by items (i), (iii), and (iv) in Proposition 2.3. □

Proof of Corollary 2.8. Recall that Z\mathcal{Z} is an FσδF_{\sigma\delta} subset of P(N)\mathcal{P}(\mathbb{N}), hence analytic. The conclusion follows by Theorem 2.2 and items (ii), (iii), and (iv) in Proposition 2.3. □

Proof of Theorem 2.10. Consider the set

S3:={x∈2N×N:∃i∈N ∀N∈N ∃n≥N, x(i,n)=1}.S_3 := \left\{x \in2^{\mathbb{N}\times\mathbb{N}} : \exists i \in\mathbb{N}\ \forall N \in\mathbb{N}\ \exists n \ge N,\ x(i,n)=1\right\}.

Thus x∈S3x \in S_3 if and only if at least one row of xx contains infinitely many 1’s. It is well known that S3S_3 is GδσG_{\delta\sigma}-complete (that is, GδσG_{\delta\sigma} and not FσδF_{\sigma\delta}), cf. [6 p. 179].

For every x∈2N×Nx \in2^{\mathbb{N}\times\mathbb{N}} and n≥1n \ge1, put

δn(x):=max⁡({2−(i+1):i≤n and x(i,n)=1}∪{0}).\delta_n(x) := \max\left(\left\{2^{-(i+1)} : i \le n\ \text{and}\ x(i,n)=1\right\} \cup\{0\}\right).

Then

x∈S3⟺lim sup⁡n→∞δn(x)>0.(22)x \in S_3 \quad\Longleftrightarrow\quad\limsup_{n\to\infty}\delta_n(x)>0. \tag*{(22)}

Indeed, the forward implication is immediate. Conversely, suppose that lim sup⁡nδn(x)>0\limsup_n \delta_n(x)>0. By the pigeonhole principle, there exists a positive integer rr such that δn(x)≥2−r\delta_n(x) \ge2^{-r} for infinitely many nn. For every such nn, there exists i<ri<r such that x(i,n)=1x(i,n)=1. Hence one of the first rr rows contains infinitely many 1’s. Thus x∈S3x \in S_3, proving (22).

Fix a set XX as in Lemma 3.1, and choose integers 1≤h0<h1<⋯1 \le h_0<h_1<\cdots such that

∀n≥1,W(hn−1)W(hn)≤2−n.(23)\forall n\ge1,\qquad\frac{W(h_{n-1})}{W(h_n)}\le2^{-n}. \tag*{(23)}

where W(⋅)W(\cdot) is defined in (4). For every x∈2N×Nx \in2^{\mathbb{N}\times\mathbb{N}} and n≥1n \ge1, define

an(x):=min⁡{a∈[0,hn]∩N:W(a)≥(1−δn(x))W(hn)},a_n(x):=\min\{a\in[0,h_n]\cap\mathbb{N}: W(a)\ge(1-\delta_n(x))W(h_n)\},

and put

Jn(x):=(an(x),hn]∩NandAx:=X∩⋃n≥1Jn(x).J_n(x):=(a_n(x),h_n]\cap\mathbb{N}\qquad\text{and}\qquad A_x:=X\cap\bigcup_{n\ge1}J_n(x).

By the minimality of an(x)a_n(x) and the fact that wk≤w0w_k\le w_0,

(1−δn(x))W(hn)≤W(an(x))≤(1−δn(x))W(hn)+w0.(24)(1-\delta_n(x))W(h_n)\le W(a_n(x))\le(1-\delta_n(x))W(h_n)+w_0. \tag*{(24)}

Since 0≤δn(x)≤1/20\le\delta_n(x)\le1/2, Equations (23) and (24) imply that an(x)≥hn−1a_n(x)\ge h_{n-1}. Hence Jn(x)⊆(hn−1,hn]J_n(x)\subseteq(h_{n-1},h_n], and the intervals Jn(x)J_n(x) are pairwise disjoint. Moreover, Jn(x)=∅J_n(x)=\varnothing if δn(x)=0\delta_n(x)=0.

The value of an(x)a_n(x) depends only on the finitely many coordinates x(0,n),…,x(n,n)x(0,n),\ldots,x(n,n). For every fixed m∈Nm\in\mathbb{N}, there is at most one n≥1n\ge1 for which m∈(hn−1,hn]m\in(h_{n-1},h_n]. Thus, the map

Ψ:2N×N→P(N):x↦Ax\Psi:2^{\mathbb{N}\times\mathbb{N}}\to\mathcal{P}(\mathbb{N}):x\mapsto A_x

is continuous.

Next, we claim that

x∈S3⟺Ax∈Σ(Zw).(25)x\in S_3\quad\Longleftrightarrow\quad A_x\in\Sigma(\mathcal{Z}_w). \tag*{(25)}

Suppose first that x∉S3x\notin S_3. By (22) we have lim⁡nδn(x)=0\lim_n\delta_n(x)=0. For every n≥1n\ge1, Equation (24) implies

∑k∈Ax(hn)wk≤W(hn−1)+δn(x)W(hn).\sum_{k\in A_x(h_n)}w_k\le W(h_{n-1})+\delta_n(x)W(h_n).

Fix n≥2n\ge2 and N∈(hn−1,hn]N\in(h_{n-1},h_n]. If N≤an(x)N\le a_n(x), then Ax(N)=Ax(hn−1)A_x(N)=A_x(h_{n-1}), and hence

∑k∈Ax(N)wkW(N)≤W(hn−2)+δn−1(x)W(hn−1)W(hn−1)≤21−n+δn−1(x).\frac{\sum_{k\in A_x(N)}w_k}{W(N)} \le\frac{W(h_{n-2})+\delta_{n-1}(x)W(h_{n-1})}{W(h_{n-1})} \le2^{1-n}+\delta_{n-1}(x).

On the other hand, if N>an(x)N > a_n(x), then W(N)≥W(an(x))≥W(hn)/2W(N) \ge W(a_n(x)) \ge W(h_n)/2. Hence

∑k∈Ax(N)wkW(N)≤2(W(hn−1)W(hn)+δn(x))≤21−n+2δn(x).\frac{\sum_{k\in A_x(N)} w_k}{W(N)} \le2\left(\frac{W(h_{n-1})}{W(h_n)}+\delta_n(x)\right) \le2^{1-n}+2\delta_n(x).

It follows that Ax∈ZwA_x \in\mathcal{Z}_w, and so Ax△({0,1}+{0,1})∈ZwA_x \mathbin{\triangle} (\{0,1\}+\{0,1\}) \in\mathcal{Z}_w since Fin⁡⊆Zw\operatorname{Fin} \subseteq\mathcal{Z}_w. Therefore Ax∉Σ(Zw)A_x \notin\Sigma(\mathcal{Z}_w).

Suppose now that x∈S3x \in S_3. By (22), there exist a positive integer jj and an infinite set L⊆NL \subseteq\mathbb{N} such that

∀n∈L,δn(x)=2−j=:δ.(26)\forall n \in L,\qquad\delta_n(x)=2^{-j}=:\delta. \tag*{(26)}

Set c:=δ/4=2−(j+2)c:=\delta/4=2^{-(j+2)}, and, for every n∈Ln\in L, put an:=an(x)a_n:=a_n(x) and an′:=⌈an/(1−c)⌉a'_n:=\lceil a_n/(1-c)\rceil. Since (wk)(w_k) is nonincreasing and c≤1/8c\le1/8, we have

W(an′)−W(an)≤(an′−an)wan≤(2can+1)wan≤2cW(an)+w0.W(a'_n)-W(a_n)\le(a'_n-a_n)w_{a_n}\le(2ca_n+1)w_{a_n}\le2cW(a_n)+w_0.

Together with (24) and (1+δ/2)(1−δ)≤1−δ/2(1+\delta/2)(1-\delta)\le1-\delta/2, this implies, for all sufficiently large n∈Ln\in L,

W(an′)≤(1−δ/2)W(hn)+3w0≤(1−δ/4)W(hn).(27)W(a'_n)\le(1-\delta/2)W(h_n)+3w_0\le(1-\delta/4)W(h_n). \tag*{(27)}

In particular, an′<hna'_n<h_n for all such nn.

Suppose, towards a contradiction, that there are B,C⊆NB,C\subseteq\mathbb{N} with ∣B∣,∣C∣≥2|B|,|C|\ge2 such that D:=Ax△S∈ZwD:=A_x\mathbin{\triangle}S\in\mathcal{Z}_w, where S:=B+CS:=B+C. We apply Lemma 3.4 to the pairs an′<hna'_n<h_n, n∈Ln\in L: indeed an′≥an≥hn−1→∞a'_n\ge a_n\ge h_{n-1}\to\infty and lim sup⁡n∈LW(an′)/W(hn)≤1−δ/4<1\limsup_{n\in L}W(a'_n)/W(h_n)\le1-\delta/4<1. Hence there are integers n∗=n∗(n)∈[an′,hn]n^*=n^*(n)\in[a'_n,h_n] and reals τn→0\tau_n\to0 such that

∀n∈L,∣D(n∗)∣≤τnn∗.(28)\forall n\in L,\qquad|D(n^*)|\le\tau_n n^*. \tag*{(28)}

Put I:=((1−c)n∗,n∗]I:=((1-c)n^*,n^*]. Since (1−c)n∗≥(1−c)an′≥an(1-c)n^*\ge(1-c)a'_n\ge a_n and n∗≤hnn^*\le h_n, we have I⊆Jn(x)I\subseteq J_n(x), hence Ax∩I=X∩IA_x\cap I=X\cap I. Recall also that Ax⊆XA_x\subseteq X.

Since Ax⊆XA_x\subseteq X, we have S∖X⊆S∖Ax⊆DS\setminus X\subseteq S\setminus A_x\subseteq D; and since Ax∩I=X∩IA_x\cap I=X\cap I, we have (X△S)∩I=D∩I(X\mathbin{\triangle}S)\cap I=D\cap I. Note that I=Ij+2(n∗)I=I_{j+2}(n^*), because c=2−(j+2)c=2^{-(j+2)}. Hence

∣(S∖X)(n∗)∣+∣(X△S)∩Ij+2(n∗)∣≤2∣D(n∗)∣≤2τnn∗(n∈L).|(S\setminus X)(n^*)|+|(X\mathbin{\triangle}S)\cap I_{j+2}(n^*)|\le2|D(n^*)|\le2\tau_n n^*\qquad(n\in L).

Since τn→0\tau_n\to0 and n∗=n∗(n)≥hn−1→∞n^*=n^*(n)\ge h_{n-1}\to\infty as n→∞n\to\infty in LL, the liminf in (3) with ℓ:=j+2\ell:=j+2 vanishes, which contradicts Lemma 3.2. Therefore Ax∈Σ(Zw)A_x\in\Sigma(\mathcal{Z}_w), proving (25).

Finally, suppose that Σ(Zw)\Sigma(\mathcal{Z}_w) were FσδF_{\sigma\delta}. Since Ψ\Psi is continuous, (25) would imply that

S3={x∈2N×N:Ax∈Σ(Zw)}=Ψ−1[Σ(Zw)]S_3=\{x\in2^{\mathbb{N}\times\mathbb{N}}:A_x\in\Sigma(\mathcal{Z}_w)\}=\Psi^{-1}[\Sigma(\mathcal{Z}_w)]

is FσδF_{\sigma\delta} as well, which provides the desired contradiction. Therefore Σ(Zw)\Sigma(\mathcal{Z}_w) is not FσδF_{\sigma\delta}. □

Remark 3.6. The proof of Theorem 2.10 actually shows that Σ(Zw)\Sigma(\mathcal{Z}_w) is GδσG_{\delta\sigma}-hard for every sequence (wn)(w_n) satisfying its hypotheses. This means that, for every zero-dimensional Polish space YY and every GδσG_{\delta\sigma} subset E⊆YE\subseteq Y, there exists a continuous map f:Y→P(N)f:Y\to\mathcal{P}(\mathbb{N}) such that

E=f−1[Σ(Zw)].E=f^{-1}[\Sigma(\mathcal{Z}_w)].

Indeed, since S3S_3 is GδσG_{\delta\sigma}-complete, there exists a continuous map g:Y→2N×Ng:Y\to2^{\mathbb{N}\times\mathbb{N}} such that E=g−1[S3]E=g^{-1}[S_3]. The continuous map Ψ\Psi constructed in the proof satisfies S3=Ψ−1[Σ(Zw)]S_3=\Psi^{-1}[\Sigma(\mathcal{Z}_w)]. Thus f:=Ψ∘gf:=\Psi\circ g has the required property.

Acknowledgment

The first author was funded by the grant 10.55776/PAT4719224 of the Austrian Science Fund (FWF).

References

Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Linz, Austria

Email address: [email protected]

Department of Economics, Università degli Studi dell’Insubria, via Monte Generoso 71, 21100 Varese, Italy

Email address: [email protected]

References

  1. [1]M. Balcerzak, P. Das, M. Filipczak, and J. Swaczyna, Generalized kinds of density and the associated ideals, Acta Math. Hungar. 147 (2015), no. 1, 97–115.DOI
  2. [2]P.-Y. Bienvenu, Metric decomposability theorems on sets of integers, Bull. Lond. Math. Soc. 55 (2023), no. 6, 2653–2659.arxiv.org/abs/2204.11773
  3. [3]I. Farah, Analytic quotients: theory of liftings for quotients over analytic ideals on the integers, Mem. Amer. Math. Soc. 148 (2000), no. 702, xvi+177.DOI
  4. [4]W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), no. 301, 13–30.
  5. [5]W. Just and A. Krawczyk, On certain Boolean algebras 𝒫(ω)/I, Trans. Amer. Math. Soc. 285 (1984), no. 1, 411–429.
  6. [6]A. S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995.DOI
  7. [7]P. Leonetti, Almost all sets of nonnegative integers and their small perturbations are not sumsets, Proc. Amer. Math. Soc. 151 (2023), no. 9, 3681–3689.arxiv.org/abs/2212.13852
  8. [8]J. H. Schmerl, What’s the difference?, vol. 93, 1998, Computability theory, pp. 255–261.
  9. [9]M. Talagrand, Compacts de fonctions mesurables et filtres non mesurables, Studia Math. 67 (1980), no. 1, 13–43.DOI
  10. [10]E. Wirsing, Ein metrischer Satz über Mengen ganzer Zahlen, Arch. Math. (Basel) 4 (1953), 392–398.DOI

Paper details

vlnc:W_5zc9e7cx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents