Examples of seemingly elementary problems that are hard to solve?

Question

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.

Answer 1

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\le39$), 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.

Answer 2

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.

Answer 3

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$!

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

The Jacobian conjecture.

Answer 8

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.

Answer 9

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$.

Answer 10

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.

Gerhard "Ask Me About System Design" Paseman, 2011.09.17

Answer 11

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, requiring that every pair of edges "meet" once. Dangerously addictive! And advances made every few years; it is by no means an isolated conjecture.

          

Answer 12

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.

Answer 13

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 :-)

Answer 14

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.

Answer 15

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

Answer 16

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.)

Answer 17

More number theory, but very elementary to state and, as far as I know, first proposed by Ailon and Rudnick in 2004, so not 20th century, but 21st century!

Conjecture [1] There are infinitely many integers $n\ge1$ such that $\gcd(2^n-1,3^n-1)=1$.

More generally, if $a,b\in\mathbb{Z}$ are multiplicatively independent, then there should be infinitely many $n\ge1$ such that $\gcd(a^n-1,b^n-1)=\gcd(a-1,b-1)$. (A rough, and not entirely believable, heuristic suggests that the set of primes $p$ such that $\gcd(a^p-1,b^p-1)=\gcd(a-1,b-1)$ has density 1.)

Ailon and Rudnick prove a stronger result with $\mathbb Z$ replaced with $\mathbb C[T]$, namely if $a(T)$ and $b(T)$ are multiplicatively independent, then there is a polynomial $c(T)\ne0$ such that $$ \gcd(a(T)^n-1,b(T)^n-1) \mid c(T) \quad\hbox{for all $n\ge1$.} $$

In the other direction, a deep result of Bugeaud, Corvaja, and Zannier [2] says that for every $\epsilon>0$ there is a $C=C(a,b,\epsilon)$ so that $$ \gcd(a^n-1,b^n-1) \le C\exp(\epsilon n)\quad\hbox{for all $n\ge1$.}. $$ So a hard, but proven, result that can be explained to students is prove that there is a constant $C$ so that (say) $$ \gcd(2^n-1,3^n-1) \le C\cdot 2^{n/10} \quad\hbox{for all $n\ge1$.} $$ (Further note: The proof in [2] does not give an effective way of computing the constant $C$, since it ultimately relies on Schmidt's subspace theorem.)

[1] N. Ailon and Z. Rudnick, Torsion points on curves and common divisors of $a^k-1$ and $b^k-1$, Acta Arith. 113 (2004), 31-38.

[2] Y. Bugeaud, P. Corvaja, U. Zannier An upper bound for the GCD of $a^n-1$ and $b^n-1$, Math. Z. 243 (2003), 79-84.

Answer 18

If you push together disks in the plane must their union decrease? More formally, given a set of disks in the plane consider each of the pairwise distances between their centers. If you decrease (or keep fixed) each of these pairwise distances, is the area of the union of the disks non-increasing?

The problem is solved in $\mathbb{R}^2$ (see the link in Shamisen's comment below). I believe the analogous problem is open for larger dimensions.

Answer 19

It is well-known that a simple random walk on a square integer lattice is recurrent to 0, meaning $P_0(X_t = 0 $ for some $t > 0) =1$. The standard proof is to show that $\sum_{t\ge 0} P(X_t = 0) = \infty$, which boils down to a combinatorial problem.

It is also well-known that the similar probability for 3-dimensional lattice is $<1$, whence the famous quote "a drunk man can eventually find his way home, but a drunk bird will be lost forever". Now consider the following edge-reinforced version of the 2d case first proposed by Persi Diaconis: initially all edges on $\mathbb{Z}^2$ have weight 1. As soon as an edge is traversed, its weight goes up to 2, and stays 2 forever. The probability of choosing an edge is proportional to its weight: so for instance if the four edges around a vertex is $(1,2,2,1)$, then with probability $1/6$ the first edge will be chosen. Note the edges are undirected, so the weight applies to both directions. This corresponds to the intuitive strategy of favoring roads one has seen before at an intersection. It seems this strategy could only make the walk more recurrent. However at least for the weight choices stated here, it has remained open. See this paper which discusses some history.

Answer 20

Here is a problem accessible to someone who has taken multivariable calculus or linear algebra:

What is the maximal number, $N$, of mutually unbiased bases in $\mathbb{C}^d$, a collection of orthonormal bases with vectors $x,y$ in separate bases satisfying $|\langle x,y \rangle|^2=\frac{1}{d}$?

This maximum number is known for all prime power dimensions $d=p^k$ so that first open case is $d=6$ where the best known upper bound is $N\leq7$. It is widely believed (due to numerical evidence) that in this case the largest number of MUB's is $N=3$.

Answer 21

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.

Answer 22

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.

Answer 23

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

Answer 24

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.

Answer 25

I like the "graceful tree conjecture": The vertices of every tree with $n+1$ vertices can be labelled bijectively by the set $\{0,\dots,n\}$ such that differences of labels on (suitably oriented) edges give the set $\{1,\dots,n\}$.

https://en.m.wikipedia.org/wiki/Graceful_labeling

Answer 26

Consider all possible sequences $(x_1,\ldots,x_n)$ in $\mathbb{Z}^2$ such that $x_1=0$, $|x_{i+1}-x_i| = 1$, and $i\neq j \rightarrow x_i \neq x_j$. For any fixed $n$, there are only finitely many of them so we pick one uniformly at random. Question: what is the asymptotic behaviour of $R_n = \mathbb{E}\sup_{i\le n} |x_i|$ as $n \to \infty$?

One trivially has $R_n \le n$ and $R_n \ge \sqrt{n/\pi}$. The conjecture (about 70 years ago by Flory) is that $R_n \approx n^{3/4}$. (The original argument apparently contained conceptual mistakes and reached the "correct" value somewhat by miracle. The modern argument is that if the self-avoiding random walk has a conformally invariant scaling limit, then it has to be one of the SLE($\kappa$), but SLE($8/3$) is the only one with the restriction property, so it has to be that one. The exponent then follows from the known self-similarity properties of SLE.)

To appreciate how far one is from proving this, consider that there is no theorem showing that there exists $\epsilon > 0$ such that either $R_n \lesssim n^{1-\epsilon}$ or $R_n \gtrsim n^{{1\over 2}+\epsilon}$! The best is a relatively recent article by Duminil-Copin and Hammond showing that $\lim_{n \to \infty} R_n/n = 0$... To the best of my knowledge, that argument does not provide any rate at all, so we still don't know that $R_n \lesssim n/\log\log n$ for example...

Answer 27

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 Integers not represented by $ 2 x^2 + x y + 3 y^2 + z^3 - z $

Answer 28

The Goldbach's conjecture:

Every even integer $k>2$ can be expressed as the sum of two primes.

The Waring's problem:

For each natural number $d$ there is a positive integer $h$ such that every natural number is the sum of at most $h$ $d$-th powers of natural numbers.

For every $d$, let $h(d)$ denote the minimum number of $d$-th powers needed to represent all integers. The problem is to find $h(d)$. For instance $h(1)=1, h(2)=4, h(3)=9, h(4)=19$.

Euler's conjecture: $h(d)=2^d+[(\frac{3}{2})^d]-2$.