mutual primitive roots

[quasi]

Conjecture:

For all primes q > 2, there exists a prime p < q such that
ord_p(q)=p-1 and ord_q(p)=q-1.

Question:

For the above conjecture, which of the following, if any,
characterizes its status?

(a) It's known to be true.

(b) It's known to be false.

(c) It's a known conjecture, but as yet unsettled.

quasi

[William Elliot]

On Thu, 1 Dec 2011, quasi wrote:

> For all primes q > 2, there exists a prime p < q such that
> ord_p(q)=p-1 and ord_q(p)=q-1.

What's ord_p mean?

[Tonico]

On Dec 2, 5:47 am, William Elliot <ma...@rdrop.com> wrote:
> On Thu, 1 Dec 2011, quasi wrote:
> > For all primes q > 2, there exists a prime p < q such that
> > ord_p(q)=p-1 and ord_q(p)=q-1.
>
> What's ord_p mean?

**** I think he probably meant ord _p(w) = the order of an element w
(mod p) in the multiplicative group (Z/pZ)* , (p a prime)
Of course, the above makes sense only if (w,p) = 1...

Tonio

>
>
>
> > Question:
> > For the above conjecture, which of the following, if any,
> > characterizes its status?
>
> >   (a) It's known to be true.
>
> >   (b) It's known to be false.
>
> >   (c) It's a known conjecture, but as yet unsettled.
>

> > quasi-

[quasi]

On Thu, 1 Dec 2011 19:47:24 -0800, William Elliot <ma...@rdrop.com>
wrote:

>On Thu, 1 Dec 2011, quasi wrote:
>>

>> Conjecture:

>>
>> For all primes q > 2, there exists a prime p < q such that
>> ord_p(q)=p-1 and ord_q(p)=q-1.
>
>What's ord_p mean?

<http://en.wikipedia.org/wiki/Multiplicative_order>

[quasi]

On Thu, 1 Dec 2011 20:16:51 -0800 (PST), Tonico <Toni...@yahoo.com>
wrote:

>On Dec 2, 5:47 am, William Elliot <ma...@rdrop.com> wrote:
>> On Thu, 1 Dec 2011, quasi wrote:
>> >

>> > Conjecture:

>> >
>> > For all primes q > 2, there exists a prime p < q such that
>> > ord_p(q)=p-1 and ord_q(p)=q-1.
>>
>> What's ord_p mean?
>
>**** I think he probably meant ord _p(w) = the order of an
>element w (mod p) in the multiplicative group

>(Z/pZ)* , (p a prime). Of course, the above makes sense only
>if (w,p) = 1...

Yes, that's what was meant.

To William Elliot:

The notation ord_n(a) is standard in Elementary Number Theory.

See the link:

<http://en.wikipedia.org/wiki/Multiplicative_order>

The notation is used in many Number Theory textbooks.

[James Waldby]

On Fri, 02 Dec 2011 01:36:45 -0500, quasi wrote:

> On Thu, 1 Dec 2011 19:47:24 -0800, William Elliot wrote:
>>On Thu, 1 Dec 2011, quasi wrote:
>>> Conjecture:
>>>
>>> For all primes q > 2, there exists a prime p < q such that
>>> ord_p(q)=p-1 and ord_q(p)=q-1.
>>
>>What's ord_p mean?
> <http://en.wikipedia.org/wiki/Multiplicative_order>
>
>>> Question:
>>>
>>> For the above conjecture, which of the following, if any,
>>> characterizes its status?
>>>
>>> (a) It's known to be true.
>>>
>>> (b) It's known to be false.
>>>
>>> (c) It's a known conjecture, but as yet unsettled.

I don't know which of those applies; most likely (c).
Computationally it's easy to verify as true for p, q < 500000,
via pari/gp code between -- lines below . For each q from
2...qmax, the code counts the number of mutual primitive roots
for primes p, q, with p < q and p < pmax. Eg, when pmax=523
and qmax=99991, there are at least q/18 solutions for each q<600,
and from 25 to 55 solutions for each q in {600..100000}; when
pmax=1979 and qmax=499979, there are at least q/21 solutions for
each q<1979, and from 87 to 144 solutions for q in {1979..500000}.

--
/* 4 Dec 2011 jiw: File "mutual-roots", re: mutual primitive
roots for primes p, q, with p < q, ie p primitive mod q and q
primitive mod p.

For production, use bigger numbers, eg:
s=299; pmax=prime(s); qmax=precprime(500000);

Shell code to filter for gnuplot:
gp < mutual-roots | grep '^[0-9]*.[0-9]*$' > t

In gnuplot use commands like:
plot [0:100000][0:100] 't', x/18, 25,55
plot [0:500000][0:300] 't', x/21, 87,144
plot [0:500000][0:300] 't', x/21, 87,144
*/
s=99; pmax=prime(s); qmax=precprime(100000);
b=vectorsmall(pmax); i=t=1;
forprime(p=2, pmax, b[p]=t; t+=p);
r=vectorsmall(t);
forprime(p=2, pmax, c=b[p]; for(i=1,p-1,if(znorder(Mod(i,p))==p-1,r[c+i]=1)));
forprime(q=3, qmax, g=0; qx=min(pmax,q-1); forprime(p=2, qx, g+=r[b[p]+(q%p)]); print(q,"\t",g));
--
jiw

