pith. machine review for the scientific record. sign in

arxiv: 2605.03551 · v1 · submitted 2026-05-05 · 🧮 math.RA

Recognition: 3 theorem links

· Lean Theorem

Solving one-sided linear systems over symmetrized and supertropical semiring

Sulaiman Alhussaini , Sergei Sergeev
Authors on Pith no claims yet

Pith reviewed 2026-05-08 18:33 UTC · model grok-4.3

classification 🧮 math.RA
keywords tropical semiringsymmetrized semiringsupertropical semiringone-sided linear systemsgreatest solutionminimal solutionssemiring algebratropical cryptography
0
0 comments X

The pith

One-sided linear systems over symmetrized and supertropical semirings can be solved by first finding the greatest solution in polynomial time and then searching for minimal solutions.

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

The paper extends the standard two-step method for solving one-sided linear systems of the form Ax equals b from the tropical semiring to its symmetrized and supertropical versions. In the base tropical case, the greatest solution is computed efficiently before tackling the harder search for minimal solutions. The authors adapt this procedure to the two extended semirings by showing that the same computational steps apply. They also examine the consequences for tropical cryptography. Readers would care because these semirings model systems with uncertainty or signed quantities that appear in optimization and security contexts.

Core claim

The central claim is that the approach of first computing the greatest solution to Ax equals b in polynomial time and then finding minimal solutions extends directly to one-sided linear systems over symmetrized and supertropical semirings. The extension is developed without introducing fundamentally new obstacles, and the findings are used to discuss implications for tropical cryptography.

What carries the argument

The two-step solution procedure of polynomial-time greatest-solution computation followed by minimal-solution search.

If this is right

  • Greatest solutions to Ax equals b remain computable in polynomial time over both extended semirings.
  • Minimal solutions can be located by adapting the search procedures from the tropical case.
  • The same complexity profile holds, so the systems stay tractable in the same way.
  • The results directly inform the design or analysis of protocols in tropical cryptography.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same two-step method might generalize to further semiring extensions not covered in the paper.
  • Concrete implementations on example systems could show whether runtimes differ noticeably in cryptographic applications.
  • Related problems in signed or uncertain optimization might admit similar reductions to greatest-then-minimal search.

Load-bearing premise

The methods for finding the greatest solution and then minimal solutions transfer to symmetrized and supertropical semirings without new computational obstacles or different techniques.

What would settle it

A concrete linear system Ax equals b over the supertropical semiring for which no greatest solution can be computed in polynomial time.

read the original abstract

One-sided linear systems of the form ``$Ax=b$'' are well-known and extensively studied over the tropical (max-plus) semiring and wide classes of related idempotent semirings. The usual approach is to first find the greatest solution to such system in polynomial time and then to solve a much harder problem of finding all minimal solutions. We develop an extension of this approach to the same systems over two well-known extensions of the tropical semiring: symmetrized and supertropical, and discuss the implications of our findings for the tropical cryptography.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper extends the standard approach for solving one-sided linear systems Ax=b over the tropical semiring to symmetrized and supertropical semirings. It shows that the greatest solution remains computable in polynomial time via a modified closure operator respecting the symmetrized sign structure and supertropical ghost ideal (both residuated), while minimal solutions are enumerated via covering-set search with only local adjustments to the dominance relation, without new exponential blow-up or undecidability. A qualitative discussion addresses implications for tropical cryptography.

Significance. If the extensions hold, the work unifies computational techniques across these idempotent semiring extensions while preserving key efficiency properties, which is valuable for tropical algebra and its applications. The explicit confirmation that residuation carries over and that the covering-set method adapts locally strengthens the foundation for further algorithmic development; the cryptography remarks usefully flag potential shifts in hardness assumptions even if they remain qualitative.

minor comments (3)
  1. Abstract: the phrase 'discuss the implications of our findings for the tropical cryptography' is vague; a single sentence indicating whether the new semirings strengthen or weaken the underlying hardness assumption would improve clarity.
  2. Section describing the symmetrized case: the modified closure operator is stated to respect the sign structure, but an explicit verification that the resulting greatest solution still satisfies the original system (analogous to the tropical proof) would help readers confirm the adaptation.
  3. Enumeration of minimal solutions: while local adjustments to the dominance relation are mentioned, including a small concrete example contrasting the tropical and supertropical dominance checks would make the 'no new exponential blow-up' claim more tangible.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments were raised in the report, so our response focuses on confirming the overall alignment with the manuscript's contributions and noting that we will incorporate any minor editorial suggestions in the revised version.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper extends the standard two-step procedure (polynomial-time greatest solution via closure operator, followed by enumeration of minimal solutions) from tropical semirings to symmetrized and supertropical variants by adapting the residuation and dominance relations to the new sign/ghost structures. These adaptations are presented as direct consequences of the algebraic definitions of the extended semirings rather than being fitted to data or reduced to prior self-citations. No equations are shown to be equivalent by construction to their inputs, no parameters are fitted and then relabeled as predictions, and the cryptography remarks remain qualitative without relying on unproven transfer of complexity results. The derivation chain is therefore self-contained against the external algebraic properties of the semirings.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities are identifiable from the provided information.

