# Combinatorial optimization problem with interdependent constraints on points in $[0,1]$

We are given a set $$S$$ of $$n$$ real numbers in $$[0,1]$$, with $$0,1\in S$$, and a value $$\alpha\in(0,1/2)$$. For each ordered triplet $$(i,j,k)$$ of values contained in $$S$$ (with $$i\le j \le k$$), we define its length as the difference $$k-i$$. Let $$L(\alpha)$$ be the sum of the lengths of all ordered triplets in $$S$$ such that we have $$j-i\le \alpha\,(k-i)$$ or $$k-j\le \alpha\,(k-i)$$, and let $$L'(\alpha)$$ be the sum of the lengths of all other ordered triplets in $$S$$.

Question: How can we find a lower bound for the ratio $$\rho(\alpha)=\frac{L(\alpha)}{L'(\alpha)}$$ when $$n\to\infty$$?

Can we use a one-dimensional packing/covering argument for finding it?

• What are $r$ and $n$? – RobPratt Oct 23 '20 at 17:33
• @RobPratt thank you. Edited. – Penelope Benenati Oct 23 '20 at 17:40
• Are the elements of $S$ generated from a uniform distribution on $[0,1]$? – Matt F. Oct 23 '20 at 18:14
• I'd conjecture (and I'm content to leave it as a conjecture) that the lower bound comes from when $S$ has a uniform distribution, and that for such a distribution $\rho(\alpha)=2\alpha/(1-2\alpha)$, assuming $\alpha<1/2$. This seems like the way to get the greatest number of $j$'s in the middle between $i$ and $k$. – Matt F. Oct 23 '20 at 18:32
• @MattF. I made some numerical simulations. It seems that, for $\alpha\in (0,1/2)$, if the points are placed with a non-uniform distribution which concentrates them in the middle of the interval $[0,1]$, i.e., the more we get close to the middle of the interval $[0,1]$, the smaller is the distance between two consecutive points, then the ratio $\rho(\alpha)$ is smaller than the one obtained using a uniform distribution. – Penelope Benenati Oct 24 '20 at 22:59

Suppose $$S_t$$ is distributed on $$[0,1]$$ with the pdf $$\frac{1+30\,t\,x^2(1-x)^2}{1+t},$$ which is one way to get a distribution as suggested in the comments with concentration in the middle. The graph below shows the pdfs for $$t=0$$ (the uniform distribution) and $$t=4$$:

Then $$E[k-i|S_t]=\frac{77+132t+50t^2}{924(1+t)^2}$$ and $$\rho(\alpha|S_t)$$ has a more complicated algebraic expression in terms of $$\alpha$$ and $$t$$.

This allows us to show that the uniform distribution does not minimize $$\rho$$, though it may come close. Specifically, $$\rho(\alpha|S_4)<\rho(\alpha|S_0)$$ for any $$0<\alpha<1/2$$. Here is a graph of those two functions:

This $$\rho(\alpha|S_4)$$ comes close to the minimum among all $$\rho(\alpha|S_t)$$ whenever $$0<\alpha<1/2$$. Probably there are families of distributions other than $$S_t$$ which would get lower values still.

• Thank you @MattF for your answer. Do you think that what you obtain can be useful to find a lower bound (although a bit loose), instead of a tight upper bound for the minimum value value of $\rho$? What kind of guarantees can we have about an upper bound (not necessarily very tight) of the gap between what you found and the real minimum? – Penelope Benenati Oct 27 '20 at 13:14
• I only know that you can probably get lower values, eg by mixing the uniform distribution and other beta distributions. It might be possible to get something more rigorous for a particular value of $\alpha$. – Matt F. Oct 27 '20 at 17:11
• I meant that I appreciate your answer, but I am looking for a lower bound, as I wrote in my question. Hence, I prefer a (possibly very loose) lower bound rather than a very tight upper bound -- if we do not know how much it is tight (but if we knew it, we would get a lower bound too, which is what I am looking for).Thanks! – Penelope Benenati Oct 27 '20 at 17:31

I don't know a good answer, but the following seems to give some lower bound.

First, define $$\rho(n,\alpha) \equiv \inf_{|S| = n} \rho_{S}(\alpha)$$. Next, fix a set $$S$$, and for $$T \subset S$$ define $$L_{T}(\alpha)$$, $$L_{T}'(\alpha)$$ in the obvious way. Then for fixed $$3 \leq k \leq |S|$$, I believe that

$$\rho_{S}(\alpha) = \frac{L_{S}(\alpha)}{L_{S}'(\alpha)} = \frac{\sum_{|T| = k, T \subset S} L_{T}(\alpha)}{\sum_{|T| = k, T \subset S} L_{T}'(\alpha)} \geq \rho(k,\alpha),$$

