pith. sign in

arxiv: 2509.07246 · v2 · pith:VN75AS3Bnew · submitted 2025-09-08 · 🧮 math.PR

Optimal Thresholds for Monotone Non-Boolean Functions

Saba Lepsveridze , Allen Lin This is my paper

Pith reviewed 2026-05-21 22:13 UTC · model grok-4.3

classification 🧮 math.PR
keywords monotone functionssymmetric functionssharp thresholdsprobability simplexLebesgue measurenon-Boolean functionsoptimal boundsproduct measures
0
0 comments X

The pith

Symmetric monotone functions from [q]^n to [q] have the measure of input distributions yielding intermediate output probabilities bounded by O(1/log n).

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

The paper establishes that for any symmetric monotone function f mapping n-length strings over an alphabet of size q to a single symbol in that alphabet, and for any fixed output symbol a, the portion of the probability simplex where the probability of outputting a lies strictly between two positive constants epsilon and one minus epsilon has normalized Lebesgue measure at most a constant over log n. This holds uniformly in the function and in q. A sympathetic reader would care because it shows that these functions transition sharply between low and high output probability for almost all input distributions, with the uncertain region vanishing as n grows. The bound is shown to be tight by a matching lower-bound construction.

Core claim

For any symmetric monotone function f : [q]^n → [q] and any a in [q], the normalized Lebesgue measure gamma of the set of mu in the simplex Delta[q] such that the product-measure probability that f(x) equals a lies in the open interval (epsilon, 1-epsilon) equals O(1/log n), and this order is optimal.

What carries the argument

The normalized Lebesgue measure gamma on the simplex Delta[q] of all distributions mu on [q], which is used to bound the volume of distributions that produce intermediate probabilities for the output of a symmetric monotone f.

If this is right

  • For most distributions mu the function f outputs any fixed a with probability either near zero or near one under the product measure.
  • The region of uncertainty in distribution space where output probability stays away from the extremes shrinks inversely with the logarithm of the dimension n.
  • The same O(1/log n) bound applies uniformly to every symmetric monotone function and every alphabet size q.
  • The result closes the gap left by earlier estimates that decayed only like log log n over log n.

Where Pith is reading between the lines

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

  • Monotonicity is essential for forcing the intermediate set to shrink, because without the ordering constraint the volume could remain large for all n.
  • The same volume bound may help analyze multi-outcome decision procedures where each participant has q choices and the collective rule is monotone.
  • Direct numerical checks for small n on concrete examples such as coordinate-wise majority or linear threshold functions could reveal how quickly the asymptotic scaling appears.

Load-bearing premise

The function must be both symmetric and monotone, without which the set of distributions producing intermediate output probabilities could occupy constant measure on the simplex even for large n.

What would settle it

Exhibit one symmetric monotone f together with a fixed epsilon greater than zero such that the measure gamma of intermediate-probability mu remains bounded below by a positive constant independent of n.

Figures

Figures reproduced from arXiv: 2509.07246 by Allen Lin, Saba Lepsveridze.

