Tail bounds on Euclidean norm for uniform distribution on $\{-n,-(n-1),...,n-1,n\}^d$ What are known upper bounds on how often the Euclidean norm of a uniformly chosen
element of $\:\{-n,~-(n-1),~...,~n-1,~n\}^d\:$ will be larger than a given threshold?
I'm mainly interested in bounds that converge exponentially to zero when $n$ is much less than $d$.
 A: Intuitively, it should be obvious that a point whose coordinates are sampled at random from the uniform distribution should have small modulus due to the curse of dimensionality. As $d$ increases, the probability that a point sampled at random from the volume of the $d$-dimensional unit ball will have distance less than or equal to $\epsilon$ from the center is $\epsilon^{d}$, which drops exponentially fast.
I'll give the full version of cardinal's solution.
Let $X_i$ be one independent copy of a discrete, uniform distribution over the integers $-n \leqslant k \leqslant n$.  Clearly, $\mathbb{E}[X] = 0$, and it is easily computed that $\text{Var}(X_i) = \frac{n(n+1)}{3}$
Recall that $\mathbb{E}[X_i^2] = \text{Var}(X_i) + \mathbb{E}[X_i]^2$ and that $\text{Var}(X_i^2) =  \mathbb{E}[X_i^4] - \mathbb{E}[X_i^2]^2$
Thus, $\mathbb{E}[X_i^2] = \text{Var}(X_i) = \frac{n(n+1)}{3}$
$\text{Var}(X_i^2) =  \mathbb{E}[X_i^4] - \mathbb{E}[X_i^2]^2 = \frac{n(n+1)(3n^2 + 3n + 1)}{15} - \left( \frac{n(n+1)}{3} \right)^2$
$\mathbb{E}[X_i^4]$ computation
Let $Y_i = X_i^2$
$$\sum_{i=1}^d Y_i = (\text{Distance of Randomly Sampled Point to Origin})^2$$
I'll finish this tomorrow, but you can see that this variable has a mean of about $\frac{n^2}{3}$, while less than $2^{-d}$ fraction of points have distances less than half the maximum distance $\frac{dn^2}{2}$ 
A: If all $X_i$ follow independent discrete uniforms over $[-n, n]$, then as there are $2n+1$ values to choose from and their mean is 0, we have for all $i$:
$\mathbb{E}(X_i)= 0$, and 
$\mathbb{V}(X_i)= \mathbb{E}\left((X_i - \mathbb{E}(X_i))^2\right)= \mathbb{E}(X_i^2)= \frac{(2n+1)^2 - 1}{12}= \frac{n(n+1)}{3}$
Then if $S$ is the squared euclidean norm of vector $(X_1, X_2, ... X_d)$, and because of the independence of the $X_i$:
$S= \sum_{i=1}^d X_i^2$
$\mathbb{E}(S)= \sum_{i=1}^d \mathbb{E}(X_i^2) = d \frac{n(n+1)}{3}$
From here on you could use Markov's inequality: $\forall a >0, \mathbb{P}(S \geq a) \leq \frac{1}{a}\mathbb{E}(S)$
$\mathbb{P}(S \geq a) \leq \frac{d}{a}\frac{n(n+1)}{3}$
This bound rises with $d$, which is normal because when $d$ gets larger the euclidean norm gets larger when compared to a fixed threshold $a$.
Now if you define $S^*$ as a "normalized" squared norm (that has the same expected value no matter how big $d$) you get:
$S^*= \frac{1}{d} Y = \frac{1}{d} \sum_{i=1}^d X_i^2$
$\mathbb{E}(S^*) = \frac{n(n+1)}{3} $
$\mathbb{P}(S \geq a) \leq \frac{n(n+1)}{3a}$
At least this bound doesn't rise with $d$, but it still far from solves your quest for an exponentially decreasing bound! I wonder if this can be due to the weakness of the Markov inequality... 
I think you should precise your question, because as stated above the mean euclidean norm of your vectors linearly rises in $d$, so you are very unlikely to find an upper bound for $\mathbb{P}(S > a)$ that is decreasing in $d$ with a fixed threshold $a$. 