where the second equality follows from the fact that each triple is counted exactly $${k \choose 3}$$ times in both numerator and denominator.

But this tells us that $$\rho(n,\alpha)$$ is monotone-increasing in $$n$$, and that we can get a lower bound on your limit by getting a lower bound for any finite $$n$$ (and of course this is "sharp" in the sense that it will eventually recover the right answer).

Getting some lower bound for fixed $$n$$ and $$\alpha$$ doesn't seem as hard as the original problem. For example, for $$n = 4$$, we observe the following. Let's write $$S = \{0,a,b,1\}$$ and assume $$L_{S}(\alpha) = 0$$. Looking at the various triples, we find: $$a \in (\alpha b, (1-\alpha)b)$$ and $$a,b \in (\alpha, 1-\alpha)$$. But then combining these we see $$a \in (\alpha^{2}, (1-\alpha)^{2})$$ as well. So $$a \in (\alpha, 1-\alpha) \cap (\alpha^{2}, (1-\alpha)^{2})$$. But this is impossible if $$\alpha > (1-\alpha)^{2}$$, which happens for $$\alpha > \frac{3 - \sqrt{5}}{2} \approx 0.382$$. Thus, $$\rho(n,\alpha) \geq \frac{1}{3}$$ for all $$\alpha \geq 0.382$$ and all $$n \geq 4$$. For any fixed $$\alpha$$, basically the same calculation immediately gives some bound for sufficiently large $$n$$, and thus a nondegenerate bound on $$\rho(\alpha)$$.

Edited to add: since this was unclear, I'll do the same calculation for large $$n$$. Consider $$S = \{0,s_{1},\ldots,s_{n},1\}$$. Then to have $$L_{S}(\alpha) =0$$, we must have $$s_{n} \in (\alpha,1-\alpha)$$, $$s_{n-1} \in (\alpha s_{n}, (1-\alpha)s_{n}) \subset (\alpha^{2}, (1-\alpha)^{2})$$, $$s_{n-2} \in (\alpha^{3},(1-\alpha)^{3})$$, and iterating $$s_{1} \in (\alpha^{n}, (1-\alpha)^{n})$$. But of course we must also have $$s_{1} \in (\alpha,1-\alpha)$$. This is impossible if $$\alpha > (1-\alpha)^{n}$$, and of course for any fixed $$\alpha > 0$$ this inequality is violated for all $$n > \frac{\log(1-\alpha)}{\log(\alpha)}$$ sufficiently large. Set $$N(\alpha) = \frac{\log(1-\alpha)}{\log(\alpha)}$$; this shows that $$\rho(\alpha) > {N(\alpha) + 2 \choose 3}^{-1}$$.

This is of course a terrible bound, and going further by hand seems fairly tedious. However I'd guess that doing it by a computer is probably not too bad for moderate $$n$$ - as with the above calculation, you end up with some finite list of conditions, and checking whether any particular set is simultaneously-satisfiable is just checking to see if the intersection of a bunch of half-spaces is empty.

This naive algorithm does have running time that is exponential in $$n$$, so e.g. getting the right answer for $$n=40$$ is probably not feasible this way... but of course if you just want lower bounds you don't actually need to check everything, and I would guess that you could do a faster and more targeted search with a few minutes thinking about the "bad" cases.

As an aside: there is a famous problem about "arithmetic progressions," and people often talk about "approximate" arithmetic progressions in this context. What you're doing here sounded somewhat familiar, though I don't know if their techniques work when $$\alpha$$ is quite small (those arithmetic progressions are very approximate). Unfortunately I'm nothing like an expert, it has been a long time since I've looked at the subject, and my old notes are in my office so I can't check very quickly right now. There is a nice book on additive combinatorics which relates (approximate) arithmetic progressions to Fourier analysis, and it might be worth taking a look.

• Thank you very much for your comment @QAMS ! It seems somewhat difficult to generalize your result when $\alpha$ is small and $n$ is large. I would be happy to obtain a result even for a finite large value of $n$ (for instance $n=10^3$ or $n=10^6$) and for a small value of $\alpha$ (e.g., $\alpha\le 1/10$). Anyway, I think there are several inspiring insights in your comment. Finally, I just posted a question whose answer is likely, in my opinion, to be useful for finding the lower bound I am looking for (mathoverflow.net/q/375356/115803). – Penelope Benenati Oct 31 '20 at 20:07
• I added an explicit (bad) bound for all $0 < \alpha < 0.5$. Presumably one could do much better by spending a few hours on a computer, but I haven't tried. – QAMS Nov 1 '20 at 10:22
• Yes, I understood it. Thank you again @QAMS ! – Penelope Benenati Nov 1 '20 at 11:04