382
$\begingroup$

Question: I'm asking for a big list of not especially famous, long open problems that anyone can understand. Community wiki, so one problem per answer, please.

Motivation: I plan to use this list in my teaching, to motivate general education undergraduates, and early year majors, suggesting to them an idea of what research mathematicians do.

Meaning of "not too famous" Examples of problems that are too famous might be the Goldbach conjecture, the $3x+1$-problem, the twin-prime conjecture, or the chromatic number of the unit-distance graph on ${\Bbb R}^2$. Roughly, if there exists a whole monograph already dedicated to the problem (or narrow circle of problems), no need to mention it again here. I'm looking for problems that, with high probability, a mathematician working outside the particular area has never encountered.

Meaning of: anyone can understand The statement (in some appropriate, but reasonably terse formulation) shouldn't involve concepts beyond high school (American K-12) mathematics. For example, if it weren't already too famous, I would say that the conjecture that "finite projective planes have prime power order" does have barely acceptable articulations.

Meaning of: long open The problem should occur in the literature or have a solid history as folklore. So I do not mean to call here for the invention of new problems or to collect everybody's laundry list of private-research-impeding unproved elementary technical lemmas. There should already exist at least of small community of mathematicians who will care if one of these problems gets solved.

I hope I have reduced subjectivity to a minimum, but I can't eliminate all fuzziness -- so if in doubt please don't hesitate to post!

To get started, here's a problem that I only learned of recently and that I've actually enjoyed describing to general education students.

https://en.wikipedia.org/wiki/Union-closed_sets_conjecture

Edit: I'm primarily interested in conjectures - yes-no questions, rather than classification problems, quests for algorithms, etc.

$\endgroup$
11
  • 2
    $\begingroup$ Here is some collection of some other "collect open problems" quests. on MO: mathoverflow.net/questions/96202/… PS Nice question ! PSPS may be add tag "open-problems" $\endgroup$ Jun 21, 2012 at 20:53
  • 2
    $\begingroup$ Nice question!! $\endgroup$
    – Suvrit
    Jun 22, 2012 at 3:25
  • 17
    $\begingroup$ To save the search for explanation of cryptic acronyms for those of us outside US, K-12 means high school. @Mahmud: You are using a wrong meaning of the word “problem”. The TSP is not an unproved mathematical statement, it is a computational task. $\endgroup$ Jun 22, 2012 at 12:05
  • 20
    $\begingroup$ More precisely, K-12 means anything up to high school (K = Kindergarten, 12 = 12th grade, and K-12 covers this range). $\endgroup$
    – Henry Cohn
    Jun 22, 2012 at 13:05
  • 3
    $\begingroup$ There seems to be a claimed proof of the union-closed sets conjecture by Blinovsky arxiv.org/abs/1507.01270 $\endgroup$
    – Marco
    Oct 22, 2015 at 14:08

115 Answers 115

12
$\begingroup$

The Happy Ending Problem

  • Says that any set of five points in the plane in general position has a subset of four points that form the vertices of a convex quadrilateral. More generally, Erdös and Szekeres proved that for any positive integer $N$, there is a minimal integer $f(N)$ such that any set of $f(N)$ points in the plane in general position has a subset of $N$ points that form the vertices of a convex polygon, and it is known that $f(N)$ is at least $1+2^{N-2}$.

An open question is: does $f(N)=1+2^{N-2}$ hold?. Taken from this MO link.

$\endgroup$
1
  • 6
    $\begingroup$ This recent preprint arxiv.org/abs/1604.08657 claims to "nearly settle" this conjecture.... $\endgroup$
    – Suvrit
    May 2, 2016 at 1:13
11
$\begingroup$

A meta-answer: I recommend Guy's Unsolved Problems in Number Theory and perhaps some of his others (Unsolved Problems in Geometry, Unsolved Problems in Combinatorial Games), which have many unsolved problems (both well-known and obscure), grouped into categories. Many of these are of attackable difficulty.

$\endgroup$
11
$\begingroup$

