Skip to main content
2 of 3
added 148 characters in body
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Is there a simple polyhedral characterization of these integral points?

Given $n\in\mathbb Z_{>0}$ consider the set of $n$-tuples $$(a_1,\dots,a_n)\in\mathbb Z_{\geq0}^n$$ on following simple conditions

  1. $0\leq a_i\leq 2^{2^n}-1$

  2. If $a_i=b_{i,2^{n}-1}2^{2^{n}-1}+\dots+b_{i,0}$ were $b_{i,j}\in\{0,1\}$ every $\{0,1\}^n$ tuple occurs as $(b_{1,j},\dots,b_{n,j})\in\{0,1\}^n$ at some unique $j\in\{0,\dots,2^n-1\}$.

  1. Is there a terminology for such $n$-tuples in literature?
  1. Is there a polyhedral characterization in $\mathbb R^n$ that captures such integer $n$-tuples?

Note if we have $O(2^n)$ integer variables we can do this trivially. I want to do this in $O(poly(n))$ integer variables and it might be possible.

Turbo
  • 13.9k
  • 1
  • 27
  • 76