112
$\begingroup$

I am looking for examples of problems that are easier in the infinite case than in the finite case. I really can't think of any good ones for now, but I'll be sure to add some when I do.

$\endgroup$
  • 5
    $\begingroup$ It’s been a while since I’ve thought of this, but I think that “any two bases of a vector space have the same cardinality” qualifies. $\endgroup$ – Lubin Aug 9 '16 at 2:44
  • 1
    $\begingroup$ People can compute cohomology/homology/homotopy stuff of stable objects easier than they can compute such invariants of their unstable/finitary versions. $\endgroup$ – Pedro Tamaroff Aug 9 '16 at 3:53
  • 3
    $\begingroup$ In general, it is sometimes easier to answer an "infinite" question first (like "are there infinitely many prime numbers?"), the "infinite" question being both easier and more natural, and then it turns out that the "finite" case, which at first was a secondary consideration, is much more difficult. The only example I can think up right now is that of prime numbers (which it turns out is not as good an example as I first thought, since there are combinatorial ways of computing values of $\pi(n)$), but I'm sure more exist. $\endgroup$ – Will R Aug 9 '16 at 8:09
  • 1
    $\begingroup$ My first thought was the classification of simple finite groups versus the classification of simple Lie groups, though that's not exactly finite vs. infinite as Lie groups are just a small subset of the infinite groups. $\endgroup$ – pregunton Aug 9 '16 at 8:23
  • 2
    $\begingroup$ Many finite Ramsey style theorems are harder to prove than some of the infinite ones... $\endgroup$ – Stefan Mesken Aug 9 '16 at 15:28

26 Answers 26

57
$\begingroup$

$\min c^Tx$

subject to $x \in P$

where $P$ is a bounded polyhedral can be solved easily by linear programming method. Ellipsoid method shows that the problem is in $P$ class.

$\min c^Tx$

subject to $x \in P \cap \mathbb{Z}^d$

that is imposing integer constraint increase the difficulty of the question.

Here $P$ is an infinite set in the sense that it contains infinitely many points but $P \cap \mathbb{Z}^d$ contains only finitely many points. Linear programming problem is easier than integer programming problem.

$\endgroup$
  • 22
    $\begingroup$ Isn't it an open problem (P = NP) whether integer programming is actually harder than linear programming? $\endgroup$ – templatetypedef Aug 9 '16 at 20:17
  • 2
    $\begingroup$ true. good point. $\endgroup$ – Siong Thye Goh Aug 9 '16 at 23:49
  • 6
    $\begingroup$ @templatetypedef But is computational hardness the same thing as hardness to people? $\endgroup$ – Jacob Wakem Aug 10 '16 at 2:41
  • 6
    $\begingroup$ @templatetypedef I don't think anyone actually believes that though $\endgroup$ – Jorge Fernández Hidalgo Aug 10 '16 at 3:25
  • 17
    $\begingroup$ But the difference in difficulty here is due to "discrete vs. continuous", not "infinite vs finite" $\endgroup$ – BlueRaja - Danny Pflughoeft Aug 11 '16 at 22:00
118
$\begingroup$

One can compute the value of $$\int_{0}^{\infty}e^{-t^{2}}\,\mathrm{d}t$$ exactly. This is known as the Gaussian integral, and it has its own Wikipedia page. The answer turns out to be $\frac{1}{2}\sqrt{\pi}.$

But one cannot do the same with $$\int_{0}^{x}e^{-t^{2}}\,\mathrm{d}t$$ because the antiderivative of the integrand is not an elementary function. This is why we gave a name to the error function $$\mathrm{erf}(x) = \frac{2}{\sqrt{\pi}}\int_{0}^{x}e^{-t^{2}}\,\mathrm{d}t,$$ which also has its own Wikipedia page.

In that sense, the infinite case is easier than the finite case.


Addendum: The same phenomenon occurs for variants of this integral, in particular we can transform the integrand to evaluate $$\int_{-\infty}^{\infty}ae^{-(t-b)^{2}/(2c^{2})}\,\mathrm{d}t = \sqrt{2}a\lvert c\rvert \sqrt{\pi}$$ as detailed here on Wikipedia.

$\endgroup$
  • 32
    $\begingroup$ @jwg: Thanks for your feedback. What do you think the questioner meant? What criteria does this answer fail to meet? $\endgroup$ – Will R Aug 9 '16 at 8:32
  • 10
    $\begingroup$ Put another way, if this answer the question that the OP intended, then it was an uninteresting question. $\endgroup$ – jwg Aug 9 '16 at 12:55
  • 17
    $\begingroup$ @jwg: You haven't answered my questions. How am I supposed to improve this answer, or give a better answer, if I am interpreting the question incorrectly? If indeed I am interpreting the question incorrectly, it would help if you (or anyone else) could give me some advice on where I am going wrong. That being said, I feel an impulse to point out that you have not said the same about any of the other answers so far: what makes this answer different to the others? $\endgroup$ – Will R Aug 9 '16 at 13:42
  • 13
    $\begingroup$ @jwg, put another way, what meaning would make the question interesting? $\endgroup$ – Paul Draper Aug 9 '16 at 13:46
  • 5
    $\begingroup$ @WillR I assume the question is looking for examples of theorems which are easy to prove about infinite sets/rings/fields/groups/etc., but harder to prove for finite objects. $\endgroup$ – Tavian Barnes Aug 10 '16 at 13:32
