Polymath Wiki - User contributions [en]

Imo 2011

2011-07-19T19:56:17Z

Rweba: Fixed typo

This is the wiki page for the mini-polymath3 project, which seeks solutions to [http://official.imo2011.nl/problems.aspx Question 5 from the 2011 International Mathematical Olympiad].

The project will start at [http://www.timeanddate.com/worldclock/fixedtime.html?year=2011&month=7&day=19&hour=20&min=0&sec=0 July 19 8pm UTC], and will be hosted at the [http://polymathprojects.org/ polymath blog]. A discussion thread will be hosted at [http://terrytao.wordpress.com Terry Tao's blog].

== Rules ==

This project will follow the [http://polymathprojects.org/general-polymath-rules/ usual polymath rules]. In particular:

* Everyone is welcome to participate, though people who have already seen an external solution to the problem should refrain from giving spoilers throughout the experiment.
* This is a team effort, not a race between individuals. Rather than work for extended periods of time in isolation from the rest of the project, the idea is to come up with short observations (or to carry an observation of another participant further) and then report back what one gets to the rest of the team. Partial results or even failures can be worth reporting.
* Participants are encouraged to update the wiki, or to summarise progress within threads, for the benefit of others. (In particular, linking between the wiki and specific comments on the blogs is highly encouraged.)

== Threads ==

Planning:

* [http://terrytao.wordpress.com/2011/06/09/mini-polymath-3-2011-imo-question/ Mini-polymath 3: 2011 IMO question], June 9 2011.

Discussion:

* [http://terrytao.wordpress.com/2011/07/19/mini-polymath3-discussion-thread Mini-polymath3 discussion thread], July 19 2011.

Research:

* [http://polymathprojects.org/2011/07/19/minipolymath3-project-2011-imo/ Minipolymath3 project: 2011 IMO], July 19 2011

== The question ==

: '''Problem 2.''' Let <math>S</math> be a finite set of at least two points in the plane. Assume that no three points of <math>S</math> are collinear. A ''windmill'' is a process that starts with a line <math>\ell</math> going through a single point <math>P \in S</math>. The line rotates clockwise about the pivot <math>P</math> until the first time that the line meets some other point <math>Q</math> belonging to <math>S</math>. This point <math>Q</math> takes over as the new pivot, and the line now rotates clockwise about <math>Q</math>, until it next meets a point of <math>S</math>. This process continues indefinitely.

: Show that we can choose a point <math>P</math> in <math>S</math> and a line <math>\ell</math> going through <math>P</math> such that the resulting windmill uses each point of <math>S</math> as a pivot infinitely many times.

== Observations and partial results ==

* None yet.

== Possible strategies ==

* None yet.

== Completed solutions ==

* None yet.

Deolalikar P vs NP paper

2010-08-10T12:35:11Z

Rweba: Standardized notation for FO(LFP) to reduce ambiguity

<B>Note: This is currently an UNOFFICIAL page on Deolalikar's P!=NP paper, and is not yet affiliated with a Polymath project.</B>

This is a clearinghouse wiki page for the analysis of Vinay Deolalikar's recent preprint claiming to prove that P != NP. Corrections and new contributions to this page are definitely welcome. Of course, any new material should be sourced whenever possible, and remain constructive and objectively neutral; in particular, personal subjective opinions are to be avoided. This page is derived from an [https://docs.google.com/document/edit?id=1uOa3BE7oK8Q7iEuOZ1EfkS16lF_Um1VwyMgdzrjZuT0&hl=en&authkey=COS65rkE earlier collaborative document] [http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing.html created by Suresh Venkatasubramanian].

For the latest discussion on the technical points of the paper, see [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/ this thread of Dick Lipton and Ken Regan]. For meta-discussion of this wiki (and other non-mathematical or meta-mathematical issues), see [http://geomblog.blogspot.com/2010/08/polymath-home-for-analysis-of.html this thread of Suresh Venkatasubramanian].

== The paper ==

* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/ Vinay Deolalikar's web page]
* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf First draft], Aug 6, 2010
* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf Second draft] Aug 9, 2010.

== Proof strategy ==

(Excerpted from [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4491 this comment of Ken Regan])

Deolalikar has constructed a vocabulary V which apparently obeys the following properties:

# Satisfiability of a k-CNF formula can be expressed by NP-queries over V—in particular, by an NP-query Q over V that ties in to algorithmic properties.
# All P-queries over V can be expressed by FO(LFP) formulas over V.
# NP = P implies Q is expressible by an FO(LFP) formula over V.
# If Q is expressible by an LFP formula over V, then by the algorithmic tie-in, we get a certain kind of polynomial-time LFP-based algorithm.
# Such an algorithm, however, contradicts known statistical properties of randomized k-SAT when k >= 9.

== Possible issues ==

=== Issues with LFP ===
There appear to be three issues related to the use of the characterization of P in terms of first order logic, an ordering and a least fixed point operator. All of these are discussed in the [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/ Lipton/Regan post], with contributions from David Barrington, Paul Christiano, Lance Fortnow, James Gate, and Arthur Milchior.

# Is the lack of ordering in the logical structures used to define the LFP structure a problem ? On the surface, it appears to be, since it is not known whether FO(LFP) can be used to characterize P without ordering.
# The paper requires that a certain predicate in the FO(LFP) formula be unary, and forces this by expanding neighborhoods and constructing k-tuples of parameters to act as single parameters. It is not clear how this affects the arguments about the propagation of local neighborhoods.
# Does the logical vocabulary created to express the LFP operation suffice to capture all P-time operations ?

=== Issues with random k-SAT ===

# '''Whether the "condensation" stage is significant''': the latest ideas from physics suggest that random <math>k</math>-SAT and similar CSPs don’t become hard at the clustering transition, but rather at the condensation transition where a subexponential number of clusters dominate the space of solutions. Graph coloring [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJ0-49M05RK-3&_user=10&_coverDate=09%2F30%2F2003&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=13eae49445b87797b1f90aa42e54b5a5 provides some evidence of this]. Moreover, random k-XORSAT has a clustering transition, frozen variables, etc., but is of course in P. ([http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4505 Cris Moore] and [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np#comment-4518 Alif Wahid])
# '''Whether the solution space is indeed complex''': The author tries to use the fact that for certain distributions of random k-SAT, the solution space has a "hard structure". Two problems:
## Polytime solvable problems (such as perfect matching on random graphs) can also have complicated solution distributions.
## There is a randomized reduction from SAT to formulas with at most ONE satisfying assignment ([http://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem Valiant-Vazirani]).

So either Valiant-Vazirani can't be derandomized or RP=NP (seems very unlikely!) or the proof must break (Ryan Williams, on [http://twitter.com/rrwilliams/status/20741046788 twitter])

=== Barriers ===

Any P vs NP proof must deal with the three known barriers described below. The concerns around this paper have not yet reached this stage yet.

==== Relativization ====

==== Natural proofs ====

==== Algebraization ====

== Terminology ==

* [http://en.wikipedia.org/wiki/Finite_model_theory Finite model theory]
* [[Immerman-Vardi theorem]]
* [[Least fixed point]] (LFP)
* [[Random k-SAT]]
* [[The complexity class NP]]
* [[The complexity class P]]

== Online reactions ==

=== Theory blogs ===

* [http://gregbaker.ca/blog/author/greg/ P ≠ NP], Greg Baker, Greg and Kat’s blog, August 7 2010
* [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ A proof that P is not equal to NP?], Richard Lipton, Godel's lost letter and P=NP, August 8 2010
* [http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing.html On the Deolalikar proof: Crowdsourcing the discussion ?], Suresh Venkatasubramanian, The Geomblog, August 9 2010
* [http://scottaaronson.com/blog/?p=456 Putting my money where my mouth isn’t], Scott Aaronson, Shtetl-Optimized, August 9 2010
* [http://blog.computationalcomplexity.org/2010/08/that-p-ne-np-proof-whats-up-with-that.html That P ne NP proof- whats up with that?], Bill Gasarch, Computational Complexity, August 9 2010
* [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/ Issues In The Proof That P≠NP], Richard Lipton and Ken Regan, Godel's lost letter and P=NP, August 9 2010
* [http://aeporreca.org/2010/08/09/proof-that-p-isnt-np/ A relatively serious proof that P != NP ?], Antonio E. Porreca, August 9 2010 (aggregates all the comments)
* [http://geomblog.blogspot.com/2010/08/polymath-home-for-analysis-of.html A 'polymath' home for analysis of the Deolalikar proof], Suresh Venkatasubramanian, The Geomblog, August 10 2010

=== Media and aggregators ===

* [http://news.ycombinator.com/item?id=1585850 P ≠ NP], Hacker News, August 8 2010
* [http://science.slashdot.org/story/10/08/08/226227/Claimed-Proof-That-P--NP Claimed Proof That P != NP], Slashdot, August 8 2010
* [http://www.aolnews.com/surge-desk/article/p-np-wtf-a-short-guide-to-understanding-vinay-deolalikars-mat/19586401 P=NP=WTF?: A Short Guide to Understanding Vinay Deolalikar's Mathematical Breakthrough], Dana Chivvis, AolNews, August 9 2010
* [http://www.pcworld.com/article/202950/hp_researcher_claims_to_crack_compsci_complexity_conundrum.html HP Researcher Claims to Crack Compsci Complexity Conundrum], Joab Jackson, IDG News, August 9 2010

=== Real-time searches ===

* [http://search.twitter.com/search?q=P%20NP Current Twitter search for "P NP"]

=== Other ===

* [http://twitter.com/fortnow/statuses/20673954168 Twitter], Lance Fortnow, August 8 2010
* [http://dabacon.org/pontiff/?p=4286 P<>NP?], Dave Bacon, The Quantum Pontiff, August 8 2010
* [http://www.daniel-lemire.com/blog/archives/2010/08/09/how-to-get-everyone-talking-about-your-research/ How to get everyone talking about your research], Daniel Lemire, August 9 2010
* [http://www.google.com/buzz/114134834346472219368/1vfSCPtRQZf/Vinay-Deolaikar-recently-released-a-102-page Google Buzz], Terence Tao, August 9 2010
* [http://www.schneier.com/blog/archives/2010/08/p_np_1.html P ≠ NP?], Bruce Schneier, Schneier on Security, August 9 2010.
* [http://blog.vixra.org/2010/08/09/vinay-deolalikar-says-p-%E2%89%A0-np/ Vinay Deolalikar says P ≠ NP], Philip Gibbs, vixra log, August 9 2010.

Additions to the above list of links are of course very welcome.

== Timeline ==

* August 6: Vinay Deolalikar sends out [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf his manuscript] to several experts in the field.
* August 7: Greg Baker [http://gregbaker.ca/blog/2010/08/07/p-n-np/ posts about the manuscript on his blog].
* August 8: The paper is noted on [http://news.ycombinator.com/item?id=1585850 Hacker News] and [http://science.slashdot.org/story/10/08/08/226227/Claimed-Proof-That-P--NP Slashdot], and [http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P%21%3DNP_paper#Theory_blogs discussed on many theoretical computer science blogs].
* August 9: A [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf second draft of the manuscript] is posted.
* August 9: Suresh Venkatasubramanian [http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing.html collects several technical comments on the paper] into a [https://docs.google.com/document/edit?id=1uOa3BE7oK8Q7iEuOZ1EfkS16lF_Um1VwyMgdzrjZuT0&hl=en&authkey=COS65rkE collaborative document].
* August 9: [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/ In a post of Dick Lipton and Ken Regan], several technical issues and concerns raised by various experts are discussed.
* August 10: Venkatasubramanian's document [http://geomblog.blogspot.com/2010/08/polymath-home-for-analysis-of.html is migrated over] to a [http://michaelnielsen.org/polymath1/index.php?title=Deolalikar's_P!%3DNP_paper wiki page].

== Bibliography ==

* [AM2003] D. Achlioptas, C. Moore, "[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJ0-49M05RK-3&_user=10&_coverDate=09%2F30%2F2003&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=13eae49445b87797b1f90aa42e54b5a5 Almost all graphs with average degree 4 are 3-colorable]", Journal of Computer and System Sciences 67, Issue 2, September 2003, Pages 441-471.
* [I1986] N. Immerman, "[http://www.cs.umass.edu/~immerman/pub/query.pdf Relational queries computable in polynomial time]", Information and Control 68 (1986), 86-104
* [VV1986] L. G. Valiant, V. V. Vazirani, "[http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf NP is as easy as detecting unique solutions]", Theoretical Computer Science (North-Holland) 47: 85–93 (1986). doi:10.1016/0304-3975(86)90135-0.
* [V1982] M. Vardi, Complexity of Relational Query Languages, 14th Symposium on Theory of Computation (1982), 137-146.

== Other links ==

* [http://en.wikipedia.org/wiki/P_%3D_NP_problem P versus NP problem] - Wikipedia
* [http://en.wikipedia.org/wiki/Vinay_Deolalikar Vinay Deolalikar] - Wikipedia
* [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/d/Deolalikar:Vinay.html Deolalikar publication list] - DBLP
* [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm Gerhard Woeginger’s P-versus-NP page]

Polymath1

2010-04-22T17:38:19Z

Rweba: /* Write-up repositories */ Pointer to April draft of "Low Dimensions" Project

== The Problem ==

Initially, the basic problem to be considered by the Polymath1 project was to explore a particular [http://gowers.wordpress.com/2009/02/01/a-combinatorial-approach-to-density-hales-jewett/ combinatorial approach] to the [[density Hales-Jewett theorem]] for k=3 (DHJ(3)), suggested by Tim Gowers. The [[Furstenberg-Katznelson argument|original proof of DHJ(3) used arguments from ergodic theory]]. Fairly soon, the scope of the project expanded and forked. Two projects emerged. The first project, "New Proof", had as its aim that of discovering any combinatorial argument for the theorem. The second project, "Low Dimensions", aimed to calculate precise bounds on density Hales-Jewett numbers and [[Moser's cube problem|Moser numbers]] for low dimensions n = 3, 4, 5, 6, 7, etc. Both projects appear to have been successful, and are in the writing-up stage.

==Write-up repositories==

[[TeX files for first paper|Write-up page for the "New Proof" project]]. The most recent draft is [http://www.cs.cmu.edu/~odonnell/papers/dhj.pdf here], tentatively titled "A new proof of the density Hales-Jewett theorem".

[[outline of second paper|Write-up page for the "Low Dimensions" project]]. The most recent draft is [http://terrytao.files.wordpress.com/2010/04/polymath.pdf here], tentatively titled "Density Hales-Jewett and Moser numbers in low dimensions".

==Basic definitions==

*[[line|Algebraic line]]

*[[line|Combinatorial line]]

*[[Combinatorial subspace]]

*[[corners|Corner]]

*[[Density]]

*[[line|Geometric line]]

*[[Slice]]

== Useful background materials ==

Here is [http://gowers.wordpress.com/2009/01/30/background-to-a-polymath-project/ some background to the project.] There is also a [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ general discussion on massively collaborative "polymath" projects.] This is [http://meta.wikimedia.org/wiki/File:MediaWikiRefCard.png a cheatsheet for editing the wiki.] Here is a [http://michaelnielsen.org/blog/?p=582 python script] which can help convert sizeable chunks of LaTeX into wiki-tex. Finally, here is the general [http://meta.wikimedia.org/wiki/Help:Contents Wiki user's guide].

== Threads and further problems==

* [http://gowers.wordpress.com/2009/01/27/is-massively-collaborative-mathematics-possible/ Is massively collaborative mathematics possible?] (inactive)
* (1-199) [http://gowers.wordpress.com/2009/02/01/a-combinatorial-approach-to-density-hales-jewett/ A combinatorial approach to density Hales-Jewett] (inactive)
* (200-299) [http://terrytao.wordpress.com/2009/02/05/upper-and-lower-bounds-for-the-density-hales-jewett-problem/ Upper and lower bounds for the density Hales-Jewett problem] (inactive)
* (300-399) [http://gowers.wordpress.com/2009/02/06/dhj-the-triangle-removal-approach/ The triangle-removal approach] (inactive)
* (400-499) [http://gowers.wordpress.com/2009/02/08/dhj-quasirandomness-and-obstructions-to-uniformity Quasirandomness and obstructions to uniformity] (inactive)
* (500-599) [http://gowers.wordpress.com/2009/02/13/dhj-possible-proof-strategies/#more-441/ Possible proof strategies] (inactive)
* (600-699) [http://terrytao.wordpress.com/2009/02/11/a-reading-seminar-on-density-hales-jewett/ A reading seminar on density Hales-Jewett] (inactive)
* (700-799) [http://terrytao.wordpress.com/2009/02/13/bounds-for-the-first-few-density-hales-jewett-numbers-and-related-quantities/ Bounds for the first few density Hales-Jewett numbers, and related quantities] (inactive)
* (800-849) [http://gowers.wordpress.com/2009/02/23/brief-review-of-polymath1/ Brief review of polymath1] (inactive)
* (850-899) [http://gowers.wordpress.com/2009/03/02/dhj3-851-899/ DHJ(3): 851-899] (inactive)
* (900-999) [http://terrytao.wordpress.com/2009/03/04/dhj3-900-999-density-hales-jewett-type-numbers/ DHJ(3): 900-999 (Density Hales-Jewett type numbers)] (inactive)
* (1000-1049) [http://gowers.wordpress.com/2009/03/10/problem-solved-probably/ Problem solved (probably)] (inactive)
* [http://gowers.wordpress.com/2009/03/10/polymath1-and-open-collaborative-mathematics/ Polymath1 and open collaborative mathematics] (inactive)
* (1050-1099) [http://gowers.wordpress.com/2009/03/16/dhj3-and-related-results-1050-1099/ DHJ(3) and related results: 1050-1099] (inactive)
* (1100-1199) [http://terrytao.wordpress.com/2009/03/14/dhj3-1100-1199-density-hales-jewett-type-numbers/ DHJ(3): 1100-1199 (Density Hales-Jewett type numbers)] (inactive)
*(discussion) [http://gilkalai.wordpress.com/2009/03/25/an-open-discussion-and-polls-around-roths-theorem/ An Open Discussion and Polls: Around Roth’s Theorem] (inactive)
* (1200-1299) [http://terrytao.wordpress.com/2009/03/30/dhjk-1200-1299-density-hales-jewett-type-numbers/ DHJ(k): 1200-1299 (Density Hales-Jewett type numbers)] (inactive)
* [http://terrytao.wordpress.com/2009/05/22/dhj-writing-the-second-paper/ DHJ: writing the second paper] (inactive)
* [http://terrytao.wordpress.com/2009/06/14/dhj-still-writing-the-second-paper/ DHJ: still writing the second paper] (inactive)
* [http://gowers.wordpress.com/2009/06/25/dhj-write-up-and-other-matters/ DHJ write-up and other matters] (inactive)
* [http://terrytao.wordpress.com/2009/07/09/dhj-writing-the-second-paper-iii/ DHJ: writing the second paper III.] (inactive)
* [http://terrytao.wordpress.com/2010/01/15/density-hales-jewett-and-moser-numbers-nearing-the-final-draft DHJ and Moser numbers: nearing the final draft.] ('''active''')

[http://blogsearch.google.com/blogsearch?hl=en&ie=UTF-8&q=polymath1&btnG=Search+Blogs Here is a further list of blog posts related to the Polymath1 project]. [http://en.wordpress.com/tag/polymath1/ Here is wordpress's list].

A spreadsheet containing the latest upper and lower bounds for <math>c_n</math> can be found [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg here]. Here are the proofs of our [[upper and lower bounds]] for these constants, as well as the [[higher-dimensional DHJ numbers|counterparts for higher k]].

We are also collecting bounds for [[Fujimura's problem]], motivated by a [[hyper-optimistic conjecture]]. We are additionally investigating [[higher-dimensional Fujimura]].

There is also a chance that we will be able to improve the known bounds on [[Moser's cube problem]] or the [[Kakeya problem]].

Here are some [[unsolved problems]] arising from the above threads.

Here is a [[tidy problem page]].

== Proof strategies ==

It is natural to look for strategies based on one of the following:

* [[Szemerédi's original proof of Szemerédi's theorem]].
* [[Szemerédi's combinatorial proof of Roth's theorem]].
* [[Ajtai-Szemerédi's proof of the corners theorem]].
* The [[density increment method]].
* The [[triangle removal lemma]].
* [[Ergodic-inspired methods]].
* The [[Furstenberg-Katznelson argument]].
* Use of [[equal-slices measure]].

== Related theorems ==

* [[Carlson's theorem]].
* The [[Carlson-Simpson theorem]].
* [[Folkman's theorem]].
* The [[Graham-Rothschild theorem]].
* The colouring [[Hales-Jewett theorem]].
* The [[Kruskal-Katona theorem]].
* [[Roth's theorem]].
* The [[IP-Szemerédi theorem]].
* [[Sperner's theorem]].
* [[Szemerédi's regularity lemma]].
* [[Szemerédi's theorem]].
* The [[triangle removal lemma]].

All these theorems are worth knowing. The most immediately relevant are Roth's theorem, Sperner's theorem, Szemerédi's regularity lemma and the triangle removal lemma, but some of the others could well come into play as well.

==Important concepts related to possible proofs==

* [[Complexity of a set]]
* [[Concentration of measure]]
* [[Influence of variables]]
* [[Obstructions to uniformity]]
* [[Quasirandomness]]

==Complete proofs or detailed sketches of potentially useful results==

*[[Sperner's theorem|The multidimensional Sperner theorem]]
*[[Line-free sets correlate locally with complexity-1 sets]]
*[[Correlation with a 1-set implies correlation with a subspace]] (Superseded)
*[[Fourier-analytic_proof_of_Sperner|A Fourier-analytic proof of Sperner's theorem]]
*[[A second Fourier decomposition related to Sperner's theorem]]
*[[A Hilbert space lemma]]
*A [[Modification of the Ajtai-Szemerédi argument]]
*An [[abstract regularity lemma]]
*[[A general result about density increments]]

==Attempts at proofs of DHJ(3)==

*[[An outline of a density-increment argument]] (ultimately didn't work)
*[[A second outline of a density-increment argument]] (seems to be OK but more checking needed)
*[[Proof of DHJ(3) via density-increment|Another outline of the whole argument]] (attempts to be more detailed)
*[[Furstenberg-Katznelson argument]] (very sketchy)
*[[Austin's proof]] (very sketchy)
*[[Austin's proof II]] (mostly complete, though more explanation and motivation needed)
*A [[timeline]] of some of the progress on the "New Proof" project.

==Generalizing to DHJ(k)==

*[[DHJ(k) implies multidimensional DHJ(k)]]
*[[Line free sets correlate locally with dense sets of complexity k-2]]
*[[A general partitioning principle]]

== Bibliography ==

Here is a [[Bibliography]] of relevant papers in the field.

== How to help out ==

There are a number of ways that even casual participants can help contribute to the Polymath1 project:

* Expand the [[bibliography]]
* Join the [http://gowers.wordpress.com/2009/03/10/polymath1-and-open-collaborative-mathematics metadiscussion thread]
* Join the [http://gilkalai.wordpress.com/2009/03/25/an-open-discussion-and-polls-around-roths-theorem open discussion] thread (about these mathematical problems; not about the open collaboration), and participate in the polls.
* Add some more Ramsey theorems to this wiki; one could hope to flesh out this wiki into a Ramsey theory resource at some point.
* Suggest a logo for this wiki!
* Suggest a way to speed up our [[genetic algorithm]]
* Point out places where the exposition could be improved
* Jump in to the technical discussion; find some nice new angles to the discussed problems.
* Add to this list

== End notes ==

[["New Proof" grant acknowledgments]]

[["Low Dimensions" grant acknowledgments]]

Finding primes

2009-08-01T21:43:44Z

Rweba: Added survey by Granville on Cramer Conjecture

This is the main blog page for the "[http://en.wordpress.com/tag/finding-primes/ Deterministic way to find primes]" project, which is currently fairly active already, and should be formally launched within a few weeks.

The main aim of the project is as follows:

:'''Problem'''. Find a ''deterministic'' algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in k. You may assume as many standard conjectures in number theory (e.g. the generalised Riemann hypothesis) as necessary, but avoid powerful conjectures in complexity theory (e.g. P=BPP) if possible.

Here is the [http://polymathprojects.org/2009/07/27/proposal-deterministic-way-to-find-primes/ proposal for the project], which is also the ''de facto'' research thread for that project. Here is the [http://polymathprojects.org/2009/07/28/deterministic-way-to-find-primes-discussion-thread/ discussion thread for the project].

Please add and develop this wiki; in order to maximise participation in the project when it launches, we will need as much expository material on this project as we can manage.

== Partial results ==

# [[P=NP implies a deterministic algorithm to find primes]]
# [[An efficient algorithm exists if Cramer's conjecture holds]]
# Problem is true if strong pseudorandom number generators exist (explain!)
# k-digit primes can be found with high probability using O(k) random bits (explain!)
# The function field analogue (i.e. finding degree k irreducible polynomials over a finite field) is known (see Adelman-Lenstra)

== Easier versions of the problem ==

# Subexponential time rather than polynomial
## Equivalently, find primes with superlogarithmically many digits (<math> \gg \log k</math>) in poly(k) time
# Find k-digit primes using o(k) random bits
# Assume complexity conjectures such as P=BPP, P=BQP, etc.
# Can one find a degree k irreducible polynomial over the rationals deterministically and quickly?

== Variants of the problem ==

# Can one derandomise factoring of polynomials over finite fields? Note that if one could do this even in the quadratic case, this would allow for efficient location of quadratic non-residues, which is not known.

== Observations and strategies ==

# If factoring is easy, then it would suffice to show that every polylog(N)-length interval in [N,2N] contains a number which is not <math>N^\varepsilon</math>-smooth. One way to start approaching this sort of problem is to take iterated product sets of sets of medium sized primes and show that they spread out to fill all short intervals in [N,2N].
## One can combine this with the "W-trick". For instance, if one lets W be the product of all the primes less than k, and if one can show that not every element of the progression <math>\{ Wn+1: 1 \leq n \leq k^{100} \}</math> (say) is <math>k^A</math>-smooth, then one has found a prime with at least <math>A \log k</math> digits in polynomial time. Can one make A arbitrarily large?
# If a primality test can be expressed as a constant-degree polynomial over a finite field from the digits of the number-under-test to {0,1}, then known [http://en.wikipedia.org/wiki/Pseudorandom_generators_for_polynomials pseudorandom generators for polynomials] can be used to derandomize finding primes the same way as under the full P=BPP assumption. So, instead of requiring a general PRG, the proposal is trying to put the primality test into a fully derandomizable subclass of P.

== Relevant concepts ==

# Complexity classes
## [[The complexity class P|P]]
## [[The complexity class NP|NP]]
## [[The complexity class BPP|BPP]]
## [[The complexity class promise-BPP|promise-BPP]]
## [[The complexity class BQP|BQP]]
## [[The complexity class DTIME|DTIME(f(n))]]
# [[Pseudo-random generators (PRG)]]
# Expander graphs
# Cramer's random model for the primes
# Prime gaps
# Smooth number
# The W-trick

== Relevant conjectures ==

# P=NP
# P=BPP
# P=promise-BPP
# P=BQP
# existence of PRG
# existence of one-way functions
# whether DTIME(2^n) has subexponential circuits
# GRH
# the Hardy-Littlewood prime tuples conjecture
# the ABC conjecture
# Cramer’s conjecture
# discrete log in P
# factoring in P.

(These conjectures should have their own links at some point.)

== Relevant results ==

# Brun-Titchmarsh inequality
# Erdos-Kac theorem
# Bertrand's postulate ("For every positive integer N, there is a prime between N and 2N" : it gives determinism, but not a polynomial algorithm.)

== Relevant papers ==

# Adelman, Lenstra, "Finding irreducible polynomials over finite fields"
# R. C. Baker and G. Harman, “The difference between consecutive primes,” Proc. Lond. Math. Soc., series 3, 72 (1996) 261–280.
# P. Dusart, [http://www.unilim.fr/laco/theses/1998/T1998_01.html Autour de la fonction qui compte le nombre de nombres premiers]
# O. Goldreich, A. Wigderson, [http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GW02/gw02.pdf Derandomization that is rarely wrong from short advice that is typically good]
#A. Granville, [http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf "Harald Cramér and the distribution of prime numbers"], Scandinavian Actuarial J. 1 (1995), 12—28.
# R. Impagliazzo, A. Wigderson, P = BPP unless E has sub-exponential circuits. In Proceedings of the 29th ACM Symposium on Theory of Computing, pages 220–229, 1997.
# K. Soundararajan, [http://arxiv.org/abs/math/0606408 The distribution of the primes] (survey)
# L. Trevisan, [http://arxiv.org/abs/cs.CC/0601100 Pseudorandomness and Combinatorial Constructions]

== External links ==

# [http://qwiki.stanford.edu/wiki/Complexity_Zoo Complexity Zoo]

Talk:Finding primes

2009-07-31T19:52:14Z

Rweba: Removing all content from page

User talk:Rweba

2009-07-29T22:12:00Z

Rweba: I bet no one checks these pages

I don't honestly imagine I'll be checking this page regularly, but whatever... --[[User:Rweba|Rweba]] 22:12, 29 July 2009 (UTC)

User:Rweba

2009-07-29T22:09:55Z

Rweba: Intro

I am a computer scientist by profession, but I like to try and dabble in a few different things (with decidedly mixed results in general).

Talk:Finding primes

2009-07-29T22:07:06Z

Rweba: Impagliazzo

It appears that Impagliazzo and Wigderson have co-written a number of papers, many of them dealing with derandomization. I couldn't figure out at a quick glance which paper(s) were most relevant. [[User:Rweba|Rweba]] 22:07, 29 July 2009 (UTC)

Finding primes

2009-07-29T22:01:24Z

Rweba: Fixed spelling of "Impagliazzo"

This is the main blog page for the "[http://en.wordpress.com/tag/finding-primes/ Deterministic way to find primes]" project, which will be started in within a few weeks.

The main aim of the project is as follows:

:'''Problem'''. Find a ''deterministic'' algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in k. You may assume as many standard conjectures in number theory (e.g. the generalised Riemann hypothesis) as necessary, but avoid powerful conjectures in complexity theory (e.g. P=BPP) if possible.

Here is the [http://polymathprojects.org/2009/07/27/proposal-deterministic-way-to-find-primes/ proposal for the project], which is also the ''de facto'' research thread for that project. Here is the [http://polymathprojects.org/2009/07/28/deterministic-way-to-find-primes-discussion-thread/ discussion thread for the project].

Please add and develop this wiki; in order to maximise participation in the project when it launches, we will need as much expository material on this project as we can manage.

== Partial results ==

# [[P=NP implies a deterministic algorithm to find primes]]
# Problem is true if Cramer's conjecture holds (explain!)
# Problem is true if strong pseudorandom number generators exist (explain!)
# k-digit primes can be found with high probability using O(k) random bits (explain!)

== Easier versions of the problem ==

# Subexponential time rather than polynomial
## Equivalently, find primes with superlogarithmically many digits (<math> \gg \log k</math>) in poly(k) time
# Find k-digit primes using o(k) random bits
# Assume complexity conjectures such as P=BPP, P=BQP, etc.

== Relevant concepts ==

# Complexity classes
## [[The complexity class P|P]]
## [[The complexity class NP|NP]]
## [[The complexity class BPP|BPP]]
## [[The complexity class promise-BPP|promise-BPP]]
## [[The complexity class BQP|BQP]]
## [[The complexity class DTIME|DTIME(f(n))]]
# [[Pseudo-random generators (PRG)]]
# Expander graphs
# Cramer's random model for the primes
# Prime gaps

== Relevant conjectures ==

# P=NP
# P=BPP
# P=promise-BPP
# P=BQP
# existence of PRG
# existence of one-way functions
# whether DTIME(2^n) has subexponential circuits
# GRH
# the Hardy-Littlewood prime tuples conjecture
# the ABC conjecture
# Cramer’s conjecture
# discrete log in P
# factoring in P.

(These conjectures should have their own links at some point.)

== Relevant papers ==

# Impagliazzo-Wigderson (reference?)
# O. Goldreich, A. Wigderson, [http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GW02/gw02.pdf Derandomization that is rarely wrong from short advice that is typically good]
# K. Soundararajan, [http://arxiv.org/abs/math/0606408 The distribution of the primes] (survey)

== External links ==

# [http://qwiki.stanford.edu/wiki/Complexity_Zoo Complexity Zoo]

Imo 2009 q6

2009-07-23T07:16:39Z

Rweba: Fixed Latex error

The International Mathematical Olympiad (IMO) consists of a set of six problems, to be solved in two sessions of four and a half hours each. Traditionally, the last problem (Problem 6) is significantly harder than the others. Problem 6 of the 2009 IMO, which was given out on July 16, reads as follows:

:'''Problem 6'''. Let <math>a_1, a_2, \ldots, a_n</math> be distinct positive integers and let M be a set of <math>n-1</math> positive integers not containing <math>s = a_1 +a_2 +\ldots+a_n</math>. A grasshopper is to jump along the real axis, starting at the point 0 and making n jumps to the right with lengths <math>a_1, a_2, \ldots , a_n</math> in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in M.

A collaborative effort to study this problem was formed [http://terrytao.wordpress.com/2009/07/20/imo-2009-q6-as-a-mini-polymath-project/ here], and continued [http://terrytao.wordpress.com/2009/07/21/imo-2009-q6-mini-polymath-project-cont/ here].

This page is a repository for any text related to this project, for instance proofs of this problem.

== Notation ==

Elements of M will be referred to as "landmines".

We say that an integer m can be ''safely reached in k steps'' if there exist distinct <math>b_1,\ldots,b_k \in \{a_1,\ldots,a_n\}</math> such that <math>m = b_1+\ldots+b_k</math> and if none of the partial sums <math>b_1+\ldots+b_i</math> for <math>1 \leq i \leq k </math> is a landmine. Thus, our objective is to show that one can safely reach <math>a_1+\ldots+a_n</math> in n steps.

In proof 2 I have used 'mines'. I refer to the possibilities for the grasshopper as leaps, and to the actual components of a path through the minefield as jumps. So the longest leap can be the first or second or third jump (etc). I refer to an unmined space as a 'clear space'. Please feel free to suggest better terms/edit for consistency.

== Proof #1 ==

We induct on n, assuming that <math>n \geq 3</math> and that the claim has already been proven for smaller n.

Observe that if one can pass k or more mines safely in k steps for some <math>k \geq 1</math>, then we are done by induction hypothesis (removing the steps <math>b_1,\ldots,b_k</math> from <math>a_1,\ldots,a_n</math>, and shifting the remaining mines leftwards by <math>b_1+\ldots+b_k</math>, reducing n by k, and adding dummy mines if necessary. Thus we may assume that it is not possible to pass k or more mines safely in k steps for any <math>k \geq 1</math>. We will refer to this assumption as '''Assumption A'''.

For each <math>1 \leq j \leq n</math>, let <math>S_j</math> denote the set of integers formed by summing j distinct elements from <math>a_1,\ldots,a_n</math>. Thus for instance <math>S_1 = \{a_1,\ldots,a_n\}</math>, <math>S_2 = \{a_i+a_{i'}: 1 \leq i < i' \leq n</math>, and <math>S_n = \{a_1+\ldots+a_n\}</math>.

We say that the grasshopper is ''immune to order j'' for some <math>1 \leq j \leq n</math> if for every distinct <math>b_1,\ldots,b_{j'}</math> in <math>\{a_1,\ldots,a_n\}</math> with <math>1 \leq j' \leq j</math> and <math>b_1+\ldots+b_{j'} \not \in M</math>, the grasshopper can safely reach <math>b_1+\ldots+b_{j'}</math> in j' steps, using a permutation of <math>b_1,\ldots,b_{j'}</math>. In particular this implies that every integer in <math>S_j \backslash M</math> can be safely reached in j steps. Clearly the grasshopper is immune to order 1; it will suffice to show that the grasshopper is immune to order n.

We use induction. Let <math>1 \leq j < n</math>, and suppose that the grasshopper is already known to be immune to order 1. We now show that it is immune to order j+1.

First suppose that <math>M \cap S_j</math> has cardinality at most j. Then the claim is easy, because to reach <math>b_1+\ldots+b_{j+1} \in S_{j+1} \backslash M</math> in j+1 steps using a permutation of <math>b_1+\ldots+b_{j+1}</math>, there are j+1 points in <math>S_j</math> that one could potentially use. At most j of these lie in M, so there is one that does not lie in M. By induction hypothesis, the grasshopper can reach that point safely in j steps, and can thus reach the original point in j+1 steps, as required.

Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1. Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps. In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.

Let I be the set of all <math>1 \leq i \leq n-j</math> such that <math>a_i+a_{n-j+1}+\ldots+a_n</math> is not in M. Since <math>M \cap S_j</math> already uses up at least j+1 of the points in M, I cannot be empty. For each i in I, <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> must lie in M, otherwise we could safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps by Assumption A. Similarly, if i is the smallest element of I, <math>a_i+a_{n-j+1}+\ldots+a_n - a_m</math> must lie in M for any m equal to either i or n-j+1,...,n-1. But this forces M to contain n distinct elements, a contradiction.

== Proof #2 ==

This is a version of Brumm’s proof with inspiration from Curioso.
It is another induction, assuming we can deal with n-1 mines in n leaps, and extending to the case with n mines and n+1 leaps.
This is an attempt at a write-up with minimal technicality - it is therefore a little wordy.
The basic strategy is to try to make the longest leap and see what might go wrong.
It turns out that there are two things.

First, we might not jump any mines at all (but perhaps landing on a mine), so our inductive hypothesis has to deal with too many mines.
In fact we can deal with all but one of the mines. We start from the far end and trace a path backwards, keeping the longest leap in reserve, and knowing that all the mines are in the range of the remaining leaps, because we didn't jump any with the longest leap. We can arrange for the mine we can't pass to be the one the one closest to the beginning and then swap in the longest leap to make sure we can jump this one as well.

Second, we might land on a mine and jump some too. The mines we jump might get in the way of shorter leaps.
It turns out that we can always find two leaps, with the longest leap as the second jump, taking us beyond at least two mines and the induction goes through.

'''PROOF'''

We can trivially negotiate zero mines with one leap (the case n=1).

We assume that, provided the last place is clear, that we can deal with (n-1) or fewer mines in n leaps, and we want to show that we can deal with n mines in (n+1) leaps.

We try to make the longest leap.

Case 1: If the longest leap carries us to a clear space (no mine) and jumps at least one mine, we are left with n leaps and at most (n-1) mines, which we can do by hypothesis.

Case 2: If the longest leap carries us to a clear space, but doesn’t jump a mine, we work from the other end of the minefield. If we remove the mine closest to the beginning we have (n-1) mines left, and we know that we can negotiate all of these with the n leaps other than the largest (we ignore the blank spaces covered by the largest leap at the beginning).

Case 2.1: If this arrangement also avoids the mine we removed, we are done.

Case 2.2: If it doesn’t – working from the far end – take the leap which lands on this mine, and replace it by the longest leap, which is longer, and therefore jumps us clear of the mine. There are no mines closer to the beginning than this, so we use any remaining leaps to take us to the beginning and we have a path through.

Case 3: If the longest leap lands on a mine but doesn’t jump any mines, this is similar to case 2.2 – this mine is the closest one to the beginning. We can find a path from the far end which lands only on this mine (by hypothesis - jumping the remaining n-1 mines with n leaps). We look at the leap which takes us there, and swap it with the longest leap to jump clear of it, while the swapped leap takes us to the beginning, and we have our path.

Case 4: In this case the longest leap lands on a mine and jumps one or more mines.
Following brumm’s notation, assume the longest leap jumps f of the mines, with f at least 1.
We have accounted for f+1 mines (including the one we landed on). So there are (n-f-1) mines out of range of the longest leap.
Observe that there are n other possible leaps from the beginning, all different and shorter than the longest leap, and there are at most f mines in this range to hit, so there are at least (n-f) possible initial leaps which don’t hit a mine.
For each of those (n-f) possible first leaps, try following with the longest leap, which definitely takes us beyond the first f+1 mines. This gives us (n-f) double jumps of different lengths, but there are just (n-f-1) mines we might hit, so one of these double jumps lands clear.
This double jump passes at least two mines. So the remaining (n-1) jumps are available to negotiate at most (n-2) mines, and we are done.

== Proof #3 ==

(Insert proof here)

Imo 2009 q6

2009-07-23T07:09:40Z

Rweba: Fixed a very minor typo

The International Mathematical Olympiad (IMO) consists of a set of six problems, to be solved in two sessions of four and a half hours each. Traditionally, the last problem (Problem 6) is significantly harder than the others. Problem 6 of the 2009 IMO, which was given out on July 16, reads as follows:

:'''Problem 6'''. Let <math>a_1, a_2, \ldots, a_n</math> be distinct positive integers and let M be a set of <math>n-1</math> positive integers not containing <math>s = a_1 +a_2 +\ldots+a_n</math>. A grasshopper is to jump along the real axis, starting at the point 0 and making n jumps to the right with lengths <math>a_1, a_2, \ldots , a_n</math> in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in M.

A collaborative effort to study this problem was formed [http://terrytao.wordpress.com/2009/07/20/imo-2009-q6-as-a-mini-polymath-project/ here], and continued [http://terrytao.wordpress.com/2009/07/21/imo-2009-q6-mini-polymath-project-cont/ here].

This page is a repository for any text related to this project, for instance proofs of this problem.

== Notation ==

Elements of M will be referred to as "landmines".

We say that an integer m can be ''safely reached in k steps'' if there exist distinct <math>b_1,\ldots,b_k \in \{a_1,\ldots,a_n\}</math> such that <math>m = b_1+\ldots+b_k</math> and if none of the partial sums <math>b_1+\ldots+b_i</math> for <math>1 \leq i \leq k </math> is a landmine. Thus, our objective is to show that one can safely reach <math>a_1+\ldots+a_n</math> in n steps.

In proof 2 I have used 'mines'. I refer to the possibilities for the grasshopper as leaps, and to the actual components of a path through the minefield as jumps. So the longest leap can be the first or second or third jump (etc). I refer to an unmined space as a 'clear space'. Please feel free to suggest better terms/edit for consistency.

== Proof #1 ==

We induct on n, assuming that <math>latex n > 2 </math> and that the claim has already been proven for smaller n.

Observe that if one can pass k or more mines safely in k steps for some <math>k \geq 1</math>, then we are done by induction hypothesis (removing the steps <math>b_1,\ldots,b_k</math> from <math>a_1,\ldots,a_n</math>, and shifting the remaining mines leftwards by <math>b_1+\ldots+b_k</math>, reducing n by k, and adding dummy mines if necessary. Thus we may assume that it is not possible to pass k or more mines safely in k steps for any <math>k \geq 1</math>. We will refer to this assumption as '''Assumption A'''.

For each <math>1 \leq j \leq n</math>, let <math>S_j</math> denote the set of integers formed by summing j distinct elements from <math>a_1,\ldots,a_n</math>. Thus for instance <math>S_1 = \{a_1,\ldots,a_n\}</math>, <math>S_2 = \{a_i+a_{i'}: 1 \leq i < i' \leq n</math>, and <math>S_n = \{a_1+\ldots+a_n\}</math>.

We say that the grasshopper is ''immune to order j'' for some <math>1 \leq j \leq n</math> if for every distinct <math>b_1,\ldots,b_{j'}</math> in <math>\{a_1,\ldots,a_n\}</math> with <math>1 \leq j' \leq j</math> and <math>b_1+\ldots+b_{j'} \not \in M</math>, the grasshopper can safely reach <math>b_1+\ldots+b_{j'}</math> in j' steps, using a permutation of <math>b_1,\ldots,b_{j'}</math>. In particular this implies that every integer in <math>S_j \backslash M</math> can be safely reached in j steps. Clearly the grasshopper is immune to order 1; it will suffice to show that the grasshopper is immune to order n.

We use induction. Let <math>1 \leq j < n</math>, and suppose that the grasshopper is already known to be immune to order 1. We now show that it is immune to order j+1.

First suppose that <math>M \cap S_j</math> has cardinality at most j. Then the claim is easy, because to reach <math>b_1+\ldots+b_{j+1} \in S_{j+1} \backslash M</math> in j+1 steps using a permutation of <math>b_1+\ldots+b_{j+1}</math>, there are j+1 points in <math>S_j</math> that one could potentially use. At most j of these lie in M, so there is one that does not lie in M. By induction hypothesis, the grasshopper can reach that point safely in j steps, and can thus reach the original point in j+1 steps, as required.

Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1. Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps. In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.

Let I be the set of all <math>1 \leq i \leq n-j</math> such that <math>a_i+a_{n-j+1}+\ldots+a_n</math> is not in M. Since <math>M \cap S_j</math> already uses up at least j+1 of the points in M, I cannot be empty. For each i in I, <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> must lie in M, otherwise we could safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps by Assumption A. Similarly, if i is the smallest element of I, <math>a_i+a_{n-j+1}+\ldots+a_n - a_m</math> must lie in M for any m equal to either i or n-j+1,...,n-1. But this forces M to contain n distinct elements, a contradiction.

== Proof #2 ==

This is a version of Brumm’s proof with inspiration from Curioso.
It is another induction, assuming we can deal with n-1 mines in n leaps, and extending to the case with n mines and n+1 leaps.
This is an attempt at a write-up with minimal technicality - it is therefore a little wordy.
The basic strategy is to try to make the longest leap and see what might go wrong.
It turns out that there are two things.

First, we might not jump any mines at all (but perhaps landing on a mine), so our inductive hypothesis has to deal with too many mines.
In fact we can deal with all but one of the mines. We start from the far end and trace a path backwards, keeping the longest leap in reserve, and knowing that all the mines are in the range of the remaining leaps, because we didn't jump any with the longest leap. We can arrange for the mine we can't pass to be the one the one closest to the beginning and then swap in the longest leap to make sure we can jump this one as well.

Second, we might land on a mine and jump some too. The mines we jump might get in the way of shorter leaps.
It turns out that we can always find two leaps, with the longest leap as the second jump, taking us beyond at least two mines and the induction goes through.

'''PROOF'''

We can trivially negotiate zero mines with one leap (the case n=1).

We assume that, provided the last place is clear, that we can deal with (n-1) or fewer mines in n leaps, and we want to show that we can deal with n mines in (n+1) leaps.

We try to make the longest leap.

Case 1: If the longest leap carries us to a clear space (no mine) and jumps at least one mine, we are left with n leaps and at most (n-1) mines, which we can do by hypothesis.

Case 2: If the longest leap carries us to a clear space, but doesn’t jump a mine, we work from the other end of the minefield. If we remove the mine closest to the beginning we have (n-1) mines left, and we know that we can negotiate all of these with the n leaps other than the largest (we ignore the blank spaces covered by the largest leap at the beginning).

Case 2.1: If this arrangement also avoids the mine we removed, we are done.

Case 2.2: If it doesn’t – working from the far end – take the leap which lands on this mine, and replace it by the longest leap, which is longer, and therefore jumps us clear of the mine. There are no mines closer to the beginning than this, so we use any remaining leaps to take us to the beginning and we have a path through.

Case 3: If the longest leap lands on a mine but doesn’t jump any mines, this is similar to case 2.2 – this mine is the closest one to the beginning. We can find a path from the far end which lands only on this mine (by hypothesis - jumping the remaining n-1 mines with n leaps). We look at the leap which takes us there, and swap it with the longest leap to jump clear of it, while the swapped leap takes us to the beginning, and we have our path.

Case 4: In this case the longest leap lands on a mine and jumps one or more mines.
Following brumm’s notation, assume the longest leap jumps f of the mines, with f at least 1.
We have accounted for f+1 mines (including the one we landed on). So there are (n-f-1) mines out of range of the longest leap.
Observe that there are n other possible leaps from the beginning, all different and shorter than the longest leap, and there are at most f mines in this range to hit, so there are at least (n-f) possible initial leaps which don’t hit a mine.
For each of those (n-f) possible first leaps, try following with the longest leap, which definitely takes us beyond the first f+1 mines. This gives us (n-f) double jumps of different lengths, but there are just (n-f-1) mines we might hit, so one of these double jumps lands clear.
This double jump passes at least two mines. So the remaining (n-1) jumps are available to negotiate at most (n-2) mines, and we are done.

== Proof #3 ==

(Insert proof here)