# Good examples for mathemathical problems/statements that are easely solvable/provable in one theory and hard to solve/prove in another

Let $P$ be a mathematical statement or a mathematical problem. I am looking for a couple of nice examples for $P$ that satisfy the following criteria:

1. Given two (or more) mathematical points of view on $P$, we find that one of them views makes $P$ easy to solve/prove and the other one makes $P$ hard to solve/prove.

2. $P$ should (at least from the easier point of view) be understandable by someone who studied maths obtained the basics and has a quiet good understanding of mathematical problems.

3. It shouldn't take to much text to formulate, since I don't have that much time and space to present it.

It would be nice if the problem is prominent and it is ok if the problem is not pure math but must have a clear link to maths.

Any ideas? A short explanation of the problem from the different angels is welcome and appreciated.

Edit: I forgot to mention that by different point of view I meant somethink like looking at $P$ from an algebraic point of view and from an analytical point of view and maybe from a topological point of view. I want to point out the awesome properties of maths to transform a hard problem to another theory where the problem is easily solvable.

-
This is a really vague and broad question. "points of view" as in different proof strategies, or as in from different fields/domains of math, or as in...different theoretical stances, e.g. assuming the axiom of choice or without assuming it...This question, as it stands, could open pandora's box! –  amWhy Nov 11 '12 at 15:44
@amWhy As in different fields/domain. Thanks for asking. I edited my question. –  Aufwind Nov 11 '12 at 15:47
Thanks, that helps narrow things a little bit, at least! –  amWhy Nov 11 '12 at 15:48
@Aufwind, then I'll delete my answer. –  sxd Nov 11 '12 at 15:48
@DimitriSurinx Sorry for my unspecified original answer. Thanks for your effort! –  Aufwind Nov 11 '12 at 15:49

Matrix multiplication is associative: you could prove this by a computation, but it's obvious once you realize a matrix gives a function $\mathbb{R}^n \to \mathbb{R}^n$. This one is sort of cheating, because it's not clear why you'd want to multiply matrices unless you understood this property already.

Subgroups of free groups are free: this can be shown group-theoretically but is not obvious. Topologically, this says covers of graphs are graphs, which is obvious.

Hilbert's Theorem 90 can be proved directly in a couple paragraphs, using linear independence of characters, but spotting the theory of etale cohomology it just says that there are no non-trivial line bundles on a point.

-
in all these examples, by the way, the "work" is hidden somewhere - it's rare that you can get something for nothing. –  user29743 Nov 11 '12 at 16:05
Terry Tao calls that the law of conversation of hard work. We should be careful when applying this principle before saying something is not possible though. Hardy was skeptical that an elementary proof of the prime number theorem could be found, because the PNT is equivalent to a purely complex function theoretical statement about the Riemann zeta function, so how could totally elementary arguments do that? This seems like good reasoning, especially when coming from Hardy, but with the benefit of hindsight we see that the missing "hard work" is all in proving the equivalence itself! –  Katie Dobbs Nov 11 '12 at 16:36

The prime number theorem states that the number of primes less than a real number $x$ (denoted by $\pi(x)$ ) can be approximated by $x/\log x$ in the sense that $$\lim_{x\to\infty} \frac{\pi(x) \log x}{x} = 1.$$

Now, the very statement of this theorem uses the concept of primality and a limit of a real function, so any proof must, at the very least, use some elementary number theory and some basic real analysis. It turns out that it is indeed possible to prove the prime number theorem with only these basic tools (Selberg/Erdős discovered such a proof) but this proof is (relatively) quite difficult.

It was discovered several decades after the first proofs were found by Hadamard and de la Vallée-Poussin (independently) in 1896. Both of their proofs used complex analysis (in fact, they developed quite a lot of the theory of complex analysis largely with this purpose in mind I recall). So the Prime number theorem is an example of a theorem that can be stated with only elementary number theory and real analysis, and can be proved with much effort with only these theories, but is much more easily established by complex analytic methods.

-
Katie Nicely stated! –  amWhy Nov 11 '12 at 17:32
it's not easy, even with complex analysis. –  sperners lemma Nov 13 '12 at 18:32
It's certainly not trivial, but if you are familiar with the basics of complex analysis, you may want to look at Newman's Proof of the PNT. –  Gamma Function Mar 11 at 3:57

