Shannon's lower bound for finite carriers and binary bases #
For any fixed finite signature with operation arities at most two, interpreted on a finite
carrier U with q ≥ 2 elements, some function on n inputs requires more than qⁿ/n gates
for all sufficiently large n. The threshold may depend on the signature and carrier.
For the De Morgan basis on Bool, this matches Lupanov's upper bound asymptotically.
The logarithm of the counting bound is at most s log s + O(s) for n + 1 ≤ s.
At s = ⌊qⁿ/n⌋, this is smaller than the logarithm of the q^(qⁿ) functions.
This extends the Boolean counting argument in the references to finite carriers.
References #
- [Claude E. Shannon, The Synthesis of Two-Terminal Switching Circuits][Shannon1949]: Theorem 7, Section 3(e), pp. 77-79, the original counting argument for switching circuits.
- [Stasys Jukna, Boolean Function Complexity: Advances and Frontiers][Jukna2012]: Lemma 1.12 and Theorem 1.14, a modern treatment of Boolean circuit counting.
theorem
Cslib.Circuits.Shannon.exists_hard_function
{σ : Signature}
{U : Type u}
[Finite σ.Op]
[Finite U]
[Nontrivial U]
(I : Interpretation σ U)
(arity_le : ∀ (op : σ.Op), σ.Arity op ≤ 2)
:
For all sufficiently large n, some function on n inputs over U requires more than
|U|ⁿ/n gates over the fixed finite signature, whose operations have arity at most two.