19
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ Do you mean $v\in\{-1,0,1\}^n$? $\endgroup$ – Jack M May 7 '14 at 18:28
  • $\begingroup$ 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$ $\endgroup$ – JessicaK May 7 '14 at 18:42
  • 1
    $\begingroup$ @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. $\endgroup$ – juniper May 7 '14 at 19:06
10
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – juniper May 12 '14 at 20:43
  • $\begingroup$ 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. $\endgroup$ – juniper May 12 '14 at 20:50
  • 1
    $\begingroup$ Argument for the $\pm 1$ case is added now. $\endgroup$ – David E Speyer May 12 '14 at 23:35
  • 3
    $\begingroup$ 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? $\endgroup$ – Anush May 13 '14 at 11:58
  • 1
    $\begingroup$ @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$. $\endgroup$ – David E Speyer May 14 '14 at 7:18
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.