Solving Square-Submatrix Equation Systems

Giovanni Manzini; Lorenzo Carfagna

REVIEW 4 major objections 4 minor 8 references

Solving Square-Submatrix Equation Systems

T0 review · 4 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 Any system of equality constraints between square submatrices of a matrix admits a generic solution in $O(|E|+mn)$ time.

desk verdict A solid 2D generalization of the SES solver with a real algorithmic contribution, but the central split lemmas need full case analysis before the linear-time claim is fully verified. read the letter →

arxiv 2608.13408 v1 pith:CF5H2NDF submitted 2026-08-13 cs.DS

Lorenzo Carfagna , Giovanni Manzini This is my paper · ORCID

classification cs.DS

keywords Two-dimensionalequationsystemsmacroschemesdatacompressionRepetitivenessmeasuresSquaresubmatrixequationsGenericsolutionLinear-timealgorithmgraph

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

The paper studies systems of equality constraints between square submatrices of a matrix and claims that any such system can be solved optimally: a generic solution, one with as many distinct symbols as possible, can be built in $O(|E|+mn)$ time, where $|E|$ is the number of equations and $mn$ is the matrix size. This extends to two dimensions the linear-time resolution of substring equation systems, and it matters because it makes two-dimensional macro schemes a practical compressed representation: a valid scheme of size $b$ for an $m\times n$ matrix can be decompressed in $O(b+mn)$ time, which is worst-case optimal. The paper also shows that the new measure $s(A)$ (smallest SSES representation) and the 2D macro-scheme measure $b_\square(A)$ are within a factor of two.

What carries the argument

The machinery is the typed equation graph $G_{\mathrm{eq}}(E)$ together with the $k$-special/$k$-short classification in base 16. An equation can be stored by any pair of homologous corners plus a type in $\{0,1,2,3\}$, so $G_{\mathrm{eq}}$ has one arc per equation and size $\Theta(|E|)$. The routine Shorten($E,k$) alternates SpecialSplit and SimpleSplit, which replace equations with side exceeding $2\cdot 16^k$ by $O(1)$ shorter $k$-special equations whose submatrices cover the originals, with Reduce applying a linear-time maximum spanning forest per type to keep the system acyclic. The coverage arguments in the split lemmas are what make these replacements equivalence-preserving.

What would settle it

Compute the connected components of the position graph $G_{\mathrm{pos}}(E)$ by brute force for a collection of small systems, including adversarial ones with equation lengths just above $2\cdot 16^k$ and hexadecimal coordinate digits equal to 0 or 15, and compare them with the components produced by the paper's algorithm on the same typed input. Any mismatch would show that a split operation changed the solution set, contradicting Theorem 1.

Watch

Extended reading notes

Core claim

The central result is Theorem 1: given a submatrix equation system $E$ for an $m\times n$ matrix, a generic solution $\phi(E)$ can be found in optimal $O(|E|+mn)$ time. The proof constructs an equivalent system whose equations have side length at most 2, builds the position graph of that system, and reads off $\phi(E)$ from its connected components. The construction is carried out by a recursive routine that, at recursion level $k$, works only with $k$-special equations (those whose four coordinates have all $k$ least significant hexadecimal digits nonzero) and alternates two operations: split operations break a long equation into $O(1)$ smaller equations whose associated squares cover the original pair, and a reduce operation discards redundant equations using maximum spanning forests, keeping the system type-acyclic. Because the fraction of positions that are $k$-special decays geometrically with $k$, the total work over all levels is linear.

Load-bearing premise

The load-bearing premise is that the split operations of Lemmas 8 and 9 always find, for every $k$-special equation, $O(1)$ smaller equations whose associated squares cover the two matching squares exactly, so the new system has the same solution set; if some configuration of coordinates escapes the covering construction, the recursion would not preserve solutions and Theorem 1 would fail.

Editorial extensions

If this is right

