# Relation to Ehrhart polynomial with Uniqueness

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)$?

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)$.
• Thank you very much for your answer, however I've got difficulties to connect it to the question. I try to clarify: I'd like to choose $A$ in such a way that the representable numbers are Poisson distributed, i.e., $min_A \epsilon(A) = min_A \sum_n || Q_A(n) - (1 - \exp(-P_A(n)))||$. The Frobenius problem is closely related, however too focused on a singular 'event', e.g., the Frobenius number is equal for $A_1 = [49,51,100]$ and $A_2 = [49,51]$, but $\epsilon(A_1)$ is larger than $\epsilon(A_2)$. – Sebastian Schlecht Aug 31 '16 at 17:03
• So far my very heuristic approaches have been: 1. avoid too many similar prime factors in $A$ (relatively prime might be too little), 2. avoid low order dependencies, i.e., $m^T A = 0$ with vector $m$ being small integers ($m$ for $A_1$ is $[1, 1, -1]$). 3. avoid clusters of numbers in $A$ being very close such as $[49,50,51]$. Sorry for this rather trail-and-error approach, but hopefully it can explain what I am after. – Sebastian Schlecht Aug 31 '16 at 17:13