## Not especially famous, long-open problems which anyone can understand

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.

-
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 at 19:11
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 at 20:53
Nice question!! – S. Sra Jun 22 at 3:25
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 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 at 13:05
show 1 more comment

Does the series $\sum_{n=1}^{\infty} \frac{1}{n^3 \sin^2 n}$ converge?

(Taken from http://math.stackexchange.com/questions/20555/are-there-any-series-whose-convergence-is-unknown where there are more such examples)

-
and, in my answer at math.SE which you link here, I refer to the mathoverflow question mathoverflow.net/questions/24579. – George Lowther Jun 24 at 0:35
show 1 more comment

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.

-

The Cerny conjecture says that if X is a collection of mappings on an n element set such that some iterated composition (repetitions allowed) of elements of X is a constant map then there is a composition of at most $(n-1)^2$ mappings from X which is a constant mapping. This comes from automata theory. See http://en.m.wikipedia.org/wiki/Synchronizing_word.

-

3D Version Of Blaschke-Lebesgue(1914) Theorem

The planar, compact.convex set of constant width, say 1, of minimal area is the Reuleaux triangle: Blaschk-Lebesgue(1914). The 3D set of constant width and mimimal volume is unknown.

-

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

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

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

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? ;)

-

Some pages:
Open Problem Garden
The Open Problems Project

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

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

-

In an oriented graph, is there always a vertex from which there are at least as many vertices that one can access by moving along exactly two edges, than there are vertices that one can access by moving along one edge?

This is known as Seymour's second neighborhood conjecture, and might be on the verge to being too famous (but it seems few of my colleagues know it).

-

Is there a dense subset of a plane having only rational distances between its points?

-
This problem is given in Klee, Victor; Wagon, Stan (1991), ["Problem 10 Does the plane contain a dense rational set?"](books.google.com/…), Old and New Unsolved Problems in Plane Geometry and Number Theory, Dolciani mathematical expositions, 11, Cambridge University Press, pp. 132–135, ISBN 978-0-88385-315-3, and attributed to Ulam and Erdős. – Vladimir Reshetnikov Jul 25 at 13:39
It was also discussed here: mathoverflow.net/questions/19127/… – Vladimir Reshetnikov Jul 28 at 20:30

Does every nonseparating planar continuum have the fixed point property?

-
For those of us whose general topology is rusty: what is the K-12 level formulation of this question? – Yemon Choi Jun 21 at 22:50
Uniform continuity is a K-12 concept now? – Douglas Zare Jun 22 at 14:25
Thanks Yemon. I agree with Doug that uniform continuity is not a stand alone K-12 concept. I mentioned it in order to avoid trying to decode its meaning in K-12 terms in this context, as follows: – Paul Fabel Jun 22 at 17:56
f is a set of 4-tuples (x1,y1,x2,y2) so that each point (x1,y,1) in K appears precisely once as the 1st two coordinates of some point in f, and we also require that the last two coordinates of each point of f is a point of K. For each positive radius R we can find a smaller positive radius r(R) so that if (x1,y1,x2,y2) is in f, then if (w1,z1) is both in K and also in the disk of radius r(R) centered at (x1,y1), and if (w1,z1,w2,z2) is in f, then (w2,z2) is in the disk of radius R centered at (x2,y2). – Paul Fabel Jun 22 at 17:56

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.

-
Could you please not use BIG FONT for your headings? – Yemon Choi Jun 24 at 9:04
@Yemon: Why whats wrong? – Chandrasekhar Jun 24 at 9:08

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

-
Where are functions of exponential growth used in the classical proof, or the Euler product + divergence of harmonic series? – Douglas Zare Jun 24 at 14:06
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. – Henry Cohn Jun 24 at 16:49
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. – Emil Jeřábek Jun 25 at 11:35
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... – Emil Jeřábek Jun 25 at 11:52

Here is a nice question due to John Conway. In a magical 4x4 square, show that the XOR composition of the four numbers, written in base 2, in every row and in every column is zero. This applies to a square in which the numbers 0 to 15 are used (rather than 1 to 16).

For instance, a typical row might be 0 15 14 1, which in binary is 0000 1111 1110 0001, and in each of the four positions there happen to be two entries 0 and two entries 1, so the binary sum is zero.

Of course there are only finitely many possible magic 4x4 squares, and you can give proof by "complete inspection" (aka brute force). In fact, that has been done, so the result is true. But neither he nor I know a conceptual proof. Should be easy to understand about a classical problem -- and yet seems not obvious. Try it!

(Incidentally, the binary sum along the diagonals need not always be zero; that's not part of the question.)

-

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

-

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

-

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

-
It was discussed here: mathoverflow.net/questions/83026/… – Vladimir Reshetnikov Jul 28 at 21:10

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

-

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.

-

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

-

The complexity of matrix multiplication (i.e. the asymptotic number of steps required to multiply two n-by-n matrices).

This is an important problem in CS theory, but is non-famous enough in other fields that a mathematician (Andrew Stothers) made a significant advance in it in 2010 (beating a 20-year-old bound of Coppersmith and Winograd), and wrote up the result on page 71 of his PhD thesis without bothering to state it as a theorem or otherwise call attention to it. Word of it only got around a year or so later, when a computer scientist (Virginia Vassilevska Williams) independently made a further improvement.

The obvious multiplication algorithm takes $O(n^3)$ steps, and a well-known Karatsuba-like rearrangement gets the exponent $\omega$ down to about 2.8. There is a simple proof that the smallest possible $\omega$ is $\ge 2$. Coppersmith and Winograd got an exponent of 2.376 and the more recent results have it at 2.373. Apparently nobody has even shown that the minimum is not equal to 2: there are some who believe there's an algorithm faster than $O(n^{2+\epsilon})$ for any $\epsilon>0$ but not an $O(n^2)$ algorithm, but this is not known.

-
I don't think this counts as "not especially famous"... – Harry Altman Jul 24 at 4:24

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.

-

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.

-

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

-

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

-

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

-

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

-

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.

-
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. – Martin Brandenburg Jul 19 at 12:17
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." – Vectornaut Jul 22 at 18:26
show 1 more comment