## Examples of seemingly elementary problems that are hard to solve?

I'm looking for a list of problems such that

a) any undergraduate student who took multivariable calculus and linear algebra can understand the statements, (Edit: the definition of understanding here is that they can verify a few small cases by themselves )

b) but are still open or very hard (say took at least 5 years to solve),

Edit: c) and first proposed in the 20th century or later.

Edit : my motivation is to encourage students to addict to solving mathematical problems.

I know that there are many such problems in number theory and combinatorics, for trivial example, Fermat's last theorem. I'll be more interested in other fields, but less famous problems in number theory or combinatorics would be also welcome. For example,

1) The $n!$ conjecture can be stated in an elementary language, but had been notoriously hard. See section 2.2 in Haiman's paper http://arxiv.org/abs/math.AG/0010246 .

2) Let $r$ be any positive integer, and let $x_1, x_2$ be indeterminates. Consider the sequence ${x_n}$ defined by the recursive relation $$x_{n+1} =(x_n^r +1)/x_{n-1}$$ for any integer n. Prove that $x_n$ is of the form $P/Q$, where $P$ is a polynomial of $x_1$ and $x_2$ with non-negative coefficients, and Q is a monomial. This problem appeared as a special case of a conjecture by Fomin and Zelevinsky in the context of cluster algebras around 2001. They proved that $x_n$ can be written as $\frac{(\text{polynomial})}{(\text{monomial})}$. Proofs of positivity are recently obtained by Nakajima ( http://arxiv.org/abs/0905.0002 ) and Qin ( http://arxiv.org/abs/1004.4171 ).

3) Nagata conjecture : Let $r$ be a positive integer $\geq 10$, but not a square. Consider $r$ random points on the plane $R^2$. Let $m$ be any positive number. Prove that the degrees of plane curves passing through each of the $r$ points at least $m$ times are greater than $m\sqrt{r}$. See "Masayoshi Nagata, On the 14-th problem of Hilbert. Amer. J. Math. 81 (1959) 766–772". This is still wide open.

I'll be grateful for any more examples.

-
You might like the answers to this question mathoverflow.net/questions/51531/… . And since you're looking for a list of examples, you should check the "community wiki" box on your question. – jc Sep 17 2011 at 21:14
I'm not sure that publicizing lists like this is necessarily a good idea: these are the problems that create cranks. – Thierry Zell Sep 17 2011 at 21:16
Outside number theory: solution of the general cubic and quartic; impossibility of angle trisection and cube-doubling; unsolvability in radicals of the general quintic; the value of $\zeta(2)$; irrationality of $\pi$, and transcendence of $\pi$ and $e$; the 13-sphere problem, and Kepler's conjecture on sphere-packing in ${\bf R}^3$; asymptotics of Ramsey numbers (say $R(n,n)$); ... – Noam D. Elkies Sep 17 2011 at 21:27
Irrationality and transcendence are arguably number theory, and Ramsey numbers certainly fall under combinatorics... – Harry Altman Sep 18 2011 at 0:28
Does Goldbach count? – Steve Huntsman Sep 18 2011 at 5:26

