67
$\begingroup$

I'm looking for a list of problems such that

a) any undergraduate student who took multivariable calculus and linear algebra can understand the statements, (Edit: the definition of understanding here is that they can verify a few small cases by themselves )

b) but are still open or very hard (say took at least 5 years to solve),

Edit: c) and first proposed in the 20th century or later.

Edit : my motivation is to encourage students to addict to solving mathematical problems.

I know that there are many such problems in number theory and combinatorics, for trivial example, Fermat's last theorem. I'll be more interested in other fields, but less famous problems in number theory or combinatorics would be also welcome. For example,

1) The $n!$ conjecture can be stated in an elementary language, but had been notoriously hard. See section 2.2 in Haiman's paper http://arxiv.org/abs/math.AG/0010246 .

2) Let $r$ be any positive integer, and let $x_1, x_2$ be indeterminates. Consider the sequence $\{x_n\}$ defined by the recursive relation $$x_{n+1} =(x_n^r +1)/x_{n-1}$$ for any integer n. Prove that $x_n$ is of the form $P/Q$, where $P$ is a polynomial of $x_1$ and $x_2$ with non-negative coefficients, and Q is a monomial. This problem appeared as a special case of a conjecture by Fomin and Zelevinsky in the context of cluster algebras around 2001. They proved that $x_n$ can be written as $\frac{(\text{polynomial})}{(\text{monomial})}$. Proofs of positivity are recently obtained by Nakajima ( http://arxiv.org/abs/0905.0002 ) and Qin ( http://arxiv.org/abs/1004.4171 ).

3) Nagata conjecture : Let $r$ be a positive integer $\geq 10$, but not a square. Consider $r$ random points on the plane $R^2$. Let $m$ be any positive number. Prove that the degrees of plane curves passing through each of the $r$ points at least $m$ times are greater than $m\sqrt{r}$. See "Masayoshi Nagata, On the 14-th problem of Hilbert. Amer. J. Math. 81 (1959) 766–772". This is still wide open.

I'll be grateful for any more examples.

$\endgroup$
8
  • 1
    $\begingroup$ You might like the answers to this question mathoverflow.net/questions/51531/… . $\endgroup$
    – j.c.
    Sep 17, 2011 at 21:14
  • 23
    $\begingroup$ I'm not sure that publicizing lists like this is necessarily a good idea: these are the problems that create cranks. $\endgroup$ Sep 17, 2011 at 21:16
  • 4
    $\begingroup$ Outside number theory: solution of the general cubic and quartic; impossibility of angle trisection and cube-doubling; unsolvability in radicals of the general quintic; the value of $\zeta(2)$; irrationality of $\pi$, and transcendence of $\pi$ and $e$; the 13-sphere problem, and Kepler's conjecture on sphere-packing in ${\bf R}^3$; asymptotics of Ramsey numbers (say $R(n,n)$); ... $\endgroup$ Sep 17, 2011 at 21:27
  • $\begingroup$ Irrationality and transcendence are arguably number theory, and Ramsey numbers certainly fall under combinatorics... $\endgroup$ Sep 18, 2011 at 0:28
  • 1
    $\begingroup$ Does Goldbach count? $\endgroup$ Sep 18, 2011 at 5:26

28 Answers 28

33
$\begingroup$

This is another one where it's hard to establish a lower bound due to not much work having been done on it -- it's been open since at least the 1980's, possibly the 1950's, but it's a pretty isolated problem. I think though that we can say that it's probably hard because proving it would establish better lower bounds on gaps between powers of $2$ and powers of $3$. (Or so I think I've been told, I'm afraid I'm going on memory here.)

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 that those should be any easier, though I suppose they might lack the same lower bound on hardness.)

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\le39$), 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...

I don't think anything better than that is currently known.