57
$\begingroup$

First thought would be series vs. partial sums (or improper vs. definite integrals) e.g.

$$ \sum_{k=0}^{\infty} \frac{1}{k!} \;=\; e $$

$$ \sum_{k=0}^{n} \frac{1}{k!} \;=\; \frac{e \cdot \Gamma(n+1,1)}{n!} $$

$\endgroup$
  • 5
    $\begingroup$ @CarryonSmiling Calculating the incomplete gamma function is even more impossible than calculating e itself ;-) It's not entirely clear what you meant by that easier in the title, which I guess is part of the game. $\endgroup$ – dxiv Aug 9 '16 at 3:27
  • 5
    $\begingroup$ @CarryonSmiling: when you say calculating $e$ is impossible, you have a limited view of calculation. The first line here is either the definition of $e$ or a theorem depending on the route you take. In either case it defines a specific real number. You are saying, correctly, that in finite time we can only calculate finitely many decimal places of $e$, but defining that constant is very useful even if we cannot find its decimal (or binary) representation. $\endgroup$ – Ross Millikan Aug 9 '16 at 3:32
  • 3
    $\begingroup$ We name certain reals, like $e$ and $\pi$ because they are useful. It doesn't matter that we don't have the whole decimal expansion. What matters is they are the same real that shows up lots of places, so we can use what we have learned about them in one place to help with another place. $\endgroup$ – Ross Millikan Aug 9 '16 at 3:37
  • 13
    $\begingroup$ This is misleading: you can define e as such as sum. In that sense, there is no evaluation there. $\endgroup$ – Pedro Tamaroff Aug 9 '16 at 3:52
  • 3
    $\begingroup$ @dxiv what do you mean by the second argument in the gamma function, i.e. what is $\Gamma(\cdot,m)$? $\endgroup$ – Therkel Aug 9 '16 at 6:31
49
$\begingroup$

Circle packing. Packing in a plane (infinite case) vs. packing in arbitrarily given bounded area (finite case).

$\endgroup$
  • 2
    $\begingroup$ This is an excellent example, and extremely understandable. Well done. $\endgroup$ – Wildcard Aug 13 '16 at 2:12
  • $\begingroup$ Even the packing of square tiles inside a simple (even with integer sides) right triangle is quite challenging $\endgroup$ – G Cab Aug 19 '16 at 22:44
  • $\begingroup$ The infinite case isn't too easy either, though ... In fact there's the issue of even defining what the problem is. What it means to be "the" best packing is apparently unresolved, although you can of course prove a packing has the maximum possible density. $\endgroup$ – 6005 Sep 2 '16 at 18:21
48
$\begingroup$

Proving that a polynomial is zero

Suppose you have an unknown polynomial $f$ of degree $d$, but you are able to say things about the values of $f$.

If you are working over an infinite field, an easy test is to check if $f(a) = 0$ for $d+1$ distinct values of $a$.

If you are working over a finite field of $d$ elements or less, you can have the unenviable problem that $f(a) = 0$ for every $a$, even when the polynomial $f(x)$ is nonzero, so this approach won't work in general.

(example: $f(x) = x^q - x$ when working over the field of $q$ elements)

$\endgroup$
  • $\begingroup$ More explicitly maybe, over finite fields there aren't $d+1$ distinct values to check. Though, when would you have a situation like this? Where can one use this argument? I've never seen it before and I think it would be neat to see. $\endgroup$ – MCT Aug 9 '16 at 14:06
  • 4
    $\begingroup$ @MichaelTong It's hard coming up with interesting examples on the spot. But here's one: suppose you have a complex polynomial with the property that $f(a)$ is a real number whenever $a$ is a real number. Let $\bar{f}$ be the polynomial you get by conjugating its coefficients. Then $\bar{f}(a) = f(a)$ whenever $a$ is a real number, and $f - \bar{f}$ as infinitely many roots! Consequently, the coefficients of $f$ must be real numbers. $\endgroup$ – Hurkyl Aug 9 '16 at 14:14
  • 6
    $\begingroup$ @MichaelTong A maybe less interesting but more important application is that one method of doing arithmetic with polynomials is to record its values rather than its coefficients. In particular, this makes multiplying polynomials easy. If you use $n$ different values, then there is at most one polynomial of degree less than $n$ attaining those values; so if you do arithmetic this way and then later find the coefficients of a polynomial with those values, you can be sure you got the right answer if the degree you were looking for is less than $n$. Keyword: "evaluate-interpolate". $\endgroup$ – Hurkyl Aug 9 '16 at 14:19
  • $\begingroup$ Testing if a polynomial function evaluates to $0$ everywhere requires fewer point evaluations for a finite field when $d \geq |F|$, and the same number of tests otherwise. Testing whether an element of $F[X]$ is $0$ requires the same number of the same field operations whether $F$ is finite or infinite. As long as the meaning of zeroness-testing is kept consistent between finite and infinite fields, the infinite case is no easier. $\endgroup$ – zyx Aug 10 '16 at 3:17
