An extension of the Erdős-Tetali theorem
Christian Táfula




RIMS, Kyoto University, 606-8502 Kyoto, Japan
tafula@kurims.kyoto-u.ac.jp

[2010]Primary 11B13, 11B34; Secondary 05D40




 Given a sequence ={a_0<a_1<a_2…}⊆, let r_,h(n) denote the number of ways n can be written as the sum of h elements of . Fixing h≥ 2, we show that if f is a suitable real function (namely: locally integrable, O-regularly varying and of positive increase) satisfying
 
    x^1/hlog(x)^1/h≪ f(x) ≪x^1/(h-1)/log(x)^ for some  > 0,

 then there must exist ⊆ with |∩ [0,x]|=Θ(f(x)) for which r_,h+ℓ(n) = Θ(f(n)^h+ℓ/n) for all ℓ≥ 0. Furthermore, for h=2 this condition can be weakened to x^1/2log(x)^1/2≪ f(x) ≪ x.
 
 The proof is somewhat technical and the methods rely on ideas from regular variation theory, which are presented in an appendix with a view towards the general theory of additive bases. We also mention an application of these ideas to Schnirelmann's method.

An extension of the Erdős–Tetali theorem
    Christian Táfula
    December 30, 2023
========================================





§ INTRODUCTION

 Denote by  the set of natural numbers with 0. Given a sequence ={a_0<a_1<a_2…}⊆ and an integer h≥ 2, the h-fold sumset h is the set {∑_i=1^h k_i : k_1,…,k_h ∈}. We say that  is an additive basis when there is h≥ 2 such that ∖ h is empty, and the least such h is the order of . An h-basis is an additive basis of order h. The representation functions r_,h(n) and s_,h(x) count the number of solutions of k_1+k_2+…+k_h = n and k_1+k_2+…+k_h ≤ x resp., where h≥ 1 is fixed and k_i ∈, considering permutations in the sense of the formal series:
 
    (∑_a∈ z^a)^h = ∑_n≥ 0 r_,h(n)z^n,   (∑_a∈ z^a)^h/1-z = ∑_n≥ 0 s_,h(n)z^n.

 When h=1, we denote r_,1(n), s_,1(n) by 1_(n) and A(n) resp..
 
 An h-basis is said to be economical[There appears to be conflicting descriptions of economical and thin h-bases in the literature. We believe that the most satisfactory definitions are the following: an h-basis ⊆ is thin when A(x) = Θ(x^1/h) (cf. Nathanson <cit.>), and economical when r_,h(n)≪_ n^ (cf. Chapter III, p. 111 of Halberstam & Roth <cit.>). Note that not all economical bases are thin, and, a priori, thin bases are not necessarily economical. In spite of that, economical h-basis always satisfy A(x) = x^1/h +o(1).] when r_,h(n) ≪_ n^, that is, r_,h(n) = O(n^) for every >0. The study of such objects dates back to S. Sidon, who in the 1930s inquired about the existence of economical 2-basis (cf. Erdős <cit.>). A positive answer was given by Erdős in the 1950s by means of probabilistic (therefore non-constructive) methods, showing the existence of ⊆ with r_,2(n) = Θ(log(n)). A constructive proof was later found in the 1990s (cf. Kolountzakis <cit.>). Also in the 1990s, Erdős and Tetali <cit.> settled the h≥ 3 case, showing for every such h the existence of an h-basis ⊆ with r_,h(n) = Θ(log(n)). The strategy behind their proof can be outlined in three main steps:
 
 
  
  * Define a random sequence ω⊆ by
  
    (n∈ω) = f(n)/n+1,

  where f(x) := Mx^1/hlog(x)^1/h for some large constant M>1; 
  
  
  * Show that the expected value of r_ω,h(n) is Θ(f(n)^h/n); 
  
  
  *  Show that r_ω,h(n) concentrates around its mean. That is,
  
    (∃ c_1,c_2>0 : ∀ n∈,  c_1𝔼(r_ω,h(n)) ≤ r_ω,h(n) ≤ c_2𝔼(r_ω,h(n)) ) = 1.
 
 
 
 The third step is by far the most involved. The case h=2 is rather special, for r_ω,2(n) can be written as a sum of independent Bernoulli trials, hence the third step may be tackled by using Chernoff-type bounds.[As in Section 8.6, p. 139 of Alon & Spencer <cit.>.] This is not the case for h≥ 3. The way Erdős and Tetali worked around this limitation was by showing that the events counted by r_ω,h(n) have low correlation. Vu's alternative proof in Section 5 of <cit.> uses the same principle, albeit with a much more powerful two-sided concentration inequality. In this paper we take each of these aforementioned steps and extend their reach, being relatively faithful to the methods from Erdős & Tetali <cit.>. Our studies culminate in the following:
 
 plain
 *mainthmMain Theorem
 
  Let h≥ 2 be fixed and x_0∈_+ arbitrarily large. For any locally integrable, positive real function f:[x_0,+∞)→_+ such that
  
   
  * ∫_x_0^x f(t)/tdt = Θ(f(x)) ,
   
  * x^1/hlog(x)^1/h≪ f(x) ≪x^1/(h-1)/log(x)^ for some > 0; ∫_x_0^x 
  
  there is an h-basis  with A(x) = Θ(f(x)) such that
  
    r_,h+ℓ(n)= Θ(f(n)^h+ℓ/n),  for every ℓ≥ 0.

  Furthermore, when h=2 the “log(n)^” term can be dropped.
 

 One way of thinking about the condition (<ref>) is that while x^1/hlog(x)^1/h works as a natural lower bound for the methods used by Erdős and Tetali,[So much so that Erdős <cit.> inquired on the existence of 2-bases  with r_,2(n) ≠ o(log(n)), a question that naturally extends to h-bases in general and is still open.] x^1/(h-1) is a natural upper bound. When h≥ 3, however, the term log(n)^ pops up because r_,h-1(n) is not necessarily bounded. These thoughts shall be made clear in our study of Step <ref>, which constitutes Section <ref>. Condition (<ref>) relates to Steps <ref> and <ref>. In Appendix <ref> we show that when f(x) = A(x) for some ⊆, this condition is satisfied if and only if  is an O-regular plus (OR_+) sequence, which are sequences such that A(2x) = O(A(x)) and a_2n = O(a_n). This appendix is used to explain the idea behind the regularity conditions we assume on sequences in order to achieve our result, with a view towards the general theory of sequences and additive bases, and some applications are given. In Section <ref> we present a natural way of using an OR_+ sequence  to induce a probability measure in the space of sequences so that the expected value of r_ω,h(n) is Θ(A(n)^h/n) for all h≥ 1. We will argue that these sequences are the only kind for which one can draw such conclusion.

 
  Our use of the asymptotic notations Θ,≍,O,≪,o,∼ is standard, as well as the “floor” and “ceiling” functions ⌊·⌋, ⌈·⌉. Unless otherwise specified, asymptotic symbols are used assuming n→ +∞ through  and x→ +∞ through . When we say “P(n) holds for all large n” we mean that there is n_0∈ such that P(n) holds for all n≥ n_0. Whenever we define a positive real function f:[x_0,+∞)→_+, the x_0∈_+ is to be assumed arbitrarily large; this is just to accommodate functions such as logloglog(x)/loglog(x) without worrying about small x.
  
  We use  for the probability measure, 𝔼 for expectation and  for variance. Given a probability space (Ω, ℱ, ), we denote the indicator function of an event E∈ℱ by ℐ_E. A random variable (abbreviated r.v.) X:Ω→ is said to be a Bernoulli trial when X(Ω) ⊆{0,1}. The conditional expectation of a r.v. X given an event E∈ℱ is denoted by 𝔼(X|E) := (E)^-1·∫_E X d.
  
  Finally, whenever we write an asymptotic sign with a superscripted “a.s.” we mean that the limit in the definition of that sign holds almost surely, i.e. for a subset of Ω with complement having measure 0. Please refer to the beginning of Appendix <ref> for the notation regarding sequences.
 

 