Any valid square bidirectional macro scheme of size $b$ for an $m\times n$ matrix can be decompressed in $O(b+mn)$ time, matching the input-plus-output lower bound and avoiding the $\Theta(|B|mn)$ worst case of naive graph traversal.
Every 2D macro scheme can be converted in linear time into an SSES of the same size, and every SSES representation yields a valid macro scheme of at most twice its size, so $s(A)\le b_\square(A)\le 2s(A)$.
The generic solution $\phi(E)$ produced by Theorem 1 is canonical: any other solution is obtained from it by relabeling symbols, so it gives a well-defined object for SSES-based compression and reconstruction.
The recursion's per-level bound $O((15/16)^{2k}mn)$ makes the total work shrink geometrically, so the $O(|E|+mn)$ running time is optimal in the worst case over input size and output size.

Reading between the lines

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

Extension beyond the paper: the same split-and-reduce recursion, with base $4^d$ and $k$-special meaning all $2d$ corner coordinates have nonzero $k$ least significant digits, should yield an $O(|E|+n^d)$ solver for equality systems over $d$-dimensional hypercubes.
Extension beyond the paper: the factor-2 gap between $s(A)$ and $b_\square(A)$ suggests testing whether there are matrices with $b_\square(A)=2s(A)$ and matrices where the gap is strictly smaller, which would clarify when SSES representations add expressive power over square macro schemes.
Extension beyond the paper: the typed equation graph and per-type maximum spanning forest argument may transfer to rectangular submatrix equalities with a fixed aspect ratio, giving linear-time solvers for those systems as well.

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.

Desk Editor's Note

read the letter

The paper gives a linear-time algorithm for square-submatrix equation systems, a genuinely natural 2D analogue of the 1D result in [4], and it builds a measure s(A) with a clean 2-approximation relation to 2D macro schemes. The typed corners, the base-16 specialness trick, and the square-splitting machinery are more than a mechanical lift from the string case, and the decompression corollary is a nice payoff. The proof follows the 1D template with the right structural ideas: Reduce via MSFs, Split into smaller equations, and a geometric shrinkage argument. Lemmas 1, 2, 6, and 7 appear correct; I checked the t=0 construction in Lemma 8 and the coordinate bounds in Lemma 7 and they work.

That said, the paper has a real verifiability gap in exactly the load-bearing place. Lemmas 8 and 9 are the only thing standing between the sketch and Theorem 1, and both defer the hard cases: Lemma 8 says the proofs for types 1–3 are analogous, and Lemma 9 says the right-edge rectangles can be handled similarly. The coverage arguments rely on figures and inequalities like ℓ−α ≥ max(ℓ−d,d) rather than an exhaustive enumeration of coordinate configurations. This is not a demonstrated contradiction, and I suspect the omitted cases do go through, but the resemblance to the 1D proof is not itself a proof. A sign error in one of the symmetric cases would collapse the recursion, and the current writeup doesn't let me rule that out without doing the case analysis myself. That is a heavy burden for a referee.

The O(mn) preprocessing step is also deferred to [4], which is acceptable but should be either reproduced or stated very explicitly, since the paper's optimality claim rests on it. The self-citation to [1] for the macro scheme definition is fine.

Who is this for? People working in 2D compression, string algorithms, and repetitiveness measures. It is a meaningful subfield result, not a breakthrough, and it deserves a serious referee. I would accept it for peer review, but I would ask the authors to expand Lemmas 8 and 9 into complete case analyses before publication. The paper is worth the extra rounds.

Referee Report

4 major / 4 minor

Summary. The paper defines Square Submatrix Equation Systems (SSES), systems of equality constraints between square submatrices of an m-by-n matrix, and claims a linear-time algorithm O(|E|+mn) that constructs the generic solution Phi(E). The algorithm is a two-dimensional generalization of the recursive string algorithm of Gawrychowski et al. [4], based on k-special and k-short equations, a geometric split procedure, and maximum-spanning-forest reductions. The paper also applies the result to decompress valid two-dimensional square macro schemes in optimal O(b+mn) time and relates SSES size to a repetitiveness measure s(A) with s(A) <= b_square(A) <= 2s(A).

Significance. If Theorem 1 is correct, the paper gives an optimal-time resolution procedure for a natural two-dimensional analogue of substring equation systems, and Corollary 1 would settle the decompression problem for square bidirectional macro schemes. The reduction to the 1D template of [4] is a meaningful technical step, and the connection between SSES representations and macro schemes is clean and potentially useful. The paper is honest about following the established proof strategy rather than claiming a fully independent machinery. Its main weakness is not the absence of a central idea but the incomplete discharge of the geometric case analyses in the two split lemmas, exactly where the recursion's equivalence property is load-bearing.

