Pith. sign in

REVIEW 3 major objections 4 minor 27 references

A walk on max-plus algebra

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read In a max-plus walk, the sum over lattice positions of the state-decision-matrix eigenvalues is conserved exactly when the local coin satisfies $a+d=0$ and $b+c=0$, and the conserved sum is always zero.

desk verdict A real new model and a mostly survivable conservation theorem, but Theorem 5.1 is false as stated; worth a careful referee, not acceptance. read the letter →

arxiv 1908.09051 v2 pith:VDY3J7QY submitted 2019-08-23 math-ph math.MP

Sennosuke Watanabe , Akiko Fukuda , Etsuo Segawa , Iwao Sato This is my paper · ORCID
classification math-phmath.MP MSC 15A8005C50
keywords max-plusalgebraquantumwalkstatedecisionmatrixconservedquantityultradiscretizationtropicaleigenvaluespectrumdirectedgraph
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Max-plus algebra replaces ordinary addition and multiplication by taking the maximum and adding, and this paper transplants the one-dimensional quantum walk into that setting. The resulting 'max-plus walk' has an explicit path-sum formula for the matrix that carries a state from time 0 to position $k$ at time $n$, and that matrix turns out to be exactly the ultradiscretization of the known quantum-walk amplitude. The paper's central result is a conservation law: the sum over all positions $k$ of the max-plus eigenvalues of these state-decision matrices does not change with time $n$ if and only if the walk's local coin entries satisfy $a+d=0$ and $b+c=0$, and in that case the conserved sum is identically zero. This condition plays the role that unitarity of the coin plays for the quantum walk's $\ell^2$-norm conservation. The paper further shows that under this condition the whole-system time-evolution operator has spectrum $\{0\}$ with a spatially linear eigenvector, a far simpler spectral picture than the continuous unit-circle spectrum of the quantum walk.

What carries the argument

The load-bearing tool is the max-plus eigenvalue of a $2\times 2$ matrix, read off its weighted digraph: for $A=\begin{pmatrix} p & q \\ r & s \end{pmatrix}$ the eigenvalue is the maximum circuit mean $\max\{p, s, (q+r)/2\}$, and with the state decision matrix $A_k^n$ this yields the closed form $\lambda(A_k^n)=\ell a+md+\min\{\ell, m, (\ell+m-1)/2\}\Delta$ for $\Delta=(b+c)-(a+d)\ge 0$ (and $\ell a+md+\Delta/2$ for $\Delta<0$). Summing this formula over $k$ and requiring time-independence forces $\Delta=0$ and $a+d=0$, which is exactly assumption (A); the same circuit-mean viewpoint, applied to the infinite matrix $A$ whose weighted digraph has maximum circuit mean $0$, produces the spectral claim $\sigma(A)=\{0\}$.

What would settle it

Take $a=d=0$, $b=c=1$ (so $\Delta=2\ge 0$), and look at $n=2$, $k=0$, where $\ell=m=1$. The direct path sum $Q\otimes P \oplus P\otimes Q$ is $\begin{pmatrix}2 & 1 \\ 1 & 2\end{pmatrix}$ in max-plus, whose eigenvalue is $2$; the paper's formula gives $0+0+\min\{1,1,1/2\}\cdot 2 = 1$. A reader who finds this discrepancy in the balanced case has falsified the eigenvalue identity on which the conservation criterion's proof depends.

Watch

Extended reading notes

Core claim

The paper establishes Theorem 4.1 as its main discovery: for the max-plus walk with local coin $P\oplus Q$, where $P=\begin{pmatrix} a & b \\ -\infty & -\infty \end{pmatrix}$ and $Q=\begin{pmatrix} -\infty & -\infty \\ c & d \end{pmatrix}$, the quantity $\sum_{k\in\mathbb{Z}} \lambda(A_k^n)$ is independent of the time step $n$ if and only if $a+d=0$ and $b+c=0$, and the constant value of the sum is $0$. Under that assumption each individual eigenvalue collapses to $\lambda(A_k^n)=-ka$, so the conservation is a linear cancellation of eigenvalues across symmetric positions. The supporting Theorem 3.1 gives the explicit max-plus expression of $A_k^n$ as a sum over paths, and Theorem 5.1 claims that the infinite time-evolution operator of the whole system has the single-point spectrum $\sigma(A)=\{0\}$, with an eigenvector whose two components at position $k$ are $-ak$ and $(-k+1)a-b$, hence linearly growing in $k$.

