Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

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.

share|improve this question
1  
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
2  
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" –  Alexander Chervov Jun 21 '12 at 20:53
1  
Nice question!! –  Suvrit Jun 22 '12 at 3:25
13  
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
8  
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

79 Answers 79

Can a disk be dissected into two or more pieces, with its centre lying within one of the pieces?

share|improve this answer
3  
Surely there is a missing condition here. Maybe the pieces are required to be congruent? –  zeb Mar 11 at 11:50

Is the sequence $(3/2)^n \mod 1$ dense in the unit interval?

In the other direction, Mahler's 3/2 problem:

Do all elements of this sequence with large enough index $n$ lie in the interval $(0,1/2)$?

It is known that $\beta^n$ is uniformly distributed modulo one for almost all $\beta>1$, but explicit examples of $\beta$ for which density holds are not known. This question seems to originate in work of Weyl and Koksma on uniform distribution.

Update: Since posting this answer I've attempted to find some references with which to flesh it out, with only modest success. The earlier paper I have identified which deals with this question directly is T. Vijayaraghavan's 1940 article On the fractional parts of the powers of a number, in which it is shown that the sequence $(3/2)^n \mod 1$ has infinitely many limit points. Mahler conjectured in 1968 that the answer to his question is negative. Jeffrey Lagarias' 1985 survey on the Collatz problem, The 3x + 1 Problem and Its Generalizations, includes a one-page overview of the literature on the distribution of this sequence. Flatto, Lagarias and Pollington subsequently proved that the diameter of the set of accumulation points is at least 1/3; Mahler's question would be answered in the negative if this is improved to "at least 1/2".

share|improve this answer
1  
An excellent reference is the recent book Distribution modulo one and Diophantine approximation, by Yann Bugeaud. –  Andres Caicedo Jan 6 at 19:35

Imre Ruzsa conjectured in 1971 (Mat. Lapok 22, in hungarian) that a congruence-preserving mapping $f : \mathbb{N} \to \mathbb{Z}$ is a polynomial as soon as the power series $A(t) := \sum_{n \in \mathbb{N}} f(n)t^n \in \mathbb{Z}[[t]]$ has radius of convergence $> 1/e$. (Congruence-preserving simply means $n-m \mid f(n)-f(m)$.)

This is still an open problem, although A. Perelli and U. Zannier have shown that the power series $A(t)$ must be $D$-finite ("On recurrent mod $p$ sequences," J. reine angew. Mat. 348, 1984). The best result on Ruzsa's problem is due to U. Zannier ("On periodic mod $p$ sequences and G-functions," Manuscripta math. 90, 1996).

share|improve this answer

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

share|improve this answer

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?

share|improve this answer

Is the density of $1$s in the Kolakoski sequence $122112122122112112212112\dots$ (Wikipedia, OEIS) equal to $1/2$? Also, does every consecutive block, which occurs at all in the Kolakoski sequence, occur infinitely often?

share|improve this answer

I always enjoyed telling people about the Inscribed square problem :

Does every (Jordan) curve in the plane contain all four vertices of some square?

Update: Here is a variation due to Helge Tverberg: Does every (polygonal) curve in the plane outside of the unit circle, contain all four vertices of some square with side length >0.1? This version implies the original problem and lacks disadvantages pointed out by Tim Chow and Henry Cohn.

share|improve this answer
18  
This is a nice problem but it's only open in the case where the curve is pathologically ugly, in a way that perhaps not "anyone can understand." –  Timothy Chow Jun 22 '12 at 2:05
4  
I do think that anyone can understand whats an injective, continuous map from the circle to the plane. –  Fernando Muro Jun 22 '12 at 6:44
25  
Actually, I disagree that anyone can (quickly, easily) understand what such a map is for the purposes of this problem, since the maps for which it's not known are of a sort even mathematicians didn't realize existed until well into the 19th century. One can still state the problem, but it's likely to lead to conversations of the following sort. "Wow, so you mean nobody knows in advance if this curve [draws a curve] has a square in it?" "Well, actually we know that case, or really any curve you can draw, but mathematicians have discovered exotic curves for which we don't know the answer." –  Henry Cohn Jun 22 '12 at 13:14
14  
The issue here is that intuitive "definitions" of continuous tend to be wrong. "You can draw it without lifting your pencil" really means at least piecewise smooth. –  Noah Snyder Jun 24 '12 at 3:40
1  
Well, not if you shake your hand fast enough (or with enough brownian motion) –  Feldmann Denis Aug 24 '12 at 22:48

