2
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ What are $r$ and $n$? $\endgroup$ – RobPratt Oct 23 '20 at 17:33
  • $\begingroup$ @RobPratt thank you. Edited. $\endgroup$ – Penelope Benenati Oct 23 '20 at 17:40
  • 1
    $\begingroup$ Are the elements of $S$ generated from a uniform distribution on $[0,1]$? $\endgroup$ – Matt F. Oct 23 '20 at 18:14
  • 1
    $\begingroup$ 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$. $\endgroup$ – Matt F. Oct 23 '20 at 18:32
  • 1
    $\begingroup$ @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. $\endgroup$ – Penelope Benenati Oct 24 '20 at 22:59
2
+50
$\begingroup$

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$:

enter image description here

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:

enter image description here

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – Penelope Benenati Oct 27 '20 at 13:14
  • $\begingroup$ 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$. $\endgroup$ – Matt F. Oct 27 '20 at 17:11
  • $\begingroup$ 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! $\endgroup$ – Penelope Benenati Oct 27 '20 at 17:31
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$ – Penelope Benenati Oct 31 '20 at 20:07
  • 1
    $\begingroup$ 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. $\endgroup$ – QAMS Nov 1 '20 at 10:22
  • $\begingroup$ Yes, I understood it. Thank you again @QAMS ! $\endgroup$ – Penelope Benenati Nov 1 '20 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.