Load-bearing premise

The proof of Theorem 4.1 relies on the closed-form eigenvalue formula $\lambda(A_k^n)=\ell a+md+\min\{\ell, m, (\ell+m-1)/2\}\Delta$ being valid for $\Delta\ge 0$ in every case, including the balanced case $\ell=m$ where the formula omits the self-loop contribution $m\Delta$ that the true eigenvalue includes.

Editorial extensions

If this is right

  • Under assumption (A), the eigenvalue at position $k$ is $\lambda(A_k^n)=-ka$, so the eigenvalue profile is a straight line in position with slope $-a$, independent of time $n$.
  • The conservation law $\sum_k \lambda(A_k^n)=0$ supplies a time-independent, position-resolved quantity in max-plus dynamics that plays the role of the $\ell^2$-norm conservation in quantum walks, allowing a max-plus 'distribution' to be defined at each position.
  • The infinite time-evolution operator $A$ has spectrum $\{0\}$, meaning the whole-system dynamics are spectrally trivial yet admit stationary states that grow linearly in position.
  • The condition $a+d=b+c=0$ is equivalent to $\operatorname{tropdet}(H)=0$ in max-plus, mirroring the determinant-1 condition for a unitary quantum coin.
  • Because $A_k^n$ is the ultradiscretization of the quantum-walk state decision matrix, the conservation law is an ultradiscrete shadow of the unitarity-driven $\ell^2$ conservation of quantum walks.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The single-point spectrum $\{0\}$ suggests that the max-plus total evolution operator stabilizes after finitely many powers on any finite truncation; testing whether max-plus walks on finite graphs or with reflecting boundaries also conserve a zero sum would give a cheap, sharp check of the mechanism.
  • The linear-in-position stationary state invites comparison with the bounded, quadratically growing, and exponentially growing generalized eigenfunctions of quantum walks; one could test whether higher-dimensional max-plus walks produce stationary states that are linear along each coordinate direction.
  • If the announced max-plus analogue of the quantum-walk weak limit theorem holds, the conserved linear profile $\lambda(A_k^n)=-ka$ suggests the limiting 'density' will be uniform on the interval between the extreme positions rather than the arcsine-like quantum density.
  • The same conserved-quantity construction could be applied to other ultradiscrete integrable walks, where the role of the coin is played by a transfer matrix; the conservation would then be a tropical analogue of a conserved charge of the dynamics.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper introduces a max-plus analogue of the one-dimensional discrete-time quantum walk, with time evolution ψ_n^k = (P⊗ψ_{n-1}^{k+1}) ⊕ (Q⊗ψ_{n-1}^{k-1}) for 2×2 max-plus matrices P and Q. It gives an explicit path-sum formula for the state decision matrices A_n^k (Theorem 3.1), proposes that the sum over positions of the max-plus eigenvalues of these matrices is the analogue of the ℓ²-conservation of quantum walks, and states that this sum is conserved if and only if the entries of H=P⊕Q satisfy a+d=0 and b+c=0 (Theorem 4.1). The final part analyzes the infinite time-evolution operator A and asserts that its spectrum is the single point {0} (Theorem 5.1). The paper also gives an explicit eigenvector for this alleged eigenvalue 0.

Significance. The proposed model is a natural ultradiscrete analogue of a quantum walk, and the explicit path-sum formula in Theorem 3.1 is a useful, carefully derived contribution. The idea of using the sum of max-plus eigenvalues as a conserved quantity is original and connects the quantum-walk literature with max-plus spectral theory. If Theorem 4.1 were fully established, it would give a clean characterization of the conservative case. However, the central spectral claim of Section 5 is false as stated, and the proof of Theorem 4.1 contains a load-bearing eigenvalue error in the balanced case. Because the main advertised theorems are not correct as written, the paper cannot be accepted in its present form.

