On the forged dice

Ehrhard Behrends

Abstract

It is a well–known exercise in elementary probability that it is impossible to forge two ordinary dice with numbers 1,…, 6 in such a way that when one throws both and takes the sum one gets the numbers 2, 3,…, 12 all with the same probability. Now let m ∈ N I . We will investigate for what families k_{1},…, k_{s} ∈ N I , s > 1, with k_{1} +⋯+k_{s} = m there are probabilities P_{1},…, P_{s} on {0,…, k_{1}},…, {0,…, k_{s}}, respectively, such that P_{1} ∗ ⋯ ∗ P_{s} is the uniform distribution on {0,…, m}; the preceding assertion is just the statement that for m = 10, k_{1} = k_{2} = 5 there are no such probabilities. It will be shown how the k_{1},…, k_{s} for which P_{1},…, P_{s} exist can be described explicitly (and how the P_{σ} look like in this case) in terms of the divisors of m + 1. In the case s = 2 the description reads as follows: Write m + 1 = g_{1} ⋯ g_{t} and define inductively k′_{1} := g_{t} − 1, k′′_{1} := 0, k′_{τ} := g_{t−τ+1}k′′_{τ−1} + g_{t−τ+1} − 1, k′′_{τ} = g_{t−τ+1}k′_{τ−1} for τ = 2,…, t; then k_{1} := k′_{t}, k_{2} := k′′_{t} admit P_{1}, P_{2}, and whenever the uniform distribution on {0,…, m} can be obtained by convolving probabilities P_{1}, P_{2} on {0,…, k_{1}} and {0,…, k_{2}} with k_{1} + k_{2} = m, then the tuple (k_{1}, k_{2}) can be obtained as (k′_{t}, k′′_{t}) (or (k′′_{t}, k′_{t})) as above. Many devisors give rise to many families k_{1},…, k_{s} so that our description can be considered as an extension of an old result of Raikov’s (which states that no k_{1},…, k_{s} exist if m + 1 is prime). Our original problem is equivalent with representing 1+x+⋯+x^{m} as a product of polynomials A_{1},…, A_{s} with nonnegative coefficients. Hence we get a catalogue of all such factorizations, and the explicit form of the measures P_{σ} (they are uniform on subsets of {0,…, k_{σ}}) gives rise to an explicit description of the partition of the (m + 1)–th roots of unity different from 1 which correspond to the factorization 1 + x + ⋯ + x^{m} = A_{1}(x) ⋯ A_{s}(x).

1. Introduction

Since the beginning of this century it has been of interest to decide whether a given distribution can be written in a nontrivial way as the convolution of two other distributions or, equivalently, whether a random variable is the sum of two independent variables. In particular the case of infinitely divisible distributions has been studied thoroughly because of its importance for generalizations of the central limit theorem. See [5], [6] and [8] for an extensive discussion of these connections and many historical comments.

The first example of an indecomposable distribution was given 1937 by Raikov [7] who showed that the uniform distribution on {0,…, m} cannot be written nontrivially as a convolution product provided that m + 1 is prime. By using an elementary result on lattice–like distributions (see e.g. th. 5.1.1 in [5]) one can easily show that this is equivalent with the assertion that there are no k_{1}, k_{2} ∈ N I with k_{1} + k_{2} = m such that there exist probability measures P_{1}, P_{2} on {0,…, k_{1}}, {0,…, k_{2}} with P_{1} ∗ P_{2} = uniform.

It has been also well–known for many years that it is impossible for n ∈ N I to find P_{1}, P_{2} on {0,…, n} such that P_{1} ∗P_{2} is uniform on {0,…, 2n}; students in elementary probability often make acquaintance with this fact in the disguise of the “forged dice”. The oldest reference seems to be [3], the same author treats this question under a different viewpoint in [4].

The present note is devoted to the problem whether for m, k_{1},…, k_{s} ∈ N I with k_{1} + ⋯ + k_{s} = m there are P_{1},…, P_{s} on {0,…, k_{1}},…, {0,…, k_{s}}, respectively, such that P_{1} ∗ ⋯ ∗ P_{s} is uniform. In section 2 we study reformulations in terms of factorizations of polynomials which will enable us to reduce our investigation to a question concerning unique additive representations of natural numbers. Section 3 contains the characterization we aim for in the framework of elementary number theory, and in section 4 we describe the necessary modifications to treat the variants dealing with probabilities and with roots of unity. This section contains also the discussion of some consequences, e.g.: If there exist P_{1}, P_{2}, are they uniquely determined? (No, they aren’t.) Is it likely or is it a rare event that, given m, k_{1}, k_{2} with k_{1} + k_{2} = m there are P_{1}, P_{2} on {0,…, k_{1}}, {0,…, k_{2}} such that P_{1} ∗ P_{2} is the uniform distribution? (It is rather unlikely for large m).

2. Preparations

Let m, k_{1},…, k_{s} ∈ N I be given such that k_{1} + ⋯ + k_{s} = m. Suppose that there exist probability measures P_{σ} on {0,…, k_{σ}}, σ = 1,…, s such that P_{1} ∗ ⋯ ∗ P_{s} is uniform. Let P_{σ} be defined by the numbers p_{j}^{σ} := P_{σ}({j}), σ = 1,…, s, j = 0,…, k_{σ}. Then

∏_{σ=1}^{s}(p_{0}^{σ} + p_{1}^{σ}x + ⋯ + p_{k_{σ}}^{σ}x^{k_{σ}}) = \frac{1}{m+1} (1 + x + ⋯ + x^{m}) so that – after dividing by ∏ p_{k_{σ}}^{σ}

