From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math,de.sci.mathematik,aus.mathematics,alt.sci.math.combinatorics Subject: Re: Consecutive 1's in a vector? Date: 24 Sep 1997 20:41:53 GMT In article <5vp1em$9q3@winx03.informatik.uni-wuerzburg.de>, Peter Fleischmann wrote: >Let x \in R^n be a vector with components in {0,1}. >We know that there are exactly m 1's (m << n) in x. >We look for a set of test vectors {a_i} and scalars {b_i} >s.t. testing x via x^T a_i {<=>} b_i checks if all >the m 1's in x are consecutive, i.e. there is no '0' between >the first and the last '1'. There may be a nice geometric way to find a set of hyperplanes which separate the n-m+1 special vectors (0, 0, ..., 0, 1, 1, ..., 1, 0, ..., 0) from the other vectors in R^n having m 1's and n-m 0's, but here's an algebraic suggestion which might fit the bill for you. Consider the vector a = (1, zeta, zeta^2, ..., zeta^(n-1) ) in C^n, where zeta is a primitive k-th root of unity. The inner product of a with any of the special vectors differs by a root of unity from R = (zeta^m - 1)/(zeta - 1). On the other hand, the inner product of a with any of the other candidate vectors will be a sum of m roots of unity which, if distinct but not consecutive, will be of smaller magnitude. So if k >= 2n (forcing the summands of x.a to lie all on one side of the circle), we conclude this inner product has magnitude R iff the candidate vector is one of the special ones. If you insist on real vectors, you can mask these computations by computing the inner products with the real vectors u=(a+abar)/2 and v=(a-abar)/2i. For example, with n=4, we use k=8: u=(1,z,0,-z) and v = (0,z,1,z), where z = 1/sqrt(2). For each vector x compute (x.u)^2 + (x.v)^2. Among the vectors with 2 1's and 2 0's, this sum is 2+2z if x is one of the three special vectors, and smaller for the other three. Among the vectors with 3 1's and 1 0, this sum is 3+4z if x is one of the two special vectors, and smaller for the other two. We can use any k >= 2n, although the test becomes less numerically stable if we take larger k. By the way, by the same reasoning, if you want to alter the test to find as well the vectors which are "cyclically special" (e.g. (1, 1, 0, 0, 0, 0, 1) ) then use k=n. The test I provided can be interpreted to say that the special vectors are the ones outside a certain ellipsoid centered at the origin. For example, applied to the case n=3 and m=2, we see that the quadratic form Q(x,y,z)=x^2-xz+z^2 + y^2+xy+zy separates the two special vectors (Q=3) from the other one (Q=1). It's interesting to note that the quadratic form to be used is independent of m. dave ============================================================================== From: snowe@rain.org (Nick Halloway) Newsgroups: sci.math,de.sci.mathematik,aus.mathematics,alt.sci.math.combinatorics Subject: Re: Consecutive 1's in a vector? Date: 25 Sep 1997 17:59:53 GMT Dave Rusin (rusin@vesuvius.math.niu.edu) wrote: : In article <5vp1em$9q3@winx03.informatik.uni-wuerzburg.de>, : Peter Fleischmann wrote: : : >Let x \in R^n be a vector with components in {0,1}. : >We know that there are exactly m 1's (m << n) in x. : >We look for a set of test vectors {a_i} and scalars {b_i} : >s.t. testing x via x^T a_i {<=>} b_i checks if all : >the m 1's in x are consecutive, i.e. there is no '0' between : >the first and the last '1'. : : There may be a nice geometric way to find a set of hyperplanes which : separate the n-m+1 special vectors (0, 0, ..., 0, 1, 1, ..., 1, 0, ..., 0) : from the other vectors in R^n having m 1's and n-m 0's, : but here's an algebraic suggestion which might fit the bill for you. : : Consider the vector a = (1, zeta, zeta^2, ..., zeta^(n-1) ) in : C^n, where zeta is a primitive k-th root of unity. The inner product : of a with any of the special vectors differs by a root of unity : from R = (zeta^m - 1)/(zeta - 1). On the other hand, the inner product : of a with any of the other candidate vectors will be a sum of m : roots of unity which, if distinct but not consecutive, will be of smaller : magnitude. So if k >= 2n (forcing the summands of x.a to lie all on : one side of the circle), we conclude this inner product has magnitude R : iff the candidate vector is one of the special ones. Any k > n will do.