8
$\begingroup$

Chebyshev got famous showing that if the limit $l:=\lim_{x\to\infty}\frac{\pi(x)}{x/\log x}$ exists, then necessarily $l=1$, constituting a major breakthrough towards a proof of the famous prime number theorem conjectured by Gauss and Legendre. What I would like to know is whether other famous similar results are known both inside and outside the realm of number theory, and if general probability theorems can be used to obtain such results (like mimicking a deterministic quantity by a random variable that follows a given distribution law, the sum of expected values of which converges almost surely to the desired value of the considered limit, or the like).

Many thanks in advance.

$\endgroup$
4
  • $\begingroup$ See section 2 of cs.toronto.edu/~yuvalf/CLT.pdf (also perhaps books.google.com/books?id=Q4XzBwAAQBAJ as mentioned in section 10 of the PDF), from which I quote: "the real content of the central limit theorem is that convergence does take place. The exact form of the basin of attraction is deducible beforehand - the only question is whether summing up lots of independent variables and normalizing them accordingly would get us closer and closer to the only possible limit, a normal distribution with the limiting mean and variance." $\endgroup$ Apr 6, 2016 at 20:17
  • 2
    $\begingroup$ On a much lower level, if the limit of the sequence $$\sqrt2,\sqrt2^{\sqrt2},\sqrt2^{\sqrt2^{\sqrt2}},\dots$$ exists, then it must be a solution of $\sqrt2^x=x$, hence, 2 (or 4). $\endgroup$ Apr 6, 2016 at 23:10
  • 1
    $\begingroup$ Not quite of this form, but zero-one laws are certainly famous: en.wikipedia.org/wiki/Zero%E2%80%93one_law $\endgroup$
    – Terry Tao
    Apr 7, 2016 at 0:19
  • $\begingroup$ One way to have such a result would be to show that a subsequence converges to a particular limit. Iosif Pinelis's LLN example is of this form. Another similar example would be to show that the sequence converges in a weaker topology. $\endgroup$ Apr 7, 2016 at 13:16

2 Answers 2

4
$\begingroup$

The story with sharp thresholds for random constraint satisfaction problems somewhat fits into this picture. In the random k-SAT problem with $n$ Boolean variables, one includes each of the $2^k \binom{n}{k}$ potential clauses independently with probability $p$, where $p$ is chosen so that the expected clause density (number of clauses over number of variables) is some fixed constant $\alpha$.

It is very widely believed that for each $k$ there is a critical density $\alpha_k$ such that for all $\epsilon > 0$ the following holds:

  • if $\alpha \leq (1-\epsilon)\alpha_k$ then the resulting formula is satisfiable with probability $1-o(1)$;
  • if $\alpha \geq (1+\epsilon)\alpha_k$ then the resulting formula is unsatisfiable with probability $1-o(1)$.

However in general the existence of this $\alpha_k$ is unknown. Friedgut's Theorem [Fri99] comes extremely close to showing that $\alpha_k$ exists. His result implies that for each $k$ the above statement is true for a sequence of real numbers $\alpha_k(n)$ depending on the number of variables. (It is also easy to show that $\alpha_k(n)$ is bounded in the range $[1,2^k \ln 2]$ for all $n$.) It's utterly inconceivable that this sequence could oscillate, rather than tend to a limit, but in general this hasn't been proven.

For each $k$, the value of $\alpha_k$ is "known", via sophisticated heuristics from statistical physics [MPZ02, MMZ06]. In this sense, we sort of have an example answering Sylvain's question.

In a recent major breakthrough, Ding, Sly, and Sun rigorously established the physics prediction for $\alpha_k$ for all sufficiently large $k$. It is worth mentioning that this does not obviate the need for Friedgut's Theorem; by virtue of that theorem, it was enough for Ding--Sly--Sun to show that

  • if $\alpha < \alpha_k$, the random k-SAT formula is satisfiable with probability bounded away from 0.

[Fri99] Ehud Friedgut, Sharp thresholds of graph properties, and the $k$-sat problem, J. Amer. Math. Soc. 12 (1999), no. 4, 1017--1054.

[MMZ06] Stephan Mertens, Marc Mézard, and Riccardo Zecchina, Threshold values of random $K$-SAT from the cavity method, Random Structures Algorithms 28 (2006), no. 3, 340--373.

$\endgroup$
1
  • $\begingroup$ I agree that that $a_k(n)$ seems more likely to converge than not but wouldn't go as far as saying that some eventual oscillation is "utterly inconceivable" - is there some specific intuition for this stronger sense? $\endgroup$ Oct 20, 2017 at 1:23
6
$\begingroup$

Perhaps the following example will do. It concerns the weak law of large numbers (LLN, established by Khinchin in 1929, https://www.encyclopediaofmath.org/index.php/Law_of_large_numbers) for independent identically distributed random variables and its strong counterpart, established by Kolmogorov in 1933, https://www.encyclopediaofmath.org/index.php/Strong_law_of_large_numbers. Since the almost sure convergence implies that in probability, one can say that the value of the almost-sure limit was established by Khinchin before Kolmogorov actually proved the strong LLN.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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