– it follows that 1 + x + ⋯ + x^{m} can be written as a product A_{1}(x) ⋯ A_{s}(x) where the degree of A_{σ} is k_{σ}, the leading coefficient is one, and all coefficients are nonnegative. The converse is also true: whenever 1 + x + ⋯ + x^{m} is decomposed in this way (we will speak of a nonnegative (k_{1},…, k_{s})–decomposition) we get P_{1}, ⋯, P_{s} such that P_{1} ∗… ∗ P_{s} is the uniform distribution on {0,…, m}.

2.1 Lemma Let 1 + x + ⋯ + x^{m} = A_{1}(x) ⋯ A_{s}(x) be a nonnegative (k_{1},…, k_{s})– decomposition, where A_{σ}(x) = a_{0}^{σ} + a_{1}^{σ}x + ⋯ + a_{k_{σ}−1}^{σ}x^{k_{σ}−1} + x^{k_{σ}}.

(i) The A_{σ} have the following palindrome property:

a_{j}^{σ} = a_{k_{σ}−j}^{σ} for j = 0,…, k_{σ}. In particular a_{0}^{σ} = 1. (ii) a_{j}^{σ} ∈ {0, 1} for all σ, j.

Proof Clearly we may assume that s = 2 (by considering A_{σ}, ( ∏_{σ′≠σ} A_{σ′})). We will

write A, B and k, n instead of A_{1}, A_{2} and k_{1}, k_{2} and the coefficients will be denoted by a_{0}, a_{1},… and b_{0}, b_{1},. . ..

(i) The roots of 1 + x + ⋯ + x^{m} are precisely the w_{j} := exp(2πij/(m + 1)), j = 1,…, m. Now let w be a root of A. Since the a_{κ} are real, \overline{w} is also a root, but since w = w_{ℓ} for a suitable ℓ it follows that \overline{w} = 1/w. Hence A(x) = ∏(x − 1/w), where the w run through the roots of A. From this it follows easily that x^{k}A(1/x) = A(x), and this is just (i) for the polynomial A.

