# Find Instance with Set Membership Condition

Given two vectors $u=(x_1,\ldots,x_n,a_1,\ldots,a_s) \in \{-1,1\}^{n+s}$ and $v=(x_1,\ldots,x_n) \in \{-1,1\}^n$ and a bunch of fixed vectors $c_1,\ldots,c_k \in \{-1,1\}^{n+s}$ and $b_1,\ldots,b_k \in \{-1,1\}^{n}$ and I want to find an instance when all the following (inner product) equations are satisfied: $$c_i \cdot u + 1 = b_i \cdot v,\quad i=1,\ldots,s$$

In general $n$ will be large. So I want to specify the condition that I am only interested in solutions in, say, $\{-1,1\}^{n+s}$ by using the membership of $u$ in Tuples[{-1,1},n+s] instead of putting numerous componentwise integer inequalities into play after specifying Integers as a condition. I will want to do this for varying $n$ and $s.$

Edit: A small example, done componentwise is below. I want to abstract out the equations by using inner products since they will get messy for larger cases. Here $n=s=1$ and I ask for 4 instances. ff allows me to specify +1 and -1 by using ff[x,1].

ff[x_, a_] := (x^2 == a);
FindInstance[
x1*xn + 1 == a1*(x1 + xn) &&  ff[x1, 1] && ff[xn, 1] &&
ff[a1, 1], {x1, xn, a1}, Integers, 4]

• It would be useful to have a small example, in Mathematica input form. – Daniel Lichtblau Dec 16 '15 at 23:39
• Where is your b1? – Dr. belisarius Dec 17 '15 at 1:55
• @belisariushassettled:For this case, it can be taken to be 1. – kodlu Dec 17 '15 at 2:15
• This example is nonlinear (it has products of variable a1 by variables x1 and xn). The description c_i.u+1==b_i.v is of a linear problem. – Daniel Lichtblau Dec 17 '15 at 17:21

Perhaps

e = {-1, 1};
SeedRandom;
n = 3;
s = 3;
k = 2;
aa = Array[a, s];
vv = Array[x, n];
uu = Join[vv, aa];
c = RandomChoice[e, {k, n + s}];
b = RandomChoice[e, {k, n}];

FindInstance[And @@ MapThread[#1.uu + 1 == #2.vv &, {c, b}] &&
(And @@    Thread[Abs[uu] == 1]), uu, Integers]

(*{{x -> 1, x -> 1, x -> -1, a -> 1, a -> 1, a -> 1}} *)

• Thank you, your MapThread and Thread commands show me how to do this. – kodlu Dec 17 '15 at 5:00
• No, no, no. This is not going to scale. – Daniel Lichtblau Dec 17 '15 at 17:26
• @DanielLichtblau I know. But n will be large doesn't set a scale either – Dr. belisarius Dec 17 '15 at 17:33
• What I meant by "to scale" was not "to the scale of the original question" but rather "to scale well on larger problems". I basically cribbed all your work, and made a minor tweak at the end, to get a method that will scale better. – Daniel Lichtblau Dec 17 '15 at 17:41

Here is a slight adjustment to the method proposed by @Dr.belisarius. I'll show with a larger set of variables though.

e = {-1, 1};
SeedRandom;
n = 11;
s = 11;
k = 2;
aa = Array[a, s];
vv = Array[x, n];
uu = Join[vv, aa];
c = RandomChoice[e, {k, n + s}];
b = RandomChoice[e, {k, n}];


Now just adjust so these are 0-1 variables, multiply each by 2 and subtract 1 to get the effect of being +-1.

soln =
FindInstance[
And @@ MapThread[#1.(2*uu - 1) + 1 == #2.(2*vv - 1) &, {c,
b}] && (And @@ Thread[0 <= uu <= 1]), uu, Integers]

(* Out= {{x -> 1, x -> 0, x -> 0, x -> 0, x -> 1,
x -> 0, x -> 0, x -> 1, x -> 0, x -> 1, x -> 1,
a -> 0, a -> 0, a -> 1, a -> 0, a -> 1, a -> 1,
a -> 0, a -> 0, a -> 0, a -> 1, a -> 0}} *)


Now undo the transformation to get the results in the desired set.

2*uu - 1 /. soln

(* Out= {{1, -1, -1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, -1, 1,
1, -1, -1, -1, 1, -1}} *)

• Veggy nice ... :) – Dr. belisarius Dec 17 '15 at 17:50