# Which vectors can give zero inner products forever

For even positive integer $n$, consider an $n$-dimensional vector $v$ such that $v \in \{-1,0,1\}^n$. Now consider an infinite dimensional vector $w$ with $w_i \in \{-1,1\}$ and define $I_k = \sum_{i=1}^n v_i w_{i+k}$. In other words, $I_k$ is the inner product of $v$ with the $k$th subvector of $w$.

For how many vectors $v$ does there exist at least one vector $w$ such that $I_k=0$ for all $k$?

I can see three categories of $v$ which will work.

1. Clearly $v = 0$ is one such vector. Any $w$ will give zero inner products for ever.
2. Any vector where there are an even number of non-zero elements which are all next to each other and are all $1$ or all $-1$s. Let us call the number of $1$s or $-1$s $x$. In this case we just need a $w$ where every window of length $x$ has the same number of $1$s and $-1$s.
3. Any vector which has the same number of $1$s as $-1$s. In this case $w$ which is all $1$s or all $-1$s will do.

But how many others are there apart from these?

I now see I missed out a whole class of vectors $v$ which give zero inner products when aligned with $w = (1,-1,1,-1,1,\dots)$. For example $v= (-1,-1,-1,0,0,1)$.

• Do you mean $v\in\{-1,0,1\}^n$? – Jack M May 7 '14 at 18:28
• Sorry, my mistake there. Maybe I am just confusing the notation here but in your non-zero $v$ solution, if you take $w = [1,1,-1,-1,1,1,-1,-1,1,1,\dots]$ and $v = [1,1]$ then $I_{k} = 0$ when $k$ is odd and $I_{k} = 1$ when $k$ is even. I don't see how you could possibly get any solution other than $v=\mathbf{0}$ for an arbitrary $w$ and $n$ – JessicaK May 7 '14 at 18:42
• @JessicaK Let $n=2$ and the vector $v = (1,1)$ . The vector $w=(1,-1,1,-1,1,-1,\dots)$ will do. I only need to show that there exists a $w$ not that all $w$ will work. – juniper May 7 '14 at 19:06

I will show that the following are equivalent:

Define $v(t) = \sum_k v_k t^k$. I will show the following are equivalent.

(1) One of the roots of $v(t)$ is a root of unity.

(2) There is a nonzero solution $w_k$ where the $w_k$ remain bounded as $k \to \pm \infty$.

(3) There is a nonzero solution $w_k$ where all the $w_k$ are in $\{ -1, 0, 1 \}$.

I will also show that the following are equivalent.

(4) One of the roots of $v(t)$ is a $2^j$-th root of unity, for some $j$.

(5) The polynomial $v(t)$ is divisible either by $1-t$ or by $1+t^{2^{j-1}}$, for some $j$.

(6) The polynomial $v(t)$ is divisible by a polynomial of the form $1-t^m$ or $1+t^m$.

(7) There is a solution $w_k$ where all the $w_k$ are $\pm 1$.

Obviously, the bottom four are most restrictive than the top three.

To knock off the easy ones, clearly $(7) \implies (3) \implies (2)$ and $(4) \implies (1)$. Also, $(4)$ and $(5)$ are easily equivalent: I am just listing the cyclotomic polynomials for $2^j$-th roots of unity. Obviously, $(5) \implies (6)$. The reverse implication $(6) \implies (5)$ is almost as easy: $1-t^n$ is divisible by $1-t$, and, if $n = 2^j (2k+1)$, then $1+t^{2^j}$ divides $1+t^n$.

It is also easy to see that $(6) \implies (7)$: If $1-t^n$ divides $v(t)$ then take any $w_k$ with $w_{k+n} = w_k$; if $1+t^n$ divides $v(t)$ then take any $w_k$ with $w_k=-w_{k+n}$.

The remaining arguments, which will be harder, show $(1) \Longleftrightarrow (2)$, $(1) \implies (3)$ and $(7) \implies (4)$.

We first discuss the proof of $(1) \Longleftrightarrow (2)$, as it sets the context for all the others:

