1
$\begingroup$

Is there a family $\mathcal{P}$ of integral polytopes and a polytope product $\star$ such that for every $n\in\mathbb N_{>1}$ $\exists p\in\mathcal{P}:vol(p)=n$ and

  1. $\forall q\in\mathcal{P}\backslash\{p\}\quad vol(q)\neq n$

  2. coordinates of $p$ are $b$ bits in length with $b\leq C\log\log n$ in bit length at a fixed $C>0$

  3. dimension $p$ satisfies upper bound $p\leq\frac{C'{\log n}}b$ at a fixed $C'>0$

  4. closed in the sense if $vol(p)=ab$ and $a,b\in\mathbb N_{>1}$ then $p=p_1\star p_2$ where $vol(p_1)=a$ and $vol(p_2)=b$ and so if $p\in\mathcal P$ represents a prime by volume it cannot be decomposed?

Is there any way to describe such a family so that given $n\in\mathbb N_{>1}$

  1. $p$ cannot be described in polynomial time from $n$?
Improve this question
$\endgroup$
7
  • $\begingroup$ Erm... As written, the family consisting of a single one-dimensional "polytope" $[0,2]$ satisfies all requirements. $\endgroup$
    – fedja
    Commented May 27, 2019 at 21:08
  • $\begingroup$ Maybe, but now you have trouble with prime $n$ and requirement 2. $\endgroup$
    – fedja
    Commented May 28, 2019 at 11:06
  • $\begingroup$ @fedja 2. and 3. gives $2^{O(\log\log n)\times\mbox{dimension}}\asymp(\log n)^{O\Big(\frac{\log n}{\log\log n}\Big)}\asymp poly(n)$)? If $p\in\mathcal P$ has prime volume then $p$ is non-decomposable. $\endgroup$
    – Turbo
    Commented May 28, 2019 at 11:21
  • $\begingroup$ I mean that there is no integral polytope of prime volume $n$ with all sidelengths much smaller than $n$ (unless your definition of "integral" is different from mine) $\endgroup$
    – fedja
    Commented May 28, 2019 at 11:42
  • $\begingroup$ @fedja My integral polytope just refers to vertices with integral coordinates. Perhaps product of several irrationals produce a prime? $\endgroup$
    – Turbo
    Commented May 28, 2019 at 12:03

0

Reset to default

You must log in to answer this question.