I propose something of a more elementary nature.

Parallelogram Law The sum of the squares built on the diagonals of a parallelogram is two times the sum of the squares built on two adjacent sides of the parallelogram.

As it is stated this is a statement in classical plane geometry which is not that easy to prove. If you are giving a lecture you could draw a picture at the blackboard and invite the public to think a bit about it: I'm quite confident that nobody will find the solution in one minute or so.

Now if you change the point of view, moving into analytical geometry, you'll see that the problem is solved by a completely straightforward computation: indeed, vectorizing the picture (the following is taken from Wikipedia)

you see that you only need to expand the squares $(x+y)\cdot(x+y)$ and $(x-y)\cdot(x-y)$, which is a familiar task to everybody who has had a course in elementary algebra.

-

There are uncountably many equations (e.g. $x^2 = -4$), and for that matter uncountably many problems which are unsolvable when restricted to real analysis -- but that have complex solutions. $$i = \sqrt{-1}\;\;\text{ to the rescue, so to speak}.$$

Similarly, a crucial advancement in mathematics occurred way back in ancient Greece, when Euclid concluded that there is no way to compute the diagonal of a $1\times1$ square in terms of the ratio of two lengths, geometrically or otherwise. From this he was motivated to establish that there must exist numbers $x$ (e.g. $\sqrt{2}$) such that $x \notin \mathbb{Q}$. In this case, $$\mathbb{R} \text{ to the rescue!}\;$$

-
I believe it was Hippasus who first concluded that $\mathbb Q \subset \mathbb R$ (showing that the diagonal of a $1\times 1$ square ...). As a result, because he dared to question Pythagoras who believed that $\mathbb Q = \mathbb R$, Pythagoreans throw him in the sea and he was drowned. One of Pythagoreans "motto" was "everything is made from integers" (in greek "Τα πάντα γίνονται από αριθμούς"). –  P.. Jun 3 '13 at 18:59
I learned the same, @P.. Happasus was taken to be a heretic! –  amWhy Jun 3 '13 at 19:02
There are only countably many equations. There are only countably many problems. There are countably many sentences in general, definitions, etc. –  ex0du5 Mar 11 at 2:20

The following theorem is quite easy to prove using model theoretic tools, but I heard it is very difficult with plain analysis tools:

Let $f\colon\mathbb{C^n\to C^n}$ be a polynomial function. If $f$ is injective then $f$ is a bijection.

There is a nice class of theorems in forcing whose proof is unclear (if even possible) when approaching to forcing by posets, whereas the proof is immediate when working with Boolean algebras (the completion of the separative quotient of the poset).

The following theorems come to mind immediately:

1. If $M$ is a model of ZFC, $M[G]$ is a generic extension of $M$ and $M\subseteq N\subseteq M[G]$, such that $N$ is a model of ZFC, then $N$ is generic over $M$ and $M[G]$ is generic over $M$.
2. If $P$ is a non-trivial countable forcing then $P$ is equivalent to a Cohen forcing (there is a unique countable atomless complete Boolean algebra).
-
I don't understand forcing - Cohen's book is just about incomprehensible to me - but I wonder about Cohen's recollection (I think in an interview, likely available online) that forcing didn't involve combinatorics, but rather was a shift in philosophical outlook. What exactly is forcing? –  alancalvitti Dec 11 '12 at 2:48
1. Fundamental theorem of Algebra:

Algebraic: I know of two proofs, one using induction and doing a whole lot of algebraic manipulations that made it quite lengthy. Another one uses Galois theory.

Complex Analytic: In my opinion some real cool proofs arise from complex analysis. The most elegant( IMO) is the proof using Liouville's Theorem though proofs using minimal modulus principle is also quite good.

2. Finding real integrals using contour integration.(Has been mentioned before by amWhy)

Right now these two stike my mind.

-
But in the algebraic proofs, do they use partial analysis results? Such as every odd degree polynomial has at least one root. –  mez Jul 29 at 7:02

This is a whole class of examples of the phenomenon you ask for, where a problem that is difficult in one theory is easy in another.