§ PRELIMINARIES

 This section gathers basic preliminary concepts and results that will be used in our arguments; for this reason, everything is unnumbered. The reader may skim through it first and come back as necessary.



 §.§ Probabilistic tools

 Consider a probability space (Ω, ℱ, ). Given a collection 𝒳 of r.v.s, denote by σ(𝒳) the σ-algebra generated by 𝒳, which is the smallest σ-algebra contained in ℱ such that all r.v.s X∈𝒳 are measurable. Given a sequence (X_n)_n≥ 1 of r.v.s, consider an event 
 
    E ∈⋂_N≥ 1σ((X_n)_n≥ N).

 When the sequence consists of mutually independent r.v.s, this event is independent of any finite subsequence and is called a tail event for the sequence. Such events have either probability 0 or 1.[Kolmogorov's zero–one law (Theorem 2 in Section IV.6, p. 124 of Feller <cit.>).] These observations will be relevant for our discussion in Section <ref>. In what follows, we present the three essential lemmas from probability theory that shall be used in our considerations.
  
 plain
 *disjlemDisjointness lemma
 [Lemma 8.4.1, p. 135 of Alon & Spencer <cit.>]
  Let ℰ = {E_i : i ∈ I} be a (not necessarily finite) family of events and define S:= ∑_E∈ℰℐ_E. If 𝔼(S)<+∞, then for all k≥ 1 the following holds:
  
    (𝒟⊆ℰ disfam : |𝒟| = k ) ≤∑_𝒥:𝒥⊆ℰ
    disfam,  |𝒥| = k(⋀_E∈𝒥 E ) ≤𝔼(S)^k/k!.

 

 plain
 *chernChernoff bounds
 [Theorem 1.8, p. 11 of Tao & Vu <cit.>]
  Let x_1,…,x_n be mutually independent r.v.s with |x_i|≤λ, ∀ i≤ n for some fixed constant λ>0. Taking S:= x_1+⋯+x_n, if 𝔼(S)>0 then, for every >0,
  
    (|S/𝔼(S)-1|≥)≤ 2e^-min{/2, (/2)^2}·𝔼(S)/λ.

 
  
 plain
 *corlemCorrelation inequality
 [Boppana & Spencer <cit.>]
  Suppose Ω = {ω_1,ω_2…} is finite and let ℛ⊆Ω be a random subset given by (ω_k∈ℛ) = p_k, these events being mutually independent. Let 𝔰_1,…,𝔰_n⊆Ω be different subsets of Ω and, respectively, let E_1,…,E_n denote the events “𝔰_i⊆ℛ”. Furthermore, assume (E_i)≤ 1/2 for 1≤ i≤ n. Then:
  
    ∏_i=1^n (E̅_i) ≤(⋀_i=1^n E̅_i) ≤(∏_i=1^n (E̅_i)) e^2Δ,

  where
  
    Δ = ∑_1 ≤ i < j ≤ n 
     E_i∩ E_j ≠∅(E_i∧ E_j)

  and E̅_i is the complement of E_i. A disjoint family (abbreviated disfam) is a mutually independent subfamily of ℰ.
 
 
 It is worth noting that, in Section <ref>, almost all the of techniques used may be broken down into several instances of the disjointness lemma followed by an application of the Borel–Cantelli lemma.[cf. Section VIII.3, p. 200 of Feller <cit.>.]
  


 §.§ Exact representation functions

 Fix an integer h≥ 2. Let n∈ and consider an arbitrary sequence ⊆. Denote by
 
    R_h(n; ) := {(k_1,…, k_h) ∈^h : k_1+⋯ + k_h = n}

 the set of h-representations of n in , writing just R_h(n) when =. We say an h-representation ℜ=(k_1,…,k_h)∈R_h(n; ) is exact when k_i≠ k_j whenever i≠ j. Denote the set of exact h-representations by
 
    ER_h(n; ) := {ℜ∈R_h(n;): ℜ is exact}𝔖_h,

 where 𝔖_h is the symmetric group in h symbols; that is, we consider two exact representations to be equal when one can be obtained by a permutation of the other, hence ℜ∈ER_h(n; ) can be thought of as a set {k_1,…,k_h} rather than as an h-tuple. Similarly, write simply ER_h(n) when =. Two h-representations ℜ, ℜ' ∈R_h(n;) are disjoint when ℜ∩ℜ' = ∅. Thus we define two auxiliary representation functions.
 
  
  * The exact representation function:
  
    ρ_,h(n) := |ER_h(n;)|;

 
  
  * The maxdisfam exact representation function:
  
    _,h(n) := max{|𝒞|: 𝒞⊆ER_h(n;)  is a maximal disjoint family
     of exact h-representations.}.

 
 
 While r_,h is more convenient for induction purposes, ρ_,h is easier to work with in probabilistic settings. This is because on the one hand, one has equations (<ref>), while on the other, ρ_,h may be written as
 
    ρ_,h(n) = ∑_k_1+… +k_h=n 
     k_1< ⋯ < k_h1_(k_1)⋯1_(k_h).

 The _,h function is more abstract. It is useful in probabilistic settings when accompanied by the disjointness lemma. If 𝒞_n⊆ER_h(n;) is a maximal disjoint family of exact h-representations, then
 
    ρ_,h(n) ≤∑_k∈⋃𝒞_nρ_,h-1(n-k) ≤ h·_,h(n)·(max_k∈⋃𝒞_nρ_,h-1(n-k) ),

 for |⋃𝒞_n| ≤ h·_,h(n). This allows us to derive some rough upper bounds for ρ_,h by induction, but is a fairly limited method since _,h(n) ≤ n/h.
 
 
  The reader familiar with hypergraphs may interpret these functions as counting hyperedges in ℋ_,h^(n) = (𝒱,ℰ), where 𝒱:=∩{0,1,…,n} and ℰ:= ER_h(n;). Thus _,h(n) is the cardinality of a maximum matching in ℋ_,h^(n), which when used with the maximum degree Δ_1(ℋ) := max_u∈𝒱| {e ∈ℰ : u ∈ e }| provides some rough upper bounds for |ℰ|. This is a pictorial analogy to keep in mind, but we will not need to make explicit use of it in this paper. For a closely related problem which requires extensive use of this graph-theoretical language, refer to Warnke <cit.>.
 
 
 Another very useful restriction of the set of representations concerns lower bounded representations. Given x_0 ∈_+, consider the partitions
 
    R_h(n;)≥ x_0   := {ℜ∈R_h(n;) : ∀ k∈ℜ, k≥ x_0}, 
    R_h(n;)♭_x_0   := {ℜ∈R_h(n;) : ∃ k∈ℜ, k< x_0}.

 This is distinguishing those h-representations for which the smallest term is at least as large as x_0 from those for which some of its elements are smaller than it. In view of what has been discussed, ER_h(n;)≥ x_0, ER_h(n;)♭_x_0, ρ_,h(n)≥ x_0, ρ_,h(n)♭_x_0, _,h(n)≥ x_0 and _,h(n)♭_x_0 are defined accordingly.
  


 §.§ Regular variation

 Fundamental to the calculations done in this paper are the notions of O-regular variation (Subsection <ref>) and Matuszewska indices ((<ref>) in Subsection <ref>). These are introduced in Appendix <ref>, with a view towards the theory of sequences (in the sense of Halberstam & Roth <cit.>) and the general study of additive bases. The concepts necessary for the proof of the Main Theorem are the definitions of OR, PI and OR_+ sequences (Propositions <ref>, <ref> and <ref>, resp.), as well as what we called the OR–PI lemma (Lemma <ref>).
 


§ THE SPACE OF SEQUENCES (STEP <REF>)

 Denote by 𝒮:={⊆ :  is infinite} the space of integer sequences. Say a real sequence (α_n)_n≥ 0 is a sequence of probabilities when 0≤α_n ≤ 1 for all n∈, and say it is proper when ∑_n≥ 0α_n diverges. A proper sequence of probabilities induces a probability measure on 𝒮; we denote by ⟨𝒮, (α_n)_n⟩ the space (𝒮,ℱ,) that satisfies the following:
 
  
  * The events E_n:={ω: n∈ω}[Here and throughout this paper we denote by ω (ω∈𝒮) a random sequence following the probability distribution induced by (α_n)_n≥ 0.] are measurable and (E_n) = α_n;

  
  * {E_0, E_1, E_2,…} is a collection of mutually independent events;

  
  * ℱ is the σ-algebra induced by the collection {E_0, E_1, E_2, …}.
 
  
 The requirement for (α_n)_n≥ 0 to be proper is a necessary and sufficient condition to ensure that this is a well-defined probability space according to the Borel–Cantelli lemmas. Indeed, once infinite Cartesian products of probability spaces are established,[This may be found in several sources, most notably in Halmos <cit.> (cf. Section 38).] consider a sequence of independent Bernoulli trials with probability α_n of success, then remove those events in which only a finite number of successes occur and identify it with σ((1_ω(n))_n≥ 0).
 
 
  As a side note, the reason we chose to work with 𝒮 instead of the entire power set of  is that we will only deal with infinite sequences. It also has the nice one-to-one correspondence:
  
    𝒮   ⟶/
       ⟼[∑_a∈ 2^-(a+1)]

  thus probability measures on 𝒮 correspond naturally to certain measures on the unit circle. The only ⟨𝒮, (α_n)_n⟩ corresponding to a translation-invariant measure in the circle is the one with α_n = 1/2 for all n∈, which coincides with the Borel measure on /.
 

 Instances of this construction appear in numerous works, most notably in Erdős & Rényi <cit.>. For a classical treatment on related combinatorial and number-theoretical applications, see Chapter III of Halberstam & Roth <cit.>. Essentially, the idea behind these probability measures is to study sequences with certain prescribed rates of growth. Indeed, it is a consequence of Kolmogorov's three-series theorem (cf. Section IX.9 of Feller <cit.>) that if (X_n)_n≥ 0 is a sequence of independent r.v.s with 𝔼(X_n)=0 and ∑_n≥ 0(X_n) < +∞, then ∑_n≥ 0 X_n converges almost surely. The idea of prescribing rates of growth has then the precise meaning implied by the following variant of the strong law of large numbers.[This is a well-known variant of the strong law, as it is mentioned in Erdős & Rényi <cit.>. A similar statement is present in Chapter III, 11 of Halberstam & Roth <cit.>, but with some unnecessary additional hypotheses. Given the fundamental nature of this result in relation to ⟨𝒮, (α_n)_n ⟩, we offer it a short proof just for the sake of completeness.]
  
 
  If (α_n)_n≥ 0 is a proper sequence of probabilities, then in ⟨𝒮, (α_n)_n ⟩ the following holds:
  
    W(x) a.s.∼𝔼(W(x)),

  where W(x) := |ω∩ [0,x]|.
 
 
  First, notice that 𝔼(W(x)) = ∑_n≤ xα_n. Letting n_0 be the smallest number for which α_n_0>0, define the r.v.s
  
    X_n := 1_ω(n)-α_n/∑_k≤ nα_k,

  for all n≥ n_0, with X_n ≡ 0 for n<n_0. Since these are just linear transformations being applied to each 1_ω(n), the r.v.s X_n are still mutually independent. By routine calculations, it follows that 𝔼(X_n)=0 and (X_n) = (α_n - α_n^2 )/(∑_k≤ nα_k)^2. Note that
  
    α_n - α_n^2/(∑_k≤ nα_k )^2≤1/∑_k< nα_k  - 1/∑_k≤ nα_k,

  hence we may telescope the sum ∑_n≥ n_0(X_n) and thus it converges.
  
  By the aforementioned theorem of Kolmogorov, it follows that ∑_n≥ 0 X_n converges almost surely to, say, C≥ 0. Then, for each n≥ -1, define _n := C - ∑_k≤ n X_k. Note that X_k = _k-1 - _k, thus by partial summation we get
  
    W(x) - ∑_n≤ xα_n   = ∑_n≤ x X_n 𝔼(W(n)) 
       = ∑_n≤ x_nα_n+1 + C·𝔼(W(0)) - _⌊ x⌋·𝔼(W(x)).

  Since _n a.s.= o(1), the last term in the RHS is a.s. o(𝔼(W(x))). Recall that ∑_n≤ xα_n diverges, thus the first term is also a.s. o(𝔼(W(x))), hence the theorem is proved.
 
  
 From the many types of tail events in ⟨𝒮, (α_n)_n⟩ one then might study, we focus on the behavior of the r.v.s r_ω,h(n) and s_ω,h(n).

 


§ THE FUNDAMENTAL LEMMA (STEP <REF>)

 Recall that our goal in this step is to describe 𝔼(r_ω,h(n)) in a simple way. If we want to have |ω∩[0,x]| a.s.=Θ(f(x)) in ⟨𝒮, (α_n)_n⟩ for some f, by the strong law it is necessary and sufficient that ∑_n≤ xα_n = Θ(f(x)). If we assume f to be differentiable, one could then choose α_n to be something like f'(n), so that everything is expressed in terms of f. Alternatively, in view of the OR–PI lemma (Lemma <ref>), we could just assume f to be O-regularly varying and having positive increase, so that α_n can be chosen to be something like f(n)/n. This is actually preferable, for it can be formulated in a very clean way:

 [The space 𝒮_]
  When  is an OR_+ sequence, let 𝒮_ denote the space ⟨𝒮, (α_n)_n⟩ with
  
    α_n := A(n)/n+1.

 

 This definition only makes sense when  is OR_+ (Proposition <ref>),[Hence whenever we write 𝒮_ in this paper,  is being assumed OR_+.] for it is the only case in which this construction yields |ω∩ [0,x]| a.s.≍ A(x). Not only that, but since  is, in particular, OR (Proposition <ref>), it follows that s_ω,h(x) a.s.≍ A(x)^h for all h≥ 1. If one has a suitable function f and still wants Θ(f(x)) as the prescribed rate of growth, it is then sufficient to obtain a sequence ⊆ with A(x) = Θ(f(x)). Moreover, in this setting, the expected result holds. We first need the following lemma.
 
 
  Let ⊆, h≥ 1, n∈ and k ≥ 0. Then
  
    r_,h(n) ≤ r_∪{k}, h(n) ≤ r_,h(n)+h⌊ h/2⌋∑_ℓ=1^h-1 r_,h-ℓ(n-ℓ k) + δ_n/h(k),

  where δ_n/h(k) = 1 if k=n/h and 0 otherwise.
 
 
  The LHS inequality is obvious. For the other side we have:
  
    r_∪{k},h(n)    = ∑_k_1+k_2+…+k_h = n1_∪{k}(k_1)1_∪{k}(k_2)…1_∪{k}(k_h) 
       = ∑_k_1+k_2+…+k_h = n1_(k_1)1_(k_2)…1_(k_h) + ∑_k_1+k_2+…+k_h = n 
     k ∈{k_1,⋯,k_h}
     k_j≠ k  k_j ∈ 1.

  Thus, assuming k∉,
  
    r_∪{k},h(n) = r_,h(n) + ∑_ℓ =1^h-1hℓr_,h-ℓ(n-ℓ k) + δ_n/h(k),

  and the RHS inequality follows.
 
  
 
  In 𝒮_ the following holds:
  
    𝔼(r_ω,h(n)) = Θ(A(n)^h/n),  ∀ h≥ 1.

 
 
  Recall the recursive formulas in (<ref>). We have
  
    𝔼(r_ω,h(n)) = ∑_k≤ n𝔼(r_ω,h-1(k)1_ω(n-k)).

  We claim that it is sufficient to show that
  
    ∑_k≤ n𝔼(r_ω,h-1(k)1_ω(n-k)) ≍∑_k≤ n𝔼(r_ω,h-1(k))𝔼(1_ω(n-k)).

  Indeed, since the claim of our lemma holds for h=1 by definition, one may apply induction to see that
  
    ∑_k≤ n𝔼(   r_ω,h-1(k))𝔼(1_ω(n-k)) 
    ≍    ∑_1≤ k≤ n-1A(k)^h-1/kA(n-k)/n-k
    
        =    ∑_1≤ k≤ n/2A(k)^h-1/kA(n-k)/n-k + ∑_n/2<k≤ n-1A(k)^h-1/kA(n-k)/n-k.

  Then, using that  is OR_+, for the “≫” side we have
  
    ∑_1≤ k≤ n-1A(k)^h-1/kA(n-k)/n-k   ≫∑_n/2<k≤ n-1A(k)^h-1/kA(n-k)/n-k
       ≫A(n)^h-1/n∑_n/2<k≤ n-1A(n-k)/n-k
       = A(n)^h-1/n∑_1≤ k< n/2A(k)/k,

  which by Lemma <ref> is ≫ A(n)^h/n. For the “≪” side
  
    ∑_1≤ k≤ n/2A(k)^h-1/k   A(n-k)/n-k + ∑_n/2<k≤ n-1A(k)^h-1/kA(n-k)/n-k
    ≪    A(n)/n∑_1≤ k≤ n/2A(k)^h-1/k + A(n)^h-1/n∑_n/2<k≤ n-1A(n-k)/n-k,

  which, again by Lemma <ref>, is ≪ A(n)^h/n.

  Hence, we just need to prove (<ref>). Note that the case h=2 holds, since the 1_ω(n) are mutually independent over n; hence we apply induction for h≥ 3. The r.v.s r_ω,h-1(k) and 1_ω(n-k) are not mutually independent in general, but since 1_ω(n-k) is a Bernoulli trial, we at least have:
  
    𝔼(r_ω,h-1(k)1_ω(n-k)) = 𝔼(1_ω(n-k))𝔼(r_ω,h-1(k)|1_ω(n-k) = 1).

  Applying Lemma <ref> to ω, h-1, k and taking n-k,
  
    ≤   𝔼(1_ω(n-k))𝔼(r_ω,h-1(k)) (
       ≤𝔼(1_ω(n-k))𝔼(r_ω,h-1(k)|1_ω(n-k) = 1) 
       ≤𝔼(1_ω(n-k))( 𝔼(r_ω,h-1(k))  + δ_k/(h-1)   (n-k)  + 
    
        + h-1⌊h-1/2⌋   ∑_ℓ =1^h-2𝔼(r_ω,h-ℓ-1(ℓ k-(ℓ-1)n))).

  The apparent problem in this estimate is the summation on the upper bound. We show that it ends up being negligible. For h≥ 3 we have
  
    = ∑_k≤ n𝔼(1_ω(n-k)) (h-1⌊h-1/2⌋∑_ℓ =1^h-2𝔼(r_ω,h-ℓ-1(ℓ k-(ℓ-1)n)) δ_k/(h-1)(n-k)) 
       
        =h-1⌊h-1/2⌋∑_ℓ =1^h-2∑_k≤ n𝔼(r_ω,h-ℓ-1(ℓ k-(ℓ -1)n))𝔼   (1_ω(n-k)) + 
     +    ∑_k≤ nδ_(h-1)n/h(k)𝔼(1_ω(n-k))
       
       ≪∑_ℓ =1^h-2∑_k≤ n𝔼(r_ω,h-2(ℓ k-(ℓ-1)n))𝔼(1_ω(n-k)) + A(n)/n
       = ∑_ℓ =1^h-2∑_k≤ n𝔼(r_ω,h-2(n- ℓ k))𝔼(1_ω(k)) +A(n)/n.

  Since “n-ℓ k ≥ 0”“k ≤ n/ℓ”, this summation can subdivided as follows:
  
    ∑_k≤ n𝔼(r_ω,h-2   (n- ℓ k))𝔼(1_ω(k)) 
    ≍    ∑_1≤ k≤n/2ℓA(n-ℓ k)^h-2/n-ℓ kA(k)/k + ∑_n/2ℓ < k≤n/ℓ-1A(n-ℓ k)^h-2/n-ℓ kA(k)/k
    ≪    A(n)^h-2/n∑_1≤ k≤n/2ℓA(k)/k + A(n)/n∑_n/2ℓ < k≤n/ℓ-1A(n-ℓ k)^h-2/n-ℓ k,

  therefore, by Lemma <ref>, this is O(A(n)^h-1/n) for all ℓ≥ 2. With this, we conclude from (<ref>) that
  
    ∑_k≤ n𝔼(r_ω,h-1(k))𝔼(1_ω(n-k)) 
    ≤    ∑_k≤ n𝔼(r_ω,h-1(k)1_ω(n-k)) 
    ≤    ∑_k≤ n𝔼(r_ω,h-1(k))𝔼(1_ω(n-k)) + O(A(n)^h-1/n),

  hence (<ref>) follows, and our proof is complete.
 
 
 Two variations of this lemma will be important to us, one for exact (ρ) and other for lower bounded exact (ρ≥) representation functions. When referenced along the text, consider them in conjunction with Lemma <ref>.
 
 
  In 𝒮_ the following holds:
  
    𝔼(ρ_ω,h(n)) = 1/h!𝔼(r_ω,h(n)) + O(A(n)^h-1/n),   ∀ h≥ 2.

 
 
  All we need to do is show that
  
    𝔼(|{ℜ∈R_h(n;ω):ℜ is non-exact}|) = O(A(n)^h-1/n).

  This is clearly true for h=2, thus we may focus on h≥ 3. For this case, consider the non-probabilistic estimate:
  
    |{ℜ∈R_h(n;ω):ℜ is non-exact}| ≤h2∑_k≤ n/2 r_ω,h-2(n-2k)1_ω(k).

  To analyze this summation, let 𝒩_ω,h(n) := ∑_k≤ n/2 r_ω,h-1(n-2k)1_ω(k). We are going to prove that
  
    𝔼(𝒩_ω,h(n)) = Θ(A(n)^h/n),  ∀ h≥ 2.

  Just as in (<ref>) on the proof of Lemma <ref>, we apply Lemma <ref> for ω, h-1, n-2k and k to obtain:
  
    ≤   𝔼(1_ω(k))𝔼(r_ω,h-1(n-2k)) (
       ≤𝔼(1_ω(k))𝔼(r_ω,h-1(n-2k)|1_ω(k) = 1) 
       ≤𝔼(1_ω(k))( 𝔼(r_ω,h-1(n-2k))  + δ_(n-2k)/(h-1)(k   )  + 
    
         + h-1⌊h-1/2⌋   ∑_ℓ =1^h-2𝔼(r_ω,h-ℓ-1(n-(ℓ+2)k))).

  By calculations similar to the ones in Lemma <ref> it follows
  
    𝔼(𝒩_ω,h(n))    = ∑_k≤ n/2𝔼(r_ω,h-1(n-2k)1_ω(k)) 
       = ∑_k≤ n/2𝔼(r_ω,h-1(n-2k))𝔼(1_ω(k)) + O(A(n)^h-1/n).

  Finally, by using Lemma <ref>,
  
    ∑_k≤ n/2𝔼(r_ω,h-1   (n- 2k))𝔼(1_ω(k)) 
    ≍    ∑_1≤ k≤n/4A(n-2k)^h-1/n-2kA(k)/k + ∑_n/4 < k≤n/2-1A(n-2k)^h-1/n- 2kA(k)/k,

  thus (<ref>) follows from Lemma <ref>.
 
 
 
  Given h≥ 2, for every >0 there is v_h()>0 such that in 𝒮_ the following holds:
  
    𝔼(ρ_ω,h(n)≥ n) ≥ (1-v_h())𝔼(ρ_ω,h(n))  for all large n.

  Furthermore, if = (n) → 0^+ as n→ +∞, then for every positive γ < (A) one can take v_h() in a manner that satisfies
  
    v_h() ≪^γ/2^h-2   (as  n→ +∞ ),

  where (A) is the lower Matuszewska index (cf. (<ref>)) of A.
 
 
  Recall that ρ_ω,h(n)♭_ n = ρ_ω,h(n) - ρ_ω,h(n)≥ n is counting those exact h-representations in which at least one term is smaller than n. All we need to do is show that 𝔼(ρ_ω,h(n)♭_ n) ≤ v_h-1() 𝔼(ρ_ω,h(n)).
  
  An exact h-representation ℜ={k_1,…,k_h} of n which has k_1<  n must have k_h > (1-)/h-1n, therefore
  
    𝔼(ρ_ω,h(n)♭_ n)    = 𝔼(∑_k_1+… +k_h = n 
     k_1 < k_2 < ⋯ < k_h 
     k_1 <  n1_ω(k_1)⋯1_ω(k_h) ) 
       = ∑_k_1+… +k_h = n 
     k_1 < k_2 < ⋯ < k_h 
     k_1 <  nA(k_1)/k_1+1⋯A(k_h)/k_h + 1
       < h-1/(1-)A(n)/n + 1/1-∑_k_1+… +k_h-1≤h-2-/h-1n 
     k_1 < k_2 < ⋯ < k_h-1
     k_1 <  nA(k_1)/k_1+1⋯A(k_h-1)/k_h-1+1,
  
  where the last sum can be estimated by
  
    ∑_ℓ≤h-2-/h-1n   ∑_k_1+… +k_h-1 = ℓ
     k_1 < k_2 < ⋯ < k_h-1
     k_1 <  nA(k_1)/k_1+1⋯A(k_h-1)/k_h-1+1
       ≤∑_ℓ≤^1/2 n𝔼(ρ_ω, h-1(ℓ)) + ∑_^1/2 n < ℓ≤ n∑_k_1+… +k_h-1 = ℓ
     k_1 < k_2 < ⋯ < k_h-1
     k_1 < ^1/2ℓA(k_1)/k_1+1⋯A(k_h-1)/k_h-1+1
       = ∑_ℓ≤^1/2 n𝔼(ρ_ω, h-1(ℓ)) + ∑_^1/2 n < ℓ≤ n𝔼(ρ_ω,h-1(ℓ)♭_^1/2ℓ).

  By Lemma <ref>, there are t_h,T_h>0 such that, for large n,
  
    t_h A(n)^h/n≤𝔼(ρ_ω,h(n)) ≤ T_h A(n)^h/n.

  In addition, recall that  is OR_+, thus its lower Matuszewska index (A) is positive. Therefore for every 0 < γ < (A) there must be some M = M_γ∈_+ for which A( n) ≤ M ^γ A(n) for all large n. Using that, we can prove our statement by induction.
  
  When h=2, by Lemma <ref>, there exists C∈_+ such that, for large n,
  
    𝔼(ρ_ω,2(n)♭_ n)    = ∑_k <  nA(k)/k+1A(n-k)/n-k+1
       ≤A(n)/(1-)n+1∑_k <  nA(k)/k+1≤ C·A(n)/n A( n),

  thus, since A( n) ≤ M ^γ A(n), our statement applies for h=2, including the upper bound for v_2() in (<ref>) for =(n)→ 0^+. Supposing it holds for h-1, from (<ref>) we get
  
    ∑_ℓ≤^1/2 n𝔼(   ρ_ω, h-1(ℓ)) + ∑_^1/2 n < ℓ≤ n𝔼(ρ_ω,h-1(ℓ)♭_^1/2ℓ) 
       ≤ C T_h-1 M^h-1^(h-1)γ/2 A(n)^h-1 + T_h-1 v_h-1(^1/2)∑_ℓ≤ nA(ℓ)^h-1/ℓ
       ≤ C T_h-1(M^h-1^(h-1)γ/2 + v_h-1(^1/2) ) A(n)^h-1,

  for large n and some C∈_+ that comes from Lemma <ref>. Substituting this in (<ref>) yields
  
    𝔼(ρ_ω,h(n)♭_ n) < h-1/(1-)n/n+1/1-C T_h-1(M^h-1^(h-1)γ/2 + v_h-1(^1/2) ) A(n)^h/n.

  We have that n/(n+1/1-) ∼ 1 as n→ +∞ and every other term in this coefficient is either bounded or independent of , except for ^(h-1)γ/2 and v_h-1(^1/2). Since the induction step includes (<ref>), we deduce that these two terms must remain bounded, and if =(n)→ 0^+ then they must vanish like O(^γ/2^h-2). The proof is then complete.
 
  
 We finish this section with an important remark about Lemma <ref>.
 
 
  Let g:[x_0,+∞)→_+ be a positive real function satisfying the conditions of Lemma <ref>. Based on this lemma, for each 2≤ℓ≤ h let c_ℓ be some positive constant for which
  
    ∑_x_0 < k ≤ n-x_0g(k)^ℓ-1/kg(n-k)/n-k > c_ℓg(n)/n

  holds for all large n. In Lemma <ref>, in view of (<ref>), it is possible to deduce from the equations in (<ref>) that if  is such that A(n) > M g(n) for some M > 0 and all large n, then
  
    𝔼(r_ω,h(n)) > M^h(∏_ℓ = 2^h c_h) g(n)^h/n,   ∀suff. large n.

  Note that the same holds when inequalities are reversed. These observations are key for the proof of the Main Theorem.
 
  



§ CONCENTRATION (STEP <REF>)

 Now that the general setup is established, we will start working with the conditions from the Main Theorem. We start with the two lemmas that constitute the most technical parts of the proof.



 §.§ Lemmas

 The following results have a similar theme concerning the condition A(x) ≪ x^1/(h-1). As mentioned in Section <ref>, our methods are naturally limited by the fact that _ω,h(n) ≤ n/h; this is basically why x^1/(h-1) pops up, and the purpose of the following lemmas is to make the most out of this restraint. The first lemma says that non-exact h-representations are, almost surely, conveniently scarce in 𝒮_ for such .
  
 
  Let h≥ 2 be fixed. If A(x)≪ x^1/(h-1), then in 𝒮_ the following holds:
  
    ρ_ω,h-1(n) a.s.= O(log(n)/loglog(n)),

  
    |{ℜ∈R_h(n;ω):ℜ is non-exact}| a.s.= O(log(n)/loglog(n)).

  Furthermore,
  
    ρ_ω,h(n) a.s.≪∑_k∈⋃𝒞_n_ω,h-1(n-k),

  where 𝒞_n ⊆ER_h(n;ω) is a maximal disjoint family.
 
 
  We start by proving the first two estimates. Just as in Lemma <ref>, we have the non-probabilistic estimate
  
    |{ℜ∈R_ℓ(n;ω):ℜ is non-exact}| ≤ℓ2𝒩_ω,ℓ -1(n)

  for ℓ≥ 3, where 𝒩_ω,ℓ(n) = ∑_k≤ n/2 r_ω,ℓ-1(n-2k)1_ω(k). Note that this is counting the number of solutions to
  
    2 x_1 + x_2 + … + x_ℓ = n,    x_i∈ω.

 
  Consider now 𝒩_ω,ℓ(n) to be the cardinality of the largest maximal collection of disjoint multisets[A multiset is a set that allows multiple instances of an element.] {k_1,k_2,…,k_ℓ}⊆ω satisfying (<ref>). We may then deduce the following non-probabilistic inequalities:
  
    r_ω,ℓ(n)    ≤ℓ! ℓ(max_k≤ nr_ω,ℓ-1(k))_ω,ℓ(n) + ℓ2𝒩_ω,ℓ-1(n) 
    𝒩_ω,ℓ(n)    ≤ℓ! ℓ^2 (max_k≤ n{𝒩_ω,ℓ-1(k)} + max_k≤ n{r_ω,ℓ-1(k)}) 𝒩_ω,ℓ(n).

  Indeed, (<ref>) follows by noticing that when 𝒞⊆ER_ℓ(n;ω) is a maximal collection of pairwise disjoint representations with |𝒞|=_ω,ℓ(n), we have |⋃𝒞| = ℓ·_ω,ℓ(n) and ℜ∩(⋃𝒞) ≠∅ for every ℜ∈ER_ℓ(n;ω); thus the first term bounds the number of exact ℓ-representations, whereas the latter bounds the number of non-exact ones. The reasoning for (<ref>) is analogous.
  
  To prove our lemma, we just need to show that 𝒩_ω,h-1(n) a.s.= O(log(n)/loglog(n)). The estimate in (<ref>) allows us to break this into the following three items:
  
   
  * r_ω,h-2(n) a.s.= O(1); 
   
  * 𝒩_ω,h-2(n) a.s. = O(1); 
   
  * 𝒩_ω,h-1(n) a.s. = O(log(n)/loglog(n)). 
  
  The first two are dealt with by induction. Since r_ω,2(n)≪_ω,2(n)+1 and 𝒩_ω,2(n) ≪𝒩_ω,2(n), to show (<ref>) and (<ref>) it is sufficient to, in view of (<ref>) and (<ref>), show that:
  
   
  * _ω,ℓ(n) a.s.= O(1),  for all  2≤ℓ≤ h-2; 
   
  * 𝒩_ω,ℓ(n) a.s. = O(1),  for all  2≤ℓ≤ h-2. 
  
  At this point, we have managed to reduce all our problems to estimates involving maxdisfam-type counting functions, thus the next natural step is to use the disjointness lemma! We now prove (<ref>)*, (<ref>)* and (<ref>). ∙ Items (<ref>)* and (<ref>)*: Starting with (<ref>)*, from (<ref>) in Lemma <ref> we know that 𝔼(𝒩_ω,ℓ(n)) = Θ(A(n)^ℓ/n). Thus, as the function 𝒩_ω,ℓ(n) is counting mutually independent events, applying the disjointness lemma yields, in view of having A(x)≪ x^1/(h-1),
  
    (𝒩_ω,ℓ(n) ≥ M ) ≤𝔼(𝒩_ω,ℓ(n))^M/M!≪(A(n)^h-2/n)^M ≪ n^-M/(h-1).

  Therefore, if we take M > 2(h-1), it follows from the Borel–Cantelli lemma that 𝒩_ω,ℓ(n) a.s.= O(1) for all ℓ considered. The case (<ref>)* for _ω,ℓ(n) goes analogously. ∙ Item (<ref>): Once again we apply the disjointness lemma, but this time we shall take M = M_n to be a slowly growing function in n. First, we have
  
    (𝒩_ω,h-1(n) ≥ M_n ) ≤𝔼(𝒩_ω,h-1(n))^M_n/M_n!.

  Let M_n := ⌈ 2log(n)/loglog(n) ⌉ for n > e^e. Since M_n is unbounded and non-decreasing, we have that for every >0 there is n_0∈ such that
  
    (1-)M_nlog(M_n) ≤log(M_n!) ≤ (1+) M_nlog(M_n),  ∀ n≥ n_0.

  Thus, keeping in mind that 𝔼(𝒩_ω,h-1(n)) < C for some C>0 and all large n, we may apply “-log” in both sides of (<ref>) to obtain, for large n,
  
    -log((𝒩_ω,ℓ(n) ≥ M_n ))    ≥log(M_n!) - M_nlog(C) 
       ≥ (1-)M_nlog(M_n) 
       ≥ (1-)2log(n)/loglog(n)log(2log(n)/loglog(n)) 
       ≥ 2(1-)log(n) - o(log(n)).

  Therefore (𝒩_ω,h-1(n) ≥ M_n ) ≤ n^-2(1-)+o(1). Choosing < 1/2, we conclude from the Borel–Cantelli lemma that 𝒩_ω,h-1(n) a.s.= O(M_n), thus completing the proof of (<ref>). As before, the reasoning for ρ_ω,h-1(n) is analogous. Finally, given ℓ≥ 2, consider 𝒞^(ℓ)_n ⊆ER_ℓ(n;ω) a maximal disjoint family of exact ℓ-representations of n. By definition, we will have
  
    ρ_ω,ℓ(n) ≤∑_k∈⋃𝒞^(ℓ)_nρ_ω,ℓ-1(n-k).

  From item (<ref>) we know that ρ_ω,ℓ-1(n) a.s.= O(1) for 2 ≤ℓ≤ h-1, therefore, since |⋃𝒞^(ℓ)_n| = ℓ·_ω,ℓ(n), the above implies ρ_ω,ℓ(n) a.s.≪_ω,ℓ(n) for such ℓ, thus the last estimate stated in the lemma follows.
 
 
 The second lemma is very similar to Lemma 11 from Erdős & Tetali <cit.>; the goal is to show that we will have “Δ” arbitrarily small in our applications of the correlation inequality. By an abuse of notation, given ℜ∈ER_h(n) we shall also use “ℜ” to denote the event “ℜ∈ER_h(n;ω)”.
  
 
  Let h≥ 2 be fixed. For every >0 there is M_0∈_+ such that, if A(x)< M^-1 x^1/(h-1) for some M>M_0 and all sufficiently large x, then in 𝒮_ the following holds:
  
    ∑_ℜ,ℜ'∈ER_h(n) 
     1≤ |ℜ∩ℜ'|≤ h-2( ℜ∧ℜ') <

  for all sufficiently large n.
 
 
  Rewriting this sum as
  
    ∑_ℜ,ℜ'∈ER_h(n) 
     1≤ |ℜ∩ℜ'|≤ h-2( ℜ∧ℜ') = ∑_ℓ=1^h-2∑_ℜ,ℜ'∈ER_h(n) 
     |ℜ∩ℜ'|=ℓ( ℜ∧ℜ'),

  we just need to estimate each of the terms for ℓ fixed. Taking ℜ∩ℜ' with |ℜ∩ℜ'|=ℓ, say we have
  
    ℜ = {x_1,…,x_ℓ, y_1,…,y_h-ℓ} and ℜ' = {x_1,…,x_ℓ, z_1,…,z_h-ℓ},

  with ∑_i=1^ℓ x_i = k and y_i ≠ z_j for all i,j. Letting ∑^* denote the sum over exact representations and abusing the notation again by writing “(x_i)” to denote “(1_ω(x_i)=1)”, we have:
  
    ∑_ℜ,ℜ'∈ER_h(n) 
     |ℜ∩ℜ'|=ℓ   ( ℜ∧ℜ') 
    
       =    ∑_k≤ n ^*∑_x_1+…+x_ℓ = k 
     y_1+…+y_h-ℓ = n-k 
     z_1+…+z_h-ℓ = n-k(x_1)⋯(x_ℓ)(y_1)⋯(y_h-ℓ)(z_1)⋯(z_h-ℓ) 
    ≤    ∑_k≤ n( ^*∑_x_1+… +x_ℓ = k(x_1)⋯(x_ℓ)) ( ^*∑_y_1+… +y_h-ℓ = n-k(y_1)⋯(y_h-ℓ))^2 
    
       =    ∑_k≤ n𝔼(ρ_ω,ℓ(k))𝔼(ρ_ω,h-ℓ(n-k))^2.

  
  Since A(n) < M^-1n^1/(h-1) and 𝔼(ρ_ω,ℓ(n)) ≤ℓ!^-1𝔼(r_ω,ℓ(n)) for all large n, the observation from Remark <ref> allows us to derive
  
    ∑_k≤ n   𝔼(ρ_ω,ℓ(k)) 𝔼(ρ_ω,h-ℓ(n-k))^2 
       < M^-ℓ (h-ℓ)^2C_ℓ (C_h-ℓ)^2/ℓ! (h-ℓ)!^2∑_1≤ k≤ n-1k^ℓ/(h-1)/k((n-k)^(h-ℓ)/(h-1)/n-k)^2,

  for some C_ℓ,C_h-ℓ>0 not depending on , for all large n. Note that for all ℓ ranging from 1 to h-2, which is the range being considered,
  
    max_1≤ k ≤ n-1((n-k)^(h-ℓ)/(h-1)/n-k) = 1,

  hence
  
    M^-ℓ (h-ℓ)^2   C_ℓ (C_h-ℓ)^2/ℓ! (h-ℓ)!^2∑_1≤ k≤ n-1k^ℓ/(h-1)/k((n-k)^(h-ℓ)/(h-1)/n-k)^2
       ≤ M^-ℓ (h-ℓ)^2C_ℓ (C_h-ℓ)^2/ℓ! (h-ℓ)!^2∑_1≤ k≤ n-1k^ℓ/(h-1)/k(n-k)^(h-ℓ)/(h-1)/n-k.

  The nature of the above convolution is analogous to that of (<ref>) and the ones described in Remark <ref>, thus it is not difficult to see that this sum is bounded as n→+∞ by, say, some T>0. Going back to (<ref>), we then arrive at
  
    ∑_ℜ,ℜ'∈ER_h(n) 
     1≤ |ℜ∩ℜ'|≤ h-2( ℜ∧ℜ') < M^-ℓ (h-ℓ)^2C_ℓ (C_h-ℓ)^2/ℓ! (h-ℓ)!^2T

  for all large n, where M is the only term depending on . Since M can be chosen as big as desirable, our lemma follows.
 
 
 We now prove the Main Theorem.
 


 §.§ Proof of the Main Theorem

 Fix h≥ 2 an integer. Take a positive and locally integrable real function f:[x_0,+∞)→_+ such that
 
    x^1/hlog(x)^1/h≪ f(x) ≪ x^1/(h-1)   and   ∫_x_0^x f(t)/tdt = Θ(f(x)).

 Since f(x)≪ x, let K := lim sup_x f(x)/x. Choose ϵ>0 and let x^* be such that f(x) ≤ (K+ϵ)x for all x≥ x^*. Define then, for every n≥ 0,
 
    α_n := 1,α_n = 1,α_n = (K+ϵ)^-1 f(n)/n, if n < x^*;
    α_n := (K+ϵ)^-1 f(n)/n,  if n≥ x^*.

 By Lemma <ref>, f is in particular almost increasing, thus
 
    ∫_x_0^xf(t)/tdt ≍∑_x_0 <n≤ xf(n)/n,

 which, by the same lemma, is Θ(f(x)). From strong law of large numbers it then follows that in ⟨𝒮,(α_n)_n ⟩ it holds |ω∩[0,x]| a.s.≍ f(x). Since this is a non-empty  probability space, there must be at least some ⊆ for which C(x)=Θ(f(x)).
  
 Based on this, let us construct a more convenient sequence . We know from x^1/hlog(x)^1/h≪ C(x) ≪ x^1/(h-1) that there must exist q_1,q_2 > 0 for which ∃ n_0∈ : ∀ n≥ n_0 the following holds:
 
    q_1 · x^1/hlog(x)^1/h≤ C(x) ≤ q_2· x^1/(h-1)

 With this in mind, take:
 
    M_1,M_2 > 1   large real constants to be specified later.

 Let n_1∈ be large enough so that, for all n≥ n_1,
 
    M_1 n^1/hlog(n)^1/h + 1    > M_1(n+1)^1/hlog(n+1)^1/h, 
    1/M_2 n^1/(h-1) + 1    > 1/M_2 (n+1)^1/(h-1).
  
 The following construction is then well-defined:
 
  
  * Define _n_1 := {1,2…,n_1}.
   
  
  * For each integer k > n_1, define _k in the following manner:
  
   
  * In case k ∉, check whether
   
    |_k-1∩ [0,k]|/k^1/hlog(k)^1/h≤ M_1.

   If so, take _k := _k-1∪{k}; otherwise, take _k := _k-1.
    
   
  * In case k ∈, check whether
   
    |(_k-1∪{k})∩ [0,k]|/k^1/(h-1)≥1/M_2.

   If so, take _k := _k-1; otherwise, take _k := _k-1∪{k}.
  
 
 Finally, let := ⋃_k≥ n_1_k. From the symmetric nature of this construction and from (<ref>), it is possible to deduce that if M_1,M_2 are large enough so that M_1 M_2 > q_1/q_2, then  must satisfy
 
    lim sup_n→ +∞A(n)/C(n)≤M_1/q_1  and  lim inf_n→ +∞A(n)/C(n)≥1/q_2 M_2,

 which implies A(x) = Θ(C(x)). More importantly,  satisfies:
 
    M_1 · n^1/hlog(n)^1/h≤ A(n) ≤1/M_2· n^1/(h-1)

 from some point onward.
  
 Before proceeding, we highlight the important stuff that shall be used throughout the proof of our next results in the following remark.
  
 
  If the constants M_1,M_2 from (<ref>) are large enough – i.e. satisfying M_1 M_2 > q_1/q_2 where q_1,q_2 are the constants from (<ref>), then we can construct an OR_+ sequence  with A(n)=Θ(f(n)) satisfying (<ref>) for all sufficiently large n.
 
 
 In short, to prove the Main Theorem stated at the introduction we first show that _ω,h(n) has a.s. the right rate of growth, then ρ_ω,h(n), and then r_ω,h+ℓ(n) for all ℓ≥ 0.
  
  In the above construction of , if M_1>1 is sufficiently large, then in 𝒮_ the following holds:
 
    _ω,h(n) a.s.=Θ(A(n)^h/n).

 
 
  We divide the proof into two parts. ∙ Part 1: Showing _ω, h(n) a.s.≪ A(n)^h/n.
  
  Let T>0 be a large integer. By the disjointness lemma,
  
    (_ω,h(n) ≥ T⌈𝔼(ρ_ω,h(n))⌉) ≤𝔼(ρ_ω,h(n))^T⌈𝔼(ρ_ω,h(n))⌉/(T⌈𝔼(ρ_ω,h(n))⌉)!,

  thus, as for all k≥ 1 it holds k!>k^ke^-k,
  
    (_ω,h(n) ≥ T⌈𝔼(ρ_ω,h(n))⌉) ≤(e/T𝔼(ρ_ω,h(n))/⌈𝔼(ρ_ω,h(n))⌉)^T⌈𝔼(ρ_ω,h(n))⌉.

  Since A(n) ≥ M_1 n^1/hlog(n)^1/h, in view of Lemma <ref> and Remark <ref> we have 𝔼(ρ_ω,h(n)) > α M_1^h log(n) for all large n, where α>0 is some constant (not depending on !). Thus, taking T > max{e^2, 2α^-1 M_1^-h} yields
  
    (e/T𝔼(ρ_ω,h(n))/⌈𝔼(ρ_ω,h(n))⌉)^T⌈𝔼(ρ_ω,h(n))⌉≪(1/e)^2log(n)+o(log(n))≪ n^-2+o(1),

  hence it follows from the Borel–Cantelli lemma that _ω,h(n)a.s.≪ A(n)^h/n. ∙ Part 2: Showing _ω, h(n) a.s.≫ A(n)^h/n.
  
  This part is basically Theorem 3 from Erdős & Tetali <cit.> with the added nuances from our hypotheses. Recalling our definition of lower bounded representations, it suffices to show that _ω, h(n)≥ n^1/2a.s.≫ A(n)^h/n. From Lemma <ref>,
  
    𝔼(ρ_ω, h(n)≥ n^1/2) = (1-o(1))𝔼(ρ_ω, h(n)).

  Similar to what was done in Lemma <ref>, given ℜ∈ER_h(n)≥ n^1/2 we abuse the notation by letting “ℜ” denote the event “ℜ∈ER_h(n;ω)≥ n^1/2”. In addition, let ∑^(k) denote the sum over all k-sets of pairwise disjoint lower bounded (by n^1/2) exact representations of n. Letting t>0 be a small real number, we then have:
  
    (∃𝒞⊆ER_h(n;ω)≥ n^1/2 maxdisfam: |𝒞| ≤ t𝔼(ρ_ω,h(n)) ) 
    
       =    ∑_1≤ k≤ t𝔼(ρ_ω,h(n))(∃𝒞⊆ER_h(n;ω)≥ n^1/2 maxdisfam: |𝒞| = k ) 
    
       =    ∑_1≤ k≤ t𝔼(ρ_ω,h(n))  ^(k)∑_{ℜ_1,…,ℜ_k}
    pairwise
    disjoint(( ℜ_1 ∧⋯∧ℜ_k )·({ℜ_1…ℜ_k} is maximal))

  
  We may estimate both factors in the above summation separately. The first term can be estimated directly from the disjointness lemma:
  
    ^(k)∑_{ℜ_1,…,ℜ_k}
    pairwise
    disjoint( ℜ_1 ∧⋯∧ℜ_k ) ≤𝔼(ρ_ω,h(n))^k/k!

  For the second term we use the correlation inequality! Given ℜ∈ER_h(n)≥ n^1/2, let “ℜ̅” denote the event “ℜ∉ER_h(n;ω)≥ n^1/2”. Then:
  
    ({ℜ_1,…,ℜ_k} is maximal) = (⋀_ℜ∈ER_h(n)≥ n^1/2
    ℜ∩ℜ_j = ∅  (j=1,…,k) ℜ̅)

  When h=2 the events ℜ̅ are mutually independent, and when h≥ 3 we can choose n large enough so that (ℜ)≤ 1/2 for every ℜ∈ER_h(n)≥ n^1/2.[This passage illustrates the necessity of considering ER_h(n)≥ n^1/2 instead of ER_h(n).] Therefore we can apply the correlation inequality as follows:
  
    (⋀_ℜ∈ER_h(n)≥ n^1/2
    ℜ∩ℜ_j = ∅  (j=1,…,k) ℜ̅)    ≤(∏_ℜ∈ER_h(n)≥ n^1/2
    ℜ∩ℜ_j = ∅  (j=1,…,k) (ℜ̅)) e^2Δ(n)
       = (∏_ℜ∈ER_h(n)≥ n^1/2
    ℜ∩ℜ_j = ∅  (j=1,…,k)  (1 - (ℜ))) e^2Δ(n)
       ≤exp(-∑_ℜ∈ER_h(n)≥ n^1/2
    ℜ∩ℜ_j = ∅  (j=1,…,k) (ℜ)) e^2Δ(n),

  where Δ(n) can be taken to be
  
    Δ(n) = ∑_ℜ,ℜ'∈ER_h(n) 
     1≤ |ℜ∩ℜ'|≤ h-2( ℜ∧ℜ').

  However, since A(x) ≤ M_2^-1 x^1/(h-1), we know from Lemma <ref> that Δ(n) is bounded, thus e^2Δ(n)<K for some constant K>0. For the term inside exp, from (<ref>),
  
    ∑_ℜ∈ER_h(n)≥ n^1/2
    ℜ∩ℜ_j = ∅  (j=1,…,k) (ℜ   ) ≥𝔼(ρ_ω,h(n)≥ n^1/2) - 𝔼(∑_ℓ∈⋃{ℜ_1,…,ℜ_k}ρ_ω,h-1(n-ℓ)) 
       = (1-o(1))𝔼(ρ_ω,h(n)) - ∑_ℓ∈⋃{ℜ_1,…,ℜ_k}𝔼(ρ_ω,h-1(n-ℓ)).

  Since A(n) ≪ n^1/(h-1), we have by Lemma <ref> that 𝔼(ρ_ω,h-1(n)) = O(1), therefore the summation in the last equality above is bounded above by k· hJ for some fixed J>0. Since h,J are fixed and k≤ t𝔼(ρ_ω,h(n)), we finally arrive at
  
    ({ℜ_1,…,ℜ_k} is maximal) ≤ Ke^-(1-_t -o(1))𝔼(ρ_ω,h(n))

  for all k-sets {ℜ_1,…,ℜ_k} considered, where _t := t· hJ, which goes to 0 as t→ 0^+.
  
  Keeping in mind that, again, k!>k^ke^-k for all k≥ 1, plugging (<ref>) and (<ref>) into what we originally wanted to estimate yields
  
    (∃𝒞⊆ER_h(n;ω)≥ n^1/2 maxdisfam: |𝒞| ≤ t𝔼(ρ_ω,h(n)) ) 
       ≤ Ke^-(1-_t -o(1))𝔼(ρ_ω,h(n))∑_1≤ k≤ t𝔼(ρ_ω,h(n))𝔼(ρ_ω,h(n))^k/k!
       ≤ Ke^-(1-'_t -o(1))𝔼(ρ_ω,h(n))∑_1≤ k≤ t𝔼(ρ_ω,h(n))(𝔼(ρ_ω,h(n))/k)^k,

  where '_t := _t + t, still going to 0 with t. As a function of k, one can show that the maximum of (𝔼(ρ_ω,h(n))/k)^k is attained when k = 𝔼(ρ_ω,h(n))/e. Thus, choosing t < 1/e, we have
  
    ∑_1≤ k≤ t𝔼(ρ_ω,h(n))(𝔼(ρ_ω,h(n))/k)^k    ≤ t𝔼(ρ_ω,h(n))· t^-t𝔼(ρ_ω,h(n))
       ≤ t𝔼(ρ_ω,h(n))· e^-tlog(t)𝔼(ρ_ω,h(n)),

  leading us to, in view of 𝔼(ρ_ω,h(n)) ≪ n^1/h-1 (Lemma <ref>),
  
    (∃𝒞⊆ER_h(n;ω)≥ n^1/2 m.d.f. : |𝒞| ≤ t𝔼(ρ_ω,h(n)) ) ≪ n^1/h-1e^-(1-”_t -o(1))𝔼(ρ_ω,h(n)),

  wherem.d.f. = maxdisfam. ”_t := '_t - tlog(t), which once more goes to 0 with t.
  
  Repeating the argument at the end of Part 1, we know that for some β>0 independent of  we have 𝔼(ρ_ω,h(n)) > β M_1^hlog(n) for all large n. Therefore, taking t>0 small and choosing M_1>1 large enough so that (1-”_t)β M_1^h > 2+1/h-1, we get
  
    (∃𝒞⊆ER_h(n;ω)≥ n^1/2 maxdisfam: |𝒞| ≤ t𝔼(ρ_ω,h(n)) ) ≪ n^-2+o(1),

  from which we apply the Borel–Cantelli lemma to conclude that _ω, h(n)≥ n^1/2a.s.≫ A(n)^h/n, thus concluding our proof.
 
 
 Notice that in order to yield the conclusion of our previous result we only had to deal with M_1, which was done at the very end. We will only deal directly with M_2 in Theorem <ref>. Since _ω,h(n) ≪ρ_ω,h(n), to prove that ρ_ω,h(n) has a.s. the right rate of growth we just need to show that
 
    ρ_ω,h(n) a.s≪_ω,h(n),

 and this is what the next two lemmas will be aiming at. This is immediate for h=2, thus the assumption h≥ 3 will be implicit. From Lemma <ref> we know that if 𝒞_n ⊆ER_ℓ(n;ω) is a maximal disjoint family of exact h-representations of n then
 
    ρ_ω,h(n) a.s.≪∑_k∈⋃𝒞_n_ω,h-1(n-k).

 In this lemma, we use the fact that 𝔼(ρ_ω,h-1(n)) = O(1) to deduce that _ω,h-1(n) a.s.= O(log(n)/loglog(n)). This fact, however, is not sufficient to conclude from (<ref>) the statement we want.[In fact, this O(log(n)/loglog(n)) seems to be a strong barrier to this method. Not having 𝔼(ρ_ω,h-1(n)) ≪ n^- is also the reason we avoided the methods from Tao & Vu <cit.> (particularly Theorem 1.37, p. 35).] We can, however, draw this conclusion for certain partitions of . Letting 0<< h^-2, consider
 
    𝐏_1 := { n∈ : A(n) ≤ n^1/(h-1)-} and  𝐏_2 := ∖𝐏_1.
 
  
 Before studying these partitions, let us first split ER_h(n;ω) in view of Lemma <ref>. We know that  is OR_+, thus its lower Matuszewska index (A) is positive. With that in mind, fix some 0 < γ < (A) and take δ >0 with
 
    δ <  (h-1)/1-γ (h-1).

 Notice that the RHS is positive, for since A(x)≪ x^1/(h-1) one must have (A) ≤ 1/(h-1). Now, split ρ_ω,h into ρ_ω,h(n) = ρ_ω,h(n)≥ n^1-δ + ρ_ω,h(n)♭_n^1-δ, with 𝒞_n≥ n^1-δ and 𝒞_n♭_n^1-δ being maxdisfams in each corresponding set. The next lemma shows that _ω,h will almost surely dominate ρ_ω,h in 𝐏_1.
 
 
  Let “≪_1” denote “≪ as n→ +∞ through 𝐏_1”. In the above notation, following Lemma <ref> (i.e. having M_1 >1 sufficiently large), if 𝐏_1 is infinite then in 𝒮_ the following holds:
  
    ρ_ω,h(n) a.s.≪_1 _ω,h(n).

 
 
  We divide the proof into two parts. First, we show that ρ_ω,h(n)♭_n^1-δ does not contribute to the growth rate of ρ_ω,h(n). ∙ Part 1: Showing ρ_ω,h(n)♭_n^1-δa.s.= O(_ω,h(n)/loglog(n) ).
  
  Recall that this quantity is counting those representations in which at least one member is less than n^1-δ. From (<ref>) in Lemma <ref>,
  
    𝔼(ρ_ω,h(n)♭_n^1-δ ) ≪ n^-δγ/2^h-2𝔼(ρ_ω,h(n) ),

  thus, proceeding as in Part 1 from Lemma <ref>, we apply the disjointness lemma to estimate |⋃𝒞_n♭_n^1-δ|. Keeping in mind that for k≥ 1 it holds k!>k^ke^-k, for any integer T>0 it follows that
  
    ( _ω,h(n)♭_n^1-δ≥ T⌈_ω,h(n)/log(n)⌉)    ≤( n^-δγ/2^h-2𝔼(ρ_ω,h(n)) )^T⌈_ω,h(n)/log(n)⌉/(T⌈_ω,h(n)/log(n) ⌉ )!
       ≤(e/T𝔼(ρ_ω,h(n))/_ω,h(n)n^-δγ/2^h-2/1/log(n))^T⌈_ω,h(n)/log(n)⌉.

  
  Since _ω,h(n) a.s.=Θ(𝔼(ρ_ω,h(n))) by Lemma <ref> and 𝔼(ρ_ω,h(n)) ≫log(n) by Lemma <ref>, let ϑ>0 such that log(n)n^-δγ/2^h-2≪ n^-ϑ and consider T large enough so as to cancel out all constant terms inside the parentheses. This will yield
  
    (e/T𝔼(ρ_ω,h(n))/_ω,h(n)n^-δγ/2^h-2/1/log(n))^T⌈_ω,h(n)/log(n)⌉   ≪(log(n) n^-δγ/2^h-2)^T⌈_ω,h(n)/log(n)⌉
       ≪ n^-ϑ T⌈_ω,h(n)/log(n)⌉.

  Therefore, picking T large enough to also have ϑ T⌈_ω,h(n)/log(n) ⌉ > 2 from some point onward, we conclude that _ω,h(n)♭_n^1-δa.s.≪_ω,h(n)/log(n) from the Borel–Cantelli lemma. Finally, the same reasoning behind (<ref>) may be used to derive
  
    ρ_ω,h(n)♭_n^1-δa.s.≪∑_k∈⋃𝒞_n♭_n^1-δ_ω,h-1(n-k)♭_n^1-δ,

  thus, since _ω,h-1(n) a.s.= O(log(n)/loglog(n)) from Lemma <ref>, we get:
  
    ρ_ω,h(n)♭_n^1-δ   a.s.≪|⋃𝒞_n♭_n^1-δ| ·max_k∈⋃𝒞_n♭_n^1-δ(_ω,h-1(n-k)♭_n^1-δ) 
       a.s.≪_ω,h(n)/log(n)·log(n)/loglog(n) = _ω,h(n)/loglog(n),

  as required. ∙ Part 2: Showing ρ_ω,h(n)≥ n^1-δa.s.≪_1 _ω,h(n).
  
  Recall that δ = δ(, γ), i.e. it depends on both  and γ, where 0< γ< (A). By the definition of (A), we know there is m>0 such that for large x, for every λ≥ 1 the following holds:
  
    A(λ x) > mλ^γ A(x).

  Rearranging this, for large x we have
  
    A(x^1-δ)^h-1/x^1-δ < 1/m^h-1x^δ(1-γ (h-1))A(x)^h-1/x,

  thus, in view of Lemma <ref>,
  
    𝔼(ρ_ω,h-1(n^1-δ)) ≪ n^δ(1-γ(h-1))𝔼(ρ_ω,h-1(n)).

  The partition 𝐏_1 was chosen because 𝔼(ρ_ω,h-1(n)) ≪_1 n^-(h-1), and thus
  
    𝔼(ρ_ω,h-1(n^1-δ)) ≪_1 n^δ(1-γ(h-1)) -(h-1).

  Therefore, by our choice of δ in (<ref>), we have that for some ϑ >0 it holds:
  
    𝔼(ρ_ω,h-1(k)) ≪ k^-ϑ as  k→ +∞ through 𝐏_1 ∪{[n^1-δ, n] : n ∈𝐏_1 },

  
  Using the same strategy used in items (<ref>)* and (<ref>)* at the proof of Lemma <ref>, our argument to bound ρ_ω,h(n)≥ n^1-δ will be an application of the disjointness lemma followed by Borel–Cantelli. From disjointness, for any integer T>2/ϑ we will have
  
    (_ω,h-1(k) ≥ T ) ≤𝔼(ρ_ω,h-1(k))^T/T!≪ k^-2

  as k→ +∞ through 𝐏_1 ∪{[n^1-δ, n] : n ∈𝐏_1}; by the Borel–Cantelli lemma, this implies _ω,h-1(k) a.s.= O(1) as k varies throughout this domain.
  
  Now, just as in (<ref>), we have  
  
    ρ_ω,h(n)≥ n^1-δa.s.≪∑_k∈⋃𝒞_n≥ n^1-δ_ω,h-1(n-k)≥ n^1-δ.
  
  Since the restrictions on the RHS imply that the corresponding sum is occurring only over n-k ≥ n^1-δ, and also since _ω,h-1(k) is conveniently limited on the domain needed, it follows that
  
    ρ_ω,h(n)≥ n^1-δa.s.≪_1 | ⋃𝒞_n≥ n^1-δ|,

  which is obviously O(_ω,h(n)).
 

 It now only remains 𝐏_2 for us to deal with. We will, however, not work with it in its entirety; instead of breaking the aforementioned “log(n)/loglog(n) barrier”, we will work around it. Our method is inspired by the idea of r-star matchings described in Subsection 3.2 of Warnke <cit.>.
 
 First, to make the notation in the next lemma less charged, let
 
    L(n) := log(n)/loglog(n).

 Next, fix some > 0 and define
 
    𝐏_21 := { n∈𝐏_2 : A(n) ≤ n^1/(h-1) L(n)^-} and  𝐏_22 := 𝐏_2∖𝐏_21.

 We now use the same γ < (A) from before to take
 
    κ > 2^h-1/γ,

 and thus split ρ_ω,h into ρ_ω,h(n) = ρ_ω,h(n)≥ nL(n)^-κ + ρ_ω,h(n)♭_≥ nL(n)^-κ, with 𝒞_n≥ nL(n)^-κ and 𝒞_n♭_nL(n)^-κ being maxdisfams in each corresponding set. Our next lemma will show that, on the occasion of 𝐏_22 being finite, _ω,h will almost surely dominate ρ_ω,h in 𝐏_21, and thus in the whole 𝐏_2. The finiteness of 𝐏_22 is a key hypothesis for the second part of the proof.
 
 
  Let “≪_2” denote “≪ as n→ +∞ through 𝐏_2”. In the above notation, following Lemma <ref> (i.e. having M_1 > 1 sufficiently large), if 𝐏_22 is finite then in 𝒮_ the following holds:
  
    ρ_ω,h(n) a.s.≪_2_ω,h(n).

 
 
  Just like in Lemma <ref>, we divide the proof into two parts, the first of which shows that ρ_ω,h(n)♭_nL(n)^-κ does not contribute to the growth rate of ρ_ω,h(n). ∙ Part 1: Showing ρ_ω,h(n)♭_nL(n)^-κa.s.≪_2_ω,h(n)/L(n)^1/2.
  
  Recall that this quantity is counting those representations in which at least one member is less than nL(n)^-κ. From (<ref>) in Lemma <ref>,
  
    𝔼(ρ_ω,h(n)♭_nL(n)^-κ ) ≪ L(n)^-κγ/2^h-2𝔼(ρ_ω,h(n) ),

  From our choice of κ in (<ref>), the exponent of L(n) may be taken to be -2. Proceeding as in Part 1 from Lemma <ref>, we apply the disjointness lemma to estimate |⋃𝒞_n♭_nL(n)^-κ|. Keeping in mind that for k≥ 1 it holds k!>k^k e^-k, for any integer T>0 it then follows that
  
    ( _ω,h(n)♭_nL(n)^-κ≥ T⌈_ω,h(n)/L(n)^3/2⌉)    ≤( L(n)^-2𝔼(ρ_ω,h(n)) )^T⌈_ω,h(n)/L(n)^3/2⌉/(T⌈_ω,h(n)/L(n)^3/2⌉ )!
       ≤(e/T𝔼(ρ_ω,h(n))/_ω,h(n)L(n)^-2/L(n)^-3/2)^T⌈_ω,h(n)/L(n)^3/2⌉.

  By Lemma <ref> we have _ω,h(n) a.s.=Θ(𝔼(ρ_ω,h(n))). Hence, considering T large enough to cancel out the constant terms inside the parentheses, we have
  
    (e/T𝔼(ρ_ω,h(n))/_ω,h(n)L(n)^-2/L(n)^-3/2)^T⌈_ω,h(n)/L(n)^3/2⌉≪ L(n)^-1/2T⌈_ω,h(n)/L(n)^3/2⌉

  From Lemma <ref> and the definition of 𝐏_2, we know that 𝔼(ρ_ω,h(n)) ≫_2 n^α for some α >0. One can then deduce that the sum of this probabilities for n∈𝐏_2 will converge, and thus from the Borel–Cantelli lemma we may conclude that _ω,h(n)♭_nL(n)^-κa.s.≪_2 _ω,h(n)/L(n)^3/2.
  
  Finally, once again the reasoning behind (<ref>) may be used to deduce
  
    ρ_ω,h(n)♭_nL(n)^-κa.s.≪∑_k∈⋃𝒞_n♭_nL(n)^-κ_ω,h-1(n-k)♭_nL(n)^-κ,

  hence, since _ω,h-1(n) a.s.= O(L(n)) from Lemma <ref>, we arrive at
  
    ρ_ω,h(n)♭_nL(n)^-κ   a.s.≪|⋃𝒞_n♭_nL(n)^-κ| ·max_k∈⋃𝒞_n♭_nL(n)^-κ(_ω,h-1(n-k)♭_nL(n)^-κ) 
       a.s.≪_2 _ω,h(n)/L(n)^3/2· L(n) = _ω,h(n)/L(n)^1/2,

  as required. ∙ Part 2: If 𝐏_22 is finite, then ρ_ω,h(n)≥ nL(n)^-κa.s.≪_2_ω,h(n).
  
  First, just as in (<ref>), we have
  
    ρ_ω,h(n)≥ nL(n)^-κa.s.≪∑_k∈⋃𝒞_n≥ nL(n)^-κρ_ω,h-1(n-k)≥ nL(n)^-κ

  Given a big integer T≥ 1, split ⋃𝒞_n≥ nL(n)^-κ into the following two sets:
  
    𝒜^(T)_n   := { k∈⋃𝒞_n≥ nL(n)^-κ : ρ_ω,h-1(n-k)≥ nL(n)^-κ < T }
    ℬ^(T)_n   := { k∈⋃𝒞_n≥ nL(n)^-κ : ρ_ω,h-1(n-k)≥ nL(n)^-κ≥ T }

  Now, consider the set
  
    ℬ^(T)_n := ⋃_k∈ℬ^(T)_nER_h-1(n-k; ω),

  and the following maxdisfam-type counting function:  
  
    β^(T)(n) := max{|𝒟|: 𝒟⊆ℬ^(T)_n is a maximal disjoint family}

  From Lemma <ref> we know r_ω,h-1(n) a.s.= O(L(n)). Thus, letting 𝒟⊆ℬ^(T)_n be a maximal disjoint family, we have
  
    |ℬ^(T)_n|    ≤ T^-1· |ℬ^(T)_n| 
       ≤ T^-1·∑_k∈⋃𝒟ρ_ω,h-1(n-k) 
       a.s.≪β^(T)(n) · L(n).

  
  Knowing that A(n) ≤ n^1/(h-1)L(n)^- for all but finitely many n in 𝐏_2, and also that L(nL(n)^-κ)∼ L(n), in view of Lemma <ref> and Remark <ref> one can see that 𝔼(ρ_ω,h-1(n-k)≥ nL(n)^-κ) < η· L(n)^-(h-1) for all k when n is sufficiently large, where η > 0 is some constant not depending on . Thus, for such large n, since T! > T^T e^-T, by the disjointness lemma:
  
    (ρ_ω,h-1(n-k)≥ nL(n)^-κ≥ T )    ≤1/T!(η· L(n)^-(h-1))^T
       ≤(η· e/T)^T L(n)^-T(h-1).

  Keeping in mind again that ρ_ω,h-1(n)a.s.≪ L(n), we can estimate |ℬ^(T)_n| by
  
    |ℬ^(T)_n| ≤ J· L(n) ∑_k∈⋃𝒞_n≥ nL(n)^-κℐ_{ρ_ω,h-1(n-k)≥ nL(n)^-κ≥ T},

  for some constant J and all large n. Hence
  
    𝔼(|ℬ^(j)_n|) ≤ c_T· L(n)^1-T(h-1)·A(n)^h/n,

  where c_T := J· (η e/T)^T. With this, we can then apply the disjointness lemma again, this time to estimate β^(T)(n). We have
  
    (β^(T)(n) ≥⌈A(n)^h/n1/L(n)^3⌉)    ≤(c_T· L(n)^1-T(h-1)A(n)^h/n)^⌈A(n)^h/n1/L(n)^3⌉/⌈ A(n)^h/n · L(n)^-3⌉ !
       ≤ (c'_T · L(n))^(4-T(h-1)) ⌈A(n)^h/n1/L(n)^3⌉,

  where c'_T = c_T· e. Let T be large enough so that 4-T(h-1) < 0. Since the function in the exponent is at least n^α for some α>0 in 𝐏_2, it is not hard to see that the sum of the above probabilities for n∈𝐏_2 will converge. Therefore, from (<ref>) and the Borel–Cantelli lemma we deduce
  
    |ℬ^(T)_n| a.s.≪_2A(n)^h/n1/L(n)^2

  
  Going back to (<ref>), notice that from ρ_ω,h-1(n)a.s.≪ L(n) we get
  
    ∑_k∈ℬ^(T)_n_ω,h-1(n-k)≥ nL(n)^-κ   ≪ |ℬ^(T)_n|· L(n) 
       a.s.≪_2A(n)^h/n1/L(n),

  thus, since ⋃𝒞_n≥ nL(n)^-κ = 𝒜^(T)_n ∪ℬ^(T)_n,
  
    ∑_k∈⋃𝒞_n≥ nL(n)^-κ_ω,h-1(n-k)≥ nL(n)^-κa.s.≪_2 T· |𝒜^(T)_n| + A(n)^h/n1/L(n).

  Finally, we know |𝒜^(T)_n| = O(_ω,h(n)), thus, since from Lemma <ref> we have A(n)^h/n1/L(n)a.s.= o(_ω,h(n)), we conclude that ρ_ω,h(n)≥ nL(n)^-κa.s.≪_2_ω,h(n).
 
 
 It then follows immediately from (<ref>) in Lemma <ref> that, when 𝐏_22 is finite, r_ω,h(n) has a.s. the right rate of growth. Since  can be chosen arbitrarily small in the definition of 𝐏_21, the case ℓ=0 of the Main Theorem follows immediately.[More precisely, it follows from the fact that 𝒮_ is a non-empty probability space.] The next result shall deal with the further cases. We actually show something a little more general: if one could prove that r_ω,h(n) has a.s. the right growth order regardless of 𝐏_22 being finite or not, then, provided M_1,M_2 are large enough, r_ω,h+ℓ(n) will also concentrate around its mean for all ℓ≥ 0.
  
 
  Suppose there is M^†∈_+ such that, in the construction of , if M_1,M_2>M^† then in 𝒮_ the following holds:
  
    ρ_ω,h(n) a.s.≪_ω,h(n).

  Then there must be M^∈_+ such that M_1,M_2>M^ implies
  
    r_ω,h+ℓ(n) a.s.=Θ(A(n)^h+ℓ/n),  ∀ℓ≥ 0

 
 
  Let us start with the observation that if t_1,t_2≥ h are such that
  
    r_ω,t_1(n) a.s.=Θ(A(n)^t_1/n)  and  r_ω,t_2(n) a.s.=Θ(A(n)^t_2/n),

  then r_ω,t_1 +t_2(n) a.s.=Θ(A(n)^t_1+t_2/n). In fact, from the recursive formulas that can be derived from (<ref>), it follows that
  
    r_ω,t_1+t_2(n)    = ∑_k≤ n r_ω,t_1(k)r_ω,t_2(n-k) 
       a.s.≍∑_1≤ k≤ n-1A(k)^t_1/kA(n-k)^t_2/n-k
       = ∑_1≤ k≤ n/2A(k)^t_1/kA(n-k)^t_2/n-k + ∑_n/2 < k≤ n-1A(k)^t_1/kA(n-k)^t_2/n-k,

  which may be dealt with in the same way we treated (<ref>). Hence, for instance, if M_1,M_2>M^† then r_ω,th(n) a.s.=Θ(A(n)^th/n) for every t≥ 1, for the case t=1 follows from our hypothesis. With this in mind, to prove our theorem it is sufficient to show that r_ω,h+ℓ(n) a.s.=Θ(A(n)^h+ℓ/n) for 0≤ℓ < h, thus the remaining cases will follow from this observation.
  
  We know this is true for ℓ = 0, so we shall proceed by induction on ℓ. Assuming it is valid for some ℓ∈{0,1,…,h-2}, we will deduce the case ℓ+1. Start by noticing that
  
    r_ω,h+ℓ+1(n)    = ∑_k≤ n r_ω,h+ℓ(k)1_ω(n-k) 
       a.s.≍∑_1≤ k≤ nA(k)^h+ℓ/k1_ω(n-k) 
       = ∑_T<k≤ n-TA(k)^h+ℓ/k1_ω(n-k) + O(A(n)^h+ℓ/n),

  where T >0 is some arbitrarily large constant to be determined. The main term from (<ref>) is a sum of independent random variables bounded by max_T< k ≤ n-T{A(k)^h+ℓ/k}, therefore, letting
  
    X_n^(ℓ) := ∑_T<k≤ n-TA(k)^h+ℓ/k1_ω(n-k),

  we can apply the Chernoff bounds stated in Section <ref> to obtain:
  
    (|X_n^(ℓ)/𝔼(X_n^(ℓ)) -1| ≥1/2) ≤ 2e^-1/16𝔼(X_n^(ℓ)) (max_T< k ≤ n-TA(k)^h+ℓ/k)^-1

  Here enters our final step: to bound from below the absolute value of the exponent in (<ref>). Since we know from the Lemma <ref> that 𝔼(X_n^(ℓ)) = Θ(A(n)^h+ℓ+1/n), it suffices to show this exponent is at least 2log(n) + o(log(n)), then we may apply the Borel–Cantelli lemma and our theorem will follow.
  
  We start by bounding 𝔼(X_n^(ℓ)) from below. We have
  
    𝔼(X_n^(ℓ))    = ∑_T< k≤ n-TA(k)^h+ℓ/k𝔼(1_ω(n-k)) 
       ≥∑_n/2< k≤ n-TA(k)^h+ℓ/kA(n-k)/n-k+1
       ≥A(n/2)^h+ℓ/n∑_n/2< k≤ n-TA(n-k)/n-k+1

  Since  is OR_+, from Lemma <ref> we know there is some constant d>0 for which
  
    𝔼(X_n^(ℓ)) ≥ d A(n)A(n/2)^h+ℓ/n   (∀large n).

  Note that d does not depend on ℓ. More importantly, it also does not depend on T, as can be seen from (<ref>). Now it remains us to bound the “max” term from above. Firstly, since A(n) is non-decreasing, we have
  
    (max_T< k ≤ n-TA(k)^h+ℓ/k) ≤ A(n)^ℓ + 1·(max_T< k ≤ n-TA(k)^h-1/k).

  Since A(n) ≤ M_2^-1 n^1/(h-1) for large n, we may take T large enough so that
  
    (max_T< k ≤ n-TA(k)^h-1/k) < 2/M_2^h-1.

  
  In view of these estimates, we then have, for all large n,
  
    1/16𝔼(X_n^(ℓ))(max_T< k ≤ n-TA(k)^h+ℓ/k)^-1 > dM_2^h-1/32A(n/2)^ℓ/A(n)^ℓA(n/2)^h/n.

  There are two problematic terms in this lower bound: A(n/2)^ℓ/A(n)^ℓ & A(n/2)^h/n. For the first one we have to go back to our original OR_+ sequence . Since  is in particular OR, we know there exists some small ϑ > 0 for which C(n/2)/C(n) > ϑ for all large n. We also know from (<ref>) that for every > 0 there is some n_∈ such that, for all n > n_,
  
    C(n/2)    < (q_2 M_2 + ) A(n/2) 
    
       C(n)    > (q_1/M_1-) A(n),

  being q_1,q_2 the constants from the construction of . Putting these two equations together we get that
  
    A(n/2)/A(n) > q_1/q_2ϑ/M_1 M_2

  for all large n, thus, since ℓ ranges from 0 to h-2, we have the first problematic term bounded from below by (M_1 M_2)^-(h-2) (q_1/q_2ϑ)^h-2. The lower bound to the second term being considered, A(n/2)^h/n, comes from the fact that A(n) ≥ M_1 n^1/hlog(n)^1/h for large n. This implies
  
    A(n/2)^h/n≥M_1^h/2log(n) + O(1).

  Finally, (<ref>) then turns into
  
    dM_2^h-1/32A(n/2)^ℓ/A(n)^ℓA(n/2)^h/n > M_1^2 M_2 d/64(q_1/q_2ϑ)^h-2log(n) + O(1).

  
  In conclusion, having M_1,M_2 large enough so that
  
    M_1^2 M_2 > 2/d/64(q_1/q_2ϑ)^h-2

  will imply that (<ref>) is greater than 2log(n) + o(log(n)), so we may finally apply the Borel–Cantelli lemma in (<ref>) to obtain, in view of (<ref>),
  
    r_ω,h+ℓ+1(n) a.s.≍A(n)^h+ℓ+1/n,

  and this concludes our proof.
 
 
 Since the countable intersection of events with probability 1 also has probability 1, our Main Theorem follows from Lemma <ref>, Lemma <ref>, Theorem <ref> and the fact that 𝒮_ is non-empty.
  
 

§ FURTHER REMARKS
  
 
  On the conditions of Theorem <ref>, one can extend the result from Lemma <ref> by showing that
  
    h+ℓ2∑_k≤ n/2 r_ω,h+ℓ-2(n-2k)1_ω(k) a.s.≪ A(n)^ℓlog(n)/loglog(n),

  where the LHS bounds the number of non-exact (h+ℓ)-representations of n from above. Since we have r_ω,h+ℓ(n) a.s.≫ A(n)^ℓlog(n)^1+ℓ/h, it then follows that ρ_ω,h+ℓ(n) a.s.≍ r_ω,h+ℓ(n). This fact implies that the Main Theorem must also apply to exact representation functions. Originally, Erdős and Tetali <cit.> worked exclusively with ρ_ω,h.
 
 
 
  Given two sequences ,ℒ⊆, one may define their composition as ℒ[] := {ℓ_a_0,ℓ_a_1,ℓ_a_2,…}. Since |ℒ[]∩ [0,x]| = A(L(x)-1), we can define, in view of Step <ref> (Section <ref>), the space of ℒ-subsequences ℒ[𝒮_] as being ⟨𝒮,(α_n)_n ⟩ with 
  
    α_n := A(L(n)-1)/L(n)1_ℒ(n).

  This is just a more direct way of considering ℒ[ω] with ω∈𝒮_. Since  is OR_+, by the strong law of large numbers (Theorem <ref>) we have |ω∩ [0,x]| a.s.≍ A(L(x)); in addition, A(L(n))^h r_ℒ,h(n)/s_ℒ,h(n) is then the natural candidate for 𝔼(r_ω,h(n)).
 
  It is a natural question to ask which kinds of regularity assumptions do we need to impose on ℒ to be able to draw nice conclusions from ℒ[𝒮_]. In the case of Waring bases, for example, one can find subbases with similar properties to those described by our Main Theorem (see Vu <cit.>).
 







§ O-REGULARITY IN SEQUENCES

 In this appendix we motivate and characterize the concepts of OR, PI and OR_+ sequences. In spite of OR_+ sequences being an essential part of our proof, this section is only tangentially related to the main subject of our paper. In Propositions <ref>, <ref> and <ref> one finds equivalent definitions of OR, PI and OR_+ sequences, resp.. In Subsection <ref> we show an application of these concepts in the non-probabilistic context of additive bases, culminating on the sketch of an essentially elementary proof that primes that split completely in a given number field constitute a basis.
 
 
  Script letters , , 𝒞... denote sequences, which are infinite subset of . Roman capital letters A, B, C... denote the counting function of the sequence represented by the corresponding script letter, as in A(x) = |∩ [0,x]|. Lowercase roman letters a_0, a_1, a_2... (resp. b, c...) denote the elements of  (resp. , 𝒞...) in order, with a_0 (resp. b_0, c_0...) being its smallest element.
 



 §.§ Generalities: from A(x) to s_A,h(x)

 To motivate the study of certain regularity conditions on sequences, we need to state our goals clearly and get our priorities in order. First of all, one of the overarching goals in the study of additive bases is to characterize all bases. This is a problem with clear number-theoretical grounding, as in this direction we find the study of the classical bases: primes (Goldbach's conjecture), kth-powers (Waring's problem) and polygonal numbers (Cauchy–Fermat polygonal number theorem). A thorough overview of these topics is covered by Nathanson <cit.>.
 
 One, however, might argue that this is more naturally understood as a combinatorial problem, in whichever sense of the word. In this direction we find all the research springing from Sidon sequences, such as the Erdős–Turán conjecture for additive bases and the very Erdős–Tetali theorem, as well as Erdős–Fuchs-type estimates for representation functions. The classical reference for this more abstract treatment of sequences is Halberstam & Roth <cit.>, and the types of questions concerning us here are the ones outlined in the introduction of Chapter II, which we paraphrase:
 
 
  
  * What is the relationship between the asymptotic behaviour of the counting function of a sequence and its representation functions? 
  
  
  * Which properties of classical bases used to derive that these are in fact bases are actually applicable to wider classes of sequences? 
  
  
  * Which techniques employed in the study of classical bases are generalizable to a broader context? 
 

 In this appendix we only deal with the representation functions coming from the formal series (<ref>). Given a sequence ⊆, let n∈ and h≥ 2 an integer. The following recursive formulas can be immediately deduced:
 
    r_,h(n)    = ∑_k≤ n r_,h-ℓ(k)r_,ℓ(n-k) 
    
       s_,h(n)    = ∑_k≤ n r_,h-ℓ(k)s_,ℓ(n-k) = ∑_k≤ n s_,h-ℓ(k)r_,ℓ(n-k)

 For purposes of induction the case ℓ=1 is usually enough, and we denote r_,1(n) simply by 1_(n). Subsection <ref> tries to provide an answer for questions <ref> and <ref> via a framework which mixes both Schnirelmann's classical theory of sequences and Hardy–Littlewood's circle method, while the remainder is dedicated to exploring question <ref> and, from it, possible “classes of sequences” as mentioned in question <ref>.
 
 We start with the following lemma.
 
 
  For every sequence ⊆,
  
    A(x/2)^h ≤ s_,h(x) ≤ A(x)^h,   ∀ h≥ 1.

 
 
  The case h=1 is clear, hence we proceed by induction. By the recursive formulas in (<ref>),
  
    s_,h(n)    = ∑_k≤ n s_,h-1(k)1_(n-k) 
       ≤ s_,h-1(n)∑_k≤ n1_(n-k) 
       = s_,h-1(n)· A(n) ≤ A(n)^h,

  and
  
    s_,h(n)    ≥∑_n/2≤ k≤ n s_,h-1(k)1_(n-k) 
       ≥ s_,h-1(n/2)∑_n/2≤ k≤ n1_(n-k)
       = s_,h-1(n/2)· A(n/2) ≥ A(n/2)^h,

  as required.
 
 
 The reason why we initially focus on s_,h(n) instead of r_,h(n) is that, apart from being easier to deal with, it relates to r_,h(n) as being a sort of an “average” when one tries to employ the rough approximation 
 
    r_,h(n) ≈s_,h(n)/n+1.

 Much of what we propose comes from this intuition. To put more precisely, we seek for the conditions necessary for this intuition to make sense.



 §.§ OR sequences

 Let us introduce some bits of regular variation theory. An extensive treatment on this topic can be found in Bingham, Goldie & Teugels <cit.>. We will only use the theory from Chapters 1 and 2.

 Take f:[x_0,+∞)→_+ a positive real function. We say that f is
 
  
  * Slowly varying if f(λ x) ∼ f(x) for all λ >0;
  
  * Regularly varying if f(λ x) ∼λ^ρ f(x), for all λ>0 and some ρ∈;
  
  * O-regularly varying if f(λ x)≍ f(x) for all λ >0.
 

 The generality of these definitions lies on Karamata's characterization theorem,[Theorem 1.4.1, p. 17 of Bingham et al. <cit.>.] which states that if f(λ x) ∼ g(λ)f(x) with g(λ)∈(0,+∞) for all λ >0 and f is measurable, then f is regularly varying, i.e. there is ρ∈ such that g(λ)=λ^ρ. One can then promptly see how O-regular variation extends regular variation, and that is why we shall focus only on the former. We have mentioned in the introduction that a sequence ⊆ is OR whenever A(2x) = O(A(x)). This is equivalent to A being an O-regularly varying function. To be more precise, we define an OR sequence to be a sequence satisfying any of the equivalent conditions of the following proposition.
   
   Let ⊆ be a sequence. The following are equivalent:
 
  
  * A is O-regularly varying; 
  
  * A(2x) = O(A(x)); 
  
  * s_,h(x) = Θ(A(x)^h) for all h≥ 1; 
  
  * s_,h(2x) = O(s_,h(x)) for all or at least some h≥ 1.[By this we mean that if this holds for at least some h≥ 1, then it also holds for all h≥ 1. The same appears in items (iv) of Propositions <ref> and <ref>.] 
 
 
 
  (<ref>)(<ref>) is clear, and (<ref>)(<ref>) follows from Lemma <ref>.

  We show now that (<ref>)(<ref>). The case h=1 is trivial, so suppose h≥ 2. From Lemma <ref> it follows s_,h(x) ≤ A(x)^h ≤ s_,h(2x), therefore (<ref>) implies s_,h(x)≍ A(x)^h. By the recursive formulas (<ref>),
  
    A(2n)^h    ≪ s_,h(2n) 
       = ∑_k≤ 2n r_,h-1(k)s_,1(2n-k) 
       ≤∑_n<k≤ 2n r_,h-1(k)s_,1(2n-k)
       ≪ A(n)∑_n<k≤ 2n r_,h-1(k) 
       ≪ A(n)· s_,h-1(2n) ≪ A(n)· A(2n)^h-1,

  thus A(2x)≪ A(x).
  
  Finally, to show that (<ref>)(<ref>), note that A(x) is non-decreasing, thus (<ref>) is equivalent to having A(x)≍ A(2x). Hence, for all k∈,
  
    A(x) ≍ A(2^k x),

  which implies A(x) ≍ A(λ x) for all λ>0.
 

 Keeping Lemma <ref> in mind, one can then say that OR sequences are the most well-behaved sequences in terms of growth order, for it is sufficient to have A(x) in order to deduce the growth of s_,h.
  
 

 §.§ PI sequences
 
 In spite of that, just assuming  to be OR does not guarantee that a_n, when viewed as a function of n, is O-regularly varying. For this part we need another bit of regular variation theory. Still following Bingham et al. <cit.>, a positive real function f:[x_0,+∞)→_+ is said to be almost increasing when there is m>0 such that
 
    f(y) ≥ mf(x),   ∀ y≥ x≥ x_0.

 This is equivalent to saying that f(x) ≪inf_y≥ x f(y); almost decreasing functions can be defined in an analogous way, namely f(x) ≫sup_y≥ x f(y). Consider then the upper () and lower Matuszewska index () of f:
 
    (f)    := inf {γ∈: x^-γf(x)  is almost decreasing}, 
    (f)    := sup{γ∈: x^-γf(x)  is almost increasing}.

 This definition is given in view of the almost-monotonicity theorem.[Theorem 2.2.2, p. 72 of Bingham et al. <cit.>.] These indices are preserved under the asymptotic sign “≍”, and both are finite if and only if f is O-regularly varying.[Theorem 2.1.7, p. 71 of Bingham et al. <cit.>.] Functions with (f)>0 are said to have positive increase. Our motivation to study these indices comes from the next two lemmas. By “a_⌊·⌋” we shall be denoting the positive real function that takes x ↦ a_⌊ x⌋.
  
 
  For every sequence ⊆,
  
    (A) = 1/(a_⌊·⌋),     (A) = 1/(a_⌊·⌋);

  adopting the conventions “1/0 = +∞” and “1/(+∞) = 0”.
 
 
  We will only show that (A) = 1/(a_⌊·⌋). The argument for the other equation is entirely analogous, but with opposite inequalities. First, suppose (A)>0. Taking 0< γ < (A), there exists m>0 and some x_0 ∈_+ for which
  
    A(y)/y^γ≥ mA(x)/x^γ,   ∀ y≥ x≥ x_0.

  Hence, there must be some n_0 ∈ such that
  
    A(a_N)/a_N^γ≥ mA(a_n)/a_n^γ,   ∀ N≥ n≥ n_0;

  but since A(a_k) = k+1,
  
    a_N/(N+1)^1/γ≤1/m^1/γa_n/(n+1)^1/γ,   ∀ N≥ n≥ n_0;

  which means a_n/n^1/γ is almost decreasing, thus (a_⌊·⌋) ≥ 1/(A).
   
  To see that strict inequality cannot hold, we now take γ > (A). Note that now we are considering the possibility of having (A) = 0, for the next argument will also apply to the “0,+∞” case. For this chosen γ, the function A(x)/x^γ will not be almost increasing; that is, ∀>0,∀ M∈_+ there are y_ > x_≥ M such that
  
    A(y_)/y_^γ≤A(x_)/x_^γ.

  Letting n_:= A(x_) and N_ := A(y_)+1, the above inequality implies
  
    a_N_/(N_-1)^1/γ≥1/^1/γa_n_/n_^1/γ,

  which means a_n/n^1/γ cannot be almost decreasing, thus (a_⌊·⌋) < 1/γ. Hence equality must hold when (A) > 0, and (A) vanishes iff (a_⌊·⌋) = +∞.
 
 
 
  For every sequence ⊆ and every h≥ 1,
  
    (s_,h) = h·(A),     (s_,h) = h·(A).

 
 
  As in Lemma <ref>, we will only show the  case, for the other is analogous but with opposite inequalities and “+∞” instead of “0”. First, suppose (A)>0. Assume for the sake of contradiction that (s_,h) < h·(A). This means that there is (s_,h) < γ < h·(A) for which there is (x_k)_k∈, (y_k)_k∈ with y_k > x_k → +∞ as k→ +∞ such that
  
    s_,h(y_k)/s_,h(x_k) < 1/k(y_k/x_k)^γ.

  From Lemma <ref> we have
  
    A(y_k/2)^h/A(x_k)^h≤s_,h(y_k)/s_,h(x_k),

  but, since γ/h < (A), we conclude that y_k/2 < x_k for all large k. Hence
  
    s_,h(y_k)/s_,h(x_k) < 2^γ/k 0,

  a contradiction. Therefore (A) >0 implies (s_,h) ≥ h·(A).
  
  To see that strict inequality cannot hold, notice that A(x) is always an increasing function and A(x) ≤ x+1, hence 0≤(A)≤ 1. Take γ > h·(A), considering the possibility of having (A)=0. Similarly to the previous case, there is (x_k)_k∈, (y_k)_k∈ with y_k > x_k → +∞ as k→ +∞ for which
  
    A(y_k)/A(x_k) < 1/k^1/h(y_k/x_k)^γ/h.

  From Lemma <ref> we have
  
    s_,h(y_k)/s_,h(x_k/2)≤A(y_k)^h/A(x_k)^h,

  therefore we may deduce that (s_,h) ≤γ, as required.
 

 Thus, we define a PI sequence to be a sequence satisfying any of the following equivalent conditions.

  
  Let ⊆ be a sequence. The following are equivalent:
  
   
  * A has positive increase;lim inf_x→ +∞ 
   
  * a_2n = O(a_n);lim inf_x→ +∞ 
   
  * lim inf_x→ +∞ A(λ x)/A(x) > 1 for some λ >1; 
   
  * s_,h has positive increase for all or at least some h≥ 1.lim inf_x→ +∞ 
  
 
 
  (<ref>)(<ref>) follows from Lemma <ref> and the observation that a function is OR exactly when both its Matuszewska indices are finite, whereas (<ref>)(<ref>) follows from Lemma <ref>.  
  
  For (<ref>)(<ref>), notice that if ℳ_*(s_,h) > 0 for some h≥ 1, then for 0<γ<ℳ_*(s_,h) there is m>0 and x_0∈_+ such that, for all μ > 1,
  
    s_,h(μ x)/s_,h(x)≥ mμ^γ,   ∀ x≥ x_0.

  From Lemma <ref>, we know that
  
    A(μ x)^h/A(x/2)^h≥s_,h(μ x)/s_,h(x),

  hence
  
    A(2μ x)/A(x)≥ m^1/hμ^γ/h,   ∀ x≥ x_0/2.

  Thus, if μ is large enough, we have lim inf_x→ +∞ A(λ x)/A(x) > 1 for λ = 2μ.  
  
  Finally, to show (<ref>)(<ref>), assume that (<ref>) is false. Then for every > 0 there is a sequence (n_k)_k∈ with n_k = n_k() → +∞ as k→ +∞ for which
  
    a_⌊ (1+)n_k ⌋/a_n_k > k.

  This is the same as ka_n_k < a_⌊ (1+)n_k⌋. Since A(a_k) = k+1, it follows that
  
    A(ka_n_k)/A(n_k) < ⌊ (1+)n_k⌋ + 1/n_k + 1≤ 1+ + 1-/n_k +1;

  that is, for every real number λ > 1,
  
    A(λ n_k)/A(n_k) < 1 +  + o(1).

  as k→ +∞. Since for every > 0 there is such (n_k)_k∈, we conclude that for every λ > 1 it holds that lim inf_x→ +∞ A(λ x)/A(x) = 1, the negation of which is exactly item (<ref>).
 

 
  We describe shortly another motivation for PI sequences. In Section 7 of Stöhr <cit.> it is presented a list of criteria for non-bases, i.e. criteria which if a sequence ⊆ satisfies it, then it cannot be an additive basis. Among these, we highlight the following two:
  
   
  * Criterion #1: A(x) ≫̸x^ for every >0.
 
   
  * Criterion #2: lim sup_n→+∞ a_n+k/a_n = +∞ for some k≥ 1.
  
  When studying bases, it is then natural to focus only on sequences that avoid such criteria. A simple way of doing this would be to consider a condition that simultaneously avoid the above two statements. We may then consider the following questions:
  
   
  * What is the smallest f for which if A(n) ≫ f(n) then  does not satisfy criterion #2? 
 
   
  * What is the smallest f for which if lim sup_n→+∞ a_n+f(n)/a_n < +∞ then  does not satisfy criterion #1? 
  
 
  It is an exercise to show that, surprisingly enough, the answer to both questions is f(n) = Θ(n). For question (<ref>), it has been long known that a sequence ⊆ with A(n)=Θ(n) is an additive bases if and only if it satisfies the trivial requirement {0,1}⊆; this is indeed equivalent to a celebrated theorem by Schnirelmann (cf. Subsection <ref>).
 
  For question (<ref>), on the other hand, we may see that taking f(n) = Θ(n) implies item (<ref>) of Proposition <ref>, therefore we arrive back at PI sequences. This is a much more general condition than A(n) = Θ(n), but not all bases are necessarily PI (cf. Remark <ref>). An interesting line of research would be to identify which PI sequences are not bases.
 
 


 §.§ OR_+ sequences

 Finally we arrive at the central point of this appendix, which are sequences that are OR and PI at the same time. The reason behind considering these two conditions simultaneously comes from the following lemma, which is of central importance to this paper.

  
  Let f:[x_0,+∞)→_+ be a positive and locally integrable real function. The following are equivalent:
  
   
  * ∫_x_0^x f(t)/tdt = Θ(f(x));
   
  * 0<(f)≤(f)<+∞ ; ∫_α^x
   
  * f is O-regularly varying and has positive increase.
  
 
 
  Corollary 2.6.2, p. 96 of Bingham et al. <cit.>.
 

 We define an OR_+ sequence to be a sequence satisfying any of the equivalent conditions of the following proposition. The “+” in OR_+ is used to indicate the positivity of both Matuszewska indices.
 
  
  Let ⊆ be a sequence. The following are equivalent:
  
   
  * A is O-regularly varying and has positive increase;∫_1^x
   
  * ∫_1^x A(t)/tdt = Θ(A(x));
   
  * Both A(2x) = O(A(x)) and a_2n = O(a_n); ∫_1^x
   
  * ∫_1^x s_,h(t)/tdt = Θ(s_,h(x)) for all or at least some h≥ 1.
  
 
 
 The proof is just a straightforward combination of Proposition <ref>, Proposition <ref> and Lemma <ref>.
 
  
  Almost all common examples of additive bases are OR_+, such as the sequence of primes and sequences generated by polynomials, which even have regularly varying counting functions. Nonetheless, not all bases are common! For instance, the sequence
  
    𝒞 := [0,2^2^17] ∪(⋃_k≥ 17{2^2^k + t(k-1) : 0≤ t≤ 2^2^k}∪ [k· 2^2^k, 2^2^k+1] )

  is an example of a 2-basis, i.e. a basis of order 2, which is not PI. It is a relatively simple exercise to show that 2𝒞 =; to see that it is not PI, let n_k be such that c_n_k = 2^2^k. One can then show that n_k ∼ 2^2^k as k→ +∞, and thus c_2n_k/c_n_k = k-o(k), implying c_2n≠ O(c_n), which by the last lemma yields (C) = 0.
 
  On the other hand, the sequence 
  
    𝒟:= 𝒫_3∪{(2^2^k)^3+t : 0≤ t≤ (2^2^k)^2, k∈},

  where 𝒫_3 is the sequence of cubes, is not OR. It is a basis, for it contains 𝒫_3, which is well-known to be a 9-basis;[Wieferich–Kempner theorem (cf. Chapter 2 of Nathanson <cit.>).] to see it is not OR, let n_k = (2^2^k)^3. It is not hard to show that D(n_k) = o(n_k^2/3) as k→+∞, and then
  
    D(2n_k)/D(n_k)≥D(n_k + n_k^2/3)/D(n_k) = 1 + n_k^2/3/D(n_k),

  which diverges, implying D(2x) ≠ O(D(x)) and yielding (D) = +∞.
 
 


 §.§ An application to additive bases

 We finish this appendix by showing a relatively general version of what is sometimes loosely referred to in the literature as Schnirelmann's method. This refers to the common element between the elementary proofs of the sequence of primes with {0,1}[Schnirelmann-Goldbach theorem (cf. Chapter 7 of Nathanson <cit.>).] and the sequence of k-powers for all k≥ 1[Linnik's solution to Waring's problem (cf. Chapter 2 of Gel'fond & Linnik <cit.>).] constituting additive bases, with “elementary” meaning avoiding the complex analytical approach of the Hardy–Littlewood circle method. Although seemingly paradoxically, we believe that our idea is most concisely stated on the context of Vinogradov's form of the circle method. This part is of complete independent interest from the main subject of this paper, although some analogies can certainly be drawn as we shall point out. We now introduce the necessary concepts and notation.

 Fix ⊆ a sequence. For α∈/, let e(α) := e^2π i α. This is well-defined, for the value of e^2π i x for x∈ depends only on the fractional part of x. Consider then the following truncated generating-type function:
 
    𝒢^(n)_(α) := ∑_k ≤ n1_(k) e(kα).

 The functions {e(kα)}_k∈ form an orthonormal basis of L^2(/). From this orthonormality relation it follows, similarly to the formal series in (<ref>), 
 
    r_,h(n) = ∫_/𝒢^(n)_(α)^h e(-nα) dα.

 This is the starting point of Vinogradov's form of the circle method. Following mainly Chapters 5 and 8 of Nathanson <cit.>, we describe something which may be thought of as a general framework of the method. In both Waring's and Goldbach's ternary representation problem, a similar sort of ansatz is employed. The idea is to first consider the following “averaged” form of (<ref>): 
 
    𝒢^(n)_(α) := ∑_k ≤ nA(k)/k+1e(kα).

 This is similar to what we did in the construction of 𝒮_. Even though we are not necessarily requiring  to be OR_+, our goal is to show that the OR_+ condition fits naturally into this framework. Indeed, the next step is to approximate (<ref>) by 
 
    J_,h(n) := ∫_/𝒢^(n)_(α)^h e(-nα) dα,

 the so-called singular integral in the context of the usual circle method. Again, the orthonormality of {e(kα)}_k∈ implies that 
 
    J_,h(n) = ∑_k_1+… +k_h = n 
     k_1,…,k_h ≥ 0A(k_1)/k_1+1⋯A(k_h)/k_h + 1.

 When  is OR_+ one can show that J_,h(n) = Θ(A(n)^h/n) for all h≥ 1; this is exactly equivalent to Lemma <ref> in the main text, which we called the fundamental lemma. Finally, one aims to arrive at
 
    r_,h(n) = 𝔖_,h(n)J_,h(n) + error,

 where 𝔖_,h  is some arithmetic function and the error term is at most o(r_,h(n)). It is worth noting that every sequence ⊆ has such a representation for r_,h for every h≥ 1; i.e. we can always choose 𝔖_,h such that r_,h satisfies (<ref>), the trivial choice being 𝔖_,h(n) = r_,h(n)/J_,h(n) when the denominator is greater than 0, and 𝔖_,h(n) = 1 otherwise. Furthermore, by the way we defined the error term, it is always the case that
 
    𝔖_,h(n) ∼r_,h(n)/J_,h(n) as  n→ +∞ through  h.

 
 
  One way to interpret the conclusion after Theorem <ref> is that, for suitable , in 𝒮_ one has 𝔖_ω,h(n) a.s.=Θ(1).
 
 
 In both Waring's and Goldbach's problem, the idea of the method centers around finding a good description to 𝔖_,h (the so-called singular series) and controlling the error term. For that aim, one partitions / into major  and minor arcs for each sufficiently large n, usually denoted by 𝔐 = 𝔐(n) and 𝔪 = 𝔪(n) resp.. This partition is constructed in a way such that the integral in (<ref>) over the minor arcs constitutes part of the error term, while over the major arcs one seeks for a representation of r_,h as in (<ref>).
 
 The method as generally employed, however, draws heavily upon the number-theoretical properties of the sequences being considered, demonstrated by the use of Hua's lemma and Weyl's inequality in the case of Waring, and specific estimates of exponential sums over primes together with non-trivial estimates for the error term in Dirichlet's prime number theorem in the case of ternary Goldbach.
 
 If on the other hand we dispense with the precision achieved by the method in the case of highly number-theoretical sequences and focus only on the more relaxed property of just being an additive basis, we find that through OR_+ sequences it is possible to marry our description of the circle method with the elementary approach of Schnirelmann's method. To properly state this result, we only need two more things. The first one was already mentioned in Remark <ref>.
 
 plain
 *stSchnirelmann's theorem
 [Theorem 4, p. 8 of Halberstam & Roth <cit.>]
  If a sequence ⊆ contains {0,1} and satisfies A(x)=Θ(x), then  is an additive basis.
 
 
 The second one is the notion of stability in additive bases as described in Section 11.2 of Nathanson <cit.>. A sequence ⊆ is said to be a stable basis when  is a basis and every subsequence ⊆ with {0,1}⊆ and B(x)= Θ(A(x)) is also a basis. Without further ado:
 
 
  Let ⊆ be an OR_+ sequence with {0,1}⊆. If there is > 0 such that
  
    1/x∑_n≤ x𝔖_,h(n)^1+ = O(1)

  in (<ref>) for some h≥ 1, then  is a stable additive basis.
 
 
  From equations (<ref>) and (<ref>), the OR_+ condition implies that (<ref>) is equivalent to ∑_n ≤ x (n· r_,h(n)/A(n)^h)^1+ = O(x). Recall that  is, in particular, PI. By item (<ref>) of Proposition <ref>, there is λ > 1 and δ > 0 for which A(λ x)/A(x) > 1+δ for all large x, therefore
  
    A(x)^(1+)h/   < δ^-(1+)h/ (A(λ x) - A(x))^(1+)h/
       = δ^-(1+)h/(∑_x < n ≤λ x1_(n))^(1+)h/
       ≤δ^-(1+)h/(∑_hx < n ≤ hλ x r_,h(n) )^(1+)/.

  We know that the sequence  is also, in particular, OR. Therefore, by Hölder's inequality,[Theorem A in Section 42, p. 175 of Halmos <cit.>.] since 1 = 1/(1+) + /(1+),
  
    (   ∑_hx < n ≤ hλ x r_,h(n) )^(1+)/≤ |h∩ [hx, hλ x]| (∑_hx < n ≤ hλ x r_,h(n)^1+)^1/
       ≤ |h∩ [hx, hλ x]| (A(hλ x)^h/hx)^(1+)/(∑_hx < n ≤ hλ x(nr_,h(n)/A(n)^h)^1+)^1/
       ≪ |h∩ [hx, hλ x]| A(x)^(1+)h//x,

  hence |h∩ [0, x]| = Θ(x). By Schnirelmann's theorem, we deduce that  is a basis. To see that  is a stable basis, notice that if ⊆ then r_,h(n)≤ r_,h(n), thus B(x) ≍ A(x) implies 𝔖_,h(n) ≪𝔖_,h(n). Hence, repeating the same argument for , since {0,1}⊆, we apply Schnirelmann's theorem again.
 
 
 A similar version for asymptotic bases can be deduced from the appropriate variant of Schnirelmann's theorem. A sequence ⊆ is called an asymptotic basis when there is h≥ 2 such that ∖ h is finite, and from Theorem 11.6, p. 366 of Nathanson <cit.> one knows that, if A(n) = Θ(n), then not being contained in some non-trivial arithmetic progression ensures that  is an asymptotic basis.
 
 
  The connection with elementary methods comes from (<ref>), as both the proof of Schnirelmann–Goldbach's theorem and Linnik's elementary solution to Waring's problem is achieved by giving non-trivial upper bounds to r_,h(n)/s_,h(n) for some large enough h≥ 2.
  
  Following Chapter 11 of Nathanson <cit.>, let f∈[x] be an integer-valued polynomial (i.e. f(k)∈ when k∈) with positive leading coefficient. Define 𝒫_f := {f(n) : n∈}∩, the sequence generated by f. Since |𝒫_f∩[0,x]| = Θ(x^(f)), we know that 𝒫_f is OR_+. To show that it is a stable basis, one proves that there is h=h_f for which 𝔖_𝒫_f, h(n) = O(1).[Theorem 11.8, p. 370 of Nathanson <cit.>.]
 
  In the case of primes, the weak form of the Prime Number Theorem says that π(x) = Θ(x/log(x)), where π(x) := |ℙ∩[0,x]|, the sequence of primes; hence ℙ is OR_+. At the heart of Schnirelmann's proof that ℙ∪{0,1} forms a stable basis is the fact that 𝔖_ℙ,2(n) = O(∏_p| n(1+p^-1)),[Theorem 7.2, p. 186 of Nathanson <cit.>.] and one can then show that ℙ satisfies (<ref>) with = 1. For the reader familiar with algebraic number theory, one can take ℙ_K to be the set of primes that split completely in a number field K/. From Chebotarev's density theorem[Theorem 13.4 in Chapter VII, p. 545 of Neukirch <cit.>.] one has π_K(x) ≍π(x), where π_K(x) := |ℙ_K∩ [0,x]|, therefore ℙ_K∪{0,1} is also a basis.
 
 
 
  As an interesting side note, it is possible to show that when  is OR_+, we have ∑_n≤ x𝔖_,h(n) = O(x) for all h≥ 1, which is the same of having = 0 in (<ref>). Since this fact is not essential to Theorem <ref>, we chose to omit the proof, which is essentially a lengthy calculation.  
 


amsplain