33
$\begingroup$

In digital data analysis (signal, image processing), data is generally discrete and finite. "Discrete" generally means "regularly sampled", and indexed by integer indices. "Finite" her mean having a compact support (not talking about the field in which the values are taken, except as a side note). This answer is about the difference in analysing continuous data $x(t)$, $t\in \mathbb{R}$, or discrete data $x[n]$, $n\in [1,\ldots,N]$. Similar problems arise in higher dimensions with $t\in \mathbb{R}^d$ and $n\in [1,\ldots,N]^d$, I will consider only $d\in\{1,2,3\}$.

Tools from harmonic analysis have been used for a while in signal (and image) processing : all sorts of integral transformations, such as Fourier, Radon, Hilbert transforms, and wavelet analysis. Such representations are generally invertible when considered on functions of continuous parameters (like a time $t$). However, the discretization of harmonic analysis transformations with a finite number of samples, which is mandatory for computer operations, while retaining nice properties (orthogonality, invertibility, symmetry) is often complicated.

A standard example is the theory of continuous wavelet transforms. A 1D signal $x(t)$ can be transformed to a 2D domain with a location ($b$) and scale ($a$) variable:

$$ X_{w}(a,b)={\frac {1}{|a|^{1/2}}}\int_{-\infty }^{\infty }x(t)\overline {\psi}\left({\frac {t-b}{a}}\right)\,dt$$ which admits an inversion $$x(t)=C_{\psi }^{{-1}}\int _{{-\infty }}^{{\infty }}\int _{{-\infty }}^{{\infty }}X_{w}(a,b){\frac {1}{|a|^{{1/2}}}}{\tilde \psi }\left({\frac {t-b}{a}}\right)\,db\ {\frac {da}{a^{2}}}$$ with a quite mild admissibility condition (SE.math) on $ \psi$ and $\tilde{\psi}$, which I do not detail here. In plain words, any couple of such functions (avoid pathological ones, still) vanishing in the Fourier domain at $0$, and decaying fast enough at $\infty$, will do the job. So one can use many smooth wiggling functions, with analytical formulas, like Gaussian derivatives, for instance the Mexican hat:

mexican hat wavelet

However, the building of discrete wavelets was difficult, apart from trivial examples in early works by A. Haar in 1910 and P. Franklin in 1928. It took some time before J.-O. Strömberg, Y. Meyer and I. Daubechies produced discrete orthogonal wavelet bases in the eighties. Daubechies wavelets of low order are notoriously not so regular, without analytical formulas, and asymmetric:

Daubechies 4 wavelet

This is for the transformation. But the signal is quantized on bits. It often takes values in $[0,\ldots,2^B-1]$ If we restrict the output to by quantified too, the problem is even more difficult.

Aside, dealing with (and defining) discrete objects on a digital grid is often more complicated than with their continuous counterparts. Think for instance about discrete arcs of circles (in 2D), drawn in "pixels", that do not scale as well as standard circles:

Discrete circle

Those topics are addressed in digital geometry, for which algorithms are developed to draw discrete lines (Bresenham algorithm), discrete planes (in 3D, see below, from 3D Noisy Discrete Objects: Segmentation and Application to Smoothing, 2009, Provot et al.), with less or more thickness, or conics for instance.

Fuzzy discrete plane and bounding planes

$\endgroup$
  • $\begingroup$ It's not obvious to me that your discrete cases are also finite. Are they? $\endgroup$ – Mehrdad Aug 16 '16 at 5:34
  • $\begingroup$ @Mehrdad As for discrete signals, I would be positive. As for digital geometry, positive for bounded objects like the cercle. Do you believe I should add a mention for discrete lines and planes? $\endgroup$ – Laurent Duval Aug 16 '16 at 6:02
  • $\begingroup$ Ah sorry, I just meant the signals. It'd be nice if you could plot what signal's wavelet transform you were taking, so that we could see that it's discrete and finite. $\endgroup$ – Mehrdad Aug 16 '16 at 6:32
  • $\begingroup$ @Mehrdad Discrete finite support wavelets boil down to the convolution of two finite support series. As I cannot produce a continuous image, would a finite signal, with a discrete wavelet plot suit your needs? $\endgroup$ – Laurent Duval Sep 2 '16 at 19:14
