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.

  • $\begingroup$ Thank Greg Martin for his answer, I check that it is correct! $\endgroup$ – 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.

  • $\begingroup$ Thanks a lot! I check that and your construction is correct. $\endgroup$ – wshjustin May 25 '15 at 10:54
  • $\begingroup$ Glad to hear it! Feel free to click that check mark that accepts answers you like :) $\endgroup$ – Greg Martin May 25 '15 at 22:24

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.