363
$\begingroup$

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

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

$\endgroup$
11
  • 2
    $\begingroup$ 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" $\endgroup$ Jun 21, 2012 at 20:53
  • 2
    $\begingroup$ Nice question!! $\endgroup$
    – Suvrit
    Jun 22, 2012 at 3:25
  • 16
    $\begingroup$ 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. $\endgroup$ Jun 22, 2012 at 12:05
  • 18
    $\begingroup$ More precisely, K-12 means anything up to high school (K = Kindergarten, 12 = 12th grade, and K-12 covers this range). $\endgroup$
    – Henry Cohn
    Jun 22, 2012 at 13:05
  • 3
    $\begingroup$ There seems to be a claimed proof of the union-closed sets conjecture by Blinovsky arxiv.org/abs/1507.01270 $\endgroup$
    – Marco
    Oct 22, 2015 at 14:08

112 Answers 112

28
$\begingroup$

Proving the Inequality of the Means by fitting boxes into a cube. From Berlekamp, Conway and Guy's Winning Ways for Your Mathematical Plays, Academic Press, New York 1983. See the discussion of this problem on Dror Bar-Natan's webpage for details, pictures, etc.

Question: Is it possible to pack $n^n$ rectangular n-dimensional boxes whose sides are $a_1, a_2,\ldots, a_n$ inside one big n-dimensional cube whose side is $a_1+a_2+\cdots+a_n$?

$\endgroup$
28
$\begingroup$

I think nobody pointed this problem, if it is repeated, please say me to delete it. This problem killed me for three weeks, when I was a young student in high school. So, I want to recall it again.

Problem: Find all right triangles with rational sides, where the area of these triangles are integer?

I think it is still open problem and if somebody can solve it, I will give 100$ as a small award.

After I searched, I found these two interesting sources. I hope it will be helpful.

1) N.Koblitz, Introduction to elliptic curves and modular forms, volume 97 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1993.

2) Washington, Lawrence C., Elliptic Curves : Number Theory and Cryptography, CRC Press Series On Discrete Mathematics and Its Applications

$\endgroup$
3
  • 14
    $\begingroup$ This is the congruent number problem and leads to the Birch-Swinnerton-Dyer conjecture... math.jussieu.fr/~colmez/congruents.pdf $\endgroup$ Jun 22, 2012 at 23:13
  • 4
    $\begingroup$ That's presumably the intention, though the problem as stated looks simpler... (The "congrent number problem" amounts to asking which integers are the areas of right triangles all of whose sides are rational.) $\endgroup$ Jun 23, 2012 at 3:09
  • $\begingroup$ I am not sure that the problems I posted under numbers 223484, 237438, and 216320 will be suitable for you, but the are definitely not very famous, some of them were stated about 10 years ago, they are formulated in a very elementary way, and I think that they are not trivial since some of very good mathematicians (not me, but really good) could not solve them quickly. And the answer will be interesting to many people. Will be glad if this information is useful. $\endgroup$
    – Deepti
    Oct 31, 2016 at 7:15
27
$\begingroup$

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 https://en.wikipedia.org/wiki/Synchronizing_word.

$\endgroup$
1
  • $\begingroup$ +1If equivalent to the original conjecture your version is definitely the proper formulation, avoiding the bias of automate theory. Thank for this. $\endgroup$ Jan 14, 2016 at 21:32
25
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ @John: Dear John, this is a well known conjecture. See the question once again. $\endgroup$
    – C.S.
    Jun 23, 2012 at 9:13
  • 7
    $\begingroup$ Also: one problem per answer $\endgroup$
    – Yemon Choi
    Jun 23, 2012 at 9:42
  • $\begingroup$ I was under the impression that the result attributed here to Ramanujan was in fact first proved as an application of the Six Exponentials Theorem (en.wikipedia.org/wiki/Six_exponentials_theorem) in the 1960s. Do you have a reference for Ramanujan's work? $\endgroup$ Oct 23, 2015 at 6:17
25
$\begingroup$

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.

$\endgroup$
0
23
$\begingroup$

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.

$\endgroup$
23
$\begingroup$

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. (Wayback Machine)

$\endgroup$
1
22
$\begingroup$

The Graph Reconstruction Conjecture:

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

$\endgroup$
21
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ 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 $\endgroup$ Jun 23, 2012 at 12:51
  • 11
    $\begingroup$ 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. $\endgroup$ Jun 24, 2012 at 15:09
19
$\begingroup$

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

