Let $Z = X + Y$. I'll assume $n$ is an integer. More generally, I'll allow Z to take values in $S_Z = \{z_1, ..., z_n \}$. As $Z$ is uniform on $S_Z$, we know that

$$P(Z = z) = \frac{1}{n}$$

for any $z \in S_Z$.

Let $S_X, S_Y$ represent the supports of $X, Y$ respectively. Let $p_x = P(X = x)$ and $q_x = P(Y = x)$. As they are independent, we can therefore write $P(Z = z)$ as

$$ P(Z = z) = \sum_{x \in S} p_x q_{z-x} . $$

Therefore, we have the following set of consistency equations

$$ \sum_{x \in S} p_x q_{z-x} = \frac{1}{n} \tag{1}$$

for all $z$. We can solve this iteratively assuming a total order on the supports $S_X$ and $S_Y$. Let $x_{(i)}$ be the $i$th minimal element of $S_X$, $y_{(i)}$ be the $i$th minimal element of $S_Y$, and $z_{(i)}$ be the $i$th minimal element of $S_Z$. We must have that $x_{(1)} + y_{(1)} = z_{(1)}$, as the sum of the minima of both sets $S_X$ and $S_Y$ must map to the minimum of the support of $Z$, so by the consistency equations $(1)$, we obtain

$$p_{x_{(1)}}q_{y_{(1)}} = \frac{1}{n} .$$

If we require that the distributions of $X$ and $Y$ are uniform, i.e., $p_{x_{(1)}} = 1/|S_X|$ and $q_{y{(1)}} = 1/|S_Y|$, then we must have

$$ |S_X||S_Y| = n \tag{2} $$

and therefore uniformity can only hold if both $|S_X|$ and $|S_Y|$ divide $n$. Hence, the distributions of $X$ and $Y$ are not always uniform.

Another way to interpret equation $(2)$ is that the mapping $X + Y$ across the supports of $S_X$, $S_Y$ must map to a unique element in $\{1,...,n\}$. This is shown explicitly in the expanded cases below for $z_{(2)}, z_{(3)}$, and $z_{(4)}$ in equation $(1)$.

In fact, if the mapping does map to unique elements, then the consistency equations become

$$p_{x_{(i)}}q_{y_{(j)}} = \frac{1}{n}, \;\;\; i \in \{1, ..., |S_X|\}, \; j \in \{1, ..., |S_Y|\},$$

Summing over $i$ or $j$ respectively produces

$$p_{x_{(i)}}= \frac{1}{|S_X|} \;\;\; q_{y_{(j)}}= \frac{1}{|S_Y|}$$

where equation $(2)$ emerges from summing over both $i$ and $j$ and is used in the last equation. Therefore, the underlying probability distributions must be uniform in this case.

The rest of this answer covers later orders but produces the same result.

For the case $z = z_{(2)}$, we must consider both the minimal elements and the next-to-minimal elements of $S_X$ and $S_Y$. Let $x_{(2)}, y_{(2)}$ be the next-to-minimal elements of $S_X$ and $S_Y$ respectively. There are three possible cases here:

- $x_{(1)} + y_{(2)} = z_{(2)}$
- $x_{(2)} + y_{(1)} = z_{(2)}$
- $x_{(1)} + y_{(2)} = x_{(2)} + y_{(1)} = z_{(2)}$

Hence, for $z = z_{(2)}$ we get (for the 3 cases)

- $p_{x_{(1)}} q_{y_{(2)}} = \frac{1}{n}$
- $p_{x_{(2)}} q_{y_{(1)}} = \frac{1}{n}$
- $p_{x_{(1)}} q_{y_{(2)}} + p_{x_{(2)}} q_{y_{(1)}} = \frac{1}{n}$

Let us focus on cases 1 and 2. Consider $z = z_{(3)}$. In these cases, we must have that

- $x_{(2)} + y_{(1)} = z_{(3)}$
- $x_{(1)} + y_{(2)} = z_{(3)}$

as we can exclude the other cases by the requirements that $x_{(i)} < x_{(j)}$ if $i < j$ and similarly for $y_{(i)}$. These conditions are identical to the $z = z_{(2)}$ case but with $p$ and $q$ reversed.

For $z = z_{(4)}$, we must have $x_{(2)} + y_{(2)} = z_{(4)}$. We therefore obtain

$$p_{x_{(2)}}q_{y_{(2)}} = \frac{1}{n}$$

In cases 1 and 2, we end up with the same set of equations:

$$ p_{x_{(i)}}q_{y_{(j)}} = \frac{1}{n} $$

for $i,j \in \{1, 2\}$. This gives us the following conditions:

$$ p_{x_{(1)}} = p_{x_{(2)}}, \;\;\; q_{y_{(i)}} = \frac{1}{n p_{x_{(1)}}}, \;\;\; i \in \{1, 2\}$$

Let us now suppose that $X$ and $Y$ are uniformly distributed on their supports, so that $p_x = \frac{1}{|S_X|}$ and $q_y = \frac{1}{|S_Y|}$. These conditions require that

$$ |S_X| |S_Y| = n $$

which means that uniformity depends on whether the cardinality of the supports both divide $n$. Hence, the probability distributions for $X$ and $Y$ aren't necessarily always uniform for cases 1 and 2.

Let us now consider case 3. In case 3, we have $x_{(2)} + y_{(2)} = z_{(3)}$ instead, with the same equation as the $z = z_{(4)}$ for cases 1 and 2. Grouping together the conditions, we have

$$ p_{x_{(1)}}q_{y_{(1)}} = \frac{1}{n}, \;\;\; p_{x_{(1)}} q_{y_{(2)}} + p_{x_{(2)}} q_{y_{(1)}} = \frac{1}{n}, \;\;\; p_{x_{(2)}}q_{y_{(2)}} = \frac{1}{n} . $$

These have no real solutions. Therefore, the probability distributions cannot exist.

2more comments