(ii) We have a_{κ}, b_{ν} ≥ 0 and hence a_{κ}, b_{ν} ∈ [0, 1]. Suppose that, e.g., some a_{κ} lies in ]0, 1[. Let κ_{0} be the smallest κ for which this happens; note that κ_{0} > 0 since, by (i), a_{0} = 1. By assumption 1 = b_{j} + b_{j−1}a_{1} + ⋯ + b_{1}a_{j−1} + a_{j} for j = 1,…, m (where b_{ν} = 0 for ν > n and a_{κ} = 0 for κ > k) and from this we get by induction on j that b_{0}, b_{1},…, b_{κ_{0}−1} ∈ {0, 1}, 0 < b_{κ_{0}} < 1. This yields a contradiction when evaluating the coefficient of x^{n}: 1 = b_{n}+b_{n−1}a_{1}+⋯+b_{n−κ_{0}}a_{κ_{0}} +⋯ ≥ 1+b_{n−κ_{0}}a_{κ_{0}} > 1 (since, by (i), b_{n−κ_{0}} = b_{κ_{0}}).

Note The proof shows that (i) is also valid if the A_{σ} have real (and not necessarily nonnegative) coefficients. For (ii), however, reality is not sufficient to have “simple” coefficients (e.g. 1 + x + x^{2} + x^{3} + x^{4} = (1 − 2 cos(\frac{2π}{5}) x + x^{2})(1 − 2 cos(\frac{4π}{5}) x + x^{2}).

In view of 2.1 ( ii) nonnegative (k_{1},…, k_{s})–decompositions of 1 + x + ⋯ + x^{m} are in one–to–one correspondence with families of sets Π_{σ} ⊂ {0,…, k_{σ}} (σ = 1,…, s) such that every j ∈ {0,…, m} has a unique representation j = j_{1} + ⋯ + j_{s} with j_{σ} ∈ Π_{σ}. In particular the product of the cardinalities of the Π_{σ} is m + 1, and this proves that there are no decompositions if m + 1 is prime (Raikov [7]).

It is also now clear that in the case of admissible k_{1},…, k_{s} the k’s have to be pairwise different: one has k_{σ} ∈ Π_{σ} for all σ, and k_{σ_{1}} = k_{σ_{2}} would give rise to two different representations of k_{σ_{1}} as j_{1} + ⋯ + j_{s} with j_{σ} ∈ Π_{σ}.

3. The characterization theorem

Families Π_{1},…, Π_{s} as above (i.e. Π_{σ} ∈ {0,…, k_{σ}}, (j_{1},…, j_{s}) ⟼ j_{1} + ⋯ + j_{s} is a bijection between Π_{1} × ⋯ × Π_{s} and {0,…, m}) will be called admissible (k_{1},…, k_{s})– families. In view of the description we have in mind it is convenient to observe that two different Π_{σ} have only 0 in their intersection so that the numbers α_{σ} := “the smallest strictly positive element of Π_{σ}” are different for different σ. We will say that the Π_{1},…, Π_{s} are canonically ordered if α_{1} < α_{2} < ⋯ < α_{s} (note that always α_{1} = 1). Occasionally it will be convenient to regard ({0,…, m}) also as an admissible family (where s = 1, k_{1} = m).

Part 1: A construction to obtain admissible families

Let m + 1 be written as m + 1 = g_{1}g_{2} ⋯ g_{t} with t, g_{τ} > 1. Then every j ∈ {0,…, m} can uniquely be represented as j = j_{1} + j_{2}g_{1} + j_{3}(g_{2}g_{1}) + ⋯ + j_{t}(g_{t−1} ⋯ g_{1}) with 0 ≤ j_{τ} < g_{τ}; in the case g_{1} = g_{2} = ⋯ = g_{t} =: g this reduces to the well–known g–adic representation of j.

This can be rephrased as: Π̂_{1},…, Π̂_{t} is an admissible (k̂_{1},…, k̂_{t})–family, where Π̂_{1} = {0,…, g_{1} − 1}, Π̂_{2} = {0, g_{1}, 2g_{1},…, (g_{2} − 1) g_{1}},…, Π̂_{τ} = (g_{τ−1}g_{τ−2} ⋯ g_{1}) {0,…, g_{τ} − 1} and k̂_{τ} = (g_{τ} − 1) g_{τ−1}g_{τ−2} ⋯ g_{1}. This family is canonically ordered since 1 < g_{1} < g_{2}g_{1} < · · ·.

Now let 2 ≤ s ≤ t be given and Δ_{1} ∪ ⋯ ∪ Δ_{s} be a partition of {1,…, t} into nonvoid subsets such that no Δ_{σ} contains two consecutive elements and such that the smallest element of Δ_{σ} is smaller than the smallest element of Δ_{σ+1}; we will speak of an alternating s–partition for short. Put Π_{σ} := ∑_{τ∈Δ_{σ}} Π̂_{τ}. Then every j ∈ {0,…, m} can uniquely be represented as

j_{1}+⋯+j_{s} with j_{σ} ∈ Π_{σ} so that Π_{1},…, Π_{s} is an admissible family (in fact a (k_{1},…, k_{s})– family with k_{σ} := ∑_{τ∈Δ_{σ}} k̂_{τ}). This family is canonically ordered by our assumption on

the Δ_{σ}.

Summing up we arrive at

3.1 Definition Suppose that m+1 = g_{1} ⋯ g_{t} (t, g_{τ} > 1) and that Δ_{1} ∪⋯∪Δ_{s} is an alternating s–partition of {1,…, t}. Then the family Π_{1},…, Π_{s} just constructed will be called the family derived from (g_{1},…, g_{t}; Δ_{1},…, Δ_{s}). It is a canonically ordered

(k_{1},…, k_{s})–family, where k_{σ} = ∑_{τ∈Δ_{σ}}(g_{τ} − 1) g_{τ−1} ⋯ g_{1}.

Examples (Here we will express subsets Π of {0,…, k} by the values of the characteristic functions; e.g. (1 1 0 0 0 0 1 1) stands for the subset {0, 1, 6, 7} of {0,…, 7}).

1. m = 23, m + 1 = 4 · 2 · 3, i.e. t = 3, (g_{1}, g_{2}, g_{3}) = (4, 2, 3). Here Π̂_{1} = (1 1 1 1), Π̂_{2} = (1 0 0 0 0 1), Π̂_{3} = (1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1). There is only one alternating 3–partition of {1, 2, 3}, nameyl Δ_{i} = {i}, and this gives rise to the (3, 4, 16)–family Π̂_{1}, Π̂_{2}, Π̂_{3}. Also there is only one alternating 2–partition in this case: Δ_{1} = {1, 3}, Δ_{2} = {2}, and we obtain the (19, 4)–family ((1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1), (1 0 0 0 1)).

2. Again with m = 23, let us try m+1 = 2·2·3·2 (t = 4, (g_{1}, g_{2}, g_{3}, g_{4}) = (2, 2, 3, 2)). Here the Π̂_{τ} are as follows: Π̂_{1} = (1 1), Π̂_{2} = (1 0 1), Π̂_{3} = (1 0 0 0 1 0 0 0 1), Π̂_{4} = (1 0 0 0 0 0 0 0 0 0 0 0 1).

There is the obvious alternating 4–partition which gives rise to the (1, 2, 8, 12)– family (Π̂_{1}, Π̂_{2}, Π̂_{3}, Π̂_{4}). As an example of an alternating 3–partition consider Δ_{1} = {1, 4}, Δ_{2} = {2}, Δ_{3} = {3}; this leads to the (13, 2, 8)–family ((1 1 0 0 0 0 0 0 0 0 0 0 1 1), Π̂_{2}, Π̂_{3}). And there is only one alternating 2–partition: Δ_{1} = {1, 3}, Δ_{2} = {2, 4}; this yields the (9, 14)–family ((1 1 0 0 1 1 0 0 1 1), (1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1).

Part 2: Every admissible family can be obtained in this way

3.2 Theorem Let (Π_{1},…, Π_{s}) be an admissible (k_{1},…, k_{s})–family; assume that it is canonically ordered (cf. the definition from the beginning of this section).

(i) There are t ≥ 1, g_{1},…, g_{t} > 1 with m + 1 = g_{1} ⋯ g_{t} and an alternating s–partition Δ_{1},…, Δ_{s} of {1,…, t} such that (Π_{1},…, Π_{s}) is the family derived from (g_{1},…, g_{t}; Δ_{1},…, Δ_{s}) in the sense of 3.1.

(ii) (Π_{1},…, Π_{s}) uniquely determine (g_{1},…, g_{t}; Δ_{1},…, Δ_{s}).

Hence there are precisely as many admissible families as there are (g_{1},…, g_{t}) with m + 1 = g_{1} ⋯ g_{t} and alternating partitions of {1,…, t}.

The proof will depend on the following lemmas.

3.3 Lemma Suppose that ({0,…, r}, Π) is an admissible family for {0,…, m}, i.e. every j ∈ {0,…, m} can uniquely be written as j = j_{1} + j_{2} with 0 ≤ j_{1} ≤ r and j_{2} ∈ Π. Then (r + 1)|(m + 1) and, with n := (m + 1)/(r + 1), the set Π is just the set {0, r + 1, 2(r + 1),…, (n − 1)(r + 1)}.

Proof Uniqueness of the representation j = j_{1} + j_{2} implies that |j − j′| > r for j, j′ ∈ Π, and gaps larger than r + 1 in Π would contradict the possibility of such representations.

3.4 Lemma Let (Π, Π̃) be an admissible family for {0,…, m} with 1 ∈ Π. Let r ≥ 1 be such that {0,…, r} ⊂ Π but r + 1 ∉ Π. Then

(i) r + 1 ∈ Π̃. (ii) Suppose that {i, i + 1,…, i + r′} ⊂ Π; then r′ ≤ r.

(iii) Let i ∈ Π be such that i − 1 ∉ Π; then i, i + 1,…, i + r ∈ Π. (iv) For j ∈ Π̃ and j′ ∈ Π such that j′ − 1 ∉ Π one has r + 1 | j, r + 1 | j′.

Proof This lemma is the crucial step towards the proof of 3.2. Particularly important is part (iii).

(i) This is obvious. (ii) Suppose that, for some i ∈ Π, one would have i, i + r + 1 ∈ Π. Then this would

yield two different representations of i + r + 1 as j_{1} + j_{2} with j_{1} ∈ Π and j_{2} ∈ Π̃, namely (i + r + 1) + 0 and i + (r + 1), a contradiction.

(iii) Suppose that (iii) does not hold; let i ∈ Π be the smallest element such that i − 1 ∉ Π, but i ∈ Π, i, i + 1,…, i + r ∈ Π is not true. Choose a maximal r′ such that i, i + 1,…, i + r′ ∈ Π; by assumption r′ + 1 ≤ r. Write i + r′ + 1 as j_{1} + j_{2} with j_{1} ∈ Π, j_{2} ∈ Π̃. Since i + r′ + 1 ∉ Π we have j_{2} > 0 and thus j_{2} ≥ r + 1. This gives j_{1} < i. We claim that j_{1} − 1 ∉ Π. This is clear if j_{1} = 0 and if j_{1} > 0 we consider the identity i + r′ = (i + r′) + 0 = (j_{1} − 1) + j_{2} which shows that j_{1} − 1 ∈ Π would yield two different representations of i + r′ by elements of Π and Π̃. Thus j_{1} ∈ Π, j_{1} − 1 ∉ Π and j_{1} < i. Since i was the smallest element for which (iii) does not hold it follows that j_{1}, j_{1}+1,…, j_{1}+r ∈ Π. In particular we have j_{1}+(r−r′) ∈ Π as well as j_{1} +(r −r′) < i which leads to two different representations of i+r +1: i + r + 1 = i + (r + 1) = (j_{1} + (r − r′)) + j_{2} (i, j_{1} + (r − r′) ∈ Π, r + 1, j_{2} ∈ Π̃). This contradiction proves (iii).

(iv) Let Π′ := {i | i ∈ Π, i − 1 ∉ Π} (possibly Π′ = {0}). By (ii) and (iii) every j ∈ Π can uniquely be written as j = j′ + j′′ with j′ ∈ {0,…, r} and j′′ ∈ Π′. Hence every j ∈ {0,…, m} has a unique representation j = j_{1} + j_{2} with j_{1} ∈ {0,…, r} and j_{2} ∈ Π′ + Π̃. Thus the assertion follows from the preceding lemma.

Proof of the theorem We proceed by induction on m. The theorem is obviously true for m = 1, and we will assume that it has already been proved for all s ≥ 2 and all m̃ < m.

Let s ≥ 2 and (Π_{1},…, Π_{s}) be a canonically ordered (k_{1},…, k_{s})–family for {0,…, m}.

In order to prove (i) we have to exhibit g_{1},…, g_{t} with g_{1} ⋯ g_{t} = m + 1 and a partition of {1,…, t} as Δ_{1} ˙∪ ⋯ ˙∪Δ_{s} such that (1) Δ_{σ} ≠ ∅

(2) for no σ and no j one has j, j + 1 ∈ Δ_{σ}

(3) the smallest element of Δ_{σ} is smaller than the smallest element of Δ_{σ+1}

(4) with Π̂_{τ} := g_{τ−1} ⋯ g_{1}{0,…, g_{τ} − 1} one has Π_{σ} = ∑_{τ∈Δ_{σ}} Π̂_{τ} for all σ.

To this end consider Π := Π_{1} and Π̃ := Π_{2} + ⋯ + Π_{s}. By assumption 1 ∈ Π_{1} so that we may apply Lemma 3.3: there is an r ≥ 1 such that Π = {0,…, r} + Π′, and r + 1 divides all elements of Π′ + Π̃. In particular r + 1 divides the largest element n of Π′ + Π̃, and since m = n + r this means that (r + 1) | (m + 1). Let m̃ := (m − r)/(r + 1) (= our candidate to apply the induction hypothesis). We set Π̃_{1} := Π′/(r + 1), Π̃_{σ} := Π_{σ}/(r + 1) for σ > 1 and suppose for the moment that all Π̃_{σ} are different from zero (in fact Π̃_{1} could be zero: this happens if Π_{1} was just {0,…, r}, we will discuss this case later). Then (Π̃_{1},…, Π̃_{s}) constitutes an admissible (k̃_{1},…, k̃_{s})–family for m̃; here k̃_{1} := (k_{1} − r)(r + 1), k̃_{σ} := k_{σ}/(r + 1) for σ > 1, and all these numbers are strictly positive. We want to apply our induction hypothesis, but the Π̃_{1},…, Π̃_{s} are not necessarily canonically ordered (they will have this property possibly only after a suitable permutation). Nevertheless, if we neglect the possible permutation, there are g̃_{1},…, g̃_{t} with g̃_{1} ⋯ g̃_{t} = m̃ + 1 and nonvoid disjoint subsets Δ̃_{σ} of {1,…, t̃} with Δ̃_{1} ∪ ⋯ ∪ Δ̃_{s} = {1,…, t̃} such that no Δ̃_{σ} contains consecutive

j, j + 1, and Π̃_{σ} = ∑_{τ∈_{Δ_{σ}}} g̃_{τ−1} ⋯ g̃_{1}{0,…, g̃_{τ} − 1}.

By the definition of the Π̃_{σ} this means that Π_{σ} = ∑_{τ∈_{Δ_{σ}}} g̃_{τ−1} ⋯ g̃_{1}(r + 1) {0,…, g̃_{τ} − 1}

for σ > 1, and Π_{1} = ( ∑_{τ∈_{Δ_{1}}} g̃_{τ−1} ⋯ g̃_{1}(r + 1) {0,…, g̃_{τ} − 1}) + {0,…, r}.

Now note that m + 1 = (r + 1)(m̃ + 1) so that m + 1 = g_{1}g_{2} ⋯ g_{t} if we set g_{1} := r + 1, t := t̃+ 1, g_{τ} := g̃_{τ−1} for τ > 1. Also Π_{σ} = ∑_{τ∈Δ_{σ}} g_{τ−1} ⋯ g_{1}{0,…, g_{τ} − 1} is valid if

we put Δ_{1} := {1} ∪ {τ + 1 | τ ∈ Δ̃_{1}}, Δ_{σ} := {τ + 1 | τ ∈ Δ̃_{σ}} for σ > 1. This is nearly that which has to be shown, only (2) and (3) remain to be proved. (2) needs a verification only for σ = 1, and there it is the assertion that 1 ∉ Δ̃_{1}. But this is just the statement r + 1 ∉ Π_{1} which is clear from the construction.

And (3) follows from the fact that the Π_{1},…, Π_{s} are in canonical order: by assumption α_{σ}, the smallest positive element of Π_{σ}, is smaller than α_{σ+1} = the smallest positive element of Π_{σ+1}. But from our construction, α_{σ} = g_{τ_{σ}−1} ⋯ g_{1}, where τ_{σ} = min Δ_{σ}, so that α_{σ} < α_{σ+1} gives τ_{σ} < τ_{σ+1}.

It remains to treat the necessary modifications if Π′ = {0}. In this case we proceed similarly, but we only have to consider the Π̃_{2},…, Π̃_{s} above which give rise to g̃_{1},…, g̃_{t} and {1,…, t̃} = Δ̃_{2} ˙∪ ⋯ ˙∪Δ̃_{s} according to the induction hypothesis. Construct the Δ_{σ} from the Δ̃_{σ} as above for σ > 1 and put additionally Δ_{1} := {1}.

The proof of (i) is complete, let us turn to the uniqueness part (ii). So suppose that Π_{1},…, Π_{s} is a canonically ordered (k_{1},…, k_{s})–family, derived from (g_{1},…, g_{t}; Δ_{1},…, Δ_{t}) and also from (g̃_{1},…, g̃_{t}; Δ̃_{1},…, Δ̃_{t}). Then g_{1} = g̃_{1} since this number is by construction that integer r for which {0,…, r} ⊂ Π_{1} but r+1 ∉ Π_{1}. Now pass as in the proof of (i) from Π_{1},…, Π_{s} to Π̃_{1},…, Π̃_{s}; it should be clear how uniqueness of the representation of Π̃_{1},…, Π̃_{s} (more precisely: of its canonically ordered rearrangement) gives rise to uniqueness for the original family so that it is simple to establish (ii) by induction.

In order to illustrate the theorem it seems to be convenient first to summarize our proof. Let us start with an admissible (k_{1},…, k_{s})–family Π_{1},…, Π_{s}. We do not assume that it is canonically ordered. Define σ(1) to be that number σ for which 1 ∈ Π_{σ} and g_{1} := r + 1, where r is such that {0,…, r} ∈ Π_{σ(1)}, r + 1 ∉ Π_{σ(1)}. Now define a new family, Π_{1}^{(2)},…, Π_{s}^{(2)} by Π_{σ}^{(2)} := Π_{σ}/g_{1} for σ ≠ σ(1), and Π_{σ(1)}^{(2)} := {i | i ∈ Π_{σ(1)}, i − 1 ∉ Π_{σ(1)}}/g_{1} (it might happen that Π_{σ(1)}^{(2)} = {0}). Suppose that g_{1},…, g_{τ}, σ(1),…, σ(τ) and Π_{1}^{(τ+1)},…, Π_{s}^{(τ+1)} already have been constructed. If this is not the family {0},…, {0} there is a unique σ(τ + 1) with 1 ∈ Π_{σ(τ+1)}^{(τ+1)}, and g_{τ+1} will be one plus that number r for which {0,…, r} ∈ Π_{σ(τ+1)}, r + 1 ∉ Π_{σ(τ+1)}^{(τ+1)}. Pass from Π_{σ}^{(τ+1)} to Π_{σ}^{(τ+2)} similarly as we have got the Π_{σ}^{(2)} from the Π_{σ} (where σ(τ + 1) has to be treated in a different way than the other indices). Thus we find g_{1},…, g_{t}, σ(1),…, σ(t) until this reduction stops with Π_{σ}^{(t+1)} = {0} (all σ). Then, with Δ_{σ} := {τ | σ(τ) = σ} the original family is derived from (g_{1},…, g_{t}; Δ_{1},…, Δ_{t}), and if the Π_{1},…, Π_{s} have been in canonical order the Δ_{1},…, Δ_{t} will automatically be an alternating partition.

As an example consider the family constructed after definition 3.1, i.e. Π_{1} = (1 1 0 0 1 1 0 0 1 1), Π_{2} = (1 0 1 0 0 0 0 0 0 0 0 0 1 0 1).

With the previously introduced notation we get:

σ(1) = 1 , g_{1} = 2 ; Π_{1}^{(2)} = (1 0 1 0 1) , Π_{2}^{(2)} = (1 1 0 0 0 0 1 1) ;
σ(2) = 2 , g_{2} = 2 , Π_{1}^{(3)} = (1 1 1) ,  Π_{2}^{(3)} = (1 0 0 1) ;
σ(3) = 1 , g_{3} = 3 ; Π_{1}^{(4)} = (0) ,  Π_{2}^{(4)} = (1 1) ;
σ(4) = 2 , g_{4} = 2 ; Π_{1}^{(5)} = (0) ;  Π_{2}^{(5)} = (0) .

It follows that Π_{1}, Π_{2} is derived from (2, 2, 3, 2; {1, 3}, {2, 4}) (which in this case we knew in advance).

In the case s = 2 the σ(τ) will be alternating, e.g. σ(1) = σ(3) = ⋯ = 1, σ(2) = σ(4) = ⋯ = 2 (if 1 ∈ Π_{1}) or vice versa (if 1 ∈ Π_{2}). This gives immediately the

3.5 Corollary Let m, k_{1}, k_{2} be such that m = k_{1} + k_{2} and that there are Π_{1} ⊂ {0,…, k_{1}}, Π_{2} ⊂ {0,…, k_{2}} such that every j ∈ {0,…, m} can uniquely be written as j = j_{1} + j_{2} with j_{1} ∈ Π_{1}, j_{2} ∈ Π_{2}; suppose that 1 ∈ Π_{1}. Then there are g_{1},…, g_{t} with g_{1} ⋯ g_{t} = m + 1 for which one has

\begin{matrix}k_{1} = (g_{1} − 1) + (g_{3} − 1) g_{2}g_{1} + (g_{5} − 1) g_{4}g_{3}g_{2}g_{1} + ⋯, \\ k_{2} = (g_{2} − 1) g_{1} + (g_{4} − 1) g_{3}g_{2}g_{1} + (g_{6} − 1) g_{5}g_{4}g_{3}g_{2}g_{1} + · · · . \end{matrix}

k_{1}, k_{2} can also be obtained as follows: Put k′_{1} := g_{t} − 1, k′′_{1} := 0, k′_{τ} := g_{t−τ+1}k′′_{τ−1} + g_{t−τ+1} − 1, k′′_{τ} := g_{t−τ+1}k′_{τ−1} for τ = 2,…, t; then (k_{1}, k_{2}) = (k′_{t}, k′′_{t}) or = (k′′_{t}, k′_{t}) (depending on whether t is even or odd).

4. Consequences

A. For what (k_{1},…, k_{s}) are there admissible families?

Let (k̃_{1},…, k̃_{s}) be fixed and m := k̃_{1}+⋯+k̃_{s}. Is there an admissible (k̃_{1},…, k̃_{s})–family in canonical order? One has to check all decompositions of m + 1 as m + 1 = g_{1}g_{2} ⋯ g_{t} and all alternating s–partitions of {1,…, t} to decide whether one possibility leads to (k̃_{1},…, k̃_{s}). If the canonical order is of no importance, it has to be calculated whether a permutation of the family derived from (g_{1},…, g_{t}; Δ_{1},…, Δ_{s}) leads to a family with the desired properties.

Examples

1) Is there an admissible (5, 8)–family? There are only two decompositions of 5+8+ 1 = 14 : 2 · 7 and 7 · 2. They lead (with the help of cor. 35) to the (1, 12)–family ((1 1), (1 0 1 0 1 0 1 0 1 0 1 0 1) and the (6, 7)–family ((1 1 1 1 1 1 1), (1 0 0 0 0 0 0 1)), respectively. Hence there is no (5, 8)–family.

2) Let’s check the existence of (3, 8)–families. The decompositions of 3 + 8 + 1 as 2 · 6, 6 · 2, 3 · 4, 4 · 3, 2 · 2 · 3, 2 · 3 · 2, 3 · 2 · 2 lead to (1, 10)–, (5, 6)–, (2,9)–, (3,8)–, (9,2)–, (7,4)–, (8,3)–families. Therefore there are even two different (3,8)–families Π_{1}, Π_{2} (but only one where 1 ∈ Π_{1}): ((1 1 1 1), (1 0 0 0 1 0 0 0 1)) and ((1 0 0 1), (1 1 1 0 0 0 1 1 1)).

B. Are the (k_{1},…, k_{s})–families unique if there exist any?

The preceding example shows that there can be different (k_{1}, k_{2})–families. It might be, however, that there is always at most one canonically ordered (k_{1}, k_{2})–family as in this example. But this is not the case; the following proposition shows how non–uniqueness is caused by certain divisors of m + 1:

4.1 Proposition

(i) Suppose that 12 | (m + 1). Then there exist k_{1}, k_{2} with k_{1} + k_{2} = m for which there are two different (k_{1}, k_{2})–families (Π_{1}, Π_{2}) (one where 1 ∈ Π_{1}, and another where 1 ∈ Π_{2}).

(ii) Let m be such that 36 | (m + 1) or 150 | (m + 1). Then one can find k_{1}, k_{2} with k_{1} + k_{2} = m such that there exist two different canonically ordered (k_{1}, k_{2})– families.

Proof

(i) Let h_{1} ⋯ h_{t} be any decomposition of (m + 1)/12. Then 4 · 3 · h_{1} ⋯ h_{t} and 3 · 2 · 2 · h_{1} ⋯ h_{t} are decompositions of m + 1 which we denote by g_{1} · · · · · g_{t} and g_{1}^{∗} ⋯ g_{t^{∗}}^{∗}. Let (k_{1}, k_{2}) and (k_{1}^{∗}, k_{2}^{∗}) be the pairs which arise according to cor. 3.5. Then (k_{1}, k_{2}) = (k_{2}^{∗}, k_{1}^{∗}) which follows from the second part of this corollary: Denote the k′_{τ}, k′′_{τ} obtained by using the g’s or the g^{∗}’s by k′_{τ}, k′′_{τ} and k_{τ}^{∗′}, k_{τ}^{∗′′}, respectively.

Then (k′ ; _{t}, k′′ ; _{t}) = (k∗′ ; _{t}, k∗′′ ; _{t}) =: (α, β), since the g’s and the g^{∗}’s have the same last t̃ elements. There are still two resp. three induction steps left to get (k_{1}, k_{2}) resp. (k_{1}^{∗}, k_{2}^{∗}), and an explicit calculation gives (k_{1}, k_{2}) = (k_{2}^{∗}, k_{1}^{∗}) = (12α+3, 12β+ 8). (Let’s abbreviate the technique of the preceding paragraph by saying that 3 · 2 · 2 ⋯ gives rise to (k_{2}, k_{1}) if 4 · 3 ⋯ gives rise to (k_{1}, k_{2}).)

It is now clear why (i) holds. Note that even more is true: what we have done with 4 · 3 ⋯ and 3 · 2 · 2 ⋯ can also be repeated with 3 · 4 ⋯ and 2 · 2 · 3 ⋯ so that there are in fact more examples than claimed.

(ii) The idea is the same, but this time 9 · 4 and 3 · 2 · 2 · 3 are of importance: 9 · 4 ⋯ and 3 · 2 · 2 · 3 ⋯ lead to the same (k_{1}, k_{2}) (the situation is different to that of (i) since in this case the number of the factors is modulo 2 the same). For the assertion concerning 150 one has to check that 5 · 5 · 6 ⋯ and 10 · 3 · 5 ⋯ lead to the same (k_{1}, k_{2}).

Notes

1) The simplest concrete example to apply (ii) is m = 35: There are two (8, 27)– families (Π_{1}, Π_{2}) with 1 ∈ Π_{1}, namely ((1 1 1 1 1 1 1 1 1), (1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1)), ((1 1 1 0 0 0 1 1 1), (1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1)).

2) The properties of 12, 36, 150 in this proposition have been found by trial and error. We have no idea how one could produce systematically a_{1} ⋯ a_{r}, b_{1}, ⋯, b_{s} such that a_{1} ⋯ a_{r} = b_{1} ⋯ b_{s}, and a_{1} ⋯ a_{r} ⋯ lead to the same (k_{1}, k_{2}) as b_{1} ⋯ b_{s} · · ·.

