Loaded Dice and Cyclotomic Polynomials

diceFor 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s