New bounds for (weak) sequenceability in ℤ k \mathbb{Z}_{k} Simone Costa, Stefano Della Fiore Abstract . A famous conjecture of Graham asserts that every set A ⊆ ℤ p ∖ { 0 } A\subseteq\mathbb{Z}_{p}\setminus\{0\} can be ordered so that all partial sums are distinct. Although this conjecture was recently proved for sufficiently large primes by Pham and Sauermann in [ 16 ] , it remains open for general abelian groups, even in the cyclic case ℤ k \mathbb{Z}_{k} . For cyclic groups, the best known result is due to Bedert and Kravitz in [ 4 ] , who proved - using a rectification and a two-step probabilistic approach - that the conjecture holds for any subset A ⊆ ℤ k ∖ { 0 } A\subseteq\mathbb{Z}_{k}\setminus\{0\} such that | A | ≤ exp ⁡ ( c ​ ( log ⁡ p ) 1 / 4 ) , |A|\leq\exp\!\big(c(\log p)^{1/4}\big), for some constant c > 0 c>0 , where p p denotes the least prime divisor of k k . In this paper, we improve their bound using a rectification argument again, followed by a one-shot probabilistic approach, showing that the conjecture holds whenever | A | ≤ exp ⁡ ( c ​ ( log ⁡ p ) 1 / 3 ) , |A|\leq\exp\!\big(c(\log p)^{1/3}\big), thus improving the exponent 1 / 4 1/4 from [ 4 ] . Moreover, the same one-shot approach adapts to the t t -weak setting: by imposing all local constraints at once and applying the Lovász Local Lemma, we obtain the existence of a t t -weak sequencing whenever t ≤ exp ⁡ ( c ​ ( log ⁡ p ) 1 / 4 ) . t\leq\exp\!\big(c(\log p)^{1/4}\big). 1991 Mathematics Subject Classification 11B75 1. Introduction Let A be a finite subset of an abelian group (G,+) . We say that an ordering a_{1},\ldots,a_{|A|} of A is valid if its partial sums p_{1}=a_{1},p_{2}=a_{1}+a_{2},\ldots,p_{|A|}=a_{1}+\cdots+a_{|A|} are pairwise distinct. Moreover, this ordering is a sequencing if it is valid and p_{i}\neq 0 for every 1\leq i\leq|A|-1 . In this case, we say that A is sequenceable. If we relax the definition, we say that an ordering is a t -weak sequencing if for every i\neq j with 1\leq|i-j|\leq t , the partial sums p_{i} and p_{j} are non-zero and distinct. In this case we say that A is t -weak sequenceable. In the literature, there are several conjectures about valid orderings and sequenceability. We refer to [ 9 , 13 , 15 ] for an overview of the topic, [ 1 , 2 , 3 , 8 ] for lists of related conjectures, and [ 5 ] for a treatment using rainbow paths. Here, we explicitly recall Graham’s conjecture, which states that every set of nonzero elements of \mathbb{Z}_{p} has a valid ordering. Conjecture 1.1 ( [ 11 ] and [ 10 ] ) . Let p be a prime. Then every subset A\subseteq\mathbb{Z}_{p}\setminus\{0\} has a valid ordering. Until recently, the main results on this conjecture were for small values of |A| ; in particular, in [ 8 ] , the conjecture was proved for sets A of size at most 12 . The first result involving arbitrarily large sets A was presented by Kravitz [ 12 ] , who used a rectification argument to show that Graham’s conjecture holds for all sets A of size |A|\leq\log p/\log\log p . A similar argument was also proposed (but not published) by Will Sawin [ 17 ] . Then, in [ 4 ] , Bedert and Kravitz improved - using a rectification and a two-step probabilistic approach - this upper bound to the following: Theorem 1.2 ( [ 4 ] ) . Let p be a large enough prime and let c>0 . Then every subset A\subseteq\mathbb{Z}_{p}\setminus\{0\} is sequenceable provided that |A|\leq\exp\!\big(c(\log p)^{1/4}\big). They explicitly state their result for \mathbb{Z}_{p} , but their approach can be easily adapted to a generic cyclic group. Finally, in [ 16 ] , Graham’s conjecture was proved for all sufficiently large primes p . This result is a consequence of anticoncentration inequalities developed using a discrete Fourier approach that seems hard to adapt to the cyclic case. In this paper, we record two complementary developments. In one direction, we show how it is possible to improve the bound [ 4 ] again using a rectification argument and a one-shot probabilistic approach, and obtain Theorem 1.3 (Improved classical bound) . There exists a constant c>0 such that, denoted by p the least prime divisor of k , then every subset A\subseteq\mathbb{Z}_{k}\setminus\{0\} is sequenceable provided that |A|\ \leq\ \exp\!\big(c(\log p)^{1/3}\big). In particular, the one-shot scheme removes the need to separate the treatment of Type I and Type II intervals, and this structural simplification is what ultimately permits the sharper quantitative bound. Here, we also show how this approach can be localized for the t -weak sequenceability problem. For this problem, in [ 8 ] , the authors proved that if the order of a group is pe then all sufficiently large subsets of the non-identity elements are t -weakly sequenceable when p>3 is prime, e\leq 3 and t\leq 6 . Then in [ 6 ] , using a hybrid approach that combines Ramsey theory and the probabilistic method, the authors proved that if the size of a subset A of an abelian group G is at least t^{\alpha t} for some \alpha>2 and A does not contain 0 , then A is t -weak sequenceable. Here, using a one-shot procedure that involves the Lovász Local Lemma, we obtain: Theorem 1.4 . There exists a constant c>0 such that, if p is the least prime divisor of k , then every subset A\subseteq\mathbb{Z}_{k}\setminus\{0\} is t -weak sequenceable provided that t\ \leq\ \exp\!\big(c(\log p)^{1/4}\big). Notation. For a sequence \mathbf{b}=b_{1},\ldots,b_{r} , let \IS(\mathbf{b}):=\{b_{1}+\cdots+b_{j}:0\leq j\leq r\} denote the set of initial segment sums of \mathbf{b} , and let \overline{\mathbf{b}}:=b_{r},\ldots,b_{1} denote the reverse of \mathbf{b} . In addition, we denote \IS_{t}(\mathbf{b}):=\{b_{1}+\cdots+b_{j}:0\leq j\leq t\}. Using standard asymptotic notation, we say that f=\Theta(g) if there exist two absolute constants C_{1},C_{2}>0 such that C_{1}g\leq f\leq C_{2}g . We also define f(p)=o(g(p)) if \lim_{p\to\infty}f(p)/g(p)=0 . 2. Proof of Theorem 1.4 and the one-shot framework Let G be an abelian group. A subset D=\{d_{1},\ldots,d_{r}\}\subseteq G is dissociated if \epsilon_{1}d_{1}+\cdots+\epsilon_{r}d_{r}\neq 0\quad\text{for all $(\epsilon_{1},\ldots,\epsilon_{r})\in\{-1,0,1\}^{r}\setminus\{(0,\ldots,0)\}$}. Equivalently, D is dissociated if all of the 2^{|D|} subset sums of D are distinct. The dimension of a subset B\subseteq G , written \dim(B) , is the size of the largest dissociated set contained in B . The \Span(B) of a subset B\subseteq G , is defined as \Span(B):=\left\{\sum_{b\in B}\epsilon_{b}b:\epsilon_{b}\in\{-1,0,1\}\right\} 2.1. Structure Theorem We begin by stating a variation of the Structure Theorem of Bedert and Kravitz, enunciated here for the rings \mathbb{Z}_{k} in a form that also enforces the dissociated sets D_{j} to have comparable size. Throughout the t -weak part of this paper we set R:=R(k)=c_{1}(\log p)^{1/2}, where c_{1}>0 is a sufficiently small absolute constant and p is the least prime divisors of k . The Structure Theorem is based on the following rectification Lemma, proved here for cyclic groups. Lemma 2.1 . If B\subseteq\mathbb{Z}_{k} is a nonempty subset of dimension dim(B)0 then: (ii) P\cup N is nonempty, and each D_{j} is dissociated of size |D_{j}|=\Theta(R) ; (iii) \delta\notin\{0\}\cup-P\cup-N , and moreover \delta\neq-\sum_{p\in P}p if N is nonempty and \delta\neq-\sum_{n\in N}n if P is nonempty; (iv) D_{1}\cup D_{s}\cup\{\delta\} is dissociated. 2.2. Ordering P and N Here we recall the following important proposition from [ 4 ] . Proposition 2.3 . Let P\subseteq(0,\frac{k}{4|P\cup N|}) and N\subseteq(-\frac{k}{4|P\cup N|},0) be subsets of \mathbb{Z}_{k} , and let \delta>0 be contained in (0,\frac{k}{4|P\cup N|}) ; moreover, assume that \delta\neq-\sum_{n\in N}n if P\neq\emptyset . Let Y^{+}_{1},\ldots,Y^{+}_{m},Y^{-}_{1},\ldots,Y^{-}_{m}\subseteq\mathbb{Z} be finite sets. Then there are orderings \mathbf{p} of P and \mathbf{n} of N such that \overline{\mathbf{p}},\delta,\mathbf{n} is a sequencing and we have \displaystyle|\IS(\mathbf{p})\cap Y^{+}_{j}|\leq\inf_{L\in\mathbb{N}}\left(\frac{|Y^{+}_{j}|}{L}+L+4+4\sum_{i=1}^{j-1}|Y^{+}_{i}|\right) and \displaystyle|\IS(\mathbf{n})\cap Y^{-}_{j}|\leq\inf_{L\in\mathbb{N}}\left(\frac{|Y^{-}_{j}|}{L}+L+4+4\sum_{i=1}^{j-1}|Y^{-}_{i}|\right) for all 1\leq j\leq m . 2.3. Splitting, rearrangement, and a one-shot control of Type I and Type II We begin with the standard anti-concentration input for dissociated sets. Lemma 2.4 (Lemma 5.1 of [ 4 ] ) . Let D\subset G be a dissociated set, and let D=D^{(1)}\sqcup D^{(2)}\sqcup D^{(3)}\sqcup D^{(4)} be a uniformly random partition of D into four sets of equal size. Then for every proper subset I\subset[4] and every x\in G , \mathbb{P}\Big(\sum_{i\in I}\sum_{d\in D^{(i)}}d=x\Big)\leq\binom{|D|}{|D|\cdot|I|/4}^{-1}\leq\binom{|D|}{|D|/4}^{-1}. Starting from a set A , we consider D_{1},\dots,D_{s} to be the dissociated sets appearing in the structural decomposition of \lambda\cdot A provided by Theorem 2.2 and P\subseteq(0,\frac{k}{4|P\cup N|}) , N\subseteq(-\frac{k}{4|P\cup N|},0) the sets of positive and negative elements there defined. We split and rearrange the dissociated sets as follows. (S1) For each j\in\{2,\dots,s-1\} , we partition D_{j} into four equal parts D_{j}=D_{j}^{(1)}\sqcup D_{j}^{(2)}\sqcup D_{j}^{(3)}\sqcup D_{j}^{(4)} uniformly at random as in Lemma 2.4 . We do all these splittings independently. (S2) For the endpoint blocks D_{1} and D_{s} , we choose a uniform random permutation \sigma_{1} of D_{1} and define D_{1}^{(1)},\dots,D_{1}^{(4)} as the four consecutive segments (equal size) of the list \sigma_{1} . Likewise, we choose a uniform random permutation \sigma_{s} of D_{s} and define D_{s}^{(1)},\dots,D_{s}^{(4)} as consecutive segments. Next, we place these newly formed sets, together with P and N , in the deterministic order (2) \displaystyle P,D_{1}^{(1)},D_{1}^{(2)},D_{2}^{(1)},D_{2}^{(2)},\ldots,D_{s}^{(1)},D_{s}^{(2)},D_{1}^{(3)},D_{1}^{(4)},D_{2}^{(3)},D_{2}^{(4)},\ldots,D_{s}^{(3)},D_{s}^{(4)},N. Write T_{1},\dots,T_{u} (with u=4s ) for the resulting sequence of dissociated sets in ( 2 ), and set \tau_{j}:=\sum_{t\in T_{j}}t . We also denote \displaystyle\sum_{\leq M}(T_{j}):=\Big\{\sum_{t\in S}t:S\subseteq T_{j},\ |S|\leq M\Big\}, \displaystyle\sum_{=M}(T_{j}):=\Big\{\sum_{t\in S}t:S\subseteq T_{j},\ |S|=M\Big\}\,. Fix an integer K=c_{2}R^{1/2} where c_{2} is a positive small enough constant. A proper nonempty interval I\subset[1,|A|] is of Type II if it contains between K and |T_{j}|-K elements of some block T_{j} . Otherwise I is of Type I . Now, set \displaystyle Y^{+}_{j}\vcentcolon=-\sum_{=j}(D_{1})\cup\left(-\delta+\sum_{=j}(D_{s})\right)\quad\text{and}\quad Y^{-}_{j}\vcentcolon=-\sum_{=j}(D_{s})\cup\left(-\delta+\sum_{=j}(D_{1})\right) for each 1\leqslant j\leqslant K , and apply Proposition 2.3 . This provides orderings \mathbf{p} of P and \mathbf{n} of N such that the sequence \overline{\mathbf{p}},\delta,\mathbf{n} is a sequencing and such that the bounds in Proposition 2.3 hold. We say that an ordering t_{1},\dots,t_{|T_{1}|} of T_{1} is acceptable if t_{1}+\dots+t_{k}\notin-\IS(\mathbf{p})\cup\left(\delta+\IS(\mathbf{n})\right)\quad\text{for all $1\leq k\leqslant K$}, and say that an ordering t_{1},\dots,t_{|T_{u}|} of T_{u} is acceptable if t_{1}+\dots+t_{k}\notin-\IS(\mathbf{n})\cup\left(\delta+\IS(\mathbf{p})\right)\quad\text{for all $1\leq k\leqslant K$}. We then state the following lemma, which is an improvement of Lemma 6.1 of [ 4 ] . Lemma 2.5 . Let \mathbf{t}_{1} be the order induced by \sigma_{1} on T_{1} and \mathbf{t}_{u} be the order induced by \sigma_{s} on T_{u} . Then, we have that \mathbf{t}_{1} is acceptable with probability at least 0.99 and \mathbf{t}_{u} 0.99 is acceptable with probability at least 0.99 . Proof. We prove only the statement for \mathbf{t}_{1} since the argument for \mathbf{t}_{u} is identical. Let \mathbf{t}_{1}=t_{1},\ldots,t_{|T_{1}|} be our random ordering induced by \sigma_{1} on T_{1} . By the union bound, it suffices to show that \mathbb{P}(t_{1}+\cdots+t_{k}\in-\IS(\mathbf{p})\cup(\delta+\IS(\mathbf{n})))\leqslant 0.01K^{-1} for each 1\leqslant k\leqslant K . Fix some 1\leqslant k\leqslant K . Then the quantity t_{1}+\cdots+t_{k} is uniformly distributed on the set \sum_{=k}(D_{1}) , which has size \binom{|D_{1}|}{k} . Then by Proposition 2.3 , with L:=\lfloor|Y_{k}^{+}|^{1/2}\rfloor , we have that \left|\sum_{=k}(D_{1})\cap(-\IS(\mathbf{p})\cup(\delta+\IS(\mathbf{n})))\right|=O\left(|Y_{k}^{+}|^{1/2}+\sum_{j0 . A one-shot lemma We now state a lemma that simultaneously controls Type I and Type II intervals by sampling the splitting and the internal orderings in a single step. Lemma 2.7 (One-shot Type I/II control) . Assume t\leq\exp(cK) for a sufficiently small absolute c>0 . Let D_{1},\dots,D_{s}\subseteq\mathbb{Z}_{k} be dissociated sets, each of size \Theta(R) , such that D_{1}\cup D_{s}\cup\{\delta\} is dissociated, where \delta:=\sum_{j=1}^{s}\sum_{d\in D_{j}}d . Let \mathbf{p} and \mathbf{n} be sequences over \mathbb{Z}_{k} and assume that \overline{\mathbf{p}},\delta,\mathbf{n} is a t -weak sequencing. Fix an integer K=c_{2}R^{1/2} where c_{2} is a small positive constant. Choose the sets T_{1},\dots,T_{u} by the splitting procedure above, and then choose orderings \mathbf{t}_{1},\dots,\mathbf{t}_{u} of the blocks T_{1},\dots,T_{u} as follows: (a) \mathbf{t}_{1} is the order induced by \sigma_{1} on T_{1} and \mathbf{t}_{u} is the order induced by \sigma_{s} on T_{u} , and we condition on the event that both \mathbf{t}_{1} and \mathbf{t}_{u} are acceptable with parameter K (in the sense of Lemma 2.5 ). (b) For each internal adjacent pair (T_{2j},T_{2j+1}) we sample uniformly at random the pair (\mathbf{t}_{2j},\mathbf{t}_{2j+1}) from the permissible pairs of orderings of length K (as done in [ 4 , Lemma 6.2] ). Let a_{1},\dots,a_{|A|} be the concatenation a_{1},\dots,a_{|A|}\ :=\ \overline{\mathbf{p}},\ \mathbf{t}_{1},\dots,\mathbf{t}_{u},\ \mathbf{n}. Then: (1) (Type II anti-concentration) For every Type II interval I\subset[1,|A|] with |I|\leq t , \mathbb{P}\Big(\sum_{i\in I}a_{i}=0\Big)\ \leq\ \exp\!\big(-\Theta(K\log R)\big). (2) (Type I anti-concentration) For every Type I interval I\subset[1,|A|] with |I|\leq t , \mathbb{P}\Big(\sum_{i\in I}a_{i}=0\Big)\ \leq\ \exp\!\big(-\Theta(R)\big). (3) ( t -weak existence via LLL) With positive probability (hence there exists a choice of the random splittings and orderings) every interval I\subset[1,|A|] with |I|\leq t has nonzero sum, and therefore a_{1},\dots,a_{|A|} is a t -weak sequencing. Proof. The Type II anti-concentration inequality follows exactly by the same argument used in [ 4 , Lemma 6.3] . Type I. Let us consider the following set of events: (i) For each proper nonempty interval [i,j]\subseteq[u] , |i-j|\leq t , 0\in\left(\sum_{\leq K}(T_{i-1})\cup-\sum_{\leq K}(T_{i})\right)+\tau_{i}+\cdots+\tau_{j}+\left(-\sum_{\leq K}(T_{j})\cup\sum_{\leq K}(T_{j+1})\right) (with the convention that T_{0}=T_{u+1}=\emptyset ); (ii) For each 1\leq j\leq\min\{t,u-1\} , 0\in\IS_{t}(\mathbf{p})+\tau_{1}+\cdots+\tau_{j}+\left(-\sum_{\leq K}(T_{j})\cup\sum_{\leq K}(T_{j+1})\right); and for each \max\{2,u-t+1\}\leq j\leq u , 0\in\IS_{t}(\mathbf{n})+\tau_{u}+\cdots+\tau_{j}+\left(-\sum_{\leq K}(T_{j})\cup\sum_{\leq K}(T_{j-1})\right). By the deterministic order ( 2 ), there exists \ell such that each proper nonempty interval J\subseteq[u] contains some but not all of D_{\ell}^{(1)},\dots,D_{\ell}^{(4)} ; hence \sum_{j\in J}\tau_{j} includes a subset-sum of D_{\ell} of fixed size, which is distributed uniformly among all such subset-sums. By dissociativity, all these sums are distinct, so each value is attained with probability at most \binom{|D_{\ell}|}{|D_{\ell}|/4}^{-1}\leq\exp(-\Theta(R)) thanks to Lemma 2.4 . Then since |T_{j}|=\Theta(R) and K=o(R) we have that |\sum_{\leq K}(T_{j})|=\exp(o(R)) . Also note that |\IS_{t}(\mathbf{p})|,|\IS_{n}(\mathbf{n})|\leq t=\exp(o(R)) , therefore we find that conditions (i) , (ii) have probability of at most \exp(-\Theta(R)) . This handles all Type I intervals except the ones starting in the last K elements of \mathbf{t}_{2j} and ending in the first K elements of \mathbf{t}_{2j+1} and the ones starting in \overline{\mathbf{p}} and ending in the first K elements of \mathbf{t}_{1} or the ones starting last K elements of \mathbf{t}_{u} and ending in \mathbf{n} but these lat two cases are avoided since we are conditioning on the event that both \mathbf{t}_{1} and \mathbf{t}_{u} are acceptable and the pairs (\mathbf{t}_{2j},\mathbf{t}_{2j+1}) are permissible. t -weak via LLL. Consider bad events E_{I} for intervals I\subset[1,|A|] , |I|\leq t , defined by \sum_{i\in I}a_{i}=0 . By the previous two parts, \mathbb{P}(E_{I})\leq P with P\leq\exp(-\Theta(K\log R)) . We now bound the dependency degree in the Lovász Local Lemma. For any interval I\subset[1,|A|] and block T_{i}\subseteq D_{\ell} , the bad event E_{I} depends on • the random ordering of T_{i} ; • the random splitting variables used to generate the four pieces D_{\ell}^{(1)},D_{\ell}^{(2)},D_{\ell}^{(3)},D_{\ell}^{(4)} ; • the random ordering of T_{i^{\prime}}\subseteq D_{\ell^{\prime}} where (T_{i},T_{i^{\prime}}) are adjacent and conditioned by the permissibility condition; • the random splitting variables used to generate the four pieces D_{\ell^{\prime}}^{(1)},D_{\ell^{\prime}}^{(2)},D_{\ell^{\prime}}^{(3)},D_{\ell^{\prime}}^{(4)} . Fix E_{I} . Since |I|\leq t , the interval I intersects at most t blocks. For each dissociated set D_{\ell} touched by I , there are at most 8 associated pieces, each of size \Theta(R) . The number of intervals of length at most t that intersect a fixed block of size \Theta(R) is O(tR+t^{2}) . Therefore the total number of bad events that can fail to be mutually independent from E_{I} is at most D=O\big(t(tR+t^{2})\big)=O(t^{2}R+t^{3}). Thus, by the symmetric Lovász Local Lemma, it suffices to verify ePD\leq 1. For t\leq\exp(cK) and c>0 sufficiently small, this holds since P\leq\exp(-\Theta(K\log R)) and D=\exp(O(\log t+\log R)) . Hence \Pr\left(\cap_{I}\overline{E_{I}}\right)>0 . ∎ 2.4. Proof of Theorem 1.4 We now complete the proof of Theorem 1.4 . Let A\subseteq\mathbb{Z}_{k}\setminus\{0\} . Apply Theorem 2.2 to obtain a dilation \lambda and a decomposition \lambda A=P\cup N\cup(\cup_{j=1}^{s}D_{j}) with the stated properties. By [ 4 , Proposition 4.1] (see Lemma 2.3 of this paper), we can choose orderings \mathbf{p} of P and \mathbf{n} of N such that \overline{\mathbf{p}},\delta,\mathbf{n} is a sequencing. Now set K:=c_{2}R^{1/2}\ =\ \Theta\big((\log p)^{1/4}\big), with c_{2}>0 sufficiently small, and apply Lemma 2.7 . Part (3) of Lemma 2.7 gives existence of a t -weak sequencing provided t\leq\exp(cK) for a sufficiently small absolute constant c>0 , which yields t\leq\exp(c(\log p)^{1/4}) after renaming constants. Therefore, if p is large enough (i.e. p\geq\bar{p} ), with positive probability, the sampled ordering contains no nontrivial zero-sum interval, i.e. it is a t -weak sequencing. Moreover we can chose c small enough so that \exp\!\big(c(\log p)^{1/4}\big)<2 for any prime p<\bar{p} . This proves the theorem. ∎ 3. Improved classical sequenceability (Proof of Theorem 1.3 ) We explain how the one-shot control of Type I and Type II intervals yields the improved classical bound. Here we work in the classical (non- t -weak) setting: we must avoid all nontrivial intervals. Proof of Theorem 1.3 . Let A\subseteq\mathbb{Z}_{k}\setminus\{0\} , and let us denote by p the least prime divisor of k . Apply the rectification/structure step (as in [ 4 ] ) with a choice of parameters that yields dissociated blocks of size R=R(A,k):=c_{1}\max\left((\log p)^{1/2},\frac{\log p}{\log|A|}\right)\,. We recall that the Structure Theorem of [ 4 ] holds for this value of R (the previous definition of R was functional to the weak-sequenceability result). Here we run the one-shot construction of Lemma 2.7 with K:=c_{2}R^{1/2}\qquad(c_{2}>0\ \text{sufficiently small}). In the classical setting, we use a union bound over all nontrivial intervals I\subset[1,|A|] . There are at most |A|^{2} such intervals. For Type II intervals, Lemma 2.7 (1) gives \mathbb{P}\Big(\sum_{i\in I}a_{i}=0\Big)\ \leq\ \exp\!\big(-\Theta(K\log R)\big)\ =\ \exp\!\big(-\Theta(R^{1/2}\log R)\big). Similarly for Type I intervals, Lemma 2.7 (2) gives \mathbb{P}\Big(\sum_{i\in I}a_{i}=0\Big)\ \leq\ \exp\!\big(-\Theta(R)\big). Hence \mathbb{P}(\exists\ \text{nontrivial }I:\ \sum_{i\in I}a_{i}=0)\ \leq\ |A|^{2}\exp\!\big(-\Theta(R^{1/2}\log R)\big)\ +\ |A|^{2}\exp\!\big(-\Theta(R)\big). Since |A|\leq\exp(c(\log p)^{1/3}) for c>0 sufficiently small then R is at least \Theta\big((\log p)^{2/3}\big) , we obtain that the right-hand side is o(1) . Therefore, if p is large enough (i.e. p\geq\bar{p} ), with positive probability, the sampled ordering contains no nontrivial zero-sum interval, i.e. it is a sequencing. Moreover we can chose c small enough so that \exp\!\big(c(\log p)^{1/3}\big)<2 for any prime p<\bar{p} . This proves the theorem. ∎ *