[Bart Goddard]

quasi <qu...@null.set> wrote in news:2n3ed7tgfqjn39hto6pgg8ldnmu1euleh5@
4ax.com:

> Conjecture:
>
> For all primes q > 2, there exists a prime p < q such that
> ord_p(q)=p-1 and ord_q(p)=q-1.

Hey, quasi, send me e-mail at the address above.

--
Cheerfully resisting change since 1959.

[quasi]

Perhaps the conjecture is true for no particular structural
reason, just a probabilistic accident, with positive,
heuristically justified probability?

Thus, the question:

What is the (heuristic) probability that the conjecture is
true?

If the probability based on random considerations is _zero_,
and given that the early data (as provided by James Waldby)
supports the conjecture, then that would suggest some
internal structural reason for its truth (if it's true), and
in that case, in my view, the conjecture would become more
interesting.

quasi

[James Waldby]

On Mon, 05 Dec 2011 09:55:33 -0500, quasi wrote:

I think the strength of the probabilistic argument (below) if
correct is such that the conjecture itself is uninteresting if true,
but its proof (rather than heuristic likelihood) would be highly
interesting. If the conjecture were proved false, whether by
counterexample or by theory, an explanation of the strange
circumstances that make it false would be interesting.

Naive heuristic/probabilistic argument:
Let h = Pi(q) = #primes < q. (So h ~ q/(ln q).) Let S denote
the set of primitive roots of q; |S| ~ q/2. For any given prime
p < q, presumably prob(p in S) = 1/2. (Half the numbers in S are
odd, half are even, give or take one, but aside from that we
suppose the likelihood of any given positive integer less than q
being in S is ~ 1/2.) Let T denote the set of primes that are in
S. On average (for large q) we have |T| ~ h/2. For any given p
in T, we suppose that prob(q is a primitive root of p) ~ 1/2.
The chance that for all p in T, {q is not a primitive root of p},
is on average (1-1/2)^(h/2) = 2^(-h/2) which rapidly goes to zero
as q grows.

--
jiw

[Helmut Richter]

On Tue, 6 Dec 2011, James Waldby wrote:

> I think the strength of the probabilistic argument (below) if
> correct is such that the conjecture itself is uninteresting if true,
> but its proof (rather than heuristic likelihood) would be highly
> interesting. If the conjecture were proved false, whether by
> counterexample or by theory, an explanation of the strange
> circumstances that make it false would be interesting.

Yet there are still two possibilities:

- either a *real* reason, that is, a relationship which makes the
probabilistic argument wrong

- or mere chance: there can be one counterexample even if the probability
of one is zero

Neither can be proved. the absence of relationships cannot, and the
absence of an accident cannot either.

--
Helmut Richter

[James Waldby]

On Tue, 06 Dec 2011 10:41:43 +0100, Helmut Richter wrote:
> On Tue, 6 Dec 2011, James Waldby wrote:

[re quasi's conjecture that for each prime q>2 there is a
prime p<q such that p is a primitive root of q, and q of p ]

Let C denote the conjecture and H the probabilistic argument.

Regarding possibility 1, If H is a wrong argument, the mathematical
thing to do is to show it is wrong. For the other possibility, the
mathematical thing to do is to explain how a counterexample (so far
hypothetical) can exist in spite of extreme odds against, or to
prove C is true or false, with or without a counterexample.

Anyhow, I think there are a few more than just two possibilities.
In the current state of proof, the several possibilities appear to
be: C may be true or false, and whichever it is, it may be proven,
not proven, or unprovable, provably or unprovably so. H predicts
C is true, which may be right or wrong, and the argument of H may
be correct or incorrect; in the latter case, there may be some
better argument H' that is correct, and H' may predict that C is
true or it may predict that C is false. Some of the possible
combinations are interesting, others boring or not useful.

--
jiw

[James Waldby]

[snip rest of completely-wrong stuff]

I corrected the errors in my probabilistic argument and posted it in
<http://math.stackexchange.com/questions/89056/>. If argument is
correct this time, B(x) < e^(-x/(d(x)^2*ln(x))), where
B(x) = probability that conjecture fails at q = x, and
d(x) = (e^gamma * log log x) + 3/(log log x).

--
jiw