This is another one where it's hard to establish a lower bound due to not much work having been done on it -- it's been open since at least the 1980's, possibly the 1950's, but it's a pretty isolated problem. I think though that we can say that it's probably hard because proving it would establish better lower bounds on gaps between powers of 2 and powers of 3. (Or so I think I've been told, I'm afraid I'm going on memory here.)

Let's let ||n|| denote the smallest number of 1's needed to write n using an arbitrary combination of addition and multiplication. For instance, ||11||=8, because $11=(1+1)(1+1+1+1+1)+1$, and there's no shorter way. This is sequence A005245.

Then we can ask: For n>0, is $\|2^n\|=2n$? Since it is known that for m>0, $\|3^m\|=3m$, we can ask more generally: For n, m not both zero, is $\|2^n 3^m\|=2n+3m$? Attempting to throw in powers of 5 will not work; ||5||=5, but $\|5^6\|=29<30$. (Possibly it could hold that $\|a^n\|=n\|a\|$ for some yet higher choices of a, but I don't see any reason that those should be any easier, though I suppose they might lack the same lower bound on hardness.)

Jānis Iraids has checked by computer that this is true for $2^n 3^m\le 10^{12}$ (in particular, for $2^n$ with n≤39), and Joshua Zelinsky and I have shown that so long as $n\le 21$, it is true for all m. (Fixed powers of 2 and arbitrary powers of 3 are much easier than arbitrary powers of 2!) In fact, using an algorithmic version of the method in the linked preprint, I have computed that so long as $n\le 41$, it is true for all $m$, though I'm afraid it will be some time before I get to writing that up...

I don't think anything better than that is currently known.

-
 This is known by some as the one-complexity of an integer; it would be nice to see some more recent references besides that of Wolfram and Ed Pegg Jr. I am suspicious about the claim of Altman and Zelinsky: a reference to that work would be welcome. (My memory says that there is a small n for which f(2^n) < 2n, but my memory has been wrong before.) Harry Altman, would you kindly supply a link to your work with Zelinsky? Gerhard "Pretend I Am From Missouri" Paseman, 2011.09.18 – Gerhard Paseman Sep 18 2011 at 23:06 Well, here's [the draft](www-personal.umich.edu/~haltman/onegenp1draft.pdf) on my website; the claim above also requires [this really long table I computed](www-personal.umich.edu/~haltman/shorttable.pdf). I will admit that verifying my computations is something of a problem (we couldn't figure out how to turn it into an algorithm, so I did them by hand; if you like I can send you the text files I did the computations in). However for low n the computations aren't long, and for n<=18 I also have an entirely different proof. (n<=13 follows from an earlier result of Rawsthorne.) – Harry Altman Sep 18 2011 at 23:13 Thank you for the reference. I will review it along with whatever notes of mine I can recover. I will be sure to contact you (or at least post here) if I find my memory is right. Thanks again for the link and the posting. Gerhard "Ask Me About System Design" Paseman, 2011.09.18 – Gerhard Paseman Sep 19 2011 at 0:38 @Gerhard Paseman: Now that we actually have more understandable preprint detailing our method, I've linked to it above. Also, now that we can automate these computations... well, just see what I wrote above. – Harry Altman Jul 26 at 7:39
-

Maybe you want to limit it to problems first proposed in the 20th century or later? Otherwise, proving the fundamental theorem of algebra took decades or longer. Gauss's first proof, for example, had a famous topological gap found in the 1920's.

Several of Hilbert's problems from 1900 are understandable at undergrad level and stayed open many years or are still open.

Then there are computer proofs, e.g. the 4-color theorem. Do those count? A few years ago we got a multi-year computer calculation finally proving that checkers is a theoretical draw, something everyone already knew even without an exhaustive proof.

Title of your question first sounded like merely "surprisingly difficult" rather than "stayed open at research level for a long time". One I like from some other MO thread: let C be a curve inside the unit square, connecting the lower left to upper right corner. Let D be a similar curve, connecting upper left to lower right. Prove that C and D intersect.

-
I think none means this question: mathoverflow.net/questions/35514/… – Joel Reyes Noche Sep 18 2011 at 1:05

What numbers are integrally represented by the three-variable inhomogeneous polynomial $$7 x^2 + 3 x y + 9 y^2 + z^3 \; \; ?$$ This is one of two similar problems where it is easy to show that certain integers are not represented owing to their prime factorization. The first inkling that it might be possible to prove if and only if on a characterization of represented numbers is due to Kevin Buzzard, in his answer to my first MO question. The list of similar problems for class number three is at LINKSECONDTRY but in any case works in my comment below

My first MO question, with answer by Kevin Buzzard and evidence about why if-and-only-if is difficult, is http://mathoverflow.net/questions/12486/

-
The OP would likely object that this is number theory. – Noam D. Elkies Sep 17 2011 at 21:46
agreed, "but less famous problems in number theory." Until today I'm the only one who knew this (and one of the few who know why it is open), so this is $< \mbox{famous}$ – Will Jagy Sep 17 2011 at 21:54
OK, but then it's hard to get a good lower bound on the problem's difficulty. – Noam D. Elkies Sep 17 2011 at 21:57
will works with manjul ??? – Luis H Gallardo Sep 18 2011 at 18:49
Luis, I have known Manjul Bhargava for a long time, but we are hardly in touch these days (after Kaplansky died). In April (I think) there was a week conference at MSRI, I told this and related problems to Manjul, Henri Cohen, and Hendrik Lenstra. I saw little sign at the time that any of the three would pursue the matter, but there seemed to be agreement that this was Manjul's area. I would be interested to hear if he has been working on this or, at least, mentioning my collection of similar problems in talks. Class number three problems at zakuski.utsa.edu/~jagy/jagy_list.pdf – Will Jagy Sep 18 2011 at 19:24

I will list two very hard problems in linear algebra, that are in fact closely related.

1. Recall that the cross product of vectors in $\mathbb R^3$ is not associative, and so if I write $v_1 \times v_2 \times \dots \times v_n$, I have not specified a reasonably map $(\mathbb R^3)^n \to \mathbb R^3$. Rather, to specify such a map, I must specify a parenthesization. Let's fix some $n$, and consider two different parenthesizations of $v_1 \times v_2 \times \dots \times v_n$ (e.g. for $n=3$, perhaps we consider $(v_1 \times v_2) \times v_3$ and $v_1 \times (v_2 \times v_3)$. Is it true that there exists an $n$-tuple of vectors so that both parenthesizations give the same nonzero answer?

2. Choose a (finite) trivalent graph $\Gamma$, meaning a graph in which every vertex has three edges emanating from it, along with the following data: for each edge in the graph, choose a "left" end and a "right" end, and for each vertex choose a "first", "second", and "third" edge. (Multiple edges connecting the same vertex are allowed, but with no loss of generality you can assume that no vertex connects to itself.) To such a graph $\Gamma$ I will assign a sequence of numbers $\Gamma(N)$ depending on a parameter $N \in \mathbb N$ — actually, the sequence will not depend on the choice of "left/right" for each edge, and will depend on the choice of "first/second/third" only up to a sign. Suppose the graph has $E$ edges and $V$ vertices (by trivalence, $2E = 3V$). The number $\Gamma(N)$ will be a sum of $(N^2)^E$ terms, indexed by assigning an ordered pair $(i,j)$ to each edge, where $i,j$ range from $1$ to $N$. Then what you do is this: near the left end of a given edge labeled $(i,j)$ write the $N\times N$ matrix which is all $0$s except for a $1$ in the $(i,j)$th spot, and near the right end write the matrices which is all $0$s except for a $1$ in the $(j,i)$th spot. Do this for every edge, and now go through the vertices. At each vertex, you see three $N\times N$ matrices, $x_1,x_2,x_3$, and I want you to compute $\operatorname{tr}(x_1x_2x_3) - \operatorname{tr}(x_1x_3x_2)$. That gives you a number for each vertex (depending on the edge labelings); multiply all these vertex numbers together. Finally, as I said above, to compute $\Gamma(N)$, sum this product over all $N^{2E}$ possible edge labelings.

Then it is a not too hard fact that for each graph $\Gamma$, $\Gamma(N)$ is a polynomial in $N$, with degree at most $2 + E - V = 2 + V/2$. The question is: Suppose that the coefficient of $\Gamma(N)$ on $N^{2 + E - V}$ is not zero. Is it necessarily true that $\Gamma(2)$ is nonzero? You can say this asymptotically: if $\lim_{N\to \infty} \Gamma(N) / N^{2 + V/2} \neq 0$, does it follow that $\Gamma(2) \neq 0$?

Each of these problems is borderline in combinatorics, but really is a natural question in linear algebra (cross products; or traces of matrices). In fact, the answer to both is "yes". But the only known proofs are very hard: both problems are equivalent to the Four Color Theorem in finite graph theory. If you are looking for problems to give in a class, these are great ones: it's possible that some undergrad will come up with a proof of one of them (especially 1), and then they have given an elementary proof of Four Color.

-
Just out of curiosity, is the equivalence to 4CT for either of these something that is itself difficult to see, or does it follow naturally from some clever way of rewriting either of the above problems? – ARupinski Sep 17 2011 at 22:38
For #2, the best write-up is by Dror Bar-Natan --- I don't have the reference handy. The short version: the leading coefficient in $\Gamma(N)$ counts the number of planar embeddings of $\Gamma$; given a planar embedding, $\Gamma(2)$ counts the number of 4-colorings of the faces. For #1, I have some recollection that there's a write-up by Kauffman, but I think the observation is first due to Penrose? It's not very hard to see the equivalence, especially if you understand the $\Gamma(2)$ part of #2. – Theo Johnson-Freyd Sep 18 2011 at 7:40
("counts" in my comment above means "counts up to some normalization factors", of course.) – Theo Johnson-Freyd Sep 18 2011 at 7:44
For an $n$-tuple of vectors, what does "both" parenthesizations refer to? – S. Sra Sep 18 2011 at 10:05
@suvrit: To the two different parenthesizations mentioned in the preceding sentence. – Hans Lundmark Sep 18 2011 at 13:26

Here are five problems which you might like:

(1) Are there 44 unit vectors in $\mathbb{R}^5$ where the dot product between each pair is less than $\frac{1}{2}$?

I originally saw this formulation on this MO post. It is open, and related to the kissing number in 5 dimensions.

(2) A Hadamard Matrix is a square matrix all of whose entries are $\pm1$, and whose rows are mutually orthogonal. Prove that there exists a Hadamard Matrix of size $4k$ for every $k\geq 1$.

This is known as the Hadamard Conjecture. While it was considered by Hadamard in the 19th century, it is still open today.

(3) Given $n$ distinct points in the plane, what is the minimum number of distinct distances between those points?

This is a famous problem of Erdos, and while it has not completely been resolved, a near optimal bound belongs to Guth and Katz. (See Terence Tao's blog post)

(4) Prove that $$\sigma(n)\leq H_n +e^{H_n}\log H_n$$ where $\sigma(n)$ is the sum of divisors function and $H_n=1+\frac{1}{2}+\cdots+\frac{1}{n}$ is the $n^{th}$ Harmonic number.

This problem is equivalent to the Riemann Hypothesis. This reformulation was done by Jeffrey Lagarias. (Since the reformulation was more recent, I think it qualifies for this list)

(5) If $\alpha\neq 0,1$ is algebraic, and $\beta$ is irrational algebraic, will $\alpha^\beta$ be transcendental?

This is the well known Hilbert's 7th Problem. This was resolved by Gelfond and Schneider in 1934. Related to this, there is the famous story of Hilbert giving a lecture in 1919 where he said that he might see the proof of the Riemann hypothesis in his life time, that the youngest members of the audience might live to see Fermat’s Last Theorem proved, but no one present in the hall would live to see a proof of transcendence of $2^{\sqrt{2}}$. Of course the exact opposite happened.

-
+1: very nice list :-) – S. Sra Sep 18 2011 at 10:08

One simple to state problem in number theory is the Collatz Conjecture, and I'm kind of surprised no one has mentioned this one yet (considering the examples you cite, I suspect it is because this one does not require anything beyond grade-school math to understand and so may seem below the level of this question). Nevertheless I add it to the list because it is amazingly addictive to think about.

-
I think more likely nobody mentioned it because it's so well-known. – Harry Altman Sep 18 2011 at 6:00

A forty years old open conjecture in automata theory, called the Černy conjecture, asserts that if $X$ is a set of mappings on $n$ symbols such that a constant map can be obtained by repeatedly composing maps from $X$, then a constant map can be obtained from a composition of at most $(n-1)^2$ elements of $X$, where repetitions are allowed. This is known to be a lower bound. The best known upper bound is cubic.

-

The naive algorithm for multiplying two $n\times n$ matrices takes $O(n^3)$ operations. Problem: Come up with an algorithm that does it in $O(n^{2.1})$. The best result so far is $O(n^{2.37})$, and the conjecture is that you can do it in $O(n^{2+\varepsilon})$ for any $\varepsilon>0$.

-

Singmaster's conjecture. Any 15-year-old can understand what it says. Singmaster wrote that Paul Erdős told him it's probably true but probably very hard to prove.

It says there's a finite upper bound on the number of times a number other than 1 appears in Pascal's triangle. For all anyone knows for sure, the upper bound could be 8. And only one number is known to appear that many times: $$\binom{3003}{1}=\binom{78}{2}=\binom{15}{5}=\binom{14}{6}.$$ It is known that infinitely many numbers appear 6 times; infinitely many appear 4 times; infinitely many appear 3 times, and infinitely many appear 2 times. (And only one appears just once.)

Whether any number appears an odd number of times where the odd number is more than 3 is unknown.

-
Well, I learned something today! Stupid question, though: are there any good reasons to believe that the conjecture is true? (Besides the fact that uncle Paul thought that it was, I mean.) – Thierry Zell Sep 22 2011 at 1:50
Singmaster did some computer searches that, for the time (1970s) might have been considered moderately extensive. I think his paper(s) on the subject might say a bit more than that. I seem to recall that some his remarks left me feeling that there's a certain untuitive plausibility, but I can't be more specific now. I seem to remember a remark that there is only one row of Pascal's triangle where three consecutive entries form an arithmetic sequence (row 14, i.e. the 15th row) and there might (or might not?) have been a hint that generally things can't happen very often in Pascal's triangle. – Michael Hardy Sep 22 2011 at 23:24

Is $\pi$ normal in base $b$, that is, are the base $b$ digits of $\pi$ evenly distributed among $0, 1, 2, \ldots, b-1$, for every integer $b > 1$? Same question for $e$, $\ln 2$, and $\sqrt{2}$. These and most well-known irrational numbers are not known to be normal in any base--yet almost all real numbers are normal in every base.

-

Cacetta conjecture. If every vertex of an $n$-vertex directed graph has at least $n/3$ edges leaving, then the graph has a directed triangle.

You can explain this even to a non-mathematician with a few pictures.

-

Is the sequence of fractional parts of $(3/2)^n$ dense in $[0,1]$?

This problem has a completeley elementary statement, yet noone has any idea how to prove it.

It is known that for almost every $t$, $t (3/2)^n \bmod 1$ is equidistributed in $[0,1]$ (this follows from a much more general result of Weyl), and also that for almost every $\beta>1$, the sequence $\beta^n\bmod 1$ is equidistributed in $[0,1]$ (This was proved by Koksma in the 30s).

It also follows from results of Pisot that $(3/2)^n \bmod 1$ has infinitely many accumulation points.

This question is somewhat related to the question (already mentioned in an answer) of whether famous irrational numbers are normal, but in a sense more elementary and frustrating because it is only about multiplication/division by $2$ and $3$!

-

One problem that my advisor infected me with was a conjecture of Peter Frankl: Let C be a finite collection of finite sets closed under union. The easy version asks: is there an element x in union C such that x is in at least half the members of C? The hard version asks if there is such a C in the easy version, except that union C is nonempty. I and several others have rediscovered partial results; the problem is still open from my perspective.

Another accessible problem for which some new research might be developed are the Graph Reconstruction Conjectures. One version uses vertices and asks which unlabeled graphs on n vertices are reconstructible from the collection of n subgraphs each on n-1 vertices. You can do a web search for variations with edges, directed graphs, and so on.

-

Zamolodchikov’s conjecture : Let $I$ be an $n$-element set of indices, and $A = (a_{ij})_{i,j\in I}$ an indecomposable Cartan matrix of finite type. (You don't have to use these words. There is an explicit list of matrices.) A family $(Y_i(t))_{i\in I,t\in \mathbb{Z}}$ of commuting variables satisfying the recurrence relations $$Y_i(t + 1)Y_i(t − 1) =\prod_{j\neq i} (Y_j(t) + 1)^{−a_{ij}}$$ is periodic, more precisely, there exists a positive integer $h$ such that $Y_i(t+2(h+2))=Y_i(t)$ for all $i$ and $t$.

This problem appeared in the theory of thermodynamic Bethe ansatz in 1991. Frenkel--Szenes and independently Gliozzi--Tateo proved a partial result (type A) around 1995, and Fomin and Zelevinsky completed in 2001.

-
 If I remember correctly, there is an extension of the conjecture, where the variables are labelled by a product of two (simply laced?) Dynkin diagrams, and where the periodicity is supposed to be the sum of the two dual coxeter numbers. I think that's stil open(?) – André Henriques Sep 30 2011 at 8:27

Conway's Thrackle Conjecture: $E \le V$ in any "thrackle," a particular type of drawing of a graph of $V$ vertices and $E$ edges in the plane. Dangerously addictive! And advances made every few years; it is by no means an isolated conjecture.

-

Take two commutative rings $A$ and $B$ such that the polynomial rings $A[X]$ and $B[X]$ are isomorphic. Does this imply that $A$ and $B$ are isomorphic? (I think this is still open.)

-
This problem is called "cancelation of indeterminates" and the answer is known to be negative if $X$ is an indeterminate or two. If $|X|>2$ it is open. See math.stackexchange.com/questions/13504/… – Bruno Stonek Sep 19 2011 at 1:10

Which (nonconvex) planar polygons can be dissected into squares? (Freiling et al., 2000)

-

Check out Unsolved Problems in Combinatorial Game Theory from More Games of No Chance RICHARD K. GUY AND RICHARD J. NOWAKOWSKI. This is from about 2002, so some of these probably have been partly solved, but many are very easy to state.

-

Can every convex polyhedron be cut along its edges and unfolded into one connected piece without overlap?

This problem was first posed formally by Shephard in 1975 (although it arguably dates back to the 1500s). There are also many related (un)folding problems which are still open, see http://maven.smith.edu/~orourke/TOPP/P9.html#Problem.9

-

The Casas Alvero conjecture: Let $f \in \mathbb{C}[x]$ be a monic polynomial of degree $n$. Suppose that for each $k = 1, \ldots, n-1$, there is a common root of $f$ and $f^{(k)}$. Then $f = (x-a)^n$ for some $a \in \mathbb{C}$. It is known only for the case that $n$ is a prime power or two times a prime power (see for example, this). At some point I thought I proved it :-)

-