用几何方法揭示布尔阈值函数的最小确定点数，解决了一个长期开放问题。
Chamber geometry and specification numbers of Boolean threshold functions
- 将阈值函数视为高维空间中的胞腔，其关键点对应胞腔的面。
- 证明平均确定点数为 Θ(n)，上界不超过 2n，解决了前人提出的问题。
- 适用于多项式阈值函数，且能分析变量扩展操作对结构的影响。
布尔阈值函数 $f$ 在 $n$ 个变量上的规范数 $σ_n(f)$ 是唯一确定该函数的最少点数。其本质点构成唯一的最小集合。本文发展了 Zuev 的几何视角：阈值函数是 $(n+1)$ 维权值与阈值空间中一个中心超平面排列的胞腔，函数的本质点恰好对应其胞腔的面，因此规范数即为胞腔的面数。下界 $σ_n(f)≥n+1$ 变为凸锥至少有 $n+1$ 个面的事实，等号成立当且仅当胞腔为单纯形。通过共振排列精确计算平均规范数 $\overlineσ_n$，并借助 Fukuda、Tamura 与 Tokuyama 定理给出上界 $\overlineσ_n≤2n$，从而得到 $\overlineσ_n=Θ(n)$，解决了 Gutekunst、Mészáros 与 Petersen 提出的问题。该方法还可推广至多项式阈值函数。同一几何结构连接阈值函数与阈值交错体，其顶点为修正的 Chow 向量，顶点度数即对应函数的规范数。最后，研究了 Lozin 等人关于最小规范数函数的操作：增加变量或变量扩展相当于将胞腔闭包与半直线取积，保持单纯性；对称变量扩展给出精确阈值判据，并证明在结果仍为阈值函数时最小规范数不变；同时解决了他们提出的第四个操作相关问题。
原文摘要 · Abstract (English)
The specification number $σ_n(f)$ of a Boolean threshold function $f$ on $n$ variables is the least number of points whose $f$-values determine $f$ uniquely among all threshold functions. Its essential points form the unique minimum such set. We develop Zuev's geometric interpretation: the threshold functions are the chambers of a central hyperplane arrangement in the $(n+1)$-dimensional space of weights and thresholds, and the essential points of a function correspond exactly to the facets of its chamber, so the specification number is the chamber's facet number. The lower bound $σ_n(f)\ge n+1$ becomes the fact that a pointed full-dimensional cone has at least $n+1$ facets, with equality for simplicial chambers. The average specification number $\overlineσ_n$ becomes an average facet count. We evaluate this average exactly via the resonance arrangement and bound it through a theorem of Fukuda, Tamura, and Tokuyama, obtaining $\overlineσ_n\le 2n$; hence $\overlineσ_n=Θ(n)$. This settles a question of Gutekunst, Mészáros, and Petersen. The method also extends to polynomial threshold functions. The same geometry links threshold functions with a threshold zonotope, whose vertices are modified Chow vectors. Its one-skeleton is the one-inclusion graph, and a vertex's degree is the specification number of that function. Finally, we treat the operations of Lozin et al. on functions of minimum specification number. Adding a variable and extending on a variable both take the product of a chamber closure with a half-line, preserving simpliciality. For the symmetric-variables extension we give an exact thresholdness criterion and show that minimum specification number is preserved whenever the extension is a threshold function. We also resolve a question they pose concerning a fourth operation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。