Skip to content

Closing An Open Problem

September 5, 2020


Crawl, then walk, then run.

Bogdan Grechuk is a lecturer in the math department at the University of Leicester. His office is in the Michael Atiyah Building. Pretty cool. He works in risk analysis, but is more broadly interested in math of all kinds. See his wonderful book Theorems of the 21st Century. Or go to his web site.

Today Ken and I want to talk about solving open problems.

Grechuk’s site got us thinking about results that solve open problems. Most of us like to think our research solves an open problem. Personally I can say that I have tried to solve problems for the first time, but did not always succeed.

Open problems usually mean something stronger. To be an open problem, a problem must be known to some community for some time. Advances in math and in complexity theory roughly fall into two categories:

  1. Results that prove or disprove something that was explicitly stated before. The more who knew the problem the better. The longer the problem was known the better, too.

  2. Results that prove something that is new. Something that no one had explicitly asked before.

Both type of results are important. The latter kind may ultimately be more important. They raise new questions, often contain new methods, and move the field ahead in a new direction. See our
discussion of Freeman Dyson and frogs and birds.

Think of how Kurt Gödel’s incompleteness theorem was unsuspected, or how Alan Turing’s proof of undecidability of the halting problem came in tandem with settling the criterion for computability, or years latter the definition of public-key crypto-systems. But we will focus on open problems in the sense (1).

Claiming A Solution

Ken and I are amazed that when an open problem is claimed, especially for P versus NP, the claim swallows it whole. That is the claim is that the full problem is solved. We do not recall once when the claim was:

  • We are able to prove that SAT requires quadratic time, or

  • We can show that SAT is in co-NP.

Either of these would be a “stop the press” result.

For a more concrete example, suppose you claim to have a polynomial-time algorithm for finding a maximum clique in an undirected graph {G}. Of course this implies P{=}NP. Your algorithm may require a chain of difficult lemmas that obscure its workings. Can you perhaps analyze its effectiveness more easily on random graphs? Here are two relevant facts:

  • In 1976, David Matula proved that with high probability for a random {n}-vertex graph of edge probability {p}, the size of the maximum clique is one of the two integers flanking {2\log_{1/p}(n)}.

  • As observed in 1976 by Dick Karp in his paper, “The Probabilistic Analysis of Some Combinatorial Search Algorithms,” no polynomial time algorithm is known to achieve size {(1+\epsilon)\log_{1/p}(n)}, for any {\epsilon > 0} and sufficiently large {n}.

You only need to close a gap of a factor of {2}, not to hit the maximum value exactly, and you do not need to succeed for all graphs. The behavior of random graphs should help your analysis. A more-recent mention of Karp’s open problem is in these 2005 slides.

Some Examples

{\bullet } Collatz Conjecture : Terence Tao made important progress on this notorious problem. He said:

In mathematics, when we cannot solve a problem completely, we look for partial results. Even if they do not lead to a complete solution, they often reveal insights about the problem.

Recall this is also called the {3n+1} problem. It asks for the long-term behavior of the function: f(n) which is equal to n/2 for n even and 3n+1 for n odd.

The conjecture is that for every {n}, iterating the function eventually hits {1}, i.e., {f^i(n) = 1} for some {i}.

There are two ways the conjecture can fail:

  • There is a finite cycle besides the trivial cycle {1 \rightarrow 4 \rightarrow 2 \rightarrow 1}.

  • For some {n}, the sequence {f^i(n)} goes off to infinity.

What Tao proved is that “many” values {n} achieve: f^i(n) < \log^* n for some i .

Grechuk's page includes the definition of “many,” which turns out to be weaker than saying a {(1-\epsilon)} proportion of values {n} “swing low” in this sense. Moreover, Tao proved this for any unbounded function {g(n)} in place of the iterated logarithm, such as the inverse Ackermann function. Note this is a case where randomized analysis worked—in the hands of a master.

{\bullet } Twin Prime Conjecture : Yitang Zhang made tremendous progress on this long standing conjecture. He proved that infinitely often is a prime {p} so there is another prime {q>p} bounded above by {p +C}. His {C} was {70} million, but this was still a breakthrough. Previously no bounded {C} was known. We discussed this before here.