$\endgroup$
5
  • 1
    $\begingroup$ This is known by some as the one-complexity of an integer; it would be nice to see some more recent references besides that of Wolfram and Ed Pegg Jr. I am suspicious about the claim of Altman and Zelinsky: a reference to that work would be welcome. (My memory says that there is a small n for which f(2^n) < 2n, but my memory has been wrong before.) Harry Altman, would you kindly supply a link to your work with Zelinsky? Gerhard "Pretend I Am From Missouri" Paseman, 2011.09.18 $\endgroup$ Sep 18, 2011 at 23:06
  • $\begingroup$ Well, here's the draft on my website; the claim above also requires this really long table I computed. I will admit that verifying my computations is something of a problem (we couldn't figure out how to turn it into an algorithm, so I did them by hand; if you like I can send you the text files I did the computations in). However for low n the computations aren't long, and for n<=18 I also have an entirely different proof. (n<=13 follows from an earlier result of Rawsthorne.) $\endgroup$ Sep 18, 2011 at 23:13
  • $\begingroup$ Thank you for the reference. I will review it along with whatever notes of mine I can recover. I will be sure to contact you (or at least post here) if I find my memory is right. Thanks again for the link and the posting. Gerhard "Ask Me About System Design" Paseman, 2011.09.18 $\endgroup$ Sep 19, 2011 at 0:38
  • $\begingroup$ @Gerhard Paseman: Now that we actually have more understandable preprint detailing our method, I've linked to it above. Also, now that we can automate these computations... well, just see what I wrote above. $\endgroup$ Jul 26, 2012 at 7:39
  • 1
    $\begingroup$ @GerhardPaseman Followup poke here from the other author wondering if you've had time to look things over and/or recovered a value of n where f(2^n) < 2n. $\endgroup$
    – JoshuaZ
    Oct 17, 2021 at 23:59
62
$\begingroup$

Singmaster's conjecture. Any 15-year-old can understand what it says. Singmaster wrote that Paul Erdős told him it's probably true but probably very hard to prove.

It says there's a finite upper bound on the number of times a number other than 1 appears in Pascal's triangle. For all anyone knows for sure, the upper bound could be 8. And only one number is known to appear that many times: $$ \binom{3003}{1}=\binom{78}{2}=\binom{15}{5}=\binom{14}{6}. $$ It is known that infinitely many numbers appear 6 times; infinitely many appear 4 times; infinitely many appear 3 times, and infinitely many appear 2 times. (And only one appears just once.)

Whether any number appears an odd number of times where the odd number is more than 3 is unknown.

$\endgroup$
10
  • $\begingroup$ Well, I learned something today! Stupid question, though: are there any good reasons to believe that the conjecture is true? (Besides the fact that uncle Paul thought that it was, I mean.) $\endgroup$ Sep 22, 2011 at 1:50
  • 3
    $\begingroup$ Singmaster did some computer searches that, for the time (1970s) might have been considered moderately extensive. I think his paper(s) on the subject might say a bit more than that. I seem to recall that some his remarks left me feeling that there's a certain untuitive plausibility, but I can't be more specific now. I seem to remember a remark that there is only one row of Pascal's triangle where three consecutive entries form an arithmetic sequence (row 14, i.e. the 15th row) and there might (or might not?) have been a hint that generally things can't happen very often in Pascal's triangle. $\endgroup$ Sep 22, 2011 at 23:24
  • 2
    $\begingroup$ @MichaelHardy It is not true that there is only one row of Pascal's triangle where 3 consecutive entries are an AP: If $k\in\mathbb{N}, k>2, n=k^2-2$ and $r=\frac{n-k}2$, then $ {}_nC_{r-1}, {}_nC_{r}, {}_nC_{r+1}$ are an AP. $\endgroup$
    – Rosie F
    Oct 28, 2016 at 7:14
  • 1
    $\begingroup$ However, ${}_nC_{r-1}: {}_nC_{r}: {}_nC_{r+1}::1:2:3\Rightarrow n=14,r=5$, which is @MichaelHardy's result. $\endgroup$
    – Rosie F
    Oct 28, 2016 at 18:22
  • 1
    $\begingroup$ @GerryMyerson : I notice that I already mentioned that in the last sentence of the posting. $\endgroup$ May 27, 2019 at 2:41
61
$\begingroup$

Is the sequence of fractional parts of $(3/2)^n$ dense in $[0,1]$?

This problem has a completeley elementary statement, yet noone has any idea how to prove it.

