Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Define a graph with vertex set $\mathbb{R}^2$ and connect two vertices if they are unit distance apart. The famous Hadwiger-Nelson problem is to determine the chromatic number $\chi$ of this graph. For the problem as stated (there are many variations), the best known bounds are $4 \leq \chi \leq 7$. The lower bound comes from the existence of a clever subgraph on just seven vertices that is readily seen to require four colors. The upper bound comes from a straightforward tiling of the plane by monochromatic hexagons that admits a proper $7$-coloring.

I like to show this problem to young students because they are always fascinated by the fact that we can cover "everything" that is known about it in just a few minutes. What are some other problems of this type?

What are some famous problems for which the best known results are fairly obvious or elementary?

share|improve this question
2  
Fermat primes 2^2^n + 1. –  zyx May 30 '13 at 18:15
4  
Any knucklehead, looking at the prime factorizations of the first four perfect numbers (known since antiquity), or perhaps even the first two perfect numbers, could conjecture that they are all of the same type, $2^{p-1}\left({2^p-1}\right)$ for prime $p$ and prime $2^p-1$. It's easy to show that all numbers of that type are perfect. All known perfect numbers are of that type. Euler proved that all even perfect numbers are of that type. But… –  MJD May 30 '13 at 18:20

5 Answers 5

The first four perfect numbers have been known for at least 2300 years. Here are their prime factorizations:

$$\begin{align} 6 & = 2^{\hphantom{2}}\cdot 3 \\ 28 & = 2^2\cdot 7 \\ 496 & = 2^4\cdot 31 \\ 8128 & = 2^6\cdot 127 \end{align} $$

Any knucklehead, looking at these, or perhaps even just looking at the first two, could make the obvious conjecture that they are all of the form $2^{p−1}(2^p−1)$ for prime $2^p−1$.

It's easy to show that all numbers of that type are perfect. All known perfect numbers are of that type. Euler proved that all even perfect numbers are of that type. But…

share|improve this answer

Is $\pi$ a normal number?

All we know is that rational numbers are not normal, and that $\pi$ is irrational.

You can just as well replace $\pi$ by many other constants, and we don't know much about any of them.

share|improve this answer
    
This is a good answer, but I don't know of an elementary or obvious proof of the irrationality of $\pi$. –  Austin Mohr May 30 '13 at 19:23
3  
@Austin, by Wikipedia's "Normal number" article you can replace it by $\sqrt2$ as well. –  Asaf Karagila May 30 '13 at 20:03
    
That's a good example! The amount of stuff that isn't known about $\pi$ is quite amazing. –  MJD Jun 2 '13 at 2:29

Let $S$ be a set of integers, each greater than 1, and $m(S)$ be the largest positive integer that is not expressible as a sum of elements of $S$, if it exists. (Elements of $S$ may be used more than once, of course, so that $7 = 2+2+3$ is considered to be a sum of 2's and 3's.) A well-known example is $m(\{6, 9 ,20\}) = 43$.

J.J. Sylvester showed (1884) that $m(S)$ exists if and only if $\gcd(S) = 1$, and also that $m(\{s_1, s_2\})$, when it exists, is equal to $$s_1s_2 - s_1 - s_2.$$ Both of these could certainly be conjectured, and probably proved, in an hour by a bright high-school student.

But for $|S| > 2$ the problem is wide open.

share|improve this answer

This isn't "famous", but it's long been of interest to me:

What is the Pythagorean Theorem for right-corner simplices in hyperbolic $d$-space?

  • For $d=2$, we have ... $$\cosh a \cosh b = \cosh c$$ for a triangle with legs of length $a$, $b$, and hypotenuse of length $c$.
  • For $d=3$, we have ... $$\cos\frac{A}{2}\cos\frac{B}{2}\cos\frac{C}{2} - \sin\frac{A}{2}\sin\frac{B}{2}\sin\frac{C}{2} = \cos\frac{D}{2}$$ for a tetrahedron with right-triangular leg-faces of area $A$, $B$, $C$, and hypotenuse-face of area $D$.
  • For $d\geq 4$, we have ... $$\text{No Idea. (So far as I know.)}$$

Three(!) years ago, I posted some thoughts about the $d=4$ case to MathOverflow. (The series stuff is probably mis-guided.) I've made no progress since then.

share|improve this answer

Here's a little ditty from Complexity Theory.

The following facts are quite easy to prove:

  1. $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXPTIME} \subseteq \mathsf{EXPSPACE}$;
  2. $\mathsf{L} \neq \mathsf{PSPACE}$;
  3. $\mathsf{PSPACE} \neq \mathsf{EXPSPACE}$.

By (2) it immediately follows that at least one of the first four inclusions in (1) is proper, and, similarly, by (3) at least one of the last two inclusions in (1) is proper. However it is completely unknown which inclusions in (1) are proper (though it is strongly suspected that each is). (Note that this subsumes the famous $\mathsf{P} \overset{\mathord{?}}{=} \mathsf{NP}$ problem.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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