{\bullet } Sensitivity Conjecture : Hao Huang is given as a counterexample to partial progress—it is the exception that proves the rule. He solved the full conjecture. He proved that every {2^{n}-1} vertex induced subgraph of the {n}-dimensional cube graph has maximum degree at least {\sqrt{n}}. The previous best was only order logarithm in {n}. But there does remain some slack: He proved a fourth-power bound, but can it be closed to cubic or even quadratic? We discussed this last year.

By the way:

The expression comes from the Latin legal principle exceptio probat regulam (the exception proves the rule), also rendered as exceptio firmat regulam (the exception establishes the rule) and exceptio confirmat regulam (the exception confirms the rule). The principle provides legal cover for inferences such as the following: if I see a sign reading “no swimming allowed after 10 pm,” I can assume swimming is allowed before that time.

Advice To Claimers

Our general advice to claimers:

Okay you are sure you have solved the big problem. Write up the weakest new result that you can.

Use your methods, your insights, to minimize the work needed for someone to be 99.99% convinced that you have proved something new, rather than a lower confidence of your having proved something huge. For P{=}NP show that you have a exponential algorithm that is better than known. Or for P{<}NP give a non-linear lower bound.

The rationale is: You are more likely to get someone to read your paper if you make a weaker claim. A paper titled: A New SAT Algorithm that Runs in Sub-exponential Time is more likely to get readers than a paper tiled P=NP. This shows that readership is non-monotone.

This is consequence of two phenomena: One is believability. The weaker paper is more likely to be correct. One is human. The stronger paper, if correct, may not be easy to improve. A weaker paper could have results that the reader could improve and write a follow-on paper:

In Carol Fletcher’s recent paper an {2^{n^{1/3}}} algorithm is found for SAT. She required the full Riemann Hypothesis. We remove that requirement and {\dots}

Open Problems

What about our advice: what would you do if you solved a major open problem? Note that the examples we highlighted all have slack for improvement short of the optimum statements.

