1
$\begingroup$

We say that a set $A\subseteq \mathbb{N}$ has positive measure if $$\text{lim inf}_{n\to\infty}\frac{|A\cap\{1,\ldots,n\}|}{n} > 0.$$

For $b\in\mathbb{N}$ with $b>1$ we consider the sets $$S_b := \big\{c\in\mathbb{N}:\{b^n \text{ mod } c:n\in\mathbb{N}\}=\{1,\ldots,c-1\}\big\}.$$

Is there $b>1$ such that $S_b$ has positive measure?

Is there $b>1$ such that $S_b$ has not positive measure?

$\endgroup$
3
  • 1
    $\begingroup$ If $c\in S_b$ it has to be coprime to $b$. By Euler's theorem $S_b$ can only contain primes. Hence by the prime number theorem $S_b$ has not positive measure. $\endgroup$
    – user35593
    May 4, 2015 at 14:27
  • $\begingroup$ Oh - typo... it should be $\{1,\ldots,c-1\}$. Thanks for pointing it out! $\endgroup$ May 4, 2015 at 14:27
  • 2
    $\begingroup$ To expand on user35593’s comment: even if the requirements were loosened so that $\{1,\dots,c-1\}$ is replaced with $\{u<c:(u,c)=1\}$, $(\mathbb Z/c\mathbb Z)^\times$ is cyclic only for $c$ of the form $p^k$ or $2p^k$, so $S_b$ would still be of density $0$. The sensible question is to ask for relative density of $S_b$, in the primes, which more or less amounts to Artin’s primitive root conjecture. $\endgroup$ May 4, 2015 at 14:49

1 Answer 1

8
$\begingroup$

As written, the question seems to have a problem (pointed out by user35593): If the powers of $b$ really give all of $1, 2, \dots, c-1$ mod $c$, then $c$ must be prime, and so certainly we do not get positive measure. (By the way, the term ``positive lower density'' seems more standard in this context.)

So let me answer a different question: Fix an integer $b$, and ask for positive integers $n$ where the powers of $b$ generate a cyclic subgroup of maximum possible size. In other words, we want integers $n$ for which the order of $b$ mod $n$ is the exponent of the group $(\mathbb{Z}/n\mathbb{Z})^{\times}$. Do we get positive lower density here?

If we restrict our universe to prime $n$, there's a well-known conjecture of Artin that the answer is usually yes. For instance, if $b=2$, then about 37.4% of primes $n$ should have the stated property.

What if we don't restrict to prime $n$? There's a beautiful theorem of Shuguang Li that for every fixed $b$, the answer is no. The lower density of such $n$ is always $0$.

On the other hand, for most $b$, the upper density (defined as before but with $\limsup$ replacing $\liminf$ is positive), at least if you believe GRH (a result of Li and Pomerance).

All of this is explained better than I have done here in this paper of Li and Pomerance: https://math.dartmouth.edu/~carlp/PDF/primitiverootstoo.pdf

$\endgroup$
1
  • $\begingroup$ Indeed my question has the problem you mention -- thanks for providing a better question along with a beautiful answer! $\endgroup$ May 4, 2015 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.