9
$\begingroup$

Let $N$ variables $x_i \ge 0$ but not all of them be zero. One may fix $\sum_{i=1}^N x_i = 1$.

There are $P$ equations which need to be solved, with coefficients $a^k_i$ indexed with superscripts $k = 1 ... P$ and subscripts $i = 1 ... N$:

$$ a^1_1 x_1 + a^1_2 x_2 + \cdots + a^1_N x_N = 0\\ a^2_1 x_1 + a^2_2 x_2 + \cdots + a^2_N x_N = 0\\ \vdots \\ a^P_1 x_1 + a^P_2 x_2 + \cdots + a^P_N x_N = 0\\ $$

Let $P$ and $N$ be sufficiently large to come up with probabilistic statements (see below).

Allow only binary choices $a_i^k = \pm 1$. If all $P \cdot N$ many coefficients are chosen randomly with probability 0.5 for $\pm 1$, and if all coefficient vectors are in general position, then it is known [Thomas Cover, [Cover65]] that variables $x_i$ can be found which solve the equations for at least 50 % of all such random choices of coefficients, as long as $2 P < N$.
[Note: this is half as many equations than can be solved if there were no restrictions on the $x_i$. ]

Now define a different generative procedure for the binary coefficients as follows. Select randomly the coefficients in the first equation $a^1_i$. Let the other coefficients be $a^k_i = \prod_{j=1}^k a^1_{(1+[(j+i-1) \! \! \! \mod \! \! N])}$ (which are then also binary). To illustrate, the first three equations are $$ a^1_1 x_1 + a^1_2 x_2 + \cdots + a^1_N x_N = 0\\ a^1_1 a^1_2 x_1 + a^1_2 a^1_3 x_2 + \cdots + a^1_N a^1_1 x_N = 0\\ a^1_1 a^1_2 a^1_3 x_1 + a^1_2 a^1_3a^1_4 x_2 + \cdots + a^1_N a^1_1 a^1_2 x_N = 0\\ \vdots $$

Then numerical simulations indicate that variables $x_i$ can be found in the same sense as above as long as $1.7 P < N$. Already for small values, like $N =10$, the effect can be seen in simulations.

I.e. with this choice of coefficients, the equations are "easier" in the sense that more of them can be simultaneously solved.

Can anybody give a hint why this is so? (and possibly also how the ratio 1.7 can be calculated?) I was reading about equations with nonnegative coefficients but didn't get a handle on this problem. Also, a link might exist to elementary symmetric polynomials but I couldn't find material which elucidates this question.

[Cover65] Thomas M. Cover: "Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition". IEEE TRANSACTIONS ON ELECTRONIC COMPUTERS, Volume: EC-14, Issue: 3, June 1965, pp. 326 - 334.

$\endgroup$
  • $\begingroup$ The person perhaps best able to address this question is (was) Tom Cover. Unfortunately, he's no longer with us. $\endgroup$ – Mark L. Stone May 17 '18 at 12:59
  • $\begingroup$ @MarkL.Stone Do you mean Thomas Cover - en.wikipedia.org/wiki/Thomas_M._Cover? $\endgroup$ – Royi May 21 '18 at 16:19
  • $\begingroup$ Do you have a citation for the result due to Cover? $\endgroup$ – David Ketcheson May 28 '18 at 9:33
  • $\begingroup$ @DavidKetcheson I put it in the main text (bottom). $\endgroup$ – Andreas May 28 '18 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.