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

http://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$
  • 1
    $\begingroup$ You might get more success if you sampled certain open problem lists and indicated which ones fit your list and which ones did not. I could mention various combinatorial problems such as integer complexity, determinant spectrum, covering design optimization, but I can't tell from your description if they would be suitable for you. Gerhard "They Are Suitable For Me" Paseman, 2012.06.21 $\endgroup$ – Gerhard Paseman Jun 21 '12 at 19: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$ – Alexander Chervov Jun 21 '12 at 20:53
  • 14
    $\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$ – Emil Jeřábek supports Monica Jun 22 '12 at 12:05
  • 12
    $\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 '12 at 13:05
  • 2
    $\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 '15 at 14:08

105 Answers 105

5
$\begingroup$

A conjecture arising from Waring problem: a number of solutions of the equation $$x_1^3+x_2^3+x_3^3=y_1^3+y_2^3+y_3^3,\qquad|x_i|,|y_i|<P,$$ is $O(P^{3+\varepsilon})$. The best known estimate is $O(P^{7/2+\varepsilon})$ (Hua Loo Keng).

$\endgroup$
5
$\begingroup$

Are there infinitely many partition numbers divisible by $3$? See A000041.

$\endgroup$
  • $\begingroup$ Could you perhaps expand a bit, i.e. for example what makes this a difficult problem, and what is known about the same question for divisors other than $3$? $\endgroup$ – Stefan Kohl Nov 9 '15 at 10:12
  • 1
    $\begingroup$ For example, it is known that there are infinitely many divisible by 2. It is hard for me to estimate how difficult the problem is, but it was publicly raised at OEIS more than 10 years ago (and I'm sure it had been discussed before), it is still open, and it is about a famous sequence that received much attention (and new interesting results) during last decade. The sequence graph suggests that the distribution of such numbers is quite irregular, they do not seem to to lie nicely on a smooth curve. $\endgroup$ – Vladimir Reshetnikov Nov 9 '15 at 17:23
5
$\begingroup$

Alexander's Conjecture, and by extension a lot of open problems about combinatorial subdivision, are as easy to understand as they are maddening. To quote Melikhov:

Alexander's 80-year old problem of whether any two triangulations of a [3-dimensional] polyhedron have a common iterated-stellar subdivision. They are known to be related by a sequence of stellar subdivisions and inverse operations (Alexander), and to have a common subdivision (Whitehead). However the notion of an arbitrary subdivision is an affine, and not a purely combinatorial notion. It would be great if one could show at least that for some family of subdivisions definable in purely combinatorial terms (e.g. replacing a simplex by a simplicially collapsible or constructible ball), common subdivisions exist...

Stellar subdivision (and arbitrary subdivisions) can be explained to a K-12 student with a picture. For a stellar subdivision, choose a face F, take its midpoint, and connect it to all vertices of tetrahedra of which F is a face. For arbitrary subdivision, invent some silly triangulation of a simplex, and just plug it inside. refining heighbouring simplexes as needed.

$\endgroup$
5
$\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$
5
$\begingroup$

(From Alon and Tarsi)

Let $A$ be a nonsingular $n$ by $n$ matrix over the finite field $\bf{F}_q$, $q>4$, then there exists a vector $x$ in $\bf{F}_q^n$ such that both $x$ and $Ax$ have no zero component.

$\endgroup$
  • 1
    $\begingroup$ It was proved to be true if q is not a prime or if q is prime and n is bounded by a function of q. $\endgroup$ – Joe Franklin Dec 8 '17 at 12:04
4
$\begingroup$

What is the least $V$ such that any convex body of unit volume can be fit into a tetrahedron of volume $V$? It is known that $V \ge 9/2$ and conjectured that $V = 9/2$.

$\endgroup$
4
$\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$
4
$\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$
3
$\begingroup$

I get the feeling that you will enjoy reading about the Simonyi and Chvatal conjectures described here by some guy called Gil Kalai. Anyone know who that is? ;)

$\endgroup$
3
$\begingroup$

Assuming that the definitions of a graph, its diameter and girth are something anyone can understand*, whether a graph with diameter $2$, girth $5$ and degree $57$ exists or not is a long standing famous open problem. See this or this.

