Skip to main content
8 of 10
added 65 characters in body
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Family of polytopes whose measure respects multiplication?

Is there a family $\mathcal{P}$ of integral polytopes 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$
  1. coordinates of $p$ are $b$ bits in length with $b\leq C\cdot\log\log n$ in bit length at a fixed $C>0$
  1. dimension $p$ satisfies upper bound $p\cdot b=C'\cdot {\log n}$ at a fixed $C'>0$
  1. closed in the sense if $vol(p)=ab$ such that $a,b>1\in\mathbb N_{>1}$ then $p=p_1\star p_2$ for a polytope product $\star$ 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$?
Turbo
  • 13.9k
  • 1
  • 27
  • 76