An isoperimetric inequality for word overlap Dmitrii Zakharov Abstract . Let A A and B B be sets of words of length n n over some finite alphabet. Suppose that no suffix of a word in A A coincides with a prefix of a word in B B . Then we show that the product of densities of A A and B B is upper bounded by ( 1 + o ⁡ ( 1 ) ) / ( e ​ n ) (1+o(1))/(en) . This bound is asymptotically sharp. 1. Introduction Let \Omega be a finite set and let n\geqslant 2 . Let \mu=\mu_{n} be the uniform probability measure on \Omega^{n} . We say that an ordered pair of words (w,u)\in\Omega^{n}\times\Omega^{n} overlaps if a final segment of w coincides with an initial segment of u . That is, if we denote w=(w_{1},\ldots,w_{n}) , u=(u_{1},\ldots,u_{n}) then for some j\in\{1,\ldots,n\} we have (w_{n-j+1},\ldots,w_{n})=(u_{1},\ldots,u_{j}) . Note that we in particular allow u=w . We are interested in the following extremal question: suppose that A,B\subset\Omega^{n} are sets of words such that no two words w\in A and u\in B overlap. For what pairs of densities \alpha,\beta\in(0,1) is it possible to have \mu(A)\geqslant\alpha and \mu(B)\geqslant\beta ? There is a related question about non-overlapping codes (also known as ‘cross-bifix-free’ codes) that has been extensively studied in the computer science literature [ 2 , 3 , 4 , 8 , 9 ] . In our notation, the question is to determine the size of a largest code A\subset\Omega^{n} such that no two distinct words in A overlap (see [ 4 ] for an asymptotically sharp construction). So the question we consider can be thought of as a bipartite variant of this and, to the best of our knowledge, it has not been studied before. Define the shift map s=s_{n}:\Omega^{n}\rightarrow\Omega^{n-1} by s(w_{1},\ldots,w_{n})=(w_{2},\ldots,w_{n}). For a subset A\subset\Omega^{n} we can define the set of words which do not overlap with A as follows: U=U(A)=\Omega^{n}\setminus\bigcup_{j=0}^{n-1}s^{j}(A)\times\Omega^{j}. It is easy to see that U(A) is precisely the set of all u such that the pair (w,u) does not overlap for all w\in A . Let \gamma(\alpha,n) be the largest possible measure of the set U(A) over all A\subset\Omega^{n} of measure \alpha and all finite sets \Omega . Here we consider the uniform measure on the space \Omega^{n} . Note that if A\subset A^{\prime} then we have the inclusion U(A^{\prime})\subset U(A) . This means that \gamma(\alpha,n) is a monotone decreasing function in \alpha . For example, it is an easy exercise to show that \gamma(\alpha,2)=\max\{(1-\alpha)^{2},~1-\alpha^{1/2}\} holds for any \alpha\in(0,1) . Our result is the following estimate. Theorem 1.1 . We have \gamma(\alpha,n)\leqslant\big(\frac{n}{n+1}\big)^{n+1}\cdot\frac{1}{\alpha n} for all n\geqslant 1 and \alpha\in(0,1) . So if we have a pair of non-overlapping sets A,B\subset\Omega^{n} with densities \alpha and \beta then we have \alpha\beta n\leqslant\big(\frac{n}{n+1}\big)^{n}=(1/e+o(1)) . The proof of Theorem 1.1 is presented in the next section. The rough idea is to split the set \Omega^{n}\setminus U(A) into several disjoint pieces and use inclusion-exclusion to lower bound the size of each piece. This then gives a certain recursive relationship between various densities associated with A and U(A) and their shifts. A careful algebraic manipulation completes the proof. We close this section by considering some examples essentially matching the upper bound in Theorem 1.1 . Let S\subset\Omega be an arbitrary subset. Then for A=S^{n} one can check that U(A)=(\Omega\setminus S)\times\Omega^{n-1} and so we get \mu(U(A))=1-\alpha^{1/n}=\frac{\log(1/\alpha)}{n}+O\left(\frac{\log^{2}(1/\alpha)}{n^{2}}\right). This is a good bound for \alpha\in(1/2,1) . Similarly, for A=\Omega^{n-1}\times S one can check that U(A)=(\Omega\setminus S)^{n} so that we get \mu(U(A))=(1-\alpha)^{n}. This is a good bound for \alpha\in(0,1/n) . We can interpolate between these two examples by taking A=\Omega^{n-k}\times S^{k} for some 1\leqslant k\leqslant n . Then the set U=U(A) is given by \displaystyle U=\{(w_{1},\ldots,w_{n}):~w_{1}\not\in S,\quad\{w_{j+1},\ldots,w_{j+k}\}\not\subset S,~j=0,\ldots,n-k\}. The exact formula for \mu(U) is a bit complicated (it involves generalized Fibonacci numbers, see [ 4 ] ) but we can use a simple Poisson approximation inequality due to [ 1 ] (see also [ 6 , 5 , 7 ] ) to get a good estimate of the measure of U . Denote p=|S|/|\Omega| so that \alpha=p^{k} . Let Z_{1},\ldots,Z_{n-1}\sim\operatorname{Ber}(p) be iid Bernoulli random variables. Let R_{n-1} be the length of the longest run of 1-s in the sequence (Z_{1},\ldots,Z_{n-1}) . The measure of U can then be computed in terms of R_{n-1} : \mu(U)=(1-p)\Pr[R_{n-1}0 multiply both sides by \rho^{j-1} and sum over j=1,\ldots,n : \displaystyle\sum_{j=1}^{n}\rho^{j-1}\delta_{j}\geqslant \displaystyle\sum_{j=1}^{n}\rho^{j-1}\left(\gamma_{j}-\sum_{i=1}^{j-1}\gamma_{i}\delta_{j-i}\right) (3) \displaystyle= \displaystyle\sum_{j=1}^{n}\rho^{j-1}\gamma_{j}\left(1-\sum_{i=1}^{n-j}\rho^{i}\delta_{i}\right) Now let us define F(\rho)=\sum_{j=1}^{n}\delta_{j}\rho^{j} . Notice that F(1)=\delta_{1}+\ldots+\delta_{n}=1-\alpha<1 and F is strictly increasing on [1,\infty) . Thus, there exists a unique \rho>1 such that F(\rho)=1 . For this \rho , all brackets on the right hand side of ( 3 ) are non-negative. So using \gamma_{n}\leqslant\gamma_{j} we obtain \displaystyle\rho^{-1}=\rho^{-1}F(\rho) \displaystyle=\sum_{j=1}^{n}\rho^{j-1}\delta_{j}\geqslant\gamma_{n}\sum_{j=1}^{n}\rho^{j-1}\left(1-\sum_{i=1}^{n-j}\rho^{i}\delta_{i}\right) \displaystyle=\gamma_{n}\left(\frac{\rho^{n}-1}{\rho-1}-\sum_{i=1}^{n}\delta_{i}\frac{\rho^{n}-\rho^{i}}{\rho-1}\right) \displaystyle=\gamma_{n}\frac{\alpha\rho^{n}+F(\rho)-1}{\rho-1}=\alpha\gamma_{n}\frac{\rho^{n}}{\rho-1}. We conclude that \alpha\gamma_{n}\leqslant\frac{\rho-1}{\rho^{n+1}} for some \rho>1 . By computing the derivative, one can verify that the right hand side is maximized at \rho=\frac{n+1}{n} . We conclude that \alpha\gamma_{n}\leqslant\frac{1}{n}\left(\frac{n}{n+1}\right)^{n+1}\leqslant\frac{1}{en} , concluding the proof. We have the following corollary of Theorem 1.1 , which gives a ‘small level set’ estimate for the union of shift sets s^{j}(A)\times\Omega^{n-j} . Corollary 2.2 . Let A\subset\Omega^{n} be a set of measure \alpha\in(0,1) . For w\in\Omega^{n} define f(w) to be the number of indices j\in\{0,\ldots,n-1\} such that w\in s^{j}(A)\times\Omega^{j} . Then for every integer t\in[1,n/4] we have the following level set estimate on f : (4) \mu(\{w\in\Omega^{n}:~f(w)\leqslant t\})\leqslant\frac{4t}{\alpha n}. For example, by taking t=\alpha n/8 and assuming that \alpha\geqslant 1/n , we obtain that at least half of elements w\in\Omega^{n} is covered by at least \alpha n/8 many sets of the form s^{j}(A)\times\Omega^{j} . Taking t=1 on the other hand recovers Theorem 1.1 in the range \alpha\in(1/n,1/2) , albeit with a constant factor loss. Proof. If t\geqslant\alpha n/2 then there is nothing to prove, so we may assume t\leqslant\alpha n/2 holds. Let \tilde{n}=[n/2t] and r=n-2t\tilde{n} . By the assumption on t we have \tilde{n}\geqslant 1 . Consider a new alphabet \tilde{\Omega}=\Omega^{2t} and let \tilde{s}=\tilde{s}_{j}:\tilde{\Omega}^{j}\rightarrow\tilde{\Omega}^{j-1} denote the shift map defined on words over the alphabet \tilde{\Omega} . By identifying \tilde{\Omega}^{j}=\Omega^{2tj} , we get that \tilde{s}=s^{2t} . For i=0,\ldots,2t-1 let \tilde{A}_{i}=s^{r+i}(A)\times\Omega^{i}\subset\Omega^{2t\tilde{n}}=\tilde{\Omega}^{\tilde{n}}. Note that \mu(\tilde{A}_{i})\geqslant\mu(A)=\alpha for i=0,\ldots,2t-1 . For an arbitrary subset \tilde{A}\subset\tilde{\Omega}^{\tilde{n}} we denote \tilde{U}(\tilde{A})=\tilde{\Omega}^{\tilde{n}}\setminus\bigcup_{j=0}^{\tilde{n}-1}\tilde{s}^{j}(\tilde{A})\times\tilde{\Omega}^{j} , that is the analogue of U(A) over the new alphabet. Let w\in\Omega^{n} and denote \tilde{w}=s^{r}(w)\in\tilde{\Omega}^{\tilde{n}} . Note that we have \tilde{w}\not\in\tilde{U}(\tilde{A}_{i}) precisely when there exists j\in\{0,\ldots,\tilde{n}-1\} such that \tilde{w}\in\tilde{s}^{j}(\tilde{A}_{i})\times\tilde{\Omega}^{j} . The latter is in turn equivalent to w\in s^{2tj+i+r}(A) . It follows that we have \#\{i\in\{0,\ldots,2t-1\}:\tilde{w}\not\in\tilde{U}(\tilde{A}_{i})\}\leqslant\#\{i\in\{0,\ldots,n-1\}:w\in s^{i}(A)\times\Omega^{i}\}=f(w) Thus, if f(w)\leqslant t then there are at least 2t-t=t indices i\in\{0,\ldots,2t-1\} such that \tilde{w}\in\tilde{U}(\tilde{A}_{i}) . So by the union bound and Theorem 1.1 applied to each \tilde{U}(\tilde{A}_{i}) we have t\mu(\{w:~f(w)\leqslant t\})\leqslant\sum_{i=0}^{2t-1}\mu(\tilde{U}(\tilde{A}_{i}))\leqslant 2t\cdot\frac{(n/(n+1))^{n}}{\alpha\tilde{n}}\leqslant\frac{t}{\alpha\tilde{n}}. So recalling that \tilde{n}=[n/2t] we get \mu(\{w:~f(w)\leqslant t\})\leqslant\frac{1}{\alpha[n/2t]}\leqslant\frac{4t}{\alpha n} provided that n\geqslant 4t , concluding the proof. \Box