Explanation of proof of why connectedness is not conjunctively local of any order $k$

Question

I was reading Minsky's and Papert's book on perceptrons and I was reading theorem 0.6.1 and I was having a hard time understanding it. The theorem was about proving that the property "connected" was not a local property i.e. that you somehow had to see the whole picture to know if something was connected or not. In particular their prove shows that "connected" is not a conjunctively local property of any order (for definition of conjunctively local see appendix at the end of this question).

In particular goes as follows:

Suppose that $\psi_{CONNECTED}$ has order K. Then to distinguish between these two $k+1$-wide figures:

there must be some $\varphi_0$ such that $\varphi_0(X_0) = 0$, because $X_0$ is not connected. All $\varphi$'s have value 1 on $X_1$, which is connected. Now $ \varphi_0$ can depend on at most $k$ points, so there must be at least one middle square, say $S_j$, that does not contain one of these points.

This last sentence is the one that does not make sense to me. Why does there must be at least one middle square that does not contain one of these points? I don't understand this. When it says "these points" what does that mean? Why are we talking about the middle points? Why does that matter? Also, the sentence as a whole doesn't make sense to me nor its purpose.

Like the first two properties make sense:

1. of course there must exist a $\varphi_0$ that rejects $X_0$, since $\psi_{CONNECTED}$ can only work properly if all of its predicates say YES if and only if the shape is connected. Since $X_0$ is not connected then some predicate must reject it. That is clear.
2. For a similar reason its obvious that all the predicates say YES on $X_1$ since its connected. More precisely, that is the definition of connected according to $\psi_{CONNECTED}$, that all its predicates say YES. Since $X_1$ is connected then all its predicates must say YES.
3. Last part that does make sense before my brain gets confused is that of course $\varphi_0$ can depend on at most $k$ points. This is obvious from the definition of $\psi_{CONNECTED}$. i.e. we assume $\psi_{CONNECTED}$ is conjunctively local of order $k$ so all of the predicates $\varphi$ can only see $k$ points.

however, the existence of $S_j$ doesn't make sense to me and thus, the remaining of the proof remains a mystery to me. If anyone can clarify that and the remains of the proof that would be fantastic!

Also, for completion, the whole proof is provided in the appendix2.

---

Appendix::

Recall the definition of Conjunctively local:

A predicate $\psi$ is conjunctively local of order k if it can be computed by independently computing a set of functions $\varphi_1(X)$...$\varphi_n(X)$ and then combined by the results of another function $\Omega$ of n argument by a set $\Phi $ of predicates $\varphi$ such that each $\varphi$ depends no more than $k$ points on a 2D Euclidean plane $R$ and: $$ \psi(X) = \begin{cases} 1 \text{ if } \varphi(X) = 1 \text{ for every } \varphi \text{ in } \Phi \\ 0 \text{ otherwise. } \end{cases} $$

or directly from Minsky's and Papert's book:

---

Appendix 2:

Proof of theorem 0.6.1

Answer 1

The predicate $\varphi_0$ depends on at most $k$ points. There are $k+1$ middle squares. So $\varphi_0$ cannot depend on all of them. That is, there is a middle square that $\varphi_0$ does not depend on. Therefore, if we add that square, the value of $\varphi_0$ doesn't change, and so $\psi$ is still 0, even though the figure is now connected.

Answer 2

For the sake of an exercise I want to explain my understanding (and to provide a alternative explanation).

When $\psi_{CONNECTED}$ computes whether something is connected or not, each predicate $\varphi_i$ can only see at most $k$ squares/pixels. Therefore, we define $\varphi_0$ to be the predicate that returns 0 on the not connected figure $X_0$. Note that even in the "best case" $\varphi_0$ can never process all the middle points that separate the strips of $X_0$ (because $\varphi_0$ can only see at most $k$ squares/pixels and the shape $X_0$ is of length $k+1$, so it will always miss at least one square/pixel). Therefore, there will always be some middle square $S_j$ that is not processed by $\varphi_0$. Therefore, if we make this square connect the top and bottom strips of $X_0$ and call this new figure $X_2$, then this new figure presents a problem. The problem is that its a figure nearly identical to $X_0$ but that its connected. Note this means that $\varphi_0(X_0) = 0 $ but it also return $\varphi_0(X_2) = 0$ (but it should return 1). Why? because it doesn't matter which squares/pixels $\varphi_0$ process, it will process them identically in both $X_0$ and $X_1$. The only chance for it to process them differently for $X_2$ than in $X_1$ is if $\varphi_0$ processed $S_j$. However, $X_2$ was constructed such that $\varphi_0$ messed up and did not process $S_j$. Thus, this presents a contradiction. There is one shape $X_2$ where our big predicate $\psi_{CONNECTED}$ says not connected when it is in fact connected. Thus, it cannot be conjunctively local of any order because if it were we can always create a figure larger where we can make it mess up and not notice its actually connected.

In addition as the authors mentioned at the end, connected can of course be computed if some predicate $\varphi_i$ is allowed to see the whole 2D plane/image. However, this would be silly, since we need $k$ to be less than the size of the image, otherwise, we wouldn't really be constructing a meaningful definition for local. So we must have $k < |image| = | R | $.

Btw, thanks Yuval!