For fixed $v$, the relation $\sum_j v_{j} w_{k+j}=0$ gives a linear recurrence for the $w_i$. The general solutions to this recurrence are of the form $$w_k = \sum p_i(k) \alpha_i^k \quad (\ast)$$ where the $p_i$ are polynomials and the $\alpha_i$ are the roots of $v(t^{-1})$.

Suppose there is a bounded nonzero expression of the form $(\ast)$. Since we must remain bounded as $k \to \infty$ and $k \to - \infty$, we deduce that all the $\alpha_i$ have norm $1$. But the leading and trailing coefficients of $v(t)$ are $\pm 1$ and all the coefficients of $v(t)$ are integers, so the $\alpha_i$ are roots of unity (read the comments on the linked answer). Conversely, if $\alpha$ is a root of unity and a root of $v(t^{-1})$, then $w_k = \alpha^{-k}$ is a bounded solution to the recurrence. This establishes the equivalence of the first two points.

We now show $(7) \implies (1)$. From our discussion in $(1) \Longleftrightarrow (2)$, any bounded solution must be of the form $$w_k = \sum c_r \alpha_r^k$$ for $\alpha_r$ various roots of unity that are zeroes of $v(t)$. We assume that all the $c_r$ are nonzero (otherwise, discard the corresponding $\alpha_r$ from the list). Let $N$ be the LCM of the orders of the $\alpha_r$, so $w_k$ has period $N$. Let $N=2^k (2m+1)$. Suppose, for the sake of contradiction, that none of the $\alpha_r$ have $\alpha_r^{2^k}=1$. Set $\beta_r=\alpha_r^{2^k}$, so $\beta_r$ is a $(2m+1)$-th root of unity that isn't $1$.

Notice that $\sum_{j=0}^{2m} w_{2^k j}$ is a sum of $2m+1$ numbers which are $\pm 1$, so it is nonzero.

On the other hand, $$\sum_{j=0}^{2m} w_{2^k j} = \sum_{j=0}^{2m} \sum_r c_r \sum_{j=0}^{2m} (\alpha_r^{2^k})^j = \sum_{j=0}^{2m} \sum_r c_r \beta_r^j = \sum_{j=0}^{2m} \sum_r c_r \frac{\beta_r^{2m+1}-1}{\beta_r-1} = 0$$ where the last equality is because $\beta_r$ is a $(2m+1)$-th root of unity that isn't $1$.

The last, and hardest, argument is that $(1) \implies (3)$. Not strictly needed to answer your question, but I am proud of it.

Let $\alpha$, a primitive $n$-th root of unity, be a root of $v(t^{-1})$. Since the coefficients of $v(t)$ are integers, and the $n$-th cyclotomic polynomial is irreducible, all of the primitive $n$-th roots of unity are roots of $v(t)$. We will find a sequence $w_k$ so that all $w_k \in \{ -1, 0, 1 \}$ and $w_k$ can be written as $$w_k = \sum_{r,\ GCD(r,n)=1} c_r \alpha^{rk} \quad (\dagger)$$ for some constants $c_r$.

Define the polynomial $$f(t) = \prod_{p | n} (1-t^{n/p})$$ where the product is over primes dividing $n$.

Lemma Every coefficient of $f$ is $\pm 1$, and all of the exponents of $f$ are distinct modulo $n$.

Proof Let $r$ be the number of distinct primes dividing $n$. We claim that all $2^n$ exponents occurring in the product are distinct modulo $n$. Suppose to the contrary that $P$ and $Q$ are two different sets of primes dividing $n$ such that $$\sum_{p \in P} \frac{n}{p} \equiv \sum_{p \in Q} \frac{n}{p} \bmod n. \quad (\mathbb{S})$$ Since $P \neq Q$, we may assume that there is some $p$ in $P$ and not in $Q$ (or vice versa.) Let $p^e$ be the precise power of $p$ dividing $n$. Then reducing $(\mathbb{S})$ modulo $p^e$ gives $$p^{e-1} + 0 + \cdots + 0 \equiv 0+ \cdots + 0 \bmod p^{e-1}$$ an absurdity. $\square$

