All monotone functions can be represented as a tree of threshold gates (or, more extreme, as a tree of and & or gates-- themselves just the extreme cases for thresholds). But this doesn't result in useful way of counting the monotone functions due to duplicates.
A great many monotone functions have a very natural representation as a threshold gate or a simple composition of threshold gates-- like a majority of three majorities. But I wonder what monotone functions are the least threshold-like. Unfortunately I don't know of a useful way to ask the question because at the extreme they can all be constructed from threshold gates, so it's not useful e.g. to ask for monotone functions that can't be constructed from them.
A related question might be what are the N monotone functions that can be combined to most efficiently represent all monotone functions up to size M? Does the selection of these best basis functions change for different sizes? (or fall into a finite set of groups like odd and even M?).
What about a monotonix function that has the keast duplicates when shown as a tree of thresholds? Or one that has the deepest tree? Or the least balanced tree? Those feel likely to have an alternative definition that is more elegant.
This discussion is about monotone Boolean functions. That is, functions from {0,1}^N → N, such that "flipping" any input from 0 to 1 never causes the output to go from 1 to 0.
I can't think of any way to to write a prime-counting function as an interesting monotone Boolean function. If you represent the numbers in binary, it's not monotone. If you write them in unary, with a separate function for each bit, then each bit's function (taken by itself) is just a near-trivial threshold function.
No worries, I got that. Boolean came before programming for me by way of electronics. Which is what I thought was interesting about this article, to imagine the algorithm but as discrete logic.
A great many monotone functions have a very natural representation as a threshold gate or a simple composition of threshold gates-- like a majority of three majorities. But I wonder what monotone functions are the least threshold-like. Unfortunately I don't know of a useful way to ask the question because at the extreme they can all be constructed from threshold gates, so it's not useful e.g. to ask for monotone functions that can't be constructed from them.
A related question might be what are the N monotone functions that can be combined to most efficiently represent all monotone functions up to size M? Does the selection of these best basis functions change for different sizes? (or fall into a finite set of groups like odd and even M?).