Figure 1
Figure 1. Figure 1: The region Γ when q = 4. Again, C denotes different constants at different lines, depending on q only. Proposition 3. Let f : [q] n → {0, 1} be a 0-monotone and symmetric function. There exists an absolute constant C = C(q) such that for any region Ri, we have λ [ µ∈Ri {µt | t ∈ [0, 1]} ∩ D ! ≤ C(ln(1 − ε) − ln(ε)) log n . Proof. Fix a measure µ ∈ Γi . By construction, µs,t(i) = s(1 − t). By Proposition 2,… view at source ↗
read the original abstract

Let $[q] = \{0,1,\ldots,q-1\}$, let $\Delta[q]$ denote the simplex of probability measures on $[q]$, and let $\gamma$ denote the Lebesgue measure normalized on $\Delta[q]$. We prove that for any symmetric monotone function $f \colon[q]^n \to [q]$ and any $a \in [q]$ we have \begin{equation*} \gamma(\{\mu \in \Delta[q]\;\vert\;\mathbb{P}_{x\sim\mu^{\otimes n}}[f(x)=a] \in (\varepsilon,1-\varepsilon)\}) = O(1/\log n)\text{.} \end{equation*} We also show that this bound is tight. This improves Kalai and Mossel's previous bound of $O(\log \log n/\log n)$ and answers their question completely.

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 / 2 minor

Summary. The manuscript proves that for any symmetric monotone function f : [q]^n → [q] and any a ∈ [q], the normalized Lebesgue measure γ on the simplex Δ[q] of those μ where P_{x∼μ^⊗n}[f(x)=a] lies in (ε,1−ε) is O(1/log n). The bound is shown to be tight via an explicit construction. This improves the Kalai-Mossel bound of O(log log n / log n) and resolves their open question.

Significance. If the result holds, it supplies an optimal quantitative description of threshold behavior for symmetric monotone functions with non-Boolean range, strengthening the understanding of concentration phenomena on the probability simplex. The direct proof, the matching lower-bound construction, and the complete resolution of the prior question are clear strengths.

minor comments (2)
  1. The dependence of the implicit constant in the O(1/log n) bound on ε and q should be stated explicitly in the main theorem (currently visible only in the abstract equation).
  2. A short paragraph in the introduction comparing the new bound directly to the Kalai-Mossel result, including the improvement factor, would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the supportive summary, the recognition of the result's significance in resolving the Kalai-Mossel question, and the recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity detected in the derivation

full rationale

The paper supplies a direct mathematical proof of the stated O(1/log n) measure bound for symmetric monotone functions f, relying on monotonicity to control output-probability variation along rays in the simplex and symmetry to reduce the problem to multiplicity vectors. The argument improves the Kalai-Mossel bound of O(log log n / log n) with an explicit matching construction; no fitted parameters, self-referential definitions, or load-bearing self-citations appear. The central claim is independently derived from the function properties and is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard definition of symmetric monotone functions and the normalized Lebesgue measure on the probability simplex; no free parameters or invented entities are introduced.

axioms (2)
  • domain assumption f is symmetric and monotone
    Invoked in the statement of the theorem; monotonicity is essential for the concentration behavior.
  • standard math γ is the normalized Lebesgue measure on Δ[q]
    Standard uniform measure on the simplex of probability vectors.

pith-pipeline@v0.9.0 · 5672 in / 1279 out tokens · 39148 ms · 2026-05-21T22:13:07.668934+00:00 · methodology

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

10 extracted references · 10 canonical work pages

  1. [1]

    Collective Coin Flipping

    Ben-Or, M., and N. Linial. “Collective Coin Flipping.”Randomness and Computation(1990)

    work page 1990

  2. [2]

    The Influence of Variables in Product Spaces

    Bourgain, J., J. Kahn, G. Kalai, Y. Katznelson, and N. Linial. “The Influence of Variables in Product Spaces.”Israel J. Math.77(1992): 55–64

    work page 1992

  3. [3]

    Every Monotone Graph Property has a Sharp Threshold

    Friedgut, E., and G. Kalai. “Every Monotone Graph Property has a Sharp Threshold.”Proc. Amer. Math. Soc.124, no. 10 (1996): 2993–3002

    work page 1996

  4. [4]

    The Influence of Variables on Boolean Functions

    Kahn, J., G. Kalai, and N. Linial. “The Influence of Variables on Boolean Functions.”Proc. 29th Ann. Symp. on Foundations of Comp. Sci.(1998): 68–80

    work page 1998

  5. [5]

    Sharp Thresholds for Monotone Non-Boolean Functions and Social Choice Theory

    Kalai, G., and E. Mossel. “Sharp Thresholds for Monotone Non-Boolean Functions and Social Choice Theory.”Math. Oper. Res.40, no. 5 (2015): 915–925

    work page 2015

  6. [6]

    On the Influences of Variables on Boolean Functions in Product Spaces

    Keller, N. “On the Influences of Variables on Boolean Functions in Product Spaces.”Combin. Probab. Comput.20, no. 1 (2011): 83–102

    work page 2011

  7. [7]

    Probabilistic Characteristics of Graphs with Large Connectivity

    Margulis, G. “Probabilistic Characteristics of Graphs with Large Connectivity.”Problemy Peredachi Informatsii10, no. 2 (1974): 101–108

    work page 1974

  8. [8]

    A Note on Percolation

    Russo, L. “A Note on Percolation.”Z. Wahrscheinlichkeitstheorie verw. Gebiete43(1978):39– 48

    work page 1978

  9. [9]

    On Russo’s Approximate Zero-One Law

    Talagrand, M. “On Russo’s Approximate Zero-One Law.”Ann. Probab.22, no. 3 (1994):1576– 1587

    work page 1994

  10. [10]

    Hypercontractivity of Simple Random Variables

    Wolff, P. “Hypercontractivity of Simple Random Variables.”Studia Math.180, no. 3 (2007):219–236. Massachusetts Institute of Technology, 77 Massachusetts A ve, Cambridge, MA 02139-4301 Email address:sabal@mit.edu Massachusetts Institute of Technology, 77 Massachusetts A ve, Cambridge, MA 02139-4301 Email address:allenees@mit.edu

    work page 2007