A formula for a generator of the multiplicative group of $\mathbb{F}_p$ ?

Question

Let $p$ be a prime. It is a common statement that the multiplicative group $(\mathbb{F}_p)^*$ of the prime field has no canonical generator. It is however no so easy to say exactly what this means, in particular it is not easy to make the statement fit into the ideas on canonicity that are expressed in the answers to this MO question.

Thus I would like to find some positive and negative facts concerning the existence, construction, functoriality (if someone can make sense of it) of generators of the group $(\mathbb{F}_p)^*$. For example, does anyone know a formula for a generator in terms of $p$ ? Maybe is there a theoretical result saying that such a formula can / can't exist ? Can anyone give an example of a fact that is related to the (presumed) non-canonicity of these generators ?

[Edit] In fact, I am more interested in the statement that "there is no canonical generator" than in finding "formulas". What I would especially like to see is if someone can cook up a precise statement of non-canonicity and prove it. As an example, we use to say that "there is no canonical isomorphism between a finite-dimensional vector space and its dual" and one can in fact prove the precise mathematical statement that there is no functor defined on the category of finite-dim. spaces of a fixed dimension $n$ (say $n\ge 3$ for simplicity) that would take a vector space $E$ to an isomorphism $E\to E^*$.

Answer 1

An obvious question is what constitutes a formula. Algebraic expressions depending on $p$ became constant modulo $p$ and it is not hard to show that, e.g. for any (even reducible) polynomial $F(x)$ with integer coefficients, no solution of $F(x) \equiv 0 \mod p$ is a primitive root for a set of primes ofpositive density.

A trickier thing would be to look at expressions that depend on Witt coordinates of constants. For example, one could try to show that $(2^p-2)/p$ is not a primitive root modulo $p$ for infinitely many (or even a positive proportion of) $p$. I would expect this to hold and that it is something one can prove but I don't have a proof offhand.

On a different line, there is an old result of Ankeny that the smallest primitive root modulo $p$ is infinitely often larger than $\log p$. Also, under GRH, the smallest primitive root is at most $4(\log p)^2$.

The primitive roots are uniformly distributed in the interval $[1,p-1]$.

If you want a more precise answer, please ask a more precise question.

Answer 2

One more update (sorry for the slight sillyness, and hoping I at least got it right, yet it is not optimized):

For $F$ a field of prime cardinality $$1 + \sum_{a=1}^{|F|-1} \prod_{b=1}^{a} (1 - \prod_{d=1}^{|F|-2}(b^d -1)^{|F|-1} )$$ generates the multiplicative group (with usual convention that $n$ is $n \cdot 1_F$).

---

If one would like to have some "formula"/definition that would give a generator as requested for each field of prime order and always 'the same' for (isomorphic) fields, one could proceed like this:

Let $g_F = n \cdot 1_{F}$ where $$n = \min \{m \in \mathbb{N} \colon \text{ord} ( m \cdot 1_F) = |F|-1\}$$ and $\text{ord}$ denotes the multiplicative order (which one could also write out just using the field operations and quantifiers and the natural numbers).

If I oversee things correctly (which is a lot less clear than usually when I answer) one could define in principle this way a functor from the category with objects fields of prime order and morphism field homomorphisms (or iso would be the same in this case) to the category of "fields of prime order with minimally chosen multiplicative generator" (objects field of prime order plus distinguished element as defined above, and morphisms fields homo/isomorphisms mapping the distinguished element to the distinguished element of the respective fields).

The point being that between fields of different prime cardinality there is no morphism at all, and if the cardinality is the same there is exatly one (as everything is determine by the one-element).

So, it is in principle possible to "select" (in a uniform way for all such fields) some 'distinguished' (which perhaps one might call canonical) multiplicatively generating element. (Of course one could also make other selections than the minimal one.)

I am sorry if this either should not make sense at all, or should miss the point completely. In either case I would be glad for an explication.

---

Old version:

To say that a "formula" cannot exist is always a bit of a tricky issue, as there are for examples formulas that generate primes still these are in general of little relevance for finding them.

A generator of this group typically goes by the name of primitive root modulo $p$ and to find one algorithmically is not easy, and of course there are various (open) conjectures on the smallest one (which would not in itself preclude that one could find some).

So, if you want some 'canonical' (in a certain sense) choice, take the smallest. Alas no one knows how large it is; the I believe best upper bound is $p^{1/4 + \varepsilon}$; under the extended Rieman hypothesis one has $O((\log p)^6)$. On the other hand one knows that for infinitely many primes it is as large as $C \log p$, while it is famously conjectured it is infinitely often also $2$ (and it is known it is infinitely of one of a very small set of small numbers).

To say something more specific: the best (to my knowledge) deterministic algorithm to find one takes $p^{1/4 + o(1)}$ (by Shparlinski).

And the question is somewhat closely linked to the discrete logarithm problem which is knwon to be hard.

See this paper by Bachman for more information http://www.ams.org/journals/mcom/1997-66-220/S0025-5718-97-00890-9/