major comments (3)
  1. [Section 4, eigenvalue formula following the Δ≥0 simplification] The displayed formula λ(A_n^k)=ℓa+md+min{ℓ,m,(ℓ+m−1)/2}Δ is incorrect when ℓ=m. In that case the simplified 2×2 matrix has diagonal entries min{ℓ,m}Δ = mΔ, and by Proposition 2.2 the eigenvalue is the maximum average circuit weight, i.e. mΔ, not (m−1/2)Δ. The paper's formula is obtained by averaging the two off-diagonal entries and ignores the self-loop contributions on the diagonal. Since the summation in the proof of Theorem 4.1 uses this formula, the necessity direction of that theorem is not proved as written. The corrected formula min{ℓ,m}Δ still makes the sum nonconstant for Δ>0, so the theorem may be repairable, but the proof needs a substantive correction.
  2. [Section 5, Theorem 5.1] Proposition 2.2 is stated for finite matrices and cannot be applied directly to the infinite block tridiagonal matrix A in (5.14). The assertion σ(A)={0} is actually false. Under assumption (A), take a=−1, b=1, c=−1, d=1 and define x_k=(k/2, k/2−1). A direct max-plus computation gives (A⊗x)_k = ((k+1)/2, (k−1)/2) = (1/2)⊗x_k for every k∈Z, so 1/2 is an eigenvalue of A. This contradicts Theorem 5.1 and the corresponding line of Table 2. The proof's statement that 'from proposition 2.2, the spectrum is obviously {0}' is invalid for an infinite matrix, since bi-infinite eigenvectors can carry nonzero eigenvalues without any finite circuit of that average weight.
  3. [Section 5, proof of eigenvector formula] The proof of Theorem 5.1 also depends on Proposition 2.3, a finite-matrix statement about columns of A^*, and on the infinite power series (5.15). No convergence or support condition is given that would justify passing from finite matrices to the bi-infinite matrix A. The counterexample in the previous comment shows that such conditions are not merely technical: the claimed eigenvector is not the only eigenvector, and the spectral conclusion fails.
minor comments (4)
  1. [Section 2] There are typographical errors such as 'weghted matrix' for 'weighted matrix'; the text should be proofread throughout.
  2. [Section 3, proof of Theorem 3.1] The sentence 'Since ξ_P, ξ_Q, ξ_R and ξ_S is not depend on w_k' is ungrammatical; it should read 'do not depend on'.
  3. [Throughout] The notation alternates between A_n^k for the max-plus state decision matrix and A_k^n for the quantum-walk matrix in (1.4); the different indexing conventions should be explained explicitly.
  4. [Section 4] The main eigenvalue formula and the summation formulas in Theorem 4.1 would be much easier to check if they were numbered; currently they appear only in displayed unnumbered equations.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 4.1 is a direct max-plus eigenvalue computation and the only self-citation is background.

full rationale

The derivation chain is self-contained. Theorem 3.1 explicitly computes A_n^k by summing path weights; the eigenvalue formula for A_n^k is then obtained by an explicit max-plus matrix calculation and by applying the external textbook result Proposition 2.2 ([2]) to each finite 2x2 state-decision matrix. No parameter is fitted to the conserved quantity; the condition a+d=0, b+c=0 is derived, not assumed, in the sufficiency direction. The claim in Theorem 5.1 that sigma(A)={0} is based on applying Proposition 2.2 to the infinite block matrix A; that extension may be invalid, as the skeptical counterexample with a=-1, b=1, c=-1, d=1 suggests a linear eigenvector of eigenvalue 1/2, but an unsupported extension of an external theorem is a correctness issue, not circularity. Reference [27] is the only citation involving the authors and it supports only the background remark that ultradiscretization preserves essential properties for integrable systems; it does not carry Theorem 4.1 or Theorem 5.1. No fitted input is relabeled as a prediction and no central premise reduces to a self-citation.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters are fitted; a, b, c, d are model variables and assumption (A) is a condition, not a fitted parameter. The central claims rest on standard max-plus spectral theorems from the literature and on an unproved, false extension of a finite-matrix result to an infinite matrix in Theorem 5.1.

