# Cyclic consecutive zeros of binary sequence with prime length

I found a feature that if $N>5$ is a prime, and $M \triangleq \frac{N-1}{2}$ is also a prime, then we will always have a binary sequence $x_1,\ldots, x_N$ with $L=\frac{N-1}{2}$(or $L=\frac{N+1}{2}$) number of ones, so that for any $1 \leq m \leq M$, we have: \begin{align} \sum_{i,j:~i-j=\pm m (\mod N)} \mathbf{1}((x_{i},x_{j})=(0,0))= \begin{cases} \frac{N+1}{4} &\text{if} ~L=\frac{N-1}{2}\\ \frac{N-3}{4} &\text{if} ~L=\frac{N+1}{2} \end{cases} \end{align} where $\mathbf{1}$ is the indicator funciton, which means $\mathbf{1}(A)=1$ iff $A$ is true.

For example, if $N=7$ and $M=3$, we can find a sequence $1011000$ with $3$ ones, so that when $m=1,2,3$, the number of the consecutive zeros are all 2. Namely,

1) If $m=1$, we check $(x_1,x_2)$, $(x_2,x_3)$, $(x_3,x_4)$, $(x_4,x_5)$, $(x_5,x_6)$, $(x_6,x_7)$, $(x_7,x_1)$, exactly 2 of them are $(0,0)$

2) For $m=2$, we check $(x_1,x_3)$, $(x_3,x_5)$, $(x_5,x_7)$, $(x_7,x_2)$, $(x_2,x_4)$, $(x_4,x_6)$, $(x_6,x_1)$, again, exactly 2 of them are $(0,0)$.

3) For $m=3$, we check $(x_1,x_4)$, $(x_4,x_7)$, $(x_7,x_3)$, $(x_3,x_6)$, $(x_6,x_2)$, $(x_2,x_5)$, $(x_5,x_1)$, once more, exactly 2 of them are $(0,0)$.

Also, we can find $0100111$ with $4$ ones(which is the complement of the former sequence), so that when $m=1,2,3$, the number of consecutive zeros are all 1.

Dose anyone know why, or what feature of prime I can use to prove it? Thanks a lot.

• Thank Greg Martin for his answer, I check that it is correct! – wshjustin May 25 '15 at 10:54

I believe that if you define the binary sequence $x_1,\dots,x_N$ by $$x_k = \begin{cases} 1, &\text{if k is a quadratic residue modulo N}, \\ 0, &\text{otherwise}, \end{cases}$$ then standard Gauss sum manipulations show that this sequence has the property you describe.