It is known that for almost every $t$, $t (3/2)^n \bmod 1$ is equidistributed in $[0,1]$ (this follows from a much more general result of Weyl), and also that for almost every $\beta>1$, the sequence $\beta^n\bmod 1$ is equidistributed in $[0,1]$ (This was proved by Koksma in the 30s).

It also follows from results of Pisot that $(3/2)^n \bmod 1$ has infinitely many accumulation points.

This question is somewhat related to the question (already mentioned in an answer) of whether famous irrational numbers are normal, but in a sense more elementary and frustrating because it is only about multiplication/division by $2$ and $3$!

$\endgroup$
49
$\begingroup$

Here are five problems which you might like:

(1) Are there 44 unit vectors in $\mathbb{R}^5$ where the dot product between each pair is less than $\frac{1}{2}$?

I originally saw this formulation on this MO post. It is open, and related to the kissing number in 5 dimensions.

(2) A Hadamard Matrix is a square matrix all of whose entries are $\pm1$, and whose rows are mutually orthogonal. Prove that there exists a Hadamard Matrix of size $4k$ for every $k\geq 1$.

This is known as the Hadamard Conjecture. While it was considered by Hadamard in the 19th century, it is still open today.

(3) Given $n$ distinct points in the plane, what is the minimum number of distinct distances between those points?

This is a famous problem of Erdos, and while it has not completely been resolved, a near optimal bound belongs to Guth and Katz. (See Terence Tao's blog post)

(4) Prove that $$\sigma(n)\leq H_n +e^{H_n}\log H_n$$ where $\sigma(n)$ is the sum of divisors function and $H_n=1+\frac{1}{2}+\cdots+\frac{1}{n}$ is the $n^{th}$ Harmonic number.

This problem is equivalent to the Riemann Hypothesis. This reformulation was done by Jeffrey Lagarias. (Since the reformulation was more recent, I think it qualifies for this list)

(5) If $\alpha\neq 0,1$ is algebraic, and $\beta$ is irrational algebraic, will $\alpha^\beta$ be transcendental?

This is the well known Hilbert's 7th Problem. This was resolved by Gelfond and Schneider in 1934. Related to this, there is the famous story of Hilbert giving a lecture in 1919 where he said that he might see the proof of the Riemann hypothesis in his life time, that the youngest members of the audience might live to see Fermat’s Last Theorem proved, but no one present in the hall would live to see a proof of transcendence of $2^{\sqrt{2}}$. Of course the exact opposite happened.

$\endgroup$
1
  • 5
    $\begingroup$ +1: very nice list :-) $\endgroup$
    – Suvrit
    Sep 18, 2011 at 10:08
32
$\begingroup$

One simple to state problem in number theory is the Collatz Conjecture, and I'm kind of surprised no one has mentioned this one yet (considering the examples you cite, I suspect it is because this one does not require anything beyond grade-school math to understand and so may seem below the level of this question). Nevertheless I add it to the list because it is amazingly addictive to think about.

$\endgroup$
1
  • 10
    $\begingroup$ I think more likely nobody mentioned it because it's so well-known. $\endgroup$ Sep 18, 2011 at 6:00
29
$\begingroup$

Cacetta conjecture. If every vertex of an $n$-vertex directed graph has at least $n/3$ edges leaving, then the graph has a directed triangle.

You can explain this even to a non-mathematician with a few pictures.

$\endgroup$
22
$\begingroup$

The Jacobian conjecture.

$\endgroup$
22
$\begingroup$