28
$\begingroup$

Geometric series finite vs. infinite case for $|q|<1$ \begin{align*} \sum_{j=0}^Nq^j=\frac{1-q^{N+1}}{1-q}\qquad\text{vs.}\qquad\sum_{j=0}^\infty q^j=\frac{1}{1-q} \end{align*}

$\endgroup$
  • 1
    $\begingroup$ What's the underlying "problem" here? Is it using the formula to compute the answer, or is it deriving the formula? The former doesn't seem like a "problem" (as I understand the word) and I'm not convinced that the latter is easier in the infinite case. (+1, though, because this is the first thing that came to my mind, too...) $\endgroup$ – Benjamin Dickman Aug 11 '16 at 19:28
  • $\begingroup$ @BenjaminDickman: Thanks! It was also my first idea. :-) Underlying problem: Find a closed expression. ... and at least the outcome is simpler. $\endgroup$ – Markus Scheuer Aug 11 '16 at 19:38
  • 2
    $\begingroup$ The "outcome is simpler" -- yeah, I was just thinking that to "find a closed expression" -- at least the way I have trad'ly done it -- involves first working with the finite case, and then getting to the infinite case by evaluating a limit (i.e., the finite case along with an extra step, hence arguably not "easier"). $\endgroup$ – Benjamin Dickman Aug 11 '16 at 19:53
24
$\begingroup$

The linear-quadratic control problem, that is, finding a function $u(t)$ that minimizes $\int_0^{t_1} x^TQx + u^TRu\,\mathrm{d} t$ under the constraint $\dot{x} = Ax + Bu$.

In the infinite-horizon case $t_1=\infty$, the solution is obtained by solving an algebraic Riccati equation (ARE). In the finite-horizon case $0<t_1 \in \mathbb{R}$, it is obtained by solving a differential Riccati equation (DRE), which is more difficult to solve; for instance, some numerical methods for DREs involve solving an ARE at each time step.

$\endgroup$
  • $\begingroup$ +1 I think this is more in the spirit of the question than some other answers. $\endgroup$ – Mehrdad Aug 11 '16 at 2:44
23
$\begingroup$

Let's take a look at Goodstein sequences $G_k(n)$ and their interesting behaviour. We associate to each natural $n$ a sequence $(G_k(n))_{k\geq 0}$.

  • Step $0$: We start by representing $n$ in base $2$ notation and also all powers and powers of powers, so that $n$ is written without using any number greater than $2$.

    Taking $n=266$ we obtain \begin{align*} G_0(266)=2^8+2^3+2^1=2^{2^{2+1}}+2^{2+1}+2^1 \end{align*}

  • Step $k\geq 1$: Replace each occurrence of base $k+1$ in $G_{k-1}(n)$ by $k+2$, represent it in base $k+2$ notation without using any number greater than $k+2$ and subtract $1$

    We obtain \begin{align*} G_1(266)&=3^{3^{3+1}}+3^{3+1}+3^1-1=3^{3^{3+1}}+3^{3+1}+2\simeq 10^{38}\\ G_2(266)&=4^{4^{4+1}}+4^{4+1}+1\simeq 10^{616}\\ G_3(266)&=5^{5^{5+1}}+5^{5+1}\simeq 10^{10921}\\ G_4(266)&=6^{6^{6+1}}+6^{6+1}-1\\ &=6^{6^{6+1}} +5\cdot6^{6}+5\cdot6^{5}+5\cdot6^{4}+5\cdot6^{3}+5\cdot6^{2}+5\cdot6^{1}+5\simeq 10^{217832}\\ G_5(266)&=7^{7^{7+1}} +5\cdot7^{7}+5\cdot7^{5}+5\cdot7^{4}+5\cdot7^{3}+5\cdot7^{2}+5\cdot7^{1}+4\simeq 10^{4871822}\\ \end{align*}

Although this sequence is enormously increasing at the beginning, subtracting $1$ in each step is sufficient that this sequence and in fact each Goodstein sequence will eventually terminate with $0$ (admittedly with $k$ often rather large).

The interesting thing is to prove this behaviour can be done by going from finite to infinite. It is done by using transfinite ordinals and arguing with the well-ordering property. See this nice introductory presentation for more information.

