Sign-pattern bound r-dependence gap

Gap in $r$-dependence of sign-pattern bound · arXiv:2308.05208

arXiv Problem medium confidence— first stated 2023-08-09

Authors: Noga Alon, Colin Defant, Noah Kravitz, Daniel G. Zhu

Status open high confidence

The conjecture asks to close the gap between the linear lower bound on $r$-dependence (from Proposition 2.5, which shows $r = 2^{m+1}$ functions suffice to realise all $2^m$ proper sign patterns) and the exponential upper bound in Theorem 2.2. No follow-up paper addressing this gap was found in a web search; the source paper was published in Combinatorica in 2025 as a direct journal version of the arXiv preprint with no announced resolution of this open problem.

Reviewer notes. The paper was published in Combinatorica 45, 25 (2025) (DOI: 10.1007/s00493-025-00148-0), but this is the journal version of the same preprint, not a follow-up. No independent paper closing the linear-vs-exponential gap in $r$-dependence was found in up to 5 web calls.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. The bound in Theorem 2.2 must have at least a linear dependence on $r$ if it is to depend polynomially on $m$; the current bound is exponential in $r$. It would be interesting to close this gap.

Context

Proposition 2.5 demonstrates that $r = 2^{m+1}$ functions suffice to realise all $2^m$ proper sign patterns even when $N = 1$ and $\Delta = s = 2$ are fixed, yielding a linear lower bound on the $r$-dependence that is far below the exponential upper bound in Theorem 2.2. The paper notes this discrepancy and calls for closing it.

Notes. Stated informally in prose; no labelled environment.

Source paper

Ordering Candidates via Vantage Points
Noga Alon, Colin Defant, Noah Kravitz, Daniel G. Zhu · 2023-08-09
https://arxiv.org/abs/2308.05208 PDF source