This is a cross-post of two recent questions at math.stackexchange without answers: [Q1](https://math.stackexchange.com/q/4843357/573047 "Necessary and sufficient conditions of linear separability of labelled cube \$\\{0,1\\}^n\$") and [Q2](https://math.stackexchange.com/q/4695646/573047 "Explanation of Linear Separability on a 3D Cube").

A boolean function on an $n$-dimensional hypercube is [linearly separable](https://en.m.wikipedia.org/wiki/Linear_separability) when the convex hulls of the points evaluating to $0$ and $1$ respectively are disjoint.

A necessary condition is that any rectangle (not only the faces) formed by $4$ points of the hypercube is linearly separable.

**Is this condition also sufficient?**

I have tested that the number of linearly separable boolean functions ([OEIS A000609](https://oeis.org/A000609)) on $n \le 4$ variables is equal to the number of hypercubes with all rectangles formed by $4$ vertices linearly separable (these ones counted using [this answer](https://math.stackexchange.com/a/4851134/573047) and [this software](https://tio.run/##jVXbctpADH1ef4VKBgYH05jcHgpmph/QPmeG8uAr8dhsiG0SmA7fTnVZG2yaSfxgS9pzJK20K4fjVRgej1epDvNtFMOsrKL05fvz3Do3FaledW1RngYXtlRXZLOuojhJdQy/fj79VreuZeECvAXDrS7TlY4jyF/0CoLEga5l6wBhtXyuX23rr6VIzMADdypygfJkalkqeSlgSJaUV/EzA42f0ci2FBJVmsDwdZEuUVUqg5EHBfFUAbMZ@1AHVDtJrMV9x1wRkfxlGOTu1gSoEBsk7EfFeRmLNYOxh5hpA9hOlWIMOqfIWe2sggEGpPSKuNoWmgOLo9qCuz5IBdd@qnm7frEKHQif/QKuUX5bLJs66YvEqcyUgawHyZrU9fYCt9ntHXqtDXKzoPYtjbZrafuW5re0oKWFLS2qNUtpLMzdVKpA@4E5TKgOZRn6OhnytiZLB3r9qOfAQNtEwsSpOVhD3ihxNcw9eDDtkHV3l5hnKrZtTUL0GMG1eTzudu4sAIoGx7Daj2sODVXKHJTmGMohhUyOYcbHUIDXHjzSBrjS/CrzUrxZ6uZmg1esSoY9E6Mf/dE9aZPdnHPsobgnYeZJE0nhMAZSIwyAxNNlwAw5KOUsBMyNdeo7Js3dp7dkTqTOIXkXBr7Jxyc7FwfS@HSFCGb3qRJkL9/TKnyGIa4x2sBV6JcxuD9EUbtFtkTqGJPci4hxNiJNpgYUFLHPd6rhTzr8/9Hdj@m3Hbrb0CmRz8PffciffCX8/Yf0L2X/8AV6N3kSD/z2BUA4MQcnw2jXWMOOdbRvlqKzpZOVu3/jmfYfOGH@Mfi5j2j8P5hR5dD89/mW1oDgEhC0AOElIGwBoktAZEvVaIxIEp64GgxMTE@YovvwjfXg7GzXl7hdSKoj74885yXj8b6PRnLb2UyXdWBGlU2RXJvX1GkWeO6u797vXHzMPIA5TslHux5BBql5ZDhmpPTzXMaHZguBrda/5Hg83v8D)). Therefore the above condition is proven sufficient for $n \le 4$.

Using the suggestion on the below comment by @Fedor Petrov I was able to prove the conjecture for $n \le 5$ using [this updated software](https://tio.run/##jVbdb9owEH92/gqvFRU0dCSsq6YBlbbnrS97mcSiKZ/UJRiahBbU8bez@3BCXKYOHuK7@51/vjvbZ@KrWRzv9@dKx/k6SeW4rBK1fH9/67RNhdKz17YkV9GRTekKbc55kmZKp/L7l593Yui19a/ffgjfw5/jgLt8irprGG@uf1cyyvoSbZqHy8ee8@IIFOdyIr0RywXI/shxRLYsZBctilAYxlLD4Lo9R8BEoTLZfZyqAFQh5tKdyAI4RCHHY6IQO2A5rL6oiUFCjznKyBFl8gJgpCnSal1ompzmZXqwQHQ7zmgRKk1hhcUs7sv4PizkJchP06DJR49aC6vMh4SzYdsWZba2sNS8nA6DKVczeIXoJWCmVAp0Iz6w2HiuNts@fhYGXyHdXT1xY2lbSwstLbK02NISS1uVFRWXQvQCKDZmjLl4AeveQfcD3gyBKRjogUV77zVZYBjLGxiavYeSGQYScT@7Wl5Jv4fTBWZe4w0XnzIY6BzNicu4Xk6AHic2BSybuExKGF6dhYBkWQR5MFjBDaqy7hlEsgZzJ/mlz/q4q2uOhiPIfHOOQRibrcT0AzJxNMZzWHsOjz2H7IlFgNTBEUtK6BRoAiiFOU8E/7FxOjqC9qsutjCrQh241iiM@ezg15TpBVpBJj0U6dKQO0RJIEdjACxNAwgRL3Wl9DqlleBK4pfu1nmqE5W1pzfFf@Zg4Muz/reHDQOfSzUDL@Lo4LYyUj6rKr6XXUDr0OpJIg7LVHqfa1VspnPc6iuoxpZFWHPFkj9q3KIiDamLtFj8I5Z/kXhvkwyPSLyGBIM6LZQPb7D4p4Zy/QbJyfl8PInkOB1WdmYM2Q29ayg6mNxNyx6/srvbFpi0wLadL3UTBR2gwaQ5QTtzgJ36nD2FeQgT4InDlw1etbA3aoORBUY2GFtgbIOJBSY9U068XrzohCkuLsw6E57FeijfkR5Zd/PQz@z6UlqcFfLnpbnu5Aatg/retNUDXRerRy8YXqu8dN2R4RgMDAu/qd4mg1/PtAMCxaFXTrxNx/u0wf8Kpl/K21vp31ApKCDzOPjQ181T1zwSYOInzzlQauq9fdO6O3m@Jl5Nlh79HxCO/aDv938B) which took about $8$ minutes on my computer, which decreases to about $5$ minutes if I test the next boolean function on the rectangle where the previous one failed the linear separability test.

**UPDATE 2024-02-13**

Using [this software](https://codegolf.stackexchange.com/a/269865/100784) I was able to compute the expected value of $15028134$ for $n=6$ in $22$ hours, so now the conjecture is proven for $n \le 6$. Later this [other software](https://codegolf.stackexchange.com/a/270080/100784) did it even better in $2$ hours and $45$ minutes. However now it looks impossible to go further searching for a possible counterexample, unless a more advanced algorithm, exploiting some structure of the problem and with much lower computational complexity, is found.

**UPDATE 2024-02-16**

A [new software](https://codegolf.stackexchange.com/a/270106/100784), exploiting some symmetry, computed the case $n = 6$ in only $2$ seconds and the expected value $8378070864$ for $n = 7$ in $1$ hour and $19$ minutes. Therefore now the conjecture is true for $n \le 7$.