$\endgroup$
  • $\begingroup$ I can't shake the feeling that "using transfinite ordinals" in this case is easier because we happen to already know a lot of things about transfinite ordinals, enough to establish the mapping between the two. So it qualifies. But out of interest, to someone who isn't already familiar with ordinals, is the proof any easier to follow than a direct proof that hereditary base-2 notation is well-ordered and that each step in the sequence results in a smaller value per this order? I suppose one can argue that since PA doesn't prove the result, in some formal sense the "finite case" is impossible! $\endgroup$ – Steve Jessop Aug 9 '16 at 10:02
  • $\begingroup$ @SteveJessop: It seems that in this case a proof via transfinite ordinals is in fact simpler, since it's easy to associate a strictly decreasing sequence with the help of transfinite ordinals as it is indicated in the referenced page. $\endgroup$ – Markus Scheuer Aug 9 '16 at 10:08
  • $\begingroup$ But just staring at your example, ignore the actual $n$ in the hereditary base-n notation, it's easy to see that the "biggest term" never gets any bigger in our chosen well-order (meaning more complex), only bigger in the usual ordering of the integers, while the -1 repeatedly chips away at the smallest term. This observation might be giving me false hope of a "high-school" proof. I've never attempted it, so I don't know at what point down that road you hit the "tricky bit" that PA doesn't prove, and have to pull in the Axiom of Foundation or whatever. $\endgroup$ – Steve Jessop Aug 9 '16 at 10:16
  • $\begingroup$ Since the "sequence" variable is actually the $k$, don't you want to write $G_n(k)$ instead of $G_k(n)$ (in which case the sequence is $G_n$ instead of $(G_k(n))_{k\ge 0}$)? In your example you are listing the values of $G_{266}$. $\endgroup$ – Mario Carneiro Aug 9 '16 at 17:52
  • 3
    $\begingroup$ It has been shown that the convergence of all Goodstein sequences to $0$ cannot be proven in PA (Peano Arithmetic) unless $\neg Con (PA)$ because it implies $con [PA].$ So without a stronger axiom (e.g. Infinity) we are stuck. $\endgroup$ – DanielWainfleet Aug 10 '16 at 1:38
14
$\begingroup$

Kolmogorov's Zero-One Law

Informally, in certain probabilities spaces, events which do not depend on any finite amount of information must have probability zero or one.

For example, suppose you flip a coin over and over again infinitely many times. Any event $E$ which is independent from the outcome of any finite number of coin flips must have probability $0$ or $1$. Examples include

  • $E =$ the event that 100 consecutive heads are flipped infinitely times (prob $=1$)
  • $E =$ the event that $\limsup_{n \to \infty} H_n - T_n = \infty$, where $H_n$ ($T_n$ resp.) is the number of heads (tails resp.) in first $n$ tosses. (prob $=1$)
  • $E =$ the event that $\lim_{n \to \infty} H_n - T_n = \infty$. (prob $=0$)
  • $E =$ the event that $\sum_{k=1}^{\infty} \frac{\sigma(k)}{k}$ converges, where $\sigma(k) = 1$ if $k$'th toss is heads and $\sigma(k) = -1$ if $k$'th toss is tails. (prob $=1$)
$\endgroup$
  • $\begingroup$ Excellent example! $\endgroup$ – Stella Biderman Jan 12 '17 at 19:47
14
$\begingroup$

The Game of Chomp:

Although a winning strategy is guaranteed to exist, finding a winning strategy for a $a \times b$ is an unsolved problem. However, finding a winning strategy for a $a \times \omega$ ($a\geq3$) board is not that hard.

First note that you lose for a $2 \times \omega$ board, because the only losing position is a board of the form of $a+1$ chocolates and then $a$ chocolates. Your opponent can always make sure that you get such board. Now note that you can always reduce a $a \times \omega$ ($a\geq3$) board to a $2 \times \omega$ board.

$\endgroup$
  • 4
    $\begingroup$ You may want to link to, or explain the Game of Chomp. I certainly didn't know it and I think I'm not alone in that. $\endgroup$ – SQB Aug 12 '16 at 8:58
  • $\begingroup$ This result is cute. And it also solves $\infty \times \infty$ board when $a = \infty$ :) $\endgroup$ – 6005 Sep 2 '16 at 18:26
  • $\begingroup$ To be picky, but think it should be $a \times \omega$ instead of $a \times \infty$. It has to be a one-directional infinity; the board is implicitly well-ordered in each direction. $\endgroup$ – 6005 Sep 2 '16 at 18:30
  • $\begingroup$ @6005 You are certainly right, I tried to explain it too many times to people who didn't know ordinal numbers. $\endgroup$ – wythagoras Sep 2 '16 at 18:56
12
$\begingroup$

Almost the entirety of calculus and all applications thereof

This needs a bit of explaining: The notion of infinity is an artificial one. There is nothing in reality that we know to be truly infinite¹. So why do we bother with infinity? Because it’s easier to deal with than “very big numbers”! And working with infinity is what calculus (née infinitesimal calculus) is about. Take any word problem in a high-school calculus text book and try to formulate and then solve it without any notion of infinity, continuity, and so on – it will be a pain in the arse.

