Basically I want to know whether the sum being discrete uniform effectively forces the two component random variables to also be uniform on their respective domains. 


To be a bit more precise:


Suppose we know $X$ and $Y$ are independent and


$$ X+Y \sim UNIF({1, \dots , n})$$


Does this necessarily imply that both $X$ and $Y$ are discrete uniform as well?



If the sum of two independent random variables is discrete uniform on $\{a, \dots,a + n\}$, what do we know about $X$ and $Y$?
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*](https://en.wikipedia.org/wiki/Reciprocal_polynomial#Palindromic_and_antipalindromic_polynomials), 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$


