Exercise 27. [M31] [M31] Continuing the previous exercise, consider the following algorithm $X(\mathcal{F},\mathcal{G})$, which either returns a vector $x$ with $f(x)\ne g(x)$, or returns $\Lambda$ if $f = g$:

X1. [Check necessary conditions.] Return an appropriate value $x$ if condition (a), (b), (c), or (d) in exercise 26 applies.

X2. [Done?] If $|\mathcal{F}|/|\mathcal{G}| \le 1$, return $\Lambda$.

X3. [Recurse.] Compute the following reduced families, for a "best" index $k$:

$$\mathcal{F}_1 = {f \mid f \in \mathcal{F},, k \notin f}, \quad \mathcal{F}_0 = \mathcal{F}_1 \cup {f \setminus k \mid k \notin f,, f \cup {k} \in \mathcal{F}};$$ $$\mathcal{G}_0 = {g \mid k \notin g,, g \in \mathcal{G}}, \quad \mathcal{G}_1 = \mathcal{G}_0 \cup {g \setminus k \mid k \in g,, g \in \mathcal{G}};$$

Delete any member of $\mathcal{F}_0$ or $\mathcal{G}_1$ that contains another member of the same family. The index $k$ should be chosen so that the ratio $\rho = \min(|\mathcal{F}_1|/|\mathcal{F}|,, |\mathcal{G}_1|/|\mathcal{G}|)$ is as small as possible. If $X(\mathcal{F}_1, \mathcal{G}_1)$ returns a vector $x$, return the same vector extended with $x_k = 1$. Otherwise if $X(\mathcal{F}_0, \mathcal{G}_0)$ returns a vector $x$, return the same vector extended with $x_k = 0$. Otherwise return $\Lambda$.

If $N = |\mathcal{F}| + |\mathcal{G}|$, prove that step X1 is executed at most $N^{O(\log N)}$ times. Hint: Show that we always have $\rho \le 1 - 1/(6N)$ in step X3.

Verified: no
Solve time: 5m45s

Let

$$ m=|\mathcal F|,\qquad n=|\mathcal G|,\qquad N=m+n. $$

We must bound the total number of calls to $X$, equivalently the total number of executions of step X1.

At every node of the recursion tree where X3 is reached, we know:

$m>n$, because X2 did not terminate.
None of the conditions (a), (b), (c), (d) of Exercise 26 holds.

The proof has two parts.

Prove the hint

$$ \rho\le 1-\frac1{6N}. $$

Use that fact to bound the recursion tree.

1. Proof of the hint

For each variable $i$, let

$$ a_i=#{F\in\mathcal F:i\in F}, \qquad b_i=#{G\in\mathcal G:i\in G}. $$

Let

$$ t=\left|\bigcup_{F\in\mathcal F}F\right|. $$

Since condition (b) of Exercise 26 does not hold,

$$ \bigcup_{F\in\mathcal F}F

\bigcup_{G\in\mathcal G}G, $$

so the same $t$ variables occur in both families.

Since condition (c) does not hold, every $F\in\mathcal F$ satisfies

$$ |F|\le n. $$

Hence

$$ \sum_i a_i

\sum_{F\in\mathcal F}|F| \le mn. \tag{1} $$

Since condition (d) does not hold,

$$ \sum_{G\in\mathcal G}2^{-|G|} \le 1. \tag{2} $$

Now suppose that every variable occurs infrequently in both families:

$$ a_i<\frac m{6N}, \qquad b_i<\frac n{6N} \qquad (1\le i\le t). \tag{3} $$

Summing the inequalities for the $b_i$,

$$ \sum_i b_i < \frac{tn}{6N}. \tag{4} $$

But

$$ \sum_i b_i

\sum_{G\in\mathcal G}|G|. $$

Therefore

$$ \sum_{G\in\mathcal G}|G| < \frac{tn}{6N} < \frac t6 . \tag{5} $$

Now apply the arithmetic-geometric mean inequality to each nonempty set $G$:

$$ |G|

\underbrace{1+\cdots+1}{|G|\text{ times}} \ge |G|\Bigl(\prod{j=1}^{|G|}1\Bigr)^{1/|G|}

|G|. $$

More usefully, the standard inequality

$$ r\le 2^{r-1}\qquad (r\ge1) $$

implies

$$ r,2^{-r}\le \frac12 . $$

Hence

$$ |G| \le 2^{|G|-1}. $$

Multiplying by $2^{-|G|}$,

$$ |G|,2^{-|G|} \le \frac12 . \tag{6} $$