There are several such (not especially famous) open problems regarding existence/uniqueness in the theory of bipartite Moore graphs (known as generalized polygons), i.e., graphs with diameter $d$ and girth $2d$, the prime power conjecture for finite projective planes that OP has mentioned being one of them. For example, is there a unique $4$-regular bipartite graph with diameter $6$, girth $12$, the so called generalized hexagon of order (3,3)?

*I have never had a problem with explaining this problem to people who have no math background beyond high school.

$\endgroup$
3
$\begingroup$

N. M. Katz: "Simple Things we don't know": https://web.math.princeton.edu/~nmk/pisa16.pdf

$\endgroup$
  • $\begingroup$ These will be a better fit here: mathoverflow.net/questions/101169/… when the collective net gods deem it time to reopen the question. $\endgroup$ – David Feldman Jul 14 '12 at 19:07
  • $\begingroup$ These will be a better fit here: mathoverflow.net/questions/101169/ when the collective net gods deem it time to reopen the question. Every vote helps, thanks. $\endgroup$ – David Feldman Jul 14 '12 at 19:08
2
$\begingroup$

The continuum hypothesis. Of course it's extremely famous, but everyone thinks it's resolved. I was astonished to find out that some serious set theorists apparently consider it (I mean in the present, decades past Cohen's proof) to be an important open problem that people should be working on solving (for some meaning of "solve").

P. Koellner ( http://logic.harvard.edu/EFI_CH.pdf ) describes some current approaches.

$\endgroup$
  • 1
    $\begingroup$ You seem to allude that it has not been resolved yet. But in that case you should explain what you mean by that. On the other hand, the continuum hypothesis is so well-known that it does not fit to the question. $\endgroup$ – Martin Brandenburg Jul 19 '12 at 12:17
  • $\begingroup$ +1 because the note you linked is really interesting! Although the "problem" is rather open-ended, I think it could be stated in a more well-defined way. Here's a stab at it: "If we want to settle the continuum hypothesis, which axioms should we add to ZFC in order to do it?" $\endgroup$ – Vectornaut Jul 22 '12 at 18:24
  • 5
    $\begingroup$ By the way, I think your statement that "everyone thinks it's resolved" is a little misleading. Maybe it would be better to say it this way: "most people think there's nothing left to say about it, because it's been proven independent of ZFC." $\endgroup$ – Vectornaut Jul 22 '12 at 18:26
  • $\begingroup$ this is not an open problem. It has been settled (like many impossibility results) a long time ago. $\endgroup$ – andrey bovykin Sep 10 at 4:08
2
$\begingroup$

Can a square with integer sides contain a point whose distance from each corner is an integer?

$\endgroup$
1
$\begingroup$

Ore's odd Harmonic number conjecture.

$\endgroup$
  • 1
    $\begingroup$ I suspect this fails on the fame criterion. Gerhard "Ask Me About System Design" Paseman, 2012.06.27 $\endgroup$ – Gerhard Paseman Jun 27 '12 at 14:22
  • $\begingroup$ Yes, but Ore's odd harmonic number conjecture, which if true, implies no odd perfect numbers, seems just right here. $\endgroup$ – David Feldman Jun 28 '12 at 4:35
  • 4
    $\begingroup$ Well, now it's so obscure that it requires a context/explanation. $\endgroup$ – Victor Protsak Jan 6 '14 at 20:45
1
$\begingroup$

Denote by $\sigma(m)$ be the sum of divisors of $m$. When is $ \sigma(n!-1) $ a perfect square?

$\endgroup$
  • 4
    $\begingroup$ Could you explain what is $\sigma$? $\endgroup$ – Ivan Izmestiev Sep 15 '17 at 15:55
  • $\begingroup$ Is this a long-open problem? Does it have a history? $\endgroup$ – Gerry Myerson Sep 15 '17 at 23:02
  • $\begingroup$ Numbers k such that σ(k) is a square are tabulated at oeis.org/A006532 – it is not even known that there are infinitely many of them (although this would follow from standard conjectures) $\endgroup$ – zeraoulia rafik Oct 17 '17 at 19:17
  • 2
    $\begingroup$ Isn't jstor.org/stable/10.4169/… proving that there are infinitely many? $\endgroup$ – Dima Pasechnik Jan 12 at 14:23

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