2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Sebastian Schlecht Aug 31 '16 at 17:03
  • $\begingroup$ 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. $\endgroup$ – Sebastian Schlecht Aug 31 '16 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.