The function he considered is an iterated AND-OR function $f_n(X)$ of $n=4^h$ variables, and is defined inductively as follows. For $n=4$, \[ f_4(x_1,x_2,x_3,x_4)=x_1x_2\lor x_3x_4. \]

We will sketch his argument when translated into "modern" terms, used in the book. Roughly speaking, his argument is as follows:Theorem(Tkachov 1980): Every monotone $\Sigma_3$-circuit for $f_n$ has $2^{\Omega( n^{1/4})}$ gates.

- Our circuit is just an OR of monotone CNFs.
- Every minterm of $f_n$ must be produced by at least one of these CNFs.
- If the number of CNFs is "small", then some of them must produce "many" minterms.
- His main lemma then says that this CNF must have "many" clauses, as well.

On the other hand, every $\pi$-scheme (i.e. DeMorgan formula) has the following easy verifiable properties, not
shared by arbitrary contact schemes.
A *chain* in a scheme is a path from its source to a sink.
A *cut* of a set of chains is a set of contacts intersecting each of these paths; such a cut is
*minimal* (is a *min-cut*) if no its proper subset does the job. A *global cut* is
a min-cut of all paths in the scheme. Then we have:

- Every global cut intersects every chain in exactly one contact.
- For every set $P$ of chains, every min-cut of $P$ lies within at least one global cut.
- No two min-cuts of $P$ can lie in the same global cut.

Now suppose we have a monotone $\Sigma_3$-circuit computing $f_n$. This circuit is just an OR of monotone CNFs. Every minterm of $f_n$ must be produced by at least one of these CNFs. So, take one of these CNFs $F$. Minterms of $f_n$ correspond to chains, and maxterms of $f_n$ to global cuts in the $\pi$-scheme for $f_n$. Let $P$ be the set of minterms of $f_n$ produced by $F$, and $P^{\perp}$ denote the set of all min-cuts of $P$. Let $|F|$ be the number of clauses in $F$. Lemma 2 in his paper states the following.

Lemma A:$|F|\geq |P^{\perp}|$.

The main technical contribution of the paper is the following lemma, which is the Main Lemma in his paper. He gives its proof in the appendix. The proof itself uses a clever counting, but is too long to at least sketch it here.

Having this lemma, we can finish the proof of the theorem as follows. For the number $\mu_n$ of minterms of $f_n$, we have the following recursion (recall that $n$ is of the form $n=4^h$): $\mu_4=2$, and $\mu_{4n}=2\mu_n^2$. This yields $$\displaystyle \mu_n\geq 2^{\sum_{i=0}^{h-1}2^i}=2^{2^h-1}=2^{\sqrt{n}-1}. $$ Let $s$ be the top fanin of our circuit, i.e. the number of CNFs in it. Then there exists a CNF $F$, the family $P$ of minterms of $f_n$ produced by which is large enough: \[ |P|\geq \frac{1}{s}\cdot \mu_n\gtrsim \frac{1}{s}\cdot 2^{\sqrt{n}}. \] Lemmas A and B imply \[ |F|\geq |P^{\perp}|\gtrsim |P|\cdot 2^{n^{1/4}-\sqrt{n}} \gtrsim \frac{1}{s}\cdot 2^{\sqrt{n}}\cdot 2^{n^{1/4}-\sqrt{n}} = \frac{1}{s}\cdot 2^{n^{1/4}} \] Thus, $\max\{s, |F|\}=2^{\Omega( n^{1/4})}$. $\Box$Lemma B:For every subset $P$ of minterms of $f_n$, \[ |P^{\perp}| \gtrsim |P|\cdot 2^{n^{1/4}-\sqrt{n}}. \]

**Note** (observed by Igor Sergeev):
Recall that the function $f_n$ is defined as a read-once formula
having the form of alternating AND and OR gates
(see how it looks).
In 1984, Valiant has shown that the majority function $Maj_m$
of $n$ variables
can be computed by an alternating (not read-once) AND/OR tree of depth $5.3\log m$.
Thus, $Maj_m$ is a "subfunction" of $f_n$ for $n$ about $m^{5.3}$
which can be obtained from $f_n$ by setting some
variables to constants, and identifying some of the remaining variables.

**Acknowledgment:**

My thanks to Igor Sergeev for scanning and repairing
this (old, hardly available, and "scan-resistant")
paper, and
for very interesting discussions on the paper itself.

**Reference:**

- G.A. Tkachov (1980): On complexity of realization of a sequence of boolean functions by schemas of functional elements and $\pi$-schemes under additional restrictions on the structure of the schemas, in: Kombinatorno-Algebraicheskie Metody v Prikladnoj Matematike (Combinatorial-Algebraic Methods in Applied Mathematics), Gorkij, 161--207. For those who can read Russian, here is a scanned .djvu copy of his paper (23MB, be patient).

April 2013