Packing arithmetic progressions Thanks: The research of the first author was supported in part by NSF grant DMS-2154082 Thanks: The third author was supported in part by Narodowe Centrum Nauki, grant 2020/37/B/ST1/03298. Thanks: The fourth author was supported in part by the AGH University of Krakow, grant no. 16.16.420.054, funded by the Polish Ministry of Science and Higher Education. Noga Alon, Michał Dębski, Jarosław Grytczuk, Jakub Przybyło Abstract . Let ℱ = { A 1 , A 2 , … , A k } \mathcal{F}=\{A_{1},A_{2},\ldots,A_{k}\} be a collection of finite arithmetic progressions, where each A d A_{d} is an initial segment of the set D d = { d , 2 ​ d , 3 ​ d , … } D_{d}=\{d,2d,3d,\ldots\} of consecutive multiples of a positive integer d d . Let m ⁡ ( ℱ ) m(\mathcal{F}) denote the minimum length of an interval containing pairwise disjoint shifted copies of all members of the family ℱ \mathcal{F} . We study this parameter in the following two cases: for a fixed positive integer n n , (1) each progression in ℱ \mathcal{F} has the form A d = D d ∩ { 1 , 2 , … , n } A_{d}=D_{d}\cap\{1,2,\ldots,n\} , and (2) all progressions A d A_{d} of ℱ \mathcal{F} have the same size n n , that is, A d = D d ∩ { 1 , 2 , … , n ​ d } A_{d}=D_{d}\cap\{1,2,\ldots,nd\} . We in particular derive the following asymptotic estimates. In case (1), when k = n k=n , we get m ⁡ ( ℱ ) = Θ ⁡ ( n 3 / 2 / ln ⁡ n ) m(\mathcal{F})=\Theta(n^{3/2}/\ln n) . In case (2), when k = n k=n , we get m ⁡ ( ℱ ) = Θ ⁡ ( n 3 / ln ⁡ n ) m(\mathcal{F})=\Theta(n^{3}/\ln n) , while if k > k 0 ​ ( n ) k>k_{0}(n) , then m ⁡ ( ℱ ) < 3 ​ k ​ n m(\mathcal{F})<3kn . In both cases we additionally determine m ⁡ ( ℱ ) m(\mathcal{F}) asymptotically or settle its order of magnitude for all k < n kn , the paramater m_{k}(n) is not defined. In our first result we determine the asymptotic order of the function m(n) . Theorem 1 . We have m(n)=\Theta(n^{3/2}/\ln n) . More precisely, \left(\frac{4}{3}-o(1)\right)\frac{n^{3/2}}{\ln n}\leqslant m(n)\leqslant\left(\frac{5}{3}+o(1)\right)\frac{n^{3/2}}{\ln n}. It would be nice to close the gap between these bounds, and we suspect that the constant 4/3 is closer to the truth. Actually, the above lower bound holds even if we restrict the differences of arithmetic progressions to prime numbers not exceeding \sqrt{n} . On the other hand, if k\leqslant\sqrt{n} , then m_{k}(n)\leqslant(1.52+o(1))n^{3/2}/\ln n , while for k\ll\sqrt{n} , we have m_{k}(n)=(1+o(1))kn/\ln k , which is a certain indication in favor of the supposition (see Theorem 4 ). Secondly, we consider similar collections of initial segments of sets of multiples D_{d} having the same size n . More precisely, we investigate the packing problem for families \mathcal{G}=\{B_{1},B_{2},\ldots,B_{k}\} , where B_{d}=D_{d}\cap[nd]=\{id:1\leqslant i\leqslant n\} , with d\in[k] . As before, for any subset D of positive integers, we denote \mathcal{G}_{D}=\{B_{d}:d\in D\} . Also, the corresponding parameters are defined in the same way, and we denote them analogously by M_{D}(n)=m(\mathcal{G}_{D}) , M_{k}(n)=m(\mathcal{G}_{[k]}) , and M(n)=m(\mathcal{G}_{[n]}) . Our next result determines the asymptotic order of the function M(n) . Theorem 2 . We have M(n)=\Theta(n^{3}/\ln n) . More precisely, \left(\frac{1}{6}-o(1)\right)\frac{n^{3}}{\ln n}\leqslant M(n)\leqslant\left(0.526+o(1)\right)\frac{n^{3}}{\ln n}. In section 4 we formulate a more detailed version of the theorem with estimates for M_{k}(n) when k\leqslant n (see Theorem 5 ). Notice that the parameter M_{k}(n) is perfectly viable for k>n , unlike m_{k}(n) . For k much larger than n , by using different techniques, we get the following result. Theorem 3 . For every n\in\mathbb{N} there exists k_{0}=k_{0}(n) such that, for all k\geqslant k_{0} , we have M_{k}(n)\leqslant 3nk. Let us remark that a similar statement may be far from true for arbitrary families of n -element sets (with bounded diameter). Consider, for instance, the set S_{r}=\{1,2,\ldots,r,2r,3r,\ldots,(r+1)r\} of size |S_{r}|=2r=n . It is not hard to see that there is no way to pack two shifted copies of S_{r} so that they overlap. Hence, packing of k copies of S_{r} requires an interval of length at least kr(r+1)=\Omega(kn^{2}) . Similar examples can be constructed with reference to other results of this paper. The problem of packing arithmetic progressions with all gaps distinct emerged in connection to certain puzzles having a common flavor of searching for perfect matchings in hypergraphs defined by some distance constraints. One of them is the following problem of barricade building posed by Cipra and popularized by Guy [ 12 ] . Let S_{n} denote the set of all permutations of [n] . Two permutations, (a_{1},a_{2},\ldots,a_{n}) and (b_{1},b_{2},\ldots,b_{n}) , are dependent if a_{1}+\cdots+a_{i}=b_{1}+\cdots+b_{j} , for some i,j\in[n-1] . A subset A\subseteq S_{n} is independent if no two of its elements are dependent. What is the maximum size of an independent set in S_{n} ? An easy upper bound is \lfloor n/2\rfloor+1 and a natural conjecture is that it is attained. In [ 8 ] we proved that it is at least linear by using initially some packing arguments, like the ones investigated here. Another, more direct inspiration came from the puzzle of perfect rhythmic tilings , invented by Johnson [ 14 ] (see also [ 3 ] and [ 21 ] ). The task is to partition a segment [nk] into k arithmetic progressions, each with n terms, but no two with the same gap. Is it true that, for every fixed n , such tilings exist for all large enough k ? The answer is not known even for n=3 . Let us finally mention that structures of our interest occur also in the context of some more famous problems. For instance, the multiplication table problem of Erdős [ 9 ] (see [ 11 ] ) asks simply for the cardinality of the union B_{1}\cup\cdots\cup B_{n} of arithmetic progressions defined above, while the Arithmetic Kakeya Conjecture of Katz and Tao [ 15 ] (stated independently by Ruzsa [ 20 ] ), concerns the least possible size of the union (s_{1}+B_{1})\cup\cdots\cup(s_{k}+B_{k}) of their shifted copies. Even Riemann Hypothesis can be equivalently formulated by using a (slightly modified) incidence matrix of the family \{A_{1},A_{2},\ldots,A_{n}\} , known as the Redheffer matrix [ 18 ] , whose determinant coincides with the partial sum of the Möbius function (see [ 5 ] ). Proofs of the above stated results are presented in the three subsequent sections. The last section contains discussion together with some further simple results, as well as several open problems. Throughout the paper we use the standard asymptotic notation. In particular, we assume that values of n or k are sufficiently large whenever this is needed. The usual notation o(1) denotes a quantity that tends to 0 as the relevant parameter tends to infinity. Should this not be clear from context we will specify such parameter p by writing o_{p}(1) instead. The logarithm in the natural base e is denoted by \ln x , and \log x denotes logarithm in base 2 . 2. Bounds for m(n) ; Proof of Theorem 1 2.1. Preliminaries We examine packings of integer sets, hence an interval will be identified with integer points, sometimes called elements , within it – the number of these will be called the length of an interval. We will exploit several known estimates and will be mostly focused on asymptotic approximations. For definiteness of notation let us however assume that an interval of length x , where x is a real number, is assumed to contain \lfloor x\rfloor (integer) elements, unless explicitly stated otherwise. We say an integer set A fits in an interval I when there is its shifted copy s+A entirely contained in I . We will be in particular repeatedly using the following well-known consequences of the Prime Number Theorem. Lemma 1 . The sum of all primes up to x is (1+o(1))\frac{x^{2}}{2\ln x}, while the sum of squares of all primes up to x is (1+o(1))\frac{x^{3}}{3\ln x}. Let us further recall that an integer is y -smooth if its largest prime divisor is at most y . We will need the following result of Canfield, Erdős and Pomerance [ 7 ] , see also [ 6 ] . Lemma 2 ( [ 7 ] ) . If x=y^{u} where u tends to infinity with x , and y\geqslant(\ln x)^{1.001} , then the number of y -smooth integers that do not exceed x is \frac{x}{u^{(1+o(1))u}}, where the o(1) -term tends to 0 as x (and also y and u ) tend to infinity. We will also use the following simple fact. Lemma 3 . Let A and B be two integer subsets of an interval I of length g>n , and assume that B fits in an interval of length n . Suppose, further, that |A|\cdot|B|\sqrt{n} . Note that all progressions with differences equal to such primes can be packed in one interval of length n . Indeed, for each such p it suffices to place the corresponding progression A_{p} in [n] at positions congruent to 0\pmod{p} . By the Chinese Remainder Theorem, the resulting embeddings in [n] of any two such progressions A_{p} and A_{q} , with primes p>q>\sqrt{n} , cannot intersect, as desired. Likewise, we may pack all progressions A_{2p} , with prime p>\sqrt{n} , in a single (new) interval of length n , and so on. As all d\leqslant s divisible by a prime p>\sqrt{n} are of the form pg , where g\leqslant(\ln n)^{3} , we can fit all the corresponding progressions A_{d} disjointly in an interval of total length n(\ln n)^{3}=o(n^{3/2}/\ln n) . Secondly, note that for each fixed prime p such that \sqrt{s}\leqslant p\leqslant\sqrt{n} , all progressions A_{d} with differences d in the set D_{p}^{(s)} can be packed in one interval of length n , since |D_{p}^{(s)}|\leqslant s/p\leqslant p . As we will expose that the remaining progressions, considered in Step 4 below, require no additional space, this suffices to obtain the upper bound with multiplicative factor roughly 2 rather than 5/3 (or 4/3 ). Indeed, the number of such primes is at most (1+o(1))\sqrt{n}/\ln(\sqrt{n}) , by the Prime Number Theorem, so the total length of an interval required for these is at most (2+o(1))n^{3/2}/\ln n . We will however be more careful here and provide a tighter packing, admitting overlaps of minimal intervals containing A_{d} with d in selected sets D_{p}^{(s)} . First note that, by the above remarks, the progressions with differences in all sets D_{p}^{(s)} with \sqrt{s}\leqslant p\leqslant\sqrt{n}/\ln n , can be packed disjointly in an interval of length o(n^{3/2}/\ln n) , due to the Prime Number Theorem, which implies that the number of such primes p is o(\sqrt{n}/\ln n) . We are thus left with sets D_{p}^{(s)} where p are primes in the range \sqrt{n}/\ln np_{2}>\ldots>p_{h} be all prime numbers in the interval (\sqrt{n}/\ln n,\sqrt{n}] . By pairing every two consecutive primes of this collection and using the above overlapping packing in a separate interval for every such pair, we may pack disjointly all progressions with differences in D_{p_{1}}\cup\ldots\cup D_{p_{h}} in an interval of length at most (2.1) \displaystyle(1+o(1))n\frac{\sqrt{n}}{\ln(\sqrt{n})}-(1-o(1))\sum_{1\leqslant i\leqslant\lfloor h/2\rfloor}\left(p_{2i}\right)^{2} \displaystyle= \displaystyle(1+o(1))n\frac{\sqrt{n}}{\ln(\sqrt{n})}-(1-o(1))\frac{1}{2}\cdot\frac{(\sqrt{n})^{3}}{3\ln(\sqrt{n})} \displaystyle= \displaystyle\left(\frac{5}{3}-o(1)\right)\frac{n^{3/2}}{\ln n}, due to the Prime Number Theorem and Lemma 1 . Step 4: differences d>s . It is easy to see that the total size of all progressions in the investigated family \mathcal{F}=\{A_{1},A_{2},\ldots,A_{n}\} is only O(n\ln n) , while each of the remaining unpacked progressions is of size at most \sqrt{n}/(\ln n)^{3} . Therefore all of them can be packed one by one into the existing packing using Lemma 3 (with room to spare). This completes the proof of the upper bound and hence the proof of Theorem 1 . \Box 3. Bounds for m_{k}(n) with small k We will now be concerned with packing only the first k\sqrt{n} , the thesis of Theorem 1 remains valid and provides the right order of m_{k}(n) , since the corresponding lower bound exploits prime differences up to \sqrt{n} exclusively.) Theorem 4 . Let k and n be arbitrary positive integers, with k\leqslant\sqrt{n} . If k\ll\sqrt{n} , then m_{k}(n)=(1+o_{k}(1))\frac{kn}{\ln k}. Otherwise, if k\leqslant\sqrt{n/2} , then \left(1-\frac{k^{2}}{3n}-o(1)\right)\frac{kn}{\ln k}\leqslant m_{k}(n)\leqslant\left(1-\frac{k^{2}}{3n}+\frac{k^{2}}{48n}+o(1)\right)\frac{kn}{\ln k}, and if \sqrt{n/2}\leqslant k\leqslant\sqrt{n} , then \left(1-\frac{k^{2}}{3n}-o(1)\right)\frac{kn}{\ln k}\leqslant m_{k}(n)\leqslant\left(\frac{1}{2}+\frac{1}{3\sqrt{2}}\frac{\sqrt{n}}{k}+\frac{k^{2}}{48n}+o(1)\right)\frac{kn}{\ln k}. Proof. For the lower bound it again suffices to focus on progressions A_{p} with prime p\leqslant k . By the Prime Number Theorem, the number of such primes equals t=(1+o_{k}(1))k/\ln k . By the same reasoning as in the proof of Proposition 1 , since intervals including arithmetic progressions with differences given by the analyzed primes cannot overlap too much, any interval including disjoint copies of all these progressions cannot be shorter than \left(1-o_{k}(1)\right)nt-\frac{k^{3}}{3\ln k}, which concludes the proof of the lower bound in all cases. For the upper bound, note first that by Lemma 2 , the number of (\ln k)^{2} -smooth positive integers d\leqslant k is at most k^{1/2+o(1)} . So, the arithmetic progressions A_{d} with such differences can be packed in an interval of length (3.1) o_{k}\left(\frac{kn}{\ln k}\right). For a prime p , recall that D_{p}^{(k)}=D_{p}\cap[k]=\{d\leqslant k:p|d\} . Analogously as in the proof of Theorem 1 , for every fixed p\leqslant\sqrt{k} , any p progressions A_{d} with d\in D_{p}^{(k)} can be packed in [n] . Thus, all arithmetic progressions with differences in D_{p}^{(k)} for all primes p\in[(\ln k)^{2},\sqrt{k}] can be packed in an interval of total length at most (3.2) n\cdot\sum_{(\ln k)^{2}\leqslant p\leqslant\sqrt{k}}\left\lceil\frac{|D_{p}^{(k)}|}{p}\right\rceil\leqslant nk\cdot O\left(\sum_{p\geqslant(\ln k)^{2}}\frac{1}{p^{2}}\right)=O\left(\frac{kn}{(\ln k)^{2}}\right)=o_{k}\left(\frac{kn}{\ln k}\right). We are left with differences in D_{p}^{(k)} for primes satisfying \sqrt{k}p_{2}>\ldots>p_{z} be all (remaining) prime numbers in (k/2,k] . Since for each such p_{i} we have D_{p_{i}}^{(k)}=\{p_{i}\} , we may be more efficient in this regime and provide two-sided overlappings for shits of (almost) all A_{p_{i}} . Namely, by the Chinese Remainder Theorem, it is straightforward to assure that the intersection of any two intervals containing shifted copies of A_{p_{i}} and A_{p_{i+1}} has length at least (1-o_{k}(1))\min\{p_{i}p_{i+1},n/2\} , for every in/2 , we may bound the length of the shortest interval admitting packing of all progressions B_{d} with d\leqslant k by the same estimate as for k\leqslant n/2 above plus the following, which accounts for alteration of the formula in ( 4.1 ) for primes p>n/2 : \displaystyle(1+o(1))\left(\frac{1}{2}\sum_{p\in(n/2,k]\cap\mathbb{P}}np-\sum_{p\in(n/2,k]\cap\mathbb{P}}(pn-p^{2})\right) \displaystyle= \displaystyle(1+o(1))\left(\sum_{p\in(n/2,k]\cap\mathbb{P}}p^{2}-\frac{n}{2}\cdot\sum_{p\in(n/2,k]\cap\mathbb{P}}p\right) \displaystyle= \displaystyle(1+o(1))\left(\left(\frac{k^{3}}{3\ln k}-\frac{\left(\frac{n}{2}\right)^{3}}{3\ln k}\right)-\frac{n}{2}\cdot\left(\frac{k^{2}}{2\ln k}-\frac{\left(\frac{n}{2}\right)^{2}}{2\ln k}\right)\right) \displaystyle= \displaystyle(1+o(1))\left(\frac{1}{3}\cdot\frac{k^{3}}{\ln k}+\frac{1}{48}\cdot\frac{n^{3}}{\ln k}-\frac{1}{4}\cdot\frac{nk^{2}}{\ln k}\right). ∎ It seems that one of the key steps towards providing optimal multiplicative constants in Theorems 1 , 4 and 5 above should rely on understanding and designing appropriate packings of arithmetic progressions with prime differences. 5. Bound for M_{k}(n) when k\rightarrow\infty ; Proof of Theorem 3 In this section we prove Theorem 3 . To do so we first pack almost all arithmetic progressions from the collection \{B_{1},B_{2},\ldots,B_{k}\} into a cyclic interval of size nk , which will give us a packing of these progressions into [m] , with m\leqslant 2nk . The rest of the progressions can be packed in another interval of length nk (in fact, even a slightly shorter interval of length nk-k+o(n^{2}k) ), which jointly give the result as stated in Theorem 3 . We will use the known result about nearly perfect matchings in nearly-regular uniform hypergraphs with small co-degrees. The required statement, proved in [ 10 ] and [ 17 ] following the initial ideas of Rödl [ 19 ] , is stated in the following lemma. Recall that the maximum co-degree of a hypergraph is the maximum number of edges containing a fixed pair of vertices. Lemma 5 ( [ 10 ] , [ 17 ] ) . For every fixed t and \mu>0 there is a D_{0} and \delta>0 such that any t -uniform hypergraph on N vertices in which the degree of every vertex is between (1-\delta)D and (1+\delta)D , where D\geqslant D_{0} , and the maximum co-degree is at most \delta D , contains a matching covering all but at most \mu N vertices. In the result below a cycle of length r is simply the cyclic group \mathbb{Z}_{r} . Let \mathcal{G}_{n}(k)=\{B_{1},B_{2},\ldots,B_{k}\} be the family of arithmetic progressions B_{d}=\{d,2d,\ldots,nd\} , with d\in[k] . Theorem 6 . Let n be a fixed positive integer. For every \epsilon>0 there exists k_{0} such that for every k\geqslant k_{0} , there is a set of at least (1-\epsilon)k distinct arithmetic progressions from the family \mathcal{G}_{n}(k) that can be packed into a cycle of length nk . Proof. Put t=n+1 , \mu=\epsilon/(n+1) , N=nk+k , and consider the following t -uniform hypergraph on the set of N vertices [k]\cup\mathbb{Z}_{nk} . For each d\in[k] there are kn edges, where the first vertex of each of these edges is d\in[k] and the other n vertices are a cyclic shift of the progression B_{d} in \mathbb{Z}_{nk} . Note that this hypergraph is D=kn -regular. It is also easy to check that the maximum co-degree in it is smaller than n^{3} . As n (and hence t ) are fixed, if k is sufficiently large, then by Lemma 5 the hypergraph contains a matching covering all vertices besides at most \epsilon k(=\mu N) of them. This gives the required progressions. ∎ The assertion of Theorem 3 follows quickly from the last result. As mentioned above, the cyclic packing gives a packing of almost all progressions into [m]=[2nk] . The rest of the progressions can be packed in another interval of length nk-k+o(n^{2}k) using Lemma 3 . 6. Concluding remarks and open problems 6.1. Error correcting codes and Ferres shapes The packing problem considered here is similar in spirit to many packing problems in discrete mathematics. A prominent example is the main combinatorial problem in Coding Theory. Here the objective is to pack shifts of m Hamming balls of binary vectors of a given length n and radius r in the Hamming cube \{0,1\}^{n} , where the shifts are performed in the group \mathbb{Z}_{2}^{n} . The existence of such a packing with no overlap is equivalent to the existence of a binary error correcting code with m codewords, length n , and distance at least 2r+1 . See, e.g., [ 16 ] and the references therein for the many relevant known results and open problems. Another example of a problem of this type is discussed in [ 1 ] . The main result there is that the maximum fraction of all the p(n) Ferrers shapes corresponding to partitions of an integer n that can be packed with no overlap in a rectangle of length n\times p(n) is O(1/\log n) . Note that here the shifts are two-dimensional. This can be used to show that the smallest length t=t(n) of an n by t rectangle in which shifts of all the p(n) shapes can be packed with no overlap is at least \Omega(p(n)\log n) . Indeed, we can cover any n by cp(n)\log n rectangle by, say, c\log n+1 subrectangles, each of height n and length smaller than p(n) , so that consecutive rectangles have an overlap of a common n by n square. If the original rectangle contains all the Ferrers shapes, then each shape is fully contained in one of the smaller rectangles, which cannot cover a fraction of at least 1/(c\log n+1) of all shapes for an appropriately chosen constant c . Therefore t(n)>cp(n)\log n for some absolute constant c>0 . It is not too difficult to show that this is tight up to the absolute constant c . Indeed, by the Hardy-Ramanujan asymptotic formula for the number of shapes of size n , see, e.g., [ 4 ] , (6.1) p(n)=(1+o(1))\frac{e^{C\sqrt{n}}}{4n\sqrt{3}}, where C=\pi\sqrt{\frac{2}{3}} , and the o(1) -term tends to 0 as n tends to infinity. This easily implies that the number of shapes in which the first row x_{1} or the first column y_{1} is larger than A\sqrt{n}\log n is less than p(n)/n for an appropriate absolute constant A . (To see this note that the number of shapes with first row of length x_{1} is p(n-x_{1}) and a similar formula holds for the first column.) We can thus first omit all these exceptional shapes, pack all the others in an n by O(p(n)\log n) rectangle using the packing along diagonals described in the final remark of [ 1 ] , and complete the packing by appending one additional n by n square for each of the remaining exceptional shapes. 6.2. Progressions with prime differences Our main result in Theorem 1 shows that, somewhat surprisingly, the minimum length of an interval in which all the n progressions A_{d} with differences d\in[n] can be packed with no overlap is the same, up to a constant factor, as the length required for all prime differences p\leqslant\sqrt{n} . Moreover, a close look at the proof reveals that it implies the following. Proposition 2 . For any \epsilon>0 there exists \delta=\delta(\epsilon)>0 so that the following holds. Let F be the set of all differences d\leqslant\sqrt{n}(\ln n)^{3} divisible by a prime p , with \delta\sqrt{n}\leqslant p\leqslant\sqrt{n} . Then, m_{[n]-F}(n)\leqslant\epsilon\frac{n^{3/2}}{\ln n}(<\epsilon m(n)). Therefore, (1-\epsilon)m(n)\leqslant m_{F}(n)(\leqslant m(n)). Proof. The total length required for packing the progressions with differences considered in steps 1,2, and 4 in the proof of the upper bound of Theorem 1 is o(n^{3/2}/\ln n)=o(m(n)). The same holds for differences d which are considered in step 3 and are divisible by a prime p>\sqrt{n} . By our argument in step 3, the contribution from the remaining differences from this step which are divisible by a prime smaller than \delta\sqrt{n} is at most n times the number of these primes. The desired result thus follows by the Prime Number Theorem. ∎ 6.3. Beyond arithmetic progressions with bounded diameter The upper bound in Theorem 1 applies the arithmetic properties of the progressions, besides the fact that their sizes are \lfloor n/d\rfloor , for 1\leqslant d\leqslant n . The sizes themselves (along with the diameter constraint) suffice to imply that the sets can be packed in an interval of length \Theta(n^{3/2}) , and this is tight up to the hidden constant in the \Theta notation. This is proved in the following simple statement, in which we do not make a serious attempt to optimize the absolute constants. Proposition 3 . Let C_{i} , 1\leqslant i\leqslant n , be an arbitrary collection of subsets of [n] , where for all admissible i , |C_{i}|=\lfloor\frac{n}{i}\rfloor . Then there are shifts r_{i}+C_{i} that can be packed in an interval of length at most (1+1/e+o(1))n^{3/2} . This is tight up to the constant factor, that is, there are such sets C_{i} that cannot be packed in an interval of length smaller than (1+o(1))n^{3/2}/2 . Proof. The first \sqrt{n} sets C_{i} can clearly be packed in an interval of length n^{3/2} by shifting each C_{i} to a separate interval of length n . Starting then with an empty new interval of length bn^{3/2} we pack shifts of the sets C_{i} for i>\sqrt{n} one by one, in order, using Lemma 3 . When trying to embed the set C_{x} , the total size of the sets embedded so far (in this new interval) is at most \sum_{\sqrt{n}\sqrt{n} at x=e\sqrt{n} , where its value is 1/(e\sqrt{n}) . Therefore, the inequality in ( 6.2 ) holds for any fixed b>1/e (and sufficiently large n ). This establishes the first part of the proposition. To see that it is tight up to a constant factor consider an example in which each of the first \sqrt{n}/2 sets C_{i} contains the interval [\sqrt{n}]=\{1,2,\ldots,\sqrt{n}\} as well as the arithmetic progression \{\sqrt{n},2\sqrt{n},3\sqrt{n},\ldots,n\} (assume, for simplicity, that \sqrt{n} is an integer.) Then in any disjoint packing of shifts of these \sqrt{n}/2 sets C_{i} , no two intervals of length n containing the shifted C_{i} can have a nonempty overlap. This completes the proof of the proposition. ∎ The constants in the upper bound and in the lower bound in the last proposition can be improved by being a bit more careful. In the upper bound the constant can be improved to \frac{2}{\sqrt{e}}+o(1) . This is done by embedding each of the first \lfloor\frac{\sqrt{n}}{\sqrt{e}}\rfloor sets C_{i} in a separate interval of length n , and then by embedding the remaining sets C_{i} , in order, one by one, using Lemma 3 , in another interval of length (\frac{1}{\sqrt{e}}+o(1))n^{3/2} . The constant in the lower bound can be improved to \ln 2+o(1) . To do so, add to the initial sets C_{i} for i\leqslant\sqrt{n}/2 described above additional sets C_{j} for \sqrt{n}/2