The following is a conjecture of Wlodzimierz Kuperberg:

Every convex planar set of area 1 is contained in a quadrilateral of area $1+\frac{4}{5}\tan\frac{\pi}{5}\sin\frac{\pi}{5}$.

In other words, such a set is contained in a quadrilateral of area less that $\sqrt{2}$, and the minimum is obtained for the minimum area quadrilateral containing a regular pentagon.

The conjecture involved only elementary plane geometry, and can be found in:

W. Kuperberg, On minimum area quadrilaterals and triangles circumscribed about convex plane regions, Elem. Math. 38 (1983), no. 3, 57–61, MR0703939 (85a:52009)

It is presented as a challenge to the MO community here:

Small quadrilaterals containing a given convex region


It is easy to prove that

(*) Every convex planar set of area 1 is contained in a quadrilateral of area 2.

It is also easy to see that statement (*) remains true if the constant 2 is replaced with a somewhat smaller one. Contest: Find such a constant, the smaller the better.

Update:

Reaching $\sqrt{2}$ and even a strictly smaller value was proved by Chakerian (1973) and Kuperberg (1983) and the research challenge offered is to improve it even further, and perhaps even to verify the conjecture that the minimum is attained by a regular pentagon. But any nice arguments for bounds below 2 are welcome.

share|improve this answer

Is there any odd perfect number?

share|improve this answer
6  
Methinks this one is both pretty famous and long open... –  J. H. S. Jun 14 '13 at 15:21

More than ten years ago I posed the following problem in a couple of math-related mailing lists:

Let $G_n$ be the graph with vertex set $\{1, 2, \dots, 2n\}$ such that $\{i,j\}$ is an edge if and only if $i+j$ is a prime number. Is it true that $G_n$ is eulerian for every $n \geq 2$?

It is a simple consequence of Bertrand's Postulate (there is always a prime between $k$ and $2k$) that $G_n$ is connected and has a perfect matching for every $n$.

The problem turned out to be an old one. I believe that some variation of it appears in Richard K. Guy's "Unsolved Problems in Number Theory" and according to this article, it was originally posed in the Journal of Recreational Mathematics in 1982.

Michael A. Jones and Leslie Cheteyan, "Two observation on unsolved problem #1046 on prime circles of $\{1, 2, . . . , 2m\}$", J. Recreational Mathematics Vol.35(1) (2006), 15--19.

The whole issue can be downloaded here:

http://www.baywood.com/comppdf/0022-412x.pdf

share|improve this answer

Let ${^n a}$ denote tetration: ${^0 a}=1, {^{n+1} a}=a^{({^n a})}$.

  • It is unknown if ${^5 e}$ is an integer.
  • It is unknown if there is a non-integer rational $q$ and a positive integer $n$ such that ${^n q}$ is an integer.
  • It is unknown if the positive root of the equation ${^4 x}=2$ is rational (ditto for all equations of the form ${^n x}=2$ with integer $n>3$)
  • It is unknown if the positive root of the equation ${^3 x}=2$ is algebraic.
share|improve this answer

This is the second time I've seen this question on mathoverflow and this will be the second time I'vve posted this answer.

Singmaster's conjecture says there is a finite upper bound on the number of times a number (other than the $1$s on the edge) can appear in Pascal's triangle. The upper bound may be as low as $8$. If so, then no number (besides those $1$s) appears more than eight times in Pascal's triangle. Only one number is known to appear that many times: $$ \binom{3003}{1} = \binom{78}{2} = \binom{15}{5} = \binom{14}{6} $$

