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 q (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 k 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.

a. w. walker

mathematics and miscellany

Loaded Dice and Cyclotomic Polynomials

Leave a Reply Cancel reply