I will list two very hard problems in linear algebra, that are in fact closely related.

  1. Recall that the cross product of vectors in $\mathbb R^3$ is not associative, and so if I write $v_1 \times v_2 \times \dots \times v_n$, I have not specified a reasonably map $(\mathbb R^3)^n \to \mathbb R^3$. Rather, to specify such a map, I must specify a parenthesization. Let's fix some $n$, and consider two different parenthesizations of $v_1 \times v_2 \times \dots \times v_n$ (e.g. for $n=3$, perhaps we consider $(v_1 \times v_2) \times v_3$ and $v_1 \times (v_2 \times v_3)$. Is it true that there exists an $n$-tuple of vectors so that both parenthesizations give the same nonzero answer?

  2. Choose a (finite) trivalent graph $\Gamma$, meaning a graph in which every vertex has three edges emanating from it, along with the following data: for each edge in the graph, choose a "left" end and a "right" end, and for each vertex choose a "first", "second", and "third" edge. (Multiple edges connecting the same vertex are allowed, but with no loss of generality you can assume that no vertex connects to itself.) To such a graph $\Gamma$ I will assign a sequence of numbers $\Gamma(N)$ depending on a parameter $N \in \mathbb N$ — actually, the sequence will not depend on the choice of "left/right" for each edge, and will depend on the choice of "first/second/third" only up to a sign. Suppose the graph has $E$ edges and $V$ vertices (by trivalence, $2E = 3V$). The number $\Gamma(N)$ will be a sum of $(N^2)^E$ terms, indexed by assigning an ordered pair $(i,j)$ to each edge, where $i,j$ range from $1$ to $N$. Then what you do is this: near the left end of a given edge labeled $(i,j)$ write the $N\times N$ matrix which is all $0$s except for a $1$ in the $(i,j)$th spot, and near the right end write the matrices which is all $0$s except for a $1$ in the $(j,i)$th spot. Do this for every edge, and now go through the vertices. At each vertex, you see three $N\times N$ matrices, $x_1,x_2,x_3$, and I want you to compute $\operatorname{tr}(x_1x_2x_3) - \operatorname{tr}(x_1x_3x_2)$. That gives you a number for each vertex (depending on the edge labelings); multiply all these vertex numbers together. Finally, as I said above, to compute $\Gamma(N)$, sum this product over all $N^{2E}$ possible edge labelings.

    Then it is a not too hard fact that for each graph $\Gamma$, $\Gamma(N)$ is a polynomial in $N$, with degree at most $2 + E - V = 2 + V/2$. The question is: Suppose that the coefficient of $\Gamma(N)$ on $N^{2 + E - V}$ is not zero. Is it necessarily true that $\Gamma(2)$ is nonzero? You can say this asymptotically: if $\lim_{N\to \infty} \Gamma(N) / N^{2 + V/2} \neq 0$, does it follow that $\Gamma(2) \neq 0$?

Each of these problems is borderline in combinatorics, but really is a natural question in linear algebra (cross products; or traces of matrices). In fact, the answer to both is "yes". But the only known proofs are very hard: both problems are equivalent to the Four Color Theorem in finite graph theory. If you are looking for problems to give in a class, these are great ones: it's possible that some undergrad will come up with a proof of one of them (especially 1), and then they have given an elementary proof of Four Color.

$\endgroup$
7
  • 4
    $\begingroup$ Just out of curiosity, is the equivalence to 4CT for either of these something that is itself difficult to see, or does it follow naturally from some clever way of rewriting either of the above problems? $\endgroup$
    – ARupinski
    Sep 17, 2011 at 22:38
  • $\begingroup$ For #2, the best write-up is by Dror Bar-Natan --- I don't have the reference handy. The short version: the leading coefficient in $\Gamma(N)$ counts the number of planar embeddings of $\Gamma$; given a planar embedding, $\Gamma(2)$ counts the number of 4-colorings of the faces. For #1, I have some recollection that there's a write-up by Kauffman, but I think the observation is first due to Penrose? It's not very hard to see the equivalence, especially if you understand the $\Gamma(2)$ part of #2. $\endgroup$ Sep 18, 2011 at 7:40
  • $\begingroup$ ("counts" in my comment above means "counts up to some normalization factors", of course.) $\endgroup$ Sep 18, 2011 at 7:44
  • $\begingroup$ For an $n$-tuple of vectors, what does "both" parenthesizations refer to? $\endgroup$
    – Suvrit
    Sep 18, 2011 at 10:05
  • $\begingroup$ @suvrit: To the two different parenthesizations mentioned in the preceding sentence. $\endgroup$ Sep 18, 2011 at 13:26
21
$\begingroup$

The naive algorithm for multiplying two $n\times n$ matrices takes $O(n^3)$ operations. Problem: Come up with an algorithm that does it in $O(n^{2.1})$. The best result so far is $O(n^{2.37})$, and the conjecture is that you can do it in $O(n^{2+\varepsilon})$ for any $\varepsilon>0$.

