Relation to Ehrhart polynomial with Uniqueness

Question

A set of relative prime, positive integers $A = [a_1, \dots, a_d]$ describe the restricted partition function $$ p_A(n) = \# \{(m_1,\dots,m_d)\in\mathbb{Z}^d: \textrm{ all }m_j \geq 0, \sum_{j=1}^d m_j a_j = n \} $$ I'm interested in a binary version of $p_A(n)$, namely $$ q_A(n) = \begin{cases} 1 \textrm{ if } p_A(n) \geq 1 \\ 0 \textrm{ if } p_A(n) = 0 \end{cases} $$ Let $P_A(n)$ and $Q_A(n)$ be the polynomial parts of $p_A(n)$ and $q_A(n)$, respectively. In fact, $p_A(n)$ is polynomial except the last coefficient term. Let us interpret $P_A(n)$ as the expected number of solution to the restricted partition and $Q_A(n)$ as the probability that there is a solution. Without the underlying structure, we could relate these quantities by: $$ Q_A(n) = 1 - \exp ( - P_A(n) ) $$

Given a specified $\alpha$, how to choose $A$ with $\alpha \approx \prod_{j=1}^N a_j$ such that $Q_A(n)$ is close to $1 - \exp ( - P_A(n) )$?

Example: $A = [49,51,100]$ is a bad choice, because $100$ gets "eaten" up by $49$ and $51$. Whereas $A = [49,63,81]$ is a better choice.

As is apparent, I am missing quite some terminology here, for example is there a name for $q_A(n)$?

Answer 1

Your function $q_A(n)$ is an indicator whether or not $n$ is representable as a nonnegative combination of $A$ and thus connected to the infamous Frobenius problem (also known as the coin-exchange problem and the chicken nuggets progblem): given $A$ (relatively prime), which is the largest integer that is not representable? Knowing $q_A(n)$ or, equivalently, its generating function $f_A(x) := \sum_{n \ge 0} q_A(n) \, x^n$, would mean you know everything needed for the Frobenius problem (and more): its solution is the degree of the polynomial $\frac 1 {1-x} - f_A(x)$.

It's not hard to see that $f_A(x)$ is a rational function with denominator $\prod_{a \in A} (1-x^a)$, and it's a fun exercise to prove that $f_{a_1,a_2}(x) = \frac{ 1 - x^{a_1 a_2} }{ (1-x^{a_1})(1-x^{a_2}) }$; you can then derive that $a_1 a_2 - a_1 - a_2$ is the solution to the Frobenius problem for $|A|=2$. There are beautiful (and almost as explicit) formulas for $f_A(x)$ when $|A|=3$, due to Marcel Morales [J. Algebra 140 (1991), no. 1, 12–25] and Graham Denham [Electron. J. Combin. 10 (2003), Research Paper 36]; one amusing (and computationally important) consequence is that the numerator has either 4 or 6 terms, for any $|A|=3$. In sharp contrast, Henrik Bresinsky [Manuscripta Math. 17 (1975), no. 3, 205–219] proved that for $|A| \ge 4$ there is no absolute bound on the number of terms in the numerator of $f_A(x)$.