To be even more concrete, let’s look at the classical setup of exponential growth (e.g., for populations, interest, and so on): You have a quantity $x$ whose growth is proportionally to its current amount and want to describe its long term behaviour. Employing the notion of infinity, you can describe and solve this with the differential equation $\dot{x} = cx$. Without calculus you have to find some finite time $\mathrm{d}t$ and then can state that $x(t+\mathrm{d}t) = (1+c)·x(t)$. (In some cases, e.g., interest applied in daily steps, this may even be more realistic.) So far, there is no big difference in terms of easiness.

But now try to quickly calculate a good approximation of $x(1000 · \mathrm{d}t)$. Without employing the concept of infinity, you probably end up with performing thousands of multiplications. With infinity, you can approximate the behaviour with the exponential function, whose value you can approximate in more efficient ways. Of course, you can formulate some equivalent or almost equivalent statements for obtaining this value without infinity. But neither would the statement itself nor deriving it would be what I would consider easy.

Some of the existing answers provide further examples for this: 1, 2, 3, 4.


¹ or truly infinitesimally small, continuous, etc.

$\endgroup$
11
$\begingroup$

Another example of an improper integral being "easier" (in this case, by having an elementary result) than a proper one would be integrating along the entire real axis by the residue theorem and Jordan's lemma or estimation lemma

For example, consider: $$f = \frac{e^{i x}}{x^2 + 1}$$ $$\int_{-a}^a f \:\mathrm{d}x$$

For the infinite case ($a \to \infty$), we consider a semicircle with its base along the real axis and curved section in the upper positive imaginary axis, and then take the limit of its radius approaching infinity.

With the residue theorem and Jordan's lemma, we have: $$ \begin{align*} \int_{-\infty}^\infty f \:\mathrm{d}x &= 2 \pi i \operatorname{Res}(f, i) \\ &= 2 \pi i \frac{e^{-1}}{2 i} \\ &= \frac{\pi}{e} \end{align*} $$

For the finite case ($a \in \mathbb{R}^+$), there is no elementary solution, so we have to solve in terms of the exponential integral: $$ \begin{align*} \int f \:\mathrm{d}x &= \frac{i}{2} \int \frac{e^{i x}}{x + i} - \frac{e^{i x}}{x + i} \:\mathrm{d}x \\ &= \frac{i}{2} \int e \frac{e^{i (x + i)}}{x + i} - e^{-1} \frac{e^{i (x - i)}}{x} \:\mathrm{d}x \\ &= \frac{i}{2 e} \left(e^2 \operatorname{Ei}(i x - 1) - \operatorname{Ei}(i x + 1)\right) \end{align*} $$

$\endgroup$
11
$\begingroup$

The asymptotic distribution of primes: nth prime ≈ n ln n as n → ∞

Try finding a formula for the nth prime in the non-asymptotic case!

$\endgroup$
  • 1
    $\begingroup$ I considered posting an answer along similar lines to this, but I was only thinking in terms of counting primes, i.e., evaluating $\pi(n).$ The point is that we know what $\lim_{n\to\infty}\pi(n)$ is by very elementary arguments. But as it turns out, there are practical combinatorial ways of computing $\pi(n)$ even for large values of $n.$ Kudos for finding the interpretation I missed. $\endgroup$ – Will R Aug 11 '16 at 3:22
  • $\begingroup$ @WillR: Thanks! :) $\endgroup$ – Mehrdad Aug 11 '16 at 5:35
10
$\begingroup$

Notation: $$(i). \text { $|A|$ is the cardinal of the set $A.$ }$$ $$(ii). [A]^2 =\{ \;\{x,y\}\subset A: x\ne y\}.$$ $$(iii). f''A=\{f(x):x\in A\}$$ for any function $f$ and any set $A\subset dom(f).$ $$(iv). \text { $\omega$ is the first infinite cardinal.}$$

For finite or infinite cardinals $a, b$ the arrow notation $$(a)\to (b)^2_2$$ means that if $|A|=a$ then for any function $f:[A]^2\to \{0,1\}$ there exists $B\subset A$ with $|B|=b$ and $|f''[B]^2|=1.$.... Observe that if $a'\geq a$ and $b'\leq b,$ then $(a)\to (b)^2_2$ implies $(a')\to (b')^2_2.$

$$\text {Theorem 1. For any $m\in \mathbb N$ there exists $n\in \mathbb N$ such that $(n)\to (m)^2_2.$}$$ Theorem 1 implies that for all sufficiently large $n ,$ any two-coloring of the edges of the complete graph on $n$ points will have a complete sub-graph on $m $ points with edges all the same color.

