A theorem communicated by Ken Calvert

A theorem communicated by Ken Calvert

For reasons that are of no relevance here, Ken Calvert mentioned the following theorem at the ATAC. (I did not know it, though it is well-known; you can find it in one of the textbooks by Hopcroft et al.)

Define for natural $n$ (the parity") $p.n$ by

$$ \begin{array}{l} p. n \equiv (\mathrm {t h e n u m b e r o f 1 s i n t h e b i n a r y} \ r e p r e s e n t a t i o n o f n i s e v e n) \ \end{array} $$

Define a segment of a sequence to be a postfix of a finite prefix of the sequence.

Then the sequence $p\left( {n : 0 \leq n}\right)$ does not contain

The relevant properties of $p$ are

(0) $p \cdot \left( {2n}\right) \neq p \cdot \left( {{2n} + 1}\right)$ (1) $p \cdot \left( {{2n} - 1}\right) = p \cdot n$

Note Relation (0) captures when $p$ changes, relation (1) captures when $p$ remains unchanged. Together they define $p$ up to polarity, i.e. well enough for this theorem: the characterization "relevant properties" was no exaggeration. (End of Note.)

What can we conclude from (0) ? Let the

"imbalance" of a segment be defined as the number of times the one value occurs more often in the sequence than the other value. Relation (0) implies that the imbalance cannot be too big, more precisely, the imbalance is $\leq 2$ .

Let a segment of the form $\mathcal{V}\mathcal{V}\mathcal{V}$ occur in $P$ .

Then

$$ \begin{array}{l} i m b a l a n c e. y \ = \mathrm {i m b a l a n c e} \cdot (y y y) / 3 \ \leq 2 / 3 \ \end{array} $$

Hence $\operatorname{imbalance.}y = 0$ ,and therefore the length of $y$ is even, i.e. for some $h,k$ and $d = {0v}$

$$ \begin{array}{l} d = 1 \ y y y = p (n: 2 h - d \leq n \land n < 2 h - d + 6 k) \ \end{array} $$

From (1) we conclude the existence of an $x$ such that

$$ x x x = p (n: h \leq n \land n < h + 3 k) $$

the length of $x$ being half the length of $y$ . By mathematical induction, the length of $y$ is divisible by 2! for any $i > 0$ . Since each integer with an unbounded number of divisors equals 0, segment $yyy$ is empty. QED

*

A few remarks about the above argument are in order. To begin with a remark about its wording. We could have defined a segment to be a non-empty postfix, which would have "simplified"

the conclusion: no segment of the form yyy. But in terms of segments thus defined, the argument would almost unavoidably have become a reductio ad absurdum. For the experienced reasoner, our inclusion of the empty segment comes as no surprise.

For the experienced reasoner, the choice of (0) and (1) as basis for our little theory about $p$ comes as no surprise either. The theorem is insensitive for the replacement $p = 7p$ , and the argument is therefore properly conducted in terms of equality and difference. (This we have learned with the problem of the complete bichrome 6-graph.)

In short: the sweetness of this solution is another confirmation of the effectiveness of known principles. And that is why this argument has been recorded.

Nuenen, 7 January 1991

prof. dr. Edsger W. Dyrksha Department of Computer Sciences The University of Texas at Austin Austin, TX 78712 - 1188 USA