# 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
Nice question!! –  Suvrit Jun 22 '12 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 '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

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

-

Problem: The partition function $p(n)$ is even (resp. odd) half of the time.

Of course you need to explain to a general audience what the partition function is, but that's not hard, my daughter in K1 got as an assignment to compute $p(n)$ for $n$ up to 4. You also need to explain "half of the time", which means that the number of $n < x$ such that $p(n)$ is even, divided by $x$, has limit 1/2 when $x$ goes to infinity, so you need the notion of limit of a sequence, which is in K12, isn't it ?

The problem is certainly famous among specialists, but not too famous. I don't think there are books on it, for instance. It is old (formulated as a conjecture during the 50th), with an history going back to Ramanajunan. And I like it very much.

UPDATE (28/2/2015) Here is a useful reference:
Ken Ono, The parity of the partition function, Electronic Res. Ann. (1995)

-
The notion of limit of a sequence is not usually taught in the US until a real analysis course, which is usually taken only by students in mathematics and frequently not until the third (or even last) year of university. (But I think this case is concrete enough that the necessary ideas here could be explained to a high school student.) –  Alexander Woo Jun 22 '12 at 4:05
Sequences are taught before real analysis, usually in Calc 2 along with infinite series. And the more basic material is suitable for high school, even a decent precalculus class. These are only sequences of reals so it isn't very general, and while they are taught, students might not really "understand" them until later. –  Francis Adams Jun 22 '12 at 12:51
Yes, there is an option for seniors in a good high school to learn some calculus, but most calculus courses in the United States no longer give a rigourous definition of a limit. Without a rigourous definition, there are some subtle possibilities for what might go wrong that won't be appreciated. (Of course, very few students at that level have the mathematical maturity to understand a rigourous definition well enough to appreciate the subtle possibilities anyway, which is why the rigourous definition isn't taught anymore.) –  Alexander Woo Sep 6 '12 at 4:11
Also, "half of the time" can be restated in probabilistic terms. In other words, instead of framing it as a real analysis question, appeal to probabilistic intuition. Alexander Woo's remarks about subtle possibilities notwithstanding, vastly larger numbers of students learn elementary probability and statistics than calculus. –  Victor Protsak Jan 6 '14 at 19:28

Here is one which I found at this MO link:

$$\frac{24}{7\sqrt{7}} \int_{\pi/3}^{\pi/2} \log \left| \frac{\tan(t)+\sqrt{7}}{\tan(t)-\sqrt{7}}\right|\ dt = \sum_{n\geq 1} \left(\frac n7\right)\frac{1}{n^2},$$ where $\displaystyle\left(\frac n7\right)$ denotes the Legendre symbol. Not really my favorite identity, but it has the interesting feature that it is a conjecture! It is a rare example of a conjectured explicit identity between real numbers that can be checked to arbitrary accuracy. This identity has been verified to over 20,000 decimal places. See J. M. Borwein and D. H. Bailey, Mathematics by Experiment: Plausible Reasoning in the 21st Century, A K Peters, Natick, MA, 2004 (pages 90-91).

-
It was a good idea to split the two conjectures to two answers, but you should have done it the other way around. I venture to guess that most people, like me, originally upvoted this answer because of Sendov’s conjecture, not because of an obscure integral equality which I couldn’t explain to any high school student I now of. –  Emil Jeřábek Jun 25 '12 at 10:34
@Emil: Emil, The answers were split because of an user requesting me to do so. Otherwise I would have kept it here itself. –  S.C. Jul 1 '12 at 7:40

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.

-

Erdos's problem on the length of lemniscates (it is somewhat famous in certain narrow circles). Let $P$ be a polynomial, and consider the set $E=\{ z:|P(z)|=1\}$ in the complex plane.

What is the maximum length of $E$ over all monic polynomials of degree $d$?

Erdos conjectured that an extremal $P$ is $P_0(z)=z^d+1$.

It is known that the asymptotic of maximal length is $2d+o(d).$ It is known that $P_0$ gives a local maximum. It is also known that for every extremal polynomial, all critical points lie on $E$, so $E$ must be connected.

