MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

share|cite|improve this question
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 – Gerhard Paseman Jun 21 '12 at 19:11
Here is some collection of some other "collect open problems" quests. on MO:… PS Nice question ! PSPS may be add tag "open-problems" – Alexander Chervov Jun 21 '12 at 20:53
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. – Emil Jeřábek Jun 22 '12 at 12:05
More precisely, K-12 means anything up to high school (K = Kindergarten, 12 = 12th grade, and K-12 covers this range). – Henry Cohn Jun 22 '12 at 13:05
There seems to be a claimed proof of the union-closed sets conjecture by Blinovsky – Marco Oct 22 '15 at 14:08

99 Answers 99

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Are there infinitely many $n\ge1$ such that $$ \gcd(2^n-1,3^n-1)=1 ? $$ Ailon and Rudnick conjectured that the answer is affirmative around 2000. What I like about this problem is that it could appear in Euclid, yet wasn't asked until fairly recently. There are obvious generalizations, and the analogue with $\mathbb Z$ replaced by $\mathbb C[T]$, is proven in the Ailon-Rudnick paper. There are also some (deep) results of Bugeaud, Corvaja, and Zannier giving the following related results:

  • There is a constant $C>0$ and infinitely many $n\ge1$ such that $$ \gcd(2^n-1,3^n-1) \ge \exp(C n/\log\log n) . $$
  • For every $\epsilon>0$ there is a $C_\epsilon$ such that $$ \gcd(2^n-1,3^n-1) \le C_\epsilon\exp(\epsilon n) \quad\text{for all $n\ge1$.} $$
share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

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?

share|cite|improve this answer

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

share|cite|improve this answer
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. – Vladimir Reshetnikov Nov 9 '15 at 17:23

Ore's odd Harmonic number conjecture

share|cite|improve this answer
Well, now it's so obscure that it requires a context/explanation. – Victor Protsak Jan 6 '14 at 20:45

protected by Community Oct 26 '15 at 4:22

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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