assumptions (3)
  • standard math Propositions 2.1, 2.2, 2.3 from Baccelli et al. [2]: max-plus eigenvalue equals maximum average circuit weight for finite matrices.
    Used in Section 4 to compute eigenvalues of finite state decision matrices and in Theorem 5.1 claimed for the infinite matrix without proof or extra conditions.
  • domain assumption The ultradiscretization formula epsilon log(e^{A/epsilon}+e^{B/epsilon}) converges to max(A,B) and preserves essential properties of the discrete recursion.
    This motivates the max-plus walk as an analogue of the quantum walk in the introduction; cited to [26].
  • ad hoc to paper Proposition 2.2 extends to the infinite matrix A in (5.14) without boundedness or growth conditions on eigenvectors.
    This extension is asserted in the proof of Theorem 5.1 and is false under the natural eigenvalue definition; a counterexample with linear eigenvector and eigenvalue 1/2 exists.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A walk on max-plus algebra." pith.science (2026). https://pith.science/paper/VDY3J7QY

@misc{pith2026190809051,
  author       = {Pith},
  title        = {Pith review of: A walk on max-plus algebra},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VDY3J7QY}},
  note         = {Machine review of arXiv:1908.09051}
}
abstract

Max-plus algebra is a kind of idempotent semiring over $\mathbb{R}_{\max}:=\mathbb{R}\cup\{-\infty\}$ with two operations $\oplus := \max$ and $\otimes := +$.In this paper, we introduce a new model of a walk on one dimensional lattice on $\mathbb{Z}$, as an analogue of the quantum walk, over the max-plus algebra and we call it max-plus walk. In the conventional quantum walk, the summation of the $\ell^2$-norm of the states over all the positions is a conserved quantity. In contrast, the summation of eigenvalues of state decision matrices is a conserved quantity in the max-plus walk.Moreover, spectral analysis on the total time evolution operator is also given.

Figures

Figures reproduced from arXiv: 1908.09051 by the authors.

Figure 1
Figure 1. The weighted digraph G(A).        . . . ψ n −1 ψ n 0 ψ n 1 . . .        =        . . . . . . . . . . . . · · · An 0 An −1 An −2 · · · · · · An 1 An 0 An −1 · · · · · · An 2 An 1 An 0 · · · . . . . . . . . . . . .        ⊗        . . . ψ 0 −1 ψ 0 0 ψ 0 1 . . .        . Hence the n-th power of A in (5.14) is given by A ⊗n =        . . . . . . . . . . . . · · · An 0 An −… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [27]

    Watanabe S Fukuda A Shigitani H and Iwasaki M 2018 Min-plus eige nvalue of tridiag- onal matrices in terms of the ultradiscrete Toda equation J. Phys. A: Math. Theor. 51 444001 18

    work page 2018

  2. [1]

    Ambainis A Bach E Nayak A Vishwanath A and Watrous J 2001 One-dim ensional quantum walks STOC ’01 Proceedings of the thirty-third annual ACM symposi um on Theory of computing 37–49

    work page 2001

  3. [2]

    Baccelli F Cohen G Olsder G L and Quadrat J P 1992 Syncronization and Linearity (New York: Wiley)

    work page 1992

  4. [3]

    Cantero MJ Gr¨ unbaum F A Moral L Vel´ azquez L 2012 The CGMV method for quantum walks Quantum Information Processing 11 1149–1192

    work page 2012

  5. [4]

    Childs A 2009 Universal computation by quantum walk Phys. Rev. Lett. 102 180501

    work page 2009

  6. [5]

    Feynman R P 1982 Simulating physics with computers International Journal of Theo- retical Physics 21 467–88

    work page 1982

  7. [6]

    Higuchi Y Konno N Sato I and Segawa E 2013 Quantum graph walks I : Mapping to quantum walks Yokohama Mathematical Journal 59 33–55

    work page 2013

  8. [7]

    Katori M Konno N Sudbury A and Tanemura H 2004 Dulalities for the Domany-Kinzel model J. Theoret. Probab. 17 131–44

    work page 2004

