Paper deep dive
Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms
Ziyi Cai, Shuangping Li, Yiheng Shen, Kangning Wang, Peng Zhang
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Language generation in the limit is a theoretical framework for studying how a generator can learn to produce new valid strings from a stream of positive examples. In this model, an adversary chooses an unknown language from a countable family and enumerates its elements in an arbitrary order, while the generator must eventually output only elements of the language that have not yet appeared in the enumeration. Reliable generation is thus formalized through two eventual guarantees: validity and novelty relative to the observed data. To further quantify the breadth of the generator's outputs, Kleinberg and Wei (FOCS 2025, STOC 2026) introduced lower density as a measure of output coverage. Given an order representing the importance or relevance of possible outputs, lower density is the asymptotic lower bound, as $n$ grows, on the fraction of the first $n$ elements of the target language that the generator outputs before they appear in the data. Kleinberg and Wei showed that $1/2$ is the optimal lower-density guarantee for deterministic algorithms. We develop a simple and unified framework for obtaining optimal lower-density guarantees. We first give a deterministic algorithm that recovers the optimal guarantee of $1/2$ with a significantly simpler analysis than prior work. We then demonstrate the flexibility of our framework through two extensions. First, against an oblivious adversary, randomization raises the optimal guarantee to $1-1/e$. Second, for any finite collection of orders, the optimal deterministic and randomized guarantees can be achieved simultaneously with respect to every order, so accommodating multiple notions of importance or relevance entails no loss in the optimal guarantee.
Tags
Links
- Source: https://arxiv.org/abs/2608.01320v1
- Canonical: https://arxiv.org/abs/2608.01320v1
Trouble viewing inline? Open PDF directly →
Full Text
121,494 characters extracted from source content.
Expand or collapse full text
Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms Ziyi Cai Rutgers University zc417@cs.rutgers.edu Shuangping Li Yale University shuangping.li@yale.edu Yiheng Shen Meta yhshen@meta.com Kangning Wang Rutgers University kn.w@rutgers.edu Peng Zhang Rutgers University pz149@rutgers.edu Language generation in the limit is a theoretical framework for studying how a generator can learn to produce new valid strings from a stream of positive examples. In this model, an adversary chooses an unknown language from a countable family and enumerates its elements in an arbitrary order, while the generator must eventually output only elements of the language that have not yet appeared in the enumeration. Reliable generation is thus formalized through two eventual guarantees: validity and novelty relative to the observed data. To further quantify the breadth of the generator’s outputs, Kleinberg and Wei (FOCS 2025, STOC 2026) introduced lower density as a measure of output coverage. Given an order representing the importance or relevance of possible outputs, lower density is the asymptotic lower bound, as n grows, on the fraction of the first n elements of the target language that the generator outputs before they appear in the data. Kleinberg and Wei showed that 1/21/2 is the optimal lower-density guarantee for deterministic algorithms. We develop a simple and unified framework for obtaining optimal lower-density guarantees. We first give a deterministic algorithm that recovers the optimal guarantee of 1/21/2 with a significantly simpler analysis than prior work. We then demonstrate the flexibility of our framework through two extensions. First, against an oblivious adversary, randomization raises the optimal guarantee to 1−1/e1-1/e. Second, for any finite collection of orders, the optimal deterministic and randomized guarantees can be achieved simultaneously with respect to every order, so accommodating multiple notions of importance or relevance entails no loss in the optimal guarantee. Contents 1 Introduction 1.1 Our Results 1.2 Technical Overview 2 Preliminaries and Notation 2.1 Background for Auxiliary Tools 3 The Patient-Scope Algorithm 3.1 Recap of the KM Algorithm 3.2 Our Algorithm 3.3 Application: Language Generation from Partial Enumeration 4 Oblivious Adversaries and Randomized Algorithms 4.1 Warm-Up 4.2 The Randomized Patient-Scope Algorithm 4.3 Upper Bound 5 Language Generation under Multiple Orders 5.1 Warm-Up 5.2 The Paired Patient-Scope Algorithm 5.3 Combining Randomization and Multiple Orders Together References A Low-Crossing Partition B A Tight Randomized Algorithm under a Single Order C A Tight Deterministic Algorithm under Multiple Orders D A Tight Randomized Algorithm under Multiple Orders 1 Introduction Language generation has become one of the central computational tasks in modern AI. Contemporary generative models are expected not merely to recognize or classify text, but also to produce new, meaningful strings. At an abstract level, this task has a simple form: after observing examples from an unknown language, a generator should produce new elements of that language. Jon Kleinberg and Sendhil Mullainathan [KM24] recently proposed a theoretical model for this task, called language generation in the limit, inspired both by modern generative applications and by classical work on language identification [Gol67, Ang80]. In this model, an adversary chooses an unknown language K from a countable collection X of languages and enumerates its elements in an arbitrary order. After observing every data point in the enumeration, the algorithm aims to output a string that belongs to K and has not appeared in the observed data. An algorithm generates in the limit if, after some finite time, all of its outputs satisfy this requirement. Kleinberg and Mullainathan proved a striking positive result: every countable collection of languages admits an algorithm that generates in the limit. Subsequent work has developed learning-theoretic characterizations and stronger notions of generation [RLT25, CP25], studied the validity–breadth trade-off and notions of representative generation [KMV25, PRR25], and examined robustness and resource constraints, including noise, contamination, feedback, privacy, and bounded memory [R25, BPZ26, MVYZ25, MVYZ26, KMSV26]. We refer the reader to the actively maintained website [Meh26] for a comprehensive and up-to-date compilation of work on language generation in the limit. The possibility of successful generation in the limit is conceptually important, but it has a fundamental limitation: the definition guarantees eventual validity but not broad coverage of the target language. For example, if the true language is Z+Z^+, then a generator that outputs only previously unseen powers of 1010 can be valid forever, but it produces an extremely sparse subset of the language. Similarly, if the true language is English, a generator that only produces sentences of the form “this generator is good,” “this generator is very good,” “this generator is very very good,” and so on, can avoid invalid outputs while representing only a narrow sliver of English. In this sense, generation in the limit rules out eventual hallucination, but it does not by itself rule out mode collapse. To quantify this issue, Jon Kleinberg and Fan Wei [KW25] introduced density measures for language generation. Fix an ordering of the ground set of strings, interpreted as an order of importance, priority, or relevance. For a language K, let K[n]K[n] denote the first n elements of K under this order. If D⊆KD K is the set of valid strings that are output by a generator before appearing in the observed data, its lower density in K is lim infn→∞|D∩K[n]|n. _n→∞ |D∩ K[n] |n. Thus, lower density asks whether the generator covers a nonvanishing fraction of the important initial portions of the target language. This mirrors the standard role of density in additive combinatorics and number theory, where it measures how large a subset is within an ordered universe; prominent examples include Szemerédi’s theorem and the Green–Tao theorem [Sze75, GT08]. In the language-generation setting, the order specifies which strings should count as early or important. Kleinberg and Wei showed that positive density is achievable. Their first density result gave an algorithm that generates in the limit and guarantees lower density at least 1/81/8 [KW25]. They also observed a simple upper bound of 1/21/2 for deterministic algorithms: even if the algorithm knows the true language K, an adversary can enumerate half of every prefix before the algorithm has a chance to output those elements. In later work, they matched this upper bound and proved that 1/21/2 is the optimal deterministic lower-density guarantee [KW26b]. These results establish a sharp quantitative answer to the validity–breadth tradeoff in the deterministic single-order setting. Their proofs, however, are technically involved. 1.1 Our Results Table 1: Overview of lower-density guarantees. Single Order Multiple Orders Deterministic Lower Bound 1/21/2 1/21/2 ([KW26b], Theorems˜3.14 and 3.19) (Theorem˜5.2) Upper Bound 1/21/2 1/21/2 (Trivial) (Trivial) Randomized Lower Bound 1−1/e1-1/e 1−1/e1-1/e (Theorem˜4.2) (Theorem˜5.9) Upper Bound 1−1/e1-1/e 1−1/e1-1/e (Theorem˜4.4) (Theorem˜4.4) The upper bounds for the multiple-order settings follow from the corresponding single-order cases. [KW26b] and Theorem˜3.19 also establish the 1/21/2 lower bound in the more general model of partial enumeration. In this paper, we give a simple route to dense language generation. Our first main result is a simple deterministic algorithm with a short proof achieving the optimal 1/21/2 lower-density guarantee. We then use the same algorithmic framework for two extensions: a randomized algorithm achieving lower density 1−1/e1-1/e, and algorithms whose density guarantees hold simultaneously with respect to multiple orders. Our results are summarized in Table˜1. Dense language generation made simple (Section˜3). We propose Our Algorithm, which provides the same 1/21/2 lower-density guarantee (Theorem˜3.14) as the algorithm of [KW26b], but with a significantly simpler structure. As a quick demonstration of our new approach, we subsequently show that adding a preprocessing step before Our Algorithm suffices to recover another result of [KW26b]: there is an algorithm achieving 1/21/2 lower density under partial enumeration (Theorem˜3.19). The proof for our deterministic algorithm achieving 1/21/2 lower density has been formalized in Lean and is available in the repository pengzhang91/generation-in-the-limit-lib. The power of randomization (Section˜4 and Appendix˜B). If the adversary who chooses the order of enumerating the data points can observe and adapt to the algorithm’s past outputs, then clearly no algorithm can achieve a lower density better than 1/21/2. When the adversary is oblivious (non-adaptive), however, we show that randomization is helpful: a randomized algorithm can achieve lower density 1−1/e1-1/e (Theorem˜4.2); this ratio is tight for all algorithms (Theorem˜4.4). To streamline the presentation, the main body (Section˜4) presents only a family of algorithms, The Randomized Patient-Scope Algorithm, that achieve lower density arbitrarily close to 1−1/e1-1/e (Theorem˜4.3). The complete version with density exactly equal to 1−1/e1-1/e, A Tight Randomized Algorithm under a Single Order, is deferred to Appendix˜B. Having multiple orders does not hurt (Section˜5 and Appendices˜C and D). The order in the definition of lower density can represent the relative importance, priority, or relevance of different possible outputs. In many applications, however, there is no single universally accepted order: different users, evaluators, or downstream tasks may rank the same outputs differently. This motivates the requirement for an algorithm to perform well simultaneously with respect to multiple orders. We show that this additional requirement entails no loss in the optimal guarantee. When lower density is computed with respect to one of finitely many orders, we show that a deterministic algorithm achieves lower density 1/21/2 against an adaptive adversary (Theorem˜5.2), and that a randomized algorithm achieves lower density 1−1/e1-1/e against an oblivious adversary (Theorem˜5.9), simultaneously for each of these orders. Thus, the optimal ratios remain the same as in the corresponding single-order settings. For the deterministic result, the main body (Section˜5) presents only a family of algorithms, The Paired Patient-Scope Algorithm, that achieve lower density arbitrarily close to 1/21/2 (Theorem˜5.3); the full version, A Tight Deterministic Algorithm under Multiple Orders, is deferred to Appendix˜C. The randomized result is obtained by A Tight Randomized Algorithm under Multiple Orders and proved in Appendix˜D. In independent and concurrent work, Kleinberg and Wei [KW26a] study more general density notions motivated by spatial embeddings of strings. To put it loosely, their notion requires the generated set to be dense not only in initial prefixes but also throughout the embedding. To the best of our knowledge, neither their results nor ours subsume the other: their work strengthens and generalizes the density requirement, whereas ours establishes simultaneous density guarantees for multiple orders. 1.2 Technical Overview The technical overview below is organized around two ideas. We first explain the core argument behind our simpler deterministic algorithm, and then describe how this argument extends to the randomized and multiple-order settings. Bounding switch losses suffices. Our starting point is the original Recap of the KM Algorithm (Section˜3.1). Their algorithm maintains a descending chain (under inclusion) of languages that are consistent with all previous announcements, called the critical chain. It truncates this chain at a position that grows with the time step and treats the infimum of the resulting chain as its guess for the true language. We identify the obstruction to a 1/21/2 density guarantee: some announcements by the adversary are not contained in the current true language guess and therefore falsify it. We call these events, and also the announced integers themselves, switch losses. Each previously unannounced switch loss reduces the algorithm’s density. Roughly speaking, under the Recap of the KM Algorithm, the number of such switch losses in a prefix can be proportional to the prefix length, making the lower density asymptotically zero. Our algorithm, the Our Algorithm, improves the Recap of the KM Algorithm through a more careful truncation policy for the critical chain. The truncation point must still be allowed to grow, but our algorithm lets it grow slowly enough that, whenever a previously unannounced switch loss occurs, the algorithm must have kept the same true language guess for an exponentially long time and, during that period, announced many new integers smaller than the switch loss. As a result, in any prefix, the number of previously unannounced switch losses is logarithmic in the prefix length and therefore negligible. Block-based algorithms as a flexible meta-algorithm. A natural starting point for designing dense language-generation algorithms is a toy regime: a single finite language known to both parties. In this toy regime, one asks for algorithms whose density approaches the desired guarantee as the language size tends to infinity. This raises the following question: can such an asymptotically dense toy-regime algorithm be lifted to the original regime with countably many candidate languages, each countably infinite, and an unknown true language? We answer this question affirmatively through a block-based meta-algorithm. The algorithm adopts the same slow-growing truncation policy for the critical chain as the Our Algorithm, but its key additional feature is that it reserves disjoint blocks of integers on the fly. When it receives an announcement from the adversary, it first checks whether the announced integer lies in a previously reserved block. If so, it follows the corresponding dense strategy for the toy regime. Otherwise, it reserves a new block consisting of the smallest available integers in the current true language guess. Locally, the algorithm is dense inside each block. Globally, however, a prefix may cut through several blocks, leaving them incomplete; for these incomplete blocks, the within-block density guarantee need not apply. The key step in the analysis is therefore to bound the number of incomplete blocks. We do this by relating incomplete blocks to switch losses, whose number can be bounded using an argument analogous to the analysis of the Our Algorithm. We do not state the meta-algorithm explicitly as a standalone result. Instead, we demonstrate its flexibility by instantiating it directly in the randomized (Section˜4) and multiple-order (Section˜5) settings. In the toy regime above, both settings connect to well-studied problems. The Ranking algorithm [KVV90] for online bipartite matching yields a randomized algorithm that is asymptotically optimal, as the language size tends to infinity, against an oblivious adversary; low-crossing partitions [Wel88, CW89, Mat92] yield an algorithm that is asymptotically optimal, again as the language size tends to infinity, simultaneously under multiple orders. These observations guide the corresponding block-based algorithms in the full regime. Comparison with Kleinberg–Wei. Our work is most closely related to the density results of Kleinberg and Wei. Their first density paper shows that the zero-density behavior of the original Recap of the KM Algorithm can be avoided by giving an algorithm that achieves positive lower density for every true language and, in particular, a 1/81/8 lower-density guarantee [KW25, Theorem 6.12]. Their later paper proves the tight deterministic bound: lower density 1/21/2 under full enumeration, and more generally lower density at least α/2α/2 when the adversary enumerates an infinite subset K′⊆K K whose lower density in K is at least α [KW26b, Theorems 1.3 and 1.6]. Our deterministic results recover these tight bounds. In the full-enumeration setting, our patient-scope algorithm has a much simpler structure and admits a short, direct proof; the partial-enumeration result then follows by applying the same algorithm to the finite-intersection closure of the language family. Their first proof is based on a global analysis of the language family X. It starts with an index-based algorithm AaccA_acc that is valid in the limit and whose current indexed language is the true language K at infinitely many time steps [KW25, Theorem 3.1]. To turn this into a positive-density guarantee, they introduce a topology on the language family, relate limit points to infinite perfect towers, construct dynamic forests of candidate languages, and maintain fallback string lists with token budgets [KW25, Definition 4.3 and Claim 6.1]. The density proof then classifies missed integers as good or bad, decomposes the bad integers into maximal intervals, and, after discarding a finite prefix and at most one integer from each maximal bad interval of length at least two, injectively maps the remaining integers to earlier algorithm outputs [KW25, Lemma 6.16]. This machinery yields the 1/81/8 lower-density bound. The later Kleinberg–Wei paper treats the more general partial-enumeration model through a semi-index construction. In the partial-enumeration model, one cannot in general rely on eventually selecting a single candidate language Li⊆KL_i K. Kleinberg and Wei therefore replace index-based guesses by conjunction-based, or semi-index-based, hypotheses: finite intersections of candidate languages, and they show that this representation is equivalent to element-based generation for worst-case density purposes [KW26b, Lemma 2.3]. The semi-index and identified-intersection machinery addresses the greater generality of partial enumeration and is no longer needed when their argument is specialized to full enumeration. The proof first constructs a time-varying descending chain of such intersections and selects an “identified” intersection from this chain. This identified intersection is eventually valid and is full, in the sense of containing the adversary’s enumerated set K′K , at infinitely many time steps [KW26b, Theorem 2.4 and Lemma 2.5]. However, the gaps between these full times may be arbitrarily large, so this structural result alone does not yield a lower-density guarantee. To obtain density, they add a separate accounting layer. A warm-up argument uses aggressive guesses, a priority string list, and tokens; the tight proof then introduces pods, conceptual batches of reserved strings from which the algorithm still outputs only one string at a time. The main pod lemma maps each bad adversary string, after discarding a finite prefix, injectively to a previously created pod whose elements all precede it. This overcomes the double-counting bottleneck in the warm-up argument and yields the tight α/2α/2 bound [KW26b, Lemma 3.6 and Theorem 3.5]. As explained above, our proof takes a more direct and streamlined route. Rather than trying to recover density from a global structural analysis of the language family, or introducing priority lists, tokens, and pods to account for bad integers, we work directly within the original KM critical-chain framework. The key observation is that density loss has a local source: a switch loss. Our patient-scope algorithm changes only how the scope moves, waiting through long stable stretches before advancing and backtracking when the focus is falsified. The optimal 1/21/2 lower-density bound follows from a direct charging argument inside the original KM framework. At a broad conceptual level, the two proofs follow a similar high-level pattern: both build up a collection of strings while tracking a current hypothesis and then use those strings to account for losses that arise later. More specifically, we work directly with the original KM algorithm, whereas Kleinberg–Wei work with a variant AaccA_acc; the scope window in our proof plays a role analogous to the priority list in their warm-up argument and to the pods in their tight argument; the length of our scope window plays a role similar to their token parameter in the warm-up argument; and the injective assignment in their pod lemma is closely related to our switch-loss accounting. The algorithms implementing these ideas, however, are quite different. Kleinberg–Wei explicitly create pods of auxiliary unused strings and select outputs from the union of these pods, whereas our algorithm changes only the scope-update rule of the original KM algorithm. Thus, although the two proofs share a high-level charging philosophy and admit these natural point-by-point analogies, our treatment gives a much simpler algorithm and a more streamlined analysis in the full-enumeration setting. 2 Preliminaries and Notation Notation. For any non-negative integer n, let [n][n] denote the set 1,…,n \1,…,n \. For any set S of integers and any non-negative integer n, let S[n]S[n] denote the set of the smallest n elements of S. These notations extend naturally to multi-order settings. Let σ1,…,σk _1,…, _k be k permutations of the universe, which may be countably infinite. For each i∈[k]i∈[k] and non-negative integer n, define [n]iσi−1([n]),[n]_i _i^-1([n]), the set of the first n integers under the order σi _i. For any set S of integers, non-negative integer n, and index i∈[k]i∈[k], let S[n]iS[n]_i denote the set of the smallest n elements of S under the order σi _i. Language generation in the limit. Throughout this paper, a language is an infinite subset of Z+Z^+ (the positive integers). The KM model interprets language generation as a game between an adversary and an algorithm over ℒ=L1,L2,L3,…L= \L_1,L_2,L_3,… \, a countably infinite collection of languages. The collection ℒL is fully accessible to both parties. The adversary chooses a true language K=Li∗∈ℒK=L_i^* and keeps it secret. The game then starts and is played in rounds. At each round t∈Z+t ^+, the adversary announces an integer in K, and the algorithm then announces a positive integer. The adversary must enumerate the language K, i.e., every integer in K is announced by the adversary at some finite time step. When there is no further clarification, we assume that the algorithm is deterministic (based on both ℒL and the history of the game), and the adversary can be adaptive. Definition 2.1 (Validity). We say that an algorithm can generate in the limit the true language K if there exists an integer t0t_0 such that, in every round t≥t0t≥ t_0, the integer announced by the algorithm belongs to K and has not previously been announced by either party. The integer t0t_0 may depend on the adversary’s strategy. In the same work [KM24] that introduced the KM model, Kleinberg and Mullainathan propose an algorithm that can always achieve generation in the limit. We will discuss their algorithm further in Section˜3.1. Density of language generation. Let A be the set of positive integers first announced by the adversary (A for “attacker”), and let D be the set of positive integers first announced by the algorithm (D for “defender”). For any set S⊆Z+S ^+ and any integer n∈Z+n ^+, define μn(S)=|[n]∩S| _n(S)= |[n]∩ S |. Then μn(A)+μn(D∩K)=μn(K) _n(A)+ _n(D∩ K)= _n(K). Definition 2.2 (Lower Density). The lower density of an algorithm is defined by lim infn→∞μn(D∩K)μn(K). _n→∞ _n(D∩ K) _n(K). We aim to design an algorithm that, regardless of the adversary’s strategy, (1) generates in the limit the true language K, and (2) achieves a large lower density. A 1/21/2 upper bound for lower density is immediate, as the adversary can always announce the minimum integer in K that has not been announced by either party. Therefore, one may ask the following question: Is there an algorithm achieving the optimal lower density 1/21/2? This question was posed by [KW25], in which they show a 1/81/8 lower bound, and was first answered in the affirmative by [KW26b]. In this paper, we present a significantly simpler proof of this fact. 2.1 Background for Auxiliary Tools Online bipartite matching. The input to an online bipartite matching problem is a bipartite graph G=(U⊔V,E)G=(U V,E), where the vertices in U arrive one by one. For every vertex u∈Uu∈ U, let N(u)N(u) denote the set of neighbors of u in V. When a vertex u∈Uu∈ U arrives, its incident edges are revealed, and the algorithm must either match u to one of its currently unmatched neighbors or leave u unmatched. Each decision is irrevocable, and the goal is to maximize the size of the resulting matching. More specifically, we seek to maximize the competitive ratio: the worst-case ratio between the size of the matching produced by the algorithm and the size of the offline maximum matching in G. Algorithm 1 Ranking algorithm for online bipartite matching 1:Choose a uniformly random permutation π of the offline vertices V. 2:Initialize M←∅M← . 3:for each arriving vertex u∈Uu∈ U do 4: Let NuN_u be the set of unmatched neighbors of u in V. 5: if Nu∅N_u≠ then 6: Let v be the vertex in NuN_u with minimum rank under π. 7: M←M∪(u,v)M← M∪\(u,v)\. 8:return M. The online bipartite matching problem was introduced by Karp, Vazirani, and Vazirani [KVV90]. In the same work, they proposed the Ranking algorithm (Algorithm˜1) and proved that it achieves the optimal competitive ratio. The algorithm is further analyzed in the work of [KV07] and [GM08]. Theorem 2.3 ([KVV90, KV07, GM08, BM08, DJK13]). Let m=|U|m= |U | and f(m)=1−(1−1m+1)m.f(m)=1- (1- 1m+1 )^m. The Ranking algorithm achieves competitive ratio f(m)f(m), which converges to 1−1/e1-1/e as m→∞m→∞. This ratio is optimal for the online bipartite matching problem. Theorem 2.4 ([KVV90]). Let m=|U|m= |U |. No randomized algorithm can achieve an asymptotic competitive ratio better than 1−1e+om(1).1- 1e+o_m(1). Moreover, for every randomized algorithm on an m-by-m bipartite graph, there is a hard instance whose incidence matrix is upper triangular up to a permutation of the columns; equivalently, N(um)=∅N(u_m)= , N(ui+1)N(ui)N(u_i+1) N(u_i), and |N(ui)∖N(ui+1)|=1 |N(u_i) N(u_i+1) |=1. Low-crossing partitions. Let m be a positive integer, and let σ1,…,σk _1,…, _k be k permutations of [m][m]. We say that a set G is crossed by the cut (S,[m]∖S)(S,[m] S) if G∩S∅andG∖S∅.G∩ S≠ G S≠ . Given a partition of [m][m] into groups G1,G2,…,Gm/sG_1,G_2,…,G_m/s of equal size s, let ci(n)c_i(n) denote the number of groups crossed by the cut ([n]i,[m]∖[n]i)([n]_i,[m] [n]_i). We call ci(n)c_i(n) the crossing number. Theorem 2.5 (Low-Crossing Partition). For every pair of positive integers s,ms,m with sms m, and every collection of permutations σ1,…,σk _1,…, _k of [m][m], there is a balanced partition G1,G2,…,Gm/sG_1,G_2,…,G_m/s of [m][m] such that ci(n)≤4⋅(ms)1−1/kc_i(n)≤ 4· ( ms )^1-1/k for every i∈[k]i∈[k] and every n∈[m]n∈[m]. The theorem follows from the standard balanced k-d-tree construction introduced by [Ben75], after representing each element by its ranks in the k permutations. We include a proof in Appendix˜A for completeness. More generally, low-crossing partitions are a central ingredient in the theory of partition trees for geometric range searching; see, for example, [Wel88, CW89, Mat92]. 3 The Patient-Scope Algorithm 3.1 Recap of the KM Algorithm Our algorithm builds on the work of Kleinberg and Mullainathan [KM24]. We first introduce the terminology needed to present their algorithm. As the adversary reveals positive samples, we can discard any language that omits one of them. Definition 3.1 (Consistency). We call a language LiL_i consistent if LiL_i is a superset of all numbers that have been announced by the adversary so far. Intuitively, though not rigorously, “in the limit” every consistent language must be either the true language K or a proper superset of K. Moreover, the language K must be the minimum consistent language under inclusion. Thus, the main idea of the KM algorithm is to maintain a descending chain of consistent languages. We formally define this chain as follows. Definition 3.2 (Criticality). A language LiL_i is critical if the following two conditions hold: • LiL_i is consistent; • Li⊆LjL_i L_j for every consistent language LjL_j with a lower index j<ij<i. Remark 3.3. At every time step, the critical languages form a descending chain under inclusion. Moreover, after the adversary makes an announcement, the languages that cease to be critical form a suffix of the previous critical chain, while every newly critical language has a larger index than every language that remains critical. Lemma 3.4. The true language K is critical at all sufficiently large time steps. Proof of Lemma˜3.4. There are only finitely many languages with indices lower than that of the true language K. Any such language L that is not a superset of K becomes inconsistent once the adversary announces an integer in K∖LK L. Therefore, by definition, the true language K is critical after finitely many time steps. ∎ Since the critical chain can contain infinitely many languages, the algorithm truncates it at a sufficiently long position and uses the running minimum in the truncated chain as its current hypothesis. Definition 3.5 (Scope). The scope size is a positive integer s (used by the algorithms). The scope is L1,L2,…,Ls \L_1,L_2,…,L_s \. We denote sts_t to be the scope size at time step t. Definition 3.6 (Focus). The focus is the highest-indexed critical language F within the scope. The focus index is the index (in ℒL) of the focus. The Kleinberg–Mullainathan (KM) algorithm • In each time step t, perform the following operations. – Set the scope size st←ts_t← t. – Receive a new integer from the adversary, and update the sets of consistent and critical languages as well as the focus accordingly. – Output the smallest integer in the focus F that has not been announced by either party. (If no focus exists, output any number.) t Figure 1: After receiving the t-th integer from the adversary, some previously critical languages may become inconsistent. The algorithm then updates the chain of critical languages and changes the focus accordingly. By Lemma˜3.4, after finitely many steps the true language K will be in the critical chain. This implies that the focus F must be a subset of K. The validity of the KM algorithm follows immediately. Fact 3.7 ([KM24]). The Recap of the KM Algorithm can generate in the limit the true language K. Although the Recap of the KM Algorithm achieves language generation in the limit, it need not achieve any positive lower density. The following example gives an adversarial enumeration under which the algorithm’s lower density is 0. Example 3.8. Let Li=[i]∪x∈Z+:x≥2iL_i=[i]∪ \x ^+:x≥ 2^i \. The adversary chooses the true language K=L1=Z+K=L_1=Z^+. 1122334455667788991010111112121313141415151616K=L1K=L_1L2L_2L3L_3L4L_4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112233442244881616LiL_iLiL_i Figure 2: The example Li=[i]∪x∈Z+:x≥2iL_i=[i]∪ \x ^+:x≥ 2^i \ and K=L1=Z+K=L_1=Z^+. The t-th row represents the focus LtL_t at time step t; highlighted cells indicate the integers announced by the adversary and by the algorithm. Gray cells are integers not contained in the corresponding language. At time step t, the adversary announces t. After the first t rounds, LtL_t is consistent; moreover, every LjL_j with 2≤j<t2≤ j<t is inconsistent because j+1Ljj+1∉ L_j, while L1L_1 contains LtL_t. Hence, LtL_t is the focus of the KM algorithm. The algorithm therefore outputs 2t2^t, the smallest integer in LtL_t that has not yet been announced by either party. Thus, the integers first announced by the algorithm are precisely the powers of two with positive exponents, and the lower density is lim infn→∞μn(D∩K)μn(K)=lim infn→∞μn(D)μn(Z+)=lim infn→∞⌊log2n⌋n=0. _n→∞ _n(D∩ K) _n(K)= _n→∞ _n(D) _n(Z^+)= _n→∞ _2n n=0. Before introducing our algorithm, we first examine why the Recap of the KM Algorithm can have zero lower density, as illustrated by Example˜3.8. We use the following terminology in the analysis. Definition 3.9 (Switch Loss). A switch loss is an integer announced by the adversary that is not in the focus from the end of the previous time step. Equivalently, its announcement makes that focus inconsistent. Fact 3.10. Apart from switch losses, any integer first announced by the adversary lies in the focus from the end of the previous time step. Moreover, it is at least as large as the Recap of the KM Algorithm’s output in the previous time step. Proof of Fact˜3.10. If the adversary’s announcement is not a switch loss, then it does not make the focus from the previous time step inconsistent, even though the focus may change because sts_t increases. Thus, the announced integer lies in the previous focus. The claim then follows because the Recap of the KM Algorithm always outputs the smallest integer in the focus F that has not yet been announced by either party. ∎ Suppose the algorithm has run for sufficiently many steps so that all subsequent outputs lie in the true language K. By Fact˜3.10, within any prefix [n][n], and excluding switch losses, the number of integers first announced by the algorithm is at least the number of integers first announced by the adversary. Therefore, if a prefix [n][n] contains too many switch losses, say a number proportional to n, then the algorithm’s lower density can be small. In Example˜3.8, every integer that is not a power of two is a switch loss, and hence the lower density is zero. In fact, even if we replace st=ts_t=t by any monotone and unbounded function of t, such as ⌈logt⌉ t , one can still construct a similar example with zero lower density. 3.2 Our Algorithm The main idea of our algorithm is to let the scope grow very slowly, and even shrink when necessary, while still ensuring that it eventually contains the true language K. The patient-scope algorithm • Initially, at time t=0t=0, set the scope size s0=1s_0=1, and set the focus-change count τ=1τ=1. • In each time step t, perform the following operations. – Set the scope size st=st−1s_t=s_t-1. – Receive a new integer from the adversary, and update the sets of consistent and critical languages accordingly. – If the focus becomes inconsistent, run the Our Algorithm. – Otherwise, (if the focus is still consistent): * If the focus has not changed during the previous 2τ2^τ time steps, increase the scope size sts_t by one and update the focus accordingly. If the focus changes, increase the focus change count τ by one. – Announce the smallest integer in the focus F that has not been announced by either party. The backtracking algorithm • Increase the focus change count τ by one. • If there is no consistent language within the scope L1,L2,…,Lst\L_1,L_2,…,L_s_t\, increase the scope size sts_t until there is one.111Note that the true language K is always consistent, and so (by the proof of Lemma 3.11) this “if” is only true for a finite number of times. • Otherwise, find the highest-indexed language LiL_i within the scope that was critical before the announcement in this time step and is still critical after the announcement. If there is no such language LiL_i, choose LiL_i to be the lowest-indexed consistent language in the scope instead.222Again, note that because of the true language K, this “if” is only true for a finite number of times. Reduce the scope size sts_t to be equal to i, the index of LiL_i. t Figure 3: After receiving the t-th integer from the adversary, some previously critical languages may become inconsistent. Starting from the old focus, the algorithm backtracks along the old critical chain to find the highest-indexed consistent language. It then sets the scope to that index, thereby truncating the critical chain at that position. The dashed vertices indicate the part of the new critical chain that would remain if the scope were unchanged from the previous time step. The Our Algorithm differs from the Recap of the KM Algorithm in two main respects: 1. Instead of advancing the scope by one index at the beginning of each time step, the algorithm keeps the scope fixed until it has announced a sufficiently large number of integers. These announcements help reduce the density of switch losses. 2. When a switch loss occurs, the algorithm invokes the Our Algorithm, starting from the old focus and backtracking along the old critical chain to find the highest-indexed consistent language. It then truncates the critical chain at that position by setting the scope to that index, as illustrated in Fig.˜3. This is analogous to the Knuth–Morris–Pratt (KMP) algorithm [KMP77] for pattern matching: when a mismatch occurs, the KMP algorithm backtracks using the failure function until it finds the first compatible partial match. We first show that, although the scope of the Our Algorithm can shrink, this does not affect the algorithm’s validity. Lemma 3.11 (Validity). The Our Algorithm can generate in the limit the true language K. Proof. It is clear from its description that the Our Algorithm only announces numbers that have not been previously announced by either party. Recall (from Lemma˜3.4) that the true language K=Li∗K=L_i^* is critical at all sufficiently large time steps. After that point, the scope size cannot go from being at least i∗i^* to being strictly less than i∗i^*. Moreover, the scope size eventually becomes at least i∗i^*, since the scope size can only decrease when a language within the scope becomes inconsistent. When K is critical and within the scope, every number announced by the Our Algorithm is in K. ∎ Now we have established that the true language K is critical at all sufficiently large time steps, and that the Our Algorithm always announces a new integer in the true language K once K is critical and within the scope. To simplify our exposition, we map K to Z+Z^+ (with the ordering in K preserved) and assume K=Z+K=Z^+. Formally, we apply the partial map that sends each integer x∈Kx∈ K to its rank in K and is undefined outside K. We will use the following observation, analogous to Fact˜3.10. Fact 3.12. Apart from switch losses, any integer first announced by the adversary lies in the focus from the end of the previous time step. Moreover, it is at least as large as the output of the Our Algorithm in the previous time step. We omit the proof of Fact˜3.12, since it is analogous to the proof of Fact˜3.10. Next, we bound the number of previously unannounced switch losses (i.e. those first announced by the adversary) in every prefix. Lemma 3.13 (Charging Lemma). For any prefix [n][n], the number of previously unannounced switch losses in [n][n] that occur after the algorithm generates K is at most log2n _2n. Proof of Lemma˜3.13. LiL_iLjL_j2τ12 _1LiL_iℓ1 _1Li′L_i Lj′L_j 2τ22 _2Li′L_i ℓ2 _2 Figure 4: The charging argument for switch losses. If a switch loss ℓ moves the focus from LjL_j back to LiL_i, then before the focus could advance from LiL_i toward LjL_j, the algorithm must have spent 2τ′2^τ consecutive steps with focus LiL_i, where τ′τ is the value of τ during that period. The outputs from those steps are charged to ℓ . Consider a previously unannounced switch loss ℓ caused by a focus change from LjL_j to LiL_i, as shown in Fig.˜4. Then i<ji<j and Lj⊆Li⊆KL_j L_i K. During the progression of the focus from LiL_i to LjL_j, the Our Algorithm must have spent 2τ′2^τ consecutive time steps with focus LiL_i, where τ′τ is the value of τ during that period. Since integer ℓ is previously unannounced and ℓ∈Li ∈ L_i, the integers announced by the algorithm during these 2τ′2^τ steps are smaller than ℓ , and hence smaller than n. We charge the switch loss ℓ to these 2τ′2^τ integers. The focus-change counts τ are distinct across different switch losses, even though different switch losses may correspond to the same LiL_i. Moreover, the sets of integers charged to different switch losses are mutually disjoint. Therefore, if there are w switch losses ℓ1,ℓ2,…,ℓw _1, _2,…, _w in [n][n], with corresponding focus-change counts τ1,τ2,…,τw _1, _2,…, _w, then disjointness of the charged sets implies n≥2τ1+2τ2+⋯+2τw.n≥ 2 _1+2 _2+·s+2 _w. Since the τi _i are distinct positive integers, we have n≥21+⋯+2w≥2wn≥ 2^1+·s+2^w≥ 2^w. Taking logarithms of both sides completes the proof. ∎ We can now prove the lower-density guarantee for the algorithm. Theorem 3.14 (Lower Density). The Our Algorithm achieves the optimal lower density of 1/21/2. Proof of Theorem˜3.14. Fix an arbitrary prefix [n][n]. Consider any integer in [n][n] first announced by the adversary after the algorithm starts generating K (Lemma˜3.11 tells us this will happen after finitely many time steps). • If such an integer is a switch loss, then by Lemma˜3.13, the number of such integers is at most log2n _2n. • Otherwise, by Fact˜3.12, each such integer can be mapped to a unique smaller integer in K that was first announced by the algorithm. Let r be the number of integers first announced by the adversary before the algorithm starts generating K. These two cases imply that, for every integer n, μn(D∩K)≥μn(A)−r−log2n. _n(D∩ K)≥ _n(A)-r- _2n. It follows that lim infn→∞μn(D∩K)μn(K) _n→∞ _n(D∩ K) _n(K) =lim infn→∞2μn(D∩K)2n = _n→∞ 2 _n(D∩ K)2n ≥lim infn→∞μn(D∩K)+μn(A)−r−log2n2n ≥ _n→∞ _n(D∩ K)+ _n(A)-r- _2n2n =lim infn→∞μn(K)−r−log2n2n = _n→∞ _n(K)-r- _2n2n =lim infn→∞n−r−log2n2n = _n→∞ n-r- _2n2n =12.∎ = 12. Remark 3.15. The same argument extends to the setting in which the algorithm may announce t integers at each time step: it simply announces the t smallest unannounced integers in its focus. Apart from a vanishing fraction of switch losses, each integer first announced by the adversary can then be matched with t distinct smaller integers first announced by the algorithm, and these matches are disjoint. Thus, the algorithm achieves lower density t/(t+1)t/(t+1). Remark 3.16. Kleinberg and Wei [KW25] call an index-based generation algorithm accurate at a time step if its current language hypothesis equals the true language K, and accurate infinitely often if this occurs at infinitely many time steps. Viewing the focus as its current hypothesis, the Our Algorithm also has this property. Once K is permanently critical and within the scope, consider any time the focus moves from K to a proper subset, and let L be the first language after K on the resulting critical chain. Since the adversary enumerates all of K, it eventually announces an integer in K∖LK L, causing L and every later language on the chain to become inconsistent; the Our Algorithm then returns the focus to K. Thus, the focus either eventually remains equal to K or returns to K after every excursion, and in either case the algorithm is accurate infinitely often. 3.3 Application: Language Generation from Partial Enumeration In this section, we recover the optimal lower density under the partial enumeration setting, first proved in the work of [KW26b]. In this setting, the adversary chooses the true language K from the collection ℒL, together with an infinite subset K′⊆K K that need not belong to ℒL. The adversary keeps both sets secret and enumerates only the partial language K′K . The algorithm proceeds as before: at each time step, it receives an announcement from the adversary and responds with an integer that has not yet been announced by either party. We still seek to maximize the lower density of the algorithm, defined by lim infn→∞μn(D∩K)μn(K). _n→∞ _n(D∩ K) _n(K). Directly applying the Our Algorithm cannot achieve any positive lower density in the worst case. This is because the validity of the algorithm relies on the fact that the adversary will enumerate K, which need not hold in the partial enumeration setting; Example˜3.17 gives a counterexample. Example 3.17. Let L1L_1 be 2k−1k∈Z+∪4kk∈Z+ \2k-1 k ^+ \∪ \4k k ^+ \, and let LiL_i be 2kk≥i−1 \2k k≥ i-1 \ for every integer i>1i>1. The adversary chooses L2L_2, the set of all positive even integers, as the true language K, but enumerates only the multiples of 44. Since L1L_1 remains consistent and LiL1L_i L_1 for every integer i>1i>1, L1L_1 is the only critical language at every time step. Consequently, the Our Algorithm outputs only positive odd integers, which have zero density in the true language K. In fact, the algorithm does not even generate in the limit the true language K. We can fix this issue without significantly changing the Our Algorithm. Given ℒ=L1,L2,L3,…L= \L_1,L_2,L_3,… \, construct a new collection ℒ′=L1′,L2′,L1,2′,…L = \L_ \1 \ ,L_ \2 \ ,L_ \1,2 \ ,… \. Each index I for the new language is a subset of indices for the old language. We define LI′L_I using finite intersection: LI′ @i∈ILi.L_I @_i∈ IL_i. We write the set I as a 11-based indicator binary. For example, the language L5′L_5 , whose index is 101(2)101_(2) in binary, is the intersection of L1L_1 and L3L_3, namely L1,3L_ \1,3 \. Each constructed language is countable, since it is a finite intersection of countable sets. If some Li′L_i is finite, we can simply discard it; to simplify the exposition, assume that every Li′L_i is countably infinite. The constructed collection is countable because it is indexed by finite subsets of a countable set. The algorithm for the partial enumeration setting works as follows: given ℒL, it constructs the new collection ℒ′L as stated above, and then run the Our Algorithm on this new collection ℒ′L . We first show that the adapted algorithm generates the true language K in the limit. Lemma 3.18 (Validity). The Our Algorithm over ℒ′L generates the true language K in the limit. Proof of Lemma˜3.18. Let Li∗L_i^* be the true language K. It suffices to show that, after sufficiently many time steps, there is an index I with 2i∗−1≤I<2i∗2^i^*-1≤ I<2^i^* such that LI′L_I is always critical. Such indices are precisely those whose binary representation has i∗i^* as its highest nonzero bit, and hence LI′⊆Li∗=KL_I L_i^*=K. Consider the languages L1′,L2′,…,L2i∗−1′L_1 ,L_2 ,…,L_2^i^*-1 . Since L2i∗−1′=Li∗L_2^i^*-1 =L_i^* is always consistent, this finite block contains at least one critical language. Let LJ′L_J be a critical language with the highest index J among them. After finitely many steps, J will stop changing. Indeed, among L1′,L2′,…,L2i∗−1′L_1 ,L_2 ,…,L_2^i^*-1 , any language that is not a superset of K′K will become inconsistent after sufficiently many time steps, while the consistency of all other languages will remain unchanged thereafter. Once J no longer changes, if J=2i∗−1J=2^i^*-1, the lemma follows immediately. Otherwise, consider the languages LJ+1′,LJ+2′,…,LJ+2i∗−1′L_J+1 ,L_J+2 ,…,L_J+2^i^*-1 . At least one of them must be critical: the language LJ+2i∗−1′=LJ′∩Li∗L_J+2^i^*-1 =L_J ∩ L_i^* is consistent and contained in LJ′L_J . Applying the same argument, we obtain a language in this range that remains critical after sufficiently many time steps. Its index lies between 2i∗−12^i^*-1 and 2i∗−12^i^*-1. ∎ Theorem 3.19 (Lower Density from Partial Enumeration). If the adversary’s enumerated set K′K has lower density α in the true language K, then applying the Our Algorithm to ℒ′L achieves lower density α/2α/2. As in the full-enumeration setting, we map K to Z+Z^+ (with the ordering in K preserved) and assume K=Z+K=Z^+. Proof of Theorem˜3.19. Let r be the number of integers first announced by the adversary before the algorithm starts generating K. As in the proof of Theorem˜3.14, Facts˜3.12, 3.13 and 3.18 imply that, for every integer n, μn(D∩K)≥μn(A)−r−log2n. _n(D∩ K)≥ _n(A)-r- _2n. It follows that lim infn→∞μn(D∩K)μn(K) _n→∞ _n(D∩ K) _n(K) =lim infn→∞2μn(D∩K)2n = _n→∞ 2 _n(D∩ K)2n ≥lim infn→∞μn(D∩K)+μn(A)−r−log2n2n ≥ _n→∞ _n(D∩ K)+ _n(A)-r- _2n2n ≥lim infn→∞μn(K′)−r−log2n2n ≥ _n→∞ _n(K )-r- _2n2n (K′⊆(D∩K)⊔AK (D∩ K) A) =12lim infn→∞(μn(K′)n−r+log2n) = 12 _n→∞ ( _n(K )n- r+ _2nn ) =α2.∎ = α2. 4 Oblivious Adversaries and Randomized Algorithms In this section, we describe a randomized variant of Our Algorithm. Randomization is useful only if the adversary cannot react to the algorithm’s random choices: against an adaptive adversary, once the algorithm’s random choice at a step is realized, the adversary can choose an optimal response. We therefore assume that the adversary is oblivious: it fixes in advance a deterministic announcement order for the true language K, which remains unknown to the algorithm. Definition 4.1 (Lower Density of a Randomized Algorithm). The lower density of a randomized algorithm is lim infn→∞E[μn(D∩K)]μn(K). _n→∞ *E [ _n(D∩ K) ] _n(K). We show that, against a non-adaptive adversary, randomization improves the best achievable lower density. Theorem 4.2 (Lower Density of a Randomized Algorithm (Lower Bound)). There is a randomized algorithm that, against every non-adaptive adversary, achieves lower density 1−1/e≈0.631-1/e≈ 0.63. To streamline the presentation, we defer the proof of Theorem˜4.2 to Appendix˜B. In this section, we instead prove a slightly weaker statement that preserves the main idea of the algorithm. Theorem 4.3 (Lower Density of a Randomized Algorithm (Weaker Lower Bound)). For every positive integer m, there is a randomized algorithm that, against every non-adaptive adversary, achieves lower density (1−1m+1)⋅f(m+1), (1- 1m+1 )· f(m+1), where f(m)=1−(1−1m+1)m.f(m)=1- (1- 1m+1 )^m. This lower density tends to 1−1/e1-1/e as m→∞m→∞. We also provide a matching 1−1/e1-1/e upper bound in Section˜4.3. Theorem 4.4 (Lower Density of a Randomized Algorithm (Upper Bound)). No randomized algorithm can achieve lower density greater than 1−1/e1-1/e against every non-adaptive adversary. 4.1 Warm-Up We illustrate the idea with the single-language game ℒ=Z+L= \Z^+ \. The algorithm fixes an integer m, partitions Z+Z^+ into blocks of size m, namely [1,m],[m+1,2m],…[1,m],[m+1,2m],…, and associates each block with an independent uniformly random permutation of its elements. After the adversary announces a number, the algorithm identifies the corresponding block and announces the first unannounced element in that block’s permutation. Lemma 4.5. Within each block, the expected number of integers first announced by the algorithm is at least (m−1)⋅f(m)(m-1)· f(m) out of the m integers in the block, regardless of the adversary’s announcement order. Then by Lemma˜4.5 and linearity of expectation, the algorithm achieves lower density (1−1/m)⋅f(m)(1-1/m)· f(m). u1u_1u2u_2u3u_3u4u_4u5u_5u6u_6u7u_711223344556677 Figure 5: The online bipartite matching instance for m=7m=7, induced by the announcement order in which the adversary announces t at time step t. The online vertex utu_t represents time step t, and the offline vertices represent the integers in [m][m]. Since the integers 1,…,t1,…,t have already been announced by the adversary at time step t, the vertex utu_t is adjacent exactly to the remaining integers t+1,…,mt+1,…,m. Proof of Lemma˜4.5. We connect this problem to online bipartite matching as follows. Consider a bipartite graph G=(U⊔V,E)G=(U V,E), where V=[m]V=[m] represents the integers to be announced and U represents the m time steps. The vertices ut∈Uu_t∈ U arrive online, one at a time. Given the adversary’s predetermined announcement order, the vertex utu_t is connected to the m−tm-t integers that have not yet been announced by the adversary at time step t; see Fig.˜5 for the case m=7m=7. Each matched edge corresponds to an integer first announced by the algorithm at the associated time step. Under this correspondence, the algorithm’s announcements within a block are exactly the matches produced by the Ranking algorithm (Algorithm˜1) with the same random permutation. Note that the offline maximum matching has size m−1m-1, since one can always match utu_t to the adversary’s announcement at time step t+1t+1 when t<mt<m. By Theorem˜2.3, the expected size of the online matching produced by the Ranking algorithm, or equivalently the expected number of integers first announced by the algorithm, is (m−1)⋅f(m)(m-1)· f(m). ∎ In the Our Algorithm, the focus may change infinitely many times. We therefore adapt this toy idea by creating the blocks dynamically. 4.2 The Randomized Patient-Scope Algorithm We fix a positive integer m, called the block size. The algorithm maintains a family of pairwise disjoint blocks B1,B2,…,B_1,B_2,…, each of size m. Each block BrB_r is equipped with an independent uniformly random permutation πr _r. Definition 4.6 (Reserved). A number is called reserved if it belongs to one of the blocks BrB_r. Definition 4.7 (Available). A number is called available if it has not yet been announced by either party and has not been reserved by the algorithm. Let W denote the set of currently available numbers. The randomized patient-scope algorithm • Fix a block size m∈Z+m ^+. Let NB=0N_B=0 be the current number of blocks. • Initially, at time t=0t=0, set the scope size s0=1s_0=1, set the focus-change count τ=1τ=1, and create no blocks. • In each time step t, perform the following operations. – Set the scope size st=st−1s_t=s_t-1. – Receive a new integer from the adversary, and update the sets of consistent and critical languages accordingly. – If the focus becomes inconsistent, run the Our Algorithm. – Otherwise, if the focus is still consistent and the adversary has announced 2τ2^τ unreserved integers, increase the scope size by one and update the focus accordingly. If the focus changes, increase τ by one. – Let xtx_t be the adversary’s announced number in this step. * If xt∈Brx_t∈ B_r for some block BrB_r, then output the first number in the permutation πr _r that has not been announced by either party. If no such number exists, see the next step. * If xtx_t has not yet been reserved or xtx_t is the last unannounced number in its block BrB_r, then let BNB+1(W∩F)[m].B_N_B+1 (W∩ F)[m]. Namely, block BNB+1B_N_B+1 contains top m available elements in current focus F. Generate an independent uniformly random permutation πNB+1 _N_B+1 of BNB+1B_N_B+1, mark all elements of BNB+1B_N_B+1 as reserved, and output the first number of πNB+1 _N_B+1. Increase NBN_B by 11. We first show the validity of the The Randomized Patient-Scope Algorithm. Lemma 4.8 (Validity). The The Randomized Patient-Scope Algorithm can generate in the limit the true language K. Proof of Lemma˜4.8. As in the deterministic proof, the true language K=Li∗K=L_i^* is critical at all sufficiently large time steps by Lemma˜3.4, and from some point onward the scope size is always at least i∗i^*. Therefore, from some point onward, every focus is a subset of K. Every block created after that point is contained in the current focus, and hence is contained in K. Therefore, every future output taken from a block is in K. The only possible outputs outside K can come from blocks created before that point, but there are only finitely many such blocks and each has size m, so they can generate only finitely many outputs. Finally, by construction, every output is chosen among numbers that have not been previously announced by either party. This proves the lemma. ∎ As in the proof of Theorem˜3.14, we may now identify K with Z+Z^+ in an order-preserving way, and assume throughout the rest of this section that K=Z+K=Z^+, every future focus is a subset of K, and every future block is contained in K. Every reserved integer belongs to a unique block. Moreover, whenever the adversary announces an unreserved integer, the algorithm immediately reserves a new block. We associate that integer with the new block and call it the trigger of the block. We classify the relevant blocks into two types. Definition 4.9 (Complete Blocks). A block BrB_r is complete within n if Br⊆[n]B_r [n]. Otherwise, we call BrB_r incomplete within n. Each integer in [n][n] that was neither announced nor reserved before the algorithm starts generating K falls into one of the following two cases: 1. it belongs to a complete block BrB_r, or is the trigger of such a block; 2. it belongs to an incomplete block BrB_r, or is the trigger of such a block. The rest of the proof can be summarized as follows: (1) the algorithm obtains a constant fraction of the integers in the first case; and (2) the number of integers falling into the second case is negligible compared with n. Therefore, even if the algorithm gives up on all integers in the second case, it can still win a constant fraction of all integers. This argument highlights the analysis of not only the The Randomized Patient-Scope Algorithm, but also the other block-based algorithms in later sections. We first compute the algorithm’s density among integers in the first case. Lemma 4.10. For any positive integer n, the expected fraction of integers in the first case that are first announced by the algorithm is at least (1−1m+1)⋅f(m+1). (1- 1m+1 )· f(m+1). Proof of Lemma˜4.10. View each block BrB_r together with its trigger as a concatenated block of size m+1m+1. By Lemma˜4.5, the algorithm first announces, in expectation, at least m⋅f(m+1)m· f(m+1) of these m+1m+1 integers. Some triggers may be larger than n, and some blocks may have no trigger; nevertheless, treating every block as if its trigger existed and belonged to [n][n] can only decrease the algorithm’s fraction, since triggers are always first announced by the adversary. The result follows by linearity of expectation. ∎ Next, we count the number of blocks involved in the second case. Lemma 4.11. For any positive integer n, there are at most log2nm+1 _2 nm+1 blocks BrB_r that are incomplete within n and satisfy either Br∩[n]∅B_r∩[n]≠ or the trigger of BrB_r is at most n. Proof of Lemma˜4.11. Once an incomplete block within n has been reserved, during any subsequent interval with no switch loss, every newly reserved block, together with its trigger if it has one, lies above n. Hence, later newly reserved blocks are not counted by the lemma until a switch loss ℓ either is an unreserved integer at most n that triggers the new block, or makes the smallest integer in W∩FW∩ F at most n. Consider such a switch loss ℓ , caused by a focus change from LjL_j to LiL_i. Then i<ji<j and Lj⊆Li⊆KL_j L_i K. During the progression of the focus from LiL_i to LjL_j, the adversary must have announced 2τ′2^τ unreserved integers, so the The Randomized Patient-Scope Algorithm must have reserved 2τ′2^τ blocks. If the smallest integer in W∩FW∩ F after switching the focus back to LiL_i is at most n, then all these blocks lie entirely below that integer, and hence below n. If instead ℓ is an unreserved integer at most n, then all these blocks lie entirely below ℓ , and hence below n. We now use the same charging argument as in Lemma˜3.13: charge the switch loss ℓ to these 2τ′2^τ blocks. If there are w such switch losses ℓ1,ℓ2,…,ℓw _1, _2,…, _w with corresponding focus-change counts τ1,τ2,…,τw _1, _2,…, _w, then disjointness of the charged sets implies n≥(2τ1+2τ2+⋯+2τw)⋅m.n≥ (2 _1+2 _2+·s+2 _w )· m. Since the τi _i are distinct positive integers, we have n≥(21+⋯+2w)⋅m≥2w⋅mn≥ (2^1+·s+2^w )· m≥ 2^w· m. Taking logarithms gives w≤log2nmw≤ _2 nm. The first incomplete block contributes the additional 11. ∎ Finally, we can compute the lower density of the The Randomized Patient-Scope Algorithm. Proof of Theorem˜4.3. Fix an arbitrary prefix [n][n]. Consider the integers in [n][n] that have not yet been announced or reserved before the algorithm starts generating K; by Lemma˜4.8, this happens after finitely many time steps. 1. Among the integers in the first case, by Lemma˜4.10, the algorithm first announces at least a (1−1m+1)⋅f(m+1) (1- 1m+1 )· f(m+1) fraction of such integers in expectation. 2. Otherwise, by Lemma˜4.11, there are at most log2nm+1 _2 nm+1 incomplete blocks involved. Therefore, the number of such integers is at most (m+1)⋅(log2nm+1)(m+1)· ( _2 nm+1 ). Let r be the number of integers that has already been announced or reserved before the algorithm starts generating K. These two cases imply that, for every integer n, μn(D∩K)≥(1−1m+1)⋅f(m+1)⋅(n−r−(m+1)⋅(log2nm+1)). _n(D∩ K)≥ (1- 1m+1 )· f(m+1)· (n-r-(m+1)· ( _2 nm+1 ) ). Therefore, the algorithm’s lower density is at least lim infn→∞μn(D∩K)μn(K) _n→∞ _n(D∩ K) _n(K) ≥lim infn→∞(1−1m+1)⋅f(m+1)⋅(n−r−(m+1)⋅(log2nm+1))n ≥ _n→∞ (1- 1m+1 )· f(m+1)· (n-r-(m+1)· ( _2 nm+1 ) )n =(1−1m+1)⋅f(m+1).∎ = (1- 1m+1 )· f(m+1). 4.3 Upper Bound In this section, we present an example of a single-language game ℒ=Z+L= \Z^+ \ in which no randomized algorithm can have lower density greater than 1−1/e1-1/e. Partition Z+Z^+ into consecutive blocks B1,B2,…B_1,B_2,… of doubly exponentially increasing size, where block BiB_i has size 22i2^2^i. Let ni= @j=1i|Bj|n_i= @_j=1^i |B_j |. The adversary will enumerate Z+Z^+ block by block. Lemma 4.12. Let B be a block of size m, and suppose that a randomized algorithm has already announced o(m)o(m) integers before the adversary starts announcing any element of B. Then there is a permutation π of B such that, when the adversary announces the elements of B in the order π, the algorithm’s density in B is at most 1−1e+om(1).1- 1e+o_m(1). Using Lemma˜4.12, we can construct, for each randomized algorithm, a hard permutation of Z+Z^+. Proof of Theorem˜4.4 assuming Lemma˜4.12. Fix a randomized algorithm A. We construct the permutation inductively. Assume that we have computed the restriction of π to B1,…,Bi−1B_1,…,B_i-1. Consider the randomized algorithm obtained by feeding the adversary’s input on the first i−1i-1 blocks to A. Since the adversary takes ni−1n_i-1 time steps to enumerate the first i−1i-1 blocks, the algorithm can announce at most this many integers before the adversary starts enumerating BiB_i. Moreover, it holds that ni−1|Bi|→0as m→∞. n_i-1 |B_i |→ 0 m→∞. Hence, by Lemma˜4.12, there is a permutation πi _i of BiB_i such that the algorithm’s density in BiB_i is at most 1−1/e+o|Bi|(1)1-1/e+o_ |B_i |(1), and hence at most 1−1/e+oni(1)1-1/e+o_n_i(1). It follows that the algorithm’s density in the first i blocks is at most ni−1+E[|Bi∩D|]ni≤ni−1ni+E[|Bi∩D|]|Bi|≤ni−1ni+1−1e+oni(1)≤1−1e+oni(1). n_i-1+ *E [ |B_i∩ D | ]n_i≤ n_i-1n_i+ *E [ |B_i∩ D | ] |B_i |≤ n_i-1n_i+1- 1e+o_n_i(1)≤ 1- 1e+o_n_i(1). We then extend π to the first i blocks by appending πi _i. Given this construction, for infinitely many integers n1,n2,…n_1,n_2,…, we have E[μni(D∩K)]μni(K)≤ni−1+E[|Bi∩D|]ni≤1−1e+oni(1). *E [ _n_i(D∩ K) ] _n_i(K)≤ n_i-1+ *E [ |B_i∩ D | ]n_i≤ 1- 1e+o_n_i(1). Therefore, the lower density cannot be greater than 1−1/e1-1/e. ∎ Remark 4.13. Since the adversary’s announcement order π is constructed inductively, and later blocks are chosen after considering the algorithm’s behavior on earlier blocks, the strategy may appear to be adaptive. This is not the case: after the randomized algorithm A is fixed, the construction fixes a single order π by reasoning about the distribution of A, and this order does not depend on the realized random choices of A during any execution. Proof of Lemma˜4.12. Fix the randomized algorithm and the adversary’s input before the adversary starts announcing elements of B. Let P⊆BP B be the random set of elements of B that the algorithm has already announced. By assumption, |P|=o(m) |P |=o(m) for every realization. For every permutation σ of B, define an online bipartite matching instance Gσ=(U⊔B,E)G_σ=(U B,E) as follows. The online vertices are u1,…,umu_1,…,u_m, and utu_t is adjacent to the elements of B that appear after σt _t in the order σ. Equivalently, N(ut)=σt+1,σt+2,…,σm.N(u_t)=\ _t+1, _t+2,…, _m\. The given randomized algorithm induces a randomized online matching algorithm on these instances: when utu_t arrives, simulate the adversary announcing σt _t to the original algorithm; if the algorithm outputs an unmatched neighbor of utu_t, match utu_t to this vertex, and otherwise leave utu_t unmatched. Thus the number of elements of B first announced by the original algorithm during the block is exactly the size of the matching produced in GσG_σ. By Theorem˜2.4, there is an upper-triangular hard instance for this randomized matching algorithm on which the expected matching size is at most (1−1e+om(1))⋅m. (1- 1e+o_m(1) )· m. Since every such upper-triangular instance is GπG_π for some permutation π of B, this permutation satisfies E[|B∩D|]≤E[|P|]+(1−1e+om(1))⋅m≤(1−1e+om(1))⋅m. *E [ |B∩ D | ]≤ *E [ |P | ]+ (1- 1e+o_m(1) )· m≤ (1- 1e+o_m(1) )· m. Therefore, the algorithm’s density in B is at most 1−1/e+om(1)1-1/e+o_m(1) in expectation. ∎ Remark 4.14. If the algorithm is allowed to announce t integers at each time step, the same randomized strategy achieves optimal lower density t⋅(1−exp(−1/t))=1−O(1/t).t· (1- (-1/t) )=1-O(1/t). At each step, the algorithm outputs the first t currently unannounced integers according to the relevant block’s random permutation. The stated ratio follows from a differential-equation analysis analogous to that of the Ranking algorithm by [KVV90]. 5 Language Generation under Multiple Orders The previous definition of density depends on the order of the positive integers. In this section, we extend the language generation problem to a multi-order setting. Given k orders σ1,…,σk _1,…, _k, can any deterministic algorithm simultaneously achieve good lower densities for all k orders against any adaptive adversary? Formally, let σ1,…,σk _1,…, _k be permutations of Z+Z^+; that is, each σi:Z+→Z+ _i ^+ ^+ is a bijection. Let μi,n(S) [n]i∩S , _i,n(S) [n]_i∩ S , the number of integers in S that are among the first n elements in the order σi _i. Definition 5.1 (Lower Density under k Orders). The lower density of an algorithm under k orders σ1,…,σk _1,…, _k is mini∈[k]lim infn→∞μi,n(D∩K)μi,n(K). _i∈[k] _n→∞ _i,n(D∩ K) _i,n(K). An immediate upper bound is 1/21/2, since the optimal lower density under a single order is 1/21/2. In this section, we show that, surprisingly, having multiple orders does not decrease the best achievable lower density. Theorem 5.2 (Lower Density under k Orders). There is an algorithm that, against every adaptive adversary, achieves lower density 1/21/2. To streamline the presentation, we defer the proof of Theorem˜5.2 to Appendix˜C. In this section, we instead prove a slightly weaker statement that preserves the main idea of the algorithm. Theorem 5.3 (Lower Density under k Orders (Weaker Lower Bound)). For every positive integer m, there is an algorithm that, against every adaptive adversary, achieves lower density 12h(m), 12h(m), where h(m)=1−4⋅(km+1)1−1/k+1m.h(m)=1- 4·(km+1)^1-1/k+1m. This lower density tends to 1/21/2 as m→∞m→∞. 5.1 Warm-Up We illustrate the idea by restricting the game to a finite language L=[m]L=[m], where m is even. Apply Theorem˜2.5 to partition [m][m] into m/2m/2 pairs; see Fig.˜6 for example. Define P(x)P(x) to be the other integer in the pair containing x. The algorithm is simple: whenever the adversary announces an integer x, the algorithm replies with P(x)P(x), if it has not yet been announced. σ1 _1σ2 _2 Figure 6: An example of a low-crossing pairing for two orders σ1 _1 and σ2 _2. We now compute the density of each prefix [n]i[n]_i. For each pair in the partition of [m][m], exactly one of the two elements is first announced by the algorithm. Therefore, it suffices to count the number of pairs crossed by the cut ([n]i,[m]∖[n]i)([n]_i,[m] [n]_i), which is ci(n)≤4⋅(m2)1−1/k≤4⋅m1−1/kc_i(n)≤ 4· ( m2 )^1-1/k≤ 4· m^1-1/k by Theorem˜2.5. Hence, in any sufficiently large prefix (say, n>m/2n>m/2), the density of the algorithm is at least mini∈[k],n∈[m]∖[m/2]n−ci(n)2n≥12−4⋅m−1/k. _i∈[k],n∈[m] [m/2] \ n-c_i(n)2n \≥ 12-4· m^-1/k. As in the randomized algorithm, we need to handle focus changes, so we reserve blocks on the fly similarly. The The Randomized Patient-Scope Algorithm always reserves the smallest m numbers in the current focus that have not been announced by either party or reserved by the algorithm. With k orders, however, the algorithm must take all of these orders into account, which makes the situation more complicated. 5.2 The Paired Patient-Scope Algorithm As in the The Randomized Patient-Scope Algorithm, we fix a positive integer m, which serves as a block-size parameter. The algorithm maintains a family of pairwise disjoint blocks B1,B2,…B_1,B_2,…, each of size between m and km+1km+1. Each block BrB_r is partitioned into pairs (denoted by PrP_r) by applying Theorem˜2.5 to the orders induced by σ1,…,σk _1,…, _k on BrB_r. The paired patient-scope algorithm • Fix a block size m∈Z+m ^+. Let NB=0N_B=0 be the current number of blocks. • Initially, at time t=0t=0, set the scope size s0=1s_0=1, set the focus-change count τ=1τ=1, and create no blocks. • In each time step t, perform the following operations. – Set the scope size st=st−1s_t=s_t-1. – Receive a new integer from the adversary, and update the sets of consistent and critical languages accordingly. – If the focus becomes inconsistent, run the Our Algorithm. – Otherwise, if the focus F is still consistent and the adversary has announced 2τ2^τ unreserved elements, increase the scope size by one and update the focus accordingly. If the focus changes, increase τ by one. – Let xtx_t be the adversary’s announced number in this step. * If xt∈Brx_t∈ B_r for some block BrB_r, output Pr(xt)P_r(x_t). If Pr(xt)P_r(x_t) has already been announced, see the next step. * If xtx_t has not yet been reserved or Pr(xt)P_r(x_t) has already been announced, then let BNB+1 @i∈[k](W∩F)[m]i.B_N_B+1 @_i∈[k](W∩ F)[m]_i. Namely, block BNB+1B_N_B+1 contains top m available elements in current focus F under each order. If |BNB+1| |B_N_B+1 | is odd, we further add the smallest element in (W∩F)∖BNB+1(W∩ F) B_N_B+1 under σ1 _1 to BNB+1B_N_B+1. Partition BNB+1B_N_B+1 into pairs PNB+1P_N_B+1 by applying Theorem˜2.5 to the induced orders of σ1,…,σk _1,…, _k on BNB+1B_N_B+1. Mark all elements of BNB+1B_N_B+1 as reserved, output the first element of BNB+1B_N_B+1 under σ1 _1. Increase NBN_B by 11. We first show the validity of The Paired Patient-Scope Algorithm. Lemma 5.4 (Validity). The The Paired Patient-Scope Algorithm can generate in the limit the true language K. Proof of Lemma˜5.4. As in the deterministic proof, the true language K=Li∗K=L_i^* is critical at all sufficiently large time steps by Lemma˜3.4, and from some point onward the scope size is always at least i∗i^*. Therefore, from some point onward, every focus is a subset of K. Every block created after that point is contained in the current focus, and hence is contained in K. Therefore, every future output taken from a block is in K. The only possible outputs outside K can come from blocks created before that point, but there are only finitely many such blocks and each has size at most km+1km+1, so they can generate only finitely many outputs. Finally, by construction, every output is chosen among numbers that have not been previously announced by either party. This proves the lemma. ∎ As in the proofs of Theorems˜3.14 and 4.3, we may now identify K with Z+Z^+ and update each σi _i accordingly. Throughout the rest of this section, assume that K=Z+K=Z^+, every future focus is a subset of K, and every future block is contained in K. ididBrB_rBr+1B_r+1 id σi _iBr[m]iB_r[m]_iBr+1[m]iB_r+1[m]_i σi _iσi _i Figure 7: A schematic comparison under a fixed order σi _i during a stretch with no switch loss. In the The Randomized Patient-Scope Algorithm, whole blocks are monotone under id. In the The Paired Patient-Scope Algorithm, a block may also contain elements chosen from (W∩F)[m]j(W∩ F)[m]_j for jij≠ i, so the full blocks can interleave under σi _i; however, the heads B[m]iB[m]_i remain monotone. A natural first attempt is to classify, for each prefix [n]i[n]_i, the relevant blocks into complete and incomplete blocks within [n]i[n]_i, as in the proof of Theorem˜4.3. However, this approach no longer works under multiple orders. In the The Randomized Patient-Scope Algorithm, blocks created during a stretch with no switch loss are nested monotonically under the single order. In the The Paired Patient-Scope Algorithm, this is no longer literally true: a block may contain elements from (W∩F)[m]j(W∩ F)[m]_j with jij≠ i, which can create gaps under the order σi _i. To capture the monotone structure that remains, we isolate the first m elements of each block under a fixed order. For a block BrB_r, define its head under σi _i to be the set Br[m]iB_r[m]_i. During any consecutive interval with no switch loss, the heads of newly reserved blocks are strictly above the heads of older reserved blocks under σi _i (see Fig.˜7 for comparison). Definition 5.5 (Complete head within n). A block head Br[m]iB_r[m]_i is complete within n if Br[m]i⊆[n]i.B_r[m]_i [n]_i. Otherwise, we call the head Br[m]iB_r[m]_i incomplete within n. Each integer in [n]i[n]_i that was neither announced nor reserved before the algorithm starts generating K falls into one of the following two cases: 1. it belongs to a block BrB_r with a complete head Br[m]iB_r[m]_i, or is the trigger of such a block; 2. it belongs to a block BrB_r with an incomplete head Br[m]iB_r[m]_i, or is the trigger of such a block. We first compute the algorithm’s density among integers in the first case. Lemma 5.6. For any prefix [n]i[n]_i, the fraction of integers in the first case that are first announced by the algorithm is at least 12h(m) 12h(m) where h(m)=1−4⋅(km+1)1−1/k+1m.h(m)=1- 4·(km+1)^1-1/k+1m. Proof of Lemma˜5.6. Fix a prefix [n]i[n]_i. Each integer in the first case can be associated with a block BrB_r whose head Br[m]iB_r[m]_i is complete. It suffices to lower bound, for each such block, the fraction of associated integers that are first announced by the algorithm. By Theorem˜2.5, such a block BrB_r, whose size is at most km+1km+1, contributes at most 4⋅(km+12)1−1/k≤4⋅(km+1)1−1/k4· ( km+12 )^1-1/k≤ 4·(km+1)^1-1/k crossed pairs. If we exclude the integers in crossed pairs and the trigger, then the algorithm first announces half of the remaining integers. Since the head is complete, at least m integers in [n]i[n]_i are associated with BrB_r. Therefore, the algorithm’s density among the integers associated with BrB_r is at least 12⋅(1−4⋅(km+1)1−1/k+1m).∎ 12· (1- 4·(km+1)^1-1/k+1m ). Next, we count the number of blocks involved in the second case. Lemma 5.7. For any prefix [n]i[n]_i, there are at most log2nm+1 _2 nm+1 blocks BrB_r whose heads Br[m]iB_r[m]_i are incomplete within n and that satisfy either Br∩[n]i∅B_r∩[n]_i≠ or the trigger of BrB_r lies in [n]i[n]_i. Proof of Lemma˜5.7. Once a block with an incomplete head within n has been reserved, during any subsequent interval with no switch loss, every newly reserved block, together with its trigger if it has one, lies outside [n]i[n]_i. Hence, later newly reserved blocks are not counted by the lemma until a switch loss ℓ either is an unreserved integer in [n]i[n]_i that triggers the new block, or makes the smallest integer in W∩FW∩ F under σi _i lie in [n]i[n]_i. Consider such a switch loss ℓ , caused by a focus change from LqL_q to LpL_p. Then p<qp<q and Lq⊆Lp⊆KL_q L_p K. During the progression of the focus from LpL_p to LqL_q, the adversary must have announced 2τ′2^τ unreserved integers, so the The Paired Patient-Scope Algorithm must have reserved 2τ′2^τ blocks. If, after the switch back to LpL_p, the smallest integer in W∩FW∩ F under σi _i lies in [n]i[n]_i, then the heads of all these blocks lie before that element under σi _i, and hence lie entirely in [n]i[n]_i. If instead ℓ is an unreserved integer of [n]i[n]_i, then these heads lie before ℓ under σi _i, and hence lie entirely in [n]i[n]_i. We now use the same charging argument as in Lemmas˜3.13 and 4.11: charge the switch loss ℓ to these 2τ′2^τ heads. If there are w such switch losses ℓ1,ℓ2,…,ℓw _1, _2,…, _w with corresponding focus-change counts τ1,τ2,…,τw _1, _2,…, _w, then disjointness of the charged sets implies n≥(2τ1+2τ2+⋯+2τw)⋅m.n≥ (2 _1+2 _2+·s+2 _w )· m. Since the τi _i are distinct positive integers, we have n≥(21+⋯+2w)⋅m≥2w⋅mn≥ (2^1+·s+2^w )· m≥ 2^w· m. Taking logarithms gives w≤log2nmw≤ _2 nm. The first block with an incomplete head contributes the additional 11. ∎ Finally, we can compute the lower density of the The Paired Patient-Scope Algorithm. Proof of Theorem˜5.3. If h(m)≤0h(m)≤ 0, the statement is trivial. Thus assume h(m)>0h(m)>0. Fix an order index i and an arbitrary prefix [n]i[n]_i. Let r be the number of integers that have already been announced or reserved before the algorithm starts generating K; by Lemma˜5.4, this happens after finitely many time steps. 1. Among the integers in the first case, by Lemma˜5.6, the algorithm first announces at least a 12h(m) 12h(m) fraction of such integers. 2. Otherwise, by Lemma˜5.7, there are at most log2nm+1 _2 nm+1 blocks involved. Each such block has size at most km+1km+1 and has at most one trigger. Therefore, the number of such integers is at most (km+2)⋅(log2nm+1).(km+2)· ( _2 nm+1 ). These two cases imply that, for every order index i and every integer n, μi,n(D∩K)≥12h(m)⋅(n−r−(km+2)⋅(log2nm+1)). _i,n(D∩ K)≥ 12h(m)· (n-r-(km+2)· ( _2 nm+1 ) ). Therefore, the algorithm’s lower density under the k orders is at least mini∈[k]lim infn→∞μi,n(D∩K)μi,n(K) _i∈[k] _n→∞ _i,n(D∩ K) _i,n(K) ≥mini∈[k]lim infn→∞12h(m)⋅(n−r−(km+2)⋅(log2nm+1))n ≥ _i∈[k] _n→∞ 12h(m)· (n-r-(km+2)· ( _2 nm+1 ) )n =12h(m).∎ = 12h(m). 5.3 Combining Randomization and Multiple Orders Together So far, we have analyzed randomized algorithms against non-adaptive adversaries and deterministic algorithms against adaptive adversaries under multiple orders. The following result combines the settings and techniques from these two sections. Definition 5.8 (Lower Density of a Randomized Algorithm under k Orders). The lower density of a randomized algorithm under k orders σ1,…,σk _1,…, _k is mini∈[k]lim infn→∞E[μi,n(D∩K)]μi,n(K). _i∈[k] _n→∞ *E [ _i,n(D∩ K) ] _i,n(K). Theorem 5.9 (Lower Density of a Randomized Algorithm under k Orders). There is a randomized algorithm that, against every non-adaptive adversary, achieves lower density 1−1/e1-1/e under k orders. The proof introduces no new ideas; it combines the The Randomized Patient-Scope Algorithm with the The Paired Patient-Scope Algorithm. We defer the details to Appendix˜D. Acknowledgments. The authors used OpenAI’s GPT-5.5 to assist with generating new content for this paper, including drafting and revising portions of the exposition, creating TikZ code for figures, and filling in low-level proof details. GPT-5.5 also identified connections between our results and online bipartite matching and low-crossing partitions; these connections are included in this paper. In the authors’ view, these connections streamline the corresponding proofs and provide useful context, although the results also admit more direct, if perhaps less elegant, proofs that do not rely on them. All AI-assisted content was reviewed, edited, and verified by the authors, who take full responsibility for the paper’s contents. The authors would like to thank Moses Charikar, Chirag Pabbaraju, and Fan Wei for their helpful insights. P.Z. was partially supported by NSF Grant CCF-2238682. References [Ang80] Dana Angluin. Inductive inference of formal languages from positive data. Information and control, 45(2):117–135, 1980. [Ben75] Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509–517, 1975. [BM08] Benjamin E. Birnbaum and Claire Mathieu. On-line bipartite matching made simple. SIGACT News, 39(1):80–87, 2008. [BPZ26] Yannan Bai, Debmalya Panigrahi, and Ian Zhang. Language generation in the limit: Noise, loss, and feedback. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 794–816. SIAM, 2026. [CP25] Moses Charikar and Chirag Pabbaraju. Exploring facets of language generation in the limit. In Proceedings of the Thirty Eighth Annual Conference on Learning Theory (COLT), volume 291 of Proceedings of Machine Learning Research, pages 854–887. PMLR, 2025. [CW89] Bernard Chazelle and Emo Welzl. Quasi-optimal range searching in space of finite VC-dimension. Discret. Comput. Geom., 4:467–489, 1989. [DJK13] Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg. Randomized primal-dual analysis of RANKING for online bipartite matching. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 101–107. SIAM, 2013. [GM08] Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 982–991. SIAM, 2008. [Gol67] E. Mark Gold. Language identification in the limit. Information and control, 10(5):447–474, 1967. [GT08] Ben Green and Terence Tao. The primes contain arbitrarily long arithmetic progressions. Annals of mathematics, pages 481–547, 2008. [KM24] Jon M. Kleinberg and Sendhil Mullainathan. Language generation in the limit. In Annual Conference on Neural Information Processing Systems (NeurIPS), 2024. [KMP77] Donald E. Knuth, James H. Morris, and Vaughan R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323–350, 1977. [KMSV26] Jon M. Kleinberg, Anay Mehrotra, Amin Saberi, and Grigoris Velegkas. On language generation in the limit with bounded memory. CoRR, abs/2605.30324, 2026. [KMV25] Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. On the limits of language generation: Trade-offs between hallucination and mode-collapse. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 1732–1743. ACM, 2025. [KV07] Erik Krohn and Kasturi Varadarajan. Private communication reported by [GM08], 2007. [KVV90] Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352–358. ACM, 1990. [KW25] Jon M. Kleinberg and Fan Wei. Density measures for language generation. In Proceedings of the 66th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 620–658. IEEE, 2025. [KW26a] Jon M. Kleinberg and Fan Wei. Banach density of generated languages: Dichotomies in topology and dimension. CoRR, abs/2604.02385, 2026. [KW26b] Jon M. Kleinberg and Fan Wei. Language generation and identification from partial enumeration: Tight density bounds and topological characterizations. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC), pages 1684–1691. ACM, 2026. [Mat92] Jirí Matousek. Efficient partition trees. Discret. Comput. Geom., 8:315–334, 1992. [Meh26] Anay Mehrotra. Language generation in the limit. https://languagegeneration.github.io/, 2026. [MVYZ25] Anay Mehrotra, Grigoris Velegkas, Xifan Yu, and Felix Zhou. Language generation with infinite contamination. CoRR, abs/2511.07417, 2025. [MVYZ26] Anay Mehrotra, Grigoris Velegkas, Xifan Yu, and Felix Zhou. Differentially private language generation and identification in the limit. CoRR, abs/2604.08504, 2026. [PRR25] Charlotte Peale, Vinod Raman, and Omer Reingold. Representative language generation. In Proceedings of the Forty-second International Conference on Machine Learning (ICML), volume 267 of Proceedings of Machine Learning Research. PMLR / OpenReview.net, 2025. [RLT25] Vinod Raman, Jiaxun Li, and Ambuj Tewari. Generation through the lens of learning theory. In Proceedings of the Thirty Eighth Annual Conference on Learning Theory (COLT), volume 291 of Proceedings of Machine Learning Research, pages 4740–4776. PMLR, 2025. [R25] Ananth Raman and Vinod Raman. Generation from noisy examples. In Proceedings of the Forty-second International Conference on Machine Learning (ICML), volume 267 of Proceedings of Machine Learning Research. PMLR / OpenReview.net, 2025. [Sze75] Endre Szemerédi. On sets of integers containing no k elements in arithmetic progression. Acta Arith, 27(299-345):21, 1975. [Wel88] Emo Welzl. Partition trees for triangle counting and other range searching problems. In Proceedings of the Fourth Annual Symposium on Computational Geometry (SoCG), pages 23–33. ACM, 1988. Appendix A Low-Crossing Partition Proof of Theorem˜2.5. Let r=m/sr=m/s. We construct a binary partition tree. The root, at height 0, is the set [m][m]. Consider a vertex at height h associated with a set A of size psps. If p=1p=1, then this vertex is a leaf. Otherwise, let j∈[k]j∈[k] be the index with j≡h+1(modk)j≡ h+1 k. We split A into two sets A−A^- and A+A^+, where A−A^- consists of the first ⌊p/2⌋s p/2 s elements of A in the order σj _j, and A+=A∖A−A^+=A A^-. Thus |A+|=⌈p/2⌉s|A^+|= p/2 s. The leaves of the tree form a balanced partition of [m][m] into r groups of size s. It remains to bound the crossing number. Fix i∈[k]i∈[k] and n∈[m]n∈[m], and consider the cut ([n]i,[m]∖[n]i)([n]_i,[m] [n]_i). Let d=⌈log2r⌉d= _2r . Every root-to-leaf path has length at most d. At a level where the tree splits according to σi _i, a crossed vertex gives rise to at most one crossed child, because the two children are consecutive in the σi _i-order restricted to that vertex. At any other level, a crossed vertex gives rise to at most two crossed children. Among any d consecutive levels, at least ⌊d/k⌋ d/k levels split according to σi _i. Therefore, ci(n)≤2d−⌊d/k⌋≤2d(1−1/k)+1≤4r1−1/kc_i(n)≤ 2^d- d/k ≤ 2^d(1-1/k)+1≤ 4r^1-1/k where the last inequality uses d≤log2r+1d≤ _2r+1. This proves the theorem. ∎ Appendix B A Tight Randomized Algorithm under a Single Order In this section, we show how to adapt The Randomized Patient-Scope Algorithm to achieve the tight lower density 1−1/e1-1/e. The The Randomized Patient-Scope Algorithm uses a fixed block size m, leaving a gap between (1−1m+1)⋅f(m+1) (1- 1m+1 )· f(m+1) and 1−1/e1-1/e for any fixed m. To close this gap, we allow the block size to grow dynamically. Whenever we need to reserve a new block, we set its size to be the square root of the smallest integer in the current focus that has not yet been announced or reserved. This ensures that most blocks intersecting [n][n] are large, while preventing any incomplete block within [n][n] from becoming too large and affecting the algorithm’s density. The variable-block randomized patient-scope algorithm • Let NB=0N_B=0 be the current number of blocks. • Initially, at time t=0t=0, set the scope size s0=1s_0=1, set the focus-change count τ=1τ=1, and create no blocks. • In each time step t, perform the following operations. – Set the scope size st=st−1s_t=s_t-1. – Receive a new integer from the adversary, and update the sets of consistent and critical languages accordingly. – If the focus becomes inconsistent, run the Our Algorithm. – Otherwise, if the focus is still consistent and the adversary has announced 2τ2^τ unreserved integers, increase the scope size by one and update the focus accordingly. If the focus changes, increase τ by one. – Let xtx_t be the adversary’s announced number in this step. * If xt∈Brx_t∈ B_r for some block BrB_r, then output the first number in the permutation πr _r that has not been announced by either party. If no such number exists, see the next step. * If xtx_t has not yet been reserved or xtx_t is the last unannounced number in its block BrB_r, then let m be the smallest number in the current focus that has not yet been announced by either party or reserved by the algorithm. Let BNB+1(W∩F)[⌈m⌉].B_N_B+1 (W∩ F)[ m ]. Namely, block BNB+1B_N_B+1 contains top ⌈m⌉ m available elements in current focus F. Generate an independent uniformly random permutation πNB+1 _N_B+1 of BNB+1B_N_B+1, mark all elements of BNB+1B_N_B+1 as reserved, output the first number of πNB+1 _N_B+1, and increase NBN_B by 11. The following lemma is analogous to Lemma˜4.8, so we state it without proof. Lemma B.1 (Validity). The A Tight Randomized Algorithm under a Single Order can generate in the limit the true language K. As in the proof of Theorem˜4.3, we ignore the time steps before the algorithm starts to generate K and identify K with Z+Z^+ in an order-preserving way. We then classify each integer in [n][n] into two cases: 1. it belongs to a complete block BrB_r, or is the trigger of such a block; 2. it belongs to an incomplete block BrB_r, or is the trigger of such a block. We first count the number of blocks involved in the second case. Lemma B.2. For any positive integer n, there are at most log2n+1 _2n+1 blocks BrB_r that are incomplete within n and satisfy either Br∩[n]∅B_r∩[n]≠ or the trigger of BrB_r is at most n. Proof of Lemma˜B.2. As in the proof of Lemma˜4.11, after the first incomplete block, each later counted block corresponds to a unique switch loss ℓ : either ℓ is an unreserved integer at most n that triggers the new block, or the switch makes the smallest integer in W∩FW∩ F at most n. In both cases, we charge ℓ to 2τ′2^τ blocks reserved by the A Tight Randomized Algorithm under a Single Order that lie below n. If there are w such switch losses ℓ1,ℓ2,…,ℓw _1, _2,…, _w, with focus-change counts τ1,τ2,…,τw _1, _2,…, _w, then disjointness of the charged sets implies n≥2τ1+2τ2+⋯+2τw.n≥ 2 _1+2 _2+·s+2 _w. Since the τi _i are distinct positive integers, we have n≥21+⋯+2w≥2wn≥ 2^1+·s+2^w≥ 2^w. Taking logarithms gives w≤log2nw≤ _2n. The first incomplete block accounts for the additional 11. ∎ Next, we compute the algorithm’s density among integers in the first case. Lemma B.3. Fix any ε>0 >0. There is a constant CεC_ such that, for any positive integer n, if FnF_n is the number of integers in the first case, then the expected number of integers in the first case that are first announced by the algorithm is at least (1−1e−ε)⋅(Fn−Cε). (1- 1e- )·(F_n-C_ ). Proof of Lemma˜B.3. For a block BrB_r, let br=|Br|b_r=|B_r|. Define ϕ(b)=(1−1b+1)⋅f(b+1)=(1−1b+1)⋅(1−(1−1b+2)b+1).φ(b)= (1- 1b+1 )· f(b+1)= (1- 1b+1 )· (1- (1- 1b+2 )^b+1 ). Then ϕ(b)→1−1/eφ(b)→ 1-1/e as b→∞b→∞. Hence, there exists an integer B=B(ε)B=B( ) such that ϕ(b)≥1−1/e−εφ(b)≥ 1-1/e- for every b≥Bb≥ B. Consider any complete block BrB_r with size brb_r. As in the proof of Lemma˜4.10, view BrB_r together with its trigger as a concatenated block of size br+1b_r+1. By Lemma˜4.5, the algorithm first announces, in expectation, at least br⋅f(br+1)b_r· f(b_r+1) of these br+1b_r+1 integers. Some triggers may be larger than n, and some blocks may have no trigger; treating every block as if its trigger existed and belonged to [n][n] can only decrease the algorithm’s fraction, since triggers are always first announced by the adversary. Thus each complete block contributes, in expectation, at least a ϕ(br)φ(b_r) fraction of the corresponding integers in the first case. It remains to control the contribution of blocks with small brb_r. Let mrm_r be the smallest integer in W∩FW∩ F used when block BrB_r is created, so that br=⌈mr⌉b_r= m_r . The integers mrm_r are distinct. For a fixed b≥1b≥ 1, the condition ⌈mr⌉=b m_r =b is equivalent to (b−1)2<mr≤b2,(b-1)^2<m_r≤ b^2, so there are at most 2b−12b-1 blocks with br=b_r=b. Therefore, the number of integers in the first case connected to blocks with br<Bb_r<B is at most Cε:= @b=1B−1(b+1)(2b−1).C_ := @_b=1^B-1(b+1)(2b-1). All remaining integers in the first case come from blocks with br≥Bb_r≥ B, and hence contribute a fraction at least 1−1/e−ε1-1/e- in expectation. The result follows. ∎ Finally, we can compute the lower density of the A Tight Randomized Algorithm under a Single Order. Proof of Theorem˜4.2. Fix an arbitrary prefix [n][n]. Let r be the number of integers that have already been announced or reserved before the algorithm starts generating K; by Lemma˜B.1, this happens after finitely many time steps. By Lemma˜B.2, there are at most log2n+1 _2n+1 incomplete blocks involved in the second case. If such a block intersects [n][n], the integer mrm_r used to define its size is at most n, and thus each such block has size at most ⌈n⌉ n . Otherwise, the trigger is the only associated integer of this block that lies in [n][n]. Either way, such a block contributes at most ⌈n⌉+1 n +1 associated integers. Therefore, the number of integers in the second case is at most (⌈n⌉+1)⋅(log2n+1).( n +1)·( _2n+1). It follows that the number FnF_n of integers in the first case is at least n−r−(⌈n⌉+1)⋅(log2n+1).n-r-( n +1)·( _2n+1). Fix any ε>0 >0. By Lemma˜B.3, for the corresponding constant CεC_ , we have E[μn(D∩K)]≥(1−1e−ε)⋅(n−r−(⌈n⌉+1)⋅(log2n+1)−Cε). *E [ _n(D∩ K) ]≥ (1- 1e- )· (n-r-( n +1)·( _2n+1)-C_ ). Thus the algorithm’s lower density is at least lim infn→∞E[μn(D∩K)]μn(K) _n→∞ *E [ _n(D∩ K) ] _n(K) ≥lim infn→∞(1−1e−ε)⋅n−r−(⌈n⌉+1)⋅(log2n+1)−Cεn ≥ _n→∞ (1- 1e- )· n-r-( n +1)·( _2n+1)-C_ n =1−1e−ε. =1- 1e- . Since ε>0 >0 was arbitrary, the lower density is at least 1−1/e1-1/e. ∎ Appendix C A Tight Deterministic Algorithm under Multiple Orders In this section, we adapt the The Paired Patient-Scope Algorithm to achieve the tight lower density 1/21/2. The idea is the same as in the A Tight Randomized Algorithm under a Single Order: choose the block size dynamically, according to the smallest available rank in the current focus. For a nonempty set S of integers and an order index i∈[k]i∈[k], let ρi(S)minn:S∩[n]i∅, _i(S) \n:S∩[n]_i≠ \, so that ρi(S) _i(S) is the smallest rank of an element of S under order σi _i. The variable-block paired patient-scope algorithm • Let NB=0N_B=0 be the current number of blocks. • Initially, at time t=0t=0, set the scope size s0=1s_0=1, set the focus-change count τ=1τ=1, and create no blocks. • In each time step t, perform the following operations. – Set the scope size st=st−1s_t=s_t-1. – Receive a new integer from the adversary, and update the sets of consistent and critical languages accordingly. – If the focus becomes inconsistent, run the Our Algorithm. – Otherwise, if the focus F is still consistent and the adversary has announced 2τ2^τ unreserved elements, increase the scope size by one and update the focus accordingly. If the focus changes, increase τ by one. – Let xtx_t be the adversary’s announced number in this step. * If xt∈Brx_t∈ B_r for some block BrB_r, output Pr(xt)P_r(x_t). If Pr(xt)P_r(x_t) has already been announced, see the next step. * If xtx_t has not yet been reserved or Pr(xt)P_r(x_t) has already been announced, then set mmini∈[k]ρi(W∩F).m _i∈[k] _i(W∩ F). Define BNB+1 @i∈[k](W∩F)[⌈m⌉]i.B_N_B+1 @_i∈[k](W∩ F)[ m ]_i. Namely, block BNB+1B_N_B+1 contains top ⌈m⌉ m available elements in the current focus F under each order. If |BNB+1| |B_N_B+1 | is odd, we further add the smallest element in (W∩F)∖BNB+1(W∩ F) B_N_B+1 under σ1 _1 to BNB+1B_N_B+1. Partition BNB+1B_N_B+1 into pairs PNB+1P_N_B+1 by applying Theorem˜2.5 to the induced orders of σ1,…,σk _1,…, _k on BNB+1B_N_B+1. Mark all elements of BNB+1B_N_B+1 as reserved, output the first element of BNB+1B_N_B+1 under σ1 _1. Increase NBN_B by 11. The following lemma is analogous to Lemma˜5.4, so we state it without proof. Lemma C.1 (Validity). The A Tight Deterministic Algorithm under Multiple Orders can generate in the limit the true language K. As in the proof of Theorem˜5.3, we may ignore the time steps before the algorithm starts generating K, identify K with Z+Z^+, and update each σi _i accordingly. For a block BrB_r, let mrm_r be the value of m when BrB_r is created, and let br=⌈mr⌉b_r= m_r . Define its head under σi _i to be the set Br[br]iB_r[b_r]_i. During any consecutive interval with no switch loss, the heads of newly reserved blocks are strictly above the heads of older reserved blocks under σi _i. Fix a prefix [n]i[n]_i. A head Br[br]iB_r[b_r]_i is complete within n if Br[br]i⊆[n]iB_r[b_r]_i [n]_i; otherwise it is incomplete within n. Each integer in [n]i[n]_i that was neither announced nor reserved before the algorithm starts generating K falls into one of the following two cases: 1. it belongs to a block BrB_r with a complete head Br[br]iB_r[b_r]_i, or is the trigger of such a block; 2. it belongs to a block BrB_r with an incomplete head Br[br]iB_r[b_r]_i, or is the trigger of such a block. We first count the number of blocks involved in the second case. Lemma C.2. For any prefix [n]i[n]_i, there are at most log2n+1 _2n+1 blocks BrB_r whose heads Br[br]iB_r[b_r]_i are incomplete within n and that satisfy either Br∩[n]i∅B_r∩[n]_i≠ or the trigger of BrB_r lies in [n]i[n]_i. Proof of Lemma˜C.2. As in the proof of Lemma˜5.7, after the first block with an incomplete head, each later counted block corresponds to a unique switch loss ℓ : either ℓ is an unreserved element of [n]i[n]_i that triggers the new block, or the switch makes the first element of W∩FW∩ F under σi _i lie in [n]i[n]_i. In both cases, we charge ℓ to 2τ′2^τ heads reserved by the A Tight Deterministic Algorithm under Multiple Orders that lie in [n]i[n]_i. If there are w such switch losses ℓ1,ℓ2,…,ℓw _1, _2,…, _w with corresponding focus-change counts τ1,τ2,…,τw _1, _2,…, _w, then disjointness of the charged sets implies n≥2τ1+2τ2+⋯+2τw.n≥ 2 _1+2 _2+·s+2 _w. Since the τi _i are distinct positive integers, we have n≥21+⋯+2w≥2wn≥ 2^1+·s+2^w≥ 2^w. Taking logarithms gives w≤log2nw≤ _2n. The first block with an incomplete head accounts for the additional 11. ∎ Next, we compute the algorithm’s density among integers in the first case. Lemma C.3. Fix any ε>0 >0. There is a constant CεC_ such that, for any prefix [n]i[n]_i, if Fi,nF_i,n is the number of integers in the first case, then the number of integers in the first case that are first announced by the algorithm is at least (12−ε)⋅(Fi,n−Cε). ( 12- )·(F_i,n-C_ ). Proof of Lemma˜C.3. For b≥1b≥ 1, define ϕ(b)=12⋅(1−4⋅(kb+1)1−1/k+1b).φ(b)= 12· (1- 4·(kb+1)^1-1/k+1b ). Then ϕ(b)→1/2φ(b)→ 1/2 as b→∞b→∞. Hence, there exists an integer B=B(ε)B=B( ) such that ϕ(b)≥1/2−εφ(b)≥ 1/2- for every b≥Bb≥ B. Consider any block BrB_r with a complete head Br[br]iB_r[b_r]_i. Since the head is complete, at least brb_r integers in [n]i[n]_i are associated with BrB_r. The block has size at most kbr+1kb_r+1, so by Theorem˜2.5 it contributes at most 4⋅(kbr+12)1−1/k≤4⋅(kbr+1)1−1/k4· ( kb_r+12 )^1-1/k≤ 4·(kb_r+1)^1-1/k crossed pairs. If we exclude the integers in crossed pairs and the trigger, then the algorithm first announces half of the remaining integers. Therefore, the algorithm’s density among the integers associated with BrB_r is at least ϕ(br)φ(b_r). It remains to control the contribution of blocks with small brb_r. At the time BrB_r is created, some order j∈[k]j∈[k] satisfies mr=ρj(W∩F)m_r= _j(W∩ F), and the corresponding first available element under σj _j is reserved in BrB_r. For each pair (j,mr)(j,m_r), this can happen at most once. Thus, for a fixed b≥1b≥ 1, there are at most k(2b−1)k(2b-1) blocks with br=b_r=b. Each such block contributes at most kb+2kb+2 integers in the first case, including its trigger. Therefore, the number of integers in the first case connected to blocks with br<Bb_r<B is at most Cε:= @b=1B−1(kb+2)⋅k(2b−1).C_ := @_b=1^B-1(kb+2)· k(2b-1). All remaining integers in the first case come from blocks with br≥Bb_r≥ B, and hence contribute a fraction at least 1/2−ε1/2- . The result follows. ∎ Finally, we can compute the lower density of the A Tight Deterministic Algorithm under Multiple Orders. Proof of Theorem˜5.2. Fix an order index i and an arbitrary prefix [n]i[n]_i. Let r be the number of integers that have already been announced or reserved before the algorithm starts generating K; by Lemma˜C.1, this happens after finitely many time steps. By Lemma˜C.2, there are at most log2n+1 _2n+1 blocks involved in the second case. For each such block, the integers it contributes to the second case consist of at most one trigger, plus the elements of Br∩[n]iB_r∩[n]_i. If Br∩[n]i∅B_r∩[n]_i≠ , then mr≤nm_r≤ n, so br≤⌈n⌉b_r≤ n and |Br|≤k⌈n⌉+1 |B_r |≤ k n +1. Otherwise, the block contributes only its trigger. Therefore, the number of integers in the second case is at most (k⌈n⌉+2)⋅(log2n+1).(k n +2)·( _2n+1). It follows that the number Fi,nF_i,n of integers in the first case is at least n−r−(k⌈n⌉+2)⋅(log2n+1).n-r-(k n +2)·( _2n+1). Fix any ε>0 >0. By Lemma˜C.3, for the corresponding constant CεC_ , we have μi,n(D∩K)≥(12−ε)⋅(n−r−(k⌈n⌉+2)⋅(log2n+1)−Cε). _i,n(D∩ K)≥ ( 12- )· (n-r-(k n +2)·( _2n+1)-C_ ). Thus the algorithm’s lower density under the k orders is at least mini∈[k]lim infn→∞μi,n(D∩K)μi,n(K) _i∈[k] _n→∞ _i,n(D∩ K) _i,n(K) ≥mini∈[k]lim infn→∞(12−ε)⋅n−r−(k⌈n⌉+2)⋅(log2n+1)−Cεn ≥ _i∈[k] _n→∞ ( 12- )· n-r-(k n +2)·( _2n+1)-C_ n =12−ε. = 12- . Since ε>0 >0 was arbitrary, the lower density is at least 1/21/2. ∎ Appendix D A Tight Randomized Algorithm under Multiple Orders The algorithm maintains a family of pairwise disjoint blocks B1,B2,…B_1,B_2,…. Each block can be partitioned into pairwise disjoint groups Gr,1,Gr,2,…G_r,1,G_r,2,…. Each group Gr,r′G_r,r is equipped with an independent uniformly random permutation πr,r′ _r,r . The randomized grouped patient-scope algorithm • Let NB=0N_B=0 be the current number of blocks. • Initially, at time t=0t=0, set the scope size s0=1s_0=1, set the focus-change count τ=1τ=1, and create no blocks. • In each time step t, perform the following operations. – Set the scope size st=st−1s_t=s_t-1. – Receive a new integer from the adversary, and update the sets of consistent and critical languages accordingly. – If the focus becomes inconsistent, run the Our Algorithm. – Otherwise, if the focus F is still consistent and the adversary has announced 2τ2^τ unreserved elements, increase the scope size by one and update the focus accordingly. If the focus changes, increase τ by one. – Let xtx_t be the adversary’s announced number in this step. * If xt∈Gr,r′x_t∈ G_r,r for some group Gr,r′G_r,r , then output the first number in the permutation πr,r′ _r,r that has not been announced by either party. If no such number exists, see the next step. * If xtx_t has not yet been reserved or xtx_t is the last unannounced number in its group Gr,r′G_r,r , then let mmini∈[k]ρi(W∩F)m _i∈[k] _i(W∩ F) Define BNB+1 @i∈[k](W∩F)[⌈m2/3⌉]i.B_N_B+1 @_i∈[k](W∩ F) [ m^2/3 ]_i. Namely, block BNB+1B_N_B+1 contains top ⌈m2/3⌉ m^2/3 available elements under each order. We further repeatedly add the smallest element in (W∩F)∖BNB+1(W∩ F) B_N_B+1 under σ1 _1 to BNB+1B_N_B+1 until |BNB+1| |B_N_B+1 | is divisible by ⌈m1/3⌉ m^1/3 . Construct a balanced partition PNB+1P_N_B+1 of BNB+1B_N_B+1 into groups of size ⌈m1/3⌉ m^1/3 by applying Theorem˜2.5 to the induced orders of σ1,…,σk _1,…, _k on BNB+1B_N_B+1. For each group GNB+1,r′G_N_B+1,r in BNB+1B_N_B+1, generate an independent uniformly random permutation πNB+1,r′ _N_B+1,r . Mark all elements of BNB+1B_N_B+1 as reserved, output the first element of πNB+1,1 _N_B+1,1. Increase NBN_B by 11. The following lemma is analogous to the validity lemmas above, so we state it without proof. Lemma D.1 (Validity). The A Tight Randomized Algorithm under Multiple Orders can generate in the limit the true language K. As in the proof of Theorem˜5.2, we may ignore the time steps before the algorithm starts generating K, identify K with Z+Z^+, and update each σi _i accordingly. For a block BrB_r, let mrm_r be the value of m when BrB_r is created, and define br=⌈mr2/3⌉andgr=⌈mr1/3⌉.b_r= m_r^2/3 g_r= m_r^1/3 . Thus grg_r is the size of every group in the partition of BrB_r. Define the head of BrB_r under σi _i to be the set Br[br]iB_r[b_r]_i. During any consecutive interval with no switch loss, the heads of newly reserved blocks are strictly above the heads of older reserved blocks under σi _i. Fix a prefix [n]i[n]_i. A head Br[br]iB_r[b_r]_i is complete within n if Br[br]i⊆[n]iB_r[b_r]_i [n]_i; otherwise it is incomplete within n. Each integer in [n]i[n]_i that was neither announced nor reserved before the algorithm starts generating K falls into one of the following two cases: 1. it belongs to a block BrB_r with a complete head Br[br]iB_r[b_r]_i, or is the trigger of such a block; 2. it belongs to a block BrB_r with an incomplete head Br[br]iB_r[b_r]_i, or is the trigger of such a block. We first count the number of blocks involved in the second case. Lemma D.2. For any prefix [n]i[n]_i, there are at most log2n+1 _2n+1 blocks BrB_r whose heads Br[br]iB_r[b_r]_i are incomplete within n and that satisfy either Br∩[n]i∅B_r∩[n]_i≠ or the trigger of BrB_r lies in [n]i[n]_i. Proof of Lemma˜D.2. As in the proof of Lemma˜C.2, after the first block with an incomplete head, each later counted block corresponds to a unique switch loss ℓ : either ℓ is an unreserved element of [n]i[n]_i that triggers the new block, or the switch makes the first element of W∩FW∩ F under σi _i lie in [n]i[n]_i. In both cases, we charge ℓ to 2τ′2^τ heads reserved by the A Tight Randomized Algorithm under Multiple Orders that lie in [n]i[n]_i. If there are w such switch losses ℓ1,ℓ2,…,ℓw _1, _2,…, _w with corresponding focus-change counts τ1,τ2,…,τw _1, _2,…, _w, then disjointness of the charged sets implies n≥2τ1+2τ2+⋯+2τw.n≥ 2 _1+2 _2+·s+2 _w. Since the τi _i are distinct positive integers, we have n≥21+⋯+2w≥2wn≥ 2^1+·s+2^w≥ 2^w. Taking logarithms gives w≤log2nw≤ _2n. The first block with an incomplete head accounts for the additional 11. ∎ Next, we compute the algorithm’s density among integers in the first case. Lemma D.3. Fix any ε>0 >0. There is a constant CεC_ such that, for any prefix [n]i[n]_i, if Fi,nF_i,n is the number of integers in the first case, then the expected number of integers in the first case that are first announced by the algorithm is at least (1−1e−ε)⋅(Fi,n−Cε). (1- 1e- )·(F_i,n-C_ ). Proof of Lemma˜D.3. For a positive integer m, let b(m)=⌈m2/3⌉andg(m)=⌈m1/3⌉,b(m)= m^2/3 g(m)= m^1/3 , and define ϕ(m)=(1−1g(m))⋅f(g(m))⋅(1−4g(m)⋅(kb(m)+g(m)g(m))1−1/kb(m)).φ(m)= (1- 1g(m) )· f(g(m))· (1- 4g(m)· ( kb(m)+g(m)g(m) )^1-1/kb(m) ). Since (1−1g(m))⋅f(g(m))→1−1/e (1- 1g(m) )· f(g(m))→ 1-1/e as m→∞m→∞, and since g(m)⋅(kb(m)+g(m)g(m))1−1/kb(m)→0as m→∞, g(m)· ( kb(m)+g(m)g(m) )^1-1/kb(m)→ 0 m→∞, we have ϕ(m)→1−1/eφ(m)→ 1-1/e. Hence, there exists an integer M=M(ε)M=M( ) such that ϕ(m)≥1−1/e−εφ(m)≥ 1-1/e- for every m≥Mm≥ M. Consider any block BrB_r with a complete head Br[br]iB_r[b_r]_i. The block has size at most kbr+grkb_r+g_r, and each group has size grg_r. Thus, by Theorem˜2.5, the number of groups crossed by the cut (Br∩[n]i,Br∖[n]i)(B_r∩[n]_i,B_r [n]_i) is at most 4⋅(kbr+grgr)1−1/k.4· ( kb_r+g_rg_r )^1-1/k. Exclude the integers in these crossed groups. Every remaining associated integer either lies in a group that is fully contained in [n]i[n]_i or is the trigger of BrB_r. For any such group G, Lemma˜4.5 implies that the expected number of elements of G first announced by the algorithm is at least (1−1|G|)⋅f(|G|) (1- 1 |G | )· f( |G |). Indeed, for the group whose permutation is used when BrB_r is created, we apply Lemma˜4.5 to G together with the trigger; for every other group, we apply it directly to G. Therefore, the expected fraction of associated integers of BrB_r that are first announced by the algorithm is at least (1−1gr)⋅f(gr)⋅(1−4gr⋅(kbr+grgr)1−1/kbr)=ϕ(mr). (1- 1g_r )· f(g_r)· (1- 4g_r· ( kb_r+g_rg_r )^1-1/kb_r )=φ(m_r). It remains to control the contribution of blocks with mr<Mm_r<M. At the time BrB_r is created, some order j∈[k]j∈[k] satisfies mr=ρj(W∩F)m_r= _j(W∩ F), and the corresponding first available element under σj _j is reserved in BrB_r. For each pair (j,mr)(j,m_r), this can happen at most once. Thus, there are at most k(M−1)k(M-1) blocks with mr<Mm_r<M. Each such block contributes at most k⌈M2/3⌉+⌈M1/3⌉+1k M^2/3 + M^1/3 +1 integers in the first case, including its trigger. Hence the number of integers in the first case connected to blocks with mr<Mm_r<M is at most Cε:=k(M−1)⋅(k⌈M2/3⌉+⌈M1/3⌉+1).C_ :=k(M-1)· (k M^2/3 + M^1/3 +1 ). All remaining integers in the first case come from blocks with mr≥Mm_r≥ M, and hence contribute a fraction at least 1−1/e−ε1-1/e- in expectation. The result follows. ∎ Finally, we can compute the lower density of the A Tight Randomized Algorithm under Multiple Orders. Proof of Theorem˜5.9. Fix an order index i and an arbitrary prefix [n]i[n]_i. Let r be the number of integers that have already been announced or reserved before the algorithm starts generating K; by Lemma˜D.1, this happens after finitely many time steps. By Lemma˜D.2, there are at most log2n+1 _2n+1 blocks involved in the second case. For each such block, the integers it contributes to the second case consist of at most one trigger, plus the elements of Br∩[n]iB_r∩[n]_i. If Br∩[n]i∅B_r∩[n]_i≠ , then mr≤nm_r≤ n, so br≤⌈n2/3⌉b_r≤ n^2/3 , gr≤⌈n1/3⌉g_r≤ n^1/3 , and |Br|≤k⌈n2/3⌉+⌈n1/3⌉. |B_r |≤ k n^2/3 + n^1/3 . Otherwise, the block contributes only its trigger. Therefore, the number of integers in the second case is at most (k⌈n2/3⌉+⌈n1/3⌉+1)⋅(log2n+1). (k n^2/3 + n^1/3 +1 )·( _2n+1). It follows that the number Fi,nF_i,n of integers in the first case is at least n−r−(k⌈n2/3⌉+⌈n1/3⌉+1)⋅(log2n+1).n-r- (k n^2/3 + n^1/3 +1 )·( _2n+1). Fix any ε>0 >0. By Lemma˜D.3, for the corresponding constant CεC_ , we have E[μi,n(D∩K)]≥(1−1e−ε)⋅(n−r−(k⌈n2/3⌉+⌈n1/3⌉+1)⋅(log2n+1)−Cε). *E [ _i,n(D∩ K) ]≥ (1- 1e- )· (n-r- (k n^2/3 + n^1/3 +1 )·( _2n+1)-C_ ). Thus, the algorithm’s lower density under the k orders is at least mini∈[k]lim infn→∞E[μi,n(D∩K)]μi,n(K) _i∈[k] _n→∞ *E [ _i,n(D∩ K) ] _i,n(K) ≥ ≥ mini∈[k]lim infn→∞(1−1e−ε)⋅n−r−(k⌈n2/3⌉+⌈n1/3⌉+1)⋅(log2n+1)−Cεn _i∈[k] _n→∞ (1- 1e- )· n-r- (k n^2/3 + n^1/3 +1 )·( _2n+1)-C_ n = = 1−1e−ε. 1- 1e- . Since ε>0 >0 was arbitrary, the lower density is at least 1−1/e1-1/e. ∎