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 '12 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 '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 arxiv.org/abs/1507.01270 – Marco Oct 22 '15 at 14:08

Are there eight points on the plane, no three on a line, no four on a circle, with integer pairwise distances?

The analogous question for seven points was posed by Paul Erdős and answered positively by Kreisel, Kurz 2008, who have then asked this question.

In general, problems by Paul Erdős are worth to check if you want to find problems you are asking for here.

Tobias Kreisel, Sascha Kurz, There Are Integral Heptagons, no Three Points on a Line, no Four on a Circle, Discrete & Computational Geometry 39/4 (2008), 786-790.

-

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?", 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 '12 at 13:39
It was also discussed here: mathoverflow.net/questions/19127/… – Vladimir Reshetnikov Jul 28 '12 at 20:30

Ramanujan's conjecture [*] If $2^x$ and $3^x$ are both rational (hereafter assumed) integers for some non-zero $x$ then $x$ is an integer.

[*] I think that is the accepted name for this problem. He certainly proved the weaker corresponding result with $2^x$, $3^x$, and $5^x$ all assumed to be integers.

Unlike some of the other fascinating conjectures already listed here, this one seems "obviously" true. Yet I gather little progress has been made on it. It must be hard to find a foothold, so to speak, or know where to start.

Another easily understood example is the Erdős-Straus Conjecture which asserts that for every integer $n > 1$, there is at least one set of positive integers $x, y, z$ with $\frac{1}{x} + \frac{1}{y} + \frac{1}{z} = \frac{4}{n}$. The result is trivially true if negative integers are also allowed.

In this case, by contrast, it's easy(ish) to "almost" prove it, and with patience and ingenuity one can proceed (apparently) ever closer to a solution. But a few annoying special cases always seem to slip through the net!

One more example - I think a high school kid would have little difficulty understanding the abc conjecture, or following the simple proof of the corresponding result for polynomials Mason-Stothers theorem.

-
Also: one problem per answer – Yemon Choi Jun 23 '12 at 9:42

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.

-

Here's another Birch Swinnerton-Dyer related problem. Sylvester conjectured that every prime that is 4,7 or 8 mod 9 is a sum of two rational cubes. Elkies (unpublished?) settled the first two cases. As far as I know, the third is still open.

-
This conjecture of Sylvester is indeed not so widely known and the case $p=8 \mod{9}$ is still open. For some informations on Elkies's construction, see math.harvard.edu/~elkies/sel_p.html For published results, see Dasgupta-Voight's article people.ucsc.edu/~sdasgup2/clay.pdf – François Brunault Jun 23 '12 at 12:51
Yes, still unpublished alas. When I was working on it I looked up Sylvester's work on $x^3+y^3=a$ and didn't find any evidence that he actually conjectured this, though he did make some speculations about the case $p \equiv 1 \bmod 9$, which is the one case where $a$ is prime and the rank might be as high as $2$. For $p \equiv 4, 7, 8 \bmod 9$ the earliest statement of the conjecture that I found is Birch-Stephens (Topology 1966), prefigured by Selmer (Acta Math. 1951). It is a special case of the parity conjecture for the rank of elliptic curves. – Noam D. Elkies Jun 24 '12 at 15:09

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

-

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.

-

Does there exist a point in the unit square whose distance to each of the four corners is rational?

This is sometimes called the rational distance problem, although that name often refers to a more general class of similar problems. It's discussed by Richard Guy in Unsolved Problems in Number Theory and in the following paper:

Guy, Richard K. "Tiling the square with rational triangles." Number theory and applications 265 (1989): 45-101.

It's also open whether there's a point outside the square whose distance to each of the four corners is rational, although it is known that no point on the edge of the square has this property.

-

A few decades ago Sherman Stein asked whether a trapezoid whose parallel sides are in the ratio 1:root 2 can be dissected into triangles, all of the same area. This remains open--it's a mystery which trapezoids admit such dissections./

-

For any $\alpha, \beta \in \mathbb{R}$ we have $$\lim\textrm{inf}_{n\to\infty} (n\cdot||n\alpha||\cdot||n\beta||) = 0$$

where $||\cdot||$ denotes the distance to the nearest integer.

-

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.

-

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.

-

For integers $a_1, a_2, \ldots$, let $[a_1,a_2,\ldots]$ denote a continued fraction expansion $a_1 + \frac{1}{a_2 + \frac{1}{\ddots}}$.

Zaremba conjectured in 1972 that there must exist some constant $A > 1$ such that given any integer integer $d > 1$, you can always find some coprime $b$ such that if we write out the continued fraction expansion $b/d = [a_1, a_2, \ldots, a_k]$, all of the coefficients $a_i \leq A$.

Everyone seems to believe that $A = 5$, but we still don't know if such a constant exists. The current best known result (of Bourgain and Kontorovich) is that almost all integers $d$ permit a $b$ such that $b/d$ has the desired property (in their paper, they took $A = 50$, but I think that has been improved slightly since).

-

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

-
Surely there is a missing condition here. Maybe the pieces are required to be congruent? – zeb Mar 11 '14 at 11:50
Thank you, zeb - that is what I meant. – maproom Mar 11 '14 at 16:55

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 '12 at 4:24

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

-
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$. – Vesselin Dimitrov Dec 17 '14 at 17:35
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. – Wadim Zudilin Nov 11 '15 at 4:01

Is it true that any word of length $n$ contains less than $n$ squares?

(A square is a factor of the form $uu$ for a non-empty word $u$.)

-
I think you need to be more precise -- say, $aaaa$ could be interpreted to contain 4 squares, and thus be a counterexample. – Stefan Kohl Dec 3 '14 at 9:54
By the definition, the word $aaaa$ contains only two squares, namely $aa$ and $aaaa$. The confusion may arise when one thinks of occurrences of factors, instead of distinct factors. – Gabriele Fici Dec 3 '14 at 11:33

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

-

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.

-
This recent preprint arxiv.org/abs/1604.08657 claims to "nearly settle" this conjecture.... – Suvrit May 2 at 1:13

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.

-

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

-

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

-
What exactly is the problem here? – Harry Altman Jul 24 '12 at 22:03

Let $G, H$ be finite, simple, loopless graphs such that $|V(G)|$ and $|V(H)|$ are at least $4$. If there is a bijection $\varphi:V(G)\to V(H)$ such that for all $v\in V(G)$ the graphs $G\setminus \{v\}$ and $H\setminus \{\varphi(v)\}$ are isomorphic, then $G\cong H$.

-

Here is another problem on equilibrium points of potentials: suppose that we have infinitely many point masses in $R^3$ (the points do not accumulate). Must there exist a point where the gravitational force created by these masses is zero?

If the masses $m_k>0$ are placed at $x_k\to\infty$ then the force is $$\sum_{k=1}^\infty m_k\frac{x-x_k}{|x-x_k|^3},\quad \mbox{where}\quad\sum_{k=1}^\infty m_k|x_k|^{-2}<\infty.$$ Does every such function have a zero?

This is a version of the problem proposed by Lee Rubel in 1980-th. For some partial results see http://www.math.purdue.edu/~eremenko/dvi/equil.pdf This question can be easily modified for any dimension $n\geq2$, using Newtonian ($n\geq 3$) or logarithmic potential ($n=2$). The question is substantially easier in dimension $2$, but even for $n=2$ it is not solved in full generality.

-

An open problem I find surprising, the PAC (Perimeter to Area Conjecture) due to Keleti (1998):

The perimeter to area ratio of the union of finitely many unit squares in the plane does not exceed 4.

See for example Bounded - Yes, but 4? and references therein.

-

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?

-

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

-

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.