C. Are there many (k_{1}, k_{2}) with k_{1} + k_{2} = m which admit admissible families?

The answer depends on m, of course. Recall our systematic enumeration of the (k_{1}, k_{2}) with k_{1} + k_{2} = 11 for which there are admissible (k_{1}, k_{2})–families: here one has such families for all (k_{1}, k_{2}) (not in every case, however, one has 1 ∈ Π_{1}; this happens only when k_{1} = 1, 2, 3, 5, 7, 8, 9). There are other examples, here is the complete list for the m < 255 : m = 3, 5, 7, 11, 15, 23, 31, 35, 47, 63, 71, 95, 127, 143, 191, 215. For some of these m the phenomenon can easily be understood; whenever m is of the form 2^{ℓ} − 1, then for all (k_{1}, k_{2}) with k_{1} + k_{2} = m admissible families exist. The easiest way to explain this is to remember the proofs in section 3. Admissible families arise when one groups together the Π̂_{τ}, and one has only to notice that every k_{1} can be obtained by taking the sum over a suitable subset of {1, 2, 4, 8,…}. We cannot offer any number theoretical explanation concerning the other m with this property.

But what is the answer if we consider a “general” m, i.e. an m chosen “at random”. More precisely, define

M_{m_{0}} = {(k_{1}, k_{2}) | k_{1} + k_{2} ≤ m_{0}} and M̂_{m_{0}} =

