{"id":"741d978d-1e59-4f93-9fb7-0f8db7502fcd","arxiv_id":"1908.07106","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For an n by n sliding-tile puzzle on a torus, the total variation mixing time is at least order n^4 and at most n^4 log n, with a single tile converging to Brownian motion at an exact rate.","lead":"This paper solves a long-standing problem about how many random moves it takes to scramble a sliding-tile puzzle on a torus. The answer is on the order of n^4 moves, with a single tile's position converging to Brownian motion.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 22's uniform characteristic function bound, not Lemma 14, is the load-bearing step for Theorem 1; its two-sentence proof leaves the local limit theorem's truncation unsupported.","rationale":"The reader selected Lemma 14's Mathematica-computed return probabilities as the weakest assumption, and the paper indeed leaves that computation under-derived. However, an independent potential-theory check shows the stated values are consistent with the known potential kernel a(1,0)=1 and the harmonic relations for a(1,1) and a(2,0), so a mistake in Lemma 14, while it would change c_puz, is not the most serious threat. Lemma 22 is more load-bearing: it is the uniform characteristic function estimate that makes the Fourier truncation in Theorem 27 work, and its proof is only a sketch. Without it, the single-tile Brownian limit itself is unsupported, not merely its constant. The paper's overall strategy remains plausible and the flagged gaps are fillable, so the reader's CONDITIONAL verdict is appropriate. I see no reason to change the verdict, only to redirect attention from Lemma 14 to Lemma 22 as the step that most needs a complete proof.","tokens_in":41340,"tokens_out":16019,"duration_ms":165126,"concrete_test":"Use the exact finite-n formula for chi(xi1,xi2) in Lemma 23 (Eq. 104) to compute 1-|chi| numerically over n = 10,...,200 and a fine grid in (xi1,xi2), checking whether 1-|chi| >= c max(xi1^2/n^2, xi2^2) holds with a universal constant c. Since the bound is claimed uniformly in n, a single violation would settle the concern; if none is found, the remaining task is an analytic re-derivation of Lemma 22 from the spectral decomposition of P' in Lemmas 18-19, which is what the current two-sentence proof omits.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that a single piece converges to Brownian motion at time c_puz n^4 t rests on the local limit theorem (Theorem 27) for the renewal sums S_N. The Fourier inversion step truncates frequencies using two bounds: the uniform quadratic bound |χ| <= 1 - c max(xi1^2/n^2, xi2^2) in Lemma 22 and the sharper Lemma 25 bound. Lemma 22 is proved in only two sentences: it invokes paths of bounded length or fixed displacement with positive probability and asserts their phase variation has the given magnitude. That does not establish a uniform quadratic lower bound for 1-|χ|, since one needs cancellation among many paths, not just existence of one path, and the claim is especially delicate for xi2 near 1/2 and for xi1 near 0 where the phase scale is small. If Lemma 22 fails in any frequency regime, the truncation error in Theorem 27 is uncontrolled and Theorem 1 lacks a proof. By contrast, Lemma 14's Mathematica black-box computation is independently checkable: the potential kernel value a(1,0)=1 and the harmonic relations give a(1,1)=4/pi and a(2,0)=4-8/pi, which reproduce the stated return probabilities; this is an exposition gap, not a correctness risk. Lemma 42's sketch affects the O(n^4 log n) upper bound, which is less central. Thus the most load-bearing unresolved step is Lemma 22, and a rigorous proof should be supplied before the exact Brownian constant is accepted.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims to solve Diaconis' '15 puzzle problem' for the n x n puzzle on the torus with lazy random moves. Theorem 1 asserts that a single labeled piece converges in total variation, at time c_puz n^4 t with c_puz = (5/2)(π - 1), to the corresponding Brownian motion limit, uniformly on compact time intervals. Theorem 2 states that after n^4 f(n) steps with f(n) -> infinity, the number of fixed points converges to Poisson(1), while this convergence fails if f is bounded; Corollary 3 concludes there is no total variation cutoff for this statistic. Theorem 4 gives an O(n^4 log n) total variation mixing time upper bound for the full puzzle, and Theorem 5 states an O(n^4 log n) expected coupling time for the empty square and any fixed number of labeled pieces. The main technical ingredients are a renewal description of a tracked piece's motion, a local limit theorem for renewal sums (Theorem 27), spectral comparison arguments, and a comparison with the 3-cycle walk for the upper bound.","tokens_in":41607,"tokens_out":3011,"duration_ms":34869,"significance":"If the proofs can be completed, the paper resolves a long-standing problem of Diaconis and establishes a sharp, parameter-free Brownian constant c_puz for the single-piece mixing. The Poisson fixed-point result and the absence of cutoff for that statistic are natural and interesting consequences, and the coupling theorem and spectral comparison framework provide tools for further study. The derivation of the constant is not circular: it is obtained from limiting return probabilities of the empty square rather than fitted to the target Brownian distance. The paper also presents a new renewal/local-limit method for this type of constrained random walk on the symmetric group. These strengths make the paper a potentially significant contribution to the probability literature, provided the under-derived technical estimates are supplied.","major_comments":[{"comment":"The uniform bound |chi(xi1, xi2)| <= 1 - c max(xi1^2/n^2, xi2^2) is the load-bearing estimate for the truncation step in Theorem 27, and hence for the exact Brownian constant in Theorem 1. The proof is only two sentences: it invokes paths of bounded length or fixed displacement with positive probability and asserts that their phase variation has the given magnitude. That argument establishes, at best, that a single path has phase close to 1 in some regimes; it does not prove a uniform quadratic lower bound for 1 - |chi|, which requires controlling cancellation among many paths. The claim is especially delicate for xi2 near 1/2 and for xi1 near 0, where the phase scale is small relative to the stated quadratic bound. The authors should provide a rigorous derivation of Lemma 22, or replace it with a proved estimate that supports the frequency truncation in Theorem 27.","section":"§5, Lemma 14 (Eq. (53))"},{"comment":"The limiting return probabilities p_(1,0) = 1/2, p_(0,±1) = 1/2 - 1/pi, and p_(-1,0) = 2/pi - 1/2 are stated after 'The exact values were calculated in Mathematica,' with no derivation shown. These values enter Lemma 21 and determine the constant c_puz = (5/2)(pi - 1) in Theorem 1. The values are checkable from the potential kernel and harmonic relations, but the reader should not be expected to trust a black-box computation at a load-bearing point of the proof. Please include an analytic derivation, or at least a complete and reproducible calculation, of the Green-function limits G_(1,0), G_(1,1), and G_(2,0) used in equations (60).","section":"§9, Lemma 42"},{"comment":"The proof of Lemma 42, which claims the d2 mixing time of the measure mu_S is O(n^2 log n), is only a sketch. In the one-dimensional representation case, the assertion that the spectrum is 'mixed in O(n^2 log n) steps' is stated without a quantitative argument covering the O(n^2) such representations. For higher-dimensional representations, the claim that an arbitrary factor n^2 in multiplicity can be saved by increasing the constant in the n^2 log n mixing time requires a justification, since the Plancherel sum includes multiplicities and the spectral gaps are only known up to constants. This lemma supports Theorem 4, so a complete proof should be supplied.","section":"§6, Theorem 27"},{"comment":"In the contour-shift step between equations (117) and (118), the horizontal integral is dismissed as bounded by O_A(n^{-A}) without a demonstration. The shift moves the integration contour by i(t - 2N mu_n)/(2 N^{1/2} v_n), and the resulting horizontal contribution is controlled only if the Gaussian factor decays uniformly in the summation range and in the error region; this decay is not shown. Since Theorem 27 is the main local limit theorem used in the proof of Theorem 1, this estimate should be stated and proved explicitly.","section":"§6, Theorem 27"}],"minor_comments":[{"comment":"The notation in the lemma statement is garbled: 'let py,n,y P tp 1, 0q, p´1, 0q, p0, 1q, p0, ´1qu' should read 'let p_{y,n}, y in {...},' and the subscript typesetting throughout Section 5 should be cleaned up.","section":"§8, Lemma 39"},{"comment":"The proof of Lemma 39 is very brief and uses an 'auxilliary step' that is not precisely defined. Since the lemma is used to justify the Gaussian approximation in Lemmas 40 and 41, please spell out the construction and the induction more carefully.","section":"§8, Lemma 40"},{"comment":"In the proof of Lemma 40, the notation 'D d_m' in display (172) is unclear; it should be D^d_m or a similar indexed family. The same issue appears in the induction argument in Lemma 41. This is a presentation issue, but it makes already dense arguments harder to check.","section":"§1, Abstract"},{"comment":"The abstract contains the typo 'annˆ n numbered grid'; please correct to 'an n x n numbered grid'.","section":"§1, Introduction"},{"comment":"The related-work paragraph cites the authors' earlier paper [15], but that paper does not appear to be used in the proofs. If it is not needed, this is fine; if it is intended to motivate the renewal technique, a sentence clarifying the connection would help.","section":"§6, Proof of Theorem 1"},{"comment":"The upper-bound part of the proof states that 'convolution with the remaining distributions can only decrease the total variation distance, as can removing the conditioning.' This is not immediate for the conditional distribution described, and a brief justification or reference would improve the exposition.","section":"§8, Deduction of Theorem 2"}],"recommendation":"major_revision","confidential_remarks":"This is a strong and significant paper, and the main architecture of the proof is plausible and non-circular: the Brownian constant is derived from return probabilities and renewal-theoretic quantities rather than fitted to the target result. However, the referee report above identifies several under-derived estimates, most importantly Lemma 22, which is load-bearing for the exact constant in Theorem 1. These gaps appear fixable within the manuscript's scope, so I recommend major revision rather than rejection. The authors should be asked to supply complete proofs for Lemma 22, Lemma 14, Lemma 42, and the contour-shift estimate in Theorem 27 before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bob,\n\nThis paper claims to solve Diaconis's 15-puzzle problem on the torus: a single tile mixes at time c_puz n^4 with c_puz = (5/2)(π−1), the whole board mixes in at least order n^4 and at most O(n^4 log n), and the fixed-point statistic is Poisson(1) after n^4 f(n) steps. If the proof holds, it is a big deal: the renewal-process decomposition and the local limit theorem are genuinely new, and the constant is derived from first principles, not fitted.\n\nThe overall architecture is credible. The reduction to a random walk on S_{n^2−1} ⋉ (Z/nZ)^2 is clean; the single-tile renewal construction is natural; the comparison to the 3-cycle walk for the upper bound is standard. The Poisson fixed-point theorem is a nice bonus, and the proof via mixed moments and comparison to a symmetrized chain is inventive.\n\nNow the soft spots. The reader's worry about Lemma 14 is misplaced: the Mathematica values are independently checkable against the potential kernel (a(1,1)=4/π, a(2,0)=4−8/π give exactly the stated return probabilities), so that is just an omitted calculation. The real load-bearing gap is Lemma 22, the uniform quadratic lower bound for the characteristic function of the renewal increments. The proof is two sentences about 'paths of bounded length' and 'variation in their phase.' That does not establish the required cancellation, especially in the delicate regimes ξ2 near 1/2 and ξ1 near 0. Theorem 27's truncation relies on this bound, so without a real proof of Lemma 22, Theorem 1 lacks support. This is fixable, but it is exactly the step a referee must verify before accepting the sharp constant.\n\nThe upper bound also depends on a sketch (Lemma 42) for the d2 mixing time of the 3-cycle plus torus walk, but that step is less central and the argument is plausible.\n\nBottom line: if you work in Markov chain mixing, this is worth reading and worth refereeing. I would not cite the sharp constant yet, but I would send it to a strong journal and ask for a rigorous proof of Lemma 22 and a fuller write-up of Lemma 42. It deserves a serious referee, not a desk reject.","headline":"A serious, novel attack on Diaconis's 15-puzzle problem that likely gets the n^4 order right, but the sharp Brownian constant rests on a two-sentence characteristic-function bound (Lemma 22) that needs a real proof.","tokens_in":42144,"tokens_out":3326,"would_cite":false,"duration_ms":34006,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60B15","60J35","20B20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes that the generalized 15 puzzle on an $n\\times n$ torus mixes in order $n^4$ steps, with a single tile's position converging to Brownian motion on the torus at time $c_{\\mathrm{puz}} n^4 t$ for…","keywords":["15 puzzle","mixing time","random walk on a group","Markov chain","Dirichlet form","Poisson approximation","cut-off phenomenon","Brownian motion on a torus"],"falsifier":"Compute the limiting return probabilities in Lemma 14 by evaluating the $\\mathbb{Z}^2$ lattice Green's functions $G_{1,0}$, $G_{1,1}$, and $G_{2,0}$ symbolically or to high precision; if the limits are not $\\frac12$, $\\frac12-\\frac1\\pi$, and $\\frac2\\pi-\\frac12$, then $c_{\\mathrm{puz}}$ changes, although the $n^4$ order would remain.","tokens_in":41102,"feed_emoji":"🧩","tokens_out":8732,"duration_ms":75648,"temperature":0.7,"pith_summary":"This paper solves the 15-puzzle problem for an $n\\times n$ board with periodic boundary conditions and random moves: how many slides does it take to randomize the board? The answer is order $n^4$ steps. Tracking a single marked tile, the proof shows that its position after $c_{\\mathrm{puz}}n^4 t$ steps has total variation distance to uniformity converging to that of Brownian motion on the flat torus run for time $t$, with $c_{\\mathrm{puz}}=\\frac52(\\pi-1)$. It also shows that after $n^4 f(n)$ steps with $f(n)\\to\\infty$, the number of tiles still in their original positions converges to a $\\mathrm{Poisson}(1)$ law, matching a uniformly random permutation. A corollary is that this fixed-point statistic has no cut-off, while the full board mixes in at most $O(n^4\\log n)$ steps.","feed_headline":"Random 15-puzzle mixes in order n^4 moves","feed_subtitle":"A single tile converges to torus Brownian motion with sharp constant (5/2)(π−1).","key_machinery":"The load-bearing object is the renewal process of a marked tile: stopping times $t_i$ alternate between the empty square swapping with the tile from left or right and from above or below, with $H_i$ and $V_i$ the tile's horizontal and vertical displacements in those intervals and $r_i$, $s_i$ the elapsed times. The key identity is Lemma 21, which computes the limiting variance $s^2$ and mean time $\\mu$ from the four directional return probabilities of Lemma 14, giving $c_{\\mathrm{puz}}=2\\mu/s^2=\\frac52(\\pi-1)$. The characteristic function of a single burst is expressed exactly as a resolvent formula (Lemma 23), then expanded at low frequencies; the resulting local limit theorem (Theorem 27) turns the renewal process into the Brownian $\\theta$ kernel $\\theta_t$. For several pieces, the mechanism shifts to a comparison of Dirichlet forms between the original puzzle, a symmetrized chain with overlapping pieces, and an abelian random walk with independent coordinates (Theorem 9), which yields the $d^2$ mixing bound $O(n^4)$.","core_discovery":"The central discovery is that the mixing of a single tile in the $n^2-1$ puzzle reduces to a renewal process with a Brownian scaling limit. The tile moves only when the empty square is adjacent to it, and between such moves the empty square performs lazy simple random walk on the torus; the tile's displacement accumulates in alternating horizontal and vertical bursts. A local limit theorem for the triple (horizontal displacement, vertical displacement, elapsed time) of these bursts shows that the elapsed-time fluctuations are absorbed into the Brownian clock. Consequently the total variation distance of the tile at time $c_{\\mathrm{puz}} n^4 t$ tends to $d_{\\mathrm{Br}}(t)$, the total variation distance of Brownian motion on $(\\mathbb{R}/\\mathbb{Z})^2$, uniformly for $t$ in compact sets. For the whole board, the same renewal structure yields Poisson(1) fixed points after $n^4 f(n)$ steps and, via comparison with a 3-cycle walk, an upper bound of $O(n^4\\log n)$.","pith_inferences":["The renewal-and-local-limit structure should transfer to other 'moving-hole' walks, such as higher-dimensional grids or rectangular boards, where only the return-probability calculation changes.","The Poisson(1) fixed-point result suggests the induced permutation is locally uniform on low-complexity representations already at order $n^4$; a further test would be whether the full board's mixing time can be sharpened from $O(n^4\\log n)$ to $O(n^4)$.","One could probe the sharp constant empirically by simulating small boards and comparing the single-tile distance to $d_{\\mathrm{Br}}(c_{\\mathrm{puz}}^{-1} t)$ at times $c_{\\mathrm{puz}} n^4 t$; a mismatch would pinpoint the return-probability calculation as the fragile step."],"forward_implications":["A single tile in an $n\\times n$ puzzle needs order $n^4$ moves to mix: at time $c_{\\mathrm{puz}} n^4 t$ its distance to uniformity approaches that of torus Brownian motion at time $t$.","After $n^4 f(n)$ random moves with $f(n)\\to\\infty$, the number of tiles in their original positions converges to $\\mathrm{Poisson}(1)$; if $f(n)$ stays bounded, this convergence fails.","The fixed-point statistic shows no cut-off phenomenon: mixing happens gradually over order $n^4$ steps.","The full board's total-variation and $\\epsilon/|G|$-$\\ell^\\infty$ mixing time is $O(n^4\\log n)$.","For each fixed $d$, the empty square and any $d$ labeled pieces can be coupled with their stationary copies in expected time $O(n^4\\log n)$."],"supporting_citations":[{"why":"Poses the 15-puzzle mixing problem and the representation-theoretic framework for measuring mixing.","marker":"[5]"},{"why":"Supplies the 3-cycle spectral gap and mixing-time estimate used to prove the $O(n^4\\log n)$ upper bound.","marker":"[14]"},{"why":"Provides the comparison theorem for reversible chains that transfers eigenvalue estimates between chains.","marker":"[8]"},{"why":"Gives the group comparison technique relating $d^2$, $\\ell^\\infty$, and total-variation mixing times.","marker":"[7]"},{"why":"Supplies the Markov-chain background, hitting-time estimates, and the coupling bound used throughout.","marker":"[18]"}],"fun_headline_variants":["15-puzzle mixing time proven to be n^4","Random 15-puzzle: n^4 moves to mix","Solving Diaconis' 15-puzzle: n^4 mixing time","Tile mixing in 15-puzzle: n^4 without cutoff","15-puzzle mixes in n^4 moves, no cutoff"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The sharp constant $\\frac52(\\pi-1)$ rests on four directional return probabilities in Lemma 14—stated as $\\frac12$, $\\frac12-\\frac1\\pi$, $\\frac2\\pi-\\frac12$ with only a computer-algebra calculation as support—being exactly correct.","fun_headline_variants_meta":{"raw":{"variants":["15-puzzle mixing time proven to be n^4","Random 15-puzzle: n^4 moves to mix","Solving Diaconis' 15-puzzle: n^4 mixing time","Tile mixing in 15-puzzle: n^4 without cutoff","15-puzzle mixes in n^4 moves, no cutoff"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000216,"raw_usage":{"total_tokens":1412,"prompt_tokens":903,"completion_tokens":509,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":519,"completion_tokens_details":{"reasoning_tokens":420}},"tokens_in":519,"tokens_out":509,"duration_ms":4944,"temperature":1.0,"reasoning_tokens":420,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:29:08.366481+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the limiting return probabilities in Lemma 14 by evaluating the $\\mathbb{Z}^2$ lattice Green's functions $G_{1,0}$, $G_{1,1}$, and $G_{2,0}$ symbolically or to high precision; if the limits are not $\\frac12$, $\\frac12-\\frac1\\pi$, and $\\frac2\\pi-\\frac12$, then $c_{\\mathrm{puz}}$ changes, although the $n^4$ order would remain.","supporting_citations":[{"cited_title":"Group representations in probability and statistics","cited_arxiv_id":null,"evidence_quote":"Poses the 15-puzzle mixing problem and the representation-theoretic framework for measuring mixing."},{"cited_title":"Random generators of the symmetric group: diameter, mixing time and spectral gap","cited_arxiv_id":null,"evidence_quote":"Supplies the 3-cycle spectral gap and mixing-time estimate used to prove the $O(n^4\\log n)$ upper bound."},{"cited_title":"Comparison theore ms for reversible Markov chains","cited_arxiv_id":null,"evidence_quote":"Provides the comparison theorem for reversible chains that transfers eigenvalue estimates between chains."},{"cited_title":"Comparison techniq ues for random walk on finite groups","cited_arxiv_id":null,"evidence_quote":"Gives the group comparison technique relating $d^2$, $\\ell^\\infty$, and total-variation mixing times."},{"cited_title":"Peres, and E.L","cited_arxiv_id":null,"evidence_quote":"Supplies the Markov-chain background, hitting-time estimates, and the coupling bound used throughout."}],"review_version":1}