Show all 27 references
  1. [8]

    Kitagawa T Rudner MS Berg E and Demler E 2010 Exploring topologica l phases with quantum walks Phys. Rev. A - Atomic, Molecular, and Optical Physics 82 033429 16

    2010

  2. [9]

    Konno N 2002 Dualities for a class of finite range probabilistic cellular automata in one dimension J. Statist. Phys. 106 915–22

    2002

  3. [10]

    Konno N 2008 Quantum Walk Lecture Notes in Mathematics 1954 309–452

    2008

  4. [11]

    Konno N 2014 The uniform measure for discrete-time quantum w alks in one dimension Quantum Inf. Process. 13 1103–1125

    2014

  5. [12]

    Konno N Kunimatsu T and Ma X 2002 Applied Mathematics and computation 155 727–35

    2002

  6. [13]

    Konno N and Takei M 2015 The non-uniform stationary measure for discrete-time quantum walks in one dimension Quantum Inf. Comput. 15 1060–1075

    2015

  7. [14]

    Komatsu T and Konno N 2017 Stationary amplitudes of quantum w alks on the higher- dimensional integer lattice Quantum Inf. Process. 16 291

    2017

  8. [15]

    Komatsu T and Konno N 2019 Stationary measure induced by the eigenvalue problem of the one-dimensional Hadamard walk arXiv:1905.00330

    2019 arXiv

  9. [16]

    Maclagan D and Sturmfels B 2015 Introduction to Tropical Geometry (American Math- ematical Society)

    2015

  10. [17]

    M´ arquez-M´ artin I Arnault P Molfetta GD and P´ erez A 2018 Ele ctromagnetic lattice gauge invariance in two-dimensional discrete-time quantum walks Phys. Rev. A 98 032333

    2018

  11. [18]

    Matsue K Matsuoka L Ogurisu O and Segawa E 2018 Resonant-tu nneling in discrete- time quantum walk Quantum Studies: Mathematics and Foundations 6 35–44

    2018

  12. [19]

    Meyer D 1996 From quantum cellular automata to quantum lattice gases J. Stat. Phys. 85 551–74

    1996

  13. [20]

    Morioka H 2019 Generalized eigenfunctions and scattering matr ices for position- dependent quantum walks Reviews in Mathematical Physics online first 1-37

    2019

  14. [21]

    Olsder GJ and Roos C 1988 Cramer and Cayley-Hamilton in the Max A lgebra Lin. Alg. Appl. 10187–108

    1988

  15. [22]

    Schutter DB and Moor DB 2002 The QR Decomposition and the Sing ular Value De- composition in the Symmetrized Max-Plus Algebra Revisited SIAM Review 44 417–54

    2002

  16. [23]

    Shikano Y 2013 From Discrete Time Quantum Walk to Continuous Tim e Quantum Walk in Limit Distribution J. Comput. Theor. Nanoscience 10 1558–70

    2013

  17. [24]

    II, The concept of duality in interacting particle systems Ann

    Sudbury A W and Lloyd P 1995 Quantum operators in classical qua ntum theory. II, The concept of duality in interacting particle systems Ann. Probab. 23 1816–1830

    1995

  18. [25]

    IV, Quasi-duality and thinnings of interacting particle systems Ann

    Sudbury A W and Lloyd P 1997 Quantum operators in classical qua ntum theory. IV, Quasi-duality and thinnings of interacting particle systems Ann. Probab. 25 96–114 17

    1997

  19. [26]

    Tokihiro T Takahashi D Matsukidaira J and Satsuma J 1996 From s oliton equations to integrable cellular automata through a limiting procedure Phys. Rev. Lett. 76 3247–50

    1996

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.