{(k_{1}, k_{2}) | k_{1} + k_{2} ≤ m_{0}, there is an admissible (k_{1}, k_{2})–family}:

what about μ_{m_{0}} := card M̂_{m_{0}}/card M_{m_{0}} for large m_{0}?

To this end we have to calculate the number of

(g_{1},…, g_{t}) such that g_{1} ⋯ g_{t} = m + 1 .

4.2 Lemma Suppose that m+1 is square–free, i.e. there are pairwise different primes p_{1},…, p_{ℓ} with p_{1} ⋯ p_{ℓ} = m+1. Denote by β_{ℓ} the number of ordered tuples (g_{1},…, g_{t}) with g_{1} … g_{t} = m + 1, where t runs through 1, 2,…, ℓ.

(i) β_{ℓ} = α_{1}^{ℓ} + α_{2}^{ℓ} + ⋯ + α_{ℓ}^{ℓ}, where the α’s can be obtained as follows: α_{1}^{ℓ} := 1 for all ℓ, α_{j}^{ℓ} := j (α_{j}^{ℓ−1} + α_{j−1}^{ℓ−1}) for j < ℓ, α_{ℓ}^{ℓ} := ℓ!

(ii) β_{ℓ} ≤ 2^{ℓ−1}ℓ!.

Proof