30 Comments leave one →
  1. September 5, 2020 3:04 pm

    These are my attempts:

    The Robin’s inequality is true for every natural number $n > 5040$ if and only if the Riemann hypothesis is true. We prove the Robin’s inequality is true for every natural number $n > 5040$ when $n$ is not divisible by $3$. Moreover, we demonstrate the Robin’s inequality is true for every natural number $n > 5040$ when $n$ is not divisible by $5$ and/or $7$.

    See more in:

    https://doi.org/10.5281/zenodo.3648511

    In 1912, Edmund Landau listed four basic problems about prime numbers in the International Congress of Mathematicians. These problems are now known as Landau’s problems. Landau’s fourth problem asked whether there are infinitely many primes which are of the form $n^{2}+1$ for some integer $n$. This problem remains open. We prove this conjecture is indeed true.

    See more in (Note: this is a naive attempt):

    https://doi.org/10.5281/zenodo.4010223

    In addition, professor Dick was helping me in the revision of my attempt to P = NP, but he suddenly stopped the revision and therefore, there are great chances the paper is incorrect (I am pretty thankful for his past help). However, I will share it.

    See more in:

    https://doi.org/10.5281/zenodo.3355776

    I hope you could enjoy this,
    Any possible advice or help will be appreciated,
    Thanks in advance,
    Frank

  2. Craig permalink
    September 5, 2020 9:05 pm

    So if you are Gauss and you discover the law of quadratic reciprocity, it is better to publish part of it, when either p or q is congruent to 1 mod 4 instead of for any odd prime p and q?

    • rjlipton permalink*
      September 5, 2020 10:38 pm

      Dear Craig:

      Good point. If the proof was simpler maybe. In any event you ask a good question.

      Best

      Dick

    • Peter Gerdes permalink
      September 5, 2020 11:19 pm

      I always thought that the expression derived from the old use of ‘proves’ meaning tests (a proof was something like the mark on a suit of armor from shooting it with a gun to test it could deflect gun shots). Your analysis linking it to the Latin seems to make much more sense. Thanks.

    • Peter Gerdes permalink
      September 5, 2020 11:24 pm

      I’d read the piece as suggesting strategies for approaching a problem (and maybe asking colleagues for advice) not as a suggestion about what to publish.

      I mean that’s how I do my proofs. Start by considering how to handle specific concrete cases and then try to generalize or at least apply the general reasoning to a more concrete and easier to conceptualize case first.

  3. Frank Vega permalink
    September 5, 2020 10:26 pm

    A weakest new result: The Robin’s inequality is true for every natural number $n > 5040$ if and only if the Riemann hypothesis is true. We prove the Robin’s inequality is true for every natural number $n > 5040$ when $n$ is not divisible by $3$. Moreover, we demonstrate the Robin’s inequality is true for every natural number $n > 5040$ when $n$ is not divisible by $5$ and/or $7$.

    https://doi.org/10.5281/zenodo.3648511

    • rjlipton permalink*
      September 5, 2020 10:40 pm

      Dear Frank:

      I like this. Obvious question is to improve on this. By the way are there papers on this type of partial result for RH? I wonder.

      Check this out: paper. They prove several related theorems.

      Best

      Dick

      • Frank Vega permalink
        September 15, 2020 10:12 pm

        Dear Dick:

        The last time you checked my paper (about P vs NP):

        https://doi.org/10.5281/zenodo.3355776

        you didn’t confirm me the last two theorems were correct. Since then, I suspected the last two theorems were wrong, because you left the revision by email. However, I have found a beautiful way of replacing these theorems by a single one in clear and simple way. In this way, there are more chances the paper is totally correct at this moment.

        What do you think?
        Thanks in advance,
        Frank

      • Frank Vega permalink
        September 16, 2020 11:15 am

        Dear Dick:

        I changed MAX-3SAT by 3UNSAT in my paper, since the linear Diophantine equations with m variables has none or infinite solutions.

        https://doi.org/10.5281/zenodo.3355776

        Best,
        Frank

      • Frank Vega permalink
        September 16, 2020 1:19 pm

        Dear Dick:

        I finally changed 3UNSAT by a solution to 3SAT. Maybe my claim is wrong. However, there are great chances that my method can be used to solve many instances of 3SAT such as the instances with n variables that have more than (2^{n – 1} – 1) satisfying truth assignments. I wonder if we can find a weakest new result from this claim that might not cover all the cases, but a huge amount of them.

        https://doi.org/10.5281/zenodo.3355776

        Best,
        Frank

      • Frank Vega permalink
        September 16, 2020 3:27 pm

        Dear Dick:

        I will keep the older version in:

        https://hal.archives-ouvertes.fr/hal-02199310

        since the suspicious of the last two Theorems are wrong is only a suspicious and nothing more (they might be right…, since I have no a strong evidence they could be wrong).

        Best,
        Frank

      • Frank Vega permalink
        September 16, 2020 6:03 pm

        Dear Dick:

        I read again the older version in:

        https://hal.archives-ouvertes.fr/hal-02199310

        and it’s correct. I will keep the new version in:

        https://doi.org/10.5281/zenodo.3355776

        since this one is less theoretical (but possibly incomplete).

        Best,
        Frank

      • Frank Vega permalink
        September 18, 2020 4:52 pm

        Dear Dick:

        I have unified both versions into a single one with stronger arguments:

        https://doi.org/10.5281/zenodo.3355776

        Best,
        Frank

    • Frank Vega permalink
      September 5, 2020 10:57 pm

      Dear Dick:

      My proof is based on the paper of the Choie, Lichiardopol, Moree and Sole (On Robin’s criterion for the Riemann hypothesis):

      Click to access article03.pdf

      Certainly, I slightly modify the Theorem 1.1 from that paper in order to obtain my result. I think they have made the major contribution for the Robin’s inequality with that paper until our days: They proved the Robin’s inequality is true for every natural number $n > 5040$ when $n$ is not divisible by $2$. My proof is beyond their result: only a new small step forward.

    • Frank Vega permalink
      September 5, 2020 11:01 pm

      Dear Dick:

      We are talking about the same paper.

      Best,
      Frank

    • Frank Vega permalink
      September 6, 2020 3:29 pm

      Dear Dick (Answering your obvious question):

      Of course, this could be improved. Actually, I have updated the result yesterday and I think I could continue doing it in the next few days. This is the new approach:

      ————————–

      We prove the Robin’s inequality is true for every natural number $n > 5040$ when $n$ is not divisible by $3$. More precisely: every possible counterexample $n > 5040$ of the Robin’s inequality must comply that $n$ should be divisible by $2^{20} \times 3^{13}$. In addition, the Robin’s inequality is true for every natural number $n > 5040$ when $n = 3^{k} \times m$, $\frac{3}{2} \times \ln \ln m \leq \ln \ln (3^{k} \times m)$ and $3 \nmid m$. Moreover, we demonstrate the Robin’s inequality is true for every natural number $n > 5040$ when $n$ is not divisible by $5$. Furthermore, we show the Robin’s inequality is true for every natural number $n > 5040$ when $n$ is not divisible by $7$.

      —————————————–

      https://doi.org/10.5281/zenodo.3648511

    • Frank Vega permalink
      September 8, 2020 12:16 am

      Dear Dick:

      We extended the result: We finally prove the Robin’s inequality is true for every natural number $n > 5040$ when $n$ is not divisible by any prime number $q_{m} \leq 113$. I am figuring out whether this could be improved or not.

      https://doi.org/10.5281/zenodo.3648511

      Best,
      Frank

    • Frank Vega permalink
      September 9, 2020 6:35 pm

      Dear Dick:

      After a lot of efforts, I achieved to solve the Riemann hypothesis. I used my previous work to prove the Robin’s inequality is true when n is not divisible by 3. Later, I showed that the Robin’s inequality is true when n is divisible by 3. I think the proof is done!!!

      https://doi.org/10.5281/zenodo.3648511

      Best,
      Frank

    • Frank Vega permalink
      September 9, 2020 8:45 pm

      Dear Dick:

      We can apply my Theorem when n is divisible by 6 for only the case when n is divisible by 2. This proof would be shorter, because of Choie, Lichiardopol, Moree and Sole (On Robin’s criterion for the Riemann hypothesis) proved the result when n is not divisible by 2. This will give a total amount of at most 3 pages for a whole proof. I think this is too short for a paper which claims a solution to the Riemann hypothesis. For that reason, I won’t change it at this moment. However, this could be fit very well in a blog post.

      What do you think?
      Frank

    • Frank Vega permalink
      September 10, 2020 12:25 am

      The Riemann approach is wrong!!! Too simple to be true!! I will return to the previous result: the Robin’s inequality is true for every natural number $n > 5040$ when $n$ is not divisible by any prime number $q_{m} \leq 113$. This can be improved to $q_{m} < 2209$: I will work on it…

  4. Ivan Gusev permalink
    September 6, 2020 8:15 pm

    For me challenging an open problem is an opportunity to develop and expand my own tools. Mathematics is a philosophy of understanding the world through the language of its structures. And more advance your tools are more understanding you can achieve. Alas, evry time I invent smth turns out it already was discovered. So, I have wild curiosity about ideas that I didn’t see present in concurrent math but made by me. Have you seen smth like chaotic claims? Suppose we have a statement A which says structure S can have property P when condition C is met. We can rephrase it into chaotic claim – A is chaotically false. Now we need to establish a language for such claim. Suppose we have hydrodynamic equation that is replaced with finite amount of automata and each of them is a point of fluid that has to form a flow in a presence of force. Let each of those points have single heuristic function H that can guide each of them individually and store assigned hidden parameters and instructions in them. That H can now be replaced with another H’ that has all those hidden parameters encapsulated in it. So, we can assume existence of hidden parameters that determine the outcome of computation. And even more, skip them because they can be hidden in interactions of H’ with itself. So, we can get a simple function that does a lot with no commentary. Now let’s imagine a chaotic rocket that falls from the sky. This rocket can fall like a ball or like a feather and chaotically change its direction, no one can predict how it is going to land on the ground. Now, let’s use H in relation to rocket control surfaces, suppose that there do exist hidden parameters that allow us to determine a chaotic vector CV of aerodynamic force and its evolution. We could obstruct its application to a body of a rocket by manipulating control surfaces in such a way that it would decrease or increase CV in power and therefore direction. If only we would be able to find finitely many of them and distinguish them from one another in finite amount of time. Now we can make H’ that would land a rocket in exact spot given to it like H'(coordinate) and H’ lands a rocket everytime through random path. Each starting position now has its own set of landing points to whcih we can land, they may look like mandelbrot set or alike but to each point there are infenetly many paths that can be performed by class of H’ functions and each one of them. So now we can show that there are points that cannot be landed on from a given starting position. And if a claim says that we can we can show our “enery conservation law/symmetry” that says we wouldn’t have enery needed to reach that point but because we have all H’s we can say that it is chaotically impossible and therefore A is chaotically false. Proving exact border between possible points and impossible is pretty hard though. I mean C and P can be chaotically united in such way on relation to A. I can try to show all of this mathematically if you are interested.

  5. Frank Vega permalink
    September 9, 2020 7:22 pm

    In addition, all my work is free available in (my homepage):

    https://uh-cu.academia.edu/FrankVega

    I hope all this could be sound interesting to you…

  6. Angela Weiss permalink
    September 10, 2020 9:01 am

    I’ve been working with a big problem, whether P=NP. Of course, there was a fatal flaw and I gahered all pieces of “my proof” and wrote a very interesting draft, in submission.
    I think that I’ve not proved that P=NP nor P=\=NP but Iǘe reached a result that can separate 3-SAT in categories. One polinomially solved and a “misterious” class.
    I can share the result and, If I have skills, I can read and criticize other results, as an exange.
    weiss@ime.usp.br

  7. September 10, 2020 3:54 pm

    delighted on multiple levels that Tao finally published something on collatz, hes been “flirting” with it for many years with an old highly-visited/ viewed blog entry (below). he has career advice to avoid very hard problems, and doesnt really take it himself. his result sounds very similar to Terras from 1970s which says roughly “most iterates converge” and would like to see them compared more closely side by side.

    not very prominently mentioned, Tao included some numerical/ computational work in his latest results. which also figured prominently in narrowing the gap found by Zhang. would really like to see some closer analysis/ profile of the computational work done on these problems. think it is increasingly substantial/ significant. the mathematicians seem to tend to understate it and/ or barely mention it. its almost as if its a slight embarrassment to them, lol! there is definitely still some big difference in cultures here. in my opinion it verges on a bias or blind spot at times.

    collatz is a paradoxical problem, reams have been written on it over many decades but at any given time/ moment it seems almost as if nobody in particular is actively working on it. its also considered not very significant by many but think my own research strongly refutes that pov. its highly connected with fractal analysis but again, that is rarely mentioned anywhere. there is a nice paper. speaking of flirting with the problem, how about YOU guys look into and profile this fractal angle sometime? think you would enjoy it. 🙂

    anyone who thinks theres something worthwhile to collatz please drop by my blog and (even more substantially) leave some comments! its been a mostly very lonely jihad over the years now, early on was surprised at the silence but now have learned to live with it (as they say in CS, thats not a bug, its a feature). saying this semifacetiously it is said the problem attracts cranks, and strangely parallel to that, generally mostly only the trolls ever seem to write anything on my blog lol! a crying shame but hey thats cyberspace for you 😦 😥 😛

    https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/

    https://vzn1.wordpress.com/category/collatz/

  8. September 10, 2020 3:54 pm

    The former looks merely like a known heuristic probability argument. That argument is not a proof.

  9. September 10, 2020 4:33 pm

    ⭐ ❤ also, a very nice popsci writeup of the recent Tao result. really luv quanta mag, thx so much simons!

    https://www.quantamagazine.org/mathematician-terence-tao-and-the-collatz-conjecture-20191211/

  10. Frank Vega permalink
    September 10, 2020 6:05 pm

    Another weakest result: The Robin’s inequality is true for every natural number $n > 5040$ if and only if the Riemann hypothesis is true. Given a natural number $n = q_{1}^{a_{1}} \times q_{2}^{a_{2}} \times \cdots \times q_{m}^{a_{m}}$ such that $n > 5040$, $q_{1}, q_{2}, \cdots, q_{m}$ are prime numbers and $a_{1}, a_{2}, \cdots, a_{m}$ are positive integers, then the Robin’s inequality is true for $n$ when $q_{1}^{\alpha} \times q_{2}^{\alpha} \times \cdots \times q_{m}^{\alpha} \leq n$, where $\alpha = (\ln n’)^{\beta}$, $\beta = (\frac{\pi^{2}}{6} – 1)$ and $n’$ is the squarefree kernel of $n$.

    https://doi.org/10.5281/zenodo.4023203

  11. Frank Vega permalink
    September 12, 2020 10:18 pm

    I have unified all my previous comments and new results in:

    https://doi.org/10.5281/zenodo.3648511

Trackbacks

  1. collatz standing on shoulders of giants (not!) | Turing Machine

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s