<p>I think $S_n$ can be written in terms of inequalities in the obvious way. Let
$$
Q_n = \{(x, y): x = \sum_{i = 0}^{n-1}{2^i y_i}, \forall i: 0 \leq y_i \leq 1\}.
$$</p>

<p>I claim that $Q_n = S_n$. First, obviously all $(x, y) \in S_n$ are also in $Q_n$, so $S_n \subseteq Q_n$. Second, fix a point $(x^*, y^*) \in Q_n$. Consider the probability distribution over $\{0, 1\}^n$ induced by picking $y_i = 1$ with probability  $y^*_i$, independently for each $i$. If $y$ is sampled from that distribution, then, by linearity of expectation,
$$
\mathbb{E}\ x = \mathbb{E} \sum_{i = 0}^{n-1}{2^i y_i} = \sum_{i = 0}^{n-1}{2^i y^*_i} = x^*.
$$
Therefore $(x^*, y^*)$ is in the convex hull of $S_n$, which proves $Q_n \subseteq S_n$.</p>

<p>BTW, this didn't really use anything special about $S_n$. Whenever you have the convex hull of the set $\{(x, y): y \in S, x = Ay\}$, and the convex hull of $S$ has a concise extended formulation, the same thing will work. The main point is that $x$ is a linear function of $y$. Here we used the fact that the cube $[0, 1]^n$ has a very easy formulation in terms of inequalities.</p>

CC BY-SA 3.0
2014-04-21T02:38:25.103Z
2014-05-30T14:04:16.590Z
2014-05-30T14:04:16.590Z
Sasho Nikolov
<p>Consider the following set.</p>

<p>$S_n =\{ (x,y) ~|~x \in \mathbb{Z}_+~\wedge~ y \in \{0,1\}^n ~\wedge~x=\sum_{i=0}^{n-1} 2^i y_i \}$</p>

<p>$S_n$ is a collection of pairs $(x,y)$, where $x$ is an integer between 0 and $2^n-1$ and $y$ is its binary representation. I'm interested in the convex hull of $S_n$; you can call it $P_n$. </p>

<p>Has $P_n$ been studied before? Does it admit a compact extended formulation?</p>

<linear-programming><integer-programming><polytope>
What is known about this binary representation polytope?
Austin Buchanan
# What is known about this binary representation polytope?

(Asked by: username_0 on 2014-04-21)

Consider the following set.

$S\_n =\{ (x,y) ~|~x \in \mathbb{Z}\_+~\wedge~ y \in \{0,1\}^n ~\wedge~x=\sum\_{i=0}^{n-1} 2^i y\_i \}$

$S\_n$ is a collection of pairs $(x,y)$, where $x$ is an integer between 0 and $2^n-1$ and $y$ is its binary representation. I'm interested in the convex hull of $S\_n$; you can call it $P\_n$.

Has $P\_n$ been studied before? Does it admit a compact extended formulation?

**Tags:** linear-programming, integer-programming, polytope

---

## 1 answers

### Answer by username_1 on 2014-04-21. Score: 6 | Accepted answer

I think $S\_n$ can be written in terms of inequalities in the obvious way. Let
$$
Q\_n = \{(x, y): x = \sum\_{i = 0}^{n-1}{2^i y\_i}, \forall i: 0 \leq y\_i \leq 1\}.
$$

I claim that $Q\_n = S\_n$. First, obviously all $(x, y) \in S\_n$ are also in $Q\_n$, so $S\_n \subseteq Q\_n$. Second, fix a point $(x^\*, y^\*) \in Q\_n$. Consider the probability distribution over $\{0, 1\}^n$ induced by picking $y\_i = 1$ with probability $y^\*\_i$, independently for each $i$. If $y$ is sampled from that distribution, then, by linearity of expectation,
$$
\mathbb{E}\ x = \mathbb{E} \sum\_{i = 0}^{n-1}{2^i y\_i} = \sum\_{i = 0}^{n-1}{2^i y^\*\_i} = x^\*.
$$
Therefore $(x^\*, y^\*)$ is in the convex hull of $S\_n$, which proves $Q\_n \subseteq S\_n$.

BTW, this didn't really use anything special about $S\_n$. Whenever you have the convex hull of the set $\{(x, y): y \in S, x = Ay\}$, and the convex hull of $S$ has a concise extended formulation, the same thing will work. The main point is that $x$ is a linear function of $y$. Here we used the fact that the cube $[0, 1]^n$ has a very easy formulation in terms of inequalities.


---

