Indecomposability Over the Max-Min Semiring

Indecomposability Over the Max-Min Semiring

Benjamin Baily
Department of Mathematics
University of Michigan
530 Church Street
Ann Arbor, MI 48109
USA

Justine Dell
Department of Mathematics
University of California San Diego
9500 Gilman Drive
La Jolla, CA 92093
USA

Henry L. Fleischmann
Department of Computer Science
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213
USA

Faye Jackson and Ethan Pesikoff
Department of Mathematics
University of Chicago
5734 South University Avenue
Chicago, IL 60637
USA

Steven J. Miller
Department of Mathematics and Statistics
Williams College
18 Hoxsey Street
Williamstown, MA 01267
USA

Luke Reifenberg
Department of Mathematics
University of Notre Dame
255 Hurley Building
Notre Dame, IN 46556
USA

Abstract:

For sets A, B ⊂ N, their sumset is A+B := {a+b: a ∈ A, b ∈ B}. If we cannot write a set C as C = A+B with |A|, |B| ≥ 2, then we say that C is (additively) indecomposable. The question of whether a given set C is indecomposable arises naturally in additive combinatorics. Equivalently, we can formulate this question as one about the indecomposability of Boolean polynomials, which has been discussed in previous work by Kim and Roush as well as Shitov.

We use combinatorial and probabilistic methods to prove that almost all polynomials are indecomposable over the max-min semiring, generalizing work of Shitov and proving a conjecture by Applegate, LeBrun, and Sloane concerning lunar numbers.

Full version: pdf, dvi, ps, latex

(Concerned with sequences A087636 A169912.)

Received January 2 2023; revised versions received January 3 2023; March 25 2024; March 2 2025; March 11 2025. Published in Journal of Integer Sequences, March 26 2025.

Return to Journal of Integer Sequences home page