# Counting lattice points can some give all?

Given convex polytope $\mathcal P\subseteq\Bbb R^n$ with $\mathcal P_\Bbb Z\leq2^n$ integer points and given locations of $O(\log \mathcal P_\Bbb Z)$ integer points in some positions can we obtain $\mathcal P_\Bbb Z$ in $O(n^c)$ time at a $c>0$?

Does the location of revealed points affect the complexity?

Intuitively, specifying a small number of integer points in a small region of some polytope has almost no connection with the rest of the polytope, so the answer should be negative. To give a concrete example, let $P$ be an $n$-element poset and $\mathcal{O}(P)$ its order polytope (see http://math.mit.edu/~rstan/pubs/pubfiles/66.pdf). If you are given the facets of $\mathcal{O}(P)$ then computing the number of integer points is equivalent to computing the number $j(P)$ of order ideals of $P$ (which is at most $2^n$), and is known to be $\#P$-complete. Suppose $P$ is the disjoint union of an $n/2$-element antichain (say) and an $n/2$-element poset $Q$. Then we know the $(n/2)!$ order ideals of the antichain, which is far more than $\log_2 j(P)\leq n$. Moreover, $j(Q)=(n/2)!j(Q)$, and computing $j(Q)$ is $\#P$-complete. I doubt whether specifying any $n$ (or some much larger number) of order ideals of $P$ will be of much help in counting the total number of them.
• My intuition is that 'if there are special positions of the polytope in $\Bbb R^n$ that can let it have more points than other positions then there should be special points in the polytope which can give information on whether the polytope is in an abundant position or not and that information might be amplifiable to help count efficiently'. – Brout Nov 26 '17 at 22:56