major comments (4)

[Appendix A, Lemma 8 (SpecialSplit), p. 9] The t=0 construction is not completed: the text says that e4 is constructed analogously and that the proofs for t=1,2,3 are analogous. The equivalence E1 union E2 == e requires that the four generated squares exactly cover the two matched squares S_e and S_e' with no uncovered cells and with no generated square protruding outside them. For e3 the text only asserts the inequality l-alpha >= max(l-d,d) and refers to Figure 2. A full coordinate-level case analysis for all four types is needed. An omitted symmetric case is precisely where a sign error (for instance, subtracting a coordinate that is smaller than the offset) could break the equality at a recursive level, so this is a verifiability gap in a load-bearing place for Theorem 1 and Lemma 3.
[Appendix A, Lemma 9 (SimpleSplit), p. 10] The lemma explicitly covers the bottom-edge rectangles and defers the right-edge rectangles with 'We can handle similarly', and it defers all other equation types with 'The proofs for the other types are symmetrical'. The claim that the output system is equivalent to the input requires that every leftover rectangle of both S_e and S_e', including the right-edge rectangles and the rightmost bottom-edge rectangles for every type t, is covered by k-special, k-short equations whose union is exactly the original squares. Since this lemma is used in the main recursion to convert (k+1)-short equations into k-short ones, the missing right-edge and type-symmetric cases must be spelled out as a formal case analysis rather than left to analogy.
[Appendix A, Lemma 7, proof of part b), p. 8] The proof is presented as an induction sketch. It asserts that borrowing is possible because i3,i4 > (z...z)_16^k, and it uses precomputed arrays for the least significant digit, but the induction step must prove a formal invariant: after fixing k digits, the subtraction of the accumulated d from i3,i4 does not alter the already-fixed low-order digits, and the final d remains in the interval [(y...y)_16^k, (z...z)_16^k]. The current wording 'borrowing, if needed, is possible' needs to be turned into a precise carry/borrow argument, because a borrow from a low-order digit would destroy k-specialty of the resulting coordinates.
[Section 3, Proof of Theorem 1, p. 6] The proof invokes 'an O(mn) one-time pre-processing step that removes the need for any subsequent vertex relabeling as in [4]' but does not describe this step or specify how it interacts with the typed equations. Since the total optimal O(|E|+mn) bound depends on this pre-processing being genuinely O(mn) and on its preserving the semantics of E, the step should either be stated in this paper or cited with a precise pointer to the corresponding lemma in [4].

minor comments (4)

[Section 1, page 2] There is a typo in 'such as A...'? More precisely, the phrase 'is is type-acyclic' in Lemma 1 should read 'is type-acyclic'.
[Section 3, Theorem 1] The generic solution is denoted Phi(E) in the introduction and Theorem 1, but phi(E) appears in the statement of Theorem 1. The notation should be made uniform.
[Appendix A, Lemma 7] The expression 'h z1 + w mod 16' is typographically unclear; it should be 'h_{z1} + w mod 16'. Also, the precomputed table 'for every possible value of y' should state its size explicitly (16 entries, each with 16^4 digit quadruples or an equivalent compact encoding).
[Section 2, Example 1] The statement 'Gpos has 8 connected components' refers to the graph of the example, but Figure 1 shows 8 components only if isolated vertices are counted. The sentence could clarify that isolated positions are included as components, since this is the convention used when assigning distinct symbols.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the core derivation is self-contained and the only self-citation is definitional, not load-bearing.

full rationale

The central claim, Theorem 1, is obtained by generalizing the recursive SES algorithm of Gawrychowski et al. [4], and the proof is carried out in the paper from definitions rather than by assuming the conclusion. Lemma 6 gives a direct cycle/transitivity argument for the MSF reduction; Lemma 7 is a constructive number-theoretic choice of an integer d; Lemmas 8 and 9 argue equivalence of the split systems by explicit square-covering geometry, not by invoking a fitted parameter or a predicted quantity. No parameter is fitted to any subset of the data, and no output quantity is renamed as an input. The only self-citation is [1], which is used in the applications section to recall the definition of a square bidirectional macro scheme; that is a definitional reference, not a load-bearing theorem, and it does not support the main algorithmic claim. The paper's remaining concerns are correctness and completeness issues rather than circularity: Lemmas 8 and 9 defer some symmetric cases ('analogous', 'handle similarly'), and Lemma 5's construction of a macro scheme from an SSES representation relies on mutual source references that need a termination check. These are verifiability gaps, not reductions by construction, so they do not raise the circularity score.

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