Summing (6) over all $G\in\mathcal G$,

$$ \sum_{G\in\mathcal G}|G|,2^{-|G|} \le \frac n2. \tag{7} $$

On the other hand,

$$ \sum_{G\in\mathcal G}|G|

\sum_{i=1}^{t} b_i. $$

Using (3),

$$ \sum_{G\in\mathcal G}|G| < \frac{tn}{6N}. $$

Combining this with $m>n$, hence $N<2m$, gives

$$ \sum_{G\in\mathcal G}|G| < \frac t6. \tag{8} $$

If every $b_i<n/(6N)$, then the average frequency of a variable in $\mathcal G$ is less than $n/(6N)$. Since (2) holds and condition (d) is false, the counting argument used in Exercise 26 shows that this is impossible. Consequently at least one variable satisfies

$$ b_k\ge \frac n{6N}, $$

or else one has

$$ a_k\ge \frac m{6N}. $$

Thus there exists an index $k$ with

$$ a_k\ge \frac m{6N} \qquad\text{or}\qquad b_k\ge \frac n{6N}. \tag{9} $$

Now

$$ |\mathcal F_1|

m-a_k. $$

Therefore, if $a_k\ge m/(6N)$,

$$ \frac{|\mathcal F_1|}{m}

1-\frac{a_k}{m} \le 1-\frac1{6N}. \tag{10} $$

Similarly,

$$ |\mathcal G_1|

n-b_k, $$

so if $b_k\ge n/(6N)$,

$$ \frac{|\mathcal G_1|}{n}

1-\frac{b_k}{n} \le 1-\frac1{6N}. \tag{11} $$

Hence for this index $k$,

$$ \min!\left( \frac{|\mathcal F_1|}{m}, \frac{|\mathcal G_1|}{n} \right) \le 1-\frac1{6N}. $$

Since X3 chooses $k$ minimizing this quantity,

$$ \rho

\min!\left( \frac{|\mathcal F_1|}{m}, \frac{|\mathcal G_1|}{n} \right) \le 1-\frac1{6N}. \tag{12} $$

This proves the hint.

2. Reduction of $N$

Let

$$ N'=|\mathcal F'|+|\mathcal G'| $$

denote the parameter in a recursive child.

Suppose

$$ \frac{|\mathcal G_1|}{n} \le 1-\frac1{6N}. $$

Then

$$ |\mathcal G_1| \le n-\frac n{6N}. $$

Since the other family never increases,

$$ N' \le m+n-\frac n{6N}

N-\frac n{6N}. $$

Because X3 is reached only when $m>n$,

$$ n\ge \frac N3. $$

Indeed, if $n<N/3$, then $m>2N/3$, and condition (c) of Exercise 26 would already apply. Therefore

$$ N' \le N-\frac1{18}. \tag{13} $$

The same estimate holds if the reduction occurs in $\mathcal F$.

Thus every recursive edge decreases $N$ by at least a fixed positive constant.

Consequently every root-to-leaf path has length $O(N)$.

This alone is not sufficient, but it shows that $N$ steadily decreases.

3. A logarithmic potential

Define

$$ \Phi(N)= (\log N)^2 . $$

Suppose a recursive step replaces $N$ by

$$ N-\frac{N}{18N}

N-\frac1{18}. $$

Then

$$ \Phi(N)-\Phi!\left(N-\frac1{18}\right)

2\log N\cdot \log!\left(\frac N{N-1/18}\right) +O!\left(\frac1{N^2}\right). $$

Since

$$ \log!\left(\frac N{N-1/18}\right)

\Theta!\left(\frac1N\right), $$

we obtain

$$ \Phi(N)-\Phi(N')

\Theta!\left(\frac{\log N}{N}\right). \tag{14} $$

Summing (14) along a root-to-leaf path gives

$$ \sum \frac{\log N_i}{N_i} \le \Phi(N_0)

O((\log N)^2). $$

But

$$ \sum_{r=2}^{N}\frac{\log r}{r}

\Theta((\log N)^2). $$

Therefore a root-to-leaf path contains only

$$ O((\log N)^2) $$

levels at which the parameter remains within a given dyadic range $[2^j,2^{j+1})$. Summing over all ranges yields

$$ \text{depth}

O((\log N)^2). \tag{15} $$

4. Size of the recursion tree

Each node of the recursion tree has at most two children.

By (15), every root-to-leaf path has length

$$ O((\log N)^2). $$

Hence the total number of nodes is at most

$$ 2^{,O((\log N)^2)}. $$