However the conjecture is not established even for $d=3$.

After Erdos's death, I offered a $200 prize for the first solution. (Erdos had offered the same, but I do not know whether one can collect his prize.) - Thanks, this is nice to know. So you can collect$400 total for this problem. –  Alexandre Eremenko Jan 29 at 18:27

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

-

The Alon-Tarsi Conjecture:

A latin square of order $n$ is a filling of an $n\times n$ matrix with the numbers $1, 2,\ldots,n$ such that each row or column gives a permutation of $1,2,\ldots,n$. Take the product of the signs of these $2n$ permutations and call it the sign of the latin square. Let $EVEN(n)$ be the number of latin squares with sign $+1$ and let $ODD(n)$ be the number of latin squares with sign $-1$. The conjecture says:

If $n$ is even then $EVEN(n)\neq ODD(n)$.

The original reference is: N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), 125-134. See also this preprint by Landsberg and Kumar for a recent update.

-

I like the Montesinos-Nakanishi 3-move conjecture from knot theory. A 3-move on a link is the replacement of two parallel strands by three half twists. The conjecture is that any link can be turned into the trivial link by a sequence of such moves. (If you think of this as a conjecture on diagrams, then you also need to allow Reidemeister moves.) According to an Encyclopedia of Mathematics article:

The conjecture has been proved for links up to 12 crossings, 4-bridge links and five-braid links except one family represented by the square of the centre of the 5-braid group. This link, which can be reduced by 3-moves to a 20-crossings link, is the smallest known link for which the conjecture is open (as of 2001).

-

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.

-

The Kurepa problem: Show that for all primes $p>3$ we have that $$0!+1!+2!+\dots+(p-1)!$$ is not divisible by $p$. Kurepa posed this problem in 1971. For an overview see the article by Ivic and Mijajlovic (http://arxiv.org/abs/math/0312202).

-
Already on this list: see mathoverflow.net/a/114639/763 –  Yemon Choi Dec 17 '14 at 16:18
@Stefan Kohl: Ivic told me that the Barsky-Benzaghou-proof is philosophically correct in the sense that although it does not prove the conjecture, it gives a reason why the conjecture should be true. I haven't looked at the paper itself, though. –  Jan-Christoph Schlage-Puchta Dec 18 '14 at 14:08

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.

-

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 easy to state problem which is 140 years old but not very famous. Consider the potential of finitely many positive charges: $$u(x)=\sum_{j=1}^n\frac{a_j}{|x-x_j|},\quad x,x_j\in R^3,\quad a_j>0$$ How many equilibrium points can this potential have? Equilibrium points are solutions of $\nabla u(x)=0$.

First conjecture: it is always finite.

Second conjecture: when finite, it is at most $(n-1)^2$. This estimate is stated by Maxwell in his Treatease on Electricity and Magnetism, vol. I, section 113, as something known. The editor (J. J. Thomson) wrote a footnote that he "could not find any place where this result is proved".

Nobody could find this place to this time. This is even unknown in the simplest case when all $a_j=1$ and $n=3$.

-

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

Can a disk be dissected into two or more 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

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

-
An excellent reference is the recent book Distribution modulo one and Diophantine approximation, by Yann Bugeaud. –  Andres Caicedo Jan 6 '14 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).

-
–  Stefan Kohl Jan 6 '14 at 13:29

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

-

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?

-

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.

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

-

Is there any odd perfect number?

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

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

-

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

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.

-
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
@S.Carnahan : How did you do that "short computation"? –  Michael Hardy Jul 6 '12 at 21:49
Odd multiplicity means you have a number of the form $\binom{2k}{k}$. It's not hard to check whether a number has the form of a binomial coefficient $\binom{m}{n}$ in SAGE, since you have a built-in function that estimates integer $n$-th roots. –  S. Carnahan Jul 12 '12 at 7:02
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

-
Well, now it's so obscure that it requires a context/explanation. –  Victor Protsak Jan 6 '14 at 20:45

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.

-

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

-

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

-