(i) Put α_{t}^{ℓ} = the number of (g_{1},…, g_{t}) with g_{1} ⋯ g_{t} = m + 1 (which obviously only depends on ℓ and not on m + 1). Then it is easy to check that the α’s satisfy the above relations.

(ii) From (i) it follows that α_{j}^{ℓ} ≤ ℓ (α_{j}^{ℓ−1} + α_{j−1}^{ℓ−1}) for 1 < j < ℓ, and this is valid for all j if we put α_{−1}^{ℓ} := 0, α_{ℓ+1}^{ℓ} := 0. Thus β_{ℓ} ≤ 2ℓβ_{ℓ−1}, and this gives (ii).

Note Here are the first β’s: β_{1} = 1, β_{2} = 3, β_{3} = 13, β_{4} = 75, β_{5} = 541.

By cor. 3.5 there are precisely β_{ℓ} admissible different (k_{1}, k_{2})–families in canonical order; one of these is the trivial (m)–family ({0,…, m}), and there might be different families for the same values of (k_{1}, k_{2}). If m + 1 = p_{1} ⋯ p_{ℓ} with primes which are not necessarily distinct then the number of different (g_{1},…, g_{t}) with g_{1} ⋯ g_{t} = m + 1 is ≤ β_{ℓ} (a precise calculation seems to be difficult). In any case we know: If (m + 1) is built up from ℓ primes, then the number of different (k_{1}, k_{2})–families for {0,…, m} is ≤ β_{ℓ}. By a result of Erdös and Kac ([2], or [1], p. 395 and p. 399) one knows that ℓ is of magnitude log log m, and combining this with 4.2 (ii) and with the help of Stirling’s formula we get μ_{m_{0}} ⟶ 0.