$\endgroup$
16
$\begingroup$

One problem that my advisor infected me with was a conjecture of Peter Frankl: Let C be a finite collection of finite sets closed under union. The easy version asks: is there an element x in union C such that x is in at least half the members of C? The hard version asks if there is such a C in the easy version, except that union C is nonempty. I and several others have rediscovered partial results; the problem is still open from my perspective.

Another accessible problem for which some new research might be developed are the Graph Reconstruction Conjectures. One version uses vertices and asks which unlabeled graphs on n vertices are reconstructible from the collection of n subgraphs each on n-1 vertices. You can do a web search for variations with edges, directed graphs, and so on.

Gerhard "Ask Me About System Design" Paseman, 2011.09.17

$\endgroup$
4
  • 5
    $\begingroup$ I don't understand the "hard version" of Frankl's conjecture, would you mind restating it? Thanks. $\endgroup$
    – bof
    Oct 12, 2014 at 20:50
  • $\begingroup$ I join @bof - please explain. Does everybody else understand?? $\endgroup$ Oct 28, 2016 at 6:50
  • $\begingroup$ @bof and others: the easy version has the answer "not always", when you pick C to have a single member, that member being the empty set. When you exclude that by having union C be nonempty, the problem is harder. Gerhard "Better Later Than Too Late" Paseman, 2018.10.22. $\endgroup$ Oct 22, 2018 at 21:42
  • $\begingroup$ It's hard for me to remember what was confusing me about your "hard version" when I posted my comment four years ago. Hmm. The "easy version" asks if there is an $x$ with a certain property, while the "hard version "asks if there is such a $C$ . . ." Hmm. It sounds like your "hard version" is asking about the existence of a $C$ which is a finite collection of finite sets closed under union, with $\bigcup C$ nonempty. Yes, I believe there is such a $C$. That doesn't seem so hard. $\endgroup$
    – bof
    Oct 22, 2018 at 22:03
16
$\begingroup$

Conway's Thrackle Conjecture: $E \le V$ in any "thrackle," a particular type of drawing of a graph of $V$ vertices and $E$ edges in the plane, requiring that every pair of edges "meet" once. Dangerously addictive! And advances made every few years; it is by no means an isolated conjecture.


          Thrackle

$\endgroup$
12
$\begingroup$

A forty years old open conjecture in automata theory, called the Černy conjecture, asserts that if $X$ is a set of mappings on $n$ symbols such that a constant map can be obtained by repeatedly composing maps from $X$, then a constant map can be obtained from a composition of at most $(n-1)^2$ elements of $X$, where repetitions are allowed. This is known to be a lower bound. The best known upper bound is cubic.

$\endgroup$
12
$\begingroup$

The Casas Alvero conjecture: Let $f \in \mathbb{C}[x]$ be a monic polynomial of degree $n$. Suppose that for each $k = 1, \ldots, n-1$, there is a common root of $f$ and $f^{(k)}$. Then $f = (x-a)^n$ for some $a \in \mathbb{C}$. It is known only for the case that $n$ is a prime power or two times a prime power (see for example, this). At some point I thought I proved it :-)

$\endgroup$
2
11
$\begingroup$

Is $\pi$ normal in base $b$, that is, are the base $b$ digits of $\pi$ evenly distributed among $0, 1, 2, \ldots, b-1$, for every integer $b > 1$? Same question for $e$, $\ln 2$, and $\sqrt{2}$. These and most well-known irrational numbers are not known to be normal in any base--yet almost all real numbers are normal in every base.

$\endgroup$
9
$\begingroup$

Can every convex polyhedron be cut along its edges and unfolded into one connected piece without overlap?

This problem was first posed formally by Shephard in 1975 (although it arguably dates back to the 1500s). There are also many related (un)folding problems which are still open, see http://maven.smith.edu/~orourke/TOPP/P9.html#Problem.9

$\endgroup$
8
$\begingroup$

Take two commutative rings $A$ and $B$ such that the polynomial rings $A[X]$ and $B[X]$ are isomorphic. Does this imply that $A$ and $B$ are isomorphic? (I think this is still open.)