It has been proved that infinitely many numbers appear twice; similarly three times, four times, and six times. It is unknown whether any number appears five times or seven times.

Singmaster states that Erdős said the conjecture is probably true but probably difficult to prove.

share|improve this answer
1  
We don't really need Erdős to tell us it's probably true when we can do straightforward probabilistic estimates (plus some geometry of plane curves). A short computation shows that there are no numbers less than $10^{1000}$ that have odd multiplicity greater than 3, and heuristics suggest it is quite unlikely that such numbers exist. –  S. Carnahan Jul 2 '12 at 9:49
3  
@S.Carnahan : How did you do that "short computation"? –  Michael Hardy Jul 6 '12 at 21:49
4  
I love this problem! Everything about it is simple and compelling, and it can be understood by anyone who knows how to add. Is there also a simple heuristic argument for why it should be true? @S. Carnahan , can you flesh out your heuristics a little more? What's this stuff about geometry of plane curves? –  Vectornaut Jul 22 '12 at 18:44

Ore's odd Harmonic number conjecture

share|improve this answer
8  
This is a notorious problem. The OP asked for “not too famous”. –  Emil Jeřábek Jun 27 '12 at 14:18

The Kurepa conjecture : For every odd prime $p$, one has $$ 0!+1!+\cdots+(p-1)!\not\equiv0\pmod p $$ A proof was claimed and published in 2004 but the claim was withdrawn in 2011. See also my comment on the accepted answer to MO24265.

share|improve this answer

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

share|improve this answer

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

share|improve this answer
  • Is Hilbert's tenth problem for Diophantine equations in rational numbers decidable?
  • Is Hilbert's tenth problem for Diophantine equations of power $3$ decidable?
  • Is there a universal Diophantine equation of power $3$?
  • Is there a universal Diophantine equation containing less than $9$ variables? If so, what is the minimal number of variables? What minimal power can be achieved for that number of variables?
  • Is there a universal Diophantine equation that can be written using less than $100$ arithmetic operations (additions or multiplications)? If so, what is the minimal number of operations?
share|improve this answer

Is there a triangle that can be cut into $7$ congruent triangles? (no)

share|improve this answer
1  
Nice problems but what are the sources? –  Alexander Chervov Jul 24 '12 at 20:23
2  
I heard this in a personal communication. But it turns out this is already settled negatively in 2008: michaelbeeson.com/research/papers/SevenTriangles.pdf –  Vladimir Reshetnikov Jul 28 '12 at 20:34
  • Is the Ring of Periods actually a field? (most likely, no)
  • Is the equality of periods decidable? (hopefully, yes)
share|improve this answer
7  
problems which anyone can understand ? Uhhh –  Denis Serre Sep 25 '12 at 7:50

Bonnesesn—Fenchel conjecture: Which body of constant width has the least volume? Is it Meissner's tetrahedron?

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer
1  
It was discussed here: mathoverflow.net/questions/83026/… –  Vladimir Reshetnikov Jul 28 '12 at 21:10

This is basically copied from my answer on this question, which I've now updated some.

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 why those should be any easier.)

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

That seems to be the best known.

share|improve this answer

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.

share|improve this answer

How many trees are there?

Let $T(n)$ be the number of trees on $n$ vertices up to graph isomorphism. There is no known closed formula for $T(n)$.

In 1947 Richard Otter proved[Source] the asymptotic result $$T(n) \sim A \cdot B^n \cdot n^{-\frac{5}{2}}$$ where $A \approx 0.535$ & $B \approx 2.996$.

By way of contrast, let $L(n)$ be the number of labelled trees, i.e. trees formed from vertices labelled $1,...,n$ where isomorphism additionally preseves the label. In 1889, Arthur Cayley showed[Source] that $$L(n)=n^{n-2}$$

share|improve this answer
1  
What exactly is the problem here? –  Harry Altman Jul 24 '12 at 22:03

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. http://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.

share|improve this answer

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

share|improve this answer

Is there an upper bound of quotients in the continued fraction representation of $\sqrt[3]{2}=[ 1; 3, 1, 5, 1, 1, \dots]$?

share|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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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