Why is the inner product of -1,+1 binary variables at most $n-2$ and not at most $n-1$?

Question

In short, if $x \neq u_i \in \{\pm1 \}^n$ then why is:

$$ \langle x, u_i \rangle \leq n-2 $$

but not:

$$ \langle x, u_i \rangle \leq n-1 $$

?

---

To add context:

I was reading understanding machine learning from theory to algorithms and it had claim 20.1 section 20.3 on the section of the expressive power of Neural Networks. In the proof it said to consider "binary" vectors $\{ \pm 1 \}^n$ (which I will call Rademacher vectors). Let $f$ be a Boolean function and consider the Rademacher vectors that make $f$ output 1. If we consider some $x \in \{ \pm 1\}^n$ such that $u_i \neq x$ then they claim that:

$$ \langle x, u_i \rangle \leq n-2 $$

Which I think is false. Isn't the correct statement:

$$ \langle x, u_i \rangle \leq n-1 $$

The reason I think this is if $x \neq u_i$ then there exists at least one entry in the vector that are difference. Call it entry/index $j$. Thus $x[j] \neq u_i[j] \implies x[j]u_i[j] -1 $ since they must have opposite sign and both are entries in Rademacher vectors. Thus since we only need 1 entry for this to be true we get $-1$ instead of $-2$. In more detail an inner product is:

$$ \langle x, u_i \rangle = \sum^n_{j=1} x[j] u_i[j]$$

since there are n terms we are adding, if we have n agreements then we have a sum of n, but if we have a single disagreement then we have only a decrease of 1, right? Is that correct or am I missing something super dum?

Answer 1

I just noticed that if we have one disagreement then we change one single entry from +1 to -1. Thus, the summation decrease by 1 because we are missing one of the +1's in the summation but on top of that because they are Rademacher vectors instead of simple binary 0,1 then it means that the +1 actually changes to -1, meaning the inner product decreases by an additional 1.

So it decreases by 2 cuz:

1. we lose a +1 in the summation
2. but we also replace the +1 with a -1

so total decrease is by two leading to $ \leq n-2$