I think I found the answer: (I think !)

In this paper from Thompson et al., there is a explanation and a demonstration of how to compute the sample size $n$ for a multinomial law, which is what I want here (a categorical variable with k classes).

The short answer is :

$n = max_{m} \left( z^2 \frac{(\frac{1}{m})(1-\frac{1}{m})}{d^2} \right) $,

where $n$ is the sample size we want to compute, $z$ is the upper $\left(\alpha/2m\right)$x100th percentile of the standard normal distribution, $m$ is an integer as $0<m\leq k$ and $d$ is the precision ny which we want to estimate the proportion of each class.

Interestingly, the author shows that the max sample size $n$ is obtained for relatively small value of $m$ and that it is not necessary to know ahead of time the number of classes in the population.

However, I think that when $k$ is big (as it is the case for me, $k=256$), the number $k$ will influence the sample size, because one will have to decrease the precision $d$ he wants to achieve. For example, if $k=3$, the theorical distribution would be all classes have a proportion of $1/3$. In this case, having a precision of 1% or 5% ($ d = 0.01$ or $d=0.05$) is fine. Now, with $k=256$, the theoretical proportion is $\frac{1}{256} \simeq 0.0039$. If one choose $d = 0.01$, it means that 0 will be a possible proportion. To avoid that, one would like to choose $d < \frac{1}{k}$.

In my case, with a risk $\alpha = 0.01$ and a precision $d = 0.003$, the needed sample size is : 218 828 !!

I hope this will be useful for someone else.

I think I found the answer:

In this paper from Thompson et al., there is a explanation and a demonstration of how to compute the sample size $n$ for a multinomial law, which is what I want here (a categorical variable with k classes).

The short answer is :

$n = max_{m} \left( z^2 \frac{(\frac{1}{m})(1-\frac{1}{m})}{d^2} \right) $,

where $n$ is the sample size we want to compute, $z$ is the upper $\left(\alpha/2m\right)$x100th percentile of the standard normal distribution, $m$ is an integer as $0<m\leq k$ and $d$ is the precision ny which we want to estimate the proportion of each class.

Interestingly, the author shows that the max sample size $n$ is obtained for relatively small value of $m$ and that it is not necessary to know ahead of time the number of classes in the population.

However, I think that when $k$ is big (as it is the case for me, $k=256$), the number $k$ will influence the sample size, because one will have to decrease the precision $d$ he wants to achieve. For example, if $k=3$, the theorical distribution would be all classes have a proportion of $1/3$. In this case, having a precision of 1% or 5% ($ d = 0.01$ or $d=0.05$) is fine. Now, with $k=256$, the theoretical proportion is $\frac{1}{256} \simeq 0.0039$. If one choose $d = 0.01$, it means that 0 will be a possible proportion. To avoid that, one would like to choose $d < \frac{1}{k}$.

In my case, with a risk $\alpha = 0.01$ and a precision $d = 0.003$, the needed sample size is : 218 828 !!

I hope this will be useful for someone else.