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

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

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

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

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

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

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

literal leaves. Therefore

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.