No Shannon effect induced by And/Or trees

NEW

Problem: Reconstructed conjecture (most natural in the paper’s context): for the limiting distribution $\mu_k$ on $k$-variable Boolean functions induced by uniform random And/Or trees with $k$ variables and size $n\to\infty$, asymptotically almost every sampled function has polynomial And/Or-tree complexity. Formally, if $L(f)$ is the minimum number of literal leaves in an And/Or tree computing $f$, then there is a polynomial $P$ such that

$$\mu_k\{f:L(f)\le P(k)\}\to 1\qquad(k\to\infty).$$

The wording is ambiguous: under the uniform measure on all Boolean functions this is false by Shannon’s counting theorem. The reference to Kozik’s limiting distributions supports the limiting And/Or-tree interpretation above.

Result: The conjecture is true. In fact one may take $P(k)=Ck^6$.

Use the standard Catalan/Kesten local limit for uniform binary trees with $n$ leaves: as $n\to\infty$, the tree locally becomes an infinite spine, and at each spine vertex an independent finite critical Galton–Watson full binary tree is attached. The attached tree has size distribution

$$\mathbb P(S=m)=C_{m-1}2^{-(2m-1)},$$

where $C_{m-1}$ is a Catalan number. Hence

$$\mathbb P(S>M)\le cM^{-1/2}.$$

At each spine vertex, independently, there is probability at least $1/(32k)$ of an absorbing two-leaf side tree: either the side tree is $x_i\wedge \neg x_i$ and the spine connector is $\wedge$, or the side tree is $x_i\vee \neg x_i$ and the spine connector is $\vee$. Such an event determines the whole remaining subtree, so the resulting Boolean function is computed by the finite prefix up to that vertex.

Let

$$N=\lceil 128k\log k\rceil,\qquad M=k^4.$$

The probability that no absorbing side tree appears among the first $N$ spine vertices is at most

$$(1-1/(32k))^N\le k^{-4}.$$

The probability that some side tree among the first $N$ has more than $M$ leaves is at most

$$N\cdot cM^{-1/2}=O((\log k)/k).$$

On the complementary event, the function is computed by a prefix using at most

$$NM=O(k^5\log k)\le Ck^6$$

literal leaves. Therefore

$$\mu_k\{f:L(f)>Ck^6\}\le k^{-4}+O((\log k)/k)\to 0.$$

Thus asymptotically almost all functions sampled from the And/Or-tree limiting distribution have polynomial complexity.

Verification audit: the proof uses exactly the limiting And/Or-tree distribution referred to by the conjecture; complexity is ordinary literal-leaf And/Or formula complexity; constants are represented by $x_i\wedge\neg x_i$ or $x_i\vee\neg x_i$, so no extra constants are assumed; the polynomial bound is uniform in $k$.

Citation: The conjecture is from Genitrini–Gittenberger–Mailler, “No Shannon effect induced by And/Or trees.” The proof above uses the standard Kesten local limit for critical Galton–Watson/Catalan trees; I am not aware of a prior source stating this polynomial-complexity consequence explicitly.