{"id":"2bf4c61c-9ed6-4c5c-acf0-c6adf342e848","arxiv_id":"2608.13408","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Any system of square-submatrix equality constraints on an m by n matrix can be solved in O(|E|+mn) time, giving optimal O(b+mn) decompression of 2D square macro schemes.","lead":"The paper gives a linear-time algorithm that solves systems of equality constraints between square submatrices of an input matrix, generalizing a known one-dimensional string algorithm. This yields optimal-time decompression for two-dimensional macro schemes based on square copy operations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Correctness hinges on the coverage proofs of Lemmas 8 and 9, and the omitted symmetric cases (types 1–3, right-edge rectangles) are never fully discharged.","rationale":"After working through the 2D adaptation, I find the recursive structure and the size-decay argument internally consistent: Lemma 1 bounds type-acyclic k-special systems, Reduce restores the bound via MSF per type, and the recursion's geometric decay in (15/16)^{2k} yields O(mn). I also checked the coordinate arithmetic behind Lemma 7: the pigeonhole choice of w in [y,y+4] is valid, and the induction condition i3,i4 > (z...z)^{k+1} is what makes borrowing possible, so Lemma 7 itself is not the weak point. The genuinely load-bearing uncertainty is the geometric coverage in Lemmas 8 and 9. The paper proves only the t=0 case in Lemma 8 and defers right-edge rectangles in Lemma 9 with 'similarly'; the equivalence of the split system to the original depends on every generated square remaining inside the original squares and on the union covering every offset. The figures and inequalities suggest this is true, but the omitted symmetric cases are not a purely cosmetic gap: a sign error in a rotated type could subtract from a small coordinate and escape the square, which would break the induction and Theorem 1. I could not exhibit such a configuration, and my hand-check of t=0 and the bottom-edge cases found no error. The right response is to keep the reader's CONDITIONAL verdict and demand either a completed case analysis or a computational audit before full acceptance.","tokens_in":36,"tokens_out":53702,"duration_ms":567925,"concrete_test":"Implement SpecialSplit (Lemma 8) and SimpleSplit (Lemma 9) for all four equation types and exhaustively or fuzz-test on small parameters, e.g., k=0..3, m,n≤64, side lengths ℓ up to 2·16^{k+1}, and all coordinates in range. For each input equation e, verify that the position-edge set induced by the split system equals that induced by e: every cell of the two matched squares is covered, no point outside the squares is constrained, and each generated equation is within matrix bounds. Then run the full Shorten on random small SSESs and compare the connected components of the resulting position graph against a brute-force G_pos computation. Any mismatch is a counterexample; if exhaustive small cases pass, confidence in the omitted type and edge cases increases substantially.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1) rests on Lemmas 8 and 9: every k-special equation must be replaced, in O(1) pieces, by equations whose associated squares exactly cover the two matched squares, so that the split system is equivalent to the original. As written, Lemma 8 gives the full argument only for type t=0 ('the proofs for t=1,2,3 are analogous'), and Lemma 9 covers the bottom-edge rectangles explicitly but defers the right-edge rectangles ('We can handle similarly'). The coverage arguments are geometric sketches: they rely on Figures 2 and 3 and inequalities such as ℓ−α ≥ max(ℓ−d,d), rather than an exhaustive enumeration of the possible coordinate configurations. If any configuration leaves a cell of S_e uncovered, or places a generated square outside S_e, the equivalence E1∪E2≡E fails at that recursive level and Theorem 1's induction collapses. I checked the t=0 constructions and the coordinate bounds for Lemma 7; they appear to work, but the omitted symmetric cases are exactly where a sign error (e.g., subtracting from a small coordinate) could occur. This is a verifiability gap in a load-bearing place, not a demonstrated contradiction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":9598,"tokens_out":3597,"duration_ms":38922,"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":[{"comment":"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.","section":"Appendix A, Lemma 8 (SpecialSplit), p. 9"},{"comment":"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.","section":"Appendix A, Lemma 9 (SimpleSplit), p. 10"},{"comment":"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":"Appendix A, Lemma 7, proof of part b), p. 8"},{"comment":"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].","section":"Section 3, Proof of Theorem 1, p. 6"}],"minor_comments":[{"comment":"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":"Section 1, page 2"},{"comment":"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.","section":"Section 3, Theorem 1"},{"comment":"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":"Appendix A, Lemma 7"},{"comment":"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.","section":"Section 2, Example 1"}],"recommendation":"major_revision","confidential_remarks":"The main technical risk is the incomplete case analysis in Lemmas 8 and 9. These are not cosmetic gaps: they are the exact steps that preserve the solution set through the recursion, and the paper's own text admits that several cases are left to analogy. I do not see a demonstrated contradiction, but the authors should be required to provide a complete, coordinate-level verification for all four equation types in both split lemmas before the claim of Theorem 1 can be accepted. The application section is largely independent of the split details and would survive even if the proof of Theorem 1 needed adjustment. The self-citation to [1] is appropriate and not a concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThat 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.\n\nThe 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.\n\nWho 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.","headline":"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.","tokens_in":10134,"tokens_out":1116,"would_cite":true,"duration_ms":12760,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Any system of equality constraints between square submatrices of a matrix admits a generic solution in $O(|E|+mn)$ time.","keywords":["Two-dimensional equation systems","Two-dimensional macro schemes","Two-dimensional data compression","Repetitiveness measures","Square submatrix equations","Generic solution","Linear-time algorithm","Equation graph"],"falsifier":"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.","tokens_in":9178,"feed_emoji":"📐","tokens_out":7068,"duration_ms":61433,"temperature":0.7,"pith_summary":"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.","feed_headline":"Square-submatrix equation systems solved in linear time","feed_subtitle":"A 2D generalization of string reconstruction also decompresses any two-dimensional macro scheme optimally.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the one-dimensional recursive algorithm and the k-special/k-short split-reduce framework that the paper generalizes to square submatrices.","marker":"[4]"},{"why":"Provides the linear-time maximum spanning forest algorithm used by the Reduce operation to discard redundant equations.","marker":"[3]"},{"why":"Defines square bidirectional macro schemes, the objects whose decompression Corollary 1 optimizes, and supplies the comparison measure $b_\\square(A)$.","marker":"[1]"},{"why":"Introduces the use of equation systems as string compression and repetitiveness measures and the conversion of macro schemes into equation systems, which the paper adapts to two dimensions.","marker":"[6]"},{"why":"Introduces textual-substitution macro schemes, the ancestry of the bidirectional macro scheme model that the SSES measure is compared against.","marker":"[7]"}],"fun_headline_variants":["Linear-time solver for square-submatrix equations","Optimal-time algorithm for square-submatrix systems","Square-submatrix equations solved in optimal time","2D macro schemes decompressed optimally via submatrix equations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Linear-time solver for square-submatrix equations","Optimal-time algorithm for square-submatrix systems","Square-submatrix equations solved in optimal time","2D macro schemes decompressed optimally via submatrix equations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001404,"raw_usage":{"total_tokens":5602,"prompt_tokens":799,"completion_tokens":4803,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":415,"completion_tokens_details":{"reasoning_tokens":4744}},"tokens_in":415,"tokens_out":4803,"duration_ms":35079,"temperature":1.0,"reasoning_tokens":4744,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:37:43.173377+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Universal reconstruction of a string.Theoretical Computer Science, 812:174–186, 2020","cited_arxiv_id":null,"evidence_quote":"Supplies the one-dimensional recursive algorithm and the k-special/k-short split-reduce framework that the paper generalizes to square submatrices."},{"cited_title":"Fredman and Dan E","cited_arxiv_id":null,"evidence_quote":"Provides the linear-time maximum spanning forest algorithm used by the Reduce operation to discard redundant equations."},{"cited_title":"The landscape of compressibility measures for two-dimensional data.IEEE Access, 12:87268–87283, 2024","cited_arxiv_id":null,"evidence_quote":"Defines square bidirectional macro schemes, the objects whose decompression Corollary 1 optimizes, and supplies the comparison measure $b_\\square(A)$."},{"cited_title":"Storer and Thomas G","cited_arxiv_id":null,"evidence_quote":"Introduces textual-substitution macro schemes, the ancestry of the bidirectional macro scheme model that the SSES measure is compared against."}],"review_version":1}