D. Factorizations of the uniform distribution

Here is the solution of the problem we started with (the set {0, g, 2g,…, rg} in this theorem is a typical set Π̂_{τ} in the notation of part 1 of section 3):

4.3 Theorem Let k_{1},…, k_{s}, m be such that k_{1}+⋯+k_{s} = m. There are probabilities P_{1},…, P_{s} on {0,…, k_{1}},…, {0,…, k_{s}} such that P_{1} ∗ ⋯ ∗ P_{s} is the uniform distribution on {0,…, m} iff there are subsets Π_{σ} ⊂ {0,…, k_{σ}} such that every j ∈ {0,…, m} can uniquely be written as j = j_{1} + ⋯ + j_{s} with j_{σ} ∈ Π_{σ}. In this case the P_{σ} are uniform on such Π_{σ}, and each P_{σ} is of the form P_{σ,1} ∗ ⋯ ∗ P_{σ,t_{σ}}, where the P_{σ,τ} are uniform distributions on sets of the form {0, g, 2g,…, rg}. The possible (k_{1},…, k_{s}), Π_{1},…, Π_{s} are described in section 3.

E. Factorizations of 1 + x + ⋯ + x^{m} into polynomials with nonnegative coefficients

4.4 Theorem If 1 + x + ⋯ + x^{m} is written as A_{1}(x) ⋯ A_{s}(x), where the A_{σ} have nonnegative coefficients and leading coefficient 1, then each A_{σ} is a product of polynomials of the form 1 + x^{g} + ⋯ + x^{rg}. Consequently the only possibility to write {ξ | ξ^{m+1} = 1, ξ ≠ 1} as a disjoint union W_{1} ˙∪ ⋯ ˙∪W_{s} such that ∏_{ξ∈W_{σ}}(x − ξ) have

nonnegative coefficients for all σ is to choose the W_{σ} as disjoint unions of sets of the form “all r’th roots of all ξ such that ξ^{g+1} = 1, ξ ≠ 1”.

References

[1] P. Billingsley: Probability and measure. John Wiley and Sons 1995.

[2] P. Erdös, M. Kac: On the Gaussian law of errors in the theory of additive functions. Proc. Nat. Acad. Sci USA 25, 1933, 206–207.

[3] G. Letac: Problèmes de Probabilité. Paris, Presses Universitaires de France, 1970.

[4] G. Letac: Integration and Probability by P. Malliavin. Springer Verlag, New York, Berlin, Heidelberg, 1995.

[5] V. Linnik: Decomposition of probability distributions. Oliver & Boyd, London 1964.

[6] E. Lukacz: Developments in characteristic function theory. Charles Griffin & Company, London 1983.

[7] D.A. Raikov: One property of cyclotomic polynomials. Matem. sb. 2 (44), 1937, 379–382.

[8] G. Szekely: Paradoxes in probability theory and mathematical statistics. D. Reidel Publishing Company, Boston 1986.

Ehrhard Behrends I. Mathematisches Institut Arnimallee 3 D – 14195 Berlin