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.



Detection of gaps in binary vector through linear methods
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.