pith-pipeline@v0.9.0 · 5384 in / 1080 out tokens · 54687 ms · 2026-05-08T18:33:10.226658+00:00 · methodology

Review history (3 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 2 canonical work pages

  1. [1]

    Akian, S

    M. Akian, S. Gaubert, and A. Guterman. Tropical Cramer Determinants Revisited. In G.L. Litvinov and S.N. Sergeev, editors,Tropical and Idem- potent Mathematics and Applications, volume 616 ofContemporary Math- ematics, page 45. AMS, 2014. See also arXiv:1309.6298

    work page arXiv 2014

  2. [2]

    Akian, S

    M. Akian, S. Gaubert, and L. Rowen. Linear algebra over semiring pairs, 2023-2025. Arxiv preprint 2310.05257

    work page arXiv 2023

  3. [3]

    Alhussaini and S

    S. Alhussaini and S. Sergeev. Cryptanalysis of multi-party key exchange protocols over a modified supertropical semiring. Cryptology ePrint Archive, Paper 2025/2062, 2025

    2025

  4. [4]

    Baccelli, G

    F.L. Baccelli, G. Cohen, G.J. Olsder, and J.P. Quadrat.Synchronization and Linearity: An Algebra for Discrete Event Systems. John Wiley & Sons Ltd, Chichester, UK, 1992

    1992

  5. [5]

    Efficiently enumerating hitting sets of hypergraphs arising in data profiling.Journal of Computer and System Sciences, 124:192–213, 2022

    T.Bläsius, T.Friedrich, J.Lischeid, K.Meeks, andM.Schirneck. Efficiently enumerating hitting sets of hypergraphs arising in data profiling.Journal of Computer and System Sciences, 124:192–213, 2022

    2022

  6. [6]

    Butkovič.Max-linear Systems: Theory and Algorithms

    P. Butkovič.Max-linear Systems: Theory and Algorithms. Springer, Lon- don, 2010. 30

    2010

  7. [7]

    Cuninghame-Green.Minimax algebra, volume 166 ofLecture Notes in Economics and Mathematical Systems

    R.A. Cuninghame-Green.Minimax algebra, volume 166 ofLecture Notes in Economics and Mathematical Systems. Springer, Berlin, Heidelberg, 1979

    1979

  8. [8]

    Di Nola, W

    A. Di Nola, W. Pedrycz, and S. Sessa. Fuzzy relation equations under LSC and USCt-norms and their Boolean solutions.Stochastica, 11(2-3), 1987

    1987

  9. [9]

    Elbassioni

    K. Elbassioni. A note on systems with max–min and max-product con- straints.Fuzzy Sets and Systems, 159(17):2272–2277, 2008. Theme: Fuzzy Relations

    2008

  10. [10]

    S. Elt. Cryptography in symmetrised tropical algebra. Master’s thesis, Uni- versity of Birmingham, School of Mathematics, Birmingham, UK, March 2024

    2024

  11. [11]

    Gaubert.Théorie des systèmes linéaires dans les dioïdes

    S. Gaubert.Théorie des systèmes linéaires dans les dioïdes. Thèse, École des Mines de Paris, July 1992

    1992

  12. [12]

    Grigoriev and V

    D. Grigoriev and V. Shpilrain. Tropical cryptography.Communications in Algebra, 42:2624 – 2632, 2013

    2013

  13. [13]

    Izhakian and L

    Z. Izhakian and L. Rowen. Supertropical linear algebra.Pacific Journal of Mathematics, 266(1):43–75, 2013

    2013

  14. [14]

    Karp.Reducibility among Combinatorial Problems, pages 85–103

    R. Karp.Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA, 1972

    1972

  15. [15]

    Kotov and A

    M. Kotov and A. Ushakov. Analysis of a key exchange protocol based on tropical matrix algebra.Journal of Mathematical Cryptology, 12(3):137– 141, 2018

    2018

  16. [16]

    A. V. Markovskii. Solution of fuzzy equations with max-product compo- sition in inverse control and decision making problems.Automation and Remote Control, 65(9):1486–1495, Sep 2004

    2004

  17. [17]

    Otero Sánchez, D

    Á. Otero Sánchez, D. Camazón Portela, and J.A. López-Ramos. On the solutions of linear systems over additively idempotent semirings.Mathe- matics, 12(18), 2024

    2024

  18. [18]

    Ponmaheshkumar, J

    R. Ponmaheshkumar, J. Ramalingham, and R. Perumal. Multi-party key exchange scheme based on super-tropical semiring.Cryptologia, 2025. pub- lished online

    2025

  19. [19]

    E. Stickel. A new method for exchanging secret keys. InThird Interna- tional Conference on Information Technology and Applications (ICITA’05), volume 2, pages 426–430, 2005

    2005

  20. [20]

    Vorobyev

    N.N. Vorobyev. Extremal algebra of positive matrices.Elektron. Informa- tionsverarbeitung und Kybernetik, 3(1):39–72, 1967. in Russian. 31

    1967