How to statistically test upper bound Suppose a theory claims that a random variable $R$ (of unknown distribution $F$) must satisfy a certian upper bound $R < c$ (where $c$ is known constant). Suppose I perform a set of measurements $X_1,...,X_n$ which are iid~$F$, but because of errors, I observe $X_1+E_1,...,X_n+E_n$ where $E_1,...,E_n$ are independent Gaussian with $E_i$ having standard deviation $\sigma_i$.
Is there some statistical method of testing whether the upper bound is indeed an upper bound based on the measurements?
Now, relax the fact that we know the distributions of $E_i$ to be Normal. My current problem is that I am given the values of $X_i + E_i$ with 68% confidence intervals for what $X_i$ should have been, and there is no additional information given (imagine someone handed me the data and perished afterwards; more realistically, it is too difficult to handle but somehow a software churned out the 68% confidence intervals). Is there still some statistical technique I can consider?
 A: A simple way:
Not having a distribution for $X$ makes it a bit tricky, but at least in the case of normal errors, I think this can be done.
I think there's no useful upper limit on $c$ provided by the data in the scenario you describe, since the unobserved values (the ones without error) might have any distribution - as such very large values of $c$ are consistent with any data no matter how small, because it may just be that $F$ just has a very tiny tail that has almost no chance to produce any sample values near the upper limit.
However, I think it's perhaps possible to get a useful lower bound on $c$ that could be used to exclude values that aren't really consistent with the assumptions.
[Excuse me but I am going to move to a slightly more conventional notation. Hopefully it will still be clear.]
Let $Y_i=X_i+\epsilon_i$
"Underlying" values $X_i\stackrel{_\text{iid}}{\sim}F$
Observed values are $Y_i=X_i+\epsilon_i\,$, where 
$\epsilon_i/\sigma_i\stackrel{_\text{iid}}{\sim}N(0,1)\,$ and $\sigma_i, i=1,...,n$ are known.
Method: We could compute for each $Y_i$ the probability that $X_i<c$. If the product of that probability over the observations is low, we reject the hypothesis that the supposed value $c$ ($c_0$) is an upper bound on the values $X$ can take.
In particular, the set of probabilities computed for each $X_i$ individually would correspond to the case of testing whether $X_i$ is no lower than $c_0$, which is equivalent to testing for $X_i=c_0$, $i=1,2,\ldots,n$. 

In the example, the 4 sets of probabilities are where all the X's are right at the hypothesized upper bound (black), below the upper bound (red), above the upper bound (blue, and what we want to reject) and randomly distributed below the bound in such a way that although the hypothesized $c_0$ is the least upper bound on the distribution, none of the X's are likely to get close to it (green).
We can combine the individual probabilities in various ways (I earlier said "take the product", and that works - as long as you compare the product with the right thing). A common way to combine these probabilities into a single test statistic would be via Fisher's method. This takes $-2\times$ the sum of the logs, so it's monotonic in the product I mentioned before. That's then compared with a $\chi^2_{2n}$.
If we do that for the data in the above example, we get p-values of:
Black:  0.3077957
Red:    1
Blue:   1.882208e-09   <--- we reject the case where the bound was below the X's
Green:  1

The green one was a beta distribution on (5,25) and $c_0$ was 25 (i.e. an exact upper bound on the distribution), but it was a very right skew distribution (most X values were close to 5, and the largest observed value was about 13). The test won't have good power in a case like the green one if all the $X$s are below $c_0$, even though $c_0$ is below the largest possible $X$. That really can't be helped.
It should have reasonably good power against $c_0<c$ in cases where $c$ is a sharp least upper bound on the X's (like a uniform, or a beta(10,1) say), which means you should get some observations very close to $c$ in reasonable sized samples.

Somewhat more complicated alternative, by simulation.
Since the distribution of the $\epsilon_i$ are completely specified, it's possible to simulate from their distribution; consequently/equivalently we can simulate from $(X_i|Y_i,\sigma_i)$ and compute the per-simulation maximum. Then if $c_0$ was too low in the tail of this distribution, we'd regard it as unlikely to have produced the sample.
I've tried a few examples and this seems to at least give plausible answers but I haven't yet explored its coverage under different distributions for $X$ (different $F$); you shouldn't rely on it without some degree of checking of its properties.
(if I get a chance to check it myself I will post an update)

On the non-normal error case, it's much trickier, because we know nothing other than a 68% interval. I think that interval is just based on a normal assumption (i.e. a  $\pm$ 1 sd interval - and presumably where the $\sigma_i$ are based on something other than the data).
However, assuming the 68% interval were a valid 68% interval and assuming that the distribution  of the $\epsilon_i$ are symmetric, we can still get somewhere. 
The lower bound of the 68% interval for an observation (presumably $Y_i-\sigma_i$) would lie entirely above $c_0$ with probability $0.16$ ($1-0.68/2$).
Hence the number of points whose interval lower bounds lies above the hypothesized value for $c$ is $\text{binomial}(n,0.16)$. If too many lie above it to be consistent with that, we would reject the possibility that the $X$'s all lie below $c_0$.

Finally, even without symmetry, we could use $\text{binomial}(n,0.32)$ as a worst case.
A: Use the distribution of bootstrapped sample maxima. The right-sided quantile of your specified level of confidence should not exceed the upper bound. You should be testing whether the upper bound is exceeded due to the measurement error.
