pith. sign in

arxiv: 2604.23634 · v1 · submitted 2026-04-26 · 🧮 math.CO · cs.IT· math.IT

On the Supremum of Singleton Ratios in Submodular Functions

Laszlo Csirmaz This is my paper

Pith reviewed 2026-05-08 06:00 UTC · model grok-4.3

classification 🧮 math.CO cs.ITmath.IT
keywords submodular functionsa-reducedsingleton ratiosbase polytopesupremumcombinatoricsdecomposition
0
0 comments X

The pith

An a-reduced submodular function with f(a)=1 can force other singletons up to Ω(n/log n) while remaining irreducible.

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

The paper introduces a-reduced submodular functions, where fixing one element a to value 1 means the function cannot be decomposed into submodular parts that ignore a. It builds a concrete example on n elements showing that the largest value on any other singleton reaches at least order n divided by log n. The authors prove this ratio λ cannot exceed a doubly exponential function of n. This quantifies the strongest constraint one variable can impose on others in a submodular setting without allowing separable components.

Core claim

The paper shows that λ, the supremum of the largest singleton value f(x) for x ≠ a in an a-reduced submodular function f with f(a)=1, satisfies Ω(n/log n) ≤ λ ≤ 2^{2^{O(n)}}. The lower bound comes from an explicit construction of such an f, while the upper bound follows from a general argument on possible decompositions and value constraints. Geometrically this limits the elongation of the submodular base polytope associated to f.

What carries the argument

The a-reduced property: any decomposition of f into submodular g + h with h independent of a must have h identically zero.

If this is right

  • The submodular base polytope can elongate by a factor Ω(n/log n) in the direction tied to a.
  • One element can constrain the possible singleton values of others by at least Ω(n/log n) under the reduced condition.
  • Any attempt to prove a tighter upper bound must handle the doubly exponential barrier shown in the argument.
  • The exact asymptotic growth of λ between the linear-log lower bound and the double-exponential upper bound stays open.

Where Pith is reading between the lines

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

  • The gap between the two bounds suggests the true order of λ may be closer to n/log n if stronger constructions exist.
  • The result indicates that submodular models can encode strong irreducible dependencies without allowing clean separation of variables.

Load-bearing premise

The constructed function must truly be a-reduced, so that no submodular summand can be pulled out without depending on a.

What would settle it

An explicit small-n computation that either fails to achieve Ω(n/log n) growth in the constructed family or finds a function with larger singleton ratio than the claimed upper bound.

read the original abstract

Let $N$ be a finite set of cardinality $n$, and $a\in N$. A submodular function $f$ on $N$ with $f(a)=1$ is defined to be $a$-reduced if, for any decomposition $f=g+h$ into submodular functions where $h$ does not depend on $a$, it follows that $h$ is identically zero. The maximal possible value of $f$ on the remaining singletons defines a quantity $\lambda$ that characterizes the degree to which one variable can constrain the value of another; geometrically, it also limits the possible elongation of the associated submodular base polytope. We construct an example demonstrating that $\lambda$ can be as large as $\Omega(n/\log n)$. Furthermore, we establish a doubly exponential upper bound on $\lambda$. The problem of narrowing the gap between these bounds remains open.

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

1 major / 2 minor

Summary. The paper defines an a-reduced submodular function f on a ground set N of size n with f(a)=1, where any submodular decomposition f=g+h with h independent of a must have h identically zero. It introduces λ as the supremum of f(b) over b≠a for such functions, constructs an explicit example achieving λ=Ω(n/log n), and proves a doubly exponential upper bound on λ (leaving the gap open).

Significance. If the lower-bound construction is verified to satisfy the a-reduced property, the result shows that singleton values in submodular functions can be forced to grow with n, with geometric implications for the elongation of submodular base polytopes. The explicit construction and separate (non-circular) proof of the upper bound are strengths; the large gap between Ω(n/log n) and doubly exponential leaves a clear open problem for tightening bounds.

major comments (1)
  1. [Lower-bound construction] The lower-bound construction (asserted to achieve Ω(n/log n)) is load-bearing for the main claim, but the verification that the constructed f satisfies the a-reduced property—i.e., that every submodular decomposition f=g+h with h independent of a forces h≡0—is not provided with sufficient detail or explicit checks. Without this, the example may admit a non-zero h independent of a for which f−h remains submodular, invalidating the bound. A complete, self-contained argument for this property is required.
minor comments (2)
  1. [Abstract] The abstract states the results but omits any reference to the section containing the construction or the upper-bound proof; adding such pointers would improve readability.
  2. [Abstract] Notation for λ is introduced in the abstract without a brief inline definition; a parenthetical reminder of its meaning would help readers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying the need for greater detail in verifying the a-reduced property of the lower-bound construction. We address the major comment below and will revise the manuscript to incorporate a more explicit and self-contained argument.