$$\text {Theorem 2. $(\omega)\to (\omega)^2_2.$}$$ This is fairly easy to prove. Now there is a result in Model Theory: If a theory has arbitrarily large finite models then it has an infinite model. We can use this, and Theorem 2, to prove Theorem 1 by contradiction: If for some $m\in \mathbb N$ we have $\neg [(n)\to (m)^2_2]$ for all $n \in \mathbb N$ then there exists infinite $a$ such that $\neg [(a)\to (m)^2_2],$ contradicting Theorem 2.

Prof. William Weiss once told me that there is a long finitistic proof of Theorem 1, but that the infinite method "uses some technology."

$\endgroup$
  • 2
    $\begingroup$ The finitistic proof of (1) that I know isn't very long, although it gives a bad upper bound. Let $e(1)=1$, $e(n+1)=2^{e(n)}+1$, and suppose $f$ is a 2-coloring of $\{1, 2, . . . , e(2n)\}$. We define a sequence of pairs of finite sets $p_i$ as follows: $p_0=(\emptyset, \{1, 2, 3, . . . , e(2n)\})$, and if $p_i=(\{x_1, . . . , x_i\}, F_i)$ then $p_{i+1}=(\{x_1, . . . , x_i, y\}, G)$, where $y$ is the least element of $F_i$ and $G$ is either the set of points in $F_i$ which get colored $0$ with $y$, or the complement in $F_i$ of that set, whichever's larger. (cont'd) $\endgroup$ – Noah Schweber Aug 11 '16 at 0:05
  • 2
    $\begingroup$ Now by choice of $e(2n)$, we can define $p_i$ for every $i\le n$. Let $C$ be the left coordinate of $p_n$, and note by induction that for any distinct $a, b, c\in C$ we have $f(\{a, b\})=f(\{a, c\})$. Let $F(a)=f(\{a, b\})$ for $a\in C$ (note that it doesn't matter what we use for $b$ here). We can now thin $C$ to get a homogeneous set of size $\ge n$, by pigeonhole: either $F^{-1}(0)$ or $F^{-1}(1)$ has size $\ge n$, and each is homogeneous. $\endgroup$ – Noah Schweber Aug 11 '16 at 0:07
  • $\begingroup$ @NoahSchweber. In retrospect I don't think that W. Weiss said "long". $\endgroup$ – DanielWainfleet Aug 17 '18 at 17:30
8
$\begingroup$

Without the axiom of infinity, it's very hard (impossible, I think) to prove that the TREE function is well-defined, even though it is a theorem about finite objects. This is taking a fairly liberal view of what "the finite case" means!

$\endgroup$
8
$\begingroup$

I am not sure if this qualifies, but I just want to share it here in case you're interested. I got it from a blog post by Mr. Greg Muller : The Axiom of Choice is Wrong

Let me write it down here the main idea of the post.

$100$ prisoners are placed in a line, facing forward so they can see everyone in front of them in line. The warden will place either a black or white hat on each prisoner’s head, and then starting from the back of the line, he will ask each prisoner what the color of his own hat is (ie, he first asks the person who can see all other prisoners). Any prisoner who is correct may go free. Every prisoner can hear everyone else’s guesses and whether or not they were right. If all the prisoners can agree on a strategy beforehand, what is the best strategy?

There is a strategy that ensures at least $99$ prisoners to go free. Let's consider a variance to that problem:

A countable infinite number of prisoners are placed on the natural numbers, facing in the positive direction (ie, everyone can see an infinite number of prisoners). Hats will be placed and each prisoner will be asked what his hat color is. However, to complicate things, prisoners cannot hear previous guesses or whether they were correct. In this new situation, what is the best strategy?

This sounds hopeless, right? However, there is a strategy that guarantee all but finitely many prisoners to go free! The paradoxical result stems from the fact that there're non-measurable sets (but some would also attribute it to the sigma-additive nature of probability).

Follows the link if you are interested. In the comment section there are also explanation/discussion of this perplexing phenomenon by many mathematician, Prof. Tao being one of them.

$\endgroup$
  • 2
    $\begingroup$ @BogdanAlexandru Well, actually you must have missed something, because the article specifically says precisely what the strategy is... I suggest that you re-read it again, more carefully this time. You can come back here once you find it and if you still want to discuss about it. $\endgroup$ – BigbearZzz Aug 11 '16 at 13:52
  • 1
    $\begingroup$ @BogdanAlexandru By the way, you need to know what an equivalent class is and what the axiom of choice do in order to understand the solution to the problem. Yes, the solution is indeed paradoxical (or even problematic) but not for the reason you had given. $\endgroup$ – BigbearZzz Aug 11 '16 at 13:54
  • 1
    $\begingroup$ I did. So, aren't there an infinite number of equivalence classes then? Would a prisoner have to memorize an infinity of infinite sequences? And even if we go over this logistics problem, then how do you solve the paradox posed by my question above? My argument is still valid: for every m and n, there is absolutely no difference between the m-th and the n-th prisoner => they have the exact chance of guessing ==> they all have the exact same chance => they all have 50% chance (becaue the first one has 50%). $\endgroup$ – Bogdan Alexandru Aug 11 '16 at 20:37
  • 1
    $\begingroup$ Regarding that thought experiment, what inputs am I allowed to use? E.g., can I say I randomly generate x in interval (0-1], then I round 1/x to the nearest integer? This solution is not good, I'm only asking for what do I have available. $\endgroup$ – Bogdan Alexandru Aug 12 '16 at 11:32
  • 2
    $\begingroup$ Cool! This actually gets me thinking. Thanks for the interesting chat and for the patience to prove me wrong on my naive assumption that "this article is bs", which I need to take back now :) $\endgroup$ – Bogdan Alexandru Aug 16 '16 at 12:26
8
$\begingroup$

Every single Machine Learning problem ever.

Optimal statistical inference is generally much easier in the case of infinite data than finite data.

$\endgroup$
6
$\begingroup$

I know this is trivial, but here's one: $x$ is finite and unknown. Determine whether $x < n$.

Easy when $n$ is infinite!

$\endgroup$
5
$\begingroup$

Stability analysis of finite difference stencils

GKS stability requires that the two semi-infinite problems defined on $[a,\infty]$ and $[-\infty,b]$ must be stable in order for the finite problem defined on $[a,b]$ to be stable. Thus, you can't do the finite case without at least doing the infinite ones first.

$\endgroup$
5
$\begingroup$

A Markov chain is characterized by a discrete probability distribution of the initial state of a system, 𝜋0, and a transition matrix P such that pij is the probability of going from state i to state j after any one transition. Under certain assumptions, the probability distribution of states after the first transition is 𝜋1 = 𝜋0P, after two transitions is 𝜋2 = 𝜋1P = 𝜋0P2, after n transitions, 𝜋n = 𝜋0Pn.

By constrast, the steady-state (as n -> ∞) probability distribution of states, 𝜋, must satisfy 𝜋 = 𝜋P, and 𝜋𝛽 = 1, where 𝛽 is a column vector of 1's. This is an over-determined (by one) system of equations, but the upshot is that the steady-state probability distribution of states is obtained by inverting a matrix.

See, for example, the Markov chain Wiki for details.

$\endgroup$
4
$\begingroup$

Burnside problem

The solution for Burnside problem in the following formulation:

For which positive integers $m$, $n$ is the free Burnside group $B(m, n)$ finite?

is not known for any $m$, $n$, but there are some results for infinite cases:

  • $B(m,n)$ is infinite for all odd $n > 665$
  • $B(m,n)$ is infinite for even $n > 2^{48}$ and $n$ divisible by $2^9$
  • $B(m,3)$, $B(m,4)$ and $B(m,6)$ are finite for all $m$

And the example for the question is $B(2,5)$, for which it is not known whether it is finite. $B(2,5)$ also has the smallest $m$ and $n$ for which the problem remains open.

$\endgroup$
3
$\begingroup$

Finding Nash equilibria for $N$ players vs $N \to \infty$ players; see mean field games.

$\endgroup$
3
$\begingroup$

The Strategy-stealing argument in game theory would seem to fit here. Thus we know some games (e.g hex) are a first player win, but that knowledge doesn't help determine the necessary strategy.

$\endgroup$
3
$\begingroup$

In the spirit of D Poole's comment on the Zero-One Law, long-term probabilistic behavior is often a lot easier to deal with than short-term. A lot of elementary theorems in probability tell us about the asymptotic behavior of a sequence $(X_k)_{k \in \mathbb{N}}$ of random variables under suitable conditions. For instance, suppose I have a six-sided die, and I want to know the probability that in the first $600$ rolls, $1/3$ of the rolls were $4$. The formula for this value might be quite ugly when we want to look at this event after some specified number of rolls, but the strong law of large numbers tells us the probability of this happening over the long run (i.e. that $1/3$ of the rolls will be $4$) is $0$ (and further we can fairly easily provide more specific descriptions of the "size" of this outcome, e.g. Hausdorff dimension). So in general, though descriptions of the behavior of random variables might be ugly after finite time, we're often able to provide nicer descriptions of the long-term ("infinite time") behavior.

$\endgroup$
2
$\begingroup$

I don't believe nobody mentioned applications of the Central Limit Theorem (CLT).

For example calculating this: \begin{align} \int^{n+\sqrt[]{n}}_0 \frac{x^{n-1}}{(n-1)!}e^{-t}\,dt \end{align} is very easy when $n\to \infty$ using the CLT.

And yet another application of CLT itself is Wilk's Theorem very strong statement about the infinity case.

$\endgroup$

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.