The central algorithm rests on standard algorithmic background; it introduces no fitted constants, no new postulated entities, and no self-referential derivation. The only notable assumptions are the linear-time MSF subroutine and the counting bound from [4].

assumptions (3)

standard math The counting bound |S_n^k| <= (15/16)^k n for k-special integers in base 16.
Inherited from [4, Fact 11a] and used in Lemmas 1 and 3 to bound the number of equations per recursion level.
domain assumption The Fredman-Willard trans-dichotomous algorithm computes an MSF of a graph in linear time.
Used in Lemma 2 to make the system type-acyclic in O(|E|) time; this is an external algorithm with a specific word-RAM model assumption.
domain assumption The 1D SES resolution framework of [4] (position graph, generic solution, recursive shorten/split structure) is correct and carries over to 2D.
The paper generalizes the recursive structure directly from [4] and references it for the preprocessing step in Theorem 1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Solving Square-Submatrix Equation Systems." pith.science (2026). https://pith.science/paper/CF5H2NDF

@misc{pith2026260813408,
  author       = {Pith},
  title        = {Pith review of: Solving Square-Submatrix Equation Systems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CF5H2NDF}},
  note         = {Machine review of arXiv:2608.13408}
}

read the original abstract

We consider systems of submatrix equations, that is, sets of equality constraints over square submatrices of the input. By generalising the recursive algorithm of Gawrychowski et al. [Universal reconstruction of a string, Theoretical Computer Science 2020] to two dimensions, we obtain a linear-time procedure that finds a solution for any such input system. As an immediate by-product, this yields an optimal-time algorithm for decompressing any two-dimensional macro scheme based on copy operations of sub-squares.

Figures

Figures reproduced from arXiv: 2608.13408 by the authors.

**Figure 1.** The position graph Gpos(E) for Example 1 (left) and the corresponding generic solution Φ(E) (right). characters since any other solution can be obtained from Φ(E) by remapping alphabet symbols. A solution Φ(E) can be obtained by means of the position graph Gpos(E) introduced in [4] for strings. Gpos(E) is an undirected graph whose nodes are the positions [m] × [n] and whose arcs represent the positionwise equalitie… view at source ↗

**Figure 2.** Construction of the equations e1, e2, e3 used in Lemma 8 that together with e4 (not shown) are equivalent to e = (i, j, i′ , j′ , ℓ, 0). The requirement is that the union of the submatrices associated with e1, . . . , e4 coincides with the submatrix associated to e. The parameters d and α are chosen to ensure that e1 is k-short and the reference corner v of the type-v equations e2, e3 are (k + 1)- special. are equiv… view at source ↗

**Figure 3.** Partitioning of a k-special and k + 1-short equation e as described in Lemma 9, here l = ℓ mod 16k where ℓ is the equation length. The two squares in the figure represents Se i.e. one of the two matching squares corresponding to e. The l × l square in the bottom-right corner and all the 16k × 16k squares are k-special and k-short. In the figure on the right, the square Q, which covers the rightmost rectangle in the … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

8 extracted references · 6 canonical work pages

[4]

Universal reconstruction of a string.Theoretical Computer Science, 812:174–186, 2020

Pawe l Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Wale´ n. Universal reconstruction of a string.Theoretical Computer Science, 812:174–186, 2020. In memoriam Danny Breslauer (1968-2017)

work page 2020
[1]

The landscape of compressibility measures for two-dimensional data.IEEE Access, 12:87268–87283, 2024

Lorenzo Carfagna and Giovanni Manzini. The landscape of compressibility measures for two-dimensional data.IEEE Access, 12:87268–87283, 2024

work page 2024
[2]

Suffixient sets.CoRR, abs/2312.01359, 2023

Lore Depuydt, Travis Gagie, Ben Langmead, Giovanni Manzini, and Nicola Prezza. Suffixient sets.CoRR, abs/2312.01359, 2023

arXiv 2023
[3]

Fredman and Dan E