read point-by-point responses

  1. Referee: [Lower-bound construction] The lower-bound construction (asserted to achieve Ω(n/log n)) is load-bearing for the main claim, but the verification that the constructed f satisfies the a-reduced property—i.e., that every submodular decomposition f=g+h with h independent of a forces h≡0—is not provided with sufficient detail or explicit checks. Without this, the example may admit a non-zero h independent of a for which f−h remains submodular, invalidating the bound. A complete, self-contained argument for this property is required.

    Authors: We appreciate the referee highlighting this point, as the a-reduced property is indeed essential to the validity of the Ω(n/log n) lower bound. In the manuscript, the function f is constructed explicitly in Section 3 via a combinatorial weighting on subsets that prioritizes elements linked to a, and the proof of Theorem 3.1 sketches why any h independent of a must be zero by showing that a non-zero h would either violate submodularity of g = f - h or contradict f(a) = 1. We agree, however, that the verification would benefit from expansion into a fully self-contained argument with explicit case analysis on possible forms of h. In the revised version we will add a dedicated subsection that enumerates candidate decompositions (constant, linear, and higher-order terms independent of a), verifies submodularity preservation, and demonstrates that h must be identically zero in each case. This change will not alter the stated bounds or construction but will make the argument easier to check. revision: yes

Circularity Check

0 steps flagged

No circularity; bounds from explicit construction and independent proof

full rationale

The paper defines λ directly as the maximum singleton value attainable by an a-reduced submodular function with f(a)=1. It then supplies an explicit construction achieving Ω(n/log n) and a separate (doubly exponential) upper-bound argument. No step reduces to its own inputs by construction, no parameters are fitted and relabeled as predictions, and no self-citation chain is load-bearing. The a-reduced property is part of the definition of the class under study rather than a derived claim that loops back to the bound itself.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Relies on standard submodularity and the new a-reduced definition; no free parameters or new entities.

axioms (2)
  • standard math f is submodular if f(X)+f(Y) >= f(XUY)+f(XnY) for all X,Y.
    Foundational property used in all definitions.
  • domain assumption f is a-reduced if f(a)=1 and any decomposition f=g+h with h independent of a forces h=0.
    Central definition defining λ.

pith-pipeline@v0.9.0 · 10026 in / 1037 out tokens · 79509 ms · 2026-05-08T06:00:42.648960+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages · 1 internal anchor

  1. [1]

    Submodular functions: Learnability, structure, and optimization.SIAM J

    Balcan, M.F.; Harvey, N.J. Submodular functions: Learnability, structure, and optimization.SIAM J. Comput.2018,47, 703–754.https://doi. org/10.1137/120888909

    work page doi:10.1137/120888909 2018

  2. [2]

    Learning with Submodular Functions: A Convex Optimization Perspective

    Bach, F. Learning with Submodular Functions: A Convex Optimization Perspective. InFoundations and Trends in Machine Learning; Now Pub- lishers: Hanover, MA, USA,2013, Volume 6

    work page 2013

  3. [3]

    Secret-sharing schemes: a survey

    Beimel, A. Secret-sharing schemes: a survey. In:IWCC 2011, volume 6639 of LNCS, Springer2011, pp 11-46

    work page 2011

  4. [4]

    and Hertrich, C

    Brandenburg, M.C.; Grillo, M. and Hertrich, C. Decomposition polyhedra of piecewise linear functions.2024arXiv.https://doi.org/10.48550/ arxiv.2410.04907

    work page internal anchor Pith review arXiv

  5. [5]

    The size of a share must be large

    Csirmaz, L. The size of a share must be large. InEUROCRYPT’94,1994, volume 950 of LNCS, pp 13–22

    work page 1994

  6. [6]

    Enumerating Extremal Submodular Func- tions for n = 6.Mathematics2024,13, 97.https://doi.org/10.3390/ math13010097

    Csirmaz, E.P.; Csirmaz, L. Enumerating Extremal Submodular Func- tions for n = 6.Mathematics2024,13, 97.https://doi.org/10.3390/ math13010097

    work page

  7. [7]

    Submodular Functions, Matroids, and Certain Polyhedra

    Edmonds, J. Submodular Functions, Matroids, and Certain Polyhedra. In:Combinatorial Structures and thero Applications,1970, pp 69–87

    work page 1970

  8. [8]

    Polymatroidal dependence structure of a set of random vari- ables.Information and Control,197839(1), 55–72

    Fujishige, S. Polymatroidal dependence structure of a set of random vari- ables.Information and Control,197839(1), 55–72

    work page

  9. [9]

    Many rays of the submodular cone, 2025

    Logo, G; Padrol, A; Poullot, G. Many rays of the submodular cone. arXiv 2510.03177,2026

    work page arXiv 2026

  10. [10]

    Supermodularity and Supermodular Games.The New Pal- grave Dictionary of Economics,2008, pp 1–9.https://doi.org/10.1057/ 978-1-349-95121-5_2443-1

    Vives, X. Supermodularity and Supermodular Games.The New Pal- grave Dictionary of Economics,2008, pp 1–9.https://doi.org/10.1057/ 978-1-349-95121-5_2443-1

    work page 2008

  11. [11]

    W.A First Course in Information Theory

    Yeung, R. W.A First Course in Information Theory. Kluwer Aca- demic/Plenum Publishers, New York, 2002

    work page 2002

  12. [12]

    Ziegler, G.M.Lectures on Polytopes; Graduate Texts in Mathematics; Springer: Berlin/Heidelberg, Germany, 1994; Volume 152. 10

    work page 1994