Detection of gaps in binary vector through linear methods Suppose I have a binary vector a = (0,1,1,1,0,0) of length $N$. I want to detect in a linear way whether a has any gaps in consecutive 1's. a as defined above has no gaps. But b = (0,1,0,1,0,0) has gaps.
Quadratic solution:
$$\sum_i^N a_i - \sum_i^{N-1}a_i a_{i+1} \le 1$$
Linear solution:
$$?$$
Is there a solution or a hint/proof that it is not possible?
This should be a constraint in an integer programming problem.
 A: Introduce binary variables $d_1,\dots,d_{N-1}$ and constraints:
$$-d_i \leq a_i - a_{i+1} \leq d_i,\quad i=1,\dots,N-1$$
and
$$a_1 + a_{N} + d_1 + \dots + d_{N-1} \leq 2.$$
A: OK, sorry for the delay. I just don't have too much free time nowadays.
Let $a_0,\dots,a_{n-1}$ be your string. Note that for any $z=e^{it}$, we have 
$$
P_a(z)=a_0+a_1z+a_2z^2+\dots+a_{n-1}z^{n}=\frac 1{z-1}\sum_s(z^{n_s}-z^{m_s})
$$
where $[m_s,n_s-1]$ ($s=1,2,\dots,p$) are the groups of successive $1$'s.
Thus, if you have just one group, you have the inequality 
$|z-1||P(z)|\le 2$ for all $z$. However, if you have two groups or more, this inequality will be violated. It is easy to see when $p\ge 3$ because the sum of $6$ or more powers of $z$ has quadratic mean at least $\sqrt 6$. However, even if you have just $(z-1)P(z)=F(z)=z^B-z^A+z^D-z^C$ with $A<B<C<D$, the function $F(z)\overline {F(z)}$ will have the zeroth Fourier coefficient $4$ and the rest will be $G(z)+G(\bar z)$ with 
$$
G(z)=-z^{D-A}-(z^{B-A}+z^{C-B}-z^{D-C})+(z^{C-A}+z^{D-B})
$$
and you can easily check that there may be only one cancellation between the parentheses, so $\|F\|_4^4=\|F\bar F\|_2^2\ge 4^2+2\cdot 4=24$ and you have the value of at least $\sqrt[4]{24}$ somewhere.
Now it is time to discretize. The trigonometric polynomials of degree $d$ integrate correctly if you just average over all $z$ with $z^{q}=1$ for any $q>d$. Since $|F|^2$ is of degree $n$ and $|F|^4$ is of degree $2n$, we will surely catch large values (if they are there) using $2n$ values of $z=e^{2\pi i /(2n+1)}$, $k=\pm 1,\dots,\pm n$ ($F(1)=0$, so we do not need to bother about it). Also, $|F(\bar z)|=|F(z)|$, so this count can be reduced to $n$.
However, you still need one-sided real inequalities, not complex ones with absolute values. This can be achieved by noticing that 
$|F|\le 2$ if and only if $\Re (wF)\le 2$ for all $w$ with $|w|=1$. We need to discretize again, so we need a polygon fitting between the circle of radius $2$ and that of radius $\sqrt[4]{24}$. The regular octagon is the first one to fit in ($\cos(\pi/7)<\frac{2}{\sqrt[4]{24}}<\cos(\pi/8)$), so we can use $8$ one-sided real inequalities per each $z$, giving us $8n$ restrictions total without extra variables.