Michael L. Fredman and Dan E. Willard. Trans-dichotomous algorithms for mini- mum spanning trees and shortest paths.Journal of Computer and System Sciences, 48(3):533–551, 1994

work page 1994
[5]

At the roots of dictionary compression: string attractors

Dominik Kempa and Nicola Prezza. At the roots of dictionary compression: string attractors. InSTOC, pages 827–840, New York, 2018. ACM

work page 2018
[6]

String representation in suffixient set size space

Hiroki Shibata and Hideo Bannai. String representation in suffixient set size space. (arXiv:2604.04377), April 2026. arXiv:2604.04377 [cs]

arXiv 2026
[7]

Storer and Thomas G

James A. Storer and Thomas G. Szymanski. Data compression via textual substi- tution.Journal of the ACM, 29(4):928–951, 1982. A Technical lemmas The next lemma extends the result in [4, Lemma 5] to our typed two-dimensional equation systems. Lemma 6.LetEbe an equation system and fort= 0,1,2,3letG t eq be the subgraph ofG eq formed by all its type-tedges. ...

work page 1982
[8]

Lete= (i, j, i′, j′, ℓ, t) be ak-special equation inEand assumet= 0, the proofs fort= 1,2,3 are analogous

and is added toE 1 orE 2 accordingly. Lete= (i, j, i′, j′, ℓ, t) be ak-special equation inEand assumet= 0, the proofs fort= 1,2,3 are analogous. Ifeis already (k+1)-short, we add it toE 1. If this is not the case, but one of its corners is (k+ 1)-special, we change the type ofeaccordingly (if needed) and we add it toE 2. In either case, we are done. Other...

work page

Pith tools

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

[1] [4]

Universal reconstruction of a string.Theoretical Computer Science, 812:174–186, 2020

Pawe l Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Wale´ n. Universal reconstruction of a string.Theoretical Computer Science, 812:174–186, 2020. In memoriam Danny Breslauer (1968-2017)

work page 2020

[2] [1]

The landscape of compressibility measures for two-dimensional data.IEEE Access, 12:87268–87283, 2024

Lorenzo Carfagna and Giovanni Manzini. The landscape of compressibility measures for two-dimensional data.IEEE Access, 12:87268–87283, 2024

work page 2024

[3] [2]

Suffixient sets.CoRR, abs/2312.01359, 2023

Lore Depuydt, Travis Gagie, Ben Langmead, Giovanni Manzini, and Nicola Prezza. Suffixient sets.CoRR, abs/2312.01359, 2023

arXiv 2023

[4] [3]

Fredman and Dan E

Michael L. Fredman and Dan E. Willard. Trans-dichotomous algorithms for mini- mum spanning trees and shortest paths.Journal of Computer and System Sciences, 48(3):533–551, 1994

work page 1994

[5] [5]

At the roots of dictionary compression: string attractors

Dominik Kempa and Nicola Prezza. At the roots of dictionary compression: string attractors. InSTOC, pages 827–840, New York, 2018. ACM

work page 2018

[6] [6]

String representation in suffixient set size space

Hiroki Shibata and Hideo Bannai. String representation in suffixient set size space. (arXiv:2604.04377), April 2026. arXiv:2604.04377 [cs]

arXiv 2026

[7] [7]

Storer and Thomas G

James A. Storer and Thomas G. Szymanski. Data compression via textual substi- tution.Journal of the ACM, 29(4):928–951, 1982. A Technical lemmas The next lemma extends the result in [4, Lemma 5] to our typed two-dimensional equation systems. Lemma 6.LetEbe an equation system and fort= 0,1,2,3letG t eq be the subgraph ofG eq formed by all its type-tedges. ...

work page 1982

[8] [8]

Lete= (i, j, i′, j′, ℓ, t) be ak-special equation inEand assumet= 0, the proofs fort= 1,2,3 are analogous

and is added toE 1 orE 2 accordingly. Lete= (i, j, i′, j′, ℓ, t) be ak-special equation inEand assumet= 0, the proofs fort= 1,2,3 are analogous. Ifeis already (k+1)-short, we add it toE 1. If this is not the case, but one of its corners is (k+ 1)-special, we change the type ofeaccordingly (if needed) and we add it toE 2. In either case, we are done. Other...

work page