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

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 ?

 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^*$.

-
– tomasz Feb 19 '13 at 11:24
Please use the existing toplevel-tags (those with two letters prefix) if they exist. (I changed it.) – user9072 Feb 19 '13 at 12:54
Questions for generators of the multiplicative group of $\mathbb{F}_p \cong \mathbb{Z}/p\mathbb{Z}$ tend to be very difficult, see e.g. en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots. – Stefan Kohl Feb 19 '13 at 13:33
I am never quite sure regarding this functorial things but: What should be the categorty? If you take fields of prime order, there are no nonidentity isomorphisms, so just take the smallest as I said (does anything go wrong?). Now if you just take the multiplicative structure, then I'd guess it is the same as asking for a generator of a cyclic group, which I guess is classical. – user9072 Feb 19 '13 at 14:33
Let me add that the first difficulty to address your question is precisely what is the meaning of "formula". I suggest you to read the paper "Formulas for primes" jstor.org/stable/2690261 to realize that although formulas fascinate they are sometimes non interesting. Indeed, this paper is a very funny reading that I recommend to all mathematicians: I never thought about these issues before reading this paper, it opened my mind to some difficulties with the notion of "formula". – boumol Feb 19 '13 at 19:14

2 Answers

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.

-
I wrote my answer independtly of yours, I am know wondering regarding the best upper bound you mention; it is better than anything I know/can find; I know of certain improvements of the (log p)^6 I mention to r^4 (log p)^2 or something like this, with r the numebr of distinct divisors of p-1. Could you please point me to the result you mention. – user9072 Feb 19 '13 at 13:41
Thank you Felipe! Indeed my question needed clarification, I edited it to underline that I'm really interested in the non-canonicity part. – Matthieu Romagny Feb 19 '13 at 14:14
@quid You are right. The bound is $O((\log p)^6)$. The $O((\log p)^2)$ bound is for an element outside a fixed index proper subgroup of the multiplicative group. – Felipe Voloch Feb 19 '13 at 15:21
Thank you for the clarification and the interesting additional information. – user9072 Feb 19 '13 at 16:29

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/

-
The "known" in the in the discret logarithm proble is a bit sloppy, i should likely better say 'well-known to be believed to be hard'. – user9072 Feb 19 '13 at 13:44
I agree that the smallest integer $g$ such that $g.1$ is a generator in $(\mathbb{F}_p)^\times$ makes sense and is preserved by all field automorphisms. This supports the claim that there is a canonical generator. However this "canonical" generator clearly does not enjoy better algebraic or number-theoretic properties than the other generators, but in our daily experience canonical objects <em>do</em> have nice properties. I am starting to think that the statement that "there is no canonical generator" is just a way of speaking that carries hardly any solid mathematical content. – Matthieu Romagny Feb 19 '13 at 20:26
Personally I hardly use the word "canonical". Yet, if one would not consider the field but only the multiplicative group (I think) one could show that there cannot be a functor (or likely I should say faithful functor or something) from cyclic groups to cyclic groups with distinguished generating element. (And in some sense it seems there is even no apparent way to "name" a distinguished generating element just knowing the group abstractly.) – user9072 Feb 19 '13 at 20:43
I came to a similar formula after discussions with Pascal Boyer. And if I have it right, in the second product you can restrict to $d$'s dividing $|F|-1$. – Matthieu Romagny Feb 20 '13 at 15:29
... and in particular $d\le \lfloor (p-1)/2 \rfloor$. – Matthieu Romagny Feb 20 '13 at 15:31