$\endgroup$
1
8
$\begingroup$

More number theory, but very elementary to state and, as far as I know, first proposed by Ailon and Rudnick in 2004, so not 20th century, but 21st century!

Conjecture [1] There are infinitely many integers $n\ge1$ such that $\gcd(2^n-1,3^n-1)=1$.

More generally, if $a,b\in\mathbb{Z}$ are multiplicatively independent, then there should be infinitely many $n\ge1$ such that $\gcd(a^n-1,b^n-1)=\gcd(a-1,b-1)$. (A rough, and not entirely believable, heuristic suggests that the set of primes $p$ such that $\gcd(a^p-1,b^p-1)=\gcd(a-1,b-1)$ has density 1.)

Ailon and Rudnick prove a stronger result with $\mathbb Z$ replaced with $\mathbb C[T]$, namely if $a(T)$ and $b(T)$ are multiplicatively independent, then there is a polynomial $c(T)\ne0$ such that $$ \gcd(a(T)^n-1,b(T)^n-1) \mid c(T) \quad\hbox{for all $n\ge1$.} $$

In the other direction, a deep result of Bugeaud, Corvaja, and Zannier [2] says that for every $\epsilon>0$ there is a $C=C(a,b,\epsilon)$ so that $$ \gcd(a^n-1,b^n-1) \le C\exp(\epsilon n)\quad\hbox{for all $n\ge1$.}. $$ So a hard, but proven, result that can be explained to students is prove that there is a constant $C$ so that (say) $$ \gcd(2^n-1,3^n-1) \le C\cdot 2^{n/10} \quad\hbox{for all $n\ge1$.} $$ (Further note: The proof in [2] does not give an effective way of computing the constant $C$, since it ultimately relies on Schmidt's subspace theorem.)

[1] N. Ailon and Z. Rudnick, Torsion points on curves and common divisors of $a^k-1$ and $b^k-1$, Acta Arith. 113 (2004), 31-38.

[2] Y. Bugeaud, P. Corvaja, U. Zannier An upper bound for the GCD of $a^n-1$ and $b^n-1$, Math. Z. 243 (2003), 79-84.

$\endgroup$
8
$\begingroup$

It is well-known that a simple random walk on a square integer lattice is recurrent to 0, meaning $P_0(X_t = 0 $ for some $t > 0) =1$. The standard proof is to show that $\sum_{t\ge 0} P(X_t = 0) = \infty$, which boils down to a combinatorial problem.

It is also well-known that the similar probability for 3-dimensional lattice is $<1$, whence the famous quote "a drunk man can eventually find his way home, but a drunk bird will be lost forever". Now consider the following edge-reinforced version of the 2d case first proposed by Persi Diaconis: initially all edges on $\mathbb{Z}^2$ have weight 1. As soon as an edge is traversed, its weight goes up to 2, and stays 2 forever. The probability of choosing an edge is proportional to its weight: so for instance if the four edges around a vertex is $(1,2,2,1)$, then with probability $1/6$ the first edge will be chosen. Note the edges are undirected, so the weight applies to both directions. This corresponds to the intuitive strategy of favoring roads one has seen before at an intersection. It seems this strategy could only make the walk more recurrent. However at least for the weight choices stated here, it has remained open. See this paper which discusses some history.

$\endgroup$
7
$\begingroup$

If you push together disks in the plane must their union decrease? More formally, given a set of disks in the plane consider each of the pairwise distances between their centers. If you decrease (or keep fixed) each of these pairwise distances, is the area of the union of the disks non-increasing?

The problem is solved in $\mathbb{R}^2$ (see the link in Shamisen's comment below). I believe the analogous problem is open for larger dimensions.

$\endgroup$
2
  • 2
    $\begingroup$ This is the Kneser-Poulsen conjecture, right? I think that instead of considering that the sum of the pairwise distances between their centers decrease, you must consider that every pairwise distance between the centers decrease. The case $d = 2$ is solved in a paper by K. Bezdek and R. Connely. $\endgroup$
    – Tadashi
    Oct 13, 2014 at 3:59
  • 2
    $\begingroup$ Thanks, yes you are right. I will make an edit. $\endgroup$
    – CoffeeCat
    Oct 13, 2014 at 8:17
7
$\begingroup$

Here is a problem accessible to someone who has taken multivariable calculus or linear algebra:

What is the maximal number, $N$, of mutually unbiased bases in $\mathbb{C}^d$, a collection of orthonormal bases with vectors $x,y$ in separate bases satisfying $|\langle x,y \rangle|^2=\frac{1}{d}$?

This maximum number is known for all prime power dimensions $d=p^k$ so that first open case is $d=6$ where the best known upper bound is $N\leq7$. It is widely believed (due to numerical evidence) that in this case the largest number of MUB's is $N=3$.

$\endgroup$
3
  • $\begingroup$ Can you point me to a review that discusses this question, and describes the attempts made to solve the d=6 case? $\endgroup$
    – gen
    Jul 21, 2021 at 21:27
  • 2
    $\begingroup$ researchgate.net/profile/Philippe-Jaming/publication/… $\endgroup$ Jul 22, 2021 at 23:03
  • $\begingroup$ Thank you very much $\endgroup$
    – gen
    Jul 23, 2021 at 2:01
6
$\begingroup$

I like the "graceful tree conjecture": The vertices of every tree with $n+1$ vertices can be labelled bijectively by the set $\{0,\dots,n\}$ such that differences of labels on (suitably oriented) edges give the set $\{1,\dots,n\}$.

https://en.m.wikipedia.org/wiki/Graceful_labeling

$\endgroup$
5
$\begingroup$

Maybe you want to limit it to problems first proposed in the 20th century or later? Otherwise, proving the fundamental theorem of algebra took decades or longer. Gauss's first proof, for example, had a famous topological gap found in the 1920's.

Several of Hilbert's problems from 1900 are understandable at undergrad level and stayed open many years or are still open.

Then there are computer proofs, e.g. the 4-color theorem. Do those count? A few years ago we got a multi-year computer calculation finally proving that checkers is a theoretical draw, something everyone already knew even without an exhaustive proof.

Title of your question first sounded like merely "surprisingly difficult" rather than "stayed open at research level for a long time". One I like from some other MO thread: let C be a curve inside the unit square, connecting the lower left to upper right corner. Let D be a similar curve, connecting upper left to lower right. Prove that C and D intersect.

$\endgroup$
1
5
$\begingroup$

Zamolodchikov’s conjecture : Let $I$ be an $n$-element set of indices, and $A = (a_{ij})_{i,j\in I}$ an indecomposable Cartan matrix of finite type. (You don't have to use these words. There is an explicit list of matrices.) A family $(Y_i(t))_{i\in I,t\in \mathbb{Z}}$ of commuting variables satisfying the recurrence relations $$Y_i(t + 1)Y_i(t − 1) =\prod_{j\neq i} (Y_j(t) + 1)^{−a_{ij}}$$ is periodic, more precisely, there exists a positive integer $h$ such that $Y_i(t+2(h+2))=Y_i(t)$ for all $i$ and $t$.

This problem appeared in the theory of thermodynamic Bethe ansatz in 1991. Frenkel--Szenes and independently Gliozzi--Tateo proved a partial result (type A) around 1995, and Fomin and Zelevinsky completed in 2001.

$\endgroup$
1
  • $\begingroup$ If I remember correctly, there is an extension of the conjecture, where the variables are labelled by a product of two (simply laced?) Dynkin diagrams, and where the periodicity is supposed to be the sum of the two dual coxeter numbers. I think that's stil open(?) $\endgroup$ Sep 30, 2011 at 8:27
5
$\begingroup$

Which (nonconvex) planar polygons can be dissected into squares? (Freiling et al., 2000)

$\endgroup$
5
$\begingroup$

Check out Unsolved Problems in Combinatorial Game Theory from More Games of No Chance RICHARD K. GUY AND RICHARD J. NOWAKOWSKI. This is from about 2002, so some of these probably have been partly solved, but many are very easy to state.

$\endgroup$
4
$\begingroup$

What numbers are integrally represented by the three-variable inhomogeneous polynomial $$ 7 x^2 + 3 x y + 9 y^2 + z^3 \; \; ? $$ This is one of two similar problems where it is easy to show that certain integers are not represented owing to their prime factorization. The first inkling that it might be possible to prove if and only if on a characterization of represented numbers is due to Kevin Buzzard, in his answer to my first MO question. The list of similar problems for class number three is at LINKSECONDTRY but in any case works in my comment below

My first MO question, with answer by Kevin Buzzard and evidence about why if-and-only-if is difficult, is Integers not represented by $ 2 x^2 + x y + 3 y^2 + z^3 - z $

$\endgroup$
7
  • 1
    $\begingroup$ The OP would likely object that this is number theory. $\endgroup$ Sep 17, 2011 at 21:46
  • $\begingroup$ agreed, "but less famous problems in number theory." Until today I'm the only one who knew this (and one of the few who know why it is open), so this is $< \mbox{famous}$ $\endgroup$
    – Will Jagy
    Sep 17, 2011 at 21:54
  • 1
    $\begingroup$ OK, but then it's hard to get a good lower bound on the problem's difficulty. $\endgroup$ Sep 17, 2011 at 21:57
  • 1
    $\begingroup$ will works with manjul ??? $\endgroup$ Sep 18, 2011 at 18:49
  • $\begingroup$ Luis, I have known Manjul Bhargava for a long time, but we are hardly in touch these days (after Kaplansky died). In April (I think) there was a week conference at MSRI, I told this and related problems to Manjul, Henri Cohen, and Hendrik Lenstra. I saw little sign at the time that any of the three would pursue the matter, but there seemed to be agreement that this was Manjul's area. I would be interested to hear if he has been working on this or, at least, mentioning my collection of similar problems in talks. Class number three problems at zakuski.utsa.edu/~jagy/jagy_list.pdf $\endgroup$
    – Will Jagy
    Sep 18, 2011 at 19:24
4
$\begingroup$

The Goldbach's conjecture:

Every even integer $k>2$ can be expressed as the sum of two primes.

The Waring's problem:

For each natural number $d$ there is a positive integer $h$ such that every natural number is the sum of at most $h$ $d$-th powers of natural numbers.

For every $d$, let $h(d)$ denote the minimum number of $d$-th powers needed to represent all integers. The problem is to find $h(d)$. For instance $h(1)=1, h(2)=4, h(3)=9, h(4)=19$.

Euler's conjecture: $h(d)=2^d+[(\frac{3}{2})^d]-2$.

$\endgroup$
1
  • 1
    $\begingroup$ Did you notice where it says, "Edit: c) and first proposed in the 20th century or later."? $\endgroup$ Apr 13, 2014 at 1:20
4
$\begingroup$

Consider all possible sequences $(x_1,\ldots,x_n)$ in $\mathbb{Z}^2$ such that $x_1=0$, $|x_{i+1}-x_i| = 1$, and $i\neq j \rightarrow x_i \neq x_j$. For any fixed $n$, there are only finitely many of them so we pick one uniformly at random. Question: what is the asymptotic behaviour of $R_n = \mathbb{E}\sup_{i\le n} |x_i|$ as $n \to \infty$?

One trivially has $R_n \le n$ and $R_n \ge \sqrt{n/\pi}$. The conjecture (about 70 years ago by Flory) is that $R_n \approx n^{3/4}$. (The original argument apparently contained conceptual mistakes and reached the "correct" value somewhat by miracle. The modern argument is that if the self-avoiding random walk has a conformally invariant scaling limit, then it has to be one of the SLE($\kappa$), but SLE($8/3$) is the only one with the restriction property, so it has to be that one. The exponent then follows from the known self-similarity properties of SLE.)

To appreciate how far one is from proving this, consider that there is no theorem showing that there exists $\epsilon > 0$ such that either $R_n \lesssim n^{1-\epsilon}$ or $R_n \gtrsim n^{{1\over 2}+\epsilon}$! The best is a relatively recent article by Duminil-Copin and Hammond showing that $\lim_{n \to \infty} R_n/n = 0$... To the best of my knowledge, that argument does not provide any rate at all, so we still don't know that $R_n \lesssim n/\log\log n$ for example...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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