Let $g(t)=\sum_{k=0}^{n-1} g_k t^k$ be the polynomial formed from $f(t)$ by reducing the exponents of $f(t)$ modulo $n$ to lie between $0$ and $n-1$, while keeping the coefficients the same. Let $w_k$ be the sequence formed by repeating the coefficients of $g(t)$ periodically modulo $n$. So $w_k \in \{ -1, 0, 1 \}$, and we must check that $w_k$ can be written in the form $(\dagger)$.

So we have $$g_k = \sum_r c_r \alpha^{rk}$$ where $c_r$ is given by the discrete Fourier transform $$c_r = \frac{1}{n} \sum g_k \alpha^{-rk}.$$ If $r$ is NOT relatively prime to $n$, then $\sum g_k \alpha^{-rk} = g(\alpha^{-r}) = f(\alpha^{-r})=0$. So the only nonzero Fourier coefficients are the ones with $GCD(r,n)=1$, and $w_k$ is of the form $(\dagger)$, as desired.

• Thank you for this. This is really interesting although I have yet to fully absorb it all. The case I care about really is $\pm 1$. I would be very grateful for any thoughts on that. – juniper May 12 '14 at 20:43
• In fact I don't quite understand the case where the entries in $w$ are allowed to be in $\{-1,0,1\}$. We can just set $w$ to all zeros in that case so the answer is all possible vectors $v$. I must have misunderstood the variant you are solving. – juniper May 12 '14 at 20:50
• Argument for the $\pm 1$ case is added now. – David E Speyer May 12 '14 at 23:35
• I expect this is obvious to an expert, but does this answer mean there are vectors $v$ other than the ones the OP listed or not? – Anush May 13 '14 at 11:58
• @anush Take any of the solutions $v = (v_1, v_2, \ldots, v_k)$ that we already know about. Then $(v_1, v_2, \ldots, v_k, 0,0,\ldots, 0, v_1, v_2, \ldots, v_k)$ is also a solution. If I understand the OP's description correctly, then this provides new missing solutions. Perhaps the simplest way to state the description is that all solutions are either orthogonal to $w = (\ldots, 1, 0^n, 1, 0^n, 1, 0^n, 1, 0^n \ldots)$ or to $w = (\ldots, 1, 0^n, -1, 0^n, 1, 0^n, -1, 0^n \ldots)$, where $0^n$ means $n$ zeroes in a row, for some $n$. – David E Speyer May 14 '14 at 7:18

This may be helpful or not, but here I go:

let define $J_n = \{1,2 \cdots n\}$. Then we can rephrase the question in terms of functions. We are given a function $v:J_n \rightarrow \{-1,0,1\}$ and we are searching for a function $w: \mathbb{N} \rightarrow \{-1,1\}$ such that $\sum_{i = 1}^n v(i)w(i+k) = 0$ holds for any $k \in \mathbb{N} \cup \{0\}$.

Then we define $\mathcal{P}$ to be set of functions from $J_n$ to $\{-1,1\}$. Then we define subset $\mathcal{M} = \{w \in \mathcal{P} : \sum_{i=1}^n w(i)v(i) = 0\}$. Let define a relation in $\mathcal{M}$: Let $a,b \in \mathcal{M}$ then $$a \sim b \iff a(i+1) = b(i), i \in \{1,2 ,\cdots, n-1\}$$

if $a \sim b$, then $a$ and $b$ are "shift compatible": We can "glue" the last element of $b$ to $a$ and we can shift $v$ by one and the inner product condition holds.

Let define subset of $\mathcal{N} = \{ w \in \mathcal{M} : \exists x,y \in \mathcal{M} ~ s.t. ~ x \sim w \textit{ and } w \sim y \}$. If there exists subset of $\mathcal{N}$ such that $x_1 \sim x_2 \sim x_3 \sim \cdots \sim x_k \sim x_1$. then we can form a periodic function (vector) which will satisfy the inner product condition.

so if this reasoning is valid, then question is about existence of such subset of $\mathcal{N}$. This handles the case of periodic $w$, but is there non-periodic w?