1
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ That is smart. I was hoping I could get it to work without auxiliary variables. If no-one does it without in a few days, then I will accept your answer. $\endgroup$ Dec 7, 2017 at 20:31
  • $\begingroup$ @DavorJosipovic You can do it without extra variables but the number of constraints will go up to $100N$ (well, perhaps I'm a bit too pessimistic, but $16N$ is definitely there). If I were you, I would go for $2N$ constraints and $N$ extra variables (i.e. use Max's suggestion) but if you are interested in such a trade-off, let me know and I'll post the corresponding set of linear inequalities. $\endgroup$
    – fedja
    Dec 8, 2017 at 2:01
  • $\begingroup$ @fedja I am definitly interested (or the general idea if it's too much work), and also to pointers/practices for finding such solutions. The quadratic solution I found through common-sense, but finding the linear one was not so obvious to me. $\endgroup$ Dec 8, 2017 at 7:08
  • $\begingroup$ Did some research on conversion from nonlinear to linear, and these are some links I found helpful: Tricks, McCormick envelope $\endgroup$ Dec 8, 2017 at 16:35
  • 1
    $\begingroup$ OK, just posted my 2 cents. Also it is $8N$ now (I just didn't notice that I could check conjugate pairs simultaneously when saying $16N$) $\endgroup$
    – fedja
    Dec 10, 2017 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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