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
    Commented Oct 23, 2020 at 17:33
  • $\begingroup$ @RobPratt thank you. Edited. $\endgroup$ Commented Oct 23, 2020 at 17:40
  • 1
    $\begingroup$ Are the elements of $S$ generated from a uniform distribution on $[0,1]$? $\endgroup$
    – user44143
    Commented Oct 23, 2020 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$
    – user44143
    Commented Oct 23, 2020 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$ Commented Oct 24, 2020 at 22:59

2 Answers 2

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$ Commented Oct 27, 2020 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$
    – user44143
    Commented Oct 27, 2020 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$ Commented Oct 27, 2020 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$ Commented Oct 31, 2020 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
    Commented Nov 1, 2020 at 10:22
  • $\begingroup$ Yes, I understood it. Thank you again @QAMS ! $\endgroup$ Commented Nov 1, 2020 at 11:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .