If the sum of two independent random variables is discrete uniform on $\{a, \dots,a + n\}$, what do we know about $X$ and $Y$?

As Lutz Mattner pointed out in his comment to another question, an affirmative answer is given in: Krasner and Ranulac (1937), Sur une propriété des polynomes de la division du cercle, C.R. Acad. Sci. Paris 204, 397–399 (which, unfortunately, does not seem to be available online, except for the Russian version due to D. Raikov). Connection to the other question was observed by @user44191.

1. Proof of the claim

The following lemma shows that $X$ and $Y$ may also be regarded as integer-valued random variables in OP's scenario.

Lemma. Assume that $X$ and $Y$ are independent random variables. Suppose that there exists a finite set $S\subset\mathbb{R}$ satisfying $$ \mathbb{P}(X+Y \in S) = 1 \qquad \text{and} \qquad \mathbb{P}(X+Y = s) > 0, \quad \forall s \in S. $$ Then there exist $x_0, y_0 \in \mathbb{R}$ such that $X' := X + y_0$ and $Y' := Y + x_0$ satisfy $$\mathbb{P}(X' \in S) = 1 \qquad\text{and}\qquad \mathbb{P}(Y' \in S) = 1.$$ Moreover, $\mathbb{P}(X' = \min S) > 0$ and $\mathbb{P}(Y' = \min S) > 0$.

The proof is postponed to the end. Now write $[\![n]\!] := \{0, \cdots, n-1\}$. Then we prove

Proposition.^{(1, Lemma 2.1)} Let $X$ and $Y$ be independent random variables such that $X+Y$ is uniformly distributed over $[\![n]\!]$. Then both $X$ and $Y$ have uniform distribution.

The following proof is based on the reference 1) mentioned in @Mark Wildon's comment.

Proof. In light of the lemma above, we may assume that both $X$ and $Y$ are supported on $[\![n]\!]$ as well as $\mathbb{P}(X=0,Y=0)=1/n$. Using this, set

$$ A(x) := \sum_{k\geq 0} a_k x^k \qquad \text{and} \qquad B(x) := \sum_{k\geq 0} b_k x^k $$

where $a_k := p_X(k)/p_X(0)$ and $b_k := p_Y(k)/p_Y(0)$. Then it follows that $a_k, b_k$ are all non-negative, $a_0 = b_0 = 1$, and

$$ A(x)B(x) = 1 + x + \cdots + x^{n-1}. $$

From this, it is easy to check that both $A(x)$ and $B(x)$ are palindromic, which will be used later.

Now, to establish the desired assertion, it suffices to show that all of the coefficients of $A(x)$ and $B(x)$ lie in $\{0, 1\}$. To this end, assume otherwise. Let $k_0$ be the smallest index such that either $a_{k_0} \notin \{0, 1\}$ or $b_{k_0} \notin \{0, 1\}$. We know that $k_0 \geq 1$. Moreover,

$$ a_{k_0} + \underbrace{ a_{k_0-1}b_{1} + \cdots + a_1 b_{k_0 - 1} }_{\in \mathbb{N}_0} + b_{k_0} = [x^{k_0}]A(x)B(x) \in \{0, 1\}, $$

forces that $a_{k_0} + b_{k_0} = 1$. So both $a_{k_0}$ and $b_{k_0}$ lie in $(0, 1)$. But if we write $d = \deg B(x)$, then we have $b_{d-k_0} = b_{k_0}$ and $b_d = b_0 = 1$, and so,

$$ 1 < a_{k_0}b_{k_0} + 1 \leq a_{d} + \cdots + a_{k_0}b_{d-k_0} + \cdots + b_{d} = [x^{d}]A(x)B(x) \in \{0, 1\}, $$

a contradiction. Therefore no such $k_0$ exists and the desired claim follows. $\square$

References.

_{1) Behrends, E., 1999. Über das Fälschen von Würfeln. Elem. Math. 54, 15–29. https://doi.org/10.1007/s000170050051}

2. Further questions

Based on some simulations as well as actual computation for small $n$, I conjecture that the followings hold:

Conjecture. Let $A(x)$ and $B(x)$ be monic polynomials with coefficients in $[0, \infty)$. Assume that there exists an integer $n \geq 1$ such that $$ A(x)B(x) = 1 + x + \cdots + x^{n-1}. $$ Then there exist positive integers $1 = n_0 \mid n_1 \mid \cdots \mid n_d = n$, not necessarily distinct, such that $$ A(x) = \frac{(x^{n_1} - 1)}{(x^{n_0} - 1)} \frac{(x^{n_3} - 1)}{(x^{n_2} - 1)} \cdots, \qquad B(x) = \frac{(x^{n_2} - 1)}{(x^{n_1} - 1)} \frac{(x^{n_4} - 1)}{(x^{n_3} - 1)} \cdots. $$

This implication of this conjecture is that, up to shift, $X$ is supported on the set of the form

$$ \{ (c_0 + c_2 n_2 + c_4 n_4 + \ldots) : c_k \in [\![n_{k+1}/n_k]\!] \} $$

and likewise $Y$ is supported on

$$ \{ (c_1 n_1 + c_3 n_3 + c_5 n_5 + \ldots) : c_k \in [\![n_{k+1}/n_k]\!] \}. $$

This may be regarded as the converse of the fact that, if $Z$ is sampled uniformly at random from the set $[\![n]\!]$ and $Z = \sum_{k\geq 0} C_k n_k$ with $C_k \in [\![n_{k+1}/n_k]\!]$, then $C_k$'s are independent.

Addendum - Proof of Lemma.

First, we note that both $X$ and $Y$ are bounded. Indeed, choose $x > 0$ so that $\mathbb{P}(|X| \leq x) > 0$ and note that

$$ \mathbb{P}(|Y| \geq y) = \frac{\mathbb{P}(|Y| \geq y, |X| \leq x)}{\mathbb{P}(|X| \leq x)} \leq \frac{\mathbb{P}(|X + Y| \geq y - x)}{\mathbb{P}(|X| \leq x)} $$

can be made to vanish if $y$ is chosen sufficiently large. This shows that $Y$ is bounded. A similar argument shows that $X$ is also bounded.

Next, choose the smallest interval $[x_0, x_1]$ so that $\mathbb{P}(X \in [x_0, x_1]) = 1$, and likewise, choose the smallest interval $[y_0, y_1]$ so that $\mathbb{P}(Y \in [y_0, y_1]) = 1$. Then $x_0 + y_0 = \min S$. Indeed,

• If $x_0 + y_0 < s$, then write $s = x+y$ with $x > x_0$ and $y > y_0$. Then

  $$ 0 < \mathbb{P}(X \leq x, Y \leq y) \leq \mathbb{P}(X + Y \leq s) $$

  shows that $s \geq \min S$. Letting $s \downarrow x_0 + y_0$, this proves $x_0 + y_0 \geq \min S$.

• If $x_0 + y_0 > s$, then $\mathcal{D} := \{(x, y) : x+y \leq s\} \cap ([x_0, x_1]\times[y_0, y_1]) = \varnothing$, and so,

  $$ \mathbb{P}(X+Y \leq s) = \mathbb{P}((X, Y) \in \mathcal{D}) = 0. $$

  This implies that $s < \min S$ and thus $x_0 + y_0 \leq \min S$.

Together with $\mathbb{P}(X+Y = \min S) > 0$, this implies $\mathbb{P}(X = x_0) > 0$ and $\mathbb{P}(Y = x_0) > 0$. From this,

$$ \mathbb{P}(X+y_0 \notin S) = \mathbb{P}(X+Y \notin S \mid Y = y_0) \leq \frac{\mathbb{P}(X+Y \notin S)}{\mathbb{P}(Y = y_0)} = 0 $$

and hence $\mathbb{P}(X+y_0 \in S) = 1$. A similar argument shows that $\mathbb{P}(Y+x_0 \in S) = 1$, and therefore the claim follows by setting $a = y_0$ and $b = x_0$. $\square$

(A rather trivial remark, but too long for a comment.)

Phrase it in a different language: two polynomials $P$ and $Q$ with non-negative coefficients have product equal to $$P(x) Q(x) = 1 + x + x^2 + \ldots + x^{n-1} = \frac{1 - x^n}{1 - x} .$$ What does it tell us about $P$ and $Q$?

Write $\sigma = e^{2 \pi i / n}$, so that $$ P(x) Q(x) = \prod_{k = 1}^{n - 1} (x - \sigma^k) .$$ Clearly, for some partition $\{1,2,\ldots,n-1\} = A \cup B$ and appropriate constants $a$ and $b$, we have $$ P(x) = a \prod_{k \in A} (x - \sigma^k) , \qquad b P(x) = \prod_{k \in B} (x - \sigma^k) . $$ For simplicity, let us require that $P(0) = Q(0) = 1$.

Since $P$ and $Q$ are real-valued, if $A$ contains $k$, it also contains $n - k$. Any such partition leads to a factorization $P(x) Q(x)$ where $P$ and $Q$ have real-valued (possibly negative) coefficients.

However, we require the coefficients of $P$ and $Q$ to be non-negative. Does this imply that the coefficients of $P$ and $Q$ are all $0$ and $1$?