Let f be a threshold Boolean function of n variables, and let sigma_H_n(f) denote its specification number in the class H_n. A function is nested when it belongs to the nested subclass of threshold functions. Anthony–Brightwell–Shawe-Taylor conjecture. If f has specification number n+1, then f is nested: sigma_H_n(f)=n+1 implies f is nested. Hu proved that every threshold Boolean function satisfies sigma_H_n(f)≥ n+1, while Anthony, Brightwell, and Shawe-Taylor proved that nested functions attain this lower bound. The conjecture asserts that these are the only functions attaining it; the supplied source does not establish a resolution.

Anthony–Brightwell–Shawe-Taylor conjecture on minimum specification threshold functions

Let $f$ be a threshold Boolean function of $n$ variables, and let $\sigma_{\mathcal{H}_n}(f)$ denote its specification number in the class $\mathcal{H}_n$ . A function is nested when it belongs to the nested subclass of threshold functions.

Anthony–Brightwell–Shawe-Taylor conjecture. If $f$ has specification number $n+1$ , then $f$ is nested:

\sigma_{\mathcal{H}_n}(f)=n+1 \implies f\text{ is nested}.

Hu proved that every threshold Boolean function satisfies $\sigma_{\mathcal{H}_n}(f)\geq n+1$ , while Anthony, Brightwell, and Shawe-Taylor proved that nested functions attain this lower bound. The conjecture asserts that these are the only functions attaining it; the supplied source does not establish a resolution.

Sources & referencesView supporting material

Primary source

Vadim Lozin, Igor Razgon, Viktor Zamaraev, Elena Zamaraeva and Nikolai Yu. Zolotykh, “Specifying a positive threshold function via extremal points”, arXiv:1706.01747 (2017).

1 week ago

Progress summary

Refreshed 5 days ago

Solved

The conjecture is false: published work gives non-nested examples attaining the minimum in every dimension from four upward.

The 1995 Anthony–Brightwell–Shawe-Taylor conjecture claimed that equality in the universal lower bound characterizes nested threshold functions. Hu established the lower bound, while Anthony, Brightwell, and Shawe-Taylor showed that nested functions attain it.

Known results

Hu (1965): every threshold function on $n$ variables has specification number at least $n+1$ .
Anthony, Brightwell, and Shawe-Taylor: nested functions attain specification number $n+1$ .
For positive threshold functions depending on all $n$ variables, exactly $n+1$ extremal points is equivalent to being nested.

2017 disproof

Razgon, Zamaraev, Zamaraeva, and Zolotykh exhibited, for every $n\geq 4$ , a non-nested threshold function with specification number $n+1$ , including $f_n=x_1x_2\vee\cdots\vee x_1x_{n-1}\vee x_2x_3\cdots x_n$ . A later exposition confirms the disproof; the extremal-point characterization remains true.

Current status (as of August 2026): The conjecture is resolved negatively for every $n\geq 4$ ; the minimum specification number is not a characterization of nested functions, while the related extremal-point statement remains established.

Sources

No solutions have been posted yet.