$\endgroup$
19
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Just a note -- would you mind fixing the link to point to the abstract rather than the PDF? Since from the abstract one can click through to the PDF but not vice versa, as well as from there you can see other versions, other papers by the same authors, etc. Thank you! $\endgroup$ Jul 31, 2015 at 17:07
  • $\begingroup$ No problem, it's done! $\endgroup$
    – Seirios
    Aug 1, 2015 at 6:54
  • 7
    $\begingroup$ This has been disproved: see here and here. $\endgroup$
    – BillyJoe
    Feb 23, 2019 at 22:30
19
$\begingroup$

The Littlewood conjecture:

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.

$\endgroup$
18
$\begingroup$

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

$\endgroup$
2
18
$\begingroup$

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

$\endgroup$
5
  • 8
    $\begingroup$ Surely there is a missing condition here. Maybe the pieces are required to be congruent? $\endgroup$
    – zeb
    Mar 11, 2014 at 11:50
  • $\begingroup$ What does it mean that the centre "lies within one of the pieces"? I guess "dissected" refers to presenting the disk as a disjoint union of subsets? Then clearly the centre belongs to exactly one piece? $\endgroup$ Sep 28, 2017 at 13:29
  • 1
    $\begingroup$ The pieces (subsets) are assumed to be connected. And "within" to mean, not on the boundary. $\endgroup$
    – maproom
    Sep 29, 2017 at 14:48
  • $\begingroup$ Does this count as connected? $\endgroup$
    – Graviton
    Feb 13, 2022 at 5:22
  • $\begingroup$ @Graviton: It doesn't count as congruent, only similar. $\endgroup$ Oct 21, 2022 at 6:41
18
$\begingroup$

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.

More info is in this blog post of Scott Aaronson: https://scottaaronson.blog/?p=839

$\endgroup$
1
  • 8
    $\begingroup$ I don't think this counts as "not especially famous"... $\endgroup$ Jul 24, 2012 at 4:24
17
$\begingroup$

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.

$\endgroup$
17
$\begingroup$

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

$\endgroup$
0
16
$\begingroup$

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

$\endgroup$
3
  • 3
    $\begingroup$ I think you need to be more precise -- say, $aaaa$ could be interpreted to contain 4 squares, and thus be a counterexample. $\endgroup$
    – Stefan Kohl
    Dec 3, 2014 at 9:54
  • 9
    $\begingroup$ 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. $\endgroup$ Dec 3, 2014 at 11:33
  • 5
    $\begingroup$ Source for this being unsolved? $\endgroup$ Oct 28, 2016 at 16:20
16
$\begingroup$

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 minimal volume is unknown.

$\endgroup$
14
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Is it still true if the constraint on the sum of the diagonals is removed? What about replacing 4 by other powers of 2? $\endgroup$ Jul 11, 2012 at 21:57
  • $\begingroup$ Consider the following transform: f(x)= x div 2 + 8(x mod 2). If you have four positive numbers sum to 30, and exactly two of those numbers are odd, then the transformed sum is also 30. Now if one can find an algebraic proof that there is no magic square with four even numbers in a row or column, then f is an action on 4x4 magic squares, and there are exactly two ones in any slice off our such numbers. But Conway probably knows this already, and f may not be an action on magic squares. Gerhard "If Only Wishes Were Proofs" Paseman, 2012.07.12 $\endgroup$ Jul 12, 2012 at 15:52
  • $\begingroup$ According to a website by H. B Meyer, the stronger statement in my comment above about slices is true for order 4 magic squares. Thus I suspect the problem is not open. If I find an algebraic proof that no row or column can have all even numbers, I will post a reference here. Gerhard "Ask Me About Right Shifts" Paseman, 2012.07.12 $\endgroup$ Jul 12, 2012 at 19:59
  • $\begingroup$ Of course, I got the argument backwards. Consider the inverse of f. It will leave sums of 30 invariant, provided exactly two of the four numbers are 8 or greater. But no row (column) can have three or more numbers greater than 7, as then one row would have one or fewer numbers greater than 7. I claim this problem can now be solved, and is no longer open. Gerhard "Ask Me About System Design" Paseman, 2012.07.16 $\endgroup$ Jul 17, 2012 at 1:23
  • 2
    $\begingroup$ The 2017 book "The Mathematics of Various Entertaining Subjects", volume 2, at chapter 5 "Frenicle’s 880 Magic Squares", by Conway, Norton and Ryba, describes this problem as "Nimm0" property. It also states in note 1 that Friedrich Fitting and Oliviero Giordano Cassani solved it independently. However I wasn't able to find any paper online regarding the proof. $\endgroup$
    – BillyJoe
    Aug 31, 2019 at 8:06
