# Examples where existence is harder than evaluation

In expressions involving an infinite process (infinite sum, infinite sequence of nested radicals), sometimes the hardest part is proving the existence of a well-defined value. Consider, for example, Ramanujan's infinite nested radical: $$\sqrt{1+2\sqrt{1+3\sqrt{1+\ldots}}}. \qquad(*)$$ Assuming the above is well-defined, there is a slick trick showing that it evaluates to $$3$$.

But such careless assumptions can lead to trouble, as in the example of the expression: $$-5 + 2(-6 + 2(-7 + 2(-8 + \ldots))). \qquad(**)$$

Applying the identity $$n = -(n + 2) + 2(n + 1)$$ repeatedly for $$n=3,4,5,\ldots$$, we get \begin{align} 3 &= -5 + 2(4) \\ &= -5 + 2(-6 + 2(5))\\ &= -5 + 2(-6 + 2(-7 + 2(6))\\ &= -5 + 2(-6 + 2(-7 + 2(-8 + 2(7)))\\ &=\ldots, \end{align} which would falsely suggest that $$(**)$$ evaluates to $$3$$.

What are some interesting examples where evaluating an expression assuming its existence is much easier than proving existence?

Edit: clarifying in light of some of the discussion in the comments. I can see how $$(**)$$ can also invite examples of false conclusions from an assumption of existence. That was not the intent of the question; the sole point of $$(**)$$ was to show that the solution technique to $$(*)$$ provided at the link can in general yield false conclusions if existence is assumed without additional proof. The spirit of the question is to exhibit cases where the limit exists, but its value given the existence is much easier to establish than the existence itsef.

• Many recursions $x_{n+1}=f(x_n)$ ("find the limit") provide examples, though this is of course exactly the type of example that you give yourself. – Christian Remling May 7 '19 at 20:38
• This is most decidedly not a good one, but something like $x_{n+1}=x_n/2+1$ fits your description. Admittedly, both showing convergence and finding the limit are very easy, but if we compare the two, then finding the limit is much easier still. – Christian Remling May 7 '19 at 20:42
• It's easy to make up examples with no mathematical content. Let $X$ be any open conjecture. Let $f(x)=0$ if $x$ is an integer, otherwise let it be zero if $X$ is true, seventeen if $X$ is false. If $\lim_{x\to\infty}f(x)$ exists, it must be zero, but deciding whether it exists is equivalent to deciding $X$. – Gerry Myerson May 8 '19 at 2:53
• Not something I understand or know anything about (so no answer from me), but I believe the order of the monster group was evaluated well before its existence was established? – bof May 8 '19 at 11:58
• For the combinatorial game Brussels Sprouts, Wikipedia gives a simple planar graph proof of the length of the game being $5n-2$ but does not show that the game is finite – Henry May 9 '19 at 18:45

Brownian motion is an example of this phenomenon in probability.

I am no expert on the history, but Einstein is often credited with having described, in 1905, the mathematical properties that Brownian motion ought to have: a continuous process with independent increments whose distribution at time $$t$$ is Gaussian with variance proportional to $$t$$. (It seems that Bachelier may have also done it independently in 1900.) These properties uniquely define Brownian motion (up to scaling), and so any question you may have about Brownian motion can in principle be deduced from these axioms. For instance, you can compute its quadratic variation, and show that it is a Markov process and a martingale, and define and compute stochastic integrals, and so on.

But proving that there actually exists a process with these properties is harder. Historically, it took another 18 years or so before this was done (by Wiener in 1923).

(From Wiener's point of view, the object in question is a measure on the Banach space $$C([0,1])$$; the aforementioned properties tell us the finite-dimensional projections of this measure, which would uniquely determine it; but it is not trivial to prove the existence of a measure with those projections.)

(The historical notes are from Pitman and Yor, Guide to Brownian Motion, which see for more references.)

• This isn't very relevant to the example as an answer to the actual question, but I think it's safe to assume that Einstein was blissfully unaware of all these mathematical issues, and probably the thought that someone might want to prove existence of BM would have seemed mildly absurd to him (just as an attempt to prove the existence of the keyboard I'm using to type this comment might seem to me). – Christian Remling May 8 '19 at 0:28
• Einstein's comments are translated here: einsteinpapers.press.princeton.edu/vol2-trans/144 – Matt F. May 8 '19 at 2:16
• I'm fairly sure Einstein was only interested in Brownian motion as a physical problem and did not particularly care about measures on Banach spaces. – Hollis Williams May 9 '19 at 8:10

The Prime Number Theorem.

Chebyshev proved that if $$\lim_{n\to\infty}{\pi(n)\log n\over n}$$ exists (here, $$\pi(n)$$ is the number of primes up to $$n$$), then it equals $$1$$. Fifty years passed after that before Hadamard and de la Vallée Poussin (independently) proved that the limit exists.

• I think the same situation holds for many expressions known to be equivalent to PNT. For example, I think it is not too bad to show that, if $\sum \tfrac{\mu(n)}{n}$ converges, its value is $0$ and, if $\lim_{N \to \infty} \tfrac{1}{N} \sum_{n=1}^N \mu(n)$ exists, its value is $0$. – David E Speyer May 8 '19 at 2:38
• Btw, Chebyshev also proved that the liminf and limsup of $\frac{\pi(n)\log n}n$ are $>0$ and $<\infty$. – YCor May 18 '19 at 8:57

Isoperimetric problem. Using clever geometric argument Steiner proved in 1838 that if there is a geometric figure of the highest area for a given perimeter, it must be a circle. However, it was only Blaschke in 1919 who showed the existence of such a figure.

By the way, Aknazar Kazhymurat's answer is approximately the Perron's joke about invalidity of Steiner's proof.

User bof, in a comment, pointed to the history of The Monster. I think that's an excellent example, and worth expanding on. I quote from Wikipedia:

The Monster was predicted by Bernd Fischer (unpublished, about 1973) and Robert Griess (1976) as a simple group containing a double cover of Fischer's Baby Monster group as a centralizer of an involution. Within a few months, the order of M was found by Griess using the Thompson order formula, and Fischer, Conway, Norton and Thompson discovered other groups as subquotients, including many of the known sporadic groups, and two new ones: the Thompson group and the Harada–Norton group. The character table of the Monster, a 194-by-194 array, was calculated in 1979 by Fischer and Donald Livingstone using computer programs written by Michael Thorne. It was not clear in the 1970s whether the Monster actually exists. [Emphasis mine] Griess (1982) constructed M as the automorphism group of the Griess algebra, a 196,884-dimensional commutative nonassociative algebra; he first announced his construction in Ann Arbor on January 14, 1980.... Griess's construction showed that the Monster exists.

• but what is the exact theorem, like "A group with such and such properties (which may or may not exist) has order $N$"? – user138661 May 10 '19 at 7:36
• The original question is, "What are some interesting examples where evaluating an expression assuming its existence is much easier than proving existence?" so there's no request for an "exact theorem" there. The order of the group, and its character table, were evaluated before it was proved to exist. But maybe I'm missing the point of your comment. – Gerry Myerson May 10 '19 at 12:44
• the comment was not meant to be hostile of course, more to clarify. I mean, if there is no exact theorem then it is not clear (to me, at least) what expression are we evaluating. The order of some group some guy decided to call "the Monster"? Does not sound very explicit. But maybe my ignorance of finite group theory is showing here. – user138661 May 10 '19 at 14:17
• @schematic_boi I think the theorem is "a simple group which has an involution whose centralizer is a certain double cover of Fischer's Baby Monster group must have the following character table" (and, in particular, the stated order). – David E Speyer May 17 '19 at 15:06

Either Tauber's original theorem or Littlewood's improvement upon it is of this form. Let $$a_n$$ be a sequence of real numbers which is $$o(1/n)$$ (for Tauber's version) or $$O(1/n)$$ (for Littlewood's verion) and suppose that $$\lim_{x \to 1^{-}} \sum_{n=1}^{\infty} a_n x^n = L$$. Then $$\sum_{n=1}^{\infty} a_n = L$$.

The hard part is that $$\sum_{n=1}^{\infty} a_n$$ converges. Assuming the sum converges, the easier Abel's theorem tells us is must converge to $$L$$.

What are some interesting examples where evaluating an expression assuming its existence is much easier than proving existence?

Simple examples are given by limits of several variables (because we can often find a path along which the limit is trivial). For example, assuming the existence of $$\lim_{(x,y)\to(0,0)}\frac{xy^2+\sin(x)x^2}{x^2+y^2}\qquad\text{and}\qquad \lim_{(x,y,z)\to(0,0,0)} (x^2+y^2+z^2)^{x^2y^2z^2},$$ we obtain $$\lim_{(x,y)\to(0,0)}\underbrace{\frac{xy^2+\sin(x)x^2}{x^2+y^2}}_{:=f(x,y)}=\lim_{y\to 0} f(0,y)=\lim_{y\to 0} 0=0$$ and $$\lim_{(x,y,z)\to(0,0,0)} \underbrace{(x^2+y^2+z^2)^{x^2y^2z^2}}_{:=g(x,y,z)}=\lim_{x\to 0} g(x,0,0)=\lim_{x\to 0} 1=1.$$

If $$0 is fixed, define the sequence $$x_n$$ recursively by $$x_{n+1}=x^{x_n}$$ and $$x_0=x$$. It is easy to show that if the limit $$l$$ of the sequence $$x_n$$ exists, then $$(\frac{1}{e})^e\leq x \leq e^{\frac{1}{e}}$$ and $$x=l^{\frac{1}{l}}$$. I found it much tougher to show that in that range of $$x$$, the limit does indeed exist. (This is an exercise in Knopp's book on infinite series).

What are some interesting examples where evaluating an expression assuming its existence is much easier than proving existence?

In the theory of percolation and other statistical physics models such as self-avoiding walks, it is common to encounter so-called critical exponents, which are rational numbers that describe a fractional exponent related to the rate of decay of a particular function, often a probability, as a parameter tends to some value.

One example of this is the exponent 5/48, tied to the asymptotic relation $$\pi(n) = n^{-5/48+o(1)} \qquad (n\to\infty),$$ where $$\pi(n)$$ denotes the probability that the connected component that contains the origin in critical percolation over a two-dimensional lattice has diameter at least $$n$$.

Another example is the exponent 5/36, which appears in the formula $$\theta(p) = (p-p_c)^{5/36+o(1)} \qquad (p\searrow p_c).$$ Here, $$p_c$$ denotes the critical percolation probability, and $$\theta(p)$$ is the probability that the origin belongs to the infinite percolation cluster. See Wendelin Werner’s notes, pages 3-4 for these two examples. See this Wikipedia page for many others.

The interesting thing about the critical exponents is that although their values are in many cases known precisely, they have been computed using mostly nonrigorous methods. However, as far as existence goes, they are conjectured to exist (in the sense that the relevant asymptotic relations such as the ones written above hold) in fairly large generality for any “reasonable” lattice, and the actual existence has either not been proved at all (I believe that’s the case for most or all exponents related to self-avoiding random walks), or has been proved only for very specific lattices (using SLE techniques pioneered by Schramm, Lawler, Werner, Smirnov and others). The above two formulas were proved in the case of the triangular lattice, as Werner explains in his notes.

Let's take the expression "the largest positive integer". Assuming existence, we get that $$n^2\leq n$$, but we also have $$n^2\geq n$$, so $$n^2=n$$, i.e. $$n=1$$. Proving existence seems to be harder: can you prove false statements in ZFC (or prove that you can't, for that matter)?

• I am not quite sure why this got down-votes. Among all the answers that I can see right now, this appears to have the highest "difficulty to prove existence/difficulty to evaluate" ratio. Or is it really easy to prove there is the largest positive integer? – user74900 May 8 '19 at 11:36
• I think the question is implicitly asking for examples were existence is hard but still true. This is more like an example you would show to undergrads to make a point about rigor. – Najib Idrissi May 8 '19 at 12:40
• @NajibIdrissi yes, that is a reasonable interpretation. Was not specified at the time I was answering though. – user74900 May 8 '19 at 12:41
• What can I say then? The point still stands. – user74900 May 8 '19 at 12:43
• Assuming $lim_{n \to \infty} \frac{n}{1}$ exists, this answer has the highest "difficulty to prove existence/difficulty to evaluate" ratio. – Vaelus May 9 '19 at 18:23

There are a number of examples from number theory of finite subsets of $$\mathbb{Z}$$ whose largest element is unknown. For instance, let $$S$$ be the set of all positive integers that cannot be written in the form $$xy+xz+yz$$, where $$x,y,z$$ are positive integers. It is known that $$|S|\leq 19$$, and eighteen elements of $$S$$ are known, the largest being 462. If there is another element $$n$$, then $$n>10^{11}$$. Assuming the Generalized Riemann Hypothesis, $$n$$ does not exist. See http://people.math.sfu.ca/~kkchoi/paper/rep.pdf.

It may be hard to prove that a given odd function $$f:\mathbb{R}\to\mathbb{R}$$ is integrable, even measurable. However, if it is integrable, $$\int_{\mathbb{R}}f(x)dx=0$$. (This example is deliberately trivial).

Minimal surfaces would provide a lot of examples.

Construction of minimal surfaces often reduces to finding a meromorphic and a holomorphic functions (Weierstrass representation). Often we have a general idea about these functions up to some parameters, which are determined by "closing the periods", meaning that some path integrals should vanish.

In many cases the periods are easily closed numerically, leading to beautiful pictures, and the surface is naturally named after the discoverer (they deserve). But existence of period-closing parameters could be very hard prove, sometimes never done. The Horgan (non)surface is a famous example that computer closes periods which is later proved impossible. Then there is the embeddedness to prove, which could be even harder.