# Loaded Dice and Cyclotomic Polynomials

For what follows, we define a loaded die as a discrete probability distribution with six outcomes (labelled {1,…,6}), each of which has positive probability. To each such die, we associate a generating polynomial, given by

$p(t):=p_1t+p_2t^2+\ldots +p_6 t^6$

in which $p_i$ denotes the probability of the outcome i.  If $q(t)$ corresponds to another such die, we note that the product

$p(t)q(t) =\sum_i a_i t^i:=\sum_{i=2}^{12}\big( \sum_{k=1}^{i-1} p_k q_{i-k}\big) t^i$

has coefficients which reflect the probabilities of  certain dice sums for p and (and this is the utility of generating polynomials).  We are now ready to ask the following question:

Question: Does there exist a pair of loaded dice such that the probability of rolling any dice sum ({2,…12}) is equally likely?

Proof: Equivalently, we question the existence of  dice polynomials p and q such that

$p(t)q(t)=\frac{1}{11}\sum_{i=2}^{12} t^i = \frac{t^2(t^{11}-1)}{11(t-1)}.$

To see that the answer must be no, we observe that pq must then have precisely two real roots (counting with multiplicity).  On the other hand, p (resp. q) has at least two real roots (counting multiplicity), since $p(t)/t$ is a real polynomial of odd degree (hence admits a real root).  Thus pq has at minimum four real roots, and we have a contradiction. $\square$

An extension of this argument shows the following:

Theorem: There is no finite set of n>1 loaded dice such that the probability of any dice sum ({n,…6n}) is equally likely.

We can extend the class of loaded dice to the class of null-loaded dice by allowing the probabilities of certain die rolls to equal zero.  In this case, our theorem still holds: the proof holds verbatim provided that $p_6$ and $q_6$ remain non-zero, and if either is zero, our theorem holds trivially.  Moreover, we may consider the class of null-loaded k-sided dice, and ask if there exists a collection of n>1 such dice (throughout which may vary, in general) such that the probability of any (attainable) dice sum is equally likely.  If $k_i$ is fixed as our dice $\{d_i\}$ vary, we have the following:

Theorem: There is no simulation of a fair (m(k-1)+1)-sided die via dice sums on a collection of  m null-loaded k-sided dice.

Proof: If, to the contrary, such a collection were to exist, we may write

$\left(\sum^k a_{1,i}t^i\right)\cdots\left(\sum^ka_{m,i}t^i\right)=\frac{t^{m(k-1)+1}-1}{(m(k-1)+1)(t-1)}.$

Equating coefficients gives $\prod a_{j,0}=\prod a_{j,k}=1/(m(k-1)+1)$.  Moreover, consideration of the $x^k$ coefficient gives us

$\frac{1}{m(k-1)+1}\geq a_{1,k}\prod_{j\neq 1} a_{j,0}+ \ldots + a_{1,k}\prod_{j\neq 1} a_{j,0}$

$=\frac{1}{(m(k-1)+1)}\left(\frac{a_{1,k}}{a_{1,0}}+ \ldots + \frac{a_{m,k}}{a_{m,0}}\right).$

It follows by the AM-GM inequality that

$1\geq \frac{a_{1,k}}{a_{1,0}} + \ldots + \frac{a_{m,k}}{a_{m,0}} \geq m \sqrt[m]{\frac{a_{1,k}}{a_{1,0}}\cdots\frac{a_{m,k}}{a_{m,0}}}=m,$

which presents a contradiction for $m>1$. $\square$

Note: when k is even, this result admits a proof analogous to that given in the $k=6$ case.  If we restrict the scope of our previous theorem to loaded k-sided dice, the following is immediate:

Corollary: There is no simulation of a fair die via dice sums on a collection of m loaded k-sided dice.

Matters become far more complicated when $k_i$ is allowed to vary with the die $d_i$.  In this case, the simulation of a fair die via dice sums becomes possible:

Example:  Let $d_2$ denote the fair 2-sided die with outcomes $\{1,2\}$, and let $d_3$ denote the null-loaded 3-sided die with outcomes $\{1,2,3\}$ and respective probabilities $\{1/2,0,1/2\}$.  Then the dice sums for $d_2$ and $d_3$ have outcomes {2,3,4,5}, each of which is equally likely. (In other words, we may simulate a fair 4-sided die via dice sums of two fair 2-sided dice (as long as one die has been renumbered {1,3}.)

Underlying all of this lies the factorization of the polynomial

$\Psi_n(t):= \frac{t^n-1}{n(t-1)}$

into scaled cyclotomic polynomials. To wit, if $\Psi_n(t)$ may be written as a product of polynomials $f_i$ with non-negative coefficients such that $f_i(1)=1$, then the null-loaded $\deg f_i$-sided dice (now numbered $\{0,\ldots, \deg f_i -1\}$ for convenience) associated to the polynomials $f_i$ have equally probable dice sums.  In particular, it is an easy exercise to show that any fair m-sided die can be simulated as a null-loaded dice sum, provided that m is composite.  In what follows, we’ll prove just one theorem concerning varied $k_i$ (concerning the factorization of $\Psi_n(t)$ over $\mathbb{Q}[t]$).

Theorem: Suppose that the dice sums of a collection of n null-loaded $k_i$-sided dice $\{d_i\}$ simulate a fair m-sided die. If the probability of each outcome of $d_i$ is rational, then each non-null outcome of the die $d_i$ is equally likely.

Proof: Let $f_i \in \mathbb{Q}[t]$ denote the generating polynomials for the dice $d_i$ (numbered $\{0,\ldots,k_i-1\}$).  Then

$m f_1\cdots f_n = \frac{x^m-1}{x-1},$

and Gauss’s lemma gives rational constants $c_i$ such that $c_if_i \in \mathbb{Z}[t]$ (with $\prod c_i =m$).  Specifically, $c_i^{-1}$ is the constant term of $f_i$, and we note that each coefficient of $g_i:= c_i f_i$ is a non-negative integer.  Let $a_{ij}$ be the $x^j$ coefficient of $g_i$.  If $a_{ij}>1$, then the $x^j$ coefficient of $(x^m-1)/(x-1)$ exceeds 1 (by non-negativity of the coefficients), a contradiction.  Hence $a_{ij}$ is 0 or 1, and our result is immediate. $\square$

Some food for thought –

Exercise: We say that a null-loaded k-sided die (labelled {0,…k-1}) is primitive if the associated polynomial is irreducible in $\mathbb{Q}[t]$.  Prove that a fair m-sided die arises as the dice sum of a collection of primitive dice if and only if m is a prime power.