Is there a rectangle that can be cut into $3$ congruent connected non-rectangular parts?

$\endgroup$
3
  • 2
    $\begingroup$ There is not; this was shown by Samuel Maltby in 1994 here. However, the case of $5$, $7$, or $9$ pieces are open to my knowledge (the $11$ case has a positive answer). $\endgroup$ Oct 21, 2022 at 6:46
  • $\begingroup$ How do you cut it into $11$ pieces? $\endgroup$ Oct 21, 2022 at 23:00
  • 2
    $\begingroup$ See this MO thread for a diagram; you can do it with a hexomino given by attaching a domino to a $2\times 2$ square and tile a $6\times 11$ rectangle with the area-$6$ pieces. $\endgroup$ Oct 22, 2022 at 0:40
11
$\begingroup$

Let $R(x)=P(x)/Q(x)$ where $P(x)$ and $Q(x)$ are polynomials with integer coefficients and $Q(0)\neq 0$. Is there an algorithm that given $P(x)$ and $Q(x)$ as an input always halts and decides if the Taylor series of $R(x)$ at $x=0$ has a coefficient $0$?

$\endgroup$
2
11
$\begingroup$

Is there a positive integer which is both triangular and factorial except these obvious examples: $1, 6, 120$? (Tomaszewski conjecture, http://oeis.org/A000217)

$\endgroup$
11
$\begingroup$

Grundy's game is a two-player mathematical game of strategy.

The starting configuration is a single heap of objects, and the two players take turn splitting a single heap into two heaps of different sizes. The game ends when only heaps of size two and smaller remain, none of which can be split unequally.

Whether the sequence of nim-values of Grundy's game ever becomes periodic is an unsolved problem. Elwyn Berlekamp, John Horton Conway and Richard Guy have conjectured that the sequence does become periodic eventually, but despite the calculation of the first $2^{35}$ values by Achim Flammenkamp, the question has not been resolved.

$\endgroup$
11
$\begingroup$

The Alon-Tarsi Conjecture:

A latin square of order $n$ is a filling of an $n\times n$ matrix with the numbers $1, 2,\ldots,n$ such that each row or column gives a permutation of $1,2,\ldots,n$. Take the product of the signs of these $2n$ permutations and call it the sign of the latin square. Let $EVEN(n)$ be the number of latin squares with sign $+1$ and let $ODD(n)$ be the number of latin squares with sign $-1$. The conjecture says:

If $n$ is even then $EVEN(n)\neq ODD(n)$.

The original reference is: N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), 125-134. See also this preprint by Landsberg and Kumar for a recent update.

$\endgroup$
11
$\begingroup$

From Rick Kenyon's open problem list:

What are the minimal number of squares needed to tile an $a \times b$ rectangle?

Kenyon showed the correct order is $\log a$ assuming $a/b$ is bounded with $b \leq a$. However, there is plenty of room for improvement in the constant factor, and an exact formula seems far, far away.

$\endgroup$
1
  • $\begingroup$ Is it easy to describe an optimal tiling for a $a\times (a-1)$ rectangle? Is the exact asymptotic known for this case? $\endgroup$ Oct 12, 2017 at 18:36
10
$\begingroup$

What is the largest possible volume of the convex hull of a space curve having unit length?

$\endgroup$
1
10
$\begingroup$

The Polya--Szego conjecture for polygonal drums: among the polygonal drums with $n$ sides and given area, the regular one has the slowest vibration (and therefore the lowest tone).

As far as I know, this remains open for $n\geq 5$.

$\endgroup$
10
$\begingroup$

The easy-to-understand "equal sums of like powers" problem, which generalizes Pythagorean triples:

$$3^2+4^2 = 5^2$$

$$3^3+4^3+5^3 = 6^3$$

In general, does,

$$x_1^k+x_2^k+\dots +x_k^k=z^k$$

have a non-zero integer solution for all positive integer $k$?

So far, integer solutions are known for all $k\leq9$, except $k=6$.

