Introduction to qSpoces


What are qSpaces?

qSpaces are directed graphs comprised of vertices and edges (also known as nodes and arcs).  There is a qSpace for every prime number, designated with the letter q.  For example, q7 is the qSpace generated by the prime number 7.  Similarly there are these qSpaces: q17, q103, q54882521, etc.

        Each qSpace is infinite in size, since the vertices in any qSpace are the set of prime numbers.


How are qSpaces formed?

The generating function for any qSpace is the function:


such that p, q & r are all prime,

where qs(p,q) = max(prdc(p*q+1)),

where prdc(n) is the set of prime factors of n,

and max(s) is the largest value in the set s.

For example, qs(13,7)=23 because 13*7+1 = 92,

and prdc(92)={2,2,23}, and max{2,2,23}=23.

Continuing this example, qs(23,7)=3 because 23*7+1 = 162, and prdc(162)={2,3,3,3,3}, and max{2,3,3,3,3}=3.

Therefore, in q7 there is an edge from vertex 13 to vertex 23; and there is another edge from 23 to 3.

It is immediately clear that ever y qSpace is unique.  While in q7 there is an edge from 13 to 23, in q29 there is an edge from 13 to 3, and an edge from 23 to 167.


Some properties of qSpaces

Since the function qs is defined for all primes, p; and the function yields a unique value for all input parameters, every vertex has exactly one from-edge.  We say that each vertex has exactly one (unique) successor.  Not immediately obvious is the fact that some vertices have many predecessor.

        For example, vertices 59, 151, 197 (and many others), are all immediate predecessors of 23.


Some interesting consequences

Perhaps the most surprising result from early exploration of the qSpaces, is that is seems that every qSpace has at least one cycle.  For example, in q7 we find this cycle:

    3 -> 11 -> 13 -> 23 -> 3

And, in q13 we find two cycles:

    19 -> 31 -> 101 -> 73 -> 19

This hypothesis has been tested and confirmed for the first 1 million primes.  Click here to see other examples of cycles in qSpaces.  At this point one might feel ready to call this working hypothesis a conjecture.


qSpace Conjecture

Every qSpace has at least one cycle.


Interesting graphs

When the partial graphs of some of the vertices of a qSpace are displayed using graph visualization software, interesting forms and shapes result.  Click here to see some of those graphical structures.

        Since there are an infinite number of primes, it is not possible to show an entire qSpace, since every qSpace has an infinite number of verices and edges.



In the qs function described above both p and q are prime numbers.  It is possible to relax that requirement and define a cqs function:


such that q & r are prime, but cp can be either prime or composite,

where qs(cp,q) = max(prdc(cp*q+1)),

where prdc(n) is the set of prime factors of n,

and max(s) is the largest value in the set s.



One of the advantages of considering cqSpaces is that it permits a simpler definition of predecessorship.  In cqSpace, if cp is a predecessor of r in q, then r|cpq+1 since r Î prdc(cpq+1).  Thus, r|q(cp+rk)+1, for all k>0 r; and r Î prdc(q(cp+rk)+1).  And, if r is the maximum integer in prdc(q(cp+kr)+1), then cp+kr is a predecessor of r; otherwise, it is not a predecessor.

For example, in q7, since cqs(3,7)=11,

11 Î prdc(7(3+11k)+1). We find in some cases that 11 is the maximum element of the prdc; in other cases it is not.  Thus, cqs(3+11,7)=11, cqs(3+22,7)=11, and cqs(3+44,7)=11; but, cqs(3+33,7)=23, cqs(3+55,7)=37, and cqs(3+77,7)=17.

This fact allows us to quickly find predecessors of 11 in q7.  p is a predecessor of 11 in q7 if p=3+11k, for k>0, p is prime, and 11 is the maximum element in prdc(7p+1).  Thus, 47, 113, 157, 311, and 509 are all predecessors of 11 in q7; but 179, 223, 421, 443, and 487 are not.


Ancestorship – i.e., sequence of subsequent predecessors

We saw above that if p is a predecessor of r in q, then r|pq+1;i.e., p*q%r=1. Since q and r are both prime, we know that k*q%r will take on all the values between 0 and r-1 as k goes from 0 to r-1.  In other words, it takes at most r probes to find an integer, k, either prime or composite, such that r|pq+1;  in other words, to find a predecessor for r in cqSpace.

And, from the discussion of predecessorship, we can use a predecessor in cqSpace to find a predecessor in qSpace.  This raises the question: Given a vertex at some prime, r, can we generate an unbounded sequence of ancestors of r?  This seems fairly likely, though the set of potential candidates gets sparser as r gets larger.

For example, in q7, let us produce a sequence of ancestors of 11 in q7.  We start with 3 -> 11.  Operating first in cqSpace, we find that 2*7%3=1, 5*7%3=1, 8*7%3=1, etc.  So, we try these values and find that cqs(5,7) = qcs(23,7) = cqs(41,7) = cqs(104,7) = cqs(185,7) = 3.  Transitioning  back to qSpace, we find that 5, 23 and 41 are all ancestors of 3.  Since 23 is in the cycle of q7, we use 5 instead.  So we have:

5 -> 3 -> 11

Continuing this process, we then find qs(2,q)=5.  So we have:

2 -> 5 -> 3 -> 11

And, after more iterations, we have:

929 -> 271 -> 73 -> 2 -> 5 -> 3 -> 11


Stub nodes

Since r=max(prdc(pq+1) it is clear that r is in the set prdc(pq+1); thus r|pq+1.  From this we can see that q has no predecessors in qSpace; otherwise we would have q|pq+1.

        We can call vertices (or nodes) which have no predecessors stub nodes.  And we can ask, are there any other stub nodes in qSpace for given q. 

What about 2? In order for 2 to be max(prdc(pq+1)), the prdc must be {2, 2, . . , 2}; i.e., prdc(pq+1)=2n.  Therefore, pq=2n-1. Can that condition be met for all qSpaces?



What would happen if we used an arbitrary integer, k, in place of 1 in the basic qSpace function?  In other words, we define:


such that p, q & r are prime, and k is any integer >1 ,

where qks(p,q,k) = max(prdc(p*q+k)),

where prdc(n) is the set of prime factors of n,

and max(s) is the largest value in the set s.

        It turns out that at least some of the resulting qkSpaces also have cycles.  For example, in q7-5 we find this cycle:

    41 -> 73 -> 43 -> 17 -> 31 -> 37 -> 11 -> 41

And, in q5-4 we find this cycle:

17 -> 89 -> 449 -> 173 -> 79 -> 19 -> 11 -> 59 -> 17


Explorations, questios & challenges

Within these qSpaces there are many avenues to explore, many questions to answer and many challenges to take on.  Here are some examples.

    – what causes cycling?

    – are there other stub nodes?

    – can a predecessor for 2 be found in all qSpaces except q2?

    – are there cycles for all (or most) q-k combinations?

    – challenge: find the longest cycle

    – challenge: find a qSpace that has no cycles

    – challenge: generate the longest branch in a given qSpace