13
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ >might be on the verge to being too famous New to me, and perfect for the purpose! $\endgroup$ Jul 12, 2012 at 20:27
13
$\begingroup$

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$.} $$
$\endgroup$
13
$\begingroup$

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?

$\endgroup$
13
$\begingroup$

Ron Graham [1,2] asked if there are infinitely many positive integers $n$ such that the central binomial coefficient $\binom{2n}{n}$ is coprime to $105 = 3 \times 5 \times 7$, and offered a prize of $1.000 for a proof/disproof.

Accordingly to some heuristics [3, §4], there should be infinitely many such $n$, but if instead of $105$ a product of four primes is taken, than only finitely many such $n$ are expected.

Furthermore, it has been proved [4] that $\binom{2n}{n}$ if coprime to $pq$ for infinitely many $n$, where $p$ and $q$ are two fixed odd primes.

[1] D. Berend and J. E. Harmse, On some arithmetic properties of middle binomial coefficients, Acta Arith. 84 (1998), 31–41.

[2] OEIS, https://oeis.org/A030979

[3] C. Pomerance, Divisors of the middle binomial coefficient, Amer. Math. Monthly, 112 (2015), 636-644.

[4] P. Erdős, R. L. Graham, I. Z. Russa and E. G. Straus, On the prime factors of C(2n,n), Math. Comp. 29 (1975), 83-92.

$\endgroup$
13
$\begingroup$

The Feit-Thompson conjecture is not too famous and it is still open: there are no prime numbers $p\neq q$ such that $$\frac{p^q-1}{p-1}\text{ divides }\frac{q^p-1}{q-1}.$$

$\endgroup$
13
$\begingroup$

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, DOI: 10.1515/crll.1984.348.135, eudml). The best result on Ruzsa's problem is due to U. Zannier ("On periodic mod $p$ sequences and G-functions," Manuscripta math. 90, 1996, eudml, DOI: 10.1007/BF02568314).

$\endgroup$
1
13
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ This recent preprint arxiv.org/abs/1604.08657 claims to "nearly settle" this conjecture.... $\endgroup$
    – Suvrit
    May 2, 2016 at 1:13
12
$\begingroup$

A list of fundamental geometry problems with simple intuitive statements involving curves and surfaces in Euclidean space is maintained at:

Open Problems in Geometry of Curves and Surfaces

Five of these problems are listed below in no particular order (see the paper for references, background, and more precise statements):

Durer's Unfolding Problem: Can every convex polyhedron be cut along a collection of its edges and developed into the plane in a single non-overlapping piece?

Alexandrov's Conjecture on Intrinsic Diameter: Of all convex surfaces with a fixed intrinsic diameter (the distance between the farthest two points as measured within the surface), the one with the greatest area is the doubled disk (the degenerate convex surface obtained by gluing a pair of disks along their boundaries).

Zalgallers's Problems on Width and Inradius: What are the shorted closed curves in Euclidean 3-space with a given width or inradius? (The width is the smallest distance between all pairs of parallel planes which contain the curve in between them, and the inradius is the radius of the largest ball which is contained in the convex hull of the curve and is disjoint from the curve; see the post by Joseph O'Rourke).

Euler-Maxwell Rigidity Problem: Can one continuously deform a smooth closed surface in Euclidean 3-space without changing the distances between its points, as measured within the surface?

Converse of the Archimedes Hatbox Theorem: Is the sphere the only convex surface such that whenever it is cut by a pair of parallel planes separated by a fixed distance, the area of the portion of the surface trapped between the planes is always the same? See this earlier post.

$\endgroup$
12
$\begingroup$

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 preserves the label. In 1889, Arthur Cayley showed[Source] that $$L(n)=n^{n-2}$$

$\endgroup$
4
  • 1
    $\begingroup$ What exactly is the problem here? $\endgroup$ Jul 24, 2012 at 22:03
  • 1
    $\begingroup$ The problem is to find a closed form for $T(n)$, I think. $\endgroup$ Oct 3, 2013 at 16:14
  • 3
    $\begingroup$ Is there a good reason to suspect such a formula exists? It could equally be that the simplest description of $T(n)$ is the one just given. $\endgroup$ Jun 4, 2015 at 19:41
  • 6
    $\begingroup$ “Closed formula” is a bit of a slippery goal — there are specific definitions, but they are mostly somewhat ad hoc. A more mathematically natural goal along similar lines might be to find a polynomial-time algorithm (or some other reasonable sense of “fast”) for computing T(n). $\endgroup$ Jan 24, 2016 at 0:23

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