The fundamental theorem of Galois theory establishes a correspondence between field extensions and an associated group. This allows for a translation of problems in one to the other. Most of the time, it is field theoretic questions reaping the rewards - generally questions about field extensions are quite difficult, but questions about groups are easier.

For example, given a field extension E/F, could you fathom how to classify all the intermediate fields? If you are a pessimist, it seems like it even may be too hard a question to hope to be able to answer. With Galois theory however, this problem is converted to classifying the subgroups of a given group, which brings us back to much more familiar territory.

-

Goodstein's theorem, which makes an easily-understood assertion about easily-understood operations on integers, is not just 'difficult' to prove, but unprovable in Peano arithmetic; however, if we're allowed to use transfinite ordinals, the proof is really quite short.

As for "it is ok if the problem is not pure math but must have a clear link to maths", I think you're going to have trouble, because of things like the objections raised in Feynman's challenge.

-

I think this might be an example. Proving the fundamental theorem of arithmetic using topological methods. However, the proof is not very difficult. Check http://en.wikipedia.org/wiki/Furstenberg%27s_proof_of_the_infinitude_of_primes

This might be an example too. Abraham Robinson and Allen Bernstein proved that every polynomially compact linear operator on a Hilbert space has an invariant subspace using non standard analysis.

http://en.wikipedia.org/wiki/Non-standard_analysis#Invariant_subspace_problem

-
The second result I don't know what it is, but I thought it may be a good example because Paul Halmos proved te same result without using non standard analysis –  Amr Nov 11 '12 at 16:11

I know that the areas concerned are not entirely different, but here's another example.

Burnside's $p^{a}q^{b}$ Theorem: Every finite group of order $p^{a}q^{b}$ (where $p,q$ are primes and $a,b\geq 0$) is solvable.

The theorem was proved by William Burnside in 1904 using character-theoretic methods (or the method of linear substitutions as Burnside referred to it). However, it was not until 1970 - over 65 years after Burnside's original proof - that David Goldschmidt - using the ideas of John Thompson - produced a group-theoretic proof in the case that $p,q$ were odd primes. In 1973, Hiroshi Matsuyama completed the proof of Burnside's Theorem by proving that a group of order $2^{a}p^{b}$ was soluble. A year earlier, Helmut Bender had also given a full proof of the theorem in his paper A group theoretic proof of Burnside's $p^{a}q^{b}$-theorem.

The character-theoretic proof is a few pages long, whilst the group theoretic one takes up 15-20 pages.

-
Out of curiosity, why was a "group theoretic" proof desired? –  sperners lemma Nov 13 '12 at 18:35
@spernerslemma Other people may correct me if I'm wrong, but I thought it was just a case of people feeling that such an important result in group theory should be able to be proved using group theoretic methods, and not by appealing to results outside the immediate subject. –  David Ward Nov 14 '12 at 9:02

Brouwer fixed point theorem has many proofs. The one via Sperner's lemma is elementary and tedious (sorry sperners lemma), but as you develop more tools in topology the proofs become shorter and shorter. It's not that any particular viewpoint makes BFPT particularly hard, but in the course of developing topological tools you make thinking about the problem easier and easier.

Hard way: Sperner's lemma, triangulation of the disk. Easier ways: Poincare index theorem. Homotopy invariance of topological degree. Homology and first isomorphism theorem. Use $S^2$ is not a retract of $D^2$.

If you need this for a presentation, then going into all this stuff will be way beyond your time limit probably. But at least Brouwer FPT has interesting explanations and applications.

Another interesting problem is proving that $e$ is irrational. There's Fourier's proof (from the BOOK) using Taylor series, a small variation on this approach, I've seen one using Niven polynomials, a geometric one involving an intersection of nested sets in the real line, and Euler's proof via continued fractions (which he somehow got while doing differential equations).

The interesting thing about each of these is that they all have something extra unique to them. Taylor series makes this very short and sweet. Niven polynomials are actually powerful enough to prove that any rational power of $e$ is irrational, and I believe $\pi$ as well. The geometric one allows one to derive an "irrationality measure." And continued fractions are always cool, no exceptions. All are elementary (i.e. assumes no more than differentiation, integration, and Taylor series) except for Euler's continued fraction stuff, I couldn't get at this original work to figure out what he did.

-