{"id":"ec9479b1-7724-48dc-bddd-d9a2e99597d7","arxiv_id":"2506.01634","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Random Minesweeper on an n-cell grid is whp solvable in linear time when p = o(n^{-1/6}) and whp unsolvable by any algorithm when p >> n^{-1/6}.","lead":"Randomly generated Minesweeper boards have a phase transition: when the mine density is below about n^{-1/6}, a linear-time method solves the board almost always; above it, no algorithm can do better than a coin flip. The paper proves this by isolating the two smallest ambiguous patterns that force a guess.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4 is the load-bearing gap: the unsolvability half of Theorem 1 depends on an unproved assertion that k occurrences of P1/P2 give k independent 50/50 guesses, and the paper gives no argument for independence or disjointness.","rationale":"The reader identified Lemma 4 as the weakest assumption, and my reading agrees. The central claim of the paper is a phase transition, with two halves. The lower half (solvability below the threshold) is supported by a plausible finite classification in Proposition 3 together with standard probabilistic estimates. The upper half (unsolvability above the threshold) and the critical-window upper bound both pass through Lemma 4. Since Lemma 4 is stated without proof, the paper currently does not certify the main theorem. I do not see a clear counterexample to the lemma, and the pattern definition may well enforce the necessary separation; but the lemma is not a corollary of the surrounding results, and the conditional independence of occurrences is the main missing step. The Section 4.4 sketch and the k << n applicability when p is bounded away from 1 are secondary issues that would also need attention, but neither is as load-bearing as Lemma 4. A concrete finite check such as enumerating occurrence overlaps and computing posterior hypothesis counts would settle whether the lemma is merely unproved or actually false as stated. Since the likely fix is to supply the missing proof or to select a separated subcollection of occurrences, the reader's CONDITIONAL verdict remains appropriate rather than REJECT or ACCEPT.","tokens_in":8434,"tokens_out":20448,"duration_ms":229447,"concrete_test":"Enumerate all translations of P1 and P2 on a 16x16 window and check whether any two occurrences have intersecting envelopes. If an intersecting pair exists, compute the number of mine assignments consistent with the revealed clues for that pair; if it is less than 2^k, Lemma 4 is false as stated and the upper bound must be reconstructed using only separated occurrences. If no such pair exists, prove the separation property from the two-cell safe margin in the pattern definition, then complete Lemma 4 by coupling each separated occurrence to an independent fair coin and verifying that the posterior is exactly 1/2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The upper bound in Theorem 1 (both above criticality and at criticality) rests on Lemma 4, stated in Section 3 without proof and used in Sections 4.2 and 4.4. Proposition 3 only classifies the smallest ambiguous patterns; it does not imply Lemma 4. Lemma 4 needs the additional and stronger fact that each occurrence of P1/P2 contributes an independent binary choice with posterior 1/2. The paper gives no argument for either the posterior or the independence. In particular, occurrences are defined as subgrid matches and are not required to be disjoint; if two occurrences can have overlapping envelopes, the conditional distribution given 'at least k occurrences' may have fewer than k independent degrees of freedom, and the bound 2^{-k}+o(1) could fail as stated. The critical-window section is itself only a sketch and explicitly leaves details as an exercise, but the essential missing bridge is Lemma 4. Even if a counterexample cannot be found, the lemma is currently an assertion, not a proof, so the main theorem is not fully established as written. The rest of the proof, including Proposition 3 and the island bounds, is plausible and largely routine once Lemma 4 is supplied.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the random Minesweeper instance M_{n,p} on an n-cell rectangular grid with independent mines of probability p. The main result, Theorem 1, claims a coarse phase transition at p=Theta(n^{-1/6}): below this scale a linear-time algorithm solves the instance with high probability, above this scale no algorithm succeeds with high probability, and at the critical scale the optimal success probability is bounded away from both 0 and 1. The strategy is to identify the smallest ambiguous patterns, P1 and P2, each using 6 mines, then to show that their appearance forces a random binary choice that no algorithm can resolve. The paper also contains a random-process version in which mines are added one by one, with a claimed hitting-time property and almost-sure monotonicity.","tokens_in":8690,"tokens_out":7017,"duration_ms":78373,"significance":"If the proofs are completed, the result is a clean and interesting phase-transition theorem for a non-monotone random discrete structure. The threshold exponent n^{-1/6} arises naturally from the size of the smallest ambiguous patterns, and the paper gives a constructive linear-time algorithm below the threshold. The classification of minimal ambiguous patterns in Proposition 3 is a substantial finite-case analysis, and the additional process-level results in Section 5 are appealing. The main obstacle is that the key unsolvability lemma, Lemma 4, is stated without proof, and the critical-window section is only sketched. These are load-bearing for Theorem 1, so the central claim is not yet fully established as written.","major_comments":[{"comment":"Lemma 4 is the central bridge from the appearance of ambiguous patterns to unsolvability, but no proof is provided. The lemma asserts that conditionally on at least k << n occurrences of P1 and P2, every algorithm succeeds with probability at most 2^{-k}+o(1). This is used in Sections 4.2 and 4.4 to obtain the upper bounds in Theorem 1. Proposition 3 only classifies the smallest ambiguous patterns; it does not imply that each occurrence contributes an independent fair binary choice. Moreover, occurrences are defined as subgrid matches and are not required to be disjoint, so overlapping occurrences could share hidden cells and reduce the number of independent degrees of freedom. Please supply a complete proof of Lemma 4, or replace it with a lemma that applies to the disjoint occurrences produced by Lemma 14 and prove that lemma in detail.","section":"Section 3, Lemma 4"},{"comment":"The critical-window case, which is the third bullet of Theorem 1, is only sketched and the details are explicitly left as an exercise. This is a load-bearing part of the main theorem and cannot be deferred. In particular, the Poisson approximation via the Stein-Chen method requires a precise dependency-graph argument; the lower bound epsilon in Theorem 1 is not explicitly derived; and the application of Lemma 4 at criticality, where the number of occurrences is typically bounded, needs a careful error analysis. Please write out the full proof of Section 4.4.","section":"Section 4.4"},{"comment":"The upper-bound arguments in both the supercritical and critical regimes rest entirely on Lemma 4. Since Lemma 4 is unproved, the unsolvability half of Theorem 1 does not follow from the current manuscript. The proof needs to establish, at minimum, that the occurrences counted by Lemma 14 are causally independent in the sense of the game: revealing cells in one occurrence cannot provide information about the hidden cells of another occurrence, and the posterior probability of each occurrence is 1/2. This should be stated and proved explicitly.","section":"Section 4.2 and Section 4.4"}],"minor_comments":[{"comment":"The proof of Proposition 5 is left as an exercise to the reader. Since this proposition is a stated result, please include the proof or a reference, or rephrase it as a remark without proof.","section":"Section 5, Proposition 5"},{"comment":"The asymptotic notation 'p << n^{-1/k}' is used throughout but never defined. Please define it precisely, for instance as p n^{1/k} -> 0.","section":"Section 2"},{"comment":"In the critical window, the statement 'the expected number of occurrences of P1 (resp. P2) is c^6 + o(1)' should be justified by an explicit computation including the (1-p)^{58} factor and the number of possible positions; this is standard but should be written out.","section":"Section 4.4"},{"comment":"Theorem 15 is said to be a direct consequence of Proposition 16 and the reasoning of Section 4.3, but the implication is not fully spelled out. In particular, one should argue that if no island contains more than 6 mines and no occurrence of P1 or P2 is present, then every ambiguous pattern is absent, so the algorithm of Section 4.3 succeeds. Please add this argument.","section":"Section 5.1"},{"comment":"The phrase 'All steps are pairwise independent' is unclear; the steps are exchangeable but not pairwise independent in the usual sense. Please rephrase to describe the process correctly.","section":"Section 5, process definition"}],"recommendation":"major_revision","confidential_remarks":"The manuscript addresses a natural and timely question, and the overall strategy is credible. The missing proof of Lemma 4 is a serious gap, but it appears fixable within the scope of the paper, and the rest of the argument is plausible. I therefore recommend major revision rather than rejection. The paper fits the scope of math.PR and should be reconsidered after the gaps are filled."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Louf proves something genuinely new: a coarse phase transition for solvability of random Minesweeper, at p around n^{-1/6}. The direction is right and the main ideas are visible. The classification of the two minimal ambiguous patterns (Proposition 3) is a real piece of work, and the envelope lemmas are clever. The linear-time algorithm below threshold is clean, as is the island decomposition. The hitting-time result in Section 5 is a nice bonus.\n\nBut the paper is not complete. The unsolvability half of Theorem 1 rests on Lemma 4, which asserts that k occurrences of P1/P2 force any algorithm to succeed with probability at most 2^{-k}+o(1). This is stated without proof. It needs at least two things: a proof that each occurrence gives a binary choice whose posterior is 1/2, and an argument that multiple occurrences give independent choices—especially since occurrences are subgrid matches and are not required to be disjoint. Without a precise statement and proof of Lemma 4, the upper bound in Theorem 1 is not established. The stress-test note is right about this.\n\nThe other soft spot is Section 4.4. The critical window is the most delicate part, and the paper explicitly leaves the details 'as an exercise'. The Stein-Chen Poisson approximation and the conditioning argument need to be written out. That is fixable, but it is not a minor typo.\n\nOne concern the reader raised does not actually land: the claim that Lemmas 12/13 are applied outside their stated range. At criticality the paper applies them with k=7, and p ~ c n^{-1/6} is indeed o(n^{-1/7}), so the condition is satisfied. That part is fine.\n\nWho is this for? Anyone working on random discrete structures and thresholds. The result is important enough that the referee process should see it, but the current version is far from publishable as is. I would ask for a full proof of Lemma 4, a written-out critical-window argument, and a careful statement about overlap of occurrences. If those are supplied, it should be a strong paper.\n\nMy recommendation: send to peer review, with a clear expectation of major revision.","headline":"First rigorous coarse phase transition for Minesweeper solvability, with a credible strategy but a load-bearing unproved lemma (Lemma 4) that must be fixed before the main theorem is established.","tokens_in":9175,"tokens_out":2449,"would_cite":false,"duration_ms":24969,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60C05","05C80","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Random Minesweeper has a coarse phase transition at mine probability $\\Theta(n^{-1/6})$: below it a linear-time algorithm wins with high probability, above it no algorithm wins.","keywords":["phase transition","Minesweeper","random discrete structures","ambiguous patterns","linear time algorithm","solvability","random mine process","coarse threshold"],"falsifier":"Simulate $M_{n,p}$ at $p=c n^{-1/6}$ for several fixed values of $c$ and large $n$: count occurrences of $P_1$ and $P_2$ and measure the success probability of the best known inference strategy. If the success probability does not approach $\\exp(-2c^6)$ below the pattern threshold and $1-(1-\\exp(-2c^6))/2$ above it, the Poisson approximation or the independence assumption in Lemma 4 would be contradicted.","tokens_in":8219,"feed_emoji":"💣","tokens_out":8608,"duration_ms":80155,"temperature":0.7,"pith_summary":"This paper proves that a random Minesweeper board, where each of $n$ cells is a mine independently with probability $p$, changes from solvable to unsolvable at the threshold $p=\\Theta(n^{-1/6})$. Below the threshold, a simple linear-time strategy solves the board with high probability; above it, every algorithm has success probability $o(1)$. The transition is neither sharp nor monotone, but it is driven by the emergence of the two smallest ambiguous patterns, each of which forces a genuine $50/50$ guess. At the critical scale $p\\sim c n^{-1/6}$, the best success probability is bounded between $\\varepsilon$ and $1-\\varepsilon$ for every fixed $c$.","feed_headline":"Random Minesweeper turns unsolvable above mine density n^{-1/6}","feed_subtitle":"Below that threshold a linear-time strategy almost surely wins; above it, every algorithm almost surely loses.","key_machinery":"The load-bearing objects are the two smallest ambiguous patterns $P_1$ and $P_2$: six-mine configurations whose revealed grid state $S_{\\min}$ contains a hidden cell that is a mine in one pattern and empty in the other, so the best possible play is an unbiased guess. Proposition 3 proves, via an envelope analysis of ambiguous grid states, that these are the only ambiguous patterns with six or fewer mines. Lemma 4 then converts many disjoint occurrences of $P_1$ or $P_2$ into an upper bound of $2^{-k}+o(1)$ on any algorithm's success probability, and Lemma 14 shows that above the threshold the board contains $\\Theta(n p^6)$ such occurrences with high probability. Below the threshold, Lemma 13 ensures every island of revealed nonzero cells is small enough that the smallest-pattern classification applies, yielding the linear-time solving algorithm.","core_discovery":"The paper's central claim is Theorem 1: for the random mine assignment $M_{n,p}$, if $p=o(n^{-1/6})$ there exists a linear-time algorithm that solves $M_{n,p}$ with high probability; if $p \\gg n^{-1/6}$, then $\\max_A \\mathbb{P}(A \\text{ solves } M_{n,p}) = o(1)$; and if $p\\sim c n^{-1/6}$, the maximal success probability lies between $\\varepsilon$ and $1-\\varepsilon$. The proof identifies the two smallest ambiguous patterns, $P_1$ and $P_2$, each with six mines, and shows they are the only ambiguous patterns with six or fewer mines. Below threshold these patterns almost never appear, so an island-by-island inference algorithm succeeds; above threshold they appear many times, and each occurrence acts as an unavoidable $50/50$ coin flip that no algorithm can eliminate. At criticality their number converges to a Poisson distribution with mean $c^6$, giving the coarse transition window.","pith_inferences":["If the same envelope classification could be pushed to patterns with more mines, the threshold exponent might generalise: a puzzle whose smallest ambiguity has $k$ mines would plausibly transition at $p=\\Theta(n^{-1/k})$.","A direct numerical test is to simulate $M_{n,p}$ at $p=c n^{-1/6}$ and compare the observed failure probability with $1-\\exp(-2c^6)$, the prediction obtained by counting occurrences of $P_1$ and $P_2$ as independent Poisson variables.","The almost-sure monotonicity proven in the random process suggests that, although solvability is not a monotone property, it is monotone enough that local ambiguous patterns may be the only obstruction; that intuition, if formalised, would connect the result to sharp-threshold theorems for monotone properties.","The paper leaves open the characterisation of larger ambiguous patterns; any enumeration of such patterns could sharpen the critical window or reveal additional transitions below the main threshold."],"forward_implications":["For mine densities well below $n^{-1/6}$, random Minesweeper is computationally easy: the paper supplies an explicit linear-time algorithm that succeeds with high probability.","For densities well above $n^{-1/6}$, no algorithm, however clever, can win with more than $o(1)$ probability, so the ambiguity is intrinsic to the random instance rather than a limitation of a particular strategy.","In the critical window $p\\sim c n^{-1/6}$, the success probability is bounded away from both $0$ and $1$, showing the phase transition is coarse rather than sharp.","In the random process where mines are added one at a time, non-solvability coincides with the first appearance of $P_1$ or $P_2$, and once such a pattern appears it is almost surely never destroyed before $n/2$ mines are placed."],"supporting_citations":[{"why":"Supplies the experimentally observed phase transition in Minesweeper that the paper proves rigorously.","marker":"[2]"},{"why":"Provides the Poisson approximation for weakly dependent occurrences used to analyse the critical window.","marker":"[1]"},{"why":"Gives the monotone-property phase-transition framework that motivates the coarse-transition statement and the focus on local constraints.","marker":"[3]"}],"fun_headline_variants":["Minesweeper hits unsolvability at n^{-1/6} mine density","Critical density found for Minesweeper solvability","Minesweeper's tipping point: density n^{-1/6}","Random Minesweeper fails when mines exceed n^{-1/6}","Solvable below n^{-1/6}, unsolvable above"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The upper bound above the threshold rests on Lemma 4, which assumes that many separated copies of the two smallest ambiguous patterns act as independent $50/50$ guesses, so that any algorithm's success probability is at most $2^{-k}+o(1)$; the paper states this lemma without a proof.","fun_headline_variants_meta":{"raw":{"variants":["Minesweeper hits unsolvability at n^{-1/6} mine density","Critical density found for Minesweeper solvability","Minesweeper's tipping point: density n^{-1/6}","Random Minesweeper fails when mines exceed n^{-1/6}","Solvable below n^{-1/6}, unsolvable above"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000612,"raw_usage":{"total_tokens":2760,"prompt_tokens":773,"completion_tokens":1987,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":389,"completion_tokens_details":{"reasoning_tokens":1891}},"tokens_in":389,"tokens_out":1987,"duration_ms":14722,"temperature":1.0,"reasoning_tokens":1891,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:37:44.031814+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate $M_{n,p}$ at $p=c n^{-1/6}$ for several fixed values of $c$ and large $n$: count occurrences of $P_1$ and $P_2$ and measure the success probability of the best known inference strategy. If the success probability does not approach $\\exp(-2c^6)$ below the pattern threshold and $1-(1-\\exp(-2c^6))/2$ above it, the Poisson approximation or the independence assumption in Lemma 4 would be contradicted.","supporting_citations":[{"cited_title":"A phase transition in Minesweeper","cited_arxiv_id":null,"evidence_quote":"Supplies the experimentally observed phase transition in Minesweeper that the paper proves rigorously."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Poisson approximation for weakly dependent occurrences used to analyse the critical window."},{"cited_title":"Sharp thresholds of graph properties, and thek-SAT problem (with an appendix by Jean Bourgain).J","cited_arxiv_id":null,"evidence_quote":"Gives the monotone-property phase-transition framework that motivates the coarse-transition statement and the focus on local constraints."}],"review_version":1}