(Unfortunately, the Eulernet search for $k=6$ has been stopped since the mid-2000s. With today's computers, and with a distributed search, it may be feasible to find it now.)

$\endgroup$
10
$\begingroup$

Enumeration of meanders. (See also meander).

Problem is to find some formula for the number of meanders or at least some good asymptotic.

As far as I understand the attention to it has been attracted by V.I. Arnold. The problem is so "everyone can understand" that there is an article by him in the math. journal for shool-children "Quant" (sorry it is in Russian. I remember it from my school years): djvu file from the site.

There are plenty papers in arXiv on the problem.

E.g. https://arxiv.org/abs/cond-mat/0003008 Exact Meander Asymptotics: a Numerical Check Philippe Di Francesco, Emmanuel Guitter (SPHT-Saclay), Jesper Lykke Jacobsen (LPTMS-Orsay)

As far as I understand from the nice book (or) by S. Lando and A. Zvonkin the problem is still open.

$\endgroup$
2
9
$\begingroup$

Can one prove the infinitude of the primes without employing any functions of super-polynomial growth?

(Of course I confess I have in mind Paris and Wilkie's more precise and sophisticated question concerning primes in the theory of bounded induction, but I think a high school student could think about looking for a positive answer without that background.)

$\endgroup$
10
  • 2
    $\begingroup$ Where are functions of exponential growth used in the classical proof, or the Euler product + divergence of harmonic series? $\endgroup$ Jun 24, 2012 at 14:06
  • 1
    $\begingroup$ In the classical proof, the exponential growth is in the product of the known primes. See mathoverflow.net/questions/59262/… for a more precise discussion. In the Euler product proof, I imagine the growth occurs in the Chinese-remainder-theorem-based coding tricks necessary to express this proof in the language of first-order arithmetic, but I haven't thought this through carefully so maybe I'm totally off base. $\endgroup$
    – Henry Cohn
    Jun 24, 2012 at 16:49
  • $\begingroup$ Thanks. The second answer to that question says in part, "functions of exponential growth aren't necessary, but we are still using a function of super-polynomial growth." That seems to contradict the statement that this is open. $\endgroup$ Jun 24, 2012 at 18:01
  • 3
    $\begingroup$ See also mathoverflow.net/questions/76058 . David, contrary to what you write, it is possible to define in bounded arithmetic a function computing rational approximations of logarithm. This does not imply that exponentiation is total, since there may be numbers greater that all values of logarithm. As for divergence of harmonic series, the problem is even to express this statement in bounded arithmetic: you cannot in general define $\sum_{n\le x}f(n)$ by a bounded formula, unless $x$ is logarithmic. $\endgroup$ Jun 25, 2012 at 11:35
  • 1
    $\begingroup$ Even if you restrict attention to small $x$, there is the question how do you formulate “divergence”. Bounded arithmetic certainly cannot prove that for every $y$, there exists $x$ such that $\sum_{n\le x}n^{-1}$ is defined and larger than $y$. However, I think that with appropriate formulations, it can prove that for every $y$, either there exists such an $x$, or all sums $\sum_{n\le x}n^{-1}$ that are defined have value less than, say, $y/2$ (which means the sum does not converge to $y$). Anyway, this is largely irrelevant. The real show-stopper in the proof using the Euler product is... $\endgroup$ Jun 25, 2012 at 11:52
9
$\begingroup$

Easy-to-Explain but Hard-to-Solve Problems About Convex Polytopes slides by Jes´us De Loera contains 7 open problems (Hirsch conjecture is also there so it is out-of-date).

$\endgroup$
1
  • $\begingroup$ Do you know of a source for the existence of hamiltonian triangulations of polyhedra being open? $\endgroup$ Jan 4 at 9:10
9
$\begingroup$

I think you could give an accessible K-12 formulation of the definition of a group (as a group of permutations, for instance) and of an integral group ring. The Zero Divisor Conjecture (Kaplansky, 1940) then states, in one version, that if $G$ is a torsion-free group then the group ring $\mathbb{Z}[G]$ has no zero divisors besides the number $0$.

$\endgroup$
7
  • 1
    $\begingroup$ >I think you could give an accessible K-12 formulation of the definition of a group ... In any case this is perfect for my follow-up question which the net gods decided to close for the time being. $\endgroup$ Jul 13, 2012 at 5:36
  • 1
    $\begingroup$ @David just wanted to write the same :) mathoverflow.net/questions/101169/… $\endgroup$ Jul 13, 2012 at 6:18
  • $\begingroup$ I agree that one could just about formulate the conjecture for "higher mathematics beginners" -- though exactly where would be an issue, IMHO -- but I am not so sure that one can get people to appreciate the conjecture $\endgroup$
    – Yemon Choi
    Jul 14, 2012 at 12:34
  • $\begingroup$ @Yemon Choi it might be useful for those who wish to become mathematicians, may be they will not appreciate it immediately but will be aware of it. It does not mean that will work on it some future, there are some indirect uses like - creating some taste what is good what is bad, etc. $\endgroup$ Jul 14, 2012 at 17:53
  • $\begingroup$ Speaking for myself, when I first encountered this, I found it very surprising it wasn't known, and deeply intriguing on its own merits. My context was low dimensional topology (for me, G was the fundamental group of a 3-manifold). But even without getting into applications, it's clear that without answering this we're ignorant about how to work with integral group rings. $\endgroup$ Jul 14, 2012 at 19:47
9
$\begingroup$

Do there exist five positive integers such that the product of any two of them increased by 1 is a perfect square?

The same question for seven distinct nonzero rationals.

Diophantine m-tuples pages

$\endgroup$
1
  • 5
    $\begingroup$ The link given to the Diophantine m-tiples pages now says that an article posted on arXiv in October 2016 (arXiv:1610.04020 [math.NT]) claims to answer the first of these two questions in the negative. $\endgroup$ Nov 4, 2016 at 5:26
9
$\begingroup$

The following problem is very well-known among algebraic geometers:

Does there exist a cubic 4-fold that is not rational?

It's probably not well-known outside of algebraic geometry, even though it can easily be explained in every elementary terms:

Does there exist a polynomial equation $F$ of degree three in five variables with the following property: Let $X \subset \mathbb C^5$ be the solution set of $F = 0$. Then there exists no chart $U \subset \mathbb C^4, \phi \colon U \to X$ such that $\phi$ is defined by rational functions (i.e., quotients of polynomials).

$\endgroup$
3
  • 1
    $\begingroup$ Cool ! what are the references for current state of art ? $\endgroup$ Jul 24, 2012 at 9:57
  • 2
    $\begingroup$ Basically nothing is known. On the other hand, it is easy to construct cubics that are rationals - e.g. cubics containing two planes. There are two conjectural descriptions of the locus of rational cubics inside the moduli space of cubics: one is due to Hassett and Harris; math.sunysb.edu/Videos/AGNES/video.php?f=04-Harris is video of a talk by Harris on the question; for Hassett's related results search "Hassett cubic fourfolds" on google scholar. Kuznetsov has a conjecture in terms of derived categories, the reference is: front.math.ucdavis.edu/0808.3351. $\endgroup$ Jul 24, 2012 at 22:03
  • $\begingroup$ K-12??? $\textrm{}$ $\endgroup$ Jan 6, 2014 at 20:12
9
$\begingroup$

The following conjecture by Carsten Thomassen:

If $G$ is a 3-connected graph, every longest cycle in $G$ has a chord.

Thomassen has proven the conjecture true for 3-connected cubic graphs.

$\endgroup$
9
$\begingroup$

One I saw in a talk yesterday by Faustin Adiceam (I hope I have remembered this correctly):

Danzer's problem (in dimension 2): Is there a subset $S$ of $\mathbb{R}^2$ of finite density (the number of points at distance $\le r$ from the origin is $O(r^2)$) that hits every rectangle of unit area?

There is also a version where instead of positive density, a stronger condition is imposed: there is $\delta > 0$ such that any two points in $S$ are at least distance $\delta$ apart.

(Both versions are usually stated for convex sets, but the rectangle versions are equivalent, as any convex set of area $1$ is contained in a rectangle of area $2$ and contains a rectangle of area $1/2$.)

$\endgroup$
1
  • $\begingroup$ Is this the same problem as in mathoverflow.net/q/3307/5340 "Can a discrete set of the plane of uniform density intersect all large triangles?" $\endgroup$ Nov 14, 2016 at 13:27
9
$\begingroup$

Given $n\in\mathbb N$, what is the smallest $k\in\mathbb N$ such that the harmonic number $H_k>n$?
It has been conjectured that for all $n$ the answer is $\lfloor\exp(n-\gamma)-1/2\rfloor$. See A002387.

$\endgroup$
9
$\begingroup$

Farideh Firoozbakht conjecture states that the sequence $P_n^{1/n}$ is strictly decreasing, where $P_n$ is the $n-$th prime number. This conjecture can also give simple proofs to many theorems related to Prime numbers.

It is not proved yet.

$\endgroup$
9
$\begingroup$

Waring's problem inequality

One of the oldest (Since 1770) and famous open problem in number theory is Waring's problem. It has been conjectured that if

$$ \left\{\left(\frac{3}{2}\right)^n\right\} \le 1 - \left(\frac{3}{4}\right)^n. $$

(where $\{ \cdot \}$ denotes the fractional part) true then, the general solution of Waring's problem is

$$ g(n) = 2^n + \left\lfloor{\left(\frac{3}{2}\right)^n}\right\rfloor - 2. $$

$\endgroup$
2
  • 4
    $\begingroup$ If I understand correctly, the statement given here has actually been proved in work by Dickson, Pillai, Rubugunday, and Niven. (This is stated in section 6.2.7 of Bombieri and Gubler's book, Heights in Diophantine Geometry.) The conjecture, which coupled to this result would complete the solution of Waring's problem, is that the the stated diophantine inequality (on the fractional part of $(3/2)^n$), should hold true for all $n$. It is an ineffective consequence of Roth's theorem (as extended by Mahler to several places) that it holds for $n \gg 0$. $\endgroup$ Dec 17, 2014 at 17:35
  • 3
    $\begingroup$ The post is misstated: the inequality is known to be true eventually, thanks to K. Mahler. See the related dx.doi.org/10.5802/jtnb.588 for a historical account and recent novelties. $\endgroup$ Nov 11, 2015 at 4:01
9
$\begingroup$

Some pages:
Open Problem Garden
The Open Problems Project edited by Erik D. Demaine, Joseph S. B. Mitchell, Joseph O’Rourke

$\endgroup$
1
  • 4
    $\begingroup$ [Removed the link to my open-problem page, which is more than a decade old; most of those problems are now solved.] $\endgroup$
    – JeffE
    Jun 22, 2012 at 12:06
8
$\begingroup$

It is not possible to find three corners of a square that form an equilateral triangle. (Left as an exercise for the reader.)

It is, however, possible to find four corners of a cube that form a regular tetrahedron:

                                          enter image description here

We could ask: in which dimensions $n>1$ is it possible to do such a thing - find a subset of the corners of the $n$-cube which form an $n$-simplex?

The answer: it is conjectured to be the case if and only if $n\cong 3\pmod{4}$, but remains open! The congruence condition is easily seen to be necessary, but existence of solutions for such $n$ has only been shown up through $n=663$ as of this writing.

(When you express the vertices of the $n$-cube as the set of length-$n$ $(0,1)$-tuples and do a little algebraic reshuffling, it becomes clear that this is equivalent to the Hadamard conjecture, a problem which was mentioned in an earlier comment but which I think becomes much more accessible under this framing.)

$\endgroup$
8
$\begingroup$

Is there such $n\in\mathbb{N}$ that ${^n\pi}\in\mathbb{N}$? (see tetration)

$\endgroup$
8
$\begingroup$

https://en.wikipedia.org/wiki/Keller%27s_conjecture

From Wikipedia:

Keller's conjecture is the conjecture introduced by Ott-Heinrich Keller (1930) that in any tiling of Euclidean space by identical hypercubes there are two cubes that meet face to face.

Keller's original cube-tiling conjecture remains open in dimension 7.

Conjecture was shown to be true in dimensions at most 6 by Perron (1940a, 1940b). However, for higher dimensions it is false, as was shown in dimensions at least 10 by Lagarias and Shor (1992) and in dimensions at least 8 by Mackey (2002), using a reformulation of the problem in terms of the clique number of certain graphs now known as Keller graphs. Although this graph-theoretic version of the conjecture is now resolved for all dimensions, Keller's original cube-tiling conjecture remains open in dimension 7.

The related Minkowski lattice cube-tiling conjecture states that, whenever a tiling of space by identical cubes has the additional property that the cube centers form a lattice, some cubes must meet face to face. It was proved by György Hajós in 1942.

Szabó (1993), Shor (2004), and Zong (2005) give surveys of work on Keller's conjecture and related problems.

$\endgroup$
1
  • 2
    $\begingroup$ Apparently the final case of Keller's conjecture was resolved recently (in the affirmative) by a computer assisted proof: arxiv.org/abs/1910.03740 $\endgroup$
    – Terry Tao
    Oct 12, 2019 at 1:22
7
$\begingroup$

What is the least $S$ (if any) such that any subset of a plane of area $S$ contains $3$ vertices of a triangle of unit area?

$\endgroup$
7
$\begingroup$

This requires some multivariable calculus, so maybe it is not strictly speaking to "everyone", but you could still use it when teaching undergraduates: the unique continuation for the $p$-Laplace equation.

Let $\Omega \in \mathbb R^3$ be an open domain. Suppose $u \in C^2(\Omega)$ and $$ \nabla \cdot (|\nabla u|^{p-2}\nabla u) = 0 \ \ \text{in}\ \Omega, \quad 1 < p \neq 2, $$ with $u\equiv 0$ in some open ball $B \Subset \Omega$. Then the question is to show that necessarily $u \equiv 0$ in all of $\Omega$.

The real open problem is to show this for all weak solutions (which are known to be $C^{1,\alpha}$), but I think this is open also for $C^2$-functions; so posing this makes sense also without any knowledge above multivariable calculus.

$\endgroup$
2
  • $\begingroup$ $p\neq2$ I guess. $\endgroup$
    – username
    Aug 1, 2015 at 14:55
  • $\begingroup$ Yes, of course. :) $\endgroup$ Aug 1, 2015 at 17:45
7
$\begingroup$

I really like this problem of Busemann and Petty (Problems on convex bodies, Math. Scand., 1956):

Given a $0$-symmetric convex body $K$ and one of its support hyperplanes, construct the solid cone whose apex is a point at which the hyperplane touches the body and whose base is the central section of $K$ that is parallel to the hyperplane. Clearly the volume of this cone will be independent of the choice of contact point (in the case the support hyperplane intersects the body in more than one point). Now assume that no matter what support hyperplane you choose, the volume of the cone is always the same. Is $K$ an ellipsoid?

As far as I know there are not even meaningful partial solutions to this problem (e.g., assume $K$ is three-dimensional and the boundary of $K$ is real analytic and strictly convex).

$\endgroup$
7
$\begingroup$

The list coloring conjecture: A list of colors is assigned to each edge of a finite graph $G$. A "list coloring" of $G$ is an edge-coloring such that (1) each edge is colored with a color from its list, and (2) edges that meet at a vertex have different colors. Suppose the graph $G$ admits a list coloring when the list $\{1,2,\dots,n\}$ is assigned to every edge; does it still admit a list coloring when an arbitrary list of $n$ colors is assigned to each edge?

$\endgroup$

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