  We study the problem of designing a data structure that reports the positions
of the distinct $\tau$-majorities within any range of an array $A[1,n]$,
without storing $A$. A $\tau$-majority in a range $A[i,j]$, for $0<\tau< 1$, is
an element that occurs more than $\tau(j-i+1)$ times in $A[i,j]$. We show that
$\Omega(n\log(1/\tau))$ bits are necessary for any data structure able just to
count the number of distinct $\tau$-majorities in any range. Then, we design a
structure using $O(n\log(1/\tau))$ bits that returns one position of each
$\tau$-majority of $A[i,j]$ in $O((1/\tau)\log\log_w(1/\tau)\log n)$ time, on a
RAM machine with word size $w$ (it can output any further position where each
$\tau$-majority occurs in $O(1)$ additional time). Finally, we show how to
remove a $\log n$ factor from the time by adding $O(n\log\log n)$ bits of space
to the structure.
