Given an ideal I on the nonnegative integers, we study the family Σ(I) of all sets for which every I-small modification is not a nontrivial sumset A+B. We prove that Σ(I) is comeager whenever I is an Erdős–Ulam ideal generated by a nonincreasing sequence of positive weights. This answers an open question for the ideal Z of asymptotic density zero sets in [Proc. Amer. Math. Soc. 151 (2023), 3681–3689]. We also show that Σ(I) is either empty or a dense Gδ-complete set whenever I is an Fσ ideal which is invariant under finite modifications. This implies that the family of nontrivial sumsets A+B is Fσ-complete (hence, Borel). On the other hand, we construct a meager ideal I for which Σ(I) is neither meager nor comeager. Finally, we prove that Σ(Z) is coanalytic and not Fσδ.
Introduction
Sumsets and irreducibility
A subset A of the nonnegative integers N is said to be irreducible if it is not a nontrivial sumset, i.e., if there are no B,C⊆N such that ∣B∣,∣C∣≥2 and A=B+C:={b+c:b∈B,c∈C}. Moreover, A⊆N is called totally irreducible if there are no sets B,C⊆N such that ∣B∣,∣C∣≥2 and A△(B+C) is finite, cf. [2, 10]. Let Σ and Σ⋆ be the families of irreducible and totally irreducible sets, respectively, so that Σ⋆⊆Σ. Let R and R⋆ respectively be their complements to P(N). Wirsing [10] initiated the investigation of these families of subsets of N and discovered that Σ⋆ 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).
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), thought to be a family of small subsets, we denote by Σ(I) the family of I-irreducible sets, namely,
Σ(I)={A⊆N:A=I(B+C) for all B,C⊆N with ∣B∣,∣C∣≥2},
where A=I(B+C) stands for A△(B+C)∈/I. We denote by R(I)=P(N)∖Σ(I) its complement. In particular,
Σ=Σ({∅})andΣ⋆=Σ(Fin)
where Fin stands for the family of all finite subsets of N.
Since I represents a family of small sets, this notion is attractive when I is an ideal on N, that is, a nonempty family of subsets stable under subsets and finite unions. A family I⊆P(N) is admissible if it is stable under finite modifications, i.e., A△F∈I for all A∈I and F∈Fin. An admissible family which is an ideal, equivalently an ideal containing Fin, is called an admissible ideal.
Examples of ideals are the trivial family {∅}, the family of finite sets Fin, the summable ideal
I1/n:={A⊆N:n∈A∑n+11<∞}
the family Z of asymptotic density zero sets, or the families
Zα={A⊆N:∣A(n)∣=o(nα) as n→∞}
for each α∈(0,1], where A(n):=A∩[0,n] (of course, Z1=Z).
Observe that, if I is an ideal on N, the binary relation between sets of nonnegative integers A=IB⟺A△B∈I is an equivalence relation, and Σ(I) is the set of all sets of nonnegative integers whose equivalence class contains no nontrivial sumsets. In addition, Σ(⋅) is nonincreasing on P(P(N)), i.e., Σ(I)⊆Σ(J) for all families I,J⊆P(N) with J⊆I. Further Σ(∅)=P(N) and Σ(P(N))=∅, so it suffices to study Σ(I) in the case of nonempty proper families I.
Topological and measure framework
In this paper, we focus on topological and measure-theoretic properties of Σ(I). To this end, we identify P(N) with {0,1}N. Equipped with the product topology, it is a compact space by Tychonoff’s theorem. In fact, (P(N),△) can be regarded as the abelian compact topological group ((Z/2Z)N,+).
We endow this group with the completion λ of the Bernoulli product probability measure
(21δ0+21δ1)⊗N.
Its restriction to the Borel σ-algebra is the unique Haar probability measure, where translation is the action of △. Further, the map {0,1}N→[0,1] defined by x↦∑ixi2−i−1 preserves the measure, and induces a bijection P(N)∖Fin→(0,1] (by the nonterminating dyadic expansion) and a homeomorphism from the set of all infinite noncofinite subsets of N to the set of all nondyadic real numbers in (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 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)) (for instance, Γ={S⊆P(N):S is a Gδ subset}), we say that S⊆P(N) is Γ-complete if S∈Γ and P(N)∖S∈/Γ, cf. [6 Definition 22.9 and Theorem 22.10].
Theorem 2.1.Σ(Zα) is a comeager subset of P(N) for all α∈(0,1/3).
It was left open in [7 Section 3] whether the smaller subset Σ(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 such that ∑nwn=∞ and limnwn/∑k≤nwk=0, define the Erdős–Ulam ideal
Zw:={A⊆N:n→∞lim∑k∈[0,n]wk∑k∈A∩[0,n]wk=0},
see e.g. [3 Section 1.13] or [1, 5]. It is immediate that, if wn=1 for each n∈N, then Zw=Z.
Theorem 2.2. Let (wn)n≥0 be a nonincreasing positive real sequence with ∑nwn=∞. Then Σ(Zw) is a comeager subset of P(N).
Now we turn to Σ(I) for general classes I (hence, not necessarily ideals). We obtain a number of basic topological properties.
Proposition 2.3. Pick a nonempty family I⊆P(N). Then the following hold:
(i) If I is Fσ then Σ(I) is Gδ;
(ii) If I is analytic then Σ(I) is coanalytic;
(iii) P(N)∖Σ(I) is dense;
(iv) If Σ(I) is comeager then Σ(I) is not Fσ;
(v) If I is admissible then Σ(I) is either empty or invariant under finite modifications (hence dense);
(vi) If I is admissible and Σ(I) has the Baire property then Σ(I) is either meager or comeager.
(vii) If Σ(I) is comeager, then I is meager.
In view of these results, one might conjecture that Σ(I) is comeager for all ideals I with sufficiently low topological complexity. The following result shows that this is false, even for well-behaved Fσ ideals. Here, an ideal I is said to be translation-invariant if S+k:={n∈N:n−k∈S}∈I for all S∈I and k∈Z.
Theorem 2.4. There exists an admissible proper translation-invariant Fσ ideal I on N such that Σ(I)=∅.
Alternatively, one might conjecture that if I is a meager ideal then Σ(I) is either meager or comeager (note that, thanks to Proposition 2.3, this holds if I is an admissible analytic ideal). Again, this turns out to be false.
Theorem 2.5. There exists an admissible meager ideal I on N such that Σ(I) is neither meager nor comeager in P(N).
Next, relying on Proposition 2.3, we find the exact topological complexity of certain families of I-irreducible sets. In a related result, Schmerl proved in [8] that the family {(A−A)∩N:A⊆N} is analytic but not coanalytic (hence, in particular, not Borel).
Theorem 2.6. Let I be an admissible nonempty Fσ subset of P(N). Then Σ(I) is either empty or dense Gδ-complete (hence comeager).
Note that Σ(I) may well be empty even under the hypotheses of Theorem 2.6, see Theorem 2.4. Moreover, establishing Σ(I)=∅ is not always easy when it is true: in fact, an elementary argument shows that any infinite set A⊆N with increasing enumeration (an:n∈N) satisfying limn(an+1−an)=∞ is totally irreducible, i.e., A∈Σ(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).
Combining Proposition 2.3 and Theorem 2.2, we obtain the following.
Corollary 2.7. Each of the families Σ, Σ⋆, and Σ(I1/n) is dense Gδ-complete (hence comeager), and with empty interior.
In particular, the family R=P(N)∖Σ of all nontrivial sumsets is Fσ-complete.
In the case of the ideal Z, we get the following.
Corollary 2.8.Σ(Z) is comeager, coanalytic, not Fσ, and with empty interior.
It would be interesting to calculate the exact topological complexity of Σ(Z), hence, in particular, whether it is Borel or not.
Question 2.9. Is Σ(Z) Borel?
Although we do not have an answer to Question 2.9, we conclude by showing, in particular, that the complexity of Σ(Z) is at least Gδσ.
Theorem 2.10. Let (wn)n≥0 be a nonincreasing positive real sequence with ∑nwn=∞. Then Σ(Zw) is not Fσδ.
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:n→∞liminfn∣A(n)∣=0}.
Notice that Z− need not be an ideal (more precisely, 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) on a set X∈P(N), we write λ(P(X)) for λ({X∈P(N):P(X)}). Also, we define
η:=1001
and
Ih(n):=((1−2h1)n,n]∩N
for all integers h,n∈N. In addition, for each t∈(0,1), set
H(t):=−tlog2t−(1−t)log2(1−t).
Observe that limt→0H(t)=0. In particular, for each t∈(0,1), it is possible to fix εt∈(0,1/2) such that H(εt)<t/8.
Lemma 3.1. The following properties are satisfied by λ-almost every set X⊆N:
(i) for every finite F⊆Z, every G⊆F and every h∈N,
(ii) for every integer h≥1 and for every sufficiently large n∈N, there are no sets P,Q⊆[0,n] satisfying
∣P∣,∣Q∣≤ε2−hnand∣(X△(P+Q))∩Ih(n)∣≤η∣Ih(n)∣.(2)
Proof. (i) Fix G⊆F⊆Z and h∈N. If F=∅ the claim is clear. Otherwise, set r:=maxF−minF. At most ∣minF∣ elements t∈Ih(n) violate t+F⊆N, so we may restrict to the others. For these, the random variables
ξt=ξt(X):=1{X∩(t+F)=t+G}
have mean 2−∣F∣.
For t ranging over a fixed residue class modulo r+1, the sets t+F are pairwise disjoint, so inside each of the r+1 classes the ξt are independent; each class has at most 2n/(r+1) elements if n≥r+1. Combined with the pigeonhole principle, Hoeffding’s inequality [4 Theorem 1], applied in each class with deviation n3/4/(r+1), shows that the numerator in (1) differs from 2−∣F∣∣Ih(n)∣ by more than n3/4+∣minF∣ with probability at most
pn=en/(r+1)2(r+1).
Observe that ∑npn<∞. Hence, the conclusion follows by the Borel–Cantelli lemma and a countable intersection over (F,G,h).
(ii) Fix a positive integer h and set ε:=ε2−h. Observe that
∀n∈N,∀θ∈[0,1/2],i=0∑θn(in)≤2H(θ)n.
Hence there are at most 22H(ε)(n+1) pairs (P,Q) of subsets of [0,n] of size at most εn. For a fixed pair, set R:=(P+Q)∩Ih(n) and note that the coordinates of X on Ih(n) are independent and each with probability 1/2, so
λ(∣(X△R)∩Ih(n)∣≤η∣Ih(n)∣)≤2(1−H(η))∣Ih(n)∣1.
Since ∣Ih(n)∣≥2−hn, H(η)<1/10, and 2H(ε)≤2−h−2, the probability that some pair satisfies (2) is at most 2−n/2h+1+1. As in the previous point, the latter sequence is summable in n, hence the conclusion follows by the Borel–Cantelli lemma and a countable intersection over h≥1. □
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 X below some large n while coinciding essentially with X on the final segment Ih(n).
Lemma 3.2. Pick a set X⊆N satisfying the conditions of Lemma 3.1, and fix an integer ℓ≥1. Then there are no sets B,C⊆N with ∣B∣,∣C∣≥2 such that
n→∞liminfn∣(B+C)∖X∣(n)+∣(X△(B+C))∩Iℓ(n)∣=0.(3)
Proof. Let us suppose for the sake of contradiction that there exists a strictly increasing sequence (nj) in N and sets B,C⊆N with ∣B∣,∣C∣≥2 such that
∣(S∖X)(nj)∣=o(nj)and∣(X△S)∩Ij∣=o(nj).
as j→∞, where S:=B+C and Ij:=Iℓ(nj) for all j∈N. Define also c:=2−ℓ and
∀j∈N,ej:=∣(S∖X)(nj)∣+∣(X△S)∩Ij∣,
and observe that $\lim_j e_j/n_j = 0.
B and C are infinite. Suppose that B is finite and put m:=1+maxB. By (1) with F={−m,…,m}, h=ℓ and G={0}, the interval Ij contains at least 2−(2m+1)cnj−o(nj) points t with X∩[t−m,t+m]={t}. If such a t is not in S, it lies in (X△S)∩Ij. Otherwise t=b+y with b∈B, y∈C; choosing b′∈B∖{b}, the point t′:=b′+y lies in S, satisfies 0<∣t′−t∣<m, hence t′∈/X, i.e., t′∈(S∖X)(nj+m). Each t′ arises from at most 2m+1 points t. Therefore
a contradiction. By symmetry, C is infinite as well.
B(nj) and C(nj) are small. Fix k∈N with 2−(k+1)≤εc/2, let b0<⋯<bk be the first k+1 elements of B and F:={bi−b0:i≤k}⊆N. At most bk elements y∈C(nj) satisfy y+bk>nj. If y∈C and y+bk≤nj, the points y+b0,…,y+bk belong to S(nj); if none of them lies in S∖X, then t:=y+b0∈[0,nj] satisfies t+F⊆X, and y↦t is injective. Each point of S∖X can be written as y+bi in at most k+1 ways. By (1) with G=F and h=0, we obtain
for all large j. Exchanging the roles of B and C gives ∣B(nj)∣≤εcnj.
Conclusion. Put P:=B(nj) and Q:=C(nj). Every element of S∩[0,nj] is a sum of elements of P and Q, so S∩Ij=(P+Q)∩Ij and
∣(X△(P+Q))∩Ij∣=∣(X△S)∩Ij∣≤ej≤ηcnj≤η∣Ij∣
for all large j. Together with ∣P∣,∣Q∣≤εcnj, this contradicts Lemma 3.1(ii) with h=ℓ and n=nj. □
The following provides a strengthening of [7], Theorem 1.5.
Proposition 3.3.λ(Σ(Z−))=1.
Proof. By Lemma 3.1, it suffices to show that every set X which satisfies the two properties of that lemma belongs to Σ(Z−). Let X be as in Lemma 3.1, and suppose that D:=X△S∈Z− for some S=B+C with ∣B∣,∣C∣≥2. Choose nj→∞ with ∣D(nj)∣=o(nj). Since S∖X⊆D and (X△S)∩I1(nj)⊆D(nj), we have
∣(S∖X)(nj)∣+∣(X△S)∩I1(nj)∣≤2∣D(nj)∣=o(nj).
Hence the liminf in (3) with ℓ=1 vanishes, which contradicts Lemma 3.2. □
Before we proceed to the proof of Theorem 2.2, we show another intermediate claim. Hereafter, if (wn)n≥0 is a positive real sequence with ∑nwn=∞, we write
∀n∈N,W(n):=k=0∑nwk.(4)
Lemma 3.4. Let (wn)n≥0 be a nonincreasing positive real sequence with ∑nwn=∞. Pick sequences (am) and (bm) of positive integers such that
Proof. Suppose that (3.5) holds, and pick D⊆N such that (3.6) fails. Then there exist ε>0 and a strictly increasing sequence (mj) of positive integers such that ∣D(n)∣≥εn for every n∈[amj,bmj] and every j∈N. Since (wn) is nonincreasing, summation by parts gives
By (3.5), the right-hand side is bounded below by a positive constant for all large j. This proves that D∈/Zw. □
Proof of Theorem 2.2. Thanks to Proposition 3.3, it is possible to fix a set X∈Σ(Z−). For every integer k≥1, choose hk>k2 such that
W(hk)W(k2)≤k1.(7)
For every m≥1, define the open set
Um:=k≥m⋃{A⊆N:A∩(k,hk]=X∩(k,hk]}.
In addition, Um is dense. Indeed, fix a nonempty basic open set V:={A⊆N:A(N)=F}, where N∈N and F⊆[0,N]. Choosing k>max{m,N}, we may prescribe the coordinates in (k,hk] to agree with those of X without changing the coordinates in [0,N]. Therefore V∩Um=∅.
It follows from the Baire category theorem, see e.g. [6 Theorem 8.4], that
U:=m≥1⋂Um
@page 7/15 starts_mid=0 ends_mid=1
Lemma 3.4. Let (wn)n≥0 be a nonincreasing positive real sequence with ∑nwn=∞. Pick sequences (am) and (bm) of positive integers such that
Proof. Suppose that (3.5) holds, and pick D⊆N such that (3.6) fails. Then there exist ε>0 and a strictly increasing sequence (mj) of positive integers such that ∣D(n)∣≥εn for every n∈[amj,bmj] and every j∈N. Since (wn) is nonincreasing, summation by parts gives
By (3.5), the right-hand side is bounded below by a positive constant for all large j. This proves that D∈/Zw. □
Proof of Theorem 2.2. Thanks to Proposition 3.3, it is possible to fix a set X∈Σ(Z−). For every integer k≥1, choose hk>k2 such that
W(hk)W(k2)≤k1.(10)
For every m≥1, define the open set
Um:=k≥m⋃{A⊆N:A∩(k,hk]=X∩(k,hk]}.
In addition, Um is dense. Indeed, fix a nonempty basic open set V:={A⊆N:A(N)=F}, where N∈N and F⊆[0,N]. Choosing k>max{m,N}, we may prescribe the coordinates in (k,hk] to agree with those of X without changing the coordinates in [0,N]. Therefore V∩Um=∅.
It follows from the Baire category theorem, see e.g. [6 Theorem 8.4], that
U:=m≥1⋂Um
is comeager. To complete the proof, we claim that
U⊆Σ(Zw).(11)
To this aim, fix A∈U. There exists a strictly increasing sequence (kj) such that
A∩(kj,hkj]=X∩(kj,hkj](12)
for every j. Suppose, towards a contradiction, that A∈/Σ(Zw). Then there exist B,C⊆N, with ∣B∣,∣C∣≥2, such that
D:=A△(B+C)∈Zw.
Now, set aj:=kj2 and bj:=hkj for each j, and note that limjaj=∞ and limjW(aj)/W(bj)=0 by (3.7). It follows by Lemma 3.4 that there exist integers nj∈[kj2,hkj] such that
j→∞limnj∣D(nj)∣=0.(13)
On the other hand, (12) implies that (A△X)(nj)⊆[0,kj]. Since nj≥kj2, we obtain
which converges to 0 as j→∞. Therefore X△(B+C)∈Z−, contradicting X∈Σ(Z−). This proves (11). Since U is comeager, it follows that Σ(Zw) is comeager as well. □
Proof of Proposition 2.3. (i) We first claim that R:=P(N)∖Σ is Fσ. For, consider the map φ:P(N)2→P(N) defined by
∀(B,C)∈P(N)2,φ(B,C):=B+C.
The map φ is continuous. Indeed, for every n∈N, whether n∈B+C depends only on the coordinates of B and C in [0,n].
Now, for all integers b0<b1 and c0<c1, set
Kb0,b1,c0,c1:={(B,C)∈P(N)2:b0,b1∈B and c0,c1∈C}.
Each Kb0,b1,c0,c1 is a compact subset of P(N)2. Therefore φ[Kb0,b1,c0,c1] is compact and, hence, closed. Moreover,
R=b0<b1c0<c1⋃φ[Kb0,b1,c0,c1].
Thus R is Fσ.
Since both I and R are Fσ, there exist closed sets En,Fm⊆P(N) such that I=⋃nEn and R=⋃mFm. Consider the continuous map Δ:P(N)2→P(N) defined by
∀(E,S)∈P(N)2,Δ(E,S):=E△S.
By the definition of I-irreducibility,
P(N)∖Σ(I)=Δ[I×R]=n,m∈N⋃Δ[En×Fm].
For every n,m∈N, the set En×Fm is compact, because it is a closed subset of the compact space P(N)2. Hence its image under Δ is compact and, therefore, closed. It follows that P(N)∖Σ(I) is Fσ. Therefore Σ(I) is Gδ.
(ii) Consider the continuous map Φ:P(N)3→P(N) defined by
∀(A,B,C)∈P(N)3,Φ(A,B,C):=A△(B+C).
Indeed, the value of the n-th coordinate of Φ(A,B,C) depends only on the coordinates of A, B, and C in [0,n]. Now set
X:={(A,B,C)∈P(N)3:∣B∣,∣C∣≥2 and Φ(A,B,C)∈I}.
Since I is analytic, its continuous preimage Φ−1[I] is analytic. Moreover, the conditions ∣B∣,∣C∣≥2 define an open subset of P(N)3. Since analytic sets are stable under intersections with Borel sets, it follows that X is analytic.
By definition,
P(N)∖Σ(I)={A⊆N:∃B,C⊆N,(A,B,C)∈X}.
Thus P(N)∖Σ(I) is analytic, being the projection of an analytic set. Therefore Σ(I) is coanalytic.
(iii) Fix E∈I. By the definition of I-irreducibility,
{E△S:S∈R}⊆P(N)∖Σ(I).
Since S↦E△S is a homeomorphism, it is enough to show that R is dense. To this end, fix a nonempty basic open set
U:={A⊆N:A(k)=F},
where k∈N and F⊆[0,k]. Define
B:={0,k+1}andC:=F∪{k+1,k+2}.
Then ∣B∣,∣C∣≥2 and (B+C)(k)=F. Thus B+C∈U∩R.
(iv) Suppose that Σ(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) cannot be Fσ.
(v) Suppose that Σ(I)=∅ and fix A∈Σ(I). We claim that A△F∈Σ(I) for every F∈Fin. Indeed, otherwise there exist F∈Fin and B,C⊆N with ∣B∣,∣C∣≥2 such that (A△F)△(B+C)∈I. By admissibility,
A△(B+C)=F△((A△F)△(B+C))∈I,
which contradicts A∈Σ(I).
Now, fix a nonempty basic open set U:={S⊆N:S(k)=E}, where k∈N and E⊆[0,k]. Define F:=(A∩[0,k])△E. Then F∈Fin and (A△F)(k)=E. Hence, by the above observation, A△F∈U∩Σ(I). Thus every nonempty basic open subset of P(N) has nonempty intersection with Σ(I).
If Σ(I) is comeager, R(I) is meager. Since E↦E△S is a homeomorphism, I is meager. □
Remark 3.5. The family Z− shows that measure and category may disagree for Σ(⋅). On the one hand, λ(Σ(Z−))=1 by Proposition 3.3. On the other hand, Σ(Z−) is meager. Indeed,
Z−=k≥1⋂N∈N⋂n≥N⋃{A⊆N:∣A(n)∣<kn}.
is a Gδ subset of P(N): each inner set is clopen, and each union over n≥N is open and dense. In fact, any prescribed finite initial segment can be followed by a sufficiently long interval containing no elements of A. Hence Z− is comeager. Moreover, Z− is stable under finite modifications, so for every A∈Z− we have A△({0,1}+{0,1})=A△{0,1,2}∈Z−, that is, A∈/Σ(Z−). Therefore Σ(Z−)⊆P(N)∖Z−, which is meager. Note that Σ(Z−) is nevertheless dense, by Proposition 2.3(v).
This contrasts with Σ(Z), which is both comeager (Theorem 2.2) and of full measure.
Proof of Theorem 2.4. Set mj:=22j+2 for all j∈N, and define
E:=j∈N⋃Ej,whereEj:=N∩[2mj,2mj+j] for all j∈N.
Observe that 2mj−1+j<mj for all j≥1, and that for every nonempty finite F⊆Z, we have
t∈F⋂(E+t)
is infinite, where E+t:={n∈N:n−t∈E}. Indeed, if j≥maxF−minF is sufficiently large, then
This implies that no finite union of translates of Ec:=N∖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}.
Then it is routine to check that I is a proper admissible translation-invariant Fσ ideal. To complete the proof, it is enough to show that every subset of N is not I-irreducible. To this aim, fix A⊆N and define Hj:={h∈[0,j]:2mj+h∈A} for all j∈N. Then, set
B:={mj:j∈N}andC:={0,1}∪j∈N⋃(Hj+mj).
Clearly, ∣B∣,∣C∣≥2.
At this point, we claim that
(B+C)∩E=A∩E.(15)
Fix j∈N. The sums of the type mj+(mj+h)=2mj+h with h∈Hj produce precisely the elements of A∩Ej. It remains to check that no other sum enters Ej. If i=k and r:=max{i,k}, then 2mr−1+r−1<mi+mk+h<2mr whenever 0≤h≤k. Thus every sum mi+(mk+h) with i=k lies strictly between two consecutive intervals forming E. Similarly, each of the sums mi and mi+1, arising from the two distinguished elements 0,1∈C, lies outside E. This proves (15). By the definition of I, we conclude that A△(B+C)⊆N∖E∈I. Therefore Σ(I)=∅. □
Proof of Theorem 2.5. Let J be a maximal ideal on N such that Fin⊆J (that is, the complement of a free ultrafilter). Define m0:=0, mn:=22n for n≥1, and In:=[mn,mn+1). For every A⊆N and n∈N, set μn(A):=∣A∩In∣/∣In∣, and define
K:={A⊆N:J-n→∞limμn(A)=0}.(16)
Here, for a real sequence (xn) and a∈R, the notation J-limn→∞xn=a means that {n∈N:∣xn−a∣≥ε}∈J for all ε>0. Since J is maximal, every bounded real sequence has a unique J-limit. Then K is a proper ideal containing Fin.
First, we claim that
K⊆Z−.(17)
Indeed, if A∈K, there exists a strictly increasing sequence (nj) such that
Second, set E:=2N and O:=2N+1. We claim that both K and Ko:=K∩P(O) are not meager, where the latter is regarded as a subset of P(O). Fix Q∈{N,O} and let (Pk) be an arbitrary partition of Q into finite sets. For each L⊆N, define
Then ν is a finitely additive probability measure on P(N) and ν({k})=0 for each k∈N. By successively splitting infinite sets into two infinite pieces, we obtain that there exist decreasing infinite sets (Lj) such that
ν(Lj)≤2−j.(18)
Choose distinct kj∈Lj and set L:={kj:j∈N}. Since L⊂{k0,…,kj−1}∪Lj, it follows by Inequality (18) that ν(L)=0. Consequently, PL∈K if Q=N, and PL∈Ko if Q=O, while PL contains infinitely many members of the given partition. By Talagrand’s characterization [9 Theorem 21], an ideal M on N is meager if and only if there exists a partition (Sn) of N into finite intervals such that every A∈M contains at most finitely many of the sets Sn. Hence both K and Ko are not meager.
At this point, define
I:=K∩L,where L:={A⊆N:∣A∩2N∣<∞}.(19)
The family L is an Fσ ideal, hence meager. It follows that I is meager as well.
Next, we show that Σ(I) is not meager. By Proposition 3.3, it is possible to pick X∈Σ(Z−). In view of (17), we have X∈Σ(K). Moreover,
X△K:={X△Y:Y∈K}⊆Σ(K).(20)
Indeed, if Y∈K and
(X△Y)△(B+C)∈K,
then X△(B+C)∈K, which is a contradiction. Since Y↦X△Y is a homeomorphism for each X, and since K is not meager, (20) implies that Σ(K) is not meager. Finally, I⊆K gives Σ(K)⊆Σ(I), and hence Σ(I) is not meager.
It remains to prove that Σ(I) is not comeager. Define Φ:P(N)→P(O) by
∀A∈P(N),Φ(A):=A△({0,1}+(A∩E)).
Notice that Φ(A)⊆O for every A. Moreover, the map P(N)→P(E)×P(O) defined by A↦(A∩E,Φ(A)) is a homeomorphism. Since Ko is not meager, it follows that
Φ−1[Ko] is not meager.(21)
The set G:={A⊆N:∣A∩E∣≥2} is open and dense. Thus G∩Φ−1[Ko] is not meager by (21). If A belongs to this intersection, put
B:={0,1}andC:=A∩E.
Then ∣B∣,∣C∣≥2 and
A△(B+C)=Φ(A)∈Ko⊆K∩L=I.
Consequently,
G∩Φ−1[Ko]⊆P(N)∖Σ(I).
The complement of Σ(I) is therefore not meager, so Σ(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 {∅}, Fin, and I1/n are Fσ ideals, with {∅}⊆Fin⊆I1/n⊆Z. Hence Σ(Z)⊆Σ(I1/n)⊆Σ⋆⊆Σ. Since Σ(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 is an Fσδ subset of P(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}.
Thus x∈S3 if and only if at least one row of x contains infinitely many 1’s. It is well known that S3 is Gδσ-complete (that is, Gδσ and not Fσδ), cf. [6 p. 179].
For every x∈2N×N and n≥1, put
δn(x):=max({2−(i+1):i≤nandx(i,n)=1}∪{0}).
Then
x∈S3⟺n→∞limsupδn(x)>0.(22)
Indeed, the forward implication is immediate. Conversely, suppose that limsupnδn(x)>0. By the pigeonhole principle, there exists a positive integer r such that δn(x)≥2−r for infinitely many n. For every such n, there exists i<r such that x(i,n)=1. Hence one of the first r rows contains infinitely many 1’s. Thus x∈S3, proving (22).
Fix a set X as in Lemma 3.1, and choose integers 1≤h0<h1<⋯ such that
∀n≥1,W(hn)W(hn−1)≤2−n.(23)
where W(⋅) is defined in (4). For every x∈2N×N and n≥1, define
an(x):=min{a∈[0,hn]∩N:W(a)≥(1−δn(x))W(hn)},
and put
Jn(x):=(an(x),hn]∩NandAx:=X∩n≥1⋃Jn(x).
By the minimality of an(x) and the fact that wk≤w0,
Since 0≤δn(x)≤1/2, Equations (23) and (24) imply that an(x)≥hn−1. Hence Jn(x)⊆(hn−1,hn], and the intervals Jn(x) are pairwise disjoint. Moreover, Jn(x)=∅ if δn(x)=0.
The value of an(x) depends only on the finitely many coordinates x(0,n),…,x(n,n). For every fixed m∈N, there is at most one n≥1 for which m∈(hn−1,hn]. Thus, the map
Ψ:2N×N→P(N):x↦Ax
is continuous.
Next, we claim that
x∈S3⟺Ax∈Σ(Zw).(25)
Suppose first that x∈/S3. By (22) we have limnδn(x)=0. For every n≥1, Equation (24) implies
k∈Ax(hn)∑wk≤W(hn−1)+δn(x)W(hn).
Fix n≥2 and N∈(hn−1,hn]. If N≤an(x), then Ax(N)=Ax(hn−1), and hence
Together with (24) and (1+δ/2)(1−δ)≤1−δ/2, this implies, for all sufficiently large n∈L,
W(an′)≤(1−δ/2)W(hn)+3w0≤(1−δ/4)W(hn).(27)
In particular, an′<hn for all such n.
Suppose, towards a contradiction, that there are B,C⊆N with ∣B∣,∣C∣≥2 such that D:=Ax△S∈Zw, where S:=B+C. We apply Lemma 3.4 to the pairs an′<hn, n∈L: indeed an′≥an≥hn−1→∞ and limsupn∈LW(an′)/W(hn)≤1−δ/4<1. Hence there are integers n∗=n∗(n)∈[an′,hn] and reals τn→0 such that
∀n∈L,∣D(n∗)∣≤τnn∗.(28)
Put I:=((1−c)n∗,n∗]. Since (1−c)n∗≥(1−c)an′≥an and n∗≤hn, we have I⊆Jn(x), hence Ax∩I=X∩I. Recall also that Ax⊆X.
Since Ax⊆X, we have S∖X⊆S∖Ax⊆D; and since Ax∩I=X∩I, we have (X△S)∩I=D∩I. Note that I=Ij+2(n∗), because c=2−(j+2). Hence
Since τn→0 and n∗=n∗(n)≥hn−1→∞ as n→∞ in L, the liminf in (3) with ℓ:=j+2 vanishes, which contradicts Lemma 3.2. Therefore Ax∈Σ(Zw), proving (25).
Finally, suppose that Σ(Zw) were Fσδ. Since Ψ is continuous, (25) would imply that
S3={x∈2N×N:Ax∈Σ(Zw)}=Ψ−1[Σ(Zw)]
is Fσδ as well, which provides the desired contradiction. Therefore Σ(Zw) is not Fσδ. □
Remark 3.6. The proof of Theorem 2.10 actually shows that Σ(Zw) is Gδσ-hard for every sequence (wn) satisfying its hypotheses. This means that, for every zero-dimensional Polish space Y and every Gδσ subset E⊆Y, there exists a continuous map f:Y→P(N) such that
E=f−1[Σ(Zw)].
Indeed, since S3 is Gδσ-complete, there exists a continuous map g:Y→2N×N such that E=g−1[S3]. The continuous map Ψ constructed in the proof satisfies S3=Ψ−1[Σ(Zw)]. Thus f:=Ψ∘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
[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]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]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]W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), no. 301, 13–30.
[5]W. Just and A. Krawczyk, On certain Boolean algebras 𝒫(ω)/I, Trans. Amer. Math. Soc. 285 (1984), no. 1, 411–429.
[6]A. S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995.DOI
[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]J. H. Schmerl, What’s the difference?, vol. 93, 1998, Computability theory, pp. 255–261.
[9]M. Talagrand, Compacts de fonctions mesurables et filtres non mesurables, Studia Math. 67 (1980), no. 1, 13–43.DOI
[10]E. Wirsing, Ein metrischer Satz über Mengen ganzer Zahlen, Arch. Math. (Basel) 4 (1953), 392–398.DOI