Short generating functions were first introduced by Barvinok to enumerate integer points in polyhedra. Adding in Boolean operations and projection, they form a whole complexity hierarchy with interesting structure. We study them in the computational complexity point of view. Assuming standard complexity assumption, we show that these functions cannot effectively represent certain truncated theta functions. Along the way, we will draw connection to ordinary number theoretic objects, such as the set of prime or square numbers. This talk assumes no prior knowledge of the subject. Some open questions will be offered at the end. Joint work with Igor Pak.