pith. sign in

arxiv: 2606.29477 · v1 · pith:M3KX2BWCnew · submitted 2026-06-28 · 💻 cs.DM · cs.LG· math.CO

Chamber geometry and specification numbers of Boolean threshold functions

Martin Anthony This is my paper

Pith reviewed 2026-06-30 01:37 UTC · model grok-4.3

classification 💻 cs.DM cs.LGmath.CO
keywords Boolean threshold functionsspecification numberhyperplane arrangementchamber geometryresonance arrangementthreshold zonotopeone-inclusion graphessential points
0
0 comments X

The pith

The average specification number of Boolean threshold functions is at most 2n, hence linear in the number of variables.

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

The paper interprets Boolean threshold functions as chambers of a central hyperplane arrangement in (n+1)-dimensional weight-threshold space. The specification number of a function equals the number of facets of its chamber because the essential points correspond exactly to those facets. Averaging the facet counts over the resonance arrangement and applying a bound on facet numbers yields an upper bound of 2n on the average specification number. This establishes that the average is linear in n and settles an open question. The same chamber geometry also connects threshold functions to vertices of a threshold zonotope and extends to polynomial threshold functions.

Core claim

Threshold functions are the chambers of a central hyperplane arrangement whose facets are the essential points of the function, so the specification number equals the facet count of the chamber. The average facet count over all chambers is evaluated exactly via the resonance arrangement and bounded above by 2n using a theorem of Fukuda, Tamura, and Tokuyama, showing the average specification number is Θ(n). The geometry also identifies the one-skeleton of the associated threshold zonotope with the one-inclusion graph, where vertex degree equals specification number, and analyzes operations that preserve minimum specification number.

What carries the argument

The chamber of the central hyperplane arrangement in (n+1)-space whose facets are the essential points determining the threshold function.

If this is right

  • Every threshold function has specification number at least n+1, with equality precisely when its chamber is simplicial.
  • The average specification number is Θ(n).
  • The method of counting facets via the resonance arrangement extends directly to polynomial threshold functions.
  • Adding a variable or extending on a variable takes the product of a chamber closure with a half-line and preserves simpliciality.
  • The symmetric-variables extension preserves minimum specification number whenever the result remains a threshold function.

Where Pith is reading between the lines

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

  • The zonotope construction may yield new combinatorial identities for modified Chow vectors of threshold functions.
  • Degree sequences in the one-inclusion graph could be used to study uniform convergence rates in learning threshold functions.
  • The simpliciality preservation under the listed operations suggests a recursive construction for all minimum-specification threshold functions.
  • The resonance-arrangement averaging technique might apply to other classes of Boolean functions defined by linear inequalities.

Load-bearing premise

The essential points of a threshold function correspond exactly to the facets of its chamber.

What would settle it

An explicit computation of the average specification number for some n greater than 2n.

Figures

Figures reproduced from arXiv: 2606.29477 by Martin Anthony.

Figure 1
Figure 1. Figure 1: Two chambers of A2 as cones in the parameter space R 3 with coordinates (a0, a1, a2), where Hx = {a : ⟨a, xe⟩ = 0}. Each cone is unbounded: solid segments are the bounded portion of the extreme rays, dashed arrows mark their extension to infinity, and the cross-section is an arbitrary truncation, not a face. (a) The chamber of x1 ∧ x2 is simplicial, with three facets, supported by H10, H01, and H11; the pl… view at source ↗
Figure 2
Figure 2. Figure 2: Two views of the threshold zonotope Z2, which is a rhombic dodecahedron. The left panel is a three-dimensional orientation view. The right panel gives a Schlegel-style drawing (a planar represen￾tation) of the one-skeleton. In the right panel, the blue circular vertices are the eight trivalent vertices, corresponding to the functions with σ2 = 3; these are the conjunctions and disjunctions of two literals.… view at source ↗
read the original abstract

The specification number $\sigma_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 $\sigma_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\sigma_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\sigma_n\le 2n$; hence $\overline\sigma_n=\Theta(n)$. This settles a question of Gutekunst, M\'esz\'aros, 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.

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

Summary. The manuscript develops Zuev's geometric view of Boolean threshold functions as chambers of a central hyperplane arrangement in (n+1)-space. It equates the specification number σ_n(f) to the number of facets of the chamber, so that the lower bound σ_n(f) ≥ n+1 follows from the fact that a pointed full-dimensional cone has at least n+1 facets. The average ar σ_n is evaluated exactly via the resonance arrangement and bounded above by 2n using the Fukuda-Tamura-Tokuyama theorem, yielding ar σ_n = Θ(n) and settling the open question of Gutekunst, Mészáros, and Petersen. The same geometry is applied to polynomial threshold functions, to a threshold zonotope whose vertices are modified Chow vectors, and to the operations of Lozin et al. that preserve minimum specification number.

Significance. If the facet correspondence and the cited theorem application hold, the paper supplies a clean geometric proof that the average specification number grows linearly, together with an exact evaluation via the resonance arrangement. The extension to polynomial threshold functions, the zonotope interpretation, and the resolution of the fourth operation question are additional contributions that strengthen the work.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for the positive evaluation, including the recommendation to accept.

Circularity Check

0 steps flagged

No circularity: derivation uses external theorem and standard facts

full rationale

The paper equates specification number to chamber facet count by developing Zuev's external geometric interpretation of threshold functions as chambers. The average is evaluated exactly via the resonance arrangement (standard in arrangement theory) and bounded above by the Fukuda-Tamura-Tokuyama theorem (external, different authors), yielding ≤2n and thus Θ(n) together with the standard n+1 lower bound for pointed cones. No step reduces by definition, fitted parameter, or self-citation chain to the paper's own inputs; the central claim is supported by independent external results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper builds on standard combinatorial geometry (hyperplane arrangements and cone facet counts) without introducing free parameters or new entities; the main results follow from the developed interpretation plus one external theorem.

axioms (1)
  • domain assumption Threshold functions are the chambers of a central hyperplane arrangement in the (n+1)-dimensional space of weights and thresholds.
    This is the foundational geometric interpretation developed from Zuev's work, stated in the abstract.

pith-pipeline@v0.9.1-grok · 5865 in / 1453 out tokens · 48854 ms · 2026-06-30T01:37:10.222840+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

50 extracted references · 3 canonical work pages · 1 internal anchor

  1. [1]

    Anthony, G

    M. Anthony, G. Brightwell, and J. Shawe-Taylor. On specifying Boolean functions by la- belled examples.Discrete Applied Mathematics, 61(1):1–25, 1995. 58

    1995

  2. [2]

    M. Anthony. Classification by polynomial surfaces.Discrete Applied Mathematics, 61(1):91– 103, 1995

    1995

  3. [3]

    Anthony and P

    M. Anthony and P. L. Bartlett.Neural Network Learning: Theoretical Foundations. Cam- bridge University Press, 1999

    1999

  4. [4]

    Baldi and R

    P. Baldi and R. Vershynin. Polynomial threshold functions, hyperplane arrangements, and random tensors.SIAM Journal on Mathematics of Data Science, 1(4):699–729, 2019

    2019

  5. [5]

    A. J. Bernstein. Maximally connected arrays on then-cube.SIAM Journal on Applied Mathematics, 15(6):1485–1489, 1967

    1967

  6. [6]

    A.Bondy.Inducedsubsets.Journal of Combinatorial Theory, Series B,12(2):201–202,1972

    1972

  7. [7]

    L. J. Billera, J. T. Moore, C. D. Moraites, Y. Wang, and K. Williams. Maximal unbalanced families. arXiv:1209.2309, 2012

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  8. [8]

    Brysiewicz, H

    T. Brysiewicz, H. Eble, and L. Kühne. Computing characteristic polynomials of hyper- plane arrangements with symmetries.Discrete & Computational Geometry, 70(4):1356– 1377, 2023

    2023

  9. [9]

    C. K. Chow. On the characterization of threshold functions.Proceedings of the Symposium on Switching Circuit Theory and Logical Design, pages 34–38, 1961

    1961

  10. [10]

    T. M. Cover. Geometrical and statistical properties of systems of linear inequalities with ap- plications in pattern recognition.IEEE Transactions on Electronic Computers, EC-14:326– 334, 1965

    1965

  11. [11]

    Diakonikolas and D

    I. Diakonikolas and D. M. Kane. Degree-dChow parameters robustly determine degree-d PTFs (and algorithmic applications). InProceedings of the 51st Annual ACM Symposium on Theory of Computing, pages 804–815, 2019

    2019

  12. [12]

    Doliwa, G

    T. Doliwa, G. Fan, H. U. Simon, and S. Zilles. Recursive teaching dimension, VC-dimension and sample compression.Journal of Machine Learning Research, 15:3107–3131, 2014

    2014

  13. [13]

    C. C. Elgot. Truth functions realizable by single threshold organs. InProceedings of the Second Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1961), pages 225–245. IEEE, 1961

    1961

  14. [14]

    D. Ellis. Almost isoperimetric subsets of the discrete cube.Combinatorics, Probability and Computing, 20(3):363–380, 2011

    2011

  15. [15]

    Fukuda, A

    K. Fukuda, A. Tamura, and T. Tokuyama. A theorem on the average number of subfaces in arrangements and oriented matroids.Geometriae Dedicata, 47:129–142, 1993

    1993

  16. [16]

    P. W. Goldberg. A bound on the precision required to estimate a Boolean perceptron from its average satisfying assignment.SIAM Journal on Discrete Mathematics, 20(2):328–343, 2006

    2006

  17. [17]

    S. C. Gutekunst, K. Mészáros, and T. K. Petersen. Root cones and the resonance arrange- ment.Electronic Journal of Combinatorics, 28(1):#P1.12, 2021

    2021

  18. [18]

    S. A. Goldman and M. J. Kearns. On the complexity of teaching.Journal of Computer and System Sciences, 50(1):20–31, 1995

    1995

  19. [19]

    L. H. Harper. Optimal assignments of numbers to vertices.Journal of the Society for In- dustrial and Applied Mathematics, 12(1):131–135, 1964

    1964

  20. [20]

    S. Hart. A note on the edges of then-cube.Discrete Mathematics, 14(2):157–163, 1976. 59

    1976

  21. [21]

    Haussler

    D. Haussler. Sphere packing numbers for subsets of the Booleann-cube with bounded Vapnik–Chervonenkis dimension.Journal of Combinatorial Theory, Series A, 69(2):217– 232, 1995

    1995

  22. [22]

    Haussler, N

    D. Haussler, N. Littlestone, and M. K. Warmuth. Predicting{0,1}-functions on randomly drawn points.Information and Computation, 115(2):248–292, 1994

    1994

  23. [23]

    Hu.Threshold Logic

    S.-T. Hu.Threshold Logic. University of California Press, 1965

    1965

  24. [24]

    J. Kahn, J. Komlós, and E. Szemerédi. On the probability that a random±1-matrix is singular.Journal of the American Mathematical Society, 8(1):223–240, 1995

    1995

  25. [25]

    L. Kühne. The universality of the resonance arrangement and its Betti numbers.Combina- torica, 43(2):277–298, 2023

    2023

  26. [26]

    A. D. Korshunov. Monotone Boolean functions.Russian Mathematical Surveys, 58(5):929–1001, 2003. Translated fromUspekhi Matematicheskikh Nauk58(5):89–162. doi:10.1070/RM2003v058n05ABEH000667

    work page doi:10.1070/rm2003v058n05abeh000667 2003

  27. [27]

    Kushilevitz, N

    E. Kushilevitz, N. Linial, Y. Rabinovich, and M. Saks. Witness sets for families of binary vectors.Journal of Combinatorial Theory, Series A, 73(2):376–380, 1996

    1996

  28. [28]

    J. H. Lindsey. Assignment of numbers to vertices.The American Mathematical Monthly, 71(5):508–516, 1964

    1964

  29. [29]

    Lozin, I

    V. Lozin, I. Razgon, V. Zamaraev, E. Zamaraeva, and N. Yu. Zolotykh. Specifying a positive threshold function via extremal points. In S. Hanneke and L. Reyzin, editors,Proceedings of the 28th International Conference on Algorithmic Learning Theory,volume76ofProceedings of Machine Learning Research, pages 208–222. PMLR, 2017

    2017

  30. [30]

    Lozin, I

    V. Lozin, I. Razgon, V. Zamaraev, E. Zamaraeva, and N. Yu. Zolotykh. Linear read-once and related Boolean functions.Discrete Applied Mathematics, 250:16–27, 2018

    2018

  31. [31]

    V.Lozin,V.Zamaraev,E.Zamaraeva,andN.Yu.Zolotykh.OnBooleanthresholdfunctions with minimum specification number.Information and Computation, 289:104926, 2022

    2022

  32. [32]

    Muroga.Threshold Logic and its Applications

    S. Muroga.Threshold Logic and its Applications. Wiley-Interscience, 1971

    1971

  33. [33]

    O’Donnell and R

    R. O’Donnell and R. A. Servedio. The Chow parameters problem.SIAM Journal on Com- puting, 40(1):165–199, 2011

    2011

  34. [34]

    N. J. A. Sloane (editor). The On-Line Encyclopedia of Integer Sequences.https:// oeis.org. Sequence A034997, number of regions of the resonance arrangement,https: //oeis.org/A034997; sequence A000609, number of threshold functions,https://oeis. org/A000609. Accessed June 8, 2026

    2026

  35. [35]

    Roudneff

    J.-P. Roudneff. Cells with many facets in arrangements of hyperplanes.Discrete Mathemat- ics, 98(3):185–191, 1991

    1991

  36. [36]

    N. Sauer. On the density of families of sets.Journal of Combinatorial Theory, Series A, 13(1):145–147, 1972

    1972

  37. [37]

    Schrijver.Theory of Linear and Integer Programming

    A. Schrijver.Theory of Linear and Integer Programming. John Wiley & Sons, 1986

    1986

  38. [38]

    R. A. Servedio. Every linear threshold function has a low-weight approximator.Computa- tional Complexity, 16(2):180–209, 2007

    2007

  39. [39]

    S. Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages.Pacific Journal of Mathematics, 41(1):247–261, 1972. 60

    1972

  40. [40]

    Shinohara and S

    A. Shinohara and S. Miyano. Teachability in computational learning.New Generation Com- puting, 8:337–347, 1991

    1991

  41. [41]

    E. Sperner. Ein Satz über Untermengen einer endlichen Menge.Mathematische Zeitschrift, 27:544–548, 1928

    1928

  42. [42]

    R. P. Stanley. An introduction to hyperplane arrangements. In E. Miller, V. Reiner, and B. Sturmfels, editors,Geometric Combinatorics, IAS/Park City Mathematics Series, vol. 13, pages 389–496. American Mathematical Society, 2007

    2007

  43. [43]

    C. Stenson. Weighted voting, threshold functions, and zonotopes. In K.-D. Crisman and M. A. Jones, editors,The Mathematics of Decisions, Elections, and Games, Contemporary Mathematics, vol. 624, pages 89–99. American Mathematical Society, Providence, RI, 2014

    2014

  44. [44]

    Wang and A

    C. Wang and A. C. Williams. The threshold order of a Boolean function.Discrete Applied Mathematics, 31:51–69, 1991

    1991

  45. [45]

    R. O. Winder. Bounds on threshold gate realizability.IEEE Transactions on Electronic Computers, EC-12(5):561–564, 1963

    1963

  46. [46]

    R. O. Winder. Chow parameters in threshold logic.Journal of the ACM, 18(2):265–289, 1971

    1971

  47. [47]

    Zaslavsky

    T. Zaslavsky. Facing up to arrangements: face-count formulas for partitions of space.Mem- oirs of the American Mathematical Society, 1(154), 1975

    1975

  48. [48]

    G. M. Ziegler.Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer- Verlag, New York, 1995

    1995

  49. [49]

    Y. A. Zuev. Asymptotics of the logarithm of the number of threshold functions of the algebra of logic.Soviet Mathematics Doklady, 39(3):512–513, 1989

    1989

  50. [50]

    Methods of geometry and probabilistic combinatorics in threshold logic,

    Y. A. Zuev. Kombinatorno-veroyatnostnye i geometricheskie metody v porogovoi logike [Methods of geometry and probabilistic combinatorics in threshold logic].Diskretnaya Matematika, 3(2):47–57, 1991. In Russian. An English translation is listed under the title “Methods of geometry and probabilistic combinatorics in threshold logic,”Discrete Mathe